確認問題

以下にスラスラ答えられる人は読まなくても大丈夫。
・ジョブとは人間から見たひとまとまりの仕事を指す。ジョブを分割したもの、それをさらに分割したものをそれぞれ何と呼ぶか。
・プロセス(タスク)の状態を三つ答えよ。また、それぞれがどのように遷移するのかを答えよ（ある状態からある状態へ直接遷移しないことが理解できているか）。
・タスクスケジューリング方式には、「到着度順」「優先度順」「動的優先度順」「ラウンドロビン方式」「多重待ち行列方式」「処理時間順方式」「イベントドリブン方式」などある。全て説明せよ。
・タスクスケジューリング方式に関する用語である「ノンプリエイティブ方式」について説明せよ。
・排他制御の「セマフォ」について説明せよ。そのとき「P操作」「V操作」の用語を用いること。
・デッドロックを起こす方法、回避する方法を簡潔に説明せよ。
・メモリ上にプログラムをロードする際に空き容量不足の場合、とりうる対処法を２つ（〜方式と〜方式）説明せよ。
・メモリ上にプログラムをロードする際、仮想記憶方式でアドレス空間を管理する場合、ページング方式と呼ぶ。ページング方式について説明せよ。ただし、「MMU」「ページフォールト」「ページイン」「ページアウト」の用語を用いること（※デマンドページング方式が採用されているものとする）。
・ページング方式とスワッピング方式の違いを説明せよ。
・ページアウトとページインを繰り返すことで処理効率が下がる現象を何と呼ぶか答えよ。
・一部のプログラムが持つ特徴４つ「再配置可能(リロケータブル)」「再使用可能(リユーザブル)」「再入可能(リエントラント)」「再帰的(リカーシブ)」を全て説明せよ。特に再使用可能と再入可能の違いについて。
・

OSの機能

OSの機能には広義のものと狭義のものがある。
＞広義：基本ソフトウェア＝OSと見做す
＞狭義：基本ソフトウェアの一部である「制御プログラム」をOSと見做す

基本ソフトウェアの主な機能３つ

１、制御プログラム（Kernel）
２、言語プロセッサ：プログラム言語の解読を行う
３、サービス、ユーティリティ
メモリやファイルの管理、セキュリティに関する管理などもOSの仕事であるが、本稿では省略する。メモリの話は一部する。

カーネルの機能

主に以下の機能がある。各項目の詳細は長くなるので後述する。
　１、ジョブ管理
　２、プロセス（タスク）管理
　３、メモリ管理
　４、ファイル管理
　５、デバイス管理
　６、セキュリティ管理

補足：バッチ処理、オンライン処理とは？

バッチ処理とは定期的に実行される処理、オンライン処理とは指示があった即座に実行される処理。

OSの機能１：ジョブ管理

ユーザがコンピュータに実行させるタスクを、コンピュータの世界では「ジョブ」と呼ぶ。batファイルを実行するように、一連の作業をひとまとめにしたイメージ。
＜補足＞ジョブの構成
１つのジョブは、いくつかのジョブステップで構成される。ジョブステップとは、いちプログラムが担当する範囲の処理を指す。かつ、ジョブステップはいくつかのプロセス(タスク)で構成される。プロセスとはコンピュータから見た単体の処理のこと。

ただジョブを実行するといっても、ジョブをジョブステップに分解したり、優先度の高低を判断したり、仕事が終わったハードウェアリソースを解放したり、ジョブの実行結果を出力したり、など様々な処理が絡んでくる。これを実行してくれるのがカーネル。

マスタスケジューラとジョブスケジューラ

ユーザが指示する作業内容を制御するのがマスタスケジューラ。ジョブの実行状態を監視し、ジョブの終了や異常の検知などを行う。
マスタスケジューラが作業を依頼する先がジョブスケジューラと呼ばれる。マスタスケジューラは、ジョブの終了の検知や制御といった役割なので、マスタスケジューラが上司、ジョブスケジューラが部下の作業者、というイメージが近いか。
ただジョブスケジューラは、名前の通り「スケジューラ」なので、どちらかというと中間管理職のイメージかも。実際のジョブステップの実行は、「カーネルの機能２：タスク管理」にて扱う。

