CS 537项目5——调度器 代写

程序代写

该文档是关于CS 537项目5——调度器的说明，介绍了项目的截止日期、提交方式、测试相关信息、协作要求等管理事项。项目基于扩展了多线程功能的xv6操作系统进行，目标是解决优先级反转问题，具体包括实现用户空间的睡眠锁、添加调整当前程序优先级的nice系统调用以及修改xv6调度器以考虑进程的优先级和优先级继承。文档还详细说明了新系统调用clone()的功能和工作原理，以及用户空间睡眠锁、nice系统调用和优先级继承在调度器中的实现细节和测试方法。

管理事项

  • 截止日期：4月2日，晚上11:59。

  • 项目最多可延迟3天提交，但每延迟一天将被扣10个百分点。

  • 延迟天数：

    • 如果您需要在项目上额外的时间，每个人将有2天的个人项目延迟天数和3天的小组项目延迟天数（本学期总共5天延迟天数）。在截止日期后，我们将为按时评分复制提交目录的副本。
    • 要使用延迟天数，您需要在常规项目提交目录中提交一个额外的文件slipdays.txt。该文件应该只包含一件事，即一个数字，表示您想要使用的延迟天数（即1或2）。每天我们都会复制任何包含这些slipdays.txt文件的目录的副本。
    • 在使用完延迟天数后，如果延迟1天提交，您最多可以获得90％的分数；延迟2天，最多可以获得80％的分数；延迟3天，最多可以获得70％的分数。3天后，我们将不再接受提交。
    • 任何例外情况都需要向教师请求。
    • slipdays.txt的示例：
    1

  • 在~cs537 - 1/tests/P5提供了一些测试。该目录中有一个README.md文件，其中包含运行测试的说明。测试部分完成，鼓励您创建更多测试。

  • 问题：我们将使用Piazza回答所有问题。

  • 协作：作业可以自己完成，也可以与一个伙伴一起完成。复制代码（从他人处）被视为作弊。阅读此内容以了解更多关于什么是可以的，什么是不可以的信息。请不要这样做，帮助我们大家度过一个愉快的学期。

  • 这个项目将在Linux实验室机器上完成，因此您可以在典型的基于UNIX的平台（Linux）上学习更多关于C编程的知识。您的解决方案将在这些机器上进行测试。

  • 提交方式：

    • 将所有xv6文件（不仅仅是您更改的文件）复制到~cs537 - 1/handin/<cslogin>/P5/ – 在运行make clean之后。目录结构应如下所示：

      handin/<cslogin>/P5/
    |---- README.md 
    |---- resources.txt
    |---- xv6 - public
          | ---- 包含您修改的所有xv6内容

    • 小组项目提交：每个小组只需要提交一次。要提交，一个人应该将代码放在他们的提交目录中（另一个人应该为空）。

  • 注意：对于这个项目，提供了一个具有多线程功能的修改后的xv6。请不要在原始的xv6上工作。

介绍

在这个实验中，我们将深入研究xv6（一个简单的类Unix教学操作系统，已扩展为支持线程）上下文中的优先级反转的复杂性。您的任务是实现关键功能，以探索和减轻优先级反转的影响。这个实验包括创建一个用于用户空间的睡眠锁，引入一个nice系统调用来调整调用进程的nice值（从而间接调整其优先级），并修改xv6调度器，以根据其有效优先级（考虑其nice值和优先级反转的动态）来优先处理进程。通过这些练习，您将获得高级操作系统概念的实践经验，增强xv6调度器以更熟练地处理优先级反转并提高整体系统性能和公平性。

目标

  • 理解优先级反转和优先级继承。
  • 理解xv6中sleeplock的实现。
  • 理解xv6中的上下文切换。
  • 实现修改进程状态的系统调用。

背景：优先级反转和优先级继承

优先级反转发生在高优先级任务被迫等待低优先级任务释放共享资源时，导致执行顺序与基于优先级的计划相反的情况。 想象一个在多任务操作系统中的场景，一个低优先级任务，任务L，持有一个共享资源的锁。一个高优先级任务，任务H，最初不需要锁定的资源，最终尝试访问它并被阻塞，因为任务L持有锁。同时，不需要共享资源的中优先级任务继续运行，有效地进一步延迟任务H。这个场景说明了一种违反直觉的现象，即低优先级任务间接抢占了高优先级任务，导致任务管理效率低下和潜在的系统减速。

优先级继承是一种旨在减轻优先级反转影响的策略解决方案。通过此协议，当高优先级任务等待低优先级任务锁定的资源时，系统会暂时将低优先级任务的优先级提升到最高优先级等待任务的优先级。这种调整有助于确保低优先级任务能够更快地完成执行并释放资源，从而减少高优先级任务的等待时间。 一旦低优先级任务释放共享资源，其优先级将恢复到原始级别，高优先级任务可以继续执行，从而保留系统调度策略的整体完整性和效率。

