OS 实验5 优先级抢占、贡献

OS

https://www.zybuluo.com/SovietPower/note/1884753
参考：
https://www.cnblogs.com/laiy/p/pintos_project1_thread.html

背景

已实现优先级调度，每次正在运行的进程一定是（未阻塞进程中）优先级最高的进程。

本次实验需通过priority相关的所有12个测试（src/threads下）（共通过20/27个样例）。

会修改的文件：thread.c, thread.h, synch.c, synch.h。

用pintos本地测试的时候出现问题：

反复提示Booting from hard disk，无法运行

网上搜的要么是：https://stackoverflow.com/questions/44269968/qemu-gets-stuck-at-booting-from-hard-disk# 或 进入到bios系统将硬盘重新设置为第一启动，要么是将硬件启动切换成软件启动。
都不行或者不知道怎么改。
qemu, bochs都不行，自己的虚拟机和老师给的虚拟机都不行，VirtualBox（旧版、最新版）和VMware也都不行。

花了很久才发现，是init_thread()中没初始化（应该主要是list lock的问题）。

priority-change, priority-preempt

两个测试需实现：最高优先级进程可抢占当前进程，包括优先级改变后成为最高优先级的进程。

测试文件在test/threads下的priority-change.c和priority-preempt.c中，标准输出在priority-change.ck和priority-preempt.ck中。

priority-change

测试：
初始进程A优先级为31（DEFAULT），然后调用test_priority_change()，创建优先级为32的进程B。
B优先级更高，所以此时B应执行，输出Thread 2 now lowering priority.。然后B将自己的优先级降为30。
此时A优先级更高，且应立刻开始执行，输出Thread 2 should have just lowered its priority.。然后A将自己的优先级降为29。
此时B优先级又更高，且应立刻开始执行，输出Thread 2 exiting.。然后B执行完毕，A输出Thread 2 should have just exited.。

Solution：
可见，若新创建的进程优先级高于当前进程，则它应立刻取代当前进程。
所以修改thread_create()：

