本次博客将详细解释pintos project1的mission2部分。
首先来回顾一下pintos project1 mission1：在mission1里，我们的主要任务是实现了timer_sleep函数唤醒机制。这里需要说明的是，经过mission1之后，我们应该明白，pintos操作系统并不是一个空白的系统：它要求我们做的东西，大部分都已经实现了。就比如timer_sleep函数，在我们对其做更为优化的实现时，实际上该函数原本就有一套实现的原理：系统原本是使用busy wait实现的，即线程不停地循环，直到时间片耗尽。
（1）pintos project1 mission2的主要任务是在Pintos中实现优先级调度，需要解决的问题有如下两个，我们将分别对其进行实现。具体的思路为：先看这一部分的test要求我们做什么，然后按照test的内容去做我们的实现。这样的做法是比较高效的。
（2）先看除去donation以外的测试。第一个测试priority-fifo的源代码如下。这个测试创建了一个优先级PRI_DEFAULT+2的主线程，并用这个线程创建了16个优先级PRI_DEFAULT+1的子线程，然后把主线程的优先级设置为优先级PRI_DEFAULT，所以现在pintos内有16个优先级PRI_DEFAULT+1的线程和1个优先级PRI_DEFAULT的线程在跑，测试需要把16个线程跑完再结束那一个线程。
（3）注意OS中线程是并行执行的，有可能最开始的一个线程在设置完优先级之后立刻结束了，而此时其他线程并未结束，即注释。在线程设置完优先级之后应该立刻重新调度，因此只需要在thread_set_priority()函数里添加thread_yield()函数即可。
（4）priority-fifo解决：
（5）再看测试priority-preempt。该测试样例创建了一个新的高优先级线程抢占当前线程。需要解决的问题是高优先级对于低优先级的中断和抢占。
（6）解决：如果新线程的优先级高于当前线程优先级，调用thread_yield()函数。
（7）此时可发现priority-change也过了，查看此测试。这个测试创建了一个新线程并要这个线程立刻调用，然后在降低优先级之后它就不应该继续执行了，这正好对应于之前修改的两处，所以自然能通过测试。
（8）上述三个测试解决之后的结果。
（9）接下来的两个测试都是线程同步问题。首先来看priority-seme测试：这个测试创建了10个优先级不等的线程，并且每个线程调用sema_down函数，其他得不到信号量的线程都得阻塞。而每次运行的线程释放信号量时必须确保优先级最高的线程继续执行。
（10）解决：显然我们需要修改sema_up。查看semaphore结构体【位置：～/pintos/src/threads/synch.h】，结构体中有一waiters为阻塞队列，而pintos的sema_up设计：只是把waiters最前面的线程取出来加入到ready_list。那么修改方法就是在waiters中取出优先级最高的thread，并yield()。
（11）priority-condvar测试：和前面的信号量机制类似，条件变量也维护了一个waiters用于存储等待接受条件变量的线程，那么就修改cond_signal（）函数唤醒优先级最高的线程即可，和priority-sema类似。实质：condition的waiters队列是优先级队列。
（12）线程同步问题的阶段结果。
（13）剩下的测试都是有关于优先级捐赠的问题。那么什么是优先级捐赠问题？举例来说：线程A,B,C分别具有1,2,3优先级(数字越大说明优先级越高), 线程A,B目前在就绪队列中等待调度,线程A对一个互斥资源拥有线程锁。而此时,高优先级的线程C也想要访问这个互斥资源,线程C只好在这个资源上等待,不能进入就绪队列。当调度器开始调度时,它只能从A和B中进行选择,根据优先级调度原理,线程B将会首先运行。这时就产生了一个问题, 即本来线程C优先级比线程B高,但是线程B却先运行了,从而产生了优先级翻转问题。
（14）怎么解决这个问题？ 当发现高优先级的任务因为低优先级任务占用资源而阻塞时，就将低优先级任务的优先级提升到等待它所占有的资源的最高优先级任务的优先级。
对于优先级捐赠的这几个测试来说，有两个关键的问题，一是优先级嵌套，另一是因为互斥锁而导致的线程阻塞。并且这一系列的问题的解决并不是独立的。
（15）接下来重点讲两个测试的原理。首先是测试priority-donte-multiple：original_thread是优先级为PRI_DEFAULT的线程，然后创建2个锁，接着创建优先级为PRI_DEFAULT+1的线程a，把锁a丢给这个线程的执行函数。这时候线程a抢占式地调用a_thread_func，获取了a这个锁，阻塞。然后original_thread输出线程优先级的msg。然后再创建一个线程优先级为PRI_DEFAULT+2的线程b， 和a一样做同样的操作。好， 然后original_thread释放掉了锁b，此时线程b被唤醒，抢占式执行b_thread_func。然后original再输出msg，a同上。
实现思路是：释放一个锁的时候，将该锁的拥有者改为该线程被捐赠的第二优先级，若没有其余捐赠者， 则恢复原始优先级。那么我们的线程必然需要一个数据结构来记录所有对这个线程有捐赠行为的线程。
（16）接下来是测试priority-donate-chain：这个测试其实就是一个链式优先级捐赠，本质测试的还是多层优先级捐赠逻辑的正确性。
（17）donate的所有测试逻辑整合。
（18）接下来是这部分测试的整体实现流程。
（19）最终结果如下。至此，我们实现了mission2里的全部内容。
