任务：实现优先级捐赠
假设目前线程 A,B,C 分别具有 1,2,3 优先级(数字越大说明优先级越高), 线程 A,B 目前在就绪队列中等待调度, 线程 A 对一个互斥资源拥有锁。此时, 高优先级的线程 C 也想要访问这个互斥资源, 线程 C 只好等待,不能进入就绪队列。当开始线程调度时, 它只能从 A 和 B 中进行选择,根据优先级调度原理,线程 B 将会首先运行。
这时就产生了一个问题, 即本来线程 C 优先级比线程 B 高, 但是线程 B 却先运行了,从而产生了优先级翻转问题。
怎么解决这个问题？
思路：当发现高优先级的任务因为低优先级任务占用资源而阻塞时，就将低优先级任务的优先级提升到等待它所占有的资源的最高优先级任务的优先级。
• 先来看priority-donate-one测试的源代码：
1 void
2 test_priority_donate_one (void)
3 {
4 struct lock lock;
5
6 /* This test does not work with the MLFQS. */
7 ASSERT (!thread_mlfqs);
8
9 /* Make sure our priority is the default. */
10 ASSERT (thread_get_priority () == PRI_DEFAULT);
11
12 lock_init (&lock);
13 lock_acquire (&lock);
14 thread_create ("acquire1", PRI_DEFAULT + 1, acquire1_thread_func, &lock);
15 msg ("This thread should have priority %d. Actual priority: %d.",
16 PRI_DEFAULT + 1, thread_get_priority ());
17 thread_create ("acquire2", PRI_DEFAULT + 2, acquire2_thread_func, &lock);
18 msg ("This thread should have priority %d. Actual priority: %d.",
19 PRI_DEFAULT + 2, thread_get_priority ());
20 lock_release (&lock);
21 msg ("acquire2, acquire1 must already have finished, in that order.");
22 msg ("This should be the last line before finishing this test.");
23}
25 static void
26 acquire1_thread_func (void *lock_)
27{
28 struct lock *lock = lock_;
29
30 lock_acquire (lock);
31 msg ("acquire1: got the lock");
32 lock_release (lock);
33 msg ("acquire1: done");
34}
35
36 static void
37 acquire2_thread_func (void *lock_)
38{
39 struct lock *lock = lock_;
40
41 lock_acquire (lock);
42 msg ("acquire2: got the lock");
43 lock_release (lock);
44 msg ("acquire2: done");
45}
第4行，它创建了一个锁，我们来看一下这个锁的定义：
struct lock
{
struct thread *holder; /* Thread holding lock (for debugging). */
struct semaphore semaphore; /* Binary semaphore controlling access. */
};
分析：首先当前线程（简称为thread1）是一个优先级为PRI_DEFAULT的线程，然后第4行创建了一个锁，接着初始化了这个锁（将信号量初始值置为1），紧接着调用lock_acquire函数请求了一个这个锁的资源。
来看lock_acquire函数：
1 Down or "P" operation on a semaphore. Waits for SEMA's value
2 to become positive and then atomically decrements it.
3
4 This function may sleep, so it must not be called within an
5 interrupt handler. This function may be called with
6 interrupts disabled, but if it sleeps then the next scheduled
7 thread will probably turn interrupts back on. */
8 void
9 sema_down (struct semaphore *sema)
10 {
11 enum intr_level old_level;
12
13 ASSERT (sema != NULL);
14 ASSERT (!intr_context ());
15
16 old_level = intr_disable ();
17 while (sema->value == 0)
18 {
19 list_push_back (&sema->waiters, &thread_current ()->elem);
20 thread_block ();
21 }
22 sema->value--;
23 intr_set_level (old_level);
24 }
由于thread1之前将信号量初值初始化为1了，因此不会进入while循环，而是直接执行第22行，将信号量的值减1，那么此时信号量的值就是0了。
返回到上层lock_acquire函数继续看第17行，作用就是将这个锁的所有者置为了当前线程（thread1）。
然后再返回最上面的priority-donate-one函数，继续分析接下来的第14行，创建了一个线程acquire1，优先级为PRI_DEFAULT+1，并传了一个函数acquire1_thread_func过去（acquire1执行的时候会调用），并且传给该函数的实参是thread1之前创建的lock。按照之前我们实现的抢占式调度，acquire1会马上执行。
好，继续来看第26行acquire1_thread_func函数，该函数也调用了lock_acquire，尝试获取之前thread1创建的锁的资源。然后lock_acquire继续调用sema_down，但我们上面提到过，此时thread1创建的锁的信号量的值已经是0了，因此acquire1会直接进入sema_down里的while循环，被插入该信号量的等待队列，然后被阻塞，然后thread1继续上处理机运行。
然后处理机继续执行thread1的第15行语句，输出msg: "This thread should have priority 32. Actual priority: 32”。接着创建一个线程acquire2，优先级为PRI_DEFAULT+2，这里调用和acquire1一致，同样的，acquire2被阻塞，然后thread1继续上处理机运行，执行第18行，输出msg: "This thread should have priority 33. Actual priority: 33."。
从输出语句可以看出，测试期望的结果是这样的：acquire1由于P操作失败被阻塞而切换到thread1后，thread1的优先级应该做出相应改动，即与acquire1的优先级保持一致。acquire2行为类似。
总结一下，就是要求：当一个正在运行的线程占有一个锁，而其他比该线程优先级高的线程由于请求这个锁而被阻塞的时候，就需要将这个线程的优先级提高到所有由于请求该锁而被阻塞的线程里的优先级最高的线程的优先级。并且释放lock之后要改回原来的优先级。
然后继续看第20行，thread1调用lock_release函数释放了lock资源。lock_release会把lock->holder置为NULL，并调用sema_up函数。我们来看一下sema_up：