ジョブスケジューラを構成する４つのプログラム

ジョブを処理する順番に、４つのプログラムを紹介する。
１、リーダ　→　ジョブを読み、ジョブ待ち行列に登録
２、イニシエータ　→　優先度の高いジョブを選択してジョブステップに分解（ジョブステップを実行させる）
３、ターミネータ　→　ジョブステップに使用したハードウェアのリソースを解放し、出力待ち行列に登録（※１）
４、ライタ　→　ジョブの結果を出力
（※１）出力待ち行列を使用しない場合、実行結果の出力（印刷など）が終わるまでCPUが占有されて他の処理が進まないので、速度差を吸収するために出力待ち行列が存在する。実行結果を一時的に蓄えておくことをスプーリングと呼ぶ。

OSの機能２：タスク管理

プロセス（タスク）の定義のおさらい。人間から見た処理のひとまとまりである「ジョブ」を、さらに各プログラムの担当範囲に分割した「ジョブステップ」、それをコンピュータ目線の一塊の処理に分割したもの、それがタスクである。

タスクの状態３種

タスクはただ実行されるものではなく、複数あるタスクの中での優先順位が決められ、「実行可能状態(READY)」「実行中(RUN)」「待機状態(WAIT)」の３つの状態を行き来する性質を持つ。
・実行可能状態(READY)：実行の準備ができている状態。CPUの使用権をもらったら「実行中」に遷移する。タスク生成直後はこの状態になる。
・実行中(RUN)：実行中の状態。実行中の状態のタスクであっても、実行に時間がかかりすぎている場合は強制終了させられたりする。
・待機状態(WAIT)：主に入出力処理の結果を待っている状態。待機状態からいきなり実行中の状態には遷移できない。待機状態→実行可能状態→実行中、と遷移する必要がある。
待機状態からすぐ実行中に遷移できないことをイメージで覚えるには、CPUと他機器には結構な速度差があることを思い出すとよい。人間からすれば入出力の結果を待つ短時間の間にも、CPUは優秀なので沢山の処理をこなすことができる。待機状態のタスクができたら、それをタスク管理者（CPUの使用権を割り当てる者＝ディスパッチャ）が検知し、すぐさま他のタスクを処理させる・・・というイメージ。

ディスパッチャとタスクスケジューリング

Dicpatch（割り当てる）から、CPUの使用権を割り当てる者＝タスクの管理者、それがディスパッチャである。
ディスパッチャがタスクにCPUの使用権を割り当てる方式をタスクスケジューリングと呼ぶ。具体的にどのようなタスクスケジューリング方式があるのかを紹介する。
・到着順方式：タスクが生成された順番に処理するだけ。また、この方式のみ「タスクを実行中に割り込み、強制終了させない」というノンプリエンティブ(non-preemptive)方式となっている。preemptiveは先制、先取の意だが、「差押」「占有」という方が今回のイメージには近い。
・優先度順方式：タスクに優先度を割り振り、高いものから順番に処理する。ただし優先度が低く設定されたタスクがず〜っと放置されることが有り得るという欠点を持つ。
・動的優先順位方式：タスクに優先度を割り振り、高いものから順番に処理する。ただし優先度が低いタスクでも、処理されずに放置されていると優先度を高く再設定してもらえる仕組み。
・ラウンドロビン方式：CPUの使用権を一定時間割り当て、一定時間を超過したタスクを容赦なく強制終了させて次のタスクに割り振る方式。
・多重待ち行列方式：ラウンドロビン方式と動的優先順位方式を合体させた方式。基本的には動的優先順位方式スタイルだが、一定期間を過ぎた場合、強制終了させられる上に優先度を下げられる。なお、割り当てられるCPU使用時間の長さは、優先度が高いものは短く、優先度が低いものは長く設定されている。もし優先度が低いものに割り当てられる使用時間が短くなってしまうと、優先度が低いタスクが処理できないまま無限ループしてしまうので、このような仕様になっている（と思われる）。
・処理時間順方式：処理時間が短いものから優先して処理する方式。ただ処理する間に実行時間を測るのは難しいので、なかなか実装されないようだ。
・イベントドリブン方式：イベントをきっかけにタスクの切り替えを行う形式。例えばWindowsなどGUIの操作において、背面のプログラムをクリックして前面表示にすることで、クリックした方のプログラムを実行させるなど。

