オペレーティングシステム
このページにまとめて、まとまったものからページを切り分けることにする
計算機システムは4つのコンポーネントに分割できる
ハードウェア
計算リソースを提供する
アプリケーションやユーザの間でハードウェアの利用を制御したり調整したりする
アプリケーションプログラム
システムリソースをどのように使ってユーザの問題を解くかを定める
Wordとか、コンパイラとか、Webブラウザとか
ユーザ
人、機械、自身以外の計算機
OSは何をするか
ユーザはリソースの割り当て？（resource utilization）に気を取られたくない
OSはリソースの割り当てと制御を行うプログラム
ハードウェアを効率的に利用して、ユーザが書いたプログラムを実行することを担当する
モバイル端末はリソース的には貧弱なのでユーザビリティやバッテリーの最適化が必要
インタフェースとしてはタッチスクリーン、音声認識が使われる
周辺端末や自動車に内蔵された組み込みコンピュータにはインタフェースがないか、あっても少し
主にユーザの介入なく実行される
コンピュータシステムの仕事
I/OデバイスやCPUは並行して実行できる
デバイスコントローラ
特定のデバイスを担当している
ローカルバッファを持っている
デバイスを管理するためにOSのデバイスドライバを備えている
CPUはデータを主記憶装置に対して入出力する
デバイスからI/Oが入力され、コントローラのローカルバッファに出力される
デバイスコントローラは割り込みによって終了すると、CPUに通知する
割り込みは通常、制御を ISR: interrupt service routine に移す 割り込みが発生したとき、割り込まれた命令のアドレスが保存される必要がある
ユーザリクエストやエラーによってソフトウェアが発生させる割り込みのことを、トラップや例外という OSはinterrupt driven
割り込み駆動？
割り込み制御
OSはレジスタとプログラムカウンタを保管することでCPUの状態を保存する
polling か vectored interrupt system のどちらの割り込みが発生したかを決定する
ベクター割り込み？
割り込みの種類によって取るべき行動を決定するコードのセグメントが用意されている
ここあまりよくわかっていない momeemt.icon
2つのI/O制御
I/Oが開始したら、I/Oが完了するまでユーザプログラムに制御を戻さない
同期処理？
次の割り込みが発生するまでCPUをアイドル状態にする
あるいは、ループして完了したかどうかを確認する
メモリアクセスにおいて競合が発生しやすい
同時に処理できるI/Oリクエストは1つだけで、同時に複数のI/Oを処理することはできない
I/Oが開始したら、I/Oの完了を待たずにユーザプログラムに制御を戻す
ユーザは以下のような手段でI/Oの完了を知る
ユーザがOSにリクエストすることでI/Oの完了を待てるようにする
CPUやOSの状態をシステムコールを通じて知ることができる？momeemt.icon
I/Oデバイスの種類、アドレス、状態を確認できるテーブル
OSがデバイスの状態を決定したり、割り込みを含むようにテーブルエントリを変更したりするために、I/Oデバイステーブルにインデックスを作成する
ストレージ構造
CPUが直接アクセスできる唯一の記憶装置
不揮発性のストレージ
/icons/-.icon
You are required to explain why Peterson's Solution is effective in solving the critical section problem. Your explanation should focus on the following three key properties: Mutual Exclusion, Progress, and Bounded Waiting.
Instructions:
Your report should clearly explain how Peterson's Solution satisfies these three properties.
Ensure your explanation is detailed and logically structured.
Answers in English are recommended, but Japanese will also be accepted.
## Overview
Peterson's Solution lets two processes share resources without conflicts. It uses two things: a flag array and a turn variable. The flag array shows if a process wants to enter the critical section, and the turn variable decides which process should wait when there is a conflict. This report explains how Peterson's Solution meets the following three properties.
- Mutual Exclusion
- Progress
- Bounded Waiting
## Mutual Exclusion
Mutual Exclusion means that only one process can be in the critical section at a time. Peterson's Solution achieves this with these steps.
- A process sets its flag to 1 when it wants to enter the critical section.
- It sets the turn variable to the other process.
- Before entering, the process waits until this condition becomes false:
`
code
while (flagother && turn == other); `
For example, if both processes p0 and p1 want to enter the critical section, and p0 sees that flag[1] == 1 and turn == 1, p0 will wait. This makes sure that both processes cannot enter at the same time, which ensures mutual exclusion.
## Progress
Progress means that if the critical section is free, one of the waiting processes can enter.
In Peterson's Solution, if neither process wants to enter the critical section (flag[0] == 0 && flag[1] == 0), the first process to set its flag to 1 will enter. When a process leaves the critical section, it sets its flag to 0. This allows the other process to enter immediately.
For example, if p0 finishes its work and sets flag[0] = 0, p1's waiting condition will be cleared, and p1 can enter. This ensures there is no deadlock, and the program keeps running when the critical section is free.
## Bounded Waiting
Bounded Waiting means no process has to wait forever to enter the critical section. Peterson's Solution ensures this by using the turn variable to make scheduling fair.
When a process enters the critical section, it sets turn to the other process. This gives the other process a chance to enter next. This cycle continues so that no process is forced to wait indefinitely.
For example, even if p0 tries to enter the critical section repeatedly, if p1 also wants to enter, p0 will have to wait because turn = 1. This ensures that each process gets a fair chance to access the critical section.
## Conclusion
Peterson's Solution satisfies the three important properties for solving the critical section problem: mutual exclusion, progress, and bounded waiting. It can be implemented also highly simple, so it is effective and strong algorithm.
/icons/-.icon
概要
Petersonのアルゴリズムは、2つのプロセス間でリソースを競合することなく共有するためのアルゴリズムである。これは、flag配列とturn変数の2つを用いて、競合を防ぎつつ公平にリソースを管理する。flag配列は各プロセスがクリティカルセクションに入りたいかどうかを示し、turn変数は競合が発生した場合にどちらのプロセスが優先されるべきかを決定する。本レポートでは、Petersonのアルゴリズムが以下の3つの性質をどのように満たすかについて説明する。
Mutual Exclusion
Progress
Bounded Waiting
Mutual Exclusion
Mutual Exclusionとは、同時に複数のプロセスがクリティカルセクションに入らないことを保証する性質である。Petersonのアルゴリズムでは以下の仕組みでこれを実現する。
各プロセスがクリティカルセクションに入りたい場合、flag配列の対応する要素を1に設定する
次に、turn変数を相手プロセスの識別子に設定する
クリティカルセクションに入る前に、以下の条件を満たすまで待機する
code:c
while (flagother && turn == other); 例として、プロセスp0とプロセスp1の競合を考える。p0がクリティカルセクションに入ろうとする際、もしflag[1] == 1 && turn == 1なら、p0は待機する。これにより、両方のプロセスが同時にクリティカルセクションに入ることが防がれ、相互排他性が保証される。
Progress
Progressとは、クリティカルセクションが空いている場合、どちらかのプロセスが適切にそのセクションに入ることが保証される性質である。
Petersonのアルゴリズムでは、どちらのプロセスもクリティカルセクションに入りたがっていないとき（flag[0] == 0 && flag[1] == 0）、最初にflagを1に設定したプロセスが待機条件を抜けてクリティカルセクションに入ることができる。
また、1つのプロセスがクリティカルセクションから抜けると、そのプロセスはflagを0に設定します。これにより、もう一方のプロセスは即座にクリティカルセクションに入ることができる。例えば、p0がクリティカルセクションを終了した場合、flag[0] = 0となり、p1の待機条件が解除される。したがって、クリティカルセクションが空いているときにデッドロックが発生せず、プログラムの実行が止まらないことが保証される。
Bounded Waiting
Bounded Waitingとは、あるプロセスがクリティカルセクションに入るまでの待ち時間が無限に長くならないことを保証する性質である。Petersonのアルゴリズムでは、turn変数が公平なスケジューリングを保証する。
プロセスがクリティカルセクションに入る際、必ずturnを相手のプロセスに設定する。これにより、次に実行されるのは相手プロセスとなる。
この仕組みを繰り返すことで、どちらか一方のプロセスが無限に待機し続けることを防ぐ。
例えば、p0が何度もクリティカルセクションに入りたい場合でも、p1がクリティカルセクションを希望すれば、p0はturn = 1によって一度待機させられる。これにより、各プロセスは必ず一定の順番でクリティカルセクションにアクセスできるので、有界待ち時間が保証される。
結論
Petersonのアルゴリズムは、クリティカルセクション問題を解決する上で必要な相互排他性、進捗性、有界待ち時間の3つの性質を満たしている。また、アルゴリズムが非常にシンプルであり、クリティカルセクション問題を解くために効果的な手法であると考えられる。
ピーターソンのアルゴリズムは、各プロセスがクリティカルセクションに入りたいという情報を保持するflag配列と、その時点で優先権を持つプロセスの識別子を保持するturn変数の2つの変数を用いて、2つのプロセス間でリソースを競合することなく共有するために使用されます。
2つのプロセス、プロセス0とプロセス1がそれぞれクリティカルセクションにアクセスするような状況を考えます。プロセス0がクリティカルセクションに入りたい場合、まずは自分自身がクリティカルセクションに入ることを示すために、flag[0] = 1に設定します。次に、turn変数を自分ではないもう片方のプロセスの識別子に設定します（turn = 1）。その後、相手がクリティカルセクションに入りたがっていて（flag[1] = 1）、かつturnが示すプロセスの識別子が相手のものだった場合（turn = 1）には、そうでなくなるまで待機します。その後、クリティカルセクションに入って所定の処理を行ってから、 フラグの値を元に戻します（flag[0] = 0）。
ミューテックスはMutual Exclusion、Progress、Bounded Waitingの3つの基本条件を満たす必要がありますが、ピーターソンのアルゴリズムはこれら全てを満たしています。まず、プロセス0がクリティカルセクションに入っているとき、flag[0] && turn == 0が満たされています。したがって、プロセス1は待機条件を満たすため、その間はクリティカルセクションに入ることができず、相互排他が満たされます。次に、プロセス0がクリティカルセクションに入っていないとき、待機条件を満たさないのでプロセス1は即座にクリティカルセクションに入ることができます。したがって、Progressです。最後に、各プロセスはクリティカルセクションから抜けるとすぐにフラグを書き換えるので、クリティカルセクション1回分の処理時間以上に待機する必要はありません。したがって、Bounded Waitingを満たします。
Petersonのアルゴリズムは上のような性質を満たすので、クリティカルセクション問題を解くアルゴリズムとして適していると考えられます。