第0章 序章 アルゴリズム 作業をどの様に遂行するかを定めた手順の集合 ある特定の型のすべての値についての問題をどの様に解くか ある作業を行うマシンが構成できる場合、その問題はアルゴリズムとして解けるし、アルゴリズムが存在しないなら、その問題の解はマシンの能力を超えたとこにある（計算可能性） ゲーデルの不完全性定理 プログラム アルゴリズムの表現の1つ プログラミング プログラムをマシンが理解できる形にして挿入するプロセス 抽象化 あるものの外面的な性質と内面的な構造の詳細を区別することを意味する 第1章 データストレージ ビットとその格納 ビット（bit） 情報を0と1に符号化したもの あくまで記号に過ぎない 処理するアプリケーションによって意味づけされる ビット自体は意味を持たない ゲート（gate） ブール演算の結果出力を生じる装置 フリップフロップ（flipflop） 値を保持することができる回路 Set 側を1にすると、常に1を出力するようになる Reset側を1にすると値は0にリセットされる ストリーム（stream） ビットの長い列 メインメモリ フリップフロップのような記録回路を大量に保持している セル（cell） メモリの構成単位 典型的には8ビット、1byte である ビット列自体に意味はないが、メモリセル中のビットを横に並べた時に、左端をhigh-order end、右端をlow-order endという 左端のビットはhigh-order bit、右端のビットはlow-order bit と呼ばれる アドレス（address） 各セルに付与されている一意な名前 全て数値（0始まり） 順序付けされている 構成要素 実際にビットを保持する回路 セルにデータを書き込む回路 セルからデータを読み取る回路 ランダムアクセス（random access） 任意のセルに瞬時にアクセスできるということ シークする必要がない ランダムアクセスメモリ（RAM） ランダムアクセスできることから名がついた 動的メモリ（dynamic memory） 揮発性の高いメモリ マスストレージ 揮発性が少ない 容量が大きい（傾向にある） 低価格（傾向にある） マシンと記録媒体を分離できる オンライン（online） 機器が接続されており、使用可能であること オフライン（offline） 機器が接続されておらず、使用できないこと メインメモリに比べて遅い フォーマット（format） 初期化 磁気ディスク 何層にも重なっており、その分のディスクとヘッドがある トラック（truck） ヘッドが辿っていく円状の領域 シリンダ（cylinder） 今からアクセスするトラックの集合 セクタ（sector） ビット列を記録する円弧状の領域 全てのセクタは同じ数のビットを持つことができる 外周に近いトラック上のセクタは中心に近いトラック上のセクタに比べてデータの密度が小さくなる 密度の小さい外周のトラックをゾーンビットレコーディング（zoned-bit recording）という手法で活用している 隣接する複数のトラックをゾーンとし、ゾーン中のトラックは全て同じ数のセクタを持つ 外側のゾーンと内側のゾーンのセクタ数を異なっていても、ゾーンとしてアクセスを提供することで密度の差による回転数のばらつきを抑える手法 ディスクシステムの性能評価 尺度 シーク時間（seek time） ヘッドをあるトラックから他のトラックへ移動するのに要する時間 レイテンシ時間（latency） ヘッドが求めるトラックと重なってから求めるデータの箇所が回ってくるまでの時間 おおよそディスクが半周するのにかかる時間となる アクセス時間（access time） シーク時間とレイテンシ時間の和 転送レート（transfer rate） ディスクとコンピュータ間の単位時間辺りのデータ転送量 光学システム 光学技術を応用したマスストレージ 反射材とその保護膜で構成されている 情報は反射材の表面に変調を生み出すことによって記録される レーザー光線を用いて回転する表面の不規則性を検知して情報を読み取る 円状であるため内側と外側のデータに密度の差が存在する 読み込んでいるレーザー光線の位置によって回転数を制御している コンピュータでの使用では、回転数が速すぎるため、転送速度を調整することによって対応している 長い連続したデータを扱うときに性能を発揮する ランダムアクセスでは磁気ディスクのアプローチの方が優れている フラッシュドライブ 電気的な信号をストレージ媒体に直接送ることでビットを格納する シリコン半導体の中に電気が格納され、回路の性質が変化する これらの格納域は格納した電気を何年にもわたって保持できる ファイルの格納と取り出し ファイル（file） 情報を概念的にグループ化したもの 物理レコード（physical record） ストレージの物理的な性質に合わせたデータのブロック 論理レコード（logical record） 情報の性質に合わせたデータのブロック フィールド（field） 論理レコード中の情報の概念的な情報単位 キーフィールド（key field） 論理レコードを一意に特定できるフィールド キー（key） キーフィールドの値 論理レコードのサイズと物理レコードのサイズが一致することはほとんど無い 物理レコード1つに収まるか、複数の物理レコードに跨るか 物理レコードから論理レコードを復元する方法 物理レコードを保持するのに十分なサイズのメモリ空間を確保する 物理レコードの倍数分のサイズが必要になる このサイズがブロックサイズ（block size）となる このように使用されるメモリ領域をバッファと呼ぶ 物理レコードをメモリ上に展開する 整えて、論理レコードを構築する バッファ（buffer） ある機器から他の機器へデータを転送するプロセスにおいて、データを一時的に保持するのに使用される領域 ビットパターンとして情報を表現する テキストの表現 ASCII ANSIが採用した 7ビット（1バイト）パターンを使用してアルファベット、句読点、0から9までの数字、制御文字を表現する Unicode 16ビット（2バイト）パターンを使用する 数値の表現 2進記法（binary notation） テキストで数値を格納するより効率が良い 2の補数表現記法（2s complement） 整数を表現する 浮動小数点記法（floating point） 実数を表現する 無理数や循環小数、大きな数などは丸められることがある 画像を表現する ピクセル（pixel, picture element（画素）の略） 画像上の点の集まり ビットマップ（bit map） 画像全体を符号化したピクセルの集合 符号化 白黒 0と1の1ビットで表現できる グレースケール 複数ビット（通常8ビット）を用いて濃淡も表現できる RGB 光の三原色に対応して（赤、緑、青）の3つの色要素として表現される 各色の要素の強さに1バイトを用いるため、1ピクセルを表現するのに3バイト必要になる 輝度とクロミナンス 構成要素 明るさ 青色クロミナンス ピクセルの青色光との差分 赤色クロミナンス ピクセルの赤色光との差分 カラーテレビ発祥の表現のため、グレースケールに変換することができる その場合、明るさだけが用いられる ビットマップ画像処理は画像を任意の大きさに拡大縮小することが難しい 幾何学構造での表現 画像を幾何学構造の集合として表現する 特定のピクセルパターンを再生するのではなく、幾何学構造をどのように表示するかを決めるだけで表示できる 音声を表現する 一定の間隔で音波の振幅を標本採取して得た値を数列として記録する手法 電話通信で使用されてきた 電子楽器デジタルインターフェース（Musical Instrument Digital Interface, MIDI） どの楽器がどの音をどれだけの時間発生させるかを符号化する シンセサイザーを用いて音楽を直接生成する 演奏するシンセサイザーによって音が全く異なる 整数を格納する エクセス記法 0を1000 として、正の数を1001 、負の数を0111 と数え上げていく記法 データ圧縮 データ圧縮（data compression） 基本的な情報は保ったままデータのサイズを縮小する手法 データ圧縮はロスなし（lossless）とロスあり（lossy）に分けられる ロスあり技法の方がロスなし技法よりも圧縮率が高いことが多い ランレングス符号化（run-length encoding） 圧縮されるデータの要素の列を、繰り返す要素とその数を示す符号へ置き換える AAABBBBCCCCCCD →A3B4C6D （1個の場合に数字を省略するかは手法による） ロスなし圧縮である 圧縮されるデータが同じ値の長い列である場合に効率的 頻度依存符号化（frequency-dependent encoding） 表現するデータ項目のビットパターンを反比例させる手法 ハフマンコード（ハフマン符号化）（Huffmann code）が有名 現在使用されている頻度依存符号化の殆どがハフマンコード AAABBBBCCCCCCD 頻度はC, B, A, Dの順 Cを1、Bを10、Aを110、Dを111とする 110110110101010100000000111 相対符号化（relative encoding）・差分符号化（differential encoding） 連続するデータ単位の差分を用いて符号化が行われる 直前の単位との関係も含めて符号化が行われる ロスあり、ロスなしどちらも対応する 辞書式符号化（dictionary encoding） 辞書とは、圧縮されるメッセージが構成される構築ブロックの集合 メッセージそのものが辞書への参照として符号化される 適合型辞書式符号化（adaptive dictionary encoding） 符号化のプロセスで辞書を変更できる LZW符号化（Lempel-Ziv-Welch encoding）が有名 メッセージが構築される基本構築ブロックを含む辞書からはじめる メッセージ中により大きな単位が見つかるとそれを辞書に追加する 符号化が進む毎に辞書が成長していく 復号化するときに大きな辞書は不要で初期の基本的な辞書のみで良い 復号化していく最中に符号化時と同様に辞書に追加していく 大きな構築ブロックは小さな構築ブロックによって構築されているため、大きな構築ブロックは基本的な辞書、またそれに途中で追加されてきた構築ブロックによって復号化できる 画像を圧縮する GIF（graphic interchange format） ロスあり圧縮 まずピクセルあたり256色を割り当てる 色をパレットと呼ばれる辞書に割り当てる 画像中の各ピクセルは、そのピクセルの色を表現するパレット中の256色のエントリを示す1バイトとして表現される JPEG ロスあり、ロスなしどちらも対応 圧縮率によって複数の戦略を使用する デフォルトの圧縮手法 人間の視覚が色の変化より明るさの変化に敏感であることを利用する 画像を輝度と色度に分割する 2x2ピクセルの正方形の色度の平均を求め、そのブロックの色とする これにより、輝度を保ったまま1/4に圧縮できる 画像を8x8のピクセルブロックへ分割し、離散余弦変換（discrete cosine transform）を用いて変換する 他のブロックと相対的にどうかというデータに変換される ある程度の値以下の場合0となる 更にランレングス符号化や相対符号化などの手法を適用する JPEGでは目に見える劣化なしに1/10から1/30程度へ圧縮できる 音声とビデオを圧縮する MPEG 前のフレームとの差分のみを保持することで圧縮する MP3 人間の耳が認識できない音を消す 継時マスキング（temporal masking） 大きな音の直後の柔らかな音を感知できない性質 周波数マスキング（frequency masking） ある周波数の音が、近い周波数のより柔らかな音を覆い隠す性質 音声やビデオの圧縮システムでは、実時間でのデータ通信に必要な送信速度によって判断されることが多い ビット毎秒（bit per second）によって計測される よく使用される単位はKbps、Mbps、Gbpsなど MPEGでは40Mbpsほど、MP3では64Kbpsほど必要となる 通信エラー パリティビット（parity bit） 奇数パリティ（odd parity） ビット全体の1の数を奇数個にするようパリティビットを立てること 偶数パリティ（even parity） ビット全体の1の数を偶数個にするようパリティビットを立てること コンピュータのメインメモリでは当たり前に使用されている なので実際のメモリセルでは9ビットのパターンとして格納されている 取り出す際には専用の回路を用いて検査し、エラーが無ければ8ビットパターンを返す エラーがあれば警告する 複数のエラーが発生した時にエラーを検出できない 数の偶奇が変わらない チェックバイト（check byte） パターン中に散在する特定のビットの集まりに対するパリティビット 8ビットおきにグループ化しそれぞれにパリティビットを設定するなど チェックバイトの概念よりチェックサム（check sum）や巡回冗長検査（cyclic redundancy check, CRC）として知られるエラー検出方法が考案された エラー訂正符号 パリティビットはエラー検出は可能だが、訂正する情報を提供するものではない エラーが訂正可能な符号が設計可能である ハミング距離（Hamming distance） パターン中で異なるビットの数 各誤り訂正コードに等しいハミング距離をもたせる 復号化する際にそれぞれのコードを比較する ハミング距離が1以下のコードが正しい記号である 第2章 データ操作 中央演算処理装置（central processing unit, CPU） コンピュータ内でデータの操作を行う 構成要素 算術論理ユニット（arithmetic logic unit, ALU） 加算減算などのデータの演算を実行する 制御ユニット（control unit） マシンの実行を制御する レジスタユニット（register unit） レジスタのデータを格納したり読み出したりする レジスタ（register） 小容量だが高速なデータ格納用セル 汎用レジスタ（general-purpose register） CPUによって行われる計算の一時的な保管場所 専用レジスタ（special-purpose register） バス（bus） CPUとメモリ間の転送路 キャッシュメモリ（cache memory） メインメモリに対するキャッシュ メインメモリの一部を転写している プログラム内蔵方式（stored-program concept） データとプログラムをメインメモリ上に配置し、データだけでなくプログラムも書き換えられるようにしたもの マシン語 マシン語（machine language） 符号化の体系を含む命令の集合 プログラム内蔵方式を適用するため、CPUはビットパターンに符号化された命令を認識できる必要がある 縮小命令セットコンピュータ（reduced instruction set computer, RISC） 命令数を少なくし、複雑なタスクは簡単な命令を複数組み合わせて実行するモデル 複合命令セットコンピュータ（complex instruction set computer, CISC） 特定の複雑なタスクを一命令で実行する専用命令を多く実装するモデル マシン命令 データ転送命令 データをある場所から他の場所へ移動する命令群 メインメモリからデータを読み取るときはload命令 、格納するときはstore 命令と呼ぶ CPUとメインメモリの外側にある危機との通信を行う命令はI/O命令と呼ぶ 算術・論理命令 算術演算や論理演算、値を操作する演算を行う命令群 制御命令 プログラムの流れや実行の順序を変える命令群 条件ジャンプ（conditional jump）命令や無条件ジャンプ（unconditional jump）命令などがある オペコード（op-code, operation code） どの命令かを表す部分 オペランド（operand） 命令で使用する値の部分 命令の引数 権限レベル（privilege level） 特権モード（privileged mode） 全ての命令を実行できる 特権命令（privileged instruction） 特権モードの時のみ実行できる命令 非特権モード（non-privileged mode） 実行できる命令が制限される 命令の実行順序はメモリに格納された順序である 命令レジスタ（instruction register） 実行される命令を保持する プログラムカウンタ（program counter） 次に実行される命令のアドレスを持つ マシンサイクル（machine cycle） CPUが計算を実行するステップ fetch プログラムカウンタが指す命令を取り出す 命令を命令レジスタに格納する プログラムカウンタをインクリメントする decode 命令レジスタの命令をオペコードとオペランドに分ける execute 指定のオペコードに対応する回路を起動する オペランドを入力して結果を取得する クロック（clock） 各機器が協調して動作するためのタイミングを取る回路 論理演算 マスキング（masking） 論理演算を用いて、必要な部分にのみビットを立てることで、該当箇所のみを複写する技法 AND演算によるマスキング ビットを立てた部分を複写できる それ以外の箇所は0 OR演算によるマスキング ビットを立てた部分を複写できる それ以外の箇所は1 XOR演算によるマスキング ビット列の補数を形成できる 循環シフト（circular shift）・ローテーション（rotation） シフトさせてはみ出たビットを反対側の空いたところにセットする 論理シフト（logical shift） シフトして空いたところに0をセットする 左にシフトすると2倍に、右にシフトすると半分の値になる 算術シフト（arithmetic shift） シフトして空いたところに0をセットする 右シフト時は符号を変えないように元の値をセットする コントローラ（controller） コンピュータと他の機器の通信を制御する中継機器 ポート（port）を介して接続している バスに接続しているため、CPUはバスを通じてコントローラと通信する メモリマップドI/O（memory mapped I/O） メインメモリとコントローラでアドレス空間を共有する手法 メインメモリと同じオペコード、LOADとSTOREを使用して機器と通信を行う 特定のアドレスが各コントローラを参照するように紐づけ、該当のアドレスへのアクセスが来た時に、メインメモリを無視しコントローラへアクセスする ダイレクトメモリアクセス（direct memory access, DMA） CPUがバスを使用していないタイミングでコントローラとメインメモリが直接通信を行う手法 CPUを介せず直接通信ができるので性能が向上する 処理の流れ CPUがコントローラに読み出し命令を送信 コントローラが読み取り演算を実行し、メインメモリから直接読み取る CPUはI/O待ちが無いので、別の処理を実行できる バス上で実行される通信が複雑になるデメリットがある CPUとコントローラがバスのアクセスで競合する フォン・ノイマン・ボトルネック（Von neumann bottleneck）として知られる ハンドシェーキング（hand shaking） コンピュータと外部機器間で調整を行うためにステータスワード（status word）などを用いて双方向で対話すること パラレル通信（parallel communication） 複数の線上で同時に信号を送ること データを高速に転送できる 順序決定や制御など、複雑な通信経路が必要 シリアル通信（serial communication） 1本の線を用いて次々に信号を送ること 通信経路が単純 電話回線を用いた通信 モデム（modem, modulator-demodulator） 送信するビットパターンを音声に変換し、電話回線を用いてシリアルに転送する 受け取った音声をビットパターンに再変換する DSL（digital subscriber line） 通常の音声通話で使用されるより高い周波数帯域をデジタルデータ転送に使用し、音声通話での使用との効率化を図る 帯域幅（bandwidth） 転送できる容量が大きいということ ある転送経路が高帯域（broadband）を持つということは、転送速度が速く、同時に多くの情報を運べるということである スループット（throughput） 与えられた時間内にどれだけのタスクをこなせるか パイプライン化（pipelining） マシンサイクルのステップを重複させること execute中に命令のfetchも同時に行うなど 実行速度を上げることなくスループットを高められる 並列処理（parallel processing） SISD（single-instruction stream, single-data stream） 単一の命令によって単一のプロセッサが単一のデータを処理すること MIMD（multiple-instruction stream, multiple-data stream） 複数の命令によって複数のプロセッサが異なるデータを並行して処理すること バスを用いて通信する場合、バスがボトルネックになりやすい SIMD（single-instruction stream, multiple-data stream） 単一の命令によって複数のプロセッサが単一のデータを処理すること あるデータソースに対して、同期を取りながら複数プロセッサで処理する データサイズが大きいものに対し、同じような処理を繰り返す際に有用 第3章 オペレーティングシステム オペレーティングシステム（operating system） コンピュータ全体の動作を管理する ジョブ（job） プログラムの実行単位 バッチ処理（batch processing） 関連するジョブを1つのまとまり（バッチ）として実行すること 初期のオペレーティングシステムはバッチ処理を管理するシステムだった ジョブキュー（job queue） バッチのジョブを溜めておく所 優先度付きの先入れ先出し（first-in, first-out）である 対話型処理（interactive processing） ジョブ中にユーザの介入を受け入れる事ができる処理環境 リアルタイム処理（realtime processing） 動作が瞬時に実行されなければならない処理環境 指定の締切までに必ずジョブを完了させなければならない 複数ユーザが同時に使用する環境において、実装には留意が必要 タイムシェアリング（time-sharing） 複数のユーザに同時にサービスを提供する機能 マルチプログラミング（multiprogramming） いわゆる並行処理 コンピュータの実行時間を細かく区切り、複数のジョブを高速に切り替えることで、同時に実行していると見せかけること 初期の実装では30人程度のユーザのリアルタイム処理が可能だった マルチタスキング（multitasking） 同時に複数の作業を行うこと オペレーティングシステムは、プログラムを一度に1つずつ取り出して実行する単純なプログラムから、タイムシェアリングを調整し、マシンのマスストレージ装置内にプログラムやデータファイルを保持し、ユーザからの要求に直接応答する複雑なシステムへと成長した オペレーティングシステムのアーキテクチャ アプリケーションソフトウェア（application software） マシンを利用して作業を行うためのプログラムから構成される システムソフトウェア（system software） コンピュータシステム一般に共通する作業を実行する アプリケーションソフトウェアが必要とするインフラストラクチャを提供する ユーティリティソフトウェア（utility software） コンピュータの利用に必要であるが、オペレーティングシステムには含まれないソフトウェア オペレーティングシステムの機能を拡張する オペレーティングシステム ユーザインターフェース（user interface） ユーザと対話する部分 シェル（shell） テキストメッセージを用いる対話環境 グラフィカルユーザインターフェース（graphical user interface, GUI） リッチな動きや装飾を持つ対話環境 ウィンドウマネージャ（window manager） ウィンドウとそれを利用するアプリケーションの割当とその情報の保持を行う カーネル（kernel） コンピュータの最も基本的な機能を実行するためのシステムソフトウェアが含まれる ファイルマネージャ（file manager） マスストレージに格納されている全てのファイルの情報を保持している 場所やアクセス権限、作成日時など Linuxではinode パス（path） 特定のファイルが存在する場所 デバイスドライバ（device driver） 接続されている周辺機器を操作するため、コントローラ（場合によっては直接外部機器）と通信する メモリマネージャ（memory manager） 各プロセスに対するメモリの割り付けを行う ページング（paging） メインメモリの一部をマスストレージに移すことで、実際の容量以上のメモリ領域があるかのように見せること 仮想メモリ（virtual memory）と呼ぶ ページ（page） 保存されるデータを数KB単位で均等に分割したもの メインメモリとマスストレージ間では、ページ単位でデータが交換される スケジューラ（scheduler） プロセスの実行を調整する ディスパッチャ（dispatcher） スケジュールされたプロセスの実行を管理する プロセス実行のための時間をタイムスライス（time slice）という短いセグメント（通常はμ秒単位）に分割し、プロセスを1つのタイムスライス分だけ実行する コンテキストスイッチ（context switch） あるプロセスから別のプロセスに変更する手続き オペレーティングシステムの起動 ブートストラップ（boot strapping）・ブースティング（booting） オペレーティングシステム起動の手続き コンピュータに電源が入るたびに実行される CPUは起動される度に特定のアドレスからプログラムカウンタが始まるように設計されている メインメモリは揮発性なので、電源が入る度にメインメモリにプログラムをロードする必要がある 読み取り専用メモリ（read-only memory, ROM） 揮発しないため、電源がなくても起動時に必要なプログラムを格納しておくことができる CPUのプログラムカウンタは起動時にこの領域を指している事が多い ブートローダ（boot loader） 設定に従って特定の場所に格納されているオペレーティングシステムをメインメモリにロードし、プログラムカウンタにそのアドレスをセットする ROMに格納されていることが多い ファームウェア更新（firmware update） オペレーティングシステムの実際のファイルはマスストレージに格納されているので、ファームウェア更新の際はマスストレージにあるファイルの更新と整合性チェックを行うことで、起動中でも更新処理が可能 メインメモリにロードされているオペレーティングシステムには影響が無い オペレーティングシステムにおけるプログラム実行の調整 プロセス（process） オペレーティングシステムの制御下で動作しているプログラム プロセス状態（process state） プロセスの状態 以下の要素が含まれる プログラムカウンタの値 CPUレジスタの値 使用しているメモリセルの値 プロセス管理 プロセス実行の調整はカーネル中のスケジューラとディスパッチャによって行われる プロセステーブル（process table） スケジューラが持つプロセス情報の一覧 メインメモリに保持している プロセス実行が要求される度にスケジューラはプロセステーブルに新たなエントリを作成する プロセスに割り付けられたメモリ領域、プロセスの優先順位、プロセス状態などの情報が含まれている プロセスが続行可能な状態であれば準備完了（ready）、 ストレージ操作の完了や他のプロセスからのメッセージ到着といった外部イベント発生を待っている時は待機中（waiting）になる マルチプログラミングにおけるプロセス切り替えの流れ ディスパッチャはスケジュールされたプロセスにタイムスライスを割り当て、プロセスを実行する 同時にタイマー回路を起動し、タイムスライスの消費を確認する タイマーは作動（タイムスライスを消費）すると、割り込み（interrupt）シグナルを発生させる CPUが割り込みシグナルをキャッチし、現在のマシンサイクルを終了させ、プロセスの情報を保存する CPUから割り込みハンドラ（interrupt handler）へ処理が委譲される ディスパッチャの一部であり、メインメモリの決められた場所に格納されている ディスパッチャが割り込みシグナルに対してどのように対応するかが記述されている ディスパッチャは、プロセステーブルの準備完了プロセスの中で、最も優先順位の高いプロセスを選択し、プロセスを起動する マルチプログラミングを用いることで、I/O待ちの時間に別のプロセスを実行することができるなど、マシン全体の効率が向上する プロセス間競合の調整 セマフォ（semaphore） あるリソースが何かに獲得されているかを示すフラグ セット（set）で獲得され、クリア（clear）で開放される セットフラグ（値1）ではリソースは何かに格納されている クリアフラグ（値0）ではリソースは利用可能である 競合状態 2つのプロセスがセマフォの状態を確認後、獲得しようとする プロセスAがセマフォの状態を参照する セマフォはクリアフラグを示す プロセスAが割り込まれる プロセスBがセマフォの状態を参照する セマフォはクリアフラグを示す プロセスBがセマフォをセットする プロセスAに処理が戻る プロセスAは既にセマフォの確認が完了している プロセスAがセマフォをセットする 対策 割り込みが発生しないようにする 割り込み不能命令と割り込み可能命令を使用する テストアンドセット（test-and-set）命令を使用する フラグの値の取り出し、値の確認、フラグのセットを1命令で行う 相互排除（mutual exclusion） 同時に1つのプロセスしか実行できないようにすること クリティカル領域（critical region） 相互排除である命令の区間 デッドロック（dead lock） 2つ以上のプロセスがそれぞれ他社に割り付けられたリソースの獲得を待ち合って処理が進められない状態 注意：すでにプロセステーブルが満杯でスケジューラが新たなプロセスを登録できないにも関わらずプロセスが部分作業を実行させるためにforkしようとしている場合、どのプロセスも処理を続行できず、デッドロックしてしまう デッドロックの条件 1....