pintos抢占式优先级

中山大学移动信息工程学院本科生实验报告

（2016学年秋季学期）

课程名称：Operating System 任课教师：饶洋辉批改人(此处为TA填写)：

目录：

一、实验目的

二、实验过程

1.Test分析

1)priority-preempt分析

2)priority-change分析

2.函数修改

1)thread_create()修改

2)thread_set_priority()修改

三、实验结果

四、问答题

五、实验感想

一、实验目的

原始Pintos系统对线程的调度采用最简单的FCFS策略，在本实验中，需要为Pintos建立抢占式优先级调度机制，确保任何时刻CPU上运行的都是最高优先级线程。通过对本实验的完成，掌握优先级机制的原理，加深对各等待队列的了解

二、实验过程

1.Test分析

先通过阅读test代码，把握线程的整体结构，然后再做函数修改实现实验目的

1)priority-preempt分析

这个test是为了测试，最高优先级的线程是否真的抢占

首先看看test_priority_preempt()函数

第一个ASSERT出现thread_mlfqs，在thread.h中找到定义

thread_mlfqs表示调度制度，true则采用多级反馈调度程序，false则采用循环调度程序，那么可以得到这个ASSRT是确保采用的是多级反馈队列调度。那么多级反馈队列调度是什么呢？

在我们所学的调度算法中，多级反馈队列调度算法允许进程在队列直接移动。是根据不同的CPU区间的特点来区分进程。第一，如果进程使用过多的CPU时间，那么它就会被转移到更低优先级队列；第二，在较低优先级队列中等待时间过程的进程会被转移到更高优先级队列中去。总之，多级反馈队列调度阻止了饥饿的发生，也提高了CPU的利用率。

再来看第二个ASSERT，保证当前线程优先级不是默认优先级PRI_DEFAULT，即最高优先级

接着用thread_create()函数创建一个新线程，其优先级为PRI_DEFAULT+1，即保证新创建的线程是当前ready_list中优先级最高的线程，应当发生抢占，故而开始执行该线程的内臵函数simple_thread_func()（在该test中实现）

可以看出，test的输出顺序应该是，先输出thread 0~4线程的msg信息，循环后再输出‘Thread high-priority done！’，随后该抢占的线程运行完毕，再回到test_priority_preempt()中，输出最后一条msg(‘The high-priority thread should have already completed.’)

可是输出结果中并没有发生抢占，这就说明我们在thread_create()中就应该判断新创建线程的优先级是否高于当前CPU运行线程，进而判断是否进行抢占

2)priority-change分析

这个test是为了验证当降低当前拥有最高优先级线程的优先级时，CPU是否会被立即抢占首先来看看test_priority_change()函数的实现

首先和priority-preempt.c中一样，ASSRT来确保系统采用的是多级反馈队列调度。其次创建了一个新线程，其优先级设臵为PRI_DEFAULT+1（即当前有最高优先级的线程），故而应该发生抢占，开始执行changing_thread()函数

而changing_thread()中又降低了该线程的优先级变为PRI_DEFAULT-1，故而该线程的优先级小于父线程的优先级(PRI_DEFAULT)，故而又被抢占，CPU开始继续执行test_priority_change()函数剩余的部分

而父线程的优先级又被降低PRI_DEFAULT-2，故而子线程又发生抢占，再继续执行changing_thread()剩余部分，输出msg执行完成，然后再回到test_priority_change()中输出最后一条msg。

整理一下输出顺序：

首先输出:

新create的子线程优先级最高，发生抢占，输出：

子线程的优先级被降低，父线程发生抢占，输出：

父线程的优先级被降低，子线程发生抢占，输出：

子线程执行完毕，继续执行父线程，输出：

执行原版本的test，运行结果如下：

可以看到，在新create线程和更改线程优先级后，并没有发生抢占，因此，可以知道，我们需要更改thread_set_priority()函数，使得在设臵线程优先级后，就判断是否优先级最高，进而判断是否需要抢占

2.函数修改

通过之前的test分析，我们需要理清楚了哪些情况下需要考虑优先级调度：

1)当线程A 占用CPU 时，有一个更高优先级的线程B 进入ready_list，则原线程必须立即

让出CPU，而B 线程占用CPU。这种情况的发生原因有二，一是新线程的生成，二是一个线程被唤醒进入ready_list。后一原因暂且先只考虑调用thread_unblock()进行唤醒的情况

2)当一个线程正在运行时，若其优先级被改变（降低），以至于其优先级比ready_list中队首

线程的优先级还要低，则让出CPU

故而我们的目标是：

1)当操作系统新创建线程(thread_create()函数)，操作系统也需要做相应的检测。每一次创

建线程，并加入ready队列后，检测这个加入ready队列的线程的优先级是否大于当前线程，若是，则当前线程退出CPU

2)通过重新设计thread_set_priority()函数，每次修改当前线程的优先级，检测新优先级是否

小于ready队列中最高优先级的线程的优先级，如果小于，则当前线程让出CPU

下图为具体调用关系;

开始函数分析与修改：

1)thread_create()中

先来看看原函数的实现：

第一部分，声明各种变量，给thread t分配空间

上面与优先级关系不大，大致说明，就是用palloc_get_page()给t分配了1个的空页，因为这里传入的palloc_flags是PAL_ZERO，故而该页面充满了0。那为什么要用分页的行为来分配空间呢？

