オペレーティングシステム

基礎概念のメモ的

普通にタイプミスや解釈ミスがあるかもしれないです

UNIX/Linuxプログラミング教室

0章 UNIXの基礎とシェル

1章 Cの復習

2章 Cの復習

3章 低水準入出力

4章 標準入出力ライブラリ

5章 プロセス

6章 ファイルシステム

7章 ファイル記述子のコピーとパイプ

8章 ソケット通信入門

9章 シグナルと競合状態

10章 端末

11章 端末

12章 非局所脱出

PFLab

OSの概要

ノイマン式コンピュータは、メモリから一度レジスタに書き出す方式で99.9%がこれ

OSの役目

・仮想化、抽象化によるハードウェア資源の有効利用

ハードウェア資源を仮想化し、実際より多く見せる--仮想メモリ

・機器の違いを抽象化して隠蔽し、統一インターフェイスを提供--open,read,write,closeで統一など

例えば、cpuは8個しかない時は8個のプログラムしか動かせないが、切り替えまくることで多くのプログラムが動くようにしている

プログラム実行方式

・マルチプログラミング

-複数のプロセスをメモリ上に配置

-プロセスがI/O要求に基づいて

・バッチシステム

-プログラム実行の流れをファイルに格納して、一括で実行

-スパコンで使用

・タイムシェアりんぐ

ユーザーインターフェイス

・Batch-一連のプログラム実行の流れをファイルに保存して一括実行

・CLI-シェル

・GUI

OSから見たコンピュータシステム

・I/OデバイスとCPUは同時に動作

・各デバイスコントローラはそのデバイスのみを制御

-そのためにバッファ領域を保持

・デバイスコントローラの状態を把握する方法

-ポーリング;逐一状態をチェック:確実だが、計算リソースがかかる

-割り込み:コントローラがCPUに対してI/O処理完了を通知←コントローラの仕様で色々と変化

・データ転送

-cpuがデバイスコントローラのバッファ領域から読み書き(PIO)、小さいデータ

-デバイスコントローラが主記憶に読み書き(DMA)、でかいデータのとき

キャッシュは何度も繰り返して使用する使用頻度の高いデータを高速にアクセスするために保管しておく記憶装置、バッファは多数のデータを処理する際にデータを一時的に保管する記憶装置や領域のことである。これにより処理するスピードと輸送するスピードの差を補っている。

CPUとI/Oのクロックは同期していないので、I/Oがデータ転送が終わっててもcpuが動かないとデータは取り出せない、これを防ぐのがロックや同期

OSの構造

・システム構成要素

・OSサービス

・システムコール

・システムプログラム群

システム構成要素

・OSカーネル

-メモリに常駐

-cpu特権モードで実行(プロセス管理、メモリ管理、ファイルシステム、ネットワーク管理、その他I/O管理)

・システムプロセス

-システム機能を実現するプロセス

・シェル

-OS機能を実行するためのユーザーインターフェースを提供

・ウィンドウシステム

・コマンド群

Cpuにアクセスできる特権レベルが、OSカーネルとシステムプロセス群より上とでは全然違う

プロセス管理

・プロセス

-OSが決めるプログラムの実行単位

-CPU時間、メモリ、ファイル、I/Oデバイスなどの資源を仕様

・OSによるプロセス管理の例

-プロセス生成・削除

-プロセス間通信

-プロセス停止・再開

全てのプロセスは、ユーザ空間とカーネル空間という同じ性質を持つ。

ここで、仮想メモリが重要になってくる。

メインメモリ管理

・メインメモリ

-複数のプロセスを展開・実行

-各プロセスの使用する領域の大きさは動的に変化

-プロセスの生成・消滅を考慮

・OSによるメインメモリ管理

-メモリの使用領域管理と身使用領域管理

-要求に応じたメモリの確保・解放

ファイル管理

・情報を格納する様々なデバイスの管理

-フラッシュメモリ、磁気ディスク、光ディスク、磁気テープ

・ファイルとは

-記憶デバイスの差に関係なく情報を格納するもの

-ファイルにはプログラムそのものやデータを格納

・OSによるファイル管理の例

-ファイル生成・削除

-ファイル、ディレクトリ操作など

I/Oシステム管理

・バッファ、キャッシュシステム

・汎用デバイスドライバインターフェイス

・デバイス依存ドライバ

Cf,usbやプリンタなどデバイスドライバを持っていればI/O

また、コードのほとんどがデバイスドライバである

二次記憶管理

・メインメモリは揮発性で容量も小さい

-メモリは早いが容量小さい

-ディスクは遅いが容量がでかい

・二次記憶（ディスク）へのバックアップ機能が必要

・OSによるディスク管理の例

-ディスク内のみ仕様領域管理

-領域の配布

-I/Oスケジュール

ネットワーキング

・コンピュータ同士のデータ交換が可能

・インターオペラビリティが重要

-sunspa

・ネットワークプロトコル

・OSはネットワークプロトコルに基づく通信機構を提供

プロテクションシステム

・プログラムが使用する資源のアクセス制御(read/write)

・アクセス制御の例 read_writeなど

・権限を与える相手の例

-ユーザ

-グループ

-プロセス

シェル

・文字ベースでのユーザインターフェイスを提供

・ユーザが入力したし自分を解釈実行する

↑これらがOSカーネルの構成要素

OS基本サービス

・OSが提供するサービスのうち基本となるもの

-プログラム実行

-I/O操作

-ファイルシステム操作

-交信

-エラー検出

OSサービス

・組み込み系OSでは基本サービスで十分

・サーバや計算センタではその他のサービスも必要になってくる

-マルチユーザジョブのための資源管理

-アカウンティング

-資源保護

Cpu実行モード

・スーパバイザモード

-危険な操作は特権モードのみ可能

・ユーザモード

-特権モードでないモードはユーザモード

Cf,root権限で動いているプロセスはスーパバーザモードで実行されているわけではない

CPU実行モードと割り込み

・割り込み

-ある事象が発生したことにより実行中に処理を中断し発生した事象のための処理を実行する機能

-割り込み処理を行わせるために、割り込み処理用プログラムが格納されているメインアドレスにプログラムカウントを変更

・割り込みの種類

-同期割り込み(例外処理、システムコール)

-非同期割り込み(タイマー割り込み、I/Oデバイス割り込み、ハードウェア障害)

システムコール

・システムコール用の特殊命令

システムコール（プリミティブ）

・システムコールはユーザプログラムとOSトノインターフェイス

-割り込み命令によって実現される

-C,C++などのプログラミング言語向けインターフェイスを提供

-Unix系ではマニュアル２章がシステムコール

Cf,ファイルオープンなどのシステムコールはむやみに使わない、わざわざ特権モードに入って、コストがかかるから

システムコールの種類(200ぐらい)

・プロセス制御

・ファイル管理

・デバイス管理

・情報管理

・交信

システムプログラム群

・プログラム開発、プログラム実行のための利便性のある環境を提供

・コマンド群

-File manipulation

-Status information

-File

・ユーザにとっては、どのようなシステムプログラムが提供されているか

プロセス管理

システムコールの仕組み

ユーザー空間からOS空間に飛べる関数はセキュリティ上存在しない

システムコール関数の呼び出しがあるとtrap命令の発行がある

すると割込みハンドラが動き、システムコール表からシステム処理ルーチンが動く

1.システムコール関数の呼び出し

2.ライブラリ関数内でtrap命令を発行

3.カーネルモードに移行,割込みハンドラを起動

4.システムコール引数を検査しカーネル内へコピー

5.システムコール番号と関数ポインタの評価ら呼び出しルーチンを特定し、処理ルーチンの実行

6.システムコール処理結果をユーザ空間へコピー

7.適切なプロセスのスケジュール

プロセス管理

プロセスはプログラムの実行単位で、CPU時間、メモリ、ファイル、I/Oデバイスなどの資源を使用

