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

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

加藤 真平

東京大学 大学院情報理工学系研究科

[email protected]

PFLab（加藤研）のウェブサイトからダウンロードできます。 ⇒http://www.pf.is.s.u-tokyo.ac.jp/ja/classes/

2019/6/17 2

講義概要

• 受講生に求める基礎知識

– C言語の理解

– コンピュータアーキテクチャの基礎の理解

• メモリ管理、割り込み、CPUモード

• 参考図書

– Silberschatz, Galvin, and Gagne, Operating System

Concepts 8th Edition,

Wiley

• 成績

– 試験の点数で決定

– 試験は持ち込み不可

– 授業に出席していた人で試験の結果が悪い人は追試

験あり

• 出席をとるが出席点はなし

第8回 オペレーティングシステム

講義スケジュール（予定）

1. OSの概要（4/8） 2. プロセス管理（4/15） 3. プロセス間交信、スレッド（4/22） 4. プロセス同期（5/13） 5. CPUスケジューリング 1（5/20） 6. CPUスケジューリング 2 & トランザクション処理（5/27） 7. メモリ管理1（6/3） 8. 休講予定（6/10） 9. メモリ管理2（6/17） 10. I/Oシステム（6/24） 11. ファイルシステム（7/1） 12. プロテクション＆セキュリティ (7/8) 13. バッチシステム＆分散システム&まとめ（7/22） 14. 試験（7/29）

UNIXの仮想アドレス空間

• 多くのUNIXは左のような

配置（Linux, FreeBSD）

– 0～3GBがユーザ プロセス空間 – exec直後のtext, dataバッキン グストアは実行ファイル自体 text

data

stack

0x0000000 0xC000000 0xffffffff

bss

kernel text, data stack text

data

header symbol table

実行ファイル

（ディスク中）

ページテーブルは 10bit，10bitの2段 (IA32 Linux，FreeBSD） 2019/6/17 第8回 オペレーティングシステム 4

Copy-on-Write

• data領域などは読み書き可能

– 実行可能ファイルをバッキングストアにして大丈夫？ – 書き換えちゃったら・・・？ – 同時に読み書きしたら・・・？ – 書き込みが行われた時にページを確保・コピー text data read read write page fault ! text data header symbol table read-only read-only text data write ページを 確保しコピー text data header symbol table read-only read-only data read-write 書き込み不可で ページ保護

プログラムコードやライブラリの共有

• プログラムの部分は一般に書き換え不可なので

主記憶の一部を共有して，省メモリ化が可能

:

0 1 15 主記憶

:

0 1 15 仮想アドレス空間

:

0 1 15 仮想アドレス空間 2019/6/17 第8回 オペレーティングシステム 6

sbrkシステムコール

• void *sbrk(増分)

– データ領域（アドレス空間）を「増分」バイト増やすシス

テムコール

• 主記憶を直ちに確保するわけではない UNIXの仮想アドレス空間（UNIXの種類によって配置される アドレスは異なるがデータ領域は空き空間に隣接） text データ stack 決められた上限まで使用可 sbrk()等で明示的に拡張しない限り，「データ」 領域を超えてアクセスは不可能 sbrk(0)

malloc()/free() ープログラムから見たメモリ管理ー

• sbrkによってメモリを確保（mmapを使うことも…）

• free()された領域の管理 … リスト等で空き領域管理

– free()された空き領域 → 足りるならそこから確保 • first-fit, best-fit等の方法で – 空き領域がなければsbrk

• OSの機能（システムコール）を利用したライブラリ関数

– OSが提供するものと異なる実装を用いても○ • cf. K&Rの単純な実装例 – 割当て･解放，断片化，局所性等の性能は実装依存 2019/6/17 第8回 オペレーティングシステム 8

mmapシステムコール

• 任意のファイル

を仮想アドレス空間にマップ

– ページフォルトで必要部分を（OSによって）読み込み

• void *mmap(void *start, size_t length,

int prot, int flags, int fd, off_t offset);

– start:このアドレスからマップ • ページサイズの整数倍, 0ならmmapに任せる – length:マップする長さ – prot:PROT_EXEC,PROT_READ,PROT_WRITE – flags:MAP_SHARED,MAP_PRIVATE（COW) – fd:マップするファイル記述子 – offset:ファイルのこの位置からマップ

