ProjectⅠ

文档称应该有个名为DESIGNDOC的纯文本文件来描述改了什么，但我想用markdown。

目标

• 重写timer_sleep()，避免busy waiting
• thread_mlfqs为false时使用优先级调度，为true时使用多级反馈队列调度
• 实现优先级调度
  • schedule应选择高优先级线程
  • 高优先级线程加到ready_list时，应抢占
  • 锁、信号量、条件变量应优先唤醒高优先级线程
  • 当前线程降低自身优先级后，应yield
  • 需考虑优先级反转，实现优先级捐赠（仅对于锁）
  • 线程不会修改其它线程的优先级
• 实现多级反馈队列
  • 此时优先级仅由公式决定，不受其它因素影响
  • 实现定点数运算
  • 实现优先级的定时更新

重写timer_sleep()，避免busy waiting

pintos自带的三种同步原语(Semaphore Lock Monitor)看起来都不太适用，还是得用底层的thread_block和thread_unblock。

struct thread加个属性wake_up_time，表示这个线程什么时候醒。

加个struct list sleep_list，存所有在睡觉的线程。

timer_sleep()的实现改为【计算并设置wake_up_time】【按升序加进sleep_list】【thread_block()】。

timer_interrupt()里加个检查，判断sleep_list队首（睡醒时间最早的那个）是不是该醒了。

可以用堆重写一下以提升性能。

但是27个tests没有一个是关于timer_sleep()的，懒得写了。

实现优先级调度

schedule应选择高优先级线程

thread_pop_highest_priority从传入的LIST中找到优先级最高的线程，移除并返回之。

next_thread_to_run不再使用list_pop_front，以thread_pop_highest_priority替代之。

现在next_thread_to_run的复杂度从O(1)涨到了O(n)，n为ready_list的长度，用堆重新写一下应该能降到O(lgn)。

高优先级线程加到ready_list时，应抢占

thread_create中加上thread_yield即可。

锁、信号量、条件变量应优先唤醒高优先级线程

首先是信号量，把thread_pop_highest_priority扩展一下就可以复用了。

锁调用了信号量，于是自然完成不必修改。

最后是条件变量，需要重新实现，把信号量包装一下就行了，两者区别仅在于sema_up或者叫cond_signal会不会增加存量而已。

当前线程降低自身优先级后，应yield

thread_set_priority中加上thread_yield即可。

需考虑优先级反转，实现优先级捐赠（仅对于锁）

thread间直接捐赠比较难维护，考虑thread捐赠给lock，lock再捐赠给thread。

数据结构

thread to lock：

• lock.semaphore.waiters刚好维护了捐赠者，无需额外记录
• thread加属性donee，维护受赠者
• lock加属性priority，维护最高捐赠额

lock to thread：

• thread加属性donor，维护捐赠者
• lock.holder刚好维护了受赠者，无需额外记录
• thread加属性base_priority，维护无捐赠优先级

函数

• 实现lock_update_priority thread_update_priority用于更新优先级，二者需要互相调用
  • 可以假定不会有循环调用，因为如果有的话必然会有deadlock，而pintos——至少暂时——没实现解除deadlock的方法
• thread_set_priority要改一下，修改base_priority然后调用thread_update_priority
• lock_acquire lock_try_acquire的内容拆一下，分成lock_acquire_fail lock_acquire_success
  • lock_try_acquire成功则调用lock_acquire_success，失败则直接返回
  • lock_acquire会先调用lock_try_acquire，成功则返回，失败则lock_acquire_fail sema_down lock_acquire_success三连
• 三处捐赠改变点：
  • lock_acquire_fail应用thread对lock的捐赠
  • lock_acquire_success解除thread对lock的捐赠，应用lock对thread的捐赠
  • lock_release解除lock对thread的捐赠

实现多级反馈队列

此时优先级仅由公式决定，不受其它因素影响

lock_update_priority thread_update_priority thread_set_priority在thread_mlfqs为true时直接return。

更好的处理可能是让thread_update_priority在不同策略下有不同表现，然后上述三个函数在不同策略下有不同调用点。

但是写起来太麻烦了，直接return效果也差不多。

实现定点数运算

文档给的算法很详细了，但没给命名，后者难度更大一些。

如果可以用更高级的语言的话，应该把定点数封装成类，然后写运算符重载，可惜这里只有c可用。

于是只好写宏，一个微不足道的好处是新增.h文件不需要改Makefile。

实现优先级的定时更新