オペレーティングシステム
OS の種類と特徴
システムソフトウェア,UNIX,PC 用 OS,オープン OS,リアルタイム OS,VM (Virtual Machine:仮想マシン),互換性OS の機能と構成
マイクロカーネル,モノリシックカーネル,ミドルウェア,カーネルモード(ス ーパバイザモード),特権モード,ユーザモード,非特権モード,コンパイラ, インタプリタ,リンケージエディタ,サービスプログラム,仮想記憶管理,プロ セス管理,タスク管理,記憶管理,データ管理,運用管理,障害管理,入出力管 理,ユーザ管理,割込み,多重(マルチ)プログラミング,ブートストラップ, ネットワークブート,マルチブート,フラッシュブートローダジョブ管理
ジョブスケジューラ,マスタスケジューラ,セション,省力化,自動運転,シス テム管理,バックグラウンドジョブ,バッチ処理,cronタスク管理
@ タスクと状態遷移 タスクとジョブステップ,スレッドとの関係,タスクの生成から実行,消滅までの状態 遷移,ディスパッチャの役割を理解する。 用語例 軽量プロセス,実行可能状態,実行状態,待ち状態,プロセス,スレッド A 多重(マルチ)プログラミング(マルチタスク)とスケジューリング 多重(マルチ)プログラミングの考え方,タスクのスケジューリングの代表的な方式に ついて,スケジューリングの方法,特徴,スケジューリングにおけるトリガと優先順位の 役割,同期制御・排他制御の必要性,実現方法を理解する。また,タスクとタスクの同期, タスク間でのデータの受け渡し,マルチスレッドの考え方,並列処理などを理解する。 用語例 プリエンプティブ方式,ノンプリエンプティブ方式,タイムスライス方式,イベ ントドリブン方式,フィードバック待ち行列方式,処理時間順方式,優先順,静 的優先順位方式,動的優先順位方式,ラウンドロビン,SJF(Short Job First), 最短時間順,割込み禁止,マルチ CPU,排他制御,FCFS(First Come First Served),タイムクウォンタム,リソーススタベーション,SVC(SuperVisor Call)割込み,入出力終了割込み,ディスパッチタスクの状態遷移
実行可能状態(ready state):タスクは実行できる状態にあり、CPU使用権が与えられるのを待っている状態
実行状態(running state):CPU使用権が与えられ処理を実行している状態
待ち状態(wait state):入出力の完了、あるいはほかのタスクタスクからの合図を待っている状態。
タスクの管理
カーネルはタスクが生成されるとTCB(Task Control Block:タスク制御ブロック)にタスク情報を登録し、タスクが消滅するまで管理
タスク情報:タスクID、優先順位、状態、レジスタ群格納アドレス
タスクの切り替え
コンテキスト切り替え:PSWや主記憶アドレス空間などを交互に切り替える
PSW(Program Status Word):プログラムの実行に必要な情報を保持するレジスタやカウンタ群
PSWなどレジスタ群の切り替えは高速に行えるが、アドレス空間の切り替えはオーバーヘッドが大きくなる。スレッドの場合は、アドレス空間は共有しているため、コンテキストの切り替えにオーバーヘッドは大きく減少する
タスクのスケジューリング方式
イベントドリブン方式:タスクの状態の変化をトリガとしてスケジューリング
タイムスライス方式:一定期間(タイムクウォンタム)ごとにスケジューリング
静的優先順位方式:あらかじめ決められた固定優先順位に従ってスケジューリング
動的優先順位方式:優先順位を動的に変更しながらスケジューリング。プリエンプション方式。
到達順方式(FCFS:First Come First Served方式):タスクには優先順位をもたせず、実行可能状態になった順に実行。ノンプリエンプション方式
スタベーション:優先順位の低いタスクにはCPU使用権が与えられずなかなか実行できない
ラウンドロビン方式:実行可能待ち行列に到達した順に従ってタスクにCPU時間を一定時間ずつ割り当て、一定時間に終了しない場合には再び実行可能状態になり同一優先順位の実行可能待ち行列の最後尾に並ぶ方式
フィードバック待ち行列方式:ラウンドロビン方式に優先順位を与える。一定時間内に処理が終了しない場合、順位優先順位を下げていく方式。
処理時間順方式、SPT(Shortest Processing Time First)方式:処理時間の短いタスクに対し、高い優先順位を与える
イベントドリブンプリエンプション方式:静的優先順位方式と組み合わされ、入出力の終了やコマンドの割込みをトリガとして、次に実行するタスクを決める
同期制御
イベントフラグ
SETシステムコール:ビットをオンにする
CLEARシステムコール:ビットをオフにする
WAITシステムコール:ビットがオンになるまでタスクを待たせる
Post/Wait命令:一つのイベントをWaitとPostの2ビットで表現し、一つのタスクが情報を送り、毛筆のタスクは情報が来るのを待って同期をとる方式
プロセス間通信(IPC:Inter-Process Communication)
記憶空間共有型:複数のタスクから参照や書き込みができる共有(シェアード)領域を用いてデータの交換を行う
OSが提供する機能:メールボックス、クリップボードなど
ランデブ機構:プログラム言語Adaによってサポートされている同期制御と同時にデータ転送を実現させるための機構
パイプ機構:一つのタスクの出力を他方のタスクの入力とする方法
排他制御
クリティカルセクション:複数のタスクが共有する共有資源(shared resouce)に対し、同時に更新処理を行うとエラーを引き起こす処理部分
TSL(Test Set Lock)命令:共有メモリ内の1ビットを使用し、ロック/アンロックのロジックを実現
2値セマフォ
セマフォ:排他制御のメカニズム。セマフォ変数とそれを操作するP操作V操作。
P(S)操作の定義
S>0の場合:Sの値を1減らし、Pを実行したタスクの実行を継続(クリティカルセクションに入る)
S=0の場合:Pを実行したタスクはSの待ち行列にいれらて待機状態になる
V(S)操作の定義
Sの値を1増やす。Sの待ち行列から1つのタスクが選ばれ、実行可能状態にうつされる(P操作実行の許可)
セマフォSの初期値:1、ゼネラルセマフォの初期値:n
EQN(enqueue)/DEQ(dequeue)命令:共有資源の占有要求および開放を行う排他制御専用の命令
EQN命令:共有資源の占有要求を行う
DEQ命令:共有資源の占有使用解放を行う
デッドロック:排他的制御を複数の共有資源に対して行おうとすると、互いに相手が占有している資源の解消を待ちあう状態
対策:デッドロックが発生するまで、資源割り当て制限は行わずデッドロックが発生したときに何らかの対処をとる
デッドロックが生じないように、あらかじめ割り当てと解放の順を決めておく、静的防止法
資源の割り当て状態に応じて、デッドロックが生じないように動的に割り当てを行っていく動的防止法
データ管理
レコード,スペース管理,カタログ管理,ファイル保護入出力管理
IOCS(Input/Output Control System:入出力制御システム),スプーリング,バ ッファプール,入出力ポート(I/O ポート),入出力マッピング(I/O マッピン グ),メモリマッピング,チャネル,チャネル制御方式,DMA(Direct Memory Access:直接記憶アクセス),入出力割込み,メモリマップド I/O,I/O マップド I/O記憶管理
@ 実記憶管理 記憶領域の管理方式である固定区画方式,可変区画方式など,実アドレス空間の割当て 方式の特徴,フラグメンテーションとその対策を理解する。また,主記憶装置を効率良く 使うためのスワッピングとオーバレイを理解する。 用語例 実アドレス方式,単一連続割当て方式,記憶域管理アルゴリズム(ファーストフ ィット,ベストフィット,ワーストフィット),メモリコンパクション,ロール イン,ロールアウト,スワップイン,スワップアウト,セグメント方式,コンパ クション A 仮想記憶管理 実記憶と仮想記憶の関係,仮想記憶の有効性,仮想記憶方式の種類と特徴,動的アドレ ス変換の仕組みを理解する。また,ページング方式の代表的なページ置換えアルゴリズム について,ページ置換え手順を理解する。 用語例 ベースアドレス方式,セグメント方式,セグメントページング方式,単一仮想空 間 方 式 , 多 重 仮 想 空 間 方 式 , ス ラ ッ シ ン グ , DAT ( Dynamic Address Translator:動的アドレス変換),TLB(Translation Lookaside Buffer),ペー ジフォールト,ページイン,ページアウト,デマンドページング,ページリプレ ースメント,LRU,FIFO,ワーキングセット実記憶管理
実アドレス空間:主記憶装置(実記憶装置)のつくる記憶空間
単一連続割り当て方式:タスクが必要とする主記憶を上方、あるいは下方に固定して連続に割り当てる方式。シングルタスク用。
固定区画方式:主記憶をあらかじめいくつかの固定長の区画に分割し、並行実行するそれぞれのタスクに、そのタスクが必要とする大きさを持つ区画を割り当て、実行する方式。パーティション方式。
可変区画方式:タスクを実行する際、そのタスクの大きさにあわせて主記憶を可変長の区画に区切って割り当てる方式
ガーベジコレクション(メモリコンパクション)
不連続な未使用領域を一つの連続領域にまとめる操作
味噌用領域を割り当てるアルゴリズム
最初適合アルゴリズム(first-fit):必要量以上の大きさを持つ未使用領域のうちで最初に見つかったものに割り当て
裁量適合アルゴリズム(best-fit):必要以上の大きさを持つ未使用領域のうちで最小のものを割り当て
最悪適合アルゴリズム(worst-fit):必要量以上の大きさを持つ未使用領域のうちで最大のものを割り当て
オーバーレイ方式:主記憶より大きなプログラムを実行させる際、あらかじめプログラムを排他的に実行される複数個のセグメントに分割しておき、実行時に必要なセグメントを主記憶に読み込んで実行する方式
スワッピング(スワップイン・スワップアウト):主記憶を効率よく利用する方法。実効待ち状態のプログラムを実行状態のまま、スワップと呼ばれる補助記憶上の領域に退避(スワップアウト)し、ほかのプログラムを補助記憶から主記憶に読み込んで実行。中断されたプログラムの再開時には、退避した状態を読み込んで(スワップイン)実行を再開
仮想記憶方式
ディスク装置を利用することによって、主記憶の物理的な容量よりはるかに大きな仮想アドレス空間(論理アドレス空間)を想定し、プログラムの実行時には仮想アドレスを主記憶上の実アドレス(物理アドレス)に交換
動的アドレス変換機構(DAT:Dynamic Address Translator):仮想アドレスから実アドレスへのアドレス変換を行うハードウェア機構
ページング方式:仮想アドレス空間をページという固定長の区画に分割し、それに対応して主記憶も同じ大きさのページ枠に分割して、ページ単位でアドレス変換を行う。
セグメント方式:プログラムをセグメントという論理的な単位(大きさは可変)に分割し、セグメント単位でアドレス交換を行う。
セグメントページング方式:
ページング方式
ページング方式では、仮想アドレスと実アドレスの対応(マッピング)はページテーブルというアドレス対応表によって管理される。仮想アドレスは、ページ番号とページ内の相対アドレス(変位)から構成され、ページテーブルにはそのページが配置されている主記憶上のアドレスが記憶されている。
ページフォールトビットが設けられ、主記憶上に存在しないページには1,存在するページには0といったフラグが設定。
DATは各命令実行ごとにこのページテーブルにアクセスし、主記憶上に該当ページが存在するか否かを判断したり、仮想アドレスから実アドレスを算出する。
TLB(Translation Look-aside Buffer)アドレス変換バッファ、連想レジスタ。最近参照したページの変換履歴を記憶したもの。
プリページング:実行に際して必要になるページをあらかじめ予測し、主記憶上に読み込むページイン方式
ページフォールト割込み:必要となったページが主記憶上に存在しないときの割込み
デマンドページング:プログラム実行時、ページフォールト発生のたびにそのページを主記憶に読み込む方式。
ページ置換えアルゴリズム
LRU(Least Recently Used):最も長い間参照されていないページを置換え
LFU(Least Frequently Used):参照された頻度が最も少ないページ
FIFO(First In First Out):最も長く存在するページ
スラッシング:ページング処理が多発→システムのオーバーヘッドが増加→アプリケーションのCPU使用率が極端に減少
ワーキングセット:現在の時間tからT時間さかのぼってその間に参照されたページ