マップする位置について

text data bss sbrk(0) こういう部分にも マップが可能 この部分のPTEは用意 しなくてよい（cf. 多段 ページテーブル） 2019/6/17 第8回 オペレーティングシステム 10

/* stdio.h, sys/mman.h, unistd.h, sys/types.h, sys/stat.h, fcntl.hをインクルード */ main() { int fd; char *p; /* getpagesize() のファイルをあらかじめ用意 */ fd = open("output", O_RDWR|O_CREAT, 0600); if ((int)(p = mmap(0, getpagesize(),

PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0)) == -1) { perror("mmap"); exit(1); } printf("%c¥n", p[100]); p[0] = 'a'; p[100] = 'b'; munmap(p, getpagesize()); /* マップを消去 */ close(fd); }

Windowsの仮想アドレス空間

• x86 Windows の標準で

は2GBのユーザ空間

• 起動時オプションで

3GBを指定可能

• XP, Server 2003 は2GB

～3GBの間で指定可能

0x00000000 0xC0000000 0xFFFFFFFF 1GB system space 3GB user space system cache, page pool, non-page pool 2GB user space kernel, executive

process page table, hyper space

0xC0800000

Page faultに関するその他

• Program structure

– int A [1024][1024];

– Program 1

for (j = 0; j < 1024; j++)

for (i = 0; i < 1024; i++)

A[i][j] = 0;

– Program 2

for (i = 0; i < 1024; i++)

for (j = 0; j < 1024; j++)

A[i][j] = 0;

A[0][0]

A[0][1]

A[0][2]

….

A[1][0]

…..

2018/6/18 第10回 オペレーティングシステム 14

DMA (Direct Memory Access)

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

• デバイス側にDMAコントローラが実装

– 例えば、InfinibandやMyrinetネットワークの場合、

• ネットワークカード＜－＞ホスト側主記憶

• ＤＭＡコントローラがデータを直接転送

• プロセッサによるコピーと違い高速転送が可能

2018/6/18 第10回 オペレーティングシステム 16

Application I/O Interface

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

– いろんなデバイスがあるが、デバイスの特徴にあわせて

ユーザに対して統一したインターフェイスを提供

• Blockデバイス • Characterデバイス • Networkデバイス

Application I/O Interface

• デバイスの特徴とインターフェース

– Character-stream or block

• 1バイト単位かブロック単位か

– Sequential or random-access

• 順次？ランダム？

– Sharable or dedicated

– Speed of operation

• キーボード入力程度のスピード？ • ギガビットネットワークのスピード？

2018/6/18 第10回 オペレーティングシステム 18

Block and Character デバイス

• Block デバイス

– ディスクなど

– コマンド：read, write, seek

– Raw I/O or file-system access

– Memory-mapped fileが可能

• Character デバイス

– キーボード、マウス、シリアル

2018/6/18 第10回 オペレーティングシステム 20

ネットワークデバイス

• ネットワークデバイス ≠ block, characterデバイス

• Socketインターフェイス

– ネットワークプロトコルとネットワーク上のオペレーション

を分離

• ネットワークプロトコル：UDP, TCP, RAW,

…

– 複数のコネクションでメッセージを待つselect 機能あり

• 他にもいろいろなAPIが存在

Clocks and Timers

• 現在時刻，経過時間，タイマー

• プログラマブルインターバルタイマ

– 経過時間によって割り込みをかけることが可能

• これによる周期的プロセスを作ることが可能

– スケジューラ、swapperなどの実装に使用

2018/6/18 第10回 オペレーティングシステム 22

2018/6/18 第10回 オペレーティングシステム 24

Improving Performance

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

• データコピー 減

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

• DMAを使用

• スループットを上げるために，CPUやメモリ，バス，

I/Oをバランス

I/O

• I/Oバス – ISA, EISA – PCI, PCI-X – PCI Express – USB, USB2 – IEEE1394

– (UNIbus, Mbus, Sbus)

• ディスク – IDE – SCSI – SAS/SATA • ディスク構成 – RAID • ネットワーク – Ethernet

– Fibre Channel, Infiniband, Myrinet