プログラムの処理イメージ

複数のプログラムを動かしているとき、タスクAを実行して入出力処理の待機状態にはいったら、その間にタスクBを実行させてCPUがヒマな時間を減らす仕組みとなっている。これをマルチプログラミングと呼ぶらしいが、CPUにヒマを与えないような仕組みがあるんだなと理解しておけば問題ないだろう。
ちなみにマルチプログラミングと呼ばれるのは、一見同時に複数のタスクを実行しているように見えるから。

排他制御、同時制御

排他制御が必要な理由については割愛する。

排他制御のメカニズム：セマフォ

セマフォ変数に「その資源を同時に使用してよいタスクの数」を格納しておき、タスクがセマフォ変数を参照して１以上であったら、対象の資源を使用できるという仕組み。対象の資源を利用している間、セマフォ変数が１減算される。
例えばセマフォ変数の初期値が２だとする。タスクAが資源を使用するのでセマフォ変数が１になる。タスクBが資源を使用するのでセマフォ変数が０になる。タスクCが資源を使おうとしてもセマフォ変数が０なので使用権がないことになる。
ただセマフォ変数が２以上のケースは正直よくわからんので、基本的に初期値は１だと思って良い。
またセマフォ変数を減算するのがP操作、元に戻すのがV操作と呼ばれる。どちらも語源はオランダ語。覚えなくて良い。

デッドロック

DB設計で絶対に避けるべきものの一つ。
例えば同じ２テーブルを参照するタスクAとタスクBがあるとする。タスクAはテーブルCをロックしてからテーブルDを参照する処理方式。タスクBはテーブルDをロックしてからテーブルCを参照する形式とする。
このときタスクAとタスクBがほぼ同時で行われると、タスクAはテーブルCをロック、タスクBはテーブルDをロックという状態が実現しうる。このときどちらもお互いの操作が終わるまでロックを解除しないので、どちらも終了できずに、どちらのテーブルのロックも解除されない事態となる。

同期制御

タスクAの起動タイミングが、イベントフラグによって決定されるとする。このときイベントフラグをとあるタスクが常時監視しており、イベントフラグが１になったのを検知したらタスクAが起動する、という仕組み。
（デザインパターンのオブザーバーみたいなイメージ？）

タスク間のデータのやり取り

タスクAの計算結果をタスクBに伝えたいとき、いくつかやり方がある。
１、メモリにデータを格納して参照してもらう
２、メッセージ処理用のキューにデータを流して受け取ってもらう
３、パイプ処理で直接渡す（Powershellなどで行うパイプライン処理はこれに該当するんだろうか？）

主記憶の管理方式（非仮想）

プログラムを実行するときはメモリにロードして実行する。
HDDへのデータ格納と同じく、プログラムをドカドカと適当に配置すると、メモリ上に空きスペースができてしまい非効率になる。
このような断片化状態において、HDDの場合はファイル自体を分割して格納していたが、メモリ上ではそれがないようだ（確証ないので知ってる人いたら教えてください）。
メモリ上にプログラムを格納する方式について整理する。

固定区画方式

メモリを固定の区画に区切り、そこにプログラムをロードしていく方式。例えばメモリが１６MBあり、４MBが４つの区画に分けられているとする。
ここで２MBのプログラムと３MBのプログラムをロードする場合、２MBのプログラムは区画１に、３MBのプログラムは区画２にロードされる。
この方式のデメリットは主に２つ。必ず区画ごとに入れ込むので空きが生まれやすいこと、また区画を超えるプログラムはロードできないこと。

可変区画方式

上から順番にプログラムをロードする方式。とてもシンプルだが、使い終わったプログラムを削除していくとスキマが空いてしまう。
それを解決するのがガーベジコレクション。

ガーベジコレクション（メモリコンパクション）