プロセスごとに仮想空間を割り当て-他のプロセスのメモリへのアクセスができないのでバグなどが起きても他のプロセスには影響しない

全てのプロセスについてユーザ空間（ユーザプログラムコード、ユーザデータ領域、ユーザヒープ領域、ユーザスタック領域）とカーネル空間（プロセス状態格納領域、カーネルプログラムコード、カーネル作業領域）が用意されている

空間割り当てはOS依存である

ユーザ空間からカーネル空間へは簡単には行けないが、割り込みを発生させて行なっている

プロセスに割り当てられているのは物理空間ではなく仮想空間である

C++などのポインタで0x、、、って表示されているのは仮想空間のメモリである。これは物理空間なので他のプロセスには影響しないのが仮想空間のいいところ。

仮想記憶

仮想記憶はページで記録される。

ポインタの値を見ると、論理ページ番号+オフセットが見られる。

Mmuはアドレスの変換をする、仮想アドレスから物理アドレスに変換する

仮想メモリをページといい、物理メモリをフレームという。

プログラムがバグってて変なアドレスの値を指定すると、segmentation faultが起きる。ページ番号があってるのに、起きるバグが一番しんどい。(4064bite程度の誤差だと普通にsegfaultにならずに動く)

ユーザー空間で書いてるうちは仮想メモリの空間にお世話になっている。

OSは表をセットして、ハードウェアがアドレスを処理する。

Mallocをするとページが追加される。read,writeするときはmmuが勝手に変換してくれる。

プロセスの種類

権限による分類

・ユーザプロセス

・スーパーユーザプロセス-特権機能を使用可能

形態による分類

・システムプロセス-オペレーティングシステムサービスを提供しているプロセスでシーパーユーザモードで動いているプロセスの総称

・デーモンプロセス-システムプロセスでユーザーからは見えないところで動いているプロセス

・サーバプロセス-クライアント・サーバモデルに基づいたサービスを提供しているプロセス

どんなプロセスが動いている？

linuxではtopやpsコマンド

Windowsではctl+alt+delしてタスクマネージャで見られる

X86系Linuxの仮想メモリ空間使用

上位がユーザ領域、その下がmmap領域、一番下がカーネル領域、カーネル領域がないと他のプロセスにアクセスできない

ユーザ領域にはtext, data,bssがある。

Mmap領域はmallocなどを宣言した時にスタックしている空間

32bitマシンだと、4ギガ以上にデータは絶対mallocできない（0x40000000 ~）

プロセス

loginプロセス

メモリイメージ

loginプログラムexex(“bin/sh.”)→shぷろぐらむ

Execというシステムコールを実行すると、空間を変わらず、メモリイメージが書き換わり新たなプロセスが実行

Forkがプロセス管理で一番基本になるシステムコール。

Forkをすると、親プロセスから子プロセスを生み出す。クローン的な。forkシステムコールの返り値は、子プロセスのid、よってできたかどうかわかる。

子プロセスの返り値は0なので、if(pid==0)で別のexecをして、その空間を別のものにする。

古典的なforkではcodeのみを共有するが、特殊なforkではdataも共有する。

プロセス実行の切り替え

・linux/unixではコマンド実行ごとにプロセス作成

・プロセス実行の切り替え＝プロセスコンテキストスイッチ、

PCB（切り替える単位）とプロセスの切り替え

PCBにプロセス毎に必要な情報を格納するープロセスの状態、CPUレジスタ、プライオリティ等のCPUスケジューリング情報、ページテーブル等のメモリ管理情報

PCBは特殊なメモリ領域。

Forループ書いても、OSがコンテキスト切り替えをするので自分のプログラムが影響を受けるだけ。例えば、forループにOSに影響するシステムコールなどのforkをたくさん入れたりすると、メモリがめっちゃ取られてPCが落ちることもある。

コード領域ーープログラム

データ領域ーーdata（初期化された静的変数、大域変数）、bss（初期化されない静的変数、大域変数）、heap（動的確保変数）

スタック領域ーーauto変数、制御情報

プロセスの状態

有限オートマトンになっている。New,Running,Waiting,Ready,Terminated

Running中にopenなどのシステムコールをするとready状態に戻ってしまうかも。

OSのスケジューラがプロセスを切り替えてくれる。

スケジューラの種類

・長期スケジューラ-バッチシステムでは、プロセスが投入されると、それらは二次記憶にはスプール（配置）され、スプールされたジョブのなかからいくつかのジョブを取り出して実行可能キューに投入する

秒あるいは分ごとに実行される

マルチプログラミングの度合いを制御する

遅くても良い

プロセスの性質に応じてスケジューリングする

・短期スケジューラ-どのプロセスを次に実行するか決定する

プロセスが待ち状態になるときに次に実行すべきプロセスを決めるために起動

プロセスが実行を続けている場合でもtimesliceごとに記号

処理が早いことが必要条件である

プロセス生成一般論

プロセス実行で起こること

-プロセスがI/O要求

-割り当てられたCPU時間が経過

-子プロセスを生成

-割り込みが発生

・プロセスはプロセスを作ることができる。最初にはinitプロセスがあり、プロセスを生成するにはforkするしかなくて、それらがプロセスツリーになっている。

・資源の共有可能性

親と子プロセスで、共有、一部を共有、共有しないことがある。普通はコード領域だけを共有する。

・実行関係

親と子は同時に実行可能で、親プロセスは子プロセスの終了を待てる

・メモリ空間

子プロセスは親プロセスのメモリ空間の複製を保持する

子プロセスはプログラムを読み込んで実行する。普通はfork→exec

プロセス終了一般論

・プロセスは最後にexitシステムコールをして、プロセスを終了

Exitシステムコールの時に終了コードを渡すことが可能である

親プロセスは子プロセスの終了をwaitシステムコールで待機できる

・プロセス終了時にすべきこと

プロセスが保持している資源の解放、シェルから起動したものはctrl+Cで子プロセスを終了することができる

スレッド

プロセスとスレッドを混同しない

スレッドはプロセス内での実行の流れ、プロセス内に複数スレッドを動かすような実行モデルはマルチスレッドモデルという。cpuが１つしかないなら、レジスタが１つしかないのでスレッドは１つしか実行できない。スレッドはデータとコードを共有しているので、スタックのポインタとレジスタのみを変えればすぐスレッドを切り替えできるので、処理が早い。例えば、データは同じで、色々な関数を実行するようなもの。

スレッドのcontext(管理実態)は小さい（切り替えが高速）

スレッドにはユーザレベルスレッドとカーネルレベルスレッドがある。

ユーザレベルスレッドは、スケジューリングの面倒をカーネルが見ない。つまりユーザライブラリで実現される。カーネルレベルスレッドより軽量、スケジューリングの方針等の変更が手軽である。カーネルが関係しないので、処理を横取りできない、

カーネルレベルスレッドでは、１つ１つのスレッドがプロセスと同様に扱われる。ほとんどがカーネルレベルのスレッドである。

マルチスレッド

並列コンピュータ上でのプロセッサの有効利用

資源を共有可能、応答性の向上

ほとんどのサーバプロセスはマルチスレッドを使う。というのも、入力待ちの時に他のものの処理が止まってしまうとサーバーが遅くなるから。また並列計算もマルチスレッドを使える。行列数のスレッドを用意すれば、並列計算で高速に計算できる。

プロセス間交信、スレッド

スレッドはプロセス内での一連の実行の流れ

独立プロセス:お互い影響なし

協調プロセス：プロセス同士で干渉する、googleスライドなど、だからローカルに落として作業することが求められる

強調プロセスの利点-性能向上、モジュラリティ

コンピュータの仕組みを正しく知らないと修正しにくいバグが出るプログラムを書いてしまう

強調プロセス間のやりとり

・プロセス間でメモリを共有

・プロセス間更新機能を提供

・シグナルの使用など

プロセス間交信

・強調プロセスを実現する別の方式

・IPCとも

・共有メモリを使用しない通信手段

・IPCの基本操作-通信路の確立、send、receive、通信路の後始末

