Status
Done

实验目的

  1. 分析说明Nachos原有的线程调度策略。
  1. 设计并实现具有静态优先级的非抢占式线程调度策略。
  1. 以线程调试模式运行Nachos(./nachos -d t)，研究调试输出信息。上下文切换的次数与被测线程SimpleThread中打印输出的总行数一致吗？多余或缺少的上下文切换次数是什么原因造成的？请修改代码减少上下文切换的次数与被测线程SimpleThread中打印输出的总行数的差距。
  1. 在实现了前面优先级调度的基础上，若要求实现优先级调度的老化(aging)，请给出在Nachos中实现的具体方法(不要求实现可运行的代码。在实验报告中用文字描述即可，必要时可在文字中结合关键代码片段、数据结构、对象等说明)。
提示：List类中已有的SortedInsert方法可加以利用。
参阅：
code/lab2/n2
code/lab2/n2readme.txt
code/lab2/n2screen.txt
code/demo0/
《操作系统概念》第7版或第9版5.3.3节
注1：若Lab2全部完成，演示提交的代码是3中完成的。

实验步骤与内容

💡
TOW：线程操作fork、yield、sleep等
分类（线程操作、实现、Scheduler类中调度工作的完成、启动和调度模块分析switch、线程模块（thread文件）等
chaos！

分析说明Nachos原有的线程调度策略

测试程序运行与分析

  1. 运行初始Nachos程序，运行结果如下。 从输出看，程序中有两个线程（thread 0 和 thread 1）在并行运行。它们执行了一个循环任务，每次循环都打印其执行次数。不难得出Nachos默认的线程调度策略为FIFO调度策略
      2. notion image
  1. 对应线程测试代码如下
      2. 测试代码中启动了一个SimpleThread线程，并设置which参数为1（代表当前的线程编号），对应的控制台输出即为thread 1。
      在控制台输出中另外还有一个thread 0线程，线程名称为main，乃主线程，也是ThreadTest函数运行的当前线程，定义在system.cc的149行
 

Nachos线程调度实现