CPU North Bridge South Bridge Memory ISA PCI PCI Express USB COM, LPT Front Side Bus Disk Controller Network Interface Card disk disk disk disk

Disk Controller

• 例

2018/6/18 第10回 オペレーティングシステム 26

Hard Disk Drive (HDD)

• ディスクアクセス時間 – シーク時間 ヘッドの移動時間 – 回転待ち時間 アクセスするセクタ時間 – データ転送時間 出典：

2018/6/18 28

ディスクの構造

• ディスクは論理的には１次元のブロックアレイ

RAID

• RAID

– Redundant Arrays of Inexpensive Disks – Redundant Arrays of Independent Disks • RAID 0

– Stripingによる性能向上

– ファイルをブロック単位に分割し，複数 のディスクに保存

• ブロックサイズ＝stripe size, chunk size – 読み書きするデータ量がブロックサイズ

より多ければ，並列にディスクをアクセ スが可能になり性能が向上

• RAID 1

RAID 0 + 1, RAID 1 + 0

• RAID 0+1 – ストライプされているディスク群をミラー – 一つのディスクが故障するとミラーされて いるディスク群を使うことに • ここでさらにディスクが故障すると駄目 • RAID 1+0 – ミラーされているディスクを使ってストラ イプ – 各ディスクがミラーされているので、各デ ィスクが故障してもＯＫ 2018/6/18 第10回 オペレーティングシステム 30

RAID5 & RAID6

• ブロック単位のパリティを分散配置 • パリティ D1= 10101010 ….. D2= 00001110 ….. D3= 01110101 ….. D4= 10010010 ….. XOR ---01000011 ….. • RAID5は、1台ディスク故障耐性 • READ性能が高い • WRITE性能はパリティ生成性能が鍵 • RAID6はパリティが2つ。2つ目は対角 方向。2台ディスク故障耐性 P D1 P D2 P D3 P D4 P P パリティ Q P D1 Q P D2 Q P D3 Q P D4 P Q P Q ・ディスクが1台故障したら、パリティ を使って故障ディスクのデータを復元 ・RAID6は、復元中に正常ディスクが 故障しても大丈夫

2018/6/18 32

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

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

– ディスクに対しては、高速アクセスと高速データ転送（ディスクバンド幅） • ディスクバンド幅 – 転送したバイト数 ÷ 転送に要した時間（リクエスト発生～転送終了） • ディスクのアクセス時間 – Seek time • ディスクヘッドを移動する時間. – Rotational latency • Platterが回転してセクタがディスクヘッドに回るまでの時間 • Seek時間を短くすることが重要

– Seek time  seek distance

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

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

するか？

• 例：

– ０から１９９までのcylinderがあり

– I/O要求の待ち行列には、以下の要求があると仮定

98, 183, 37, 122, 14, 124, 65, 67

– 初期ヘッド位置

53

2018/6/18 34

FCFS

FCFSでは、ヘッド移動は640cylinders

SSTF

• Shortest Seek Time First

• 現在のヘッド位置から一番近いヘッド位置に移動できる要求を

処理

• SJFスケジューリング同様starvationが生じる可能性あり

• 例では、 ヘッド移動は236 cylinders

2018/6/18 36

SCAN

• ディスクアームは一端から多端に向かって動きながらリクエス

トを処理

• 端までたどり着いたら逆方向に動きながら処理を継続

• elevator algorithmとも

• 例では、 ヘッド移動は208 cylinders.

第10回 オペレーティングシステム

SCAN (Elevator)

• もし、ヘッド位置の要求が均一に分布しているとすると・・・

• ヘッドの周辺からSCAN方向の要求はすぐに処理されるが、

SCAN方向の反対側の要求は処理が遅く

• ヘッドが端にいったら逆方向に進まずに、ヘッドを逆方向の端

に移動して、処理をしてほうが、良いのでは？

2018/6/18 38

C-SCAN (C-Elevator)

• Circular SCAN

• SCANよりも待ち時間が均一になる傾向がある

• ヘッドが端にいったら逆方向に進まずに、ヘッドを逆方向の端

に移動させて処理を継続

第10回 オペレーティングシステム

LOOK and C-LOOK

• SCAN, C-SCANの改良

• ヘッドを端までもっていかず、もし、ヘッドの移動方

向にI/O要求がなければ、移動方向を変更