・ブロッキングとノンブロッキング

-I/O要求をすぐに処理できないときに対応の仕方による差

普通はブロッキングの世界である

ブロッキングとはデータを読みたいときにデータがなくて先に進めないこと、ノンブロッキングはデータが読めないなら先に進んで後で読めばいいやということ。

シンクロなす、アシンクロナス

-I/O要求側とI/O処理側の関係による差

シンクロナスは相手が受信可能であることを確認してからデータを送る、アシンクロナスは相手が受信可能でなくもデータを送って相手が受信可能になったときにデータを読み取るという感じである。

シグナル

・プロセスに対してある事象を通知

・UnixやLinuxの場合、killシステムコールによりシグナルを通知

・シグナルを受け付けるための関数はsignalあるいはsigactionシステムコールにより設定可能

協調プロセス実現

・共有メモリ、IPC、シグナル

共有メモリを使ったプロセス同期

・背景-複数のプロセスが共有メモリ領域に読み書きすると、一貫性がなくなるので、データ一貫性のために何らかの機構が必要になる

・クリティカルセクション問題

・同期のためのハードウェア

・セマフォア

・古典的同期問題

Bounded-Buffer

マルチスレッドでの競合

コンテキストスイッチにおける競合

RaceCondition(競合状態)

・Race Condition-複数のプロセスが共有メモリを同時にアクセスしているとき、その共有メモリの最終的な値が、最後にその共有メモリのアクセスを終了したプロセス依存すること

・Race conditonを回避するために、プロセス同士の同期が必要になる

クリティカルセクション問題

・Critical Section-複数のプロセスがある共有メモリ領域を競合するアクセスをしているとき、競合アクセスしているプログラム部分

・Critical Section問題-あるプロセスがcritical sectionを実行しているとき、他のプロセスにはそのcritical sectionを実行しないようにさせること

・critical section = 際どい領域

クリティカルセクション問題における要求事項

1.Mutual Exclusion(排他制御)

-もしプロセスPiがクリティカルセクションを実行しているとき、他のプロセスがそのクリティカルセクションの実行が不可能

2.Progress

-もしどのプロセスもクリティカルセクションを実行しないなくて、かつ、ある複数のプロセスがクリティカルセクションに入りたいとき、どれかは必ず選ばれて実行

3.Bounded Waiting

-アルプセスがクリティカルセクションに入りたいと要求してから有限時間でクリティカルセクションに突入

ここでの仮定

・クリティカルセクション内で実行が中断する場合

・マルチプロセッサ上での話

・なお、シングルプロセッサにおけるクリティカルセクション問題は以下で解決が可能

-クリティカルセクションに入るまえに割り込み禁止に変更

-クリティカルセクションからできるときに割り込み可能に変更

同期のためのハードウェア

・Test and Set命令

-メモリ領域に1をセットし、昔のメモリ領域の値を返す

-これを処理をアトミックに処理

Test-and-Set命令を使ってmutual Exclusionを行うことができる

・Swap命令

-２つの変数の値を不可分に入れ替え

Swap命令を使ってMutual Exclusionを行うこともできる

Lock-freeとWait-freeを用いた同期

・Wait-freeな実装

-すべてのプロセスが、任意の有限ステップで終わる命令を他のプロセスに続行速度に無関係に実行できることが保証されていること

-つまりクリティカルセクションにおいて、test_and_setやswapなどを用いたLockを行う実装はwait-freeではない

・Lock-freeな実装

-いくつかのプロセスが、任意の有限ステップで終わる命令を、他のプロセスの実行sくどに無関係に実行できることが保証されていること

-飢餓状態になるスレッドが発生しても良い

-wait-freeな実装ではlock-freeだが、その逆は真ではない

Compare and Swap

ABA問題

マルチスレッドプログミングにおいて、同期化の過程で発生する問題であり、ある記憶域を二回読み出し、二回の読み出しが同じ値であることを変更がないとみなすことにした時、二回の読み出しの間に別のスレッドが値を変更し他の作業を行なった後また元の値に戻すと、最初のスレッドが誤って変更がなかったとみなしてしまうというものである。コンパイラはあるメモリが空いて、まったく同じものが来たら、同じ場所にわりあてようとする。これはコンパイラの問題なのでosにはどうしようもない。回避策としては、tagビットの導入がある。この場合のtagビットが扱える数は有限なので、ABA問題を完全に解決できているわけではない。

RCU

RCU参照クリティカルセクションでは、共有メモリにはポインタ経由腕アクセス。

Lockingでは、いくつものプロセスがlockを待っていると、キャッシュが汚れてしまい、そのあとのパフォーマンスに問題をきたしてしまう。

TransactionalMemory

株などで取引するときはバグが起こったらやばい損失が生まれてしまうのでハードウェアの同期の制御をする。

マルチスレッドをするにはpthread_mutexライブラリを用いると良いでしょう。

プロセス同期

セマフォア

レースコンディション

Pcが落ちる原因の9割はデッドロックという原因である。

デッドロックとは、資源を排他的利用しているプロセス集合において、あるプロセスが他のプロセスが排他的利用している資源を確保しようとしてまち状態になることである。

デバックしきれていないオンラインゲームなどでよく起こる。

飢餓状態

半永久的なブロッキング、プロセスが停止したままセマフォアのキューから取り除かれることがない状態、例えばp0とp1がセマフォを取りあるような状態

共有資源に対するもんdない

Bounded-Buffer問題

あるバファーに対する処理をするのに

Reader-Writer問題

書き込みと読み込みをwriteという共有のセマフォを使って守る。

これらの問題は比較的簡単に解決できる

Dining-Philosophers問題

複数の共有資源を同時に取りたい時に起こる問題で、一番解決が難しい

ナイーブなプログラムだとデッドロックが発生してしまう

Critical region

共有変数は特別な方法で処理をしようという考え方

そもそもバグったコードを書けないようにプログラミングを構造化してしまうという考え方である

Monitors

モニタないの手続きは、一時期に１つのプロセスのみ実行

つまり、安全なコードをモニター側が用意しているのでそれを使えばいい

共有変数とプロセスを絵に描くと、デッドロックが起きるかどうかを判定してくれる

デッドロックの性質

・Mutual Exclusion:１つのプロセスのみがリソースを使用できる状態

・Hold and wait：１つのプロセスが１つ以上のリソースを保持した上で他のプロセスが

・No preemption

・circular wait

この４つの状態をグラフを用いて解析する

グラフを書けば、デッドロックを起こす可能性があるのかどうかがわかる。

デッドロック問題に対する手法

デッドロック予防：デッドロック状態にならないように共有資源の使い方を決定

デッドロック回避：デッドロック状態になると検知したらそれを回避する

多くのシステムではデッドロック回避手法は実装されていない

Osはデッドロックが生じないように注意深く設計されているが、linuxにも20行に1つはバグがあることが証明されている

スケジューリングによってデッドロックを回避

銀行家のアルゴリズム：要するに資源を貸せるプロセスにかしていくというアルゴリズム

試験に出るぞ

CPUスケジューリング

CPUスケジューリング

OSの中心となること、問題の6,7割がこのcpuスケジューリングの問題に帰着される

基本概念

・マルチプログラミングで得られる最大限のcpu使用率を上げること

-マルチプログラミング:一台のコンピュータで同時に複数のプログラムを実行すること

・cpuとI/O処理のサイクル

-プロセスはcpuによる処理とI/O待ちをしているという２つのサイクルで成立

Cpuスケジューラ

・実行可能状態のプロセスの中からプロセスを一つえらび、cpuによる実行を許可

・cpuスケジューラが呼び出されるタイミング

1.プロセス状態が変わるとき

2.タイマー割り込み:cpuスケジューリングのためだけのクロックがある

3.I/O割り込み

・Nonpreemptiveスケジューリング

-上記1のタイミングでしかスケジューリングしない場合

・preemptiveスケジューリング

Dispatcher