当nachos运行时，首先进入thread模块下的main函数，，随后调用system.cc中的 Initialize 函数，用于初始化 Nachos 系统
可以看到，Initialize()函数初始化了一个Scheduler类作为全局调度者，Scheduler维护一个就绪线程队列，当一个线程可以占用处理机时，就可以调用ReadyToRun方法把这个线程放入就绪线程队列，并把线程状态改成就绪态。
线程的调度与线程插入就绪队列、线程切换的代码有关，我们找到Scheduler.cc文件，可以看到scheduler有以下三个函数完成调度工作，下面对三个函数分别进行分析：
  • Scheduler类
    • Thread* FindNextToRun();
        • 从就绪队列中选择下一个要运行的线程。函数返回下一个要运行的线程对象。如果没有线程可用，则返回 NULL。
        但在该算法中，没有提及线程的调度，那就一定在准备序列中调度，于是找到ReadyToRun()函数
    • ReadyToRun(Thread* thread);
        • 将线程标记为就绪状态(READY)，并将其加入到就绪队列中，等待调度。
        在复杂系统中，调度算法可能会根据线程的优先级或其他策略进行选择。但在这段代码中，默认调度策略为 FIFO，不涉及线程优先级的判断。
    • void Run(Thread* nextThread);
        • 该函数的作用是先保存当前线程状态，令其下处理机，并恢复nextThread的状态，令其上处理机运行，并加载其线程状态为RUNNING。并消灭死亡的线程。其中调用SWITCH方法完成上下文切换，该方法由汇编语言实现
    SWITCH的语法是这样的：
    其中t1是原运行线程指针，t2是需要切换到的线程指针。线程切换的三步曲是：
    1. 保存原运行线程的状态
    1. 恢复新运行线程的状态
    1. 在新运行线程的栈空间上运行新线程

    Nachos线程模块分析

    Thread类实现了操作系统的线程控制块，同操作系统课程中进程程管理中的PCB (Process Control Block) 有相似之处。但Thread线程控制类较PCB为简单的多，这是因为一个Nachos线程是在宿主机上运行的，无论是系统进程还是用户进程，Thread线程控制类的实例都生成在宿主机而非虚拟机上，所以不存在实际操作系统中proc结构常驻内存，而user结构可以存放在盘交换区上的情况，将原有的两个结构合并是Nachos作的一种简化。
    线程状态有四种，状态之间转换如图
    notion image
    JUST_CREATED
    线程初始时的状态。此时线程控制块中没有任何内容
    RUNNING
    线程正在处理机上运行
    READY
    线程处理就绪态
    BLOCKED
    线程处于阻塞态
    1. Thread()构造函数
        2. 创建线程
    1. Fork()
        2. 用于创建一个新的线程，并将它放入就绪队列，使得该线程可以和调用者线程并发执行。
        StackAllocate()函数则负责对线程的执行栈进行分配和初始化，确保在栈上设置正确的入口函数和参数，以便后续的上下文切换操作（SWITCH()函数）能够正确地执行新线程的功能。
        💡
        Fork()函数中，有两个参数：VoidFunctionPtr func和_int arg ，它们分别定义新线程要执行的函数以及传递给该函数的参数
    1. yield()
        2. 让线程在它不再需要独占CPU时让出控制权，以使其他线程能够有机会执行。
        调用interrupt->SetLevel(IntOff)关闭中断，这样在查找下一个线程和执行上下文切换的过程中不会被打断。调用scheduler->FindNextToRun()查找就绪队列中的下一个线程。如果找到了就绪的线程，则调用scheduler->Run(nextThread)进行上下文切换，否则恢复中断。
    1. sleep()
        2. 将当前线程从可运行状态（RUNNING）转换为阻塞状态（BLOCKED）。通常用于需要等待某些外部事件（例如 I/O 操作完成）时。 首先设置当前线程状态为BLOCKED，表示当前线程由于某些原因（如等待某个条件或资源）而无法继续执行；然后调用scheduler->FindNextToRun()查找就绪队列中的下一个线程，并通过scheduler->Run(nextThread)进行上下文切换。如果没有就绪线程，系统会调用interrupt->Idle()进入空闲状态，等待新的中断发生。
    1. finish()
        2. 用于在线程完成它的任务时清理资源，但它并不立即删除自己，因为它仍然在其执行栈中运行。
        当调用Finish()时，当前线程并不会立即被销毁。取而代之的是设置一个标志变量threadToBeDestroyed，这使得调度器在下次运行其他线程时销毁该线程；接下来调用sleep() 函数使当前线程阻塞，以让出CPU给其他线程。
        💡
        这种设计是因为直接销毁当前线程会涉及到销毁它的栈空间，而这个栈空间本身还在使用中，因此不能直接销毁。

    FIFO调度机制分析

    在nachos默认实现中，调用ReadyToRun后，将新线程append到就绪队列的尾部，而后当thread类执行线程切换时（在Sleep和Yield函数中），先调用FindNextToRun()函数在readyList队列头取出一个线程（并将其从队列中删除），然后调用Run函数运行它，实现了FIFO的线程调度机制。
    例如，在Yield()函数中，先关中断，然后获取下一个要运行的线程。如果其存在，则将当前线程加入到就绪队列尾部，然后运行下一个要运行的线程。最后开中断。

    设计并实现具有静态优先级的非抢占式线程调度策略

    Nachos默认调度策略是不具有优先级的，因此为实现具有优先级的调度，应该在Thread类中为线程加入优先级字段priority；线程的优先级priority为0-99，0最高，99最低。默认优先级为9，可在Thread类的构造函数中设置。
    由于成员变量priority的可见性为private，所以为其添加getter和setter方法以实现外部访问
    与此同时，需要重新编写Thread类的构造函数，以便在创建线程时就可以指定其优先级
    在第一部分中，我们了解到Nachos默认情况下ReadyToRun函数始终将新线程插入到就绪队列readyList的末尾，此处需要修改插入方式，采用SortedInsert函数，sortKey指定为线程的优先数，实现按优先数插入
    接下来更改ThreadTest文件，运行多个具有不同优先级的线程
    得到运行结果如下
    notion image
    main线程首先执行，执行一次后放弃CPU。由于Yield函数要求在一个线程放弃CPU后，将控制权转交给另一个非自身的线程，所以接下来两个优先级最高的线程交替执行，待这两个线程执行结束后，由优先级次高的两个线程交替执行。待这些线程执行结束后，优先级最低的线程4才开始运行。

    分析上下文切换次数，并修改代码减少该次数

    💡
    为了便于计数，此处将线程d删去，仅保留main、a、b、c四个线程
    使用调试模式运行，得到程序的调试信息
    通过查找Switching开头的输出行，即可快速确定上下文交换的次数；共计进行了23次上下文切换；
    通过查找***开头的输出行，即可确定打印输出的总行数，共计输出了20行。
    不难看出，在某些情况下，上下文切换选择并调度一个线程，但该线程并未有信息需要输出，而是直接退出（即调用currentThread->Finish()）。这时退出时需要执行Yield以便由其他程序删除退出线程，从而再次发生上下文切换，这便是上下文切换次数多于实际线程输出次数的原因。
    例如
    在一个线程完成输出后，总是调用Yield函数将CPU使用权转让给另一个线程。当最后一次输出（num=4）后，仍然调用该函数转让CPU，此时该线程以及没有需要输出的内容了，却依旧被转换为READY状态，等待下一次切换。
    所以优化思路也非常清晰了，就是省去最后一次的Yield函数调用，转而让线程直接退出。
    修改后调试信息输出如下
    可以看到，在执行完所有输出后，便直接切换为线程c，通过增加判断语句成功减少了上下文切换次数。再次计数可以得知，修改后的代码调试信息共计输出了20行，进行了19次上下文切换。缺少的一次上下文切换是由于最后执行的进程c没有可切换的线程

    实现优先级调度的老化

    优先级调度的老化（Aging） 是一种调度算法的技术，用于解决优先级调度中 低优先级线程或进程“饿死” 的问题。
    老化是一种动态调整进程优先级的技术。其基本思想是随着等待时间的增加，逐渐提高进程或线程的优先级，以确保它们最终可以获得 CPU 的执行机会。也就是说，优先级会根据任务等待的时间逐渐增加，这样即使是原本优先级较低的任务，经过长时间等待后，其优先级也会被提高到足够高，进而获得 CPU 资源。 老化有两种实现方式：其一是提高长期未执行的线程的优先级；其二是降低长时间占用CPU的线程的优先级。由于遍历readyList寻找长期未执行的线程复杂度较高，故采用第二种方法。
    首先在Thread类中加入aging变量，初始值为0，并编写相应的getter和setter函数
    编写一个AddAging()函数，目的是增加该线程的aging值，从而减少它在CPU上运行的机会。并在Run()函数执行上下文切换前调用它。
    此外，线程插入就绪队列的顺序也需要进行修改，此处以优先数+老化值作为sortedKey来计算实际优先数，随着线程在CPU上运行的时间越长，老化值越大，实际优先数越高，从而线程的优先级越低。以此实现避免其过度占用CPU资源的情况
    新的运行结果如下，可以看到当优先级较高的线程（线程1、2）运行一段时间后，优先级较低的线程（线程3）也得到了上CPU运行的机会
    notion image

    结论分析和体会

    本次实验分析了Nachos线程调度策略，并通过编写代码将其由FIFO改为了优先级调度策略，并设计了线程老化的思路。通过实验，我们了解了nachos的线程切换、线程调度、线程休眠等实现，进一步理解了真实操作系统中进程、线程有关的操作和实现。
     
    Loading...