2018/6/18 40

Disk Attachment

•

２つの方法

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

– ネットワークに接続

1. NFSのような分散ファイルシステム 2. SCSIの延長

SAN(Storage Area Network) 分散ファイルシステム

ファイルシステム

• File Concept

• Access Methods

• Directory Structure

• File System Mounting

• File Sharing

• Protection

• File System Structure

• File System Implementation

• Directory Implementation

• Allocation Methods

• Free-Space Management

• Efficiency and Performance

• Recovery

ファイル

• ファイルとは

– 連続した論理的アドレス空間

– 内容:

• データ – 数値 – 文字 – バイナリ • プログラム

• ファイル構造

– 構造なし

• 語あるいはバイト列

– 単純なレコード構造

• 行、固定長、可変長

– 複雑な構造

• 書式化されたドキュメント、 リロケータブルプログラム オブジェクト

– 誰が決める？:

• Operating system • Program 2018/6/18 第10回 オペレーティングシステム 42

ファイルとは

• プログラム中に保持する情報

– プロセス生成後に発生し、終了時に消滅 – アドレス空間の大きさに制限 もっと長期に大容量… プロセス メモリ中 ファイル CPU メモリ 2次記憶

ファイルとは

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

– データやプログラム

– 記憶装置は主に2次記憶（外部記憶）

• HDD, フラッシュメモリ, 磁気テープ, etc. • 主記憶上にファイルを配置することも可能

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

– 生成、オープン, 読み, 書き, クローズ, etc.

– 属性情報を保持

2018/6/18 第10回 オペレーティングシステム 44

ファイルの名前

• 情報の抽象化：保存しておいて後から読み出し

– ファイルに名前を付加

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

– 8+3, 256, ... ; 大文字・小文字の区別

• 拡張子 (ピリオド [.] より後ろの扱い)

– ファイルの種類の判定

• .txt, .tex, .doc, .ppt, .bat, .exe, .c, .h, .o, ... – 単なる慣習の場合

2018/6/18 46

ファイル属性とディレクトリ

• Name – 名前 • Type – ファイルのタイプ • Location – デバイス上のどこにあるか • Size – 大きさ • Protection – 誰にread/write/deleteを許すか • Time, date, and user identification

第10回 オペレーティングシステム F 1 F 2 _{F 3} F 4 F n Directory Files これらの属性はディレクトリの中に保持

ファイル操作

• Create

• Write

• Read

• Seek

• Delete

• Truncate

• Open(F

_i

) ： F

_i

で示されるファイルをディスクから探索

– ファイルの中身をメモリ上で操作できるように

• Close (F

_i

) ：メモリ上で操作した内容をディスクに反映

2018/6/18 48

ファイルタイプ例

OSにおけるファイルアクセス

• ファイル制御ブロック(FCB: File Control Block)

– ファイル記述子(File Descriptor)とも

– ファイルシステム中の属性情報のうち必要なものを保持

– ファイルのアクセス状態の管理

– プロセスはFCBを通じてファイルを操作

• read, writeの引数ではFCBの配列のインデックスを指定

– ユーザプロセスはFCBの中味は変更が不可能

– Openの返り値として取得が可能

OSにおけるファイル操作

• create/delete

– ファイルの生成・削除

– 生成時には属性の指定

• open

– ファイルの使用開始

– 必要な属性をFCBへコピー

• ファイルアクセスに関する状態情報も保持

– 操作属性の指定 (read only など)

2018/6/18 第10回 オペレーティングシステム 50

OSにおけるファイル操作

• close

– バッファのフラッシュ、FCBの削除

– 属性情報の更新

– プロセス終了時には全て自動的にclose

• read/write

– データの読み出し・書き込み

– ある程度のまとまりを主記憶(バッファ)に保持

OSにおけるファイル操作

• append

– 追記、writeの限定版

• seek

– 読み・書きの場所の移動

• set/get attribute

– 属性値の取得 (時刻やら)

• rename

– ファイル名の変更

2018/6/18 第10回 オペレーティングシステム 52

ファイルの構造

• バイト列

– OSはファイルの中味に興味なし – 構造的な解釈はアプリケーションが担当

• レコード列