・Dispatcher:スケジューラによって選択されたプロセスにcpuの実行を与えるカーネルモジュール

・Dispatcher latency

-実行中の

スケジューリング評価の指標

・cpu使用率

・スループット

・ターンアラウンドタイム

・待ち時間

・応答時間

これらのトレードオフで決まる

・cpu利用率

-cpuの動作時間/システム稼働時間

-OSによるオーバヘッドもこみ

-利用率が高い方が良い

・待ち時間

-プロセス完了までに実行可能キューで待つ時間の合計

・スループット

-cpiが単位時間当たりに行う仕事量（完了するプロセス数）

-バッチ処理の登場でスループットが向上

・ターンアラウンド時間

-プロセスの実行を要求してから完了するまでの時間

・応答時間

-プロセスの実行要求から最初の応答までの時間

ここら辺の言葉は覚えておく！

古典的スケジューリングアルゴリズム

世の中にスケジューリングアルゴリズムは１万以上ある

・FCFS

・SJF

・Priority Scheduling

・Round Robin Scheduling

First-come, First-served scheduling

アルゴリズムはとても簡単である

・仮定

-プロセスがP1, P2, P3の順番に到着

・待ち時間

→どうやら待ち時間が短いプログラムから実行すると平均待ち時間やターンアラウンドタイムは短くなるらしい

Shortest-Job-First Scheduling

・各プロセスはcpu burst処理する時間を保持

・一番短いcpu burst時間を持つプロセスに実行権を付与

・２タイプ

-Nonpreemptive

-Preemptive

・決められてプロセス軍の最小待ち時間を達成するにはsjfが最適

プロセスの処理時間はあらかじめわからないので厳密にできないのが欠点

次のcpu burst時間をどうやって予測するか？

・直前の実際のcpu burst時間から、指数平均を使って推測

Priority Scheduling

・各プロセスに優先番号を付与

・高いプライオリティを持つプロセスにcpuを割り当て

-preemptive

-nonpreemptive

・sjfはpriority scheduling の一種

・問題

-飢餓:,

・解決法

-エージンぐ:プロセスを実行するごとに優先番号を増

Round Robin(RR):linuxに実装されている

リアルタイム系を作るときはこれを使うことがお多い。

・各プロセスにcpu時間単位を割り当て

・プロセスがtime quantum時間cpuを使用すると処理が中断され、ready queueの最後に移動

・ready queueの先頭からプロセスを取り出し、そのプロセスにcpu資源を割り当て

Deeplearningはブラックボックスなので、処理時間がわからず、処理時間がわからないとシステムは製品にできない。こういうのは国際規格で決まってきてしまう。

RRの性質

・qが十分に大きいとfcfsとなる

・qの大きさと小さくすると、、、

・平均ターンアラウンド時間は、time quantumの値に依存

・一般的に、一回のtime quantumでほとんどのプロセスのアイッッ興亜終了できる値に設定すると平均ターンアラウンド時間は短縮

・Round Robin:TSSの基本的なスケジューリング方式

・行って時間だけcpuを割り当て

・実行可能キューはFIFO

Multilevel Queue

・実行可能キューをプロセスの性質に応じていくつかのキューに分割

例えば、シェルなどはkill commandなどができないといけないので優先度が高く設定されている

Lunuxにはアルゴリズムが実装されていないが、階層化して各レベルに異なるアルゴリズムの適用を考えたら多くのパターンの優先度付けができるようになる

・キューごとに独自のスケジューリングアルゴリズムを持たす

Foreground-RR

Background-FCFS

・キュー間でのスケジューリング

Multilevel Feedback Queue

普通プロセスが他のキューに移動することはないが、feedbackではスタベーションが起きているプロセスは他のキューに移動させたりする。

Multilevel Feedback Queue一般論

・プロセスを様々な待ち行列に移動

-実行時間に応じて待ち行列を変更

・Multlevel-feedback-queue schedulerの設定

-待ち行列の数

-各待ち行列のスケジューリングアルゴリズム

-プロセスを低いレベルの待ち行列に移す条件

-プロセスを高いレベルの待ち行列に移す条件

-プロセスがサービスを必要とした時にどのレベルの待ち行列に入れるかを決めるメソッド

・多重レベルフィードバックの効果

-入出力バウンドなプロセスはcpu処理時間が短い傾向

-cpuバウンドなプロセスの優先度は低い

→cpu処理と入出力処理のオーバラップ

・cpu利用率/スループットの向上

・時間がかかる入出力は早めに要求し、待つ間に他の仕事をする

-何にバウンドするかは前もってわからない

あるリソースに依存しているタスクを~バウンドという

・多重レベルフィードバックの効果

-どう優先度プロセスが複数ある場合でも、ラウンドロビンにより応答性を確保する

CPUスケジューリングとトランザクション処理

Real-Time Scheduling

・Hard real-time system:クリティカルなタスクを保証された時間内に完了することが必要、時間きっちり

・Soft real-time systems:クリティカルなタスクはそのほかのものよりもプライオリティが高いことが必要、時間おくr

・実時間スケジューリングアルゴリズム

-静的優先度方式:Rate Monotonic Scheduling

-動的優先度方式:Earliest Deadline First Scheduling

リアルタイムシステムの応用分野:マルチメディア、ロボット、VR、ゲームナド

リアルタイムプロセス:時間制約はアプリケーション依存、スマブラなら60FPSみたいなこと

この周期のうちでどのくらい実行時間があるのかがCPU使用率である。これは高い方が良い。

Rate Monotonic Scheduling

・周期プロセス:デッドラインは次の周期が始まるまで

・固定優先順位

・周期の短いプロセスが高い優先順位を与える

・Rate Monotonic Schedulingではスケジューリング可能性を静的に解析可能

Rate Monotonic Analysis

・仮定

-全てのプロセスは単一CPU上で動作

-コンテキストスイッチ時間は無視

-プロセス間での依存関係なし

・スケジューラビリティは69%

RMAはCPU利用率が100%以下でもスケジュールできない例

Earliest Deadline First Scheduling

・動的優先度スケジューリング

・デッドラインが近いプロセスを高い優先度

・スケジューラビリティは100%

・タイマ割り込みごとに

-デッドラインの計算

-デッドラインの最も近いプロセスを実行

・スケジューリングコスト有

各タスクは周期的にジョブを生成

全てのジョブが次の周期までに実行を完了できるようにスケジューリング

時間的正確さはスケジューリングアルゴリズムに依存

マルチコアでのリアルタイムスケジューリング

グローバルスケジューリング:コアの移動ok

パーティションスケジューリング:タスクキューに対応したコアのみで処理

効率的なアルゴリズム

・EDF-USアルゴリズム

・EDF-BFアルゴリズム

・EDZLアルゴリズム

スケジュール可能なシステム使用率50~60%

最適なアルゴリズム

・Pfairアルゴリズム

・EKGアルゴリズム

・LLREFアルゴリズム

スケジュール可能なシステム使用率が100%

計算が複雑化、プリエンプションが多発

Priority Inversion

・高いプライオリティのプロセスが実行できず、結果として低いプライオリティのプロセスが実行されてしまう現象

・共有資源

-低いプロセスが共有資源を排他的にしよう

-高いプロセスが共有資源を必要とした時に、低いプロセスが使用しているために待ちが発生

トランザクション

・トランザクションとは

-論理的に１つの機能として実行される操作の集まり

-一般にはデータベースにおける更新、検索などの処理

・例（銀行口座で１万円を引き落とす）

READ A

A = A-10000

WRITE A

トランザクション

・トランザクションは以下の４つの特性ACIDを満たさなければならない

-Atomic(原子性)

-Consist(一貫性)

-Isolated(Serializability)

-Durable(永続性)

トランザクションのAtomicity(原子性)

・トランザクションの原子性

-クリティカルセクションは排他制御と同様に、外の世界に対して不可分

-トランザクションは完全に実行されるか、全く実行されないかのどちらかで中途半端な実行はしない

