ProjectⅠ

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

目标

• 重写timer_sleep()，避免busy waiting
• 把FCFS调度改成优先级调度
  • schedule应选择高优先级线程
  • 高优先级线程加到ready_list时，应抢占
  • 锁、信号量、条件变量应优先唤醒高优先级线程
  • 当前线程降低自身优先级后，应yield，与thread_set_priority有关
  • 需考虑优先级反转，实现优先级捐赠（仅对于锁），与thread_get_priority有关
  • 线程不会修改其它线程的优先级
• 实现多级反馈队列

重写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()的，懒得写了。

把FCFS调度改成优先级调度

schedule应选择高优先级线程

thread_pop_highest_priority从ready_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_set_priority中加上thread_yield即可。

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

实现多级反馈队列

todo