– 論理レコード • ファイルを構成するデータの集まりの単位 – 住所録 = 名前・住所・電話番号 – 改行まで (可変長) – 物理レコード(ブロック) • 記憶装置に入出力する際のデータの単位 – 内容は１つまたは複数の論理レコード

ファイルの構造

• 構造を持つファイル (論理構造)

– 2次記憶装置(物理構造)に依らず扱う必要性

– ファイルの2次記憶への格納時

• 論理構造 ⇒ 物理構造へ変換し格納

– 2次記憶からファイルの読み出し時

• 物理構造 ⇒ 論理構造へ変換し主記憶に配置

• ファイルアクセスの方法

– 2次記憶での構造と入出力の効率化

2018/6/18 第10回 オペレーティングシステム 54

バッファリング

• 二次記憶を直接読み書き → 遅い

– メモリ中に一次蓄積

• バッファリング（buffering）

– 二次記憶からブロック単位でメモリに転送

– プロセスはバッファに読み書き

– 変更のあるバッファは定期的・解放時に二次記憶に書き戻す

– CPUと入出力の並行処理

ダブルバッファリング

• 二つのバッファ

– 一方のバッファを読み・書きしている間に他方に二次記憶から／へ転送 • プロセスのI/O待ちを最小化 入力レコード 出力レコード レコード レコード レコード レコード レコード レコード レコード レコード レコード レコード レコード レコード レコード レコード レコード レコード レコード レコード レコード レコード レコード レコード レコード レコード 作業バッファ 入力バッファ1 入力バッファ2 出力バッファ1 出力バッファ2 2018/6/18 第10回 オペレーティングシステム 56

ファイルアクセス手法

• 逐次ファイル (sequential file)

– レコードを書き込んだ順で配置

• 書き込んだ順でのみ読み出し可能

– 磁気テープ上のファイルはこの構造

• レコードの位置はレコード番号で指定

• 途中のレコードを読む場合

– 先頭から読みたいレコードの前までを読み飛ばす必要あり

ファイルアクセス手法

• 直接アクセスファイル (direct access file)

– ランダムアクセスファイル(random access)

– 任意の位置のレコードを直接アクセス可能

• ファイルのブロックサイズの粒度(固定)

– 逐次アクセスの2次記憶装置では実現不可能

• 磁気テープ

• ランダムアクセス可能な２次記憶装置

• ランダムアクセス可能な割当て方式

2018/6/18 第10回 オペレーティングシステム 58

ファイルの管理

• ディレクトリ (directory) … フォルダ

– ファイルの情報を保持する管理実体

• 1つのディレクトリで複数ファイルを管理 • ２次記憶上に保持

• ファイルアクセスの際にディレクトリもアクセス

– 高速化が必要

– 一部を主記憶にキャッシュ

2018/6/18 60

ディレクトリ操作

• ファイルの探索

• ファイルの生成

• ファイルの削除

• ディレクトリの下のファイルをリスト化

• ファイル名を変更Rename a file

• 他のファイルシステムに移動

– 例： • LinuxファイルシステムからWindowsファイルシステムへ – 貸与したLaptop上でWindowsファイルシステムを見ることが可能 • LinuxファイルシステムからNFSファイルシステムへ 第10回 オペレーティングシステム

ディレクトリ作成の指標

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

• Naming ： ユーザー利便性

– 複数のユーザーが異なるファイルに同じ名前

– 同じファイルに異なる名前

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

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

• 線形リスト

– 特定のエントリの検索 ⇒ 線形探索 – エントリをソート ⇒ ２分探索 • エントリの挿入・削除が複雑 (2次記憶)

• ２分木

– エントリの挿入・削除が容易 – 線形リストより領域が必要

• ハッシュ

– 高速，エントリの挿入・削除が容易 – 同一ハッシュ値の対策が必要 2018/6/18 第10回 オペレーティングシステム 62

ディレクトリの階層

• 単一レベルディレクトリ

– システムにディレクトリは１つ – ファイル名をシステム全体でユニークにする必要あり

• ２階層ディレクトリ

– ユーザごとに独立 • 自分の空間のみ参照 • ユーザ間共有不可 ・・・ File File File ・・・ ディレクトリ ・・・ File File File ・・・ user n user 2 user 1 ・・・ マスタファイルディレクトリ ユーザファイルディレクトリ

