week 08-102メガgit repo

https://github.com/JahunSeo/pintos-kaist/tree/master

参考資料

https://web.stanford.edu/class/cs140/projects/pintos/

https://oslab.kaist.ac.kr/pintosslides/

https://oslab.kaist.ac.kr/ee415-spring-2020/

Alarm Clock

に質問

Pintosは基本的にBusy waitingによるアラーム機能です.

Alarm:カーネル内部関数

、指定された時間後に呼び出されたプロセスを再起動

Busy waiting

Busy waiting:ThreadはCPUを占有し、消費電力などの不要なリソースの浪費を招く.

改善方法

sleep/wake up

従来のloopベースのwait()方式の代わりにsleep list(queue)を用いて、timer_sleep()関数を呼び出したときに実行中のスレッドをブロック状態(read listから削除)にし、sleep listに入れる.
その後、timer割り込みが発生した場合、tickをチェックし、sleepリストからタイムアウトしたスレッドを削除し、readyリストに入れます.

検査結果

 pintos -- -q run alarm-multiple

待ち時間からsleep/wakeupに変更すると、空き時間が長くなりkernel時間が短縮されます.ビジーウエイト方式は,スレッドがスリープ状態でもCPUを占有しているため,アイドル状態ではない.

Priority Scheduling

に質問

既存のpintosスケジューラはRRによって実現される.したがって、threadは、ready listに挿入される順序でCPUを占有する.

Round Robin:RRは操作完了を待たない.しばらく実行してから、実行キューの次のタスクに切り替えます.タスクが実行される期間をタイムスライスと呼びます.作業が完了するまでこのように行われていたため、RRは時間遅延と呼ばれることがある.

したがって、スレッドを変更して優先度(priority)を考慮する必要があります.

改善方法

ready listに新しく追加されたthreadの優先度が現在CPUを占有している(実行)threadの優先度より高い場合は、既存のthreadを押しのけて優先権を奪う.

複数のスレッドがロックと信号量の取得を待つ場合、最も優先度の高いスレッドがCPUを占有します.

PRI_MIN : 0

PRI_MAX : 63

PRI_DEFAULT : 31

thread_create():スレッドがready listに入ると、実行スレッドの優先度と比較され、新しく作成されたスレッドの優先度が高い場合は、thread_yield()を介してCPUプリエンプトを呼び出すように変更されます.

thread_unblock():push backではなく、ロック解除時にスレッドを優先順位でソート(順序付け)し、ready listに追加します.

thread_yield():curr threadは、push backではなくready listに挿入するときに優先順位でソート(順序付け)するようにcpuをプリエンプトし、変更します.

thread_set_priority():スレッドの優先度が変更されると、優先順位によるプリエンプトに変更されます.

test_max_priority():read listは、最も優先度の高いスレッドをcurr threadの優先度と比較して、スケジューリング(降伏)関数を追加します.

thread_compare_priority():list_insert_ordered()にboolタイプの関数を追加します.1番目のパラメータ(thread)の優先度が高い場合は1を返し、2番目のパラメータの優先度が高い場合は0を返します.

検査結果

# 먼저 test.c 파일에서 mlfqs 관련 테스트 라인을 주석처리 해야 함 먽 
make check

改善されると、アラート-優先度、FIFO、プリエンプトが通過します.

Synchronization

に質問

既存のpintosはFIFOによって実現され、信号量のtheread listを待つ.

改善方法

複数のスレッドがlock、信号量、condition変数の取得を待つ場合は、最も優先度の高いスレッドにCPUを占有させる必要があります.

sema_down():信号量を取得し、pushbackではなく既存の優先度でウェイトレスリストを挿入するように変更する(Ordered).

sema_up():threadがウェイトレスリストにある場合(待機中)優先度が変更される可能性があるため、ウェイトレスリストを降順(優先度が高い)にソートするコードが追加されました.

sema_compare_priority():信号量要素構造体のlist elemメンバーをパラメータとして受け入れ、残りのメンバーに属するthreadのprioity間の優先度を比較するために関数を追加する.

cond_wait():既存の非後退cond待機要素に対応するスレッド間の優先順位順に挿入されるように、条件待機者リストを変更します.

cond_signal():優先度が変更される可能性があるため、条件待ちリスト(待機中)で優先度を変更します(list_sort()).

検査結果

make check

上記の改良があればpriority-sema、condvarが通過する.

Priority Inversion Problem

に質問

優先度の高いスレッドは、低いスレッドを待つため、優先度が反転します.

改善方法

優先度は自分より低いthreadであるが、自分が必要とするロックを得るために、一時的に低いthreadの優先度(寄付)を高め、対応するロックを得る.

マルチ寄付:寄付を受ける前の状態の優先順位を覚えておいてください.

Nested寄付:必要なロックに関連付けられたすべてのスレッドの優先度を上げます.

lock_acquire():ロックholderが存在する場合、現在のスレッドwait on lock変数の取得を待つロックのアドレスが格納される.複数の寄付を考慮するために、以前の状態の優先度を覚え、寄付を受けたthreadをthread構造体listとして管理します.lockを取得したら、lock holderにcurrthreadを入れます.

donate_priority():最大DONATE MAX DEPTH(ネスト深度)に優先度を譲渡するコードを記述する.wait on lockのholderを見つけ、holderの優先度を更新します.この場合、curr threadの優先度がholderの優先度より高い場合にのみ更新されます.

remove_with_lock():currthreadの寄付(リスト)を表示し、戻りロックを待つスレッドを削除する関数を作成します.

refresh_priority():currthread優先度の関数が更新され、以前の優先度と寄付リストの優先度よりも高い値に更新されます.このとき、寄付リストは優先度の高い順に並べ替えられ、beginの優先度が決定される.

thread_set_priority():currthreadの優先度は寄付によって変更される可能性があるため、init priorityを更新する必要があります.後でrefresh_priority()をあげます.

検査結果

make check

上記の事項を適用するとpriority-denda-one、multiple、multiple 2、nest、sema、lower、chainが通過します.