・マシンの故障を考えると、記憶デバイスの性質を考える必要がある

-Volatile Storage

-Nonvolatile Storace

-Stable Storage

トランザクションのConsistency

・不変性:システムに常時満たされなけレバならないある種の制約

・もしトランザクションの前にその普遍性を満たしていれば、トランザクションの後でも満足

トランザクションのSerializability

・IsolatedあるいはSerializability

・複数トランザクションが実行されている時、最終的な結果があたかも全てのトランザクションがある順序で逐次的に動作したようにみえること

2相ロック

・整列化が可能

・２つの相

-Growing phase:Lockのみをしていくフェーズでunlockなし

-Shrinking phase:UnlockのみをしていくフェーズでLockなし

・厳密2相ロック

-全てのリソースをロックするフェーズ

-データをアクセス

-コミット

-リソースを解放するフェーズ

厳密2相ロックの利点

・Cascaded Abortを防ぐことができる

-Cascaded Abort:例えば、トランザクションT1があるデータを修正し、そのあと、T1がコミットする前にトランザクションT2　がそのデータを読むあるいは修正

メモリ管理 part1

メモリ管理

・プログラム実行までの道のり

・swapping

・連続メモリ領域割り当て

・paging

・segmentation

・segmentation with paging

Static vs Dynamic

・Static link：ファイルサイズの肥大化

・dynamic link：ライブラリにバグがあった時にリンクし直す必要がある

プログラム実行までの道のり

メモリ使用量を減らす工夫

・Dynamic Linking

-実行時にライブラリのリンク

-リンク時には、実行時にライブラリリンクするためのルーチンとリンク

-ファイルとして保存される実行イメージ小

・Dynamic Loading

-サブルーチンが呼ばれるまでメモリ上にコピーなし

-必要ないルーチンは呼ばれないのでメモリ使用率高

・shared Libraries

-Dynamic Linking機能を利用してライブラリを提供

-ライブラリのバグフィックスに対応可能

-プロ

Linuxにおける共有ライブラリ

・バイナリファイルはELF

・カーネルは、execvシステムコール内において

・最近のアプリケーションはたくさんの共有ライブラリを使用

・たくさんの共有ライブラリを動的にリンクするのは時間が必要

スタックは上から下に下り、heapは下から上に番地を上がって行く感じ、

これは逆でも成り立つ

オーバーレイ

・プロセスのメモリ領域が足りない時に、メモリ領域を処理に応じて複数の目的で使用

Swapping

ほとんどの場合は２次記憶があるのでこの技術を使う

・メモリが足りなくなり、プロセスが動けなくなった時

・プロセスイメージを一時的に２次記憶にswap out

・その代わりに、２次記憶上にswapoutしていたプロセスイメージを主記憶に復元

連続メモリ領域の管理方法

・２つのメモリ領域

-カーネルが使用：主記憶になければならない

-ユーザプロセスが使用

・Multiple-partition allocation

-Hole：割り当て可能な連続するメモリ領域、様々なサイズのholeが発生

動的連続メモリ領域割り当て問題

・フリーなholeから大きさnのメモリ領域をどのように探すか？

- First-fit；要求しているサイズに最初にマッチしたholeを割り当て

- Best-fit：要求しているサイズにマッチする一番小さいholeを割り当てリストはサイズ順に並べられている必要あり

- Worst-fit：一番大きいholeを割り当て

Fragmentation

・External Fragmentation

-トータルメモリ領域はあるが、連続領域としては存在しない

・Internal Fragmentation

-割り当てられたメモリは要求したメモリより大きく、使用しない無駄なメモリ領域がある

・Reduce external fragmentation by compaction

-メモリの内容を移動してコンパクション

・I/O program

-I/Oが使用しているメモリ領域は他の目的に使用不可能

可変区画割つけ

・固定区画割つけの問題点

・区画を可変サイズで管理

ここまで扱ったのは物理メモリの扱いである、しかし物理メモリでは少なすぎるので仮想記憶という概念を用いる

C言語のポインタは全て仮想アドレスなので、物理アドレスとは関係ない。

MMU（メモリ管理ユニット）がないと仮想記憶が構成できない。OSがやるのはMMUの設定だけで、OSは関係ない。変換はハードウェアが勝手にやってくれる。また、アドレス変換テーブルを作るのもOSの役割である。

仮想記憶

・物理メモリ量以上のメモリを仮想的に作成

・仮想的に見えるので仮想記憶

・仮想アドレス：仮想記憶上のアドレス

・物理アドレス：物理メモリ上のアドレス

・主記憶よりも大きな記憶領域

・各プロセスに独立したアドレス空間

・実アドレス空間

-主記憶のアドレス空間

-最初は連続しているが、、、

・仮想アドレス空間

-

動的アドレス変換

・仮想アドレスと実アドレスの対応

-バイトやワード単位

・主記憶以上の領域が必要

-ブロック単位で対応

・セグメンテーション:セグメントは可変長のブロック

・ページング:ページは固定長のブロック

・仮想アドレス v = b | d

・b:ブロック番号→アドレス変換テーブルのインデックス

・d:ブロック先頭からのオフセット

Paging

・プロセスの論理アドレス空間は物理メモリ上で連続である必要なし

・物理メモリを固定長のブロックにして管理

このブロックはフーレムという、フレームは物理メモリ側なので固定長である

ブロックの長さは２のべき乗であることが多い。

・論理メモリ領域も同じサイズに分割

・Internal fragmentation:よく起こる問題である。2のべき乗にしたら少しは回避できるかも。要調査。

・ページイン:ページを二次記憶から主記憶上のページフレームに移動

・ページアウト：ページを二次記憶へスワップアウト

・ページフォルト

-主記憶に存在しないページをアクセスした時に発生する割り込み

-ハードウェアの機能

-割り込みハンドラ

ハードウェアによるアドレス変換機構

・Page mapping tableによる変換

-各エントリは物理アドレスと属性を保持

-Access Permission

ページテーブルと物理アドレス

上のビットが変わり、下の方のビットは変わらない

ページテーブルの置き場所

・主記憶に置くか？

-ページテーブルベースレジスタ→実アドレス

・メモリアクセスをするために、さらにページテーブルへのメモリアクセスが生じて速度が低下

→仮想記憶をサポートするCPUにTLBを置く

TLB

・Translation Look-aside Buffer

・一般的には連想メモリで実現

・アドレス変換の際は、まず連想メモリを調査

・なければ主記憶のテーブル

なるべきTLBにページテーブルを置いておきたい、というのもメモリにアクセスしなくてもよくて楽なので。

Hierachical Page tables

・論理アドレス空間を複数のページテーブルで管理する

・２レベルページテーブル

・３レベルページテーブルなど

メモリは節約されるが、時間がかかる。トレードオフである。ハードウェアでやるのであまり遅延は起きず、今では多段階でやるのが普通である。

メモリ管理 & I/Oシステム

どのOSにも当てはまる話は今回が最後である。CPUとメモリがないOSはない。

C言語のポインタは仮想アドレスである。

仮想アドレスは上位でページテーブル上の位置を表す。下位ではページ内のアドレスを表す。

ページテーブルは主記憶に置くと、遅くなるので、TLBというCPU上のキャッシュを使う。

ページテーブルの大きさ

全エントリを使うと、１つのプロセスにつき使うメモリが多すぎて主記憶に置くことは無理になるので全エントリを使うことは滅多にない。

多重レベルページングとセグメンテーションを併用している。

Mmuはcpuのハードウェア機能である。OSはアドレス変換表をセットするだけで、アドレス変換はCPUのハードウェアがやってくれる。ページエントリにvalid-invalidをつける。0の時はページ例外が発生して、OSガページをメモリにロードしようとする。

Page Fault

ページがあればOSは何もしなくていいので、page faultを中心にしてOSが実装される。

1.あるページが初めて参照

2.ページ例外が起こりカーネルに制御が移動

3.カーネルは、カーネル内のテーブルを参照