ディレクトリの階層

• 木構造ディレクトリ

– ディレクトリの階層化を一般化 • ルートディレクトリ，サブディレクトリ ・・・ File File File File File File File File File ルートディレクトリ サブディレクトリ 2018/6/18 第10回 オペレーティングシステム 64

ディレクトリの階層

• パス名(path name) … 木構造の中での指定法

– 絶対パス名 (absolute path name) • ルートから指定

– 例： /usr/local/bin/

– 相対パス名 (relative path name)

• 作業ディレクトリ (working directory)から辿る際のパス • カレントディレクトリとも (current directory)

• UNIXの場合

– / で区切り、. がカレント、.. が一つ上

2018/6/18 66

単一レベルディレクトリ

• すべてのユーザーが同じディレクトリを使う

Naming problem Grouping problem 第10回 オペレーティングシステム

２レベルディレクトリ

• ユーザ毎にディレクトリを作る

•Path name

•Can have the same file name for different user •Efficient searching

2018/6/18 68

木構造ディレクトリ

• 効率良い検索

• グループ化機能

• カレントディレクトリ

やワーキングディレク

トリの概念

– cd /spell/mail/prog

– more list

– mkdir tmp

– rmdir tmp

第10回 オペレーティングシステム

Acyclic-Graph ディレクトリ

• 異なる名前で同一の実体を参照

(aliasing)

• If dict deletes list



dangling

pointer.

解決方法:

– Backpointers, so we can delete all pointers.

Variable size records a problem. – Backpointers using a daisy chain

organization.

2018/6/18 70

Acyclic-Graph ディレクトリ

• Hard Link

– ディレクトリからファイルの実体を参照

– ファイル側はreference countを保持

– 参照しているファイルが削除されてもファイルの実体は残る

• reference countがゼロでないから

• Symbolic Link (Soft Link)

– ファイルのパス（文字列）でファイルを参照

– 参照しているファイルが削除されると、symbolic linkしているファイル名から の参照が不可能

Acyclic-Graph ディレクトリ

• Hard LinkとSymbolic Link (Soft Link)

% cd ~/linktest

% echo “hello” > mydata.txt % mkdir foo % cd foo % ln ../mydata.txt archive.txt % cd ~/ % ln –s linktest/mydata.txt data.txt % ls –l data.txt % rm ~/linktest/mydata.txtの結果、 ~/linktest/foo/archive.txtおよび~/data.txtはどうなるか？ % rm ~/linktest/foo/archive.txtの結果、 ~/linktest/mydata.txtおよび~/data.txtはどうなるか？

2018/6/18 72

プロテクション

• ファイルの所有者と生成者は、誰に対してどのような

操作を許すかを制御すべき

• 操作の種類

– Read

– Write

– Execute

– Append

– Delete

– List

• ディレクトリの場合、ディレクトリにあるファイル名を検索 第10回 オペレーティングシステム

Unix系におけるアクセス制御

• アクセスモード

– read, write, executeを3bitsで表現する

• ３カテゴリ

RWX

a) owner access

7



1 1 1

RWX

b) group access

6



1 1 0

RWX

c) public access

1



0 0 1

• グループの作成

– /etc/group

• ファイルのグループ名の変更

– chgrp Group-name game

owner group public

アクセス制御

• ファイル等の資源に対する操作を適切に制限（保護）

– 制御の対象となるファイル操作： • 読出し(R)，書込み(W)，実行(X)，追加，削除

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

• 制御手法

– アクセス制御行列 – アクセス制御リスト – ケーパビリティ – ユーザをクラスに分類 保護ドメインの例 ドメイン1 ドメイン2 ドメイン3 2018/6/18 第10回 オペレーティングシステム 74 ファイル6 [RWX] プリンタ2 [W] ファイル1 [R] ファイル2 [RW] ファイル3 [R] ファイル4 [RWX] ファイル5 [RW] プリンタ1 [W]

アクセス制御行列

• ドメイン毎に各資源にどの操作を許可するか

– ユーザ毎に各ファイルにどの操作を許可するか

• アクセス制御行列の要素a

ij

(ドメインi、資源j)

