Distributed Operating Systems & Algorishms (by Chow, Johnson)
久野靖∗

2000.9.11

はじめに1.1□ 今学期のゼミ — Randy Chow, Theodore Johnson: Dis-

Evolution of Modern Operating Systems

tributed Operating Systems & Algorithms, Addison- □ OS →アプリケーションとハードウェアのインタフェースをとり、アプリケーションに「使いやすい環境」を提供
Wesley, 1997. (ISBN 0-201-49838-3)□ 内容 — 分散システム/分散 OS とそこに出て来るさまざ• プロセスの多重化、資源の管理、アクセス制御、エラー回復、ユザインタフェース

まな手法やアルゴリズムについて□ OS の構造→カーネルとシステムサービスに分けられる• 原理も実際も等しくカバー• 前半 (〜8 章) → OS のテキスト、後半 (9 章〜) →分散 OS のテキスト• カーネル→ハードウェアと接する部分• システムサービス→アプリケーションにサービスを提供する□ 本書の構成• ユーザから見ると OS は「仮想マシン」を提供する←

• 1〜2 章→基本概念

主たる目的• 3〜5 章→分散プロセス (同期、通信、スケジューリ• 管理者から見ると OS は「資源管理機構」に見える←ング)

目的のために必要• 6〜8 章→分散資源 (ファイルとメモリ)

ユーザ• 9〜13 章→さまざまな分散アルゴリズム

アプリケーションシステムサービス
カーネル

1

Operating System Fundamentals

ハードウェア□ 集中型 (centtralized)OS →単一システム (1CPU/マル□ 現代の計算機システム→高度化→ネットワーク、複雑なチ CPU) 上で稼働→その設計方法などはよく知られている

アプリ、分散計算□ WS、LAN の普及→

□ 本書ではそのようなシステムの基本技術 (特に分散 OS/• ネットワーク OS、分散 OS の出現

分散アルゴリズム) を学ぶ• 自 律 協 調 シ ス テ ム (cooperative autonomous□ 「分散システム」と「分散 OS」は違う意味。さらに様々system) の概念←分散アプリ、オープンシステム

なハードウェアアーキテクチャの違い→本章ではこれら□ 結合の疎/密さに注目した比較を整理

第１世代

第３世代

第４世代

第２世代

分散ＯＳ

自律協調システム

ネットワークＯＳ

結合が密結合が疎集中型
ＯＳ∗ 筑波大学大学院経営システム科学専攻

1• 結合が密/疎…プロセッサ間通信時間とプロセッサ内通信時間の比が小/大• ユーザは「自分がやりたいことができるれば」満足→透明性は必須ではない• 1 つの OS で全体を管理→密、複数 OS の協調→疎• ユーザはシステムが複数のマシンから成ることも、他のユーザがいることも知っている。

• 集中型 OS →ハード、ソフトとも密結合• 分散 OS(名前としてはよくない) →疎結合のハード上 □ 透明性に代って開放性 (openness) があればよい→無名
1 つの OS に見える性 (autonomy)• ネットワーク OS →別々のシステムがネット経由で• システムは多数のマシンから成る→自律性
通信• システムにとってもユーザは沢山いる→自律性• 自律協調→分散 OS から「単一制御」を取り払ったもの□ 現代の OS →これらすべての特性を統合□ 何を主要な機能/目標としているかという面から見ると分かりやすい。

1.2

分類

特性

集中型 OS

プロセス管理、メモリ管理、 資源管理、仮目標

IO 管理、ファイル管理

Centralized Operating System□ 集中型 OS の主要な機能

想マシンの提ネット

供 (仮想化)
遠隔アクセス、情報交換、 資源共有 (相ワーク OS
分散 OS

ネットワークブラウジング(ファイルシステム、ネーム互運用性)
単一システムスペース、時刻、計算資源として見える

自律協調の) 単一ビュー
オープンかつ協調的な分散システム

アプリケーション(透明性)
協調作業 (自律性)

要求管理機能シングル

UI、I/O 制御、割り込み、デバイスドラ

ユーザ
効 率 的イバ
仮想 I/O、スプーリング

I/O
大規模ア
プリ
マ ル チ

ョン
マルチプログラミング、TSS、スケジュー

ユーザ

リング、アクセス制御/保護、ファイル共有、並行制御□ 旧世代の OS →仮想化。最近の OS →相互運用、透明、自律性を追加

1.2.1□ ネットワーク OS →ネットワークでの通信→相互運用が• 伝統的な分割方法→垂直分割、水平分割□ 透明…仮想化とよく似ている□ 垂直分割→階層化→各レイヤはその 1 つ上/下とだけや何が違うか分かりますか?