项目细节

在这个项目中，您的任务是通过引入机制来减轻优先级反转来增强xv6操作系统。具体来说，您将： 1. 实现一个可以在用户空间中使用的睡眠锁。 2. 开发一个nice系统调用来调整当前程序的nice值，影响其调度优先级。 3. 修改xv6调度器，以考虑进程的nice值和优先级继承。

新系统调用：clone()

提供了一个修改后的xv6版本，具有新的系统调用clone，便于创建线程。

使用clone()创建多线程程序

clone()允许在与父进程相同的虚拟地址空间中在新线程中执行一个函数。与fork()不同，clone()共享调用进程的地址空间，因此需要明确的堆栈管理。 新系统调用clone()的函数原型为：

int clone(void (*fn)(void*), void* stack, void* arg)

它在新线程（与父进程共享相同的虚拟地址空间）中执行由fn指定的函数，并提供由arg提供的参数。 由于子进程和调用进程可能共享内存，因此子线程不可能在与调用进程相同的堆栈中执行。因此，调用进程必须为子堆栈设置内存空间，并将指向此空间的指针传递给clone()。堆栈向下增长，因此stack通常指向为子堆栈设置的内存空间的最高地址。请注意，clone()没有提供一种方法，使调用者可以告知内核堆栈区域的大小。 这里是一个展示如何创建多线程程序的示例

void fn(void* arg) {
 ...;
  // 请使用 `exit` 终止
  exit();
}
int main() {
  char* stack = (char*)malloc(4096);
  int tid =
      clone(fn, stack + 4096, 0);
  if (tid < 0) {
    printf(2, "clone error");
  }
  wait();
  exit();
}

一个示例多线程程序也在文件multithread.c中提供。 此函数旨在类似于Linux上的clone(2)。

理解clone()的工作原理

进程表插槽分配：在调用时，clone()在进程表（在proc.c中特别提到为ptable，第10行）中搜索未使用的条目来注册新线程。 虚拟地址空间共享：它为新线程分配与父进程相同的页目录指针，确保它们共享相同的虚拟地址空间。 堆栈和执行设置：clone()然后通过将为指定函数（fn）提供的参数（arg）推送到新线程的堆栈上，初始化线程的堆栈。它调整堆栈指针和指令指针，以确保在启动时，线程在fn中开始执行，使用自己的私有堆栈空间。 线程终止和页表管理：当一个线程终止时，系统检查是否有其他线程仍在共享相同的页表。这是通过与每个页表相关联的引用计数来完成的。如果终止线程是最后一个使用页表的线程（即，引用计数降至0），则页表将被系统回收。

用户空间睡眠锁

xv6在sleeplock.c和sleeplock.h中提供了一个sleeplock，可在内核中使用。然而，这个锁不能直接从用户空间程序访问。为了弥补这一差距，您将实现用户空间变体的睡眠锁。 用户空间睡眠锁接口：

  • 定义锁结构： 首先在您的代码中定义一个锁结构。这个结构将代表锁的状态和所有权。您将typedef这个结构为mutex。

    typedef struct {
  // 锁状态、所有权等。
} mutex;

  • 初始化锁： 定义一个函数minit用于初始化mutex。这个函数将锁设置为未锁定状态，并准备任何必要的内部结构。

    void minit(mutex* m);

  • 获取锁（macquire）： 一个线程调用macquire来获取锁。如果锁可用，线程获取它并继续执行。如果另一个线程持有锁，调用线程将被置于睡眠状态，直到锁可用。

    void macquire(mutex* m);

  • 释放锁（mrelease）： 持有锁的线程在完成其临界区后调用mrelease。此操作释放锁并唤醒任何在等待锁可用时处于睡眠状态的线程。

    void mrelease(mutex* m);

    推荐的方法是将minit实现为用户级函数，同时将macquire和mrelease实现为系统调用。 为了使这些功能可访问，确保用户程序可以通过包含user.h来使用这些函数和结构。 这里是使用mutex的示例： “`c

#include “user.h” mutex m; void fn(void* arg) { macquire(mutex* m); // 临界区 void mrelease(mutex* m); exit(); } int main() { minit(&m); … if (clone(fn, stack + STACK_SZ, 0) < 0) … }

在实现锁之后，您可以使用`test_1`、`test_2`和`test_3`测试您的解决方案。

#### 附加说明
- 在实现此功能时，参考`sleeplock.c`和`sleeplock.h`中现有的睡眠锁实现以获取灵感是有益的。
- 您不需要处理在持有锁时创建子进程或线程的情况。

### `nice`系统调用
`nice`系统调用旨在调整调用线程的优先级。它的功能如下：
- 函数原型：
  ```c
  int nice(int inc);
  • 功能 目的：nice()通过将inc添加到调用线程的nice值来修改它。 优先级影响：nice值影响线程的优先级，其中较高的nice值对应较低的优先级。 范围：nice值的范围可以从+19（表示最低优先级）到-20（表示最高优先级）。 默认值：最初，每个线程的nice值为0。 范围限制：如果尝试设置超出允许范围的nice值，该值将调整为范围内的最近限制（+19或-20）。
  • 返回值： 成功：如果操作成功，返回0。 错误：如果出现错误，返回-1。此行为与Linux上的nice实现不同。

