2-1ジョブ管理
12月20日、クリスマスケーキの予約の締め切り日です。閉店後の作業台で、ミナトは店のノートパソコンに三つの仕事をさせていました。通販サイトから予約を取り込むこと、ケーキの箱に貼るラベルを印刷すること、今月の売上を集計すること。最初の数分は順調でした。ところが途中から、マウスを動かしても画面がほとんど動かなくなり、本体の横にあるディスクのランプだけが点きっぱなしになります。店長は箱を組み立てる手を止めて言いました。「三つ同時にやらせたのが、まずかったのかな」。ミナトは相棒に打ち込みます。「CPUも主記憶も一つずつしかないのに、三つの仕事はどうやって同時に動いてるの。それに、なんで急に止まったみたいになったの」
相棒の返事は、三つの仕事の性質を分けるところから始まりました。予約の取り込みとラベルの印刷は、今夜のうちに終わっていないと明日の朝に困ります。一方で、売上の集計は、明日の朝までに結果が出ていれば十分です。誰かが画面の前で待っている必要もありません。
コンピュータにひとまとまりで頼む仕事の単位を、ジョブと呼びます。売上の集計なら、「1か月分の注文を読み込む」「商品ごとに合計する」「表にして保存する」という段階を順に踏んで一つのジョブになります。この一つ一つの段階をジョブステップといいます。ジョブの受け付けから実行、後始末までを管理するのが、OSのジョブ管理の役目です。
売上の集計のように、データを一定の期間や件数ぶん貯めておき、あとでまとめて一度に処理する方式をバッチ処理といいます。銀行の振込を夜間にまとめて処理したり、月末に給与を一括で計算したりするのが典型です。一件ごとにすぐ結果を返す処理（予約の受付など）と比べると、待たされる代わりに、コンピュータが空いている時間にまとめて効率よく片づけられます。
ここから基本情報！ジョブを動かすOSの機能
ジョブの実行順序を決め、一つ一つのジョブを起動し、終わったら後始末をするプログラムをジョブスケジューラー（ジョブスケジューラ）といいます。大型の汎用コンピュータのOSでは、その中身を、ジョブを読み込む機能、ジョブステップごとに資源を割り当てて起動する機能、終わったジョブの後始末をする機能、結果を書き出す機能に分けて説明することがあります。
そのジョブスケジューラの上に立ち、システム全体のジョブの流れを取りまとめるのがマスタスケジューラー（マスタスケジューラ）です。運用担当者（オペレータ）からの指示を受け付けたり、システムの状態を知らせたりして、その指示に沿ってジョブスケジューラを動かします。「全体を仕切る係」と「個々のジョブを回す係」の上下関係で押さえておくと、取り違えません。
パソコンやサーバのUNIX系のOSでは、ジョブをもっと身近な形で扱えます。シェルでコマンドの末尾に & を付けて実行すると、そのコマンドは端末の入出力を占有せずに裏で動き続け、利用者は同じ画面で次のコマンドを打てます。このように裏側で動かすジョブをバックグラウンドジョブといいます。売上の集計をバックグラウンドで動かしておけば、ミナトはその間に別の作業を進められます。
基本情報の範囲ここまで
集計を夜中のバッチ処理に回すだけで、締め切り日の夜に動く仕事は二つに減ります。ただ、相棒によれば、画面が止まった理由はそれだけでは説明しきれません。残る二つの仕事のうち、ラベルの印刷にも、パソコンを待たせる性質があるからです。
2-2入出力管理とスプーリング
ラベルは全部で240枚。店の古いプリンタは1枚に3秒ほどかかります。印刷のボタンを押してから、プリンタはカタカタと紙を送り続け、そのあいだミナトは予約の画面を開くのも待たされました。12分も印刷を見守るのは、さすがに長すぎます。
CPUは1秒に何億回も計算できますが、プリンタやディスクのような入出力装置は、それに比べてけた違いに遅い装置です。CPUが入出力のたびに装置の動きに付き合っていたら、ほとんどの時間を待つことに使ってしまいます。そこで、CPUの代わりに入出力装置とのデータの受け渡しを受け持つ専用の装置が考え出されました。これをチャネルといいます。
CPUは「このデータをこの装置へ送っておいて」とチャネルに頼むと、すぐ自分の計算に戻れます。転送が終わると、チャネルはCPUに割り込んで完了を知らせます。この知らせを入出力割込みといいます。CPUと入出力装置が別々に動けるので、遅い装置を待つ時間が、ほかの計算に使えるようになります。
ここから基本情報！印刷を待たない仕組み
それでも、プログラムが240枚ぶんのデータをプリンタの速さに合わせて1枚ずつ渡していたら、プログラム自身は印刷が終わるまで終われません。そこで、プリンタへ送るデータをいったん磁気ディスクなどの補助記憶装置に書き出しておき、プログラムはそこで仕事を終えたことにします。補助記憶に貯まったデータは、OSがプリンタの速さに合わせて少しずつ送り出します。この方式をスプーリング（スプーリング機能）といいます。
ラベルの印刷にスプーリングが働いていれば、ミナトのプログラムは数秒でデータを書き終え、240枚の印刷は裏で進みます。予約の画面も、すぐに開けるようになります。複数のプログラムが同時に印刷を頼んでも、補助記憶に順番に並べておけるので、ラベルと領収書が1枚ずつ混ざって出てくることもありません。
基本情報の範囲ここまで
チャネルのおかげで、CPUは印刷を待つ間も別の仕事ができるようになりました。では、空いたCPUは、その「別の仕事」をどうやって選んでいるのでしょうか。
2-3タスクと状態遷移
ミナトはタスクマネージャを開いてみました。並んでいる名前は、予約の取り込み、ラベルの印刷、ブラウザ、それに見覚えのない何十もの項目。ブラウザは一つのはずなのに、同じ名前がいくつも並んでいます。「これ全部、いま動いてるの？」
OSから見ると、ディスクに置かれたプログラムは、ただのファイルです。それを主記憶に読み込んで実行を始めると、CPUの時間や主記憶の領域を割り当てる相手になります。この、OSが資源を割り当てる単位として見た実行中のプログラムをプロセスといいます。OSによってはタスクとも呼び、試験でもほぼ同じ意味で使われます。タスクマネージャの一覧は、いまOSが面倒を見ているプロセスの名簿です。
名簿のプロセスが、全部同時にCPUで計算しているわけではありません。CPUが一つなら、ある瞬間に計算できるのは一つだけです。残りは順番を待っているか、入出力の終わりを待っているかのどちらかです。
ここから基本情報！プロセスの三つの状態
ブラウザの名前がいくつも並んでいたのは、タブごとに別のプロセスを立てるブラウザがあるからです。一方で、一つのプロセスの中で、画面の描画と通信を並行して進めたい場面もあります。そのために、一つのプロセスの中に複数作れる、より軽い実行の単位がスレッドです。同じプロセスのスレッドどうしは主記憶の領域を共有するので、プロセスを新しく作るより手間が少なく、切り替えも速く済みます。
プロセスは、生成されてから消滅するまで、三つの状態を行き来します。CPUさえ空けばすぐ動ける、順番待ちの状態を実行可能状態といいます。CPUを割り当てられて実際に計算している状態が実行状態です。そして、入出力の完了などの出来事を待っていて、CPUが空いても先へ進めない状態を待ち状態といいます。
実行可能状態のプロセスの中から一つを選び、CPUを割り当てて実行状態に移す操作をディスパッチといい、それを受け持つOSの部分をディスパッチャといいます。ディスパッチャはCPUの席への案内係です。どの順で案内するかの方針は、次の節のスケジューリングで決まります。
状態の移り方は、決まった四本の矢印だけです。
| 移り方 | きっかけ | こむぎ堂の例 |
|---|---|---|
| 実行可能 → 実行 | ディスパッチされた | 予約の取り込みにCPUの番が回ってきた |
| 実行 → 待ち | 入出力を頼んだ | ラベル印刷がデータをディスクへ書き出し始めた |
| 待ち → 実行可能 | 入出力が終わった（入出力割込み） | 書き出しが終わり、次の行の準備に戻れる |
| 実行 → 実行可能 | 持ち時間が切れた、またはもっと急ぐプロセスに譲った | 集計に番を譲って列の後ろに並び直した |
基本情報の範囲ここまで
名簿にあるプロセスの大半は、ほとんどの時間、何かを待っています。だからこそ、一つのCPUを順番に回すだけで、たくさんのプログラムが同時に動いているように見えるのです。
2-4マルチプログラミングとスケジューリング
集計を夜に回すことにしたものの、ミナトは一度だけ、昼間に売上の集計を動かしてみました。すると、レジ横で予約の画面を開いた店長が「いらっしゃいませ」と言ってから予約の一覧が出るまで、10秒もかかります。お客さんの前で待たされる仕事と、誰も待っていない仕事が、同じ順番待ちの列に並んでいるからでした。
一つのCPUを短い時間で次々に切り替え、複数のプログラムを並行して進めることをマルチタスクといいます。パソコンでブラウザと表計算と音楽を同時に使えるのは、OSがこの切り替えを人の目に見えない速さで続けているからです。
このとき、どのプログラムを先に動かすかの目安になるのが優先順位（優先度）です。お客さんの前で使う予約の画面は高く、誰も待っていない集計は低く決めておけば、OSは高い方から先にCPUを回します。何を高い値とするか（数が小さいほど高いのか、大きいほど高いのか）はOSによって違います。
ここから基本情報！CPUの順番の決め方
マルチタスクのもとになる考え方が多重プログラミング（マルチプログラミング）です。複数のプログラムを同時に主記憶に置いておき、一つが入出力を待っている間に、CPUを別のプログラムに使わせます。CPUの空き時間を埋めることで、全体として多くの仕事を片づけられます。
そのうえで、OSが複数のタスクのうちどれにCPUを割り当てるか、どれだけの時間使わせるかを決める処理をタスクスケジューリングといいます。決め方にはいくつかの方式があり、まず、実行中のタスクからCPUを取り上げてよいかどうかで二つに分かれます。
OSが必要と判断すれば、実行中のタスクからでもCPUを取り上げ、別のタスクに切り替えられる方式がプリエンプティブ方式です。優先順位の高い予約の画面が動き出したら、集計を途中で止めてでも予約に席を譲らせる、という動きができます。反対に、実行中のタスクが自分で終わるか待ち状態に入るまで、CPUを取り上げない方式がノンプリエンプティブ方式です。仕組みは単純ですが、一つのタスクが長く居座ると、ほかはすべて待たされます。昼間の集計で店長が10秒待たされたのは、この居座りと同じ形です。
CPUの時間を細かく区切って順に配る方式もあります。CPUの時間を一定の長さに区切り、その区切りごとにタスクを切り替えて実行する方式をタイムスライス方式といい、一つのタスクに一度に与える一定の時間をタイムクウォンタム（タイムスライス）といいます。到着順に並べたタスクに同じタイムクウォンタムを順に与え、使い切ったタスクは列の最後に並び直す、という巡回のやり方をラウンドロビン（ラウンドロビン方式）と呼びます。持ち時間で区切ること自体がCPUを取り上げることなので、ラウンドロビンはプリエンプティブ方式の一つです。
こむぎ堂の三つの仕事で試してみます。予約の取り込み（A）がCPUを4単位時間、ラベルの書き出し（B）が2単位時間、集計（C）が3単位時間必要で、三つとも時刻0にA、B、Cの順で並んだとします。入出力の待ちは考えません。
| 時刻 | CPUを使う仕事 | その後の残り時間 |
|---|---|---|
| 0〜2 | A | A 2、B 2、C 3 |
| 2〜4 | B | B 0（時刻4で終了） |
| 4〜6 | C | A 2、C 1 |
| 6〜8 | A | A 0（時刻8で終了） |
| 8〜9 | C | C 0（時刻9で終了） |
到着順に一つずつ最後まで動かすと、Aが時刻4、Bが6、Cが9に終わります。ラウンドロビンでは、短い仕事のBが時刻4に終わり、2単位時間早まりました。その代わり、長いAの終わりは8まで延びています。全部が終わる時刻は、どちらも9で変わりません。切り替えが速くなるのではなく、短い仕事が長い仕事の後ろで待たされにくくなる、というのがこの方式の利点です。
優先順位だけで順番を決める方式には弱点があります。高い優先順位のタスクが次々に来ると、低いタスクにはいつまでも番が回ってきません。そこで、待たされている時間が長くなるほど、そのタスクの優先順位を少しずつ上げていく仕組みを足します。これをエージングといい、低いタスクが無期限に先延ばしされるのを防ぎます。夜まで後回しにされた集計も、いつかは必ずCPUにたどり着くわけです。
基本情報の範囲ここまで
予約の画面の優先順位を上げてからは、昼間に集計が動いていても、店長が待たされることはなくなりました。CPUの順番の問題は、これで片づきます。それでも締め切りの夜のディスクのランプは、まだ説明がついていません。CPUではなく、主記憶の側に原因があったからです。
2-5実記憶管理
店のパソコンの主記憶は8Gバイトです。タスクマネージャでメモリの欄を見ると、予約の取り込み、ラベル印刷、ブラウザのタブが少しずつ場所を取り、空きはほとんど残っていません。しかも、朝からつけっぱなしの予約の取り込みは、午後になると朝の倍近い場所を使っていました。
実際に計算に使われる主記憶は、いくつものプログラムで分け合う共有の棚です。限られた棚を誰にどれだけ貸すかを決めるのが、OSの記憶管理です。棚を区切る方法には、あらかじめ決まった大きさの区画に分けておく固定区画方式と、プログラムが来るたびに必要な大きさだけ切り出す可変区画方式があります。
ここから基本情報！空き領域の細切れと後片づけ
可変区画方式で貸し出しと返却を繰り返すと、空きが小さな切れ端になって、あちこちに散らばります。空きの合計は足りているのに、どの切れ端も小さすぎて、大きなプログラムを置けない状態です。これを断片化（フラグメンテーション）といいます。散らばった使用中の領域を詰め直し、空きを一つの連続した領域にまとめる操作がコンパクションです。
決まった大きさの小さな領域を、何度も素早く確保しては返すような使い方には、別の工夫があります。あらかじめ一定の領域をまとめて確保し、ブロックに分けて貸し借りするメモリプール管理です。確保と解放のたびにOSが空きを探さずに済むので、処理時間の読みやすさが求められるリアルタイムシステムの組込み機器などで使われます。
メモリプールの分け方には二つあります。すべてのブロックを同じ大きさにそろえる固定長方式は、管理が単純で速い反面、小さな要求にも一つ分のブロックを貸すので、ブロックの中に使わない部分が残ります。要求に合わせて大きさの違うブロックを切り出す可変長方式は、ブロックの中の無駄は出にくい一方、管理が複雑になり、可変区画方式と同じく空きが細切れになりやすくなります。
ディスクとの読み書きを速くするために主記憶に用意する一時置き場がバッファで、それを多数まとめて管理する領域をバッファプールといいます。データベース管理システムは、よく読まれるデータをバッファプールに置いておき、同じデータが再び求められたらディスクを読まずに返します。
午後になると予約の取り込みが朝の倍近い場所を使っていたのは、使い終わった領域を返さずに持ち続けていたからかもしれません。プログラムが確保した主記憶を解放し忘れ、使える領域が少しずつ減っていく不具合をメモリリークといいます。長時間動かし続けるプログラムほど影響が大きく、最後には主記憶が足りなくなります。
解放し忘れを防ぐ仕組みを、言語の側が持っていることもあります。どこからも参照されなくなった領域を、実行中に自動で見つけて解放する仕組みをガベージコレクション（GC）といい、JavaやPythonなどの処理系が備えています。ただし、不要になったデータへの参照を残したままにしておくと、ガベージコレクションはそれを使用中と見なすので、リークは起こりえます。
基本情報の範囲ここまで
貸し方をどれだけ工夫しても、棚の大きさは8Gバイトから増えません。足りないときは、棚の中身を一時的にどこかへ移すしかありません。
ここから基本情報！主記憶とディスクの入れ替え
主記憶がまだ小さかったころに使われたのがオーバーレイ方式です。主記憶に収まらない大きなプログラムを、同時には使わない部分（セグメント）に分けておき、必要になった部分だけを同じ領域に順に読み込んで上書きしながら実行します。どこで分けるかは、プログラムを作る人があらかじめ決めておきます。シラバスでは、この方式に「（セグメント方式）」と添えてあります。
プログラムを分けずに、プロセス全体を主記憶と補助記憶の間で入れ替える方式がスワッピングです。しばらく動かないプロセスを、主記憶から補助記憶へ追い出す操作をスワップアウト、追い出しておいたプロセスを主記憶に読み戻す操作をスワップインといいます。
同じ入れ替えを、優先順位の視点で呼ぶ名前もあります。優先順位の高いジョブに主記憶を空けるため、実行中の低いジョブを丸ごと補助記憶へ退避させる操作がロールアウト、高いジョブが終わってから退避していたジョブを読み戻し、続きから実行を再開させる操作がロールインです。昼間に予約の画面が動き出したら集計を追い出し、予約が片づいたら戻す、という動きになります。
基本情報の範囲ここまで
2-6仮想記憶管理
主記憶の空きがほとんど無いのに、ミナトがもう一つタブを開いても、パソコンは「主記憶が足りません」とは言いませんでした。その代わり、ディスクのランプがまた点き始めます。相棒は言いました。「棚が足りないとき、このパソコンは倉庫を棚の続きとして使っているんだよ」
今のOSは、主記憶だけでなく補助記憶の一部も主記憶の続きのように扱い、実際の主記憶より大きな記憶領域をプログラムに見せています。これを仮想記憶といいます。プログラムは、自分が使っている場所が主記憶なのかディスクなのかを気にせず動けます。OSは、いま使われている部分だけを主記憶に置き、しばらく使われていない部分をディスクへ移しておきます。
ただし、ディスクは主記憶に比べてずっと遅い装置です。主記憶が足りないほど、ディスクとの出し入れが増え、パソコン全体が遅くなります。締め切りの夜に起きていたのは、まさにこれでした。三つの仕事とブラウザのタブが主記憶の取り合いになり、ディスクとの出し入れが休みなく続いて、計算そのものがほとんど進まなくなっていたのです。
ここから基本情報！アドレスの変換と仮想記憶の方式
仮想記憶を実現するには、プログラムの中で使っている番地（論理アドレス）を、主記憶上の本当の番地（実アドレス）に置き換える必要があります。その基本の形がベースアドレス方式です。プログラムを主記憶に置いた先頭の番地（ベースアドレス）を覚えておき、プログラムの中の番地はすべて先頭からの距離（相対アドレス）で書いておきます。ベースアドレスが5000で、プログラムが相対アドレス300のデータを読むなら、実アドレスは5000＋300＝5300です。プログラムを別の場所に置き直しても、ベースアドレスを書き換えるだけで済みます。
仮想記憶では、この変換をプログラムの実行中に、主記憶を参照するたびにハードウェアが行います。これを動的アドレス変換（DAT）といいます。プログラムの一部がディスクから主記憶の別の場所に読み戻されても、変換の表を書き換えれば、プログラムはそのまま正しい番地を読めます。
主記憶とディスクの間で出し入れする単位の決め方で、仮想記憶の方式が分かれます。プログラムを固定長の小さな単位（ページ）に機械的に区切って管理するのがページング方式です。これに対し、プログラムを「命令の部分」「データの部分」のように意味のまとまり（セグメント）で、長さをそろえずに区切って管理するのがセグメント方式です。両方を組み合わせ、まずセグメントに分け、各セグメントをさらにページに区切って管理するのがセグメントページング方式です。意味のまとまりで保護や共有をしやすいセグメントの長所と、大きさがそろって主記憶に置きやすいページの長所を合わせています。
ページング方式でプログラムが読もうとしたページが主記憶に無いと、その場で処理を中断し、ディスクから読み込む必要が生じます。これをページフォールトといいます。読み込むとき主記憶に空きが無ければ、すでにあるページを一つ選んでディスクへ追い出し、新しいページと入れ替えます。この入れ替えをページリプレースメント（ページ置換え）といいます。
どのページを追い出すかで、ページフォールトの回数が変わります。代表的な決め方は二つです。主記憶に最も早く読み込まれたページを追い出すのがFIFO（First In First Out）、最も長い間参照されていないページを追い出すのがLRU（Least Recently Used）です。主記憶にページを3枚置けるとき、ページを1、2、3、1、4、1、2の順に参照すると、次のようになります。
| 参照 | LRUの主記憶 | LRUの結果 | FIFOの主記憶 | FIFOの結果 |
|---|---|---|---|---|
| 1 | 1 | フォールト | 1 | フォールト |
| 2 | 1・2 | フォールト | 1・2 | フォールト |
| 3 | 1・2・3 | フォールト | 1・2・3 | フォールト |
| 1 | 1・2・3 | ある | 1・2・3 | ある |
| 4 | 1・3・4 | フォールト（最も長く使っていない2を追い出す） | 2・3・4 | フォールト（最も早く来た1を追い出す） |
| 1 | 1・3・4 | ある | 3・4・1 | フォールト（2を追い出す） |
| 2 | 1・4・2 | フォールト（3を追い出す） | 4・1・2 | フォールト（3を追い出す） |
ページフォールトは、LRUで5回、FIFOで6回です。分かれ目は5番目の参照（ページ4）でした。ここでFIFOは、ついさっき使ったばかりのページ1を「最初に来たから」という理由で追い出し、すぐ次の参照でまた読み直しています。LRUは参照の新しさを見るので、よく使われているページを手元に残せます。
締め切りの夜の症状にも、これで名前が付きます。主記憶が足りずにページフォールトが多発し、ページの出し入ればかりに時間を取られて、システムの処理効率が極端に落ちる現象をスラッシングといいます。追い出す相手の選び方を工夫しても、同時に動かすプログラムが使うページの合計が主記憶に収まらなければ防げません。同時に動かす仕事を減らすか、主記憶を増やすのが対策です。
基本情報の範囲ここまで
仮想記憶があるおかげで、主記憶が足りなくてもプログラムは止まらずに動きます。ただ、それは遅いディスクに肩代わりさせているだけで、主記憶が増えたわけではありません。同時に動かす仕事を減らせば、ディスクのランプは落ち着きます。
2-7プログラムの性質
翌年に向けて、ミナトはラベルを作る小さなプログラムを自分で書いてみることにしました。相棒に見せると、こう返ってきます。「店のパソコンで予約の画面と通販の画面の両方から、同時にこのラベル作りを呼んだらどうなると思う？」。ミナトは答えに詰まりました。
プログラムが主記憶に置かれて動く以上、どこに置かれても動けるか、何度でも、何人からでも呼べるかといった性質が問題になります。記憶管理と組み合わせて使うときに、OSが前提にする性質です。
ここから基本情報！再配置・再使用・再入・再帰
主記憶のどの場所に読み込まれても正しく動く性質をリロケータブル（再配置可能）といいます。プログラムの中の番地を、ベースアドレスからの相対アドレスで書いておけば、スワップインのたびに置き場所が変わっても動けます。
一度主記憶に読み込んだプログラムを、読み込み直さずに繰り返し実行できる性質をリユーザブル（再使用可能）といいます。1回目の実行で書き換えた変数などを、次の実行の前に初期状態へ戻せるように作ってあるプログラムです。ただし、同時に使えるのは一つのタスクだけで、前の実行が終わるまで次は待たされます。
複数のタスクから同時に呼び出されても、互いに邪魔をせずに正しく動く性質がリエントラント（再入可能）です。命令の部分は共有したまま、書き換えるデータの部分をタスクごとに別の領域に持たせて作ります。ミナトのラベル作りが、作りかけのラベルの内容を一か所の変数に入れていたら、予約の画面と通販の画面から同時に呼ばれたときに、二つのラベルの中身が混ざってしまいます。呼び出しごとに作業用の領域を分ければ、混ざりません。
手続きの中から自分自身を呼び出せる性質をリカーシブ（再帰的）といいます。自分自身を呼ぶときには、まだ終わっていない1回目の呼び出しの途中のデータを残したまま、2回目が動き出します。そのため、リカーシブなプログラムも、呼び出しごとにデータの領域を分けるリエントラントと同じ作り方が必要です。
基本情報の範囲ここまで
翌年の12月20日、こむぎ堂の締め切りの夜は静かでした。売上の集計は、閉店後に自動で始まる夜中のバッチ処理に回してあります。240枚のラベルは、スプーリングで印刷の順番待ちに預けたので、ミナトのプログラムはすぐに手を離れ、予約の取り込みの画面も止まりません。同時に動く仕事が減ったので、主記憶の取り合いも起きず、ディスクのランプは時々またたくだけでした。箱を組み立て終えた店長が画面をのぞいて言います。「去年は三つ全部を一度にやらせたのが、まずかったんだね」。CPUも主記憶も一つずつのままです。変わったのは、仕事の渡し方のほうでした。