Invalidの時メモリ参照例外、メモリにロードされていない時空きフレーム確保

フレームとは、物理メモリをページサイズで区切っていったもの

4.ディスクからメモリにロード

5.validation bit = 1

6.実行を再開

空きフレームがない時はPage Replacementが起きる。あまり使われてないページを探して、その領域を２時記憶にコピーする

Demand pagingの性能

アクセス時間の平均をEATという指標で表せる

動画やメディアはいろんなページを使うのでpage faultが発生しがち。

Demand pageとcopy writeは関連性が高い。

Copy on Write

・Forkシステムコールで生成された子プロセスは親プロセスのイメージをコピーする代わりに、親のプロセスイメージを共有

・どちらかのプロセスがページに書き込む時、そのページをコピー

Memory-mapped files

・Memory-mapped file I/Oとは、ファイル内容をメモリにマップすることにより、メモリの読み書きでファイルの内容をアクセスできるようにする機能

ここまでがdead pagangの話

Page Replacement

あまり使われてないページを探して、その領域を二時記憶にコピーすることでその領域を使用

・ユーザプロセスがページを必要とする時、フリーフレームがないと・・・

・どのページを選択するか？

・使用されていたフレームをディスクにコピーするかどうかの判断は？

Basic Page Replacement

・ディスク上に保存してあるページを探索

・空きフレームを

-見つかればそのフレームを使用

-なければpage replacement algorithm

-victimページをディスクに書いて、ページテーブルを変更

・ディスク上のページの内容を空きフレームにコピーしてページテーブルを変更

・プロセス再開

Page Replacement Algorithms

・Page Faultが少なくなるようなアルゴリズムを使いたい

・もちろんpage faultの回数は、どのくらいの物理フレームがあるかに依存する

First-in-First-out algorithm