使调度器nice感知

xv6的默认调度器使用轮询策略，不考虑每个进程的优先级。由于现在线程/进程具有优先级属性，调度器应该意识到这一点。这意味着它现在应该根据它们的优先级值来优先处理进程和线程。 具体来说，在每个调度决策（tick）中，调度器必须选择具有最低优先级值的线程或进程来运行下一个。这种选择优先考虑具有更高重要性的任务。 如果多个线程或进程共享相同的最低优先级值，调度器应该恢复到轮询方法来处理这些任务，确保它们之间公平分配CPU时间。 确保修改后的调度器对进程和线程一视同仁，对两者应用相同的优先级规则。 在调度中适应优先级后，您可以使用test_4~test_9测试您的解决方案。

在调度器中实现优先级继承

如背景中所述，当高优先级线程等待锁时，调度器应优先考虑锁持有者。 这里我们以test_10为例，说明优先级继承是如何工作的，以及您如何编写更多测试来测试您的解决方案。


#include "types.h"

#include "user.h"
mutex m;
void fn1(void* arg) {
  nice(10);
  macquire(&m);
  // 一些工作...
  mrelease(&m);
  exit();
}
void fn2(void* arg) {
  sleep(3);
  nice(-10);
  macquire(&m);
  // 一些工作...
  mrelease(&m);
  exit();
}
int main() {
  char* stack1 = (char*)malloc(4096);
  char* stack2 = (char*)malloc(4096);
  clone(fn1, stack1 + 4096, 0);
  clone(fn2, stack2 + 4096, 0);
  sleep(6);
  // 一些工作...
  wait(); wait(); exit();
}

在这个示例中，main首先创建2个线程。线程1执行fn1，线程2执行fn2。主线程和线程2首先被阻塞一段时间，因此唯一可运行的线程1被调度。线程1降低其优先级并成功获取锁。当线程2有机会运行时，它提高其优先级并尝试获取锁。由于锁已被线程1持有，线程2被置于睡眠状态以等待锁可用。然而，由于高优先级线程线程2正在等待线程1，线程1的优先级现在被提升，并且在调度时，线程1应该比具有中等优先级的主线程更受青睐。在线程1完成后，线程2将成功持有锁，并被调度，因为它具有比主线程更高的优先级。 具体来说，在这个项目中，锁持有者的临时优先级（优先级值）被调整为与所有等待该锁的线程中的最高优先级（最低优先级值）相匹配。从数学上讲，这表示为： elevated_nicelock holder = mint waits on locknicet 如果一个线程持有多个锁，其临时优先级将提升到所有等待其持有的任何锁的线程中的最高优先级。 请注意，我们不考虑嵌套提升。例如，假设t1的优先级为0持有锁l1，t2的优先级为-1持有锁l2并等待l1，t3的优先级为-2等待l2。t2的提升优先级为-2，因为t3等待t2持有的锁。然而，t1的提升优先级为-1而不是-2，因为只有t2直接等待t1。 在锁持有者释放锁后，其优先级应恢复。 为了简化项目，我们假设一个线程同时持有不超过16个锁。 在实现优先级继承后，您可以使用test_10测试您的解决方案。

提示

  1. 推荐的工作流程是按照指令的结构方式进行：
    • 了解xv6中sleeplock的工作原理，并实现您自己的可在用户空间中使用的版本。
    • 添加nice系统调用并更改调度器以考虑优先级。
    • 在调度时使用提升的优先级而不是简单的优先级来解决优先级反转。 在处理您的睡眠锁之前，请确保您了解sleep和wakeup的工作原理以及proc结构中chan的作用。 在处理调度器之前，您应该已经知道scheduler()如何进行轮询调度以及为什么swtch()可以切换进程。
  2. 对于优先级继承，调度器需要知道进程之间的等待关系。因此，关于睡眠锁的