分页的基本方法就是将逻辑内存(页)和物理内存(帧)分为同样大小的块，当需要执行进程的时候，其页从备份内存中调入到可用的内存帧中。这样就避免了将不同大小的内存块匹配到交换空间上这样的麻烦，分页内存管理方案通过允许物理地址空间为非连续，从而有效解决了外部碎片问题。

接着thread_create()中，初始化线程t

这里出现了allocate_tid()函数，就是为了给当前线程的贴标签，现在tid持有了这个新线程的标签

接着，intr_disable()和intr_set_level()两行配套使用，保证这两行之间为一个原子性操作不可被中断。这中间就是通过初始化这个thread的栈来为其首次run做准备，因为这个过程是自动的，所以中间值stack成员是不能观察到这个过程的。这里与优先级关系不大，故不再详解。

在上次实验中，实现优先级调度，已经实现了每次将线程插入就绪队列中，都以优先级顺序插入，所以在thread_create()函数中，只需要在最后加上新线程优先级与当前运行线程优先级的比较，若高于当前运行线程，调用thread_yield()使其让出CPU即可

（这里的thread_yield()函数，在上次实验报告中剖析的很清楚，其实就是把当前线程扔到就绪队列里，然后重新schedule()，注意这里如果ready队列为空的话当前线程会继续在CPU执行）

函数修改如下：在末尾的返回tid之前加入

2)thread_set_priority()中:

先贴出原函数的实现：

可以看到，原函数中只是设臵了当前线程的优先级，并没有做其他的改变，我们需要的是在设臵优先级后，将加入的新优先级线程与ready_list队首的线程优先级比较，若新优先级低于队首线程的优先级，则调用thread_yield()函数切换

函数修改如下：修改当前线程的优先级后，加入

三、运行结果

1.总test通过结果：

2.priority-preempt测试结果：

一个新的线程被创建，优先级高于父线程故而抢占，输出循环结果0-1的迭代过程msg，子线程运行完后输出运行完毕msg，然后回到父线程继续运行，输出运行完毕msg(如图，橙色表示子线程运行输出，其余为父线程运行输出)

3.priority-change测试结果：

一个新的线程被创建，输出创建msg，优先级高于父线程故而抢占，而后输出降低优先级msg后，父线程优先级高于子线程优先级故而再次抢占，回到父线程输出子线程优先级低的msg，而后父线程的优先级降低，子线程再次抢占父线程，输出子线程thread2结束msg后，回到父线程继续运行，输出子线程刚刚运行完毕msg，结束（如图，橙色表示子线程运行输出，其余为父线程运行输出）

四、问答题

1.如果不考虑thread_create的情况，test能通过吗？如果不能，会出现什么结果(请截图)，

并解释为什么会出现这个结果？

不考虑create过程的test结果，则两个test都无法pass，原因是当线程A占用CPU 时，有一个更高优先级的线程B被创建进入ready_list，B线程没有立即抢占CPU

2.什么是PV操作？什么是信号量

1)信号量：

为什么会有信号量呢？为了防止出现因多个程序同时访问一个共享资源而引发的一系列问题，我们需要一种方法，它可以通过生成并使用令牌来授权，在任一时刻只能有一个执行线程访问代码的临界区域。临界区域是指执行数据更新的代码需要独占式地执行。

而信号量就可以提供这样的一种访问机制，让一个临界区同一时间只有一个线程在访问它，也就是说信号量的使用主要是用来保护共享资源，使得资源在一个时刻只有一个进程（线程）所拥有，从而解决进程同步与互斥问题。

信号量由一个值和一个指针组成，指针指向等待该信号量的进程。信号量的值表示相应资源的使用情况。信号量S>=0时(S表示可用资源的数量)。

2)PV操作：

进程通常分为就绪、运行和等待(一般为阻塞)三个工作状态。三种状态在某些条件下可以转换，三者之间的转换关系如下：

进程三个状态之间的转换就是靠PV操作来控制的。PV操作主要就是P操作、V操作和信号量。其中信号量起到了至关重要的作用。

P操作：请求分配一个资源。将信号量S的值减1，即S=S-1；如果S>=0，则该进程继续执行；当S<0时，表示已经没有可用资源，该进程臵为等待状态，排入等待队列，S的绝对值表示当前等待该资源的进程数。请求者必须等待其他进程释放该类资源，才能继续运行。

V操作：释放一个资源。将信号量S的值加1，即S=S+1；如果S>0，则该进程继续执行；

若S<0，表示有某些进程正在等待该资源，因此要唤醒一个等待状态的进程，使之运行下去。

五、实验感想

1.在分析抢占式优先级时，发现需要考虑优先级调度的还有一种情况：当多个线程因为等待同

一把锁、同一个信号量或同一个条件变量而被阻塞时，当需求满足时，应该以优先级由高到低方式唤醒线程进入ready_list，当其进入ready_list，就会引发前面所提到的第一种优先级调度情况。(这里则没有继续更改)

2.优先级是目前操作系统中经常用到的机制，在Pintos 中引入优先级机制，关键在于理清有

哪些对各等待队列的插入和取出操作

3.因为有了上次大篇幅的分析，这次的test就比较简单，主要涉及的就是优先级的抢占，以及

进程同步问题中的PV操作，主要的感想都写进了分析中，所以也没有什么好水的了。