ProjectⅠ

已完成

目标

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

重写timer_sleep()，避免busy waiting

先实现heap，之后写调度也能用上。

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

加个struct heap sleep_q，存所有在睡觉的线程。

timer_sleep()的实现变成设置wake_up_time并heap_push进sleep_q，然后thread_block()。

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

实现优先级调度

schedule应选择高优先级线程

把struct list ready_list改成struct heap ready_q即可。

高优先级线程就绪时，应抢占

thread_create中加上thread_yield即可。

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

首先是信号量，实现thread_pop_highest_priority，从传入的LIST中找到优先级最高的线程，移除并返回之。

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

最后是条件变量，需要重新实现，把信号量包装一下就行了，两者区别仅在于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。

实现优先级的更新

需要维护的值主要是nice load_avg recent_cpu priority，其中load_avg为全局变量，其它三个为每个thread所持有。

nice

• 仅由thread_set_nice修改

load_avg

• 每TIMER_FREQ，先于recent_cpu更新

recent_cpu

• 每tick更新当前线程的recent_cpu
• 每TIMER_FREQ更新所有线程的recent_cpu，需先更新load_avg

priority

• 每次更新load_avg或recent_cpu后，更新priority

测试结果

pintos -v -k -T 60 --bochs  -- -q  run alarm-single < /dev/null 2> tests/threads/alarm-single.errors > tests/threads/alarm-single.output
perl -I../.. ../../tests/threads/alarm-single.ck tests/threads/alarm-single tests/threads/alarm-single.result
pass tests/threads/alarm-single
pintos -v -k -T 60 --bochs  -- -q  run alarm-multiple < /dev/null 2> tests/threads/alarm-multiple.errors > tests/threads/alarm-multiple.output
perl -I../.. ../../tests/threads/alarm-multiple.ck tests/threads/alarm-multiple tests/threads/alarm-multiple.result
pass tests/threads/alarm-multiple
pintos -v -k -T 60 --bochs  -- -q  run alarm-simultaneous < /dev/null 2> tests/threads/alarm-simultaneous.errors > tests/threads/alarm-simultaneous.output
perl -I../.. ../../tests/threads/alarm-simultaneous.ck tests/threads/alarm-simultaneous tests/threads/alarm-simultaneous.result
pass tests/threads/alarm-simultaneous
pintos -v -k -T 60 --bochs  -- -q  run alarm-priority < /dev/null 2> tests/threads/alarm-priority.errors > tests/threads/alarm-priority.output
perl -I../.. ../../tests/threads/alarm-priority.ck tests/threads/alarm-priority tests/threads/alarm-priority.result
pass tests/threads/alarm-priority
pintos -v -k -T 60 --bochs  -- -q  run alarm-zero < /dev/null 2> tests/threads/alarm-zero.errors > tests/threads/alarm-zero.output
perl -I../.. ../../tests/threads/alarm-zero.ck tests/threads/alarm-zero tests/threads/alarm-zero.result
pass tests/threads/alarm-zero
pintos -v -k -T 60 --bochs  -- -q  run alarm-negative < /dev/null 2> tests/threads/alarm-negative.errors > tests/threads/alarm-negative.output
perl -I../.. ../../tests/threads/alarm-negative.ck tests/threads/alarm-negative tests/threads/alarm-negative.result
pass tests/threads/alarm-negative
pintos -v -k -T 60 --bochs  -- -q  run priority-change < /dev/null 2> tests/threads/priority-change.errors > tests/threads/priority-change.output
perl -I../.. ../../tests/threads/priority-change.ck tests/threads/priority-change tests/threads/priority-change.result
pass tests/threads/priority-change
pintos -v -k -T 60 --bochs  -- -q  run priority-donate-one < /dev/null 2> tests/threads/priority-donate-one.errors > tests/threads/priority-donate-one.output
perl -I../.. ../../tests/threads/priority-donate-one.ck tests/threads/priority-donate-one tests/threads/priority-donate-one.result
pass tests/threads/priority-donate-one
pintos -v -k -T 60 --bochs  -- -q  run priority-donate-multiple < /dev/null 2> tests/threads/priority-donate-multiple.errors > tests/threads/priority-donate-multiple.output
perl -I../.. ../../tests/threads/priority-donate-multiple.ck tests/threads/priority-donate-multiple tests/threads/priority-donate-multiple.result
pass tests/threads/priority-donate-multiple
pintos -v -k -T 60 --bochs  -- -q  run priority-donate-multiple2 < /dev/null 2> tests/threads/priority-donate-multiple2.errors > tests/threads/priority-donate-multiple2.output
perl -I../.. ../../tests/threads/priority-donate-multiple2.ck tests/threads/priority-donate-multiple2 tests/threads/priority-donate-multiple2.result
pass tests/threads/priority-donate-multiple2
pintos -v -k -T 60 --bochs  -- -q  run priority-donate-nest < /dev/null 2> tests/threads/priority-donate-nest.errors > tests/threads/priority-donate-nest.output
perl -I../.. ../../tests/threads/priority-donate-nest.ck tests/threads/priority-donate-nest tests/threads/priority-donate-nest.result
pass tests/threads/priority-donate-nest
pintos -v -k -T 60 --bochs  -- -q  run priority-donate-sema < /dev/null 2> tests/threads/priority-donate-sema.errors > tests/threads/priority-donate-sema.output
perl -I../.. ../../tests/threads/priority-donate-sema.ck tests/threads/priority-donate-sema tests/threads/priority-donate-sema.result
pass tests/threads/priority-donate-sema
pintos -v -k -T 60 --bochs  -- -q  run priority-donate-lower < /dev/null 2> tests/threads/priority-donate-lower.errors > tests/threads/priority-donate-lower.output
perl -I../.. ../../tests/threads/priority-donate-lower.ck tests/threads/priority-donate-lower tests/threads/priority-donate-lower.result
pass tests/threads/priority-donate-lower
pintos -v -k -T 60 --bochs  -- -q  run priority-fifo < /dev/null 2> tests/threads/priority-fifo.errors > tests/threads/priority-fifo.output
perl -I../.. ../../tests/threads/priority-fifo.ck tests/threads/priority-fifo tests/threads/priority-fifo.result
pass tests/threads/priority-fifo
pintos -v -k -T 60 --bochs  -- -q  run priority-preempt < /dev/null 2> tests/threads/priority-preempt.errors > tests/threads/priority-preempt.output
perl -I../.. ../../tests/threads/priority-preempt.ck tests/threads/priority-preempt tests/threads/priority-preempt.result
pass tests/threads/priority-preempt
pintos -v -k -T 60 --bochs  -- -q  run priority-sema < /dev/null 2> tests/threads/priority-sema.errors > tests/threads/priority-sema.output
perl -I../.. ../../tests/threads/priority-sema.ck tests/threads/priority-sema tests/threads/priority-sema.result
pass tests/threads/priority-sema
pintos -v -k -T 60 --bochs  -- -q  run priority-condvar < /dev/null 2> tests/threads/priority-condvar.errors > tests/threads/priority-condvar.output
perl -I../.. ../../tests/threads/priority-condvar.ck tests/threads/priority-condvar tests/threads/priority-condvar.result
pass tests/threads/priority-condvar
pintos -v -k -T 60 --bochs  -- -q  run priority-donate-chain < /dev/null 2> tests/threads/priority-donate-chain.errors > tests/threads/priority-donate-chain.output
perl -I../.. ../../tests/threads/priority-donate-chain.ck tests/threads/priority-donate-chain tests/threads/priority-donate-chain.result
pass tests/threads/priority-donate-chain
pintos -v -k -T 480 --bochs  -- -q -mlfqs run mlfqs-load-1 < /dev/null 2> tests/threads/mlfqs-load-1.errors > tests/threads/mlfqs-load-1.output
perl -I../.. ../../tests/threads/mlfqs-load-1.ck tests/threads/mlfqs-load-1 tests/threads/mlfqs-load-1.result
pass tests/threads/mlfqs-load-1
pintos -v -k -T 480 --bochs  -- -q -mlfqs run mlfqs-load-60 < /dev/null 2> tests/threads/mlfqs-load-60.errors > tests/threads/mlfqs-load-60.output
perl -I../.. ../../tests/threads/mlfqs-load-60.ck tests/threads/mlfqs-load-60 tests/threads/mlfqs-load-60.result
pass tests/threads/mlfqs-load-60
pintos -v -k -T 480 --bochs  -- -q -mlfqs run mlfqs-load-avg < /dev/null 2> tests/threads/mlfqs-load-avg.errors > tests/threads/mlfqs-load-avg.output
perl -I../.. ../../tests/threads/mlfqs-load-avg.ck tests/threads/mlfqs-load-avg tests/threads/mlfqs-load-avg.result
pass tests/threads/mlfqs-load-avg
pintos -v -k -T 480 --bochs  -- -q -mlfqs run mlfqs-recent-1 < /dev/null 2> tests/threads/mlfqs-recent-1.errors > tests/threads/mlfqs-recent-1.output
perl -I../.. ../../tests/threads/mlfqs-recent-1.ck tests/threads/mlfqs-recent-1 tests/threads/mlfqs-recent-1.result
pass tests/threads/mlfqs-recent-1
pintos -v -k -T 480 --bochs  -- -q -mlfqs run mlfqs-fair-2 < /dev/null 2> tests/threads/mlfqs-fair-2.errors > tests/threads/mlfqs-fair-2.output
perl -I../.. ../../tests/threads/mlfqs-fair-2.ck tests/threads/mlfqs-fair-2 tests/threads/mlfqs-fair-2.result
pass tests/threads/mlfqs-fair-2
pintos -v -k -T 480 --bochs  -- -q -mlfqs run mlfqs-fair-20 < /dev/null 2> tests/threads/mlfqs-fair-20.errors > tests/threads/mlfqs-fair-20.output
perl -I../.. ../../tests/threads/mlfqs-fair-20.ck tests/threads/mlfqs-fair-20 tests/threads/mlfqs-fair-20.result
pass tests/threads/mlfqs-fair-20
pintos -v -k -T 480 --bochs  -- -q -mlfqs run mlfqs-nice-2 < /dev/null 2> tests/threads/mlfqs-nice-2.errors > tests/threads/mlfqs-nice-2.output
perl -I../.. ../../tests/threads/mlfqs-nice-2.ck tests/threads/mlfqs-nice-2 tests/threads/mlfqs-nice-2.result
pass tests/threads/mlfqs-nice-2
pintos -v -k -T 480 --bochs  -- -q -mlfqs run mlfqs-nice-10 < /dev/null 2> tests/threads/mlfqs-nice-10.errors > tests/threads/mlfqs-nice-10.output
perl -I../.. ../../tests/threads/mlfqs-nice-10.ck tests/threads/mlfqs-nice-10 tests/threads/mlfqs-nice-10.result
pass tests/threads/mlfqs-nice-10
pintos -v -k -T 480 --bochs  -- -q -mlfqs run mlfqs-block < /dev/null 2> tests/threads/mlfqs-block.errors > tests/threads/mlfqs-block.output
perl -I../.. ../../tests/threads/mlfqs-block.ck tests/threads/mlfqs-block tests/threads/mlfqs-block.result
pass tests/threads/mlfqs-block
pass tests/threads/alarm-single
pass tests/threads/alarm-multiple
pass tests/threads/alarm-simultaneous
pass tests/threads/alarm-priority
pass tests/threads/alarm-zero
pass tests/threads/alarm-negative
pass tests/threads/priority-change
pass tests/threads/priority-donate-one
pass tests/threads/priority-donate-multiple
pass tests/threads/priority-donate-multiple2
pass tests/threads/priority-donate-nest
pass tests/threads/priority-donate-sema
pass tests/threads/priority-donate-lower
pass tests/threads/priority-fifo
pass tests/threads/priority-preempt
pass tests/threads/priority-sema
pass tests/threads/priority-condvar
pass tests/threads/priority-donate-chain
pass tests/threads/mlfqs-load-1
pass tests/threads/mlfqs-load-60
pass tests/threads/mlfqs-load-avg
pass tests/threads/mlfqs-recent-1
pass tests/threads/mlfqs-fair-2
pass tests/threads/mlfqs-fair-20
pass tests/threads/mlfqs-nice-2
pass tests/threads/mlfqs-nice-10
pass tests/threads/mlfqs-block
All 27 tests passed.