开发者学堂课程【高校精品课-西安电子科技大学-操作系统课程设计：priority task1课程】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/74/detail/15854
priority task1课程
这节课主要学习线程的优先级调度。通过本次实验，希望可以对操作系统的优先级调度机制有更加深入的了解。
任务简介
原始 Pintos 操作系统中对于线程的调度，没有考虑优先级的问题，而是采用最为简单的 FCFS（先来先服务）策略。显然通过这样简单的策略无法满足复杂操作系统正常运行的调度需求。
本次实验要求为 Pintos 操作系统建立一个合理的优先级调度机制，确保任何时刻 cpu 上运行的都是最高优先级线程。
1、Pintos 线程优先级
在正式介绍本次任务的实验方案之前，可以先观察在 Pintos 操作系统中如何进行线程优先级的设置。
首先是关于线程优先级的定义，在线程部分的源码中可以看到 Pintos 操作系统已经在 in thread.h 文件中定义了线程的优先级属性，这样的优先级属性可以直接使用。
Pintos 操作系统对于线程的优先级有0到63总共64个线程的优先级。当优先级等于0时，表示当前线程为最低优先级；当优先级等于31时，表示当前线程为默认优先级；当优先级为63时，代表当前线程为最高优先级。
通过在线程结构体中加入优先级的定义，可以实现一个具有优先级大小的线程。
2.线程生成时
在操作系统运行时，存在两种情况需要设置线程的优先级。
生成线程时需要生成具有优先级大小的线程，通过在线程的创建函数中传入优先级参数，然后通过调用初始化线程函数得到具有优先级的线程，这样的优先级称为初始优先级。
3.线程优先级设置
在线程执行过程中 Pintos 操作系统还可以通过thread_set_ priority（函数）修改当前线程的优先级。在 Pintos 操作系统源码中已经提供了设置优先级函数的原型，但是此函数的功能，只是简单修改当前运行线程的优先级数值，而没有真正实现优先级调度的功能。
4.何时优先级会对线程调度产生影响
正式介绍本次任务的实验方案，通过分析何时优先级会对线程调度产生影响，以此来确定本次实验任务所需要修改的 Pintos 操作系统源码。在操作系统中，导致线程优先级发生了变化的原因有很多，这与具体的操作系统调度策略有关。
在实际运行时，Cpu 会依次运行 ready-list，也就是就绪队列中的首线程。所以当线程的就绪队列发生变化时，可能会对 cpu 的运行产生影响。通过下图可知，当有新线程进入就绪队列或者阻塞线程唤醒时，都有可能改变线程的就绪队列。
在 Pintos 操作系统中，大概会有以下四种情况需要增加线程的优先级调度机制。
（1）新线程生成时
第一种情况：当创建一个新线程时，新生成的线程需要和就绪队列中的线程优先级进行比较，确定运行中的线程是否让出 cpu。如果新线程的优先级更高，则源线程必须立即让出 cpu 资源，使新线程抢占 cpu 资源。所以在 Pintos 操作系统源码中，需要修改创建线程的相关逻辑。
（2）ready-list 的有序化
第二种情况：就绪队列的有序化，当一个线程让出 cpu 或者阻塞线程被唤醒时，这个线程需要重新进入线程的就绪队列中。当有新线程进入就绪队列中，就绪队列都需要对队列中的线程优先级进行重新排序，确保高优先级线程为就绪队列中的首线程。所以在线程的让步逻辑与唤醒逻辑中都需要加入线程的优先级调度机制。下图可以得知线程让步函数和唤醒阻塞线程函数中都会调用 list_push_back 方法将线程加入就绪队列中，所以在该方法中，需要加入线程的优先级调度机制，使就绪队列有序化。Pintos 操作系统中，已经提供了一种电表排序方法插入排序，所以我们可以直接调用 list insert order 函数实现电表插入排序功能。使用该函数可以将就绪队列有序化，实现优先级调度机制。
void
thread yield (void)
{
struct thread *cur = thread current ( );
enum intr_level old_level;
ASSERT (!intr_context ( ));
old_level = intr_disable ( ));
if (cur != idle thread)
list push back (&ready list, &cur->elem)；
cur->status - THREAD READY;
Schedule（）;
intr set level (old level);
void
thread unblock (struct thread *t)
{
enum intr level old level;
ASSERT (is thread (t));
old level = intr disable ();
ASSERT (t->status s= THREAD BLOCKED)；
list push back (&ready ist, &t->elem);
t->status - THREAD READY;
intr set level (old level);
void
list insert ordered ( struct list *list, struct list elem *elem,
list less_ func *less, void *aux)
{
struct list_ elem *e;
ASSERT (list != NULL);
ASSERT (elem != NULL);
ASSERT (less != NULL);
for (e = list begin (list);e!= list end (list);e= list next (e))
if (less (elem, e, aux))
break;
return list insert (e, elem);
}
（3）调用 thread_set_priority()改变线程优先级
第三种情况：当线程的优先级发生改变时，应该立即比较当前线程与就绪队列中线程的优先级，确定当前线程是否需要立即让出 cpu 资源。如果当前线程修改后的优先级比就绪队列中首线程的优先级还要高，则当前线程需要立即让出 cpu 资源，所以在改变线程的优先级逻辑中，需要加入线程的优先级调度机制。
void
thread_set_priority(int new_priority)
thread current ()->priority = new priority;
（4）线程同步机制
第四种情况：由于线程的同步机制，当有多个线程因为等待同一把锁、同一个信号量或者同一个条件变量而被阻塞时，应该以优先级大小的顺序将阻塞线程有序的插入等待队列中。如果当信号量改变，条件变量改变或者释放锁时阻塞线程又被重新唤醒，则线程应该以优先级由高到低的方式重新进入线程的就绪队列中。下图可以得知在信号量的下降函数中会对信号量进行操作，该函数会等待信号量值变为整数并自动减1，可以得知该函数在检测到信号量值为0时，会将当前线程阻塞并放到该信号量的阻塞队列中。为了保证该信号量大于0时，被唤醒的是最高优先级。线程可以将信号量的等待队列进行有序化处理。
同理当一个线程获得锁的时候，如果条件变量不满足时，该线程无法运行。
于是为了满足其他线程的运行需要，当前线程需要先将锁资源释放，等待条件变量满足以后再重新获取锁资源。但是这样条件变量可能正在同时被多个线程等待，所以需要对这些线程也做好优先级排序。当条件变量满足后，优先级最高的线程应该优先获得锁，所以在信号量的上升、下降、枷锁或者释放锁、条件变量改变等线程同步机制中都应该加入线程的优先级调度机制。
以上是本次实验的全部内容，大家按照要求做完实验后，可以在系统的原文件 threat 目录下运行 Make check 命令，当本次实验正确完成后，会有部分任务检测通过。
