恐竜本の5章練習問題を解きました。筆者のページから問題を見ることができます。
5.1 In Section 5.4, we mentioned that disabling interrupts frequently can
affect the system’s clock. Explain why this can occur and how such
effects can be minimized.
自身の回答：定期的な割り込みによって時刻管理のためのカウンターをインクリメントしているので割り込みを無効化するとカウンターがインクリメントされず時刻が遅れていく。そのような効果を最小化するためには割り込みの無効化を最小限に留める、時刻管理をOSで行うのをやめ特殊なハードを使うなどが考えられる。
解答：システムクロックはクロック割り込みごとに更新される。割り込みが無効化された場合、特に長い時間無効化された場合、システムクロックの時間が狂うということが容易に起こり得る。システムクロックはスケジューリング目的でも使われる。例えば、プロセスのタイムクオンタムはクロックのティック数で表される。クロック割り込みが起こるたびにスケジューラは現在動作しているプロセスのタイムクオンタムが執行したかどうかを判定する。クロック割り込みが無効化されたらスケジューラは正確にタイムクオンタムを割り当てることができなくなる。この効果はクロック割り込みの無効化を非常に短い時間にすることで最小化できる。
5.2 Explain why Windows, Linux, and Solaris implement multiple locking
mechanisms. Describe the circumstances under which they use spinlocks, mutex locks, semaphores, adaptive mutex locks, and condition
variables. In each case, explain why the mechanism is needed.
自身の回答：
スピンロック：プロセスがプリエンプトされるより前にロックが解放されると予想される場合、コンテキストスイッチを経ることなくロック解放を待てるスピンロックが効率的になる。他のロック方法はコンテキストスイッチが挟まる（？）
ミューテックス：クリティカルセクションに入れるスレッドが一つである場合にシンプルで利便性が高い。
セマフォ：リソースの数が2以上であるときにカウンタが内部で管理されるので利便性が高い。
adaptive mutex lock：これは何？
condition variables：何だったか忘れた
解答：OSはアプリケーション開発者の需要に依存して異なるロック機構を提供する。スピンロックはスレッドがスリープキューに入れられるオーバーヘッドを受けることなく、短い時間ビジーループで動作できるマルチプロセッサシステムで有用である。ミューテックスはリソースのロックに有用である。Solaris 2はadaptive mutexを使用しているが、これはミューテックスがマルチプロセッサマシンでスピンロックを用いて実装されていることを意味する。セマフォとcondition variablesはリソースが長い時間保持されなければならないときにより適切なツールとなる。
5.3 What is the meaning of the term busy waiting? What other kinds of
waiting are there in an operating system? Can busy waiting be avoided
altogether? Explain your answer.
自身の回答：ロックオブジェクトのロック状態をポーリングすることでロックの解放待ちを行う手法。OSが提供する同期手法としては、リソースが解放されるまでプロセスをwait状態にしてそのリソースのキューに入れる。キューの先頭に来たらプロセスをreadyとして実行キューに入れる。ビジーウェイトは完全に廃止することはできない。マルチプロセッサのマシンでカーネルがマルチスレッドだった場合そのカーネルをスケジューリングする存在がいないので、カーネルはビジーウェイトせざるを得ない。
解答：ビジーウェイトはプロセスがある条件がみたされるまでプロセッサを放棄することなくタイトなループで待つことを意味する。代わりとして、プロセスはプロセッサを放棄してある条件でブロックし、将来の適切な時刻に起こされるまで待つこともできる。ビジーウェイトは避けることができるが、それはプロセスをスリープさせ適切なプログラムの状態に到達したときに起こす必要があるというオーバーヘッドを課すことになる。
5.4 Explain why spinlocks are not appropriate for single-processor systems
yet are often used in multiprocessor systems.
自身の回答：シングルプロセッサだとスピンロック中は他のプロセスが動かないので、決してリソースが解放されることはない。そのためコンテキストスイッチまで時間をムダにすることとなる。一方マルチプロセッサだと他のプロセッサでプロセスが動いているのでCPU時間を使いながら待っているとリソースが解放されることがありうる。そのため無駄になる時間が少ない。
解答：スピンロックはスピンロックを抜ける条件は他のプロセスを実行することによってのみ得られるため、シングルプロセッサシステムでは適切ではない。プロセスがプロセッサを放棄しなければ他のプロセスはそのプロセスが進捗を生むのに必要な条件をセットする機会が得られない。マルチプロセッサシステムではほかのプロセスが別のプロセッサで実行でき、最初のプロセスをスピンロックから解放するためにプログラムの状態を変更することができる。
5.5 Show that, if the wait() and signal() semaphore operations are not
executed atomically, then mutual exclusion may be violated.
自身の回答：
解答：wait操作はセマフォに関連付けられた値をアトミックにデクリメントする。もし２つのwait操作が内部値1のセマフォに実行され、２つの操作がアトミックに実行されなかったとしたら、両方の操作がセマフォをデクリメントし、排他制御を破ることになる。
5.6 Illustrate how a binary semaphore can be used to implement mutual
exclusion among n processes.
自身の回答：あるプロセスがセマフォを獲得したとすると、他のプロセスはセマフォが解放されるまで待つことになる。プロセスがセマフォを解放すると待っていたプロセスのうち一つがセマフォを獲得し、ほかはやはり待ち続ける。この動作はmutexにほかならない。
解答：nプロセスがmutexという1に初期化されたセマフォを共有しているとする。それぞれのプロセスPiは次のように組織される。
do{
wait(mutex);
/*critical section*/
signal(mutex);
/*remainder section*/
}while(true);
コメント