– アクセス許可なら１，制限なら０ – ユーザのファイル操作要求時に行列を検索 • ファイル保護エラー (Permission denied） – 行列が大きくなる, 殆ど0の疎行列 ファイル1 ファイル2 ファイル3 ファイル4 ファイル5 ファイル6 プリンタ1 プリンタ2 ドメイン1 読み 読み, 書き ドメイン2 読み 読み, 書き, _実行 読み, 書き 書き ドメイン3 読み, 書き, _実行 書き 書き ファイル6 [RWX] プリンタ2 [W] ファイル1 [R] ファイル2 [RW] ファイル3 [R] ファイル4 [RWX] ファイル5 [RW] プリンタ1 [W]

アクセス制御リスト

• ACL: access control list

• それぞれの資源毎に

– 許可するドメインと操作の組だけをリストにして保存 ファイル1: （D1, R） ファイル2: （D1, RW） ファイル3: （D2, R） ファイル4: （D2, RWX） ファイル5: （D2, RW） ファイル6: （D3，RWX） プリンタ1 : （D2，W），（D3,W） プリンタ2 : （D3, W） • ドメイン： ユーザ，グループの組 •

＊は任意（any）

ファイル1: (John, *, RW-) ファイル2: (*, admin, R--) ファイル3: (MIke staff, RWX) ファイル4: (John, *, ---), (*, staff, R--)

user group File 1 File 2 FIle 3 File 4

John admin RW- R-- --- ---staff RW- --- --- ---Mike admin --- R-- --- ---staff --- --- RWX R--2018/6/18 第10回 オペレーティングシステム 76 ファイル6 [RWX] プリンタ2 [W] ファイル1 [R] ファイル2 [RW] ファイル3 [R] ファイル4 [RWX] ファイル5 [RW] プリンタ1 [W]

ケーパビリティ

• capability

• ドメイン毎に権限の集合を保持

– OSが不正改竄に対して保護 ファイル6 [RWX] プリンタ2 [W] ファイル1 [R] ファイル2 [RW] ファイル3 [R] ファイル4 [RWX] ファイル5 [RW] プリンタ1 [W] 型 権限 対象 ファイル _R-- ファイル1へのポインタ ファイル _RW- ファイル2へのポインタ 型 権限 対象 ファイル _R-- ファイル3へのポインタ ファイル _RWX ファイル4へのポインタ ファイル _RW- ファイル5へのポインタ プリンタ _-W- プリンタ1へのポインタ 型 権限 対象 ファイル _RWX ファイル3へのポインタ プリンタ _-W- プリンタ1へのポインタ プリンタ _-W- プリンタ2へのポインタ ドメイン1 ドメイン2 ドメイン3 プロセスに適切な ケーパビリティを付与

ユーザクラスによる方法

• アクセスを許可・制限する対象の分類

– 所有者（owner） • ファイルを作成したユーザ – グループ • 特定のユーザ群 – 任意のユーザ

• ファイルごとに各ユーザクラスに対してアクセス許可・制限の

情報を保持

2018/6/18 第10回 オペレーティングシステム 78

UNIXのファイル保護

• ファイルごとにrwxrwxrwxの9bitの情報

userA% mkdir foo; touch foo/bar userA% ls -ld foo foo/bar

drwxr-xr-x 3 userA groupA 102 Feb 7 13:57 foo

-rw-r--r-- 1 userA groupA 0 Feb 7 13:57 foo/bar

userA% chmod o-r foo userA% ls -ld foo

drwxr-x--x 3 userA groupA 102 Feb 7 13:57 foo

guest% groups guest

guest% ls ~userA/foo

ls: /home/userA/foo/: Permission denied ; ディレクトリファイルの表示は不可

guest% cd ~userA/foo ; cdは許される（ディレクトリのxの意味） guest% ls

ls: .: Permission denied % ls -l bar

2018/6/18 80

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

第10回 オペレーティングシステム 例： • CD-ROMをマウント • USBメモリをマウント • VMからホストマシンのディスクをマウント

ファイル共有

• 複数の人によるファイル共有

• プロテクションがキーポイント

• ネットワーク上でのファイルを共有するためのシステ

– =分散ファイルシステム

– LANでは

• User-IDが一元管理されていることを想定 • UNIX系: Network File System (NFS)

– WANでは

• User-IDは一元管理できない