Belady`s Anomaly

・FIFOでページフレーム数を増やすとかえってページフォルト数が増えることもある

未来のことがわからないと最適なアルゴリズムは作れなさそう

Least Recently Used Algorithm

最適に近そうだと言われている。最近使われてないページは今後も使われないだろうという仮定に由来する。というのもプログラムには時間的局所性があるから。

LRUの実現には、カウンタ、スタック、行列が考えられる。カウンタはハードウェア的に無理ゲー。行列は二進数で見ていく。

LRUの近似：参照ビット

・ページに関する状態ビット（統計値の収集）

-ページテーブルエントリ中に保持

-ハードウェアがメモリアクセス時に該当ビットをセット

-ソフトウェア的なシュミレートも可能

近似アルゴリズムには、Reference bitを使ったアルゴリズム、Second chanceアルゴリズム、nruアルゴリズム、クロックアルゴリズム、nfuアルゴリズム、

Nfuアルゴリズムでは、昔よく使われていたものは退避対象にならないのでエージングという手法がある。これは、時間が経つにつれてビットをシフトしていくという手法である。

フレーム割り当て

・プロセスを実行するのに必要な最小ページ数が存在

・例えば、データのコピー

・もし、フレームが３つしかなかったら、フレーム割り当て法

割り当て法

1. Equal allocation

2. Proportional allocation

3. プロセスの優先順位でproportional allocation

Global vs Local allocation

・Global replacement

-各プロセスは置き換えるページフレームを選ぶ際、すべてのページフレームから選択可能

・Local replacement

-それぞれのプロセスは置き換えるページフレームを選ぶ際、決められたページフレームの集合からの身選択可能

ページングの利点

・外部断片化がない

・主記憶の大きさに依存しないアドレス空間

・実際に使用するページのみを主記憶の配置

参照の局所性

・短期的なページアクセスに多く見られる傾向

・少量の高速メモリでも処理を高速化

時間的局所性、空間的局所性もある

Segmentation

・ユーザから見るとメモリ領域は、様々な意味のある塊

-プログラム

-変数

-スタック

・セグメントとはこのような塊

Segmentationはメモリで領域をくぎれる機能で、領域を越えようとすると、segmentation faultが出る。これがseg fauが出る理由。

Working set model

・ワーキングセット

-プログラムが使用しているページの集合、主記憶にあればページフォルトはほとんど発生なし

・ワーキングセットモデル

-各プロセスのワーキングセットを記録

-プロセス実行前に対応するメモリ中への存在を確認

・D = WSSの合計 = 要求されるフレームの合計

・if D > mの時、thrashingが起きる

Thrashing

プロセスが頻繁にページイン・ページアウトを繰り返すこと（頻繁に使用するページがメモリキャパよりも多いとき）

・マルチプログラミングの多重度を向上

-CPU利用率/スループットが向上

・多重度を上げすぎるとページフォールトが多発

サービスをダウンさせないためにこういった知識が必要である

バッキングストア

一般にHDDの一部で固定領域主記憶よりも大きく、ファイル・主記憶よりも小さい

I/0システム

Sbrkシステムコール

Bssを拡張するシステムコール。

Mallocをすると、sbrkシステムコールでbss領域を拡張して拡張した領域をmallocに当てられる。

Mmapシステムコール

任意のファイルを仮想アドレス空間にマップする。

ほとんどI/Oへは、read/writeのシステムコールで接続する。

Page faultに関するその他

Program2は一回ページを読んでくると、そのページで1024回使えるが、program1だと一回ごとにページを読んでこないといけないのでpage faultの回数が全然違う。また、このプログラムを2回実行するとキャッシュなどの関係であまり関係なくなる。

コンピューターサイエンスを学ぶと、どういうコードが早くて、どういうコードがだめなのかがわかるようになる。page faultやシステムコールの数も気にする。普通のコンピューターで早いコードが書けなければ、スーパーコンピューターで速くなるわけがない。

DMA(direct memory access)

I/Oとメモリの読み込み書き込みでわざわざcpuでシステムコールしてread/writeするのはめんどくさいし遅いのでコントローラーが独自に転送するというシステム。

・高速I/Oデバイスがデータを主記憶に転送するための機能

Linuxのコードが8割ぐらいがI/Oドライバのコードである。その中で少しでもドライバのコードを楽にする技術が必要。

Application I/O interface

・I/Oシステムコールによるデバイスの抽象化

いろんなデバイスがあるが、デバイスの特徴に合わせてユーザに対して統一したインターフェイスを提供

・Blockデバイス：ディスクとか、１バイト単位じゃない通信

・Characterデバイス：1バイト単位で通信、

・Networkデバイス：前の二つを兼ね備えているが、ネットワークで外に行ったりするので分けて考える。

この３種類に統一！統一することでシステムコールが減らせる。

ネットワークデバイス

・Socketインターフェイス

-ネットワークプロトコルとネットワーク上のオペレーションを分離

OSから見るとみんなファイルに見える

Life cycle of an I/O request

例えば、readを何回も読んで、データを読み込むと、このlife cycleが何回も実行される。

Improving Performance

・コンテキストスイッチの数 減

・データコピー　減

・Pollingやうまい制御での割り込み数 減

・DMAを使用

・スループットを上げるためにCPUやメモリ、バス、I/Oをバランス

I/O

バスは2系統あってNorthBridgeとSouthBridgeがある。NorthBridgeはほとんどメモリだけ。SouthBridgeと比べてメモリは高速に使える。

DiskContoroller

OS屋はDiskcontrollerを見てデスクドライバを書いていく。

Hard Disk Drive(HDD)

HDDは皿を回さなきゃいけないので遅い、磁気で操作する

SDDは皿を回す必要がないので早い、電気で操作する

クラウドとかサーバーではハードディスクが全盛期

大容量で安いが遅い

SSD、フラッシュディスク、は高くて、容量小さいがアクセスが早い

・ディスクアクセス時間

-シーク時間（ヘッドの移動時間）

-回転待ち時間(アクセスするセクタ時間)、どのセクタかはOSが教えてくれる

-データ転送期間

ディスクの構造

OSはディスクをデータ構造としてどのように管理しているのかというと、１次元配列として管理をしている

RAID0

サーバーとかクラウドの構成で知っておくべき技術。

安いディスクをたくさん並べて、壊れにくいストレージシステムを作ろうという考え方。

全部で7つのRAIDの概念がある。

RAID0:壊れにくさは変わらない。ディスクを分散させることでスピードが上がる。また、１つのディスクに集中して接続しないので、ちょっと壊れにくくなる。スピード重視の時に使う。

RAID1

1つのディスクが吹っ飛んでもコピーが残っているので大丈夫。

RAID5&RAID6

パリティ：他のディスクの情報の暗号みたいなもの、

他ディスクの内容が吹っ飛んでもパリティとそのディスクの内容を使えば復元できる。

1000日に一回ぐらい吹っ飛ぶ。

日本の事業はRAID5やRAID6が作れずに、クラウドにあまり手を出せなかった。冗長構成で大きなディスクを作るのはとても難しい。GoogleとかAmazonとかFaceBookはだからすごい。

ディスクスケジューリング

・OSの役割はハードウェアを効率よく使用すること

クラウドの遅い、早いはRAIDの組み方とディスクスケジューリングでかなり変わってくる。

・ディスクのアクセス数

・seek時間を短くすることが重要

・複数ディスクI/O要求に対して、どの順番でそれらの要求を処理するか？

0から199までのシリンダー（ディスクの半径）があって、どの順番でそれらの要求を処理するか？初期は53で98,183,37,122,14,124,65,67の順番とする。

-FCFS：例では640cylinders

-SSTF：例では236cylinders

-SCAN：一番効率が良いと言われている、例では208cylinders

-SCAN(Elevator)：逆方向に進まないで、ヘッドを逆方向の端まで移動すればいいじゃん！

-C-SCAN

-C-SCAN(C-Elevator)

-LOOK and C-LOOK：0とか先まで行く必要ないじゃん！という気持ち

アマゾンやGoogleでは何百万台のディスクに対して、ディスクを壊さないようにRAIDで組んで、みんなが平均的に接続するように分散しなきゃいけないので、スケジューリングも難しい。コンピューターサイエンスのコアな部分をやってる人はGoogleやAmazonに行く。だから、アメリカでは大学生の勉強モチベが高い。

Disk Attachment

・２つの方法

-コンピュータのI/Oポートに接続

-ネットワークに接続：NFSのような分散ファイルシステムとSCSIの延長

最近はデータが大きいので、データを動かすのではなく、データがある場所にクライアントが言ってそこでプログラムを動かすという考え方に移行してきている

ファイルシステム

ファイルはOSが見せてくれている連続した論理的アドレス空間である

プログラム中に保持する情報は、プロセス生成後に発生し、終了時に消滅する、またアドレス空間の大きさに制限がある→ファイルは二次記憶に保存する

ファイルとは

・記憶装置の構造に依存しないデータ保持の単位

・統一的な取り扱いが可能な論理的存在

ファイルの名前

・情報の抽象化

・文字数・使える文字などの制限はファイルシステムにより差がある

・拡張子：ファイルの種類の判定、単なる慣習、OS・アプリが解釈する場合も

ファイル属性はディレクトリの中に保持されている：name,type,locationなど

ファイル操作では基本的に、Create, Write, Read, Seek, Delete, Truncate, Open, Closeしかできない

OSがみるファイルのタイプは３種類ぐらいしかないが、アプリケーションが見るアプリの種類は色々作ることができる

Readはディスクの内容をメモリに読み込むことで、writeはメモリの情報をディスクに書き込むことです

ファイルを開くと、メモリへのポインタが必ず渡される

ファイルの構造

・バイト列

・レコード列

バッファリング

・二次記憶に直接読み書きするのは遅いのでメモリ中に一次蓄積

・バッファリング：二次記憶からブロック単位でメモリに転送、プロセスはバッファに読み書き、変更のあるバッファは定期的・開放時に虹記憶に書き戻す、CPUと入出力の並列処理

ダブルバッファリング

・２つのバッファ：一方のバッファを読み書きしている間に他方に二次記憶から転送・プロセスのI/O町を最小化

ファイルアクセス方法

逐次ファイルよりもランダムアクセスファイルの方が楽である、磁気ディスクだとこういうランダムなアクセス方法はできない

ファイルの管理

・ディレクトリ（フォルダ）：ファイルの情報を保持する管理実態、二次記憶上に保持、ファイルを見るときにいちいち名前やsizeを読み込んでいたらめんどくさい

ディレクトリ作成の指標

・Efficiency：高速にファイルを探索可能

・Naming：ユーザー利便性

・Grouping：ファイルの特徴による論理的な集合を定義可能

ディレクトリエントリの管理

・線形リスト

・二分木

・ハッシュ

Acyclic-Graphディレクトリ

異なる名前で同一の実態を参照するので、木構造の止まらず有向グラフになる

つまりグラフの探索は有向グラフの探索問題ということになる

・Hard Link：ディレクトリから直接ファイルの実態を参照する

・Symbolic Link：パス名を保持していて、そのパスに飛べるという機能

プロテクション

・ファイルの所有者と生成者は誰に対してどのような操作を許すべきかを制御する

・操作の種類：Read,Write,Execute,Append,Delete,List

プロテクションの使い分けが情報倫理として重要である

７はRWXが111、6はRWXが110、1はRW1が001と表す。

Owner access, group access, public accessの順番である

アクセス制御

ファイルなどの資源に対する操作を適切に制限する

ホワイトハッカーはまずこれをチェックする

・ドメイン：保護の対象とそれに対する権限の組の集合

・制御手法：アクセス制限行列、アクセス制御リスト、けーぱビリティ、ユーザをクラスに分類

アクセス制御リスト

ネットワーク管理はACLをどのように管理するのかが鍵である

これを設定した人がいなくなると手をつけられてなくなることが多い

ケーパビリティ

・ドメインごとに権限の集合を保持する

プロセスにはけーばビリティが与えらえ、これによって使用できるファイルなどが変わってくる

ACLは人と外部、けーばビリティはプロセスに対する権限

ファイルシステムのマウント

USBをさしたときに自分のファイルシステムの中にUSBのファイルを連結することができる

これをマウントという

ファイルシステムの構造

アプリはread/writeしかできない

ファイルコントロールブロックには色々な情報が入っている

Virtual File System

UnixとかLinuxでは大きいところ

ファイルシステムによってreadもwriteも変わるが、それは等価性を保つために見せられないので、VFSを用いてファイル管理をする

ファイルシステムの実装者はVFS関数を作る必要がある

ディレクトリの実装方法

・データブロックへのポインタを保持したファイル名の線形リスト：シンプルな実装だが実行に時間がかかる可能性

・ハッシュテーブル：ハッシュデータの線形リスト、ディレクトリ探索の時間コスト軽減、衝突、サイズを変更しやすい

割り当て手法

ファイルを保存するためにディスクブロックをどのように割り当てるか

・連続割り当て：実装は簡単で、ランダムアクセスが容易、連続で割り当てなきゃいけないので空き領域がいっぱいできる、フラグ面テーションが起こる

・リンク割り当て：そのファイルに何バイトめがどこにあるのかわらかない、つまりランダムアクセスが出ない

・インデックス割り当：最近ではこの方法が主要、ファイルの属性持てないインデックつおいう要素を付け足す、欠点としてはファイル１つごとに無駄なファイルを１つ作らなきゃいけない、最近はディスクが巨大になってきているので一般的

巨大なファイルになると、dirext blocksだけでは扱いきれず、single indirextやdouble indirectが使われる

Unixなどではiノードという構造体の中に全てのファイルに関する情報が入っている

Unixファイルシステムの構造

Boot block：OSの軌道に必要なプログラム

Super block：ファイルシステムの基本情報、ブロック数、最大ファイル数など

I-node space：Iノード空間

Data blocks：ファイルの実態、i-node中のブロックポインタから指定される

ディレクトリもi-nodeで管理されているので、OSから見たらディレクトリもファイルもあまり差がない

Fopenするとファイルポインタが出てきてユーザーはファイルの中身へのポインタを保持するが、osの中ではi-nodeへのポインタを保持する

Iノードとファイル記述し

Openというシステムコールをラップして、ユーザーに見せている

Fflushというシステムコールを打つと、メモリにあるものを強制的にディスクに書き込む

Fopenとするとファイルの最初をポインタが示しているが、seekをするといきなり１００バイトめとかに飛べる。

９９行分空行読みをしてもいいが、空行読みは一度メモリに読み込まなきゃいけないので時間が遅くなる

一度読んだファイルはほぼほぼキャッシュに残っているので、ディスクの性能を見るときにこれのせいで早くなっちゃうことがあることが多い。ディスクから直接読むことはあまりない。

Pcならここら辺まででいいが、サーバーなどではrecoveryの機能が必要になっている

Recovery

・一貫性のチェック：ディレクトリ構造内のデータとディスク上のデータを比較して誤りがあれば修正

・他ストレージにバックアップを取るプログラムを使用

・バックアップから消えたファイルを復元

Log Structured File Systems

・ログ構造ファイルシステム：ファイルシステム適用されるアップデートをトランザクションとして記録する

・全てのトランザクションはまずログに記録

・コミット：トランザクションがログに反映されること

大事なのはiノードがどのような構造を取るのかを理解すること、多分テスト出るぞ！

プロテクション、バッチシステム、並列分散システム

プロテクション問題

OSのデバイス、プログラム、データ、プロセスなどのオブジェクトはユニークな名前を持ち、決められた操作を介して参照されるべき

Domain構造

アクセス権はあるオブジェクトに対する全ての有効な操作の部分集合、ドメインはプロセスのアクセス権の集合

UNIXにおけるDomainの実装

CPU資源に関する２つのドメイン：user,supervisor

ユーザに関するドメイン：user-id、owner, group,othersに対して、readwrite, execute, lookup

Access Matrix

プロテクションを行列として表現、行はdomainsを表現、列はobjectsを表現

バッチシステム

ユーザはあらかじめ実行手順をファイルに書いて、そのファイルを提出

システムは待ち行列からファイルを取り出して実行

システムはジョブキューからジョブを取り出して空いているノードにジョブを割り当てる

バッチシステムにおけるスケジューリング

バッチジョブスケジューリング：コンピュータシステム上で同時に幾つのジョブをどのように実行させるかを決定

並列分散コンピュータ

クラスタ：本来単体で使われるコンピュータ群をネットワークで接続し、それらをシステムとして使用する

超並列コンピュータ：千台以上の規模の計算機をネットワークで接続して並列コンピュータを実現するために開発されたコンピュータ

グリッド：インターネット上での仮想組織

クラウド、ビッグデータ

分散システム

複数の独立したコンピュータを単一システムとしてみせるシステム

透過性

・access：データ表現の違いを隠蔽

・location：資源がどこに存在するかを隠蔽

・migration：資源が他の場所に移動したかどうかを隠蔽

・Relocation：震源が使用中に他の場所に移動したかどうかを隠蔽

・Replication：資源が複数のユーザから共有されているときに複製が作られているかどうかを隠蔽

・Concurrency：共有資源が複数のユーザから使われていることを隠蔽

・Failure：故障を隠蔽

・Persistence：資源がメモリ上かディスク上にあるかを隠蔽

並列分散システム構成法

ハードウェアを管理し、ユーザに対してシングルシステムイメージを提供

Cuda

Compute unified device architecture

CUDAでプログラムを書いている限りは様々なgpuで実行可能である

GPUでプログラミングするときは大体CUDAを使う

GPUは数千コアがあり、グルーピングして使う

今までは、GPUで１つのタスクを行うだけだったが、最近はいくつものタスクを行わなければならなくなり、OSがスケジューリングを行わなければならないが、このスケジューリングはCPUのスケジューリングと異なる。

共有メモリ管理機構

GPUにも必要

GPUはほぼ行列計算をするために用いられるので、色々なcontextでメモリを共有できないとすごいめんどくさい

というのも、一度CPUにコピーして、またGPUにコピーする必要があってめんどくさくなる

OS関連の雑多なメモ

ブートの仕組み

OSが起動しないとファイルやディレクトリにはアクセスできない

ここではOSが起動する直前までの段階と主なOS起動のごく初期の段階、ブートシーケンスについて説明する

電源を入れるとマザーボード上にあるBIOS ROM内に格納されている初期化プログラムが呼び出される

周辺機器の初期化

初期化プログラムはまずビデオカードの初期化を行う

これは初期化の経過をディスプレイに表示する必要があるため一番最初に行われる

そのあとはメモリチェックや基本的なデバイスの初期化

起動ドライブのサーチ

ドライブにはDFF,HDD,CD-ROMなどがあるがここではHDDの場合について

BIOSの設定でBoot Sequenceという項目があるが、この項目を設定することによって起動ドライブを指定できる

起動ドライブディスクの先頭セクターのロード

次にBIOSプログラムが行うのは起動ドライブディスクの先頭セクターのロードである

この段階ではOSは何も実行されておらず、ファイルシステムは存在しない

この状態でディスクにアクセスするにはBIOS ROM内部に16ビットコードで書かれているPC/ATの基本入出力サブルーチンのうち、ソフトウェア割り込みINT13Hで呼び出せるディスクBIOSによって行うしかない

これはある意味ハードディスクを生で読むこと

先頭セクターにある起動プログラムの実行

先頭セクターをロードすると、BIOSプログラムはそこに書かれたプログラムに制御を移す

この先頭セクターをハードディスクではマスターブートレコードと一般によび、フロッピーディスクの方はブートセクターと呼ぶ

マスターブートレコード(MBR)

PC/AT互換機ではセクターは512バイトなのでMBRも当然512バイトである

パーティションテーブル、ブートシグニチャがある

先頭から446バイトのプログラム領域はBIOSプログラムによって次のように実行される

1 パーティションテーブルの検査

2 見つかったらその領域の先頭位置をテーブルから取得する

3 BIOSにその位置を示して、当該先頭セクターをメモリーにロードしてもらう

4 ロードした先頭セクターに制御を移す

この起動プログラムをマスターブートストラップローダと呼ぶ

LinuxのローダであるLILOなどはマスターブートレコード内のプログラム領域部分に書き込むことができ、PC/AT互換機の一般的ブートシーケンスをトラップして独自の起動シーケンスを実現することができる

このようにしてPC/AT互換機一般のIBMオリジナルの部ートストラップローダと違ったものになってしまったものを元に戻す方法として、DOSやWindows95/98のFdisk/mbrというコマンドがある

これはパーティションテーブルに触れることなく、プログラム領域部分だけPC/AT互換機一般の不ートストラップローダに書き換える

ブートセクター修復用のsysコマンドとfdisk/mbrコマンドの役割が時折混同されるので気を付ける

MBRの部ートストラップローダによってブートセクターがロードされ、制御がそちらに移されると、ブートシーケンスもいよいよPC/AT互換機一般の世界から離れてOS固有の世界に足を踏み入れる

ブートセクター

ブートセクターはOS固有

ブートセクターは各パーティションの先頭セクターということでパーティションブートレコード(PBR)と呼ばれることも結構ある

ブートブロックなどとも呼ぶ

プログラムコードへのジャンプ命令、ディスクパラメータ、プログラムコード、ブートシグニチャ

ブートセクターの役割とこれを作る人

MicrosoftOSの場合、ブートセクターの役割はOSのブート作業だけにとどまらない

ブートセクターの中のディスクパラメータはそのパーティションのファイルシステムに関する重要な情報源としてOS稼働時にも参照される

LinuxなどはLILOを当該ブートセクターにインストールしない限り、ブート作業すらしない

ブートシーケンス図

ブートシーケンスをそれぞれのデータの位置関係もわかるように図式化した

システムコールの仕組み