可変区画方式でスキマが空いた状態のとき、スキマを埋めるように上から配置しなおすこと。ガーベジコレクションともメモリコンパクションとも呼ばれる。余談だがC言語とかだとソースコード上でガーベジコレクションを実行するように指示ができた記憶がある。

メモリにプログラムが入らない場合の対処法２つ

解決法は主に２つある。１つは格納するプログラム自体をセグメントという単位に分割し、必要なものだけロードするオーバーレイ方式、もう１つは既存のプログラムを一度HDDなどに書き出して（スワップアウト）、空いたスペースにプログラムをロードする（スワップイン）というスワッピング方式。
ここで大事なのは、一般的にスワッピング方式という場合、プログラム単位でのデータ移動を指すという認識を持つこと。

主記憶の仮想管理

メモリ上にプログラムをロードするやり方において、前節のように不便がいろいろと生じる。固定区画にせよ可変区画にせよ、結局は物理的制約に悩まされることになる。
それを解消するのが仮想記憶管理である。
仮想的な主記憶アドレス一覧を作成し、メモリ変換ユニット（MMU：Memory Management Unit）が、仮想アドレスと実アドレスを紐づける。
この仕組みを動的アドレス変換機構（DAT：Dynamic Address Translator）と呼ぶ。
実アドレスは主記憶に加えて、足りない場合は補助記憶装置も使用する…のだが、本試験で問われるページング方式の場合、最終的には主記憶の中にプログラムがロードされている必要があるので、補助記憶装置も使える、という認識はあまりなくてもいいのかもしれない。

ページング方式

ページング方式のイメージは、前述のスワッピング方式にかなり近い。
スワッピング方式は「プログラム単位でデータをやり取り」するのに対し、ページング方式は「プログラムを分割したページという単位でデータをやり取り」するという違いがある。

ページング方式では、プログラムは４キロバイト単位でページに分割される。仮想記憶のアドレス空間もページで分割されているので、そこに対応するように調整するわけである。
プログラムは仮想記憶アドレスにロードされるが、主記憶にはまだ読み込まない。実際にプログラムが使用される状況になってようやく「あれ必要らしいから主記憶にロードしておいて」という処理が走る。この必要なときになるまでロードを遅らせる手法をデマンドページングと呼ぶ。他には「ここらへん必要そうだし先にロードしておこう」という方式をプリページングと呼ぶ。
補助記憶から主記憶に読み込む処理をページイン、主記憶からページを追い出すページアウトと呼ぶ。ここがスワップイン、スワップアウトと同じ。
またメモリが小さすぎるためにページアウトが頻発して処理が遅くなることをスラッシングと呼ぶ。

ページイン、ページアウトのアルゴリズム

大まかに四つある。
・FIFO（First In First Out）：ページインされた時刻が最も古いものをページアウトする。
・LIFO（Last In First Out）：ページインされた時刻が最も新しいものをページアウトする。
・LRU（Least Recentry Used）：ページを最近呼ばれた順にソートしたとき、最近呼ばれていないページをアウトさせる。
・LFU（Least Frequently Used）：ページの参照回数を算出し、参照回数が少ないページをアウトさせる。

一部プログラムの持つ「再」系の特徴４つ

ガベージコレクションによってメモリ上のプログラムの場所が動的に変更されても、そのプログラムを実行できる仕様を再配置可能(ReLocatable)と呼ぶ。このような「再」がつくプログラムの特徴を他にも見ていこう。
・再配置可能(ReLocatable)：上述の通り、メモリ上のどこに配置されてもプログラムが実行できること。ベースアドレス指定方式などによってこれを可能としている。
・再使用可能(ReUsable)：プログラムを何度実行しても正しい結果が得られるもの。
・再入可能(ReEntrant)：同時に複数のタスクから呼び出されてもそれぞれに対して正しい結果を返せるもの。データ部と処理部を別に持っており、それぞれのタスクに対して別のデータ部を用意することができるそうだ。
・再帰的(Recursive)：処理中に自身を呼び出すような処理。フォルダ内検索にてサブフォルダのパスを引数に渡すようなイメージ。