りとりすればよい→システム構造が分かりやすくなる□ 透明と仮想化の違い:• 仮想化→利用者は「見たいものを見る」(例:□ 水平分割→モジュール化→機能ごとの分割など。現在で広いはオブジェクトを単位とするのがよい

メモリ空間)• 透明→利用者は「見たくないものを見ない」(例:
シンの境界)

Operating System Structure□ OS は大きなソフト→どのように構造化するかが重要

目標• しかし違う!

仮想記憶、ページング、セグメンテーシ□ さらに「ハードウェア依存部分の分離」という構造化もマ

重要□ 依存部分は「最小カーネル」として設計しシステムサー• 両方が備わっているのがベスト「見たいものだけを見れば済む」

ビスから分離• 最小カーネルだけ移植すればそのまま他のマシンへ□ 透明性はあればあるだけ望ましいか?

移せる2• 最小カーネルの典型的な機能→マルチプロセス、割り込み、デバイスドライバ、同期、IPC(Interprocess

各種アプリケーションソフト

Communication)ＡＰＩ□ カーネルの構造自体は単一 (Monolithic) カーネルが多拡張性指向

システムサービスい←効率がよい、カーネルの機能自体はなるべく小さくＳＰＩ（ＨＡＬ）してある (ホント?)

可搬性指向□ さらに C/S(client/server) 構造にするというのも良い方法

各種ハードウェアプラットフォーム• システムサービスを呼ぶのがサーバプロセスへの通□ 代表的なマイクロカーネル…Mach、OS/2、WindowsNT

信と同等 (メッセージパッシング)□ マイクロカーネルの上で動くサブシステム→各種の OS• システムの機能をサーバとして外に出しやすい環境を同時に提供可能• 分散 OS のモデルと整合する□ どこまでがシステムでどこからがアプリケーションかは

ＯＳ／２
クライアントＷｉｎ３２
クライアントＰＯＳＩＸ
クライアントＯＳ／２
サブシステムＷｉｎ３２
サブシステムＰＯＳＩＸ
サブシステム

曖昧
会計処理

文書処理

生産システムサブシステムプログラミング環境

ユティリティ

コンパイラ

システムサービス

ファイルシステム

カーネル

ＣＰＵ多重化、割り込み、デバイスドライバ、同期機構、プロセス間通信（ＩＰＣ）

ＤＢＭＳ

コマンド
インタプリタ
メモリ管理

Kernelmode

システムサービスＡＰＩ
objectsecurity
process local
virtualmanager reference manager procedure memory
monitorcall
manager

ライブラリ

ハードウェアを抽象化したカーネル

スケジューラ

User
mode

I/O
manager

Executives

アプリケーション

ハードウェアプラットフォーム• コンパイラはシステム?
• DBMS はシステム?

アプリ?

アプリ?

1.2.3 Management Functions• ユーザにとっては自分が使うサブシステム以下は全部システム□ OS は資源管理機構であると見ることもできる。資源→プロセサ/プロセス、メモリ、I/O、データ/ファイル

1.2.2• プロセス→複数のプログラム実行を (時間) 多重化+

Subsystem and Microkernel

同期、IPC□ OS のサービスが構築可能な最小限の汎用カーネル→マ• メモリ→複数プロセスの記憶領域を (空間) 多重化

イクロカーネル• API(application programming interface)□ 同 期 機 構 … さ ま ざ ま 。セ マ フォ、CCR(conditional→critical region)、モニタ、CSP、ランデブ、パス式、…

カーネルが提供するサービスのインタフェース

3 章でも出て来る• HAL(hardware abstraciton layer)
な い し
SPI(service provider interface) → プ ラット □ プロセス間通信→共有メモリと割り込み/メッセージパッシング
フォーム依存性を隠蔽する• システムサービス→各種の OS 機能を実現するのに十• 同期とプロセス間通信は密接に関連。メッセージを分な機能群同期に使える3□ プロセススケジューリング→ターンアラウンド、スルー

1.3

プットに影響• 2 種類のスケジューリング:

Network Operating Systems□ LAN で接続された WS →資源 (データやプログラム) を共静的スケジューリング

有したい→ネットワーク OS。相互運用性が目標(プライオリティベース)、動的スケジューリング (負 □ ネットワーク機能→階層構造に構成
荷分散等)• 通信サブシステム→トランスポートサービス→ピア□ I/O デバイスの管理← OS の重要な仕事の 1 つ
間 (アプリケーションレベル) 通信• 難しさ←本質的にハードウェア依存←デバイスドラ

アプリケーションプロセス

イバで吸収

アプリケーションプロセス

ファイルサービス• 抽象化した I/O →「記憶装置」(読む/書く機能のみを提供)• スプーリング、バッファリングなども提供 (spool →simaltaneous peripheral operation on-line)

