{吉沢4.3.2-7節,前川2.4–5節,岩波情報科学辞典} non-preemptive vs. preemptive:
ノンプリエンプティブ・スケジューリング · · · プロセスにCPUを割り付けた後そのプロ セスが完了するか自らCPUを放棄するまでCPUを使用させる方法。
プリエンプティブ・スケジューリング · · · 現在実行しているプロセスの処理を中断し別 のプロセスの処理を開始することがある方法。
8.8. プロセススケジューリングの方法 89
スケジューリングのためのデータ構造： CPUを使用するためのプロセスの待ち行列 が出来ていると考えて良い。これがスケジューリングの基本。
スケジューリングの方式： 基本的な方式としては次の7つがある。一般には、これらの 基本方式を組み合わせた複合方式が採用されることが多い。
(1) 到着順(FIFO,first-in-first-out, FCFS,first-come-first-served) ：
· · · プロセスをその到着の順序に従って処理する。
=⇒ 典型的なノンプリエンプティブ方式。
特定のプロセスによるCPU独占の可能性。
(2) 処理時間順(SPT,shortest-processing-time first)：
· · ·処理時間の短いプロセスから処理する。
=⇒ 処理時間を予め知る方法は一般に存在しないので、
実現が難しい。(プリエンプティブ方式と組み合わせて実現する?) (3) 優先度順スケジューリング(priority scheduling)：
· · · 各プロセスに割り当てられた優先度の高い順に処理する。実行中のものより優
先度の高いプロセスが到着すると、即座にこれがディスパッチされる。
=⇒ 典型的なプリエンプティブ方式。'
&
$
% 補足：一旦指定された優先度が変化しない静的優先度方式と、実行中に優
先度を変える動的優先度方式の2種類がある。
動的優先度方式の例：
優先度の低いプロセスになかなかサービスの順番が回って来ない問 題を解決するために、待ち時間に比例して優先度を上げる、エージ
ング(aging)と呼ばれる方法が取られることがある。
(4) ラウンドロビン(RR,round robin)：
· · · 実時間を短いタイムスライスに区切り、走行プロセスが与えられたタイムスラ
イスを使い切る度に最も長時間待っているプロセスに切り替える。これによっ て、多数のプロセスを切り替えながら並行に少しずつ実行する。
=⇒ 典型的なプリエンプティブ方式。タイムスライス値をどう決めるか？
(5) 動的ディスパッチング(dynamic dispatching, heuristic dispatching)：
· · · I/Oバウンドな(i.e.入出力を多用する)プロセスをCPUバウンドな(i.e.入出 力をあまり使わない)プロセスより優先して処理する。
'
&
$
% 補足：この方式を用いると多重プログラミング方式の計算機システムの処
理能力(スループット)が最も高くなることが、実験・経験的にも理
論的にも示されている。この方式を採用する場合は、どのプロセス がI/OバウンドでどれがCPUバウンドなのかを判断するために、
最近のある一定期間の入出力の頻度を測定するのが一般的である。
(6) フィードバック待ち行列方式(FB,feedback queue)：
· · ·プロセスを多段のラウンドロビン方式で処理する。
'
&
$
% 補足：
優先度の低いプロセスになかなかサービスの順番が回って来ない問 題を解決するために、待ち時間に比例して優先度を上げる、エージ
ング(aging)と呼ばれる方法が取られることがある。
(7) デッドラインスケジューリング(deadline scheduling)：
· · ·処理完了の目標時間が迫っている順に処理する。
到着順方式の実装：
・・・
プロセス管理表 プロセス
管理表 プロセス
管理表 tail top
CPU プロセス管理表
新しいジョブ の到着
実行中の(i.e.CPUのサービスを受けている) プロセス
処理終了
処理時間順方式の実装：
自分で考えてみて下さい。
優先度順スケジューリング方式の実装：
・・・
プロセス管理表 プロセス
管理表 プロセス
管理表 tail top
CPU プロセス管理表
新しいジョブ 実行中のプロセス の到着
処理終了
実行中のものより優先度の高いプロセスが現れると、
実行中のものは実行可能状態になり、
優先度のより高いものがディスパッチされる。
または
8.8. プロセススケジューリングの方法 91
・・・
プロセス管理表 プロセス
管理表 プロセス
管理表
tail
top CPU
プロセス管理表
新しいジョブ の到着
実行中のプロセス
処理終了
・・・
プロセス管理表
プロセス管理表 プロセス 管理表
・・・
プロセス管理表 プロセス
管理表 プロセス
管理表
・ ・
・
tail tail
top top
低 高
実行中のものより優先度の高いプロセスが現れると、
実行中のものは実行可能状態になり
優先度のより高いものがディスパッチされる。
優先 度
ラウンドロビン方式の実装：
・・・
プロセス管理表 プロセス
管理表 プロセス
管理表 tail top
CPU プロセス管理表
新しいジョブ の到着
実行中のプロセス 処理終了
タイムスライスを使い果たしたら待ち行列の最後尾に移る
動的ディスパッチング方式の実装：
自分で考えてみて下さい。
フィードバック待ち行列方式の実装：
・・・
プロセス管理表 プロセス
管理表 プロセス
管理表 tail(1) top(1)
CPU プロセス管理表
新しいジョブ の到着
実行中のプロセス 処理終了
タイムスライスを使い果たしたら優先度の１段低い待ち行列の最後尾に移る
・・・
プロセス管理表 プロセス
管理表 プロセス
管理表 tail(2) top(2)
・・・
プロセス管理表 プロセス
管理表 プロセス
管理表 tail(3) top(3)
・・・
プロセス管理表 プロセス
管理表 プロセス
管理表 tail(n) top(n)
プロセス管理表
プロセス管理表
プロセス管理表
タイムスライスを使い果たしたら優先度の１段低い待ち行列の最後尾に移る
タイムスライスを使い果たしたら優先度の１段低い待ち行列の最後尾に移る
タイムスライスを使い果たしたら待ち行列の最後尾に移る
・・・・・・・・・
処理終了
処理終了
処理終了
デッドラインスケジューリング方式の実装：
自分で考えてみて下さい。
演習問題
□演習 8.8 プロセスとスレッドの違いを説明せよ。
□演習 8.9 プロセスの状態としてどんなものがあるか？ それらの状態遷移の様子を図 示して説明せよ。
□演習 8.10 複数のプロセスで処理を実行する利点、欠点を挙げよ。
□演習 8.11 多重プログラミング、多重タスキング、多重プロセシングの違いを説明 せよ。
□演習 8.12 プロセススケジューリングの方法として、到着順、優先度順、ラウンドロ ビンについて簡単に説明せよ。
93
9 メモリ管理 — 仮想記憶の実現 —
• 主記憶を管理する上での、課題の変化(吉沢2.2.1 節),
• 大容量記憶への願望 (オーバレイ;6.4節,吉沢 5.2.3節),
• メモリ管理の初期の課題(吉沢5.1節),
• 主記憶の中にジョブを詰めこむ際にどういう問 題が発生するか(吉沢5.1節),
• 主記憶を分割して多重プログラミングを実現す る方法(吉沢5.2.1-2節,谷口3.2節),
• 仮想記憶の考え(吉沢2.2.2節,谷口2.4.2節),
• ページングによる仮想記憶(吉沢5.3–4節),
• デマンドページング(吉沢5.4.4–5節),
• 仮想記憶を支えるハードウェア(吉沢8.2.2節),
• ページ表が大きくなり過ぎることをどう克服す るか,
• ページングvs.セグメンテーション(谷口2.4.4 節),
• 単一仮想記憶vs.多重仮想記憶(吉沢8.3節),
• 記憶保護の機構(吉沢5.1.4節)
9.1 主記憶を管理する上での、課題の変化
{吉沢2.2.1節} 主記憶の容量によって、管理の目標が少し変わってくる。
• 初期のコンピュータ：
主記憶の容量が小さい。
=⇒ OSの課題：
3 大きなプログラムを実行できる様にする。
3 限られたメモリ領域を有効に活用した上で、
多重プログラミングの多重度を向上する。
=⇒ 仮想記憶
• 現在：
半導体の集積化技術の急激な進歩によって、メモリが大容量化した。'
&
$
% 例えば、
HITAC 8350: 200KB −→ 普通のPC: 4GB,
(1975頃教育用電算機) 情報工学科実習室のWS: 64GB
=⇒ 大容量メモリを用いた性能向上技術が開発された。例えば、
キャッシング(cashing) · · · 主記憶に使用しているRAMの一部を磁気ディスク (RAMディスクという)と見なして、頻繁にアクセスされる情報をRAM 内に格納しておく。