tid_t
thread_create (const char *name, int priority,
               thread_func *function, void *aux)
{
    ...
    // 解除线程t的阻塞状态，设为就绪状态，并将其加入到就绪队列。
    thread_unblock (t);
    // ----- My code
    if(priority > thread_get_priority())
        thread_yield();
    // -----
    // 创建成功，返回其tid。
    return tid;

此外，每次当前进程的优先级改变后（通过thread_set_priority()），若其优先级不再是最高，则它应被另一最高优先级进程取代（只需它调用thread_yield()）。
所以在thread_set_priority()中加入：

void thread_set_priority (int new_priority)
{
    thread_current ()->priority = new_priority;
    // ----- My code
    thread_yield();
    // -----
}

priority-preempt

测试：
初始进程A优先级为31（DEFAULT），创建优先级为32的进程B。
B优先级更高，所以开始执行。B共进行5次thread_yield()，因为其优先级最高，所以每次yield后，B仍然是运行进程，直到B运行完毕输出Thread high-priority done!。
然后A运行，输出The high-priority thread should have already completed.。

Solution：
因为之前已实现thread_yield()选择（未阻塞的）优先级最高的进程执行，所以可以直接通过。

测试内容/需求分析

关于priority-donate：
优先级翻转问题：
设优先级分别为1,2,3的三个进程A,B,C，此时优先级最低的进程A拥有一个互斥锁，优先级最高的进程C需要这个互斥锁，会被阻塞，需等待A先进行。但B优先级高于A，所以会先执行，B执行完后，A,C才能执行。
所以虽然C的优先级更高，但B却先于C运行完毕。
此时应该讲拥有锁的进程A的优先级，设为需要该锁的进程中的最高优先级，以便A先执行完毕，运行最高优先级进程先执行。

要解决该问题，可在一个进程A因锁被阻塞时，将拥有对应锁的进程B的优先级暂时提高为A的优先级（如果B优先级低于A）；在B释放锁后，改回B之前的优先级。

要注意，因为优先级会改变，所以所有按优先级排序的队列/链表在使用前，都需重新排序。
如果要让进程在优先级改变时重新进入队列，要么需对每个进程都记录它所属的所有队列（不行），要么需在使用队列前，重排被修改的进程，但这是$O(n^2)$的。

有多个测试数据，依次看。

priority-donate-one

初始进程A优先级为31，拥有锁lock，会依次创建优先级分别为32,33的两个进程B,C，B,C在实际运行前，都需要获得锁A。
在A创建进程B后，A的优先级应变为32；在A创建进程C后，A的优先级应变为33。
当A执行完释放锁后，C,B应依次执行。

priority-donate-multiple

priority-donate-multiple
初始进程A优先级为31，拥有两个锁lock，会依次创建优先级分别为32,33的两个进程B,C，B,C在实际运行前，都需要分别获得A的一个锁。
在A创建进程B后，A的优先级应变为32；在A创建进程C后，A的优先级应变为33。
当A释放C所需的锁后，A的优先级应变为32；释放B所需的锁后，A的优先级应变为最初的31。

该测试表明，但进程拥有多个锁时，可能会同时有多个贡献得到的优先级，需要动态取最大的。
所以需要维护，每个进程被贡献的优先级有哪些。

priority-donate-multiple2
上一个测试的进一步测试，保证进程拥有所有贡献得到的优先级，需动态取最大优先级。

priority-donate-chain

初始进程$p_0$优先级为0，拥有锁0。
创建7个进程$p_1,p_2,...,p_7$，分别拥有优先级$3,6,9,12,...,21$，各需获取两个锁$(1,0),(2,1),(3,2),...$。
注意第7个进程$p_7$优先级为$21$，但只有一个锁$6$。
此外，又创建7个进程$q_1,q_2,...,q_7$，分别拥有优先级$2,4,8,11,...,20$。不需要锁。

$p_7$需要$p_6$解锁，$p_6$需要$p_5$解锁... $p_2$需要$p_1$解锁，$p_1$需要$p_0$解锁，所以这8个进程都获得优先级$21$，并按$p_0,p_1,p_2,...,p_7$的顺序依次执行、释放锁。
$p_7$执行完后，$q_7,q_6,q_5,...,q_1$才依次执行。

所以在一个进程被贡献优先级时，需将该优先级继续贡献给它原本在贡献的进程。
所以，每个进程获得贡献优先级时，需递归贡献它在贡献的进程（即导致它阻塞的进程）。

priority-donate-nest

初始进程A优先级为31，拥有锁a。
A创建进程B，优先级32，B拥有锁b，然后获取锁a（等待A执行完），所以A此时优先级应变为32。
A创建进程C，优先级33，需要锁b，所以B此时优先级应变为33，A也应同步变为33。
A执行完毕后，释放a，B执行；B执行完后，释放a,b，C执行。

所以在一个进程优先级改变时，若其有未获得的锁（贡献给其它进程了优先级），也应修改它贡献的进程的优先级。
所以需要维护，每个进程因为哪些进程而被阻塞。

priority-donate-lower

初始进程A优先级为31，拥有锁。
创建进程B，优先级为41，需要锁。此时A优先级为41。
然后A将自己的优先级设为21。因为仍有锁，所以实际优先级仍应为41。
A释放锁，优先级变为21。

这个测试保证，在进程自己的优先级改变后，也需考虑所有贡献得到的优先级，选择最大的。

priority-donate-sema

锁和信号量的混合使用。前面实现了这个就可以过。

priority-condvar

condvar表示条件变量。
结构condition就是一个等待队列/链表，其元素为信号量。
cond_wait(cond, lock)会新建一个信号量$s$放在cond队尾，这个信号量$s$会释放当前持有的锁lock，然后等待信号量$s$，在$s$增加时重新获取这个lock。
cond_signal(cond, lock)会释放cond的队首，并增加队首这个信号量，重新获取它之前释放的锁。

初始进程，创建10个优先级分别为$21,22,...,30$的进程。每次创建进程后，进程会获取锁，然后调用cond_wait()释放该锁，然后被阻塞到cond_signal()发生时重新获取锁、完成执行。
因为cond_wait()被阻塞的10个进程，需用cond_signal()按优先级从大到小，依次唤醒。

所以，cond_wait()中的list_push_back，需改为按优先级插入。
同时，在cond_signal()获取队列元素前，也需对队列重新按优先级排序。

priority-sema

初始进程拥有一个为0的信号量，然后创建10个优先级不同的进程，10个进程均等待信号量而被阻塞。
初始进程依次增加信号量，被阻塞的10个进程，需按优先级从大到小依次被唤醒。

semaphore有一个链表waiters，表示其等待队列。
当调用sema_up(sema)时，会唤醒&sema->waiters中的第一个元素。
所以semaphore的链表waiters，也应按优先级插入元素。

所以，sema_down()中的list_push_back，需改为按优先级插入。
同时，在sema_up()获取队列元素前，也需对队列重新按优先级排序。

实现流程

综合前面的测试，可得实验需求为：
1. 维护每个进程被贡献的优先级有哪些，并动态取最大的作为其优先级。
2. 维护每个进程因为哪个进程（或哪个锁）而被阻塞，以贡献优先级。
3. 在一个进程被阻塞时，会向锁的拥有者贡献优先级；每个进程获得贡献优先级时，需递归贡献它在贡献的进程（即导致它阻塞的进程）。
4. 在一个进程释放锁时，需删除因该锁向它贡献的优先级。若删除后其优先级不是最高，则可被抢占。
5. 进程优先级改变时，需考虑其拥有锁的优先级（而不是直接赋值）；也应改变它贡献出的优先级。
6. cond_wait()中的list_push_back，需改为按优先级插入；在cond_signal()获取队列元素前，也需对队列重新按优先级排序。
7. sema_down()中的list_push_back，需改为按优先级插入sema.waiters；在sema_up()获取队列元素前，也需对sema.waiters队列重新按优先级排序。

可以发现，进程获得贡献优先级，完全因为它拥有的锁；贡献优先级消失，也是因为拥有锁消失。因为每个锁只有一个拥有者，所以不妨直接对每个锁，维护向该锁贡献的优先级；进程维护它拥有哪些锁。当锁被释放时，直接从进程的锁序列中删除它即可（更新一下进程优先级）。
所以需求可改为：
1. 维护每个锁被贡献的最大优先级。
2. 维护每个进程因为哪个锁而被阻塞、拥有哪些锁，以贡献优先级、维护最大优先级。
3. 在一个进程被阻塞时，会向请求锁贡献优先级；锁获得贡献优先级时，需递归贡献锁的拥有者在贡献的锁（导致它阻塞的锁）。
4. 在一个进程释放锁时，需删除该锁的优先级。若删除后其优先级不是最高，则可被抢占。
5. 进程优先级改变时，需考虑其拥有锁的优先级（而不是直接赋值）。
6. 在cond_signal()获取队列元素前，也需对队列重新按优先级排序。
7. sema_down()中的list_push_back，需改为按优先级插入sema.waiters；在sema_up()获取队列元素前，也需对sema.waiters队列重新按优先级排序。

注：

• 1本应是“维护每个锁被贡献的优先级有哪些，并动态维护最大的”，是因为如果该锁拥有的最大优先级被删除后，需取次大的；但“最大优先级被删除”发生在该锁被最大优先级进程获取，不需要被贡献次大优先级。所以只需维护锁的最大优先级即可（每次锁被获得时，将该优先级置为该进程的优先级）。
• 锁获得贡献优先级$x$时，需递归贡献锁的拥有者等待的锁的优先级$y$，若$x\gt y$，则更新$y=x$并继续递归；否则可以停止递归，因为只需维护最大值。
• 5删掉了“当进程优先级改变时，也应改变它贡献出的优先级”，因为一个进程的优先级不能被其它进程改变，所以改变时一定没被阻塞，不会贡献优先级。
• 在进程被贡献优先级时，若其在就绪队列且优先级改变，需从就绪队列中删除，重新插入队列；在进程释放锁而改变优先级时，因为一定是当前运行程序，所以一定不在就绪队列中，不需重新维护。
• 7的semaphore的排序，是将等待该semaphore的进程按优先级排序；6的condition的排序，是将condition的semaphore队列中的semaphore，按等待该semaphore的进程的最大优先级排序。
• 6 condition的“list_push_back，需改为按优先级插入”，与或者在使用前“重新排序”，本来应实现一个就可。但插入后，等待semaphore的进程可能会更改，已经必须每次排序，所以不用有序插入。但7 semaphore不一样，因为不仅sema_up()需要获取sema.waiters，condition也需sema.waiters的第一个元素作为condition的sema队列的排序标准，所以在插入时就应有序插入，以供condition使用。

1.维护每个锁被贡献的最大优先级

注意为了将锁放入队列，还需为锁维护一个list_elem，在使用时用list_entry(LIST_ELEM, STRUCT, MEMBER)将list_elem转为锁。
所以修改锁的定义：

/* Lock. */
struct lock
{
    struct thread *holder;      /* Thread holding lock (for debugging). */
    struct semaphore semaphore; /* Binary semaphore controlling access. */
    // ----- My code
    int max_priority;
    struct list_elem elem;
    // -----
};

2.维护每个进程因为哪个锁而被阻塞、拥有哪些锁

修改thread的定义：

struct thread
{
    ...
    struct list locks;      // 拥有的锁
    struct lock *waiting;   // 在等待的锁
    int default_priority;   // 自身的优先级
}

注意在init_thread()中加入初始化！

t->default_priority = priority;
t->waiting = NULL;
list_init(&t->locks);

3.被阻塞时，向请求锁贡献优先级；锁获得贡献优先级时，递归贡献

修改lock_acquire()：

void
lock_acquire (struct lock *lock)
{
    ASSERT (lock != NULL);
    ASSERT (!intr_context ());
    ASSERT (!lock_held_by_current_thread (lock));
    // ----- My Code
    struct thread *cur = thread_current();
    // 被阻塞，向锁递归贡献优先级
    if (lock->holder!=NULL)
    {
        cur->waiting = lock;
        int pri = cur->priority;
        struct lock *l = lock;
        while (l!=NULL && pri>l->max_priority)
        {
            l->max_priority = pri;
            thread_donate_priority(l->holder);
            l = l->holder->waiting;
        }
    }
    sema_down (&lock->semaphore);
    lock->holder = cur;
    lock->max_priority = cur->priority; // 锁被当前优先级最高的进程获取，所以其最大优先级就是当前进程的优先级
    cur->waiting = NULL;
    thread_get_lock(lock);
    // -----
}

相关函数：

/* 进程拥有的某个锁向它贡献优先级。需尝试更新优先级（通过重排整个拥有锁队列）。然后若其在就绪队列且优先级改变，需从就绪队列中删除，重新插入队列。 */
void thread_donate_priority(struct thread *t)
{
    int old_priority = t->priority;
    thread_update_priority(t);
    if (t->priority!=old_priority && t->status==THREAD_READY)
    {
        list_remove(&t->elem);
        list_insert_ordered(&ready_list, &t->elem, cmp_thread_priority, NULL);
    }
}
/* 更新进程的优先级（通过重排整个拥有锁队列） */
void thread_update_priority(struct thread *t)
{
    int pri = t->default_priority;
    if (!list_empty(&t->locks))
    {
        list_sort(&t->locks, cmp_lock_priority, NULL);
        int mx = list_entry(list_front(&t->locks), struct lock, elem)->max_priority;
        if (mx > pri)
            pri = mx;
    }
    t->priority = pri;
}
/* 当前进程获得一个锁，将其插入拥有锁队列，并尝试更新优先级。 */
void thread_get_lock(struct lock *lock)
{
    struct thread *cur = thread_current();
    list_insert_ordered(&cur->locks, &lock->elem, cmp_lock_priority, NULL);
    if (lock->max_priority > cur->priority)
    {
        cur->priority = lock->max_priority;
        thread_yield(); // todo 可能并不需要
    }
}
bool cmp_lock_priority(const struct list_elem *x, const struct list_elem *y, void *aux UNUSED)
{
    return list_entry(x, struct lock, elem)->max_priority > list_entry(y, struct lock, elem)->max_priority;
}

4.释放锁时，删除该锁的优先级；删除后可能被抢占

修改lock_release()：

void
lock_release (struct lock *lock)
{
  ASSERT (lock != NULL);
  ASSERT (lock_held_by_current_thread (lock));
  // ----- My Code
  thread_remove_lock(lock);
  // -----
  lock->holder = NULL;
  sema_up (&lock->semaphore);
}

相关函数：

/* 当前进程释放一个锁，将其从拥有锁队列中删除，并更新优先级 */
void thread_remove_lock(struct lock *lock)
{
    list_remove(&lock->elem);
    thread_update_priority(thread_current());
}

5.优先级改变时，需考虑拥有锁

修改thread_set_priority()：

/* 设置进程的优先级。需考虑拥有锁的优先级。 */
void thread_set_priority (int new_priority)
{
    struct thread *cur = thread_current();
    int before = cur->priority;
    cur->default_priority = new_priority;
    if (!list_empty(&cur->locks))
    {
        int mx = list_entry(list_front(&cur->locks), struct lock, elem)->max_priority;
        if (mx > new_priority)
            new_priority = mx;
    }
    if (before != new_priority)
    {
        cur->priority = new_priority;
        thread_yield();
    }
}

6. cond_signal()需对队列排序

修改cond_signal()：

void
cond_signal (struct condition *cond, struct lock *lock UNUSED)
{
    ASSERT (cond != NULL);
    ASSERT (lock != NULL);
    ASSERT (!intr_context ());
    ASSERT (lock_held_by_current_thread (lock));
    if (!list_empty (&cond->waiters))
    {
        // ----- My Code
        list_sort (&cond->waiters, cmp_cond_priority, NULL);
        // -----
        sema_up (&list_entry (list_pop_front (&cond->waiters), struct semaphore_elem, elem)->semaphore);
    }
}

相关函数：

/* 将condition的semaphore队列中的semaphore，按等待该semaphore的进程的最大优先级排序 */
bool cmp_cond_priority(const struct list_elem *x, const struct list_elem *y, void *aux UNUSED)
{
    struct semaphore_elem *sx = list_entry (x, struct semaphore_elem, elem);
    struct semaphore_elem *sy = list_entry (y, struct semaphore_elem, elem);
    return list_entry(list_front(&sx->semaphore.waiters), struct thread, elem)->priority > list_entry(list_front(&sy->semaphore.waiters), struct thread, elem)->priority;
}

7. sema_down()需改为按优先级插入；sema_up()需对队列排序

修改sema_down()：

void
sema_down (struct semaphore *sema)
{
    enum intr_level old_level;
    ASSERT (sema != NULL);
    ASSERT (!intr_context ());
    old_level = intr_disable ();
    while (sema->value == 0)
    {
        // ----- My Code
        list_insert_ordered (&sema->waiters, &thread_current()->elem, cmp_thread_priority, NULL);
        // -----
        thread_block ();
    }
    sema->value--;
    intr_set_level (old_level);
}

修改sema_up()：

void
sema_up (struct semaphore *sema)
{
    enum intr_level old_level;
    ASSERT (sema != NULL);
    old_level = intr_disable ();
    if (!list_empty (&sema->waiters))
    {
        // ----- My Code
        list_sort (&sema->waiters, cmp_thread_priority, NULL);
        // -----
        thread_unblock (list_entry (list_pop_front (&sema->waiters), struct thread, elem));
    }
    sema->value++;
    thread_yield();
    intr_set_level (old_level);
}