local
file system

network
file system

devicemanagementtransport
servicedevicedrivers□ 代表的な/重要なデバイス→ハードディスク、ビットマッ□ デバイスの獲得/開放→デッドロックの心配

ファイルサービス
network
file system

local
file systemtransport
servicedevicemanagement

network
deviceservice KERNEL drivers

network
KERNEL service

ローカルハードウェア

プ端末

ピア
プロトコル

ネットワークローカルハードウェア□ OS の機能の一部はトランスポートサービスの上に実装(例:NFS)□ メモリ管理→主記憶の管理、仮想記憶機能の提供□ アプリケーションからのネットワークの利用形態→ソ• ページ方式 (固定長の単位)、セグメント方式 (論理ケット等の API的な単位)、両方併用• 仮想記憶→遅いディスクと速い主記憶を組み合わせ □ 各種のネットワークアプリケーションを含む→遠隔ログ
イン (仮想端末)、ファイル転送、電子メール/EDI、WWW、て「速くて大きな記憶領域」を実現←空間的/時間的遠隔実行
局所性の利用• 遠隔実行は強力だが危険性もある。遠隔実行で相手先ホストが同じ機種でない場合→スクリプトを解釈□ 共有メモリは古くから使われている共有手段。分散シス
テム上でこれを利用可能にするもの→分散共有メモリ

実行すれば大丈夫→ Java VM など□ ファイルシステム→「論理的な情報の単位」を提供→ディスク、メモリ、その他の I/O の上に構築可能

1.4• ファイルの機能→読み書き、共有、アクセス制御、並行制御

Distributed Operating Systems□ 多数の WS が高速な LAN でつながっている→それらの間での資源共有をもっと行いたい→個々のシステムを区別• 分散システムではしばしばファイルも分散化されてせず自律システムとして扱ういる→複数の複製の維持等、複雑な制御が必要□ 各種の資源が分散→それらを管理する機能も分散→分散□ OS の 4 つの機能 (プロセス、I/O、メモリ、ファイル) のアルゴリズムの必要性

うちで、分散システムで問題になるのはプロセスとファイル。あとの 2 つはローカルな管理なので以下では扱わ □ 分散 OS の重要な目標→透明性 (位置透明、並行透明)ない。

• これらを実現するのにも分散アルゴリズムが必要

4

1.5

Cooperative Autonomous Systems

1.6□ マルチユーザシステムを一人のユーザの視点ではなくDistributed Algorithms□ 分散システムの実現→分散アルゴリズムが必要→何が難

全体としての視点から見る→各プロセスは自律的に動作しいか?

し、互いに情報を交換し合いながら計算を進めて行く□ 広域的に共有された情報がない、通信には必ず遅延□ 分散システムでは「1 つの OS」を複数のノードに分けて• 特に広域クロックがない→近似的な時刻の共有、イ実現。自律協調システムでは複数ノードの協調動作が全ベントの順序を保つのにも手間が必要

体としてシステムを構成• これらの時刻や順序づけの上に立ってさまざまな機能を実現□ 故障からの回復/信頼できない通信への対処も重要な課題• このため、集中型システムのアルゴリズムそのまま
では駄目• 2 つの方向→分散アルゴリズム、集中アルゴリズム+故障回復
分散システムへの分解□ 例:

協調システムへの統合□ ネットワークトポロジの影響、データの複製の管理なども

不動産の取り引き通信路□ 分散アルゴリズムの特徴

イエローページ• メッセージパシング→共有メモリがないのですべてメッセージで情報交換しなければならない

サーバ
サーバ

• 広域情報がない→合意プロトコルによって合意を形成する必要

不動産会社
営業員

営業員

買い手

新聞

売り手

クライアント

著名なサーバ• 重複化→データは複製されているかも→その整合性を管理• 故障とその回復→冗長な情報を保持しておき、故障が起きた場合でも必要な情報を回復できるようにする

クライアント□ OS の進化…集中→ネットワーク→分散→自律協調• クライアントは各種のサーバに以来して目的を達成する• 目標…仮想化→相互運用→透明→自律性• 必要な情報を発見するには「著名なサーバ」を介する□ OS の各種技術• サーバのなかにはブローカとして働くものもある□ OS の教科書□ ネットワークの巨大化→全体を 1 つとして動かすのでは□ 分散 OS の教科書

なく、個々の要素が自律的に協調し合いながら作業を進□ 分散アルゴリズムの教科書

めて行く方があっている□ CORBA などのミドルウェア、ORB(ブローカ、トレーダ) □ その他…各種 OS、CORBA、WWW、Java などがサービスを仲介

5