Operating System Lecture 11/7

Menu Menu

来週はお休みとします。

先週の復習

ガントチャート

軽量プロセス

軽量プロセスは、Threads または LWP (Light weight process )と呼ばれる、メモリ空間を切り替えない仮想プロセッサのみのプロセスである。これは仮想的に複数の計算の流れを実現する並行プログラム(Concurrrent Programming)を高速に実装することができる。最近のOSでは必ず採用されている重要な機能である。
Windows Win32 APIに Threads が含まれている
Mach Threads を採用したOSの元祖 C-Threads
Solaris Kernel Threads を実装している。Pthreads APIもある
BSD/OS Posix 準拠 PThreads を ユーザレベルで実装している
Java User level threads を VM により実装している
MP 前琉大講師の新城先生が実装したLWP
Threadsといってもさまざまな実装がある。
種類 実装 スケジュール
User level threads プロセス内部でCPUコンテキストを手動切り替えるライブラリを提供する 手動 non-preemptive
Kernel level threads OSのKernelによりthreadsを管理する Kernel によるpreemptive
Parallel threads Threadsを複数のCPUに割り当てる Kernel による
MachやSolarisではParallel Threadsが実装されている。BSD/OSでは User level threads が実装されている。User level threads では、sched_yeild()という関数により手動でthreadの切り替えを行う必要がある。

Process と Threads の使い分け

Process は、独立したメモリ空間を持つために、他のProcessの影響を受けにくい。しかし、Processの切り替えにはメモリ空間の切り替えを伴うために、複数の並行プログラムの同期、通信は一般的に遅い。したがって、Bufferring を中心としたThrourghput 優先のプログラムを行う必要がある (select/socket/pipe)Process は、他のプロセスにより実行の優先順位や、singalによる状態切り替えを行うことができる。

Threads は、一つのメモリ空間/Processの中に複数存在し、お互いの切り替えは関数呼び出しより若干重い程度で可能である。お互いの同期や通信もメモリを通して直接行うことができるので高速である。例えば、JavaやNetscapeで絵を動かす場合などに使うこともできる。しかし、User level threadsでは、外からのThreadsの制御をおこなうことはできない。

Threadsからは通常のライブラリ (libc など) を呼び出すことになるが、そのライブラリが固有の状態を持っていると、複数のThreadsから呼び出した時に不都合なことになる。そういう不都合が起きないライブラリを Re-entrant (自己再入可能)または、Threads safe という。printf は一般には Threads safeでないことが多い。また、I/O関係のライブラリもThreads safeでない場合がある。User level threads では、Re-entry は起きないので、このような問題は生じない。

Processのスケジューリングは、一般的におこなう必要があるためユーザが制御できる部分は限られている。しかし、Threadsでは、一つのプロセス内部に閉じているっため、その内部でのスケジューリングを自由に管理することができる。

Process Synchronization

複数のプロセス(process)は、単一のプロセッサ(Processor)、または、複数のプロセッサ上で動作している。このプロセスがおたがいに協調して動作するためには、なんらかの形で、プロセス同士のタイミングをとる必要がある。これを、プロセスの同期 (Sychronization)と呼ぶ。

何故、同期が必要なのか?
プログラムが、要求された仕様を満たすことを 整合(consistent) という。一般的な整合性(Consistency)は、並列に動作するプログラムが直列可能(Serializable)である場合にのみ得られる。並列環境下で直列可能性を保証するためには、同期機構が必要となる。(consitentの反対はinconsitent (矛盾)、従って、整合のことを無矛盾ともいう)
要求仕様の例

以下のような例を考えてみよう。 

    [操作A] 
    a = count;
    [操作B] 
    a += 1;
    [操作C] 
    count = a;
これを複数のユーザが同時に行うと困ったことが起きる。もちろん、プロセスの内部での実行順序はA,B,Cの順だが、それらはスケジューラによって分割されて、他のプロセスのA,B,Cと混じる(Interleaving)されることがある。 

    count は 256
    [操作A1]  by User 1
       count == 256
    [操作B1]  by User 1
       count == 256
    [操作C1]  by User 1
       count == 257
    [操作A2]  by User 2
       count == 257
    [操作B2]  by User 2
       count == 257
    [操作C2]  by User 2
       count == 258
もちろん、count は258になることが期待される。

問題

count が258以外になる操作の列を示せ。(これは、明らかにAやBが予期していたAが単独で操作ABCを行う結果とは異なる。)

同期は、いろいろなレベルで行われる。

これらはお互いに独立なわけではない。より高いレベルのものが、より低いレベルのものにより実装されるのが普通である。さまざまなレベルの同期機構を使っても、個々のレベルでの干渉がないことが保証される必要がある。しかし、それは自動的に保証されるわけではない。これらの機構のユーザが、それぞれを正しく使う必要がある。特に、低いレベルの実装はシステム全体のユーザに影響するので、完全なものである必要がある。

前の例の操作ABCのようなデータの変更のまとまりをというトランザクション(transaction)という。トランザクションは、それを順番にやったようになって欲しい。それが普通の直感である。この場合は、「1を加える」を2回おこなったのだから、2だけ値が増えてほしい。これを直列可能性(Serializability)という。 

 直列可能性が成立していれば、プログラムはトランザクション
の変更の積み重ねとなる。これは、トランザクションの積み重ねからプログラム全体ができていることを意味する。これをプログラムの無矛盾性(Consistency)という。ある条件のもとでConsistencyとSerializabilityは同値であることが証明されている。

これは、a1a2,b1b2 の二つのトランザクションが、s1→ s2の順序に依存するb1b2→ a1a2 という順序と、s2→ s3 によって生じるa1a2 → b1b2 という順序が矛盾していることから生じている。</P> 

 前の人の値を上書きしているという単純なことだが、このよう
に依存関係の矢印を書くことによって、より矛盾が明快になる。また、機械的に矛盾を見つける手順を提供することもできる。あたり前のことを明確にすることがコンピュータサイエンスでは重要なことが多い。

さまざまな同期機構

並列システムでは、Test-and-set または、read-modify-write というのが、ハードウェアレベルでは用いられている。これは、自分が書き込んだ値が相手に読まれることを保証している。これは、単なるatomic read, atomic write では実現できない。これらを用いて、Critical Section や Semaphor, Monitor を実現することができる。

逐次システム上の疑似並列システムでは、割り込まれない区間であるを作れば同期機構を作ることができる。これは、例えば割り込み禁止やcritical sectionにより実現する。

Test-and-set などでの待ち合わせは、CPUがそこを繰り返し読むことで行っても良い。これはspin-lockと呼ばれる。CPUを無駄に消費するが、同期待ちからの回復は、これが一番高速である。複数のCPUが、協調してspin-lock を行うのはBarrier と呼ばれる。これらの同期機構は、thread level で、並列プログラムのPerformance tuning を行う時に重要になる。

spin-lockでは無駄が大きくなる時には、プロセスを一旦、退避させる。この退避を抽象化した機構が、Semaphor である。Semaphor にはP動作とV動作がある。これは、Critical section へ入ることと出ることに相当する。さらに、これを Monitor という形でより柔軟な処理をおこなうことができる。Java などは言語レベルでCritical Section を採用している。(なぜ、Monitor を採用しなかったかは謎である) 並列オブジェクト指向言語では、オブジェクトをMonitor として扱う。

Guard は、lock や critical section などと異なり複数の条件を同時に待つことにより同期をおこなう。この機構は、より複雑な同期状況を実装するのにすぐれている。つまり表現能力が高い方法である。Unix の system call としては、select/listen というのがあり、これは一種の限られたGuradになっている。

通常プロセスでの共有資源

通常プロセスでの同期

Lock and Transaction

同期機構で実現したいのはConsistencyである。ただ、やみくもに同期機構を使ってもConsistencyは得られない。例えば、lock によって直列可能性を得るには、きまった方法によりlockをかける必要がある。一つのresource (資源)しかない場合には、lock は自明であるが、複数のresourceがある場合には、lock をかける順序を工夫する必要がある。この問題は、データベースの理論と同じ問題である。

Decd lock 閉塞

同期機構は、なんらかの待ちあわせを含む。この時に、いくつかのプロセスが相互に待ちあわせてしまうことがある。これをDeck lockという。

問題ある町のホテルの空室数をX、この町にいく飛行機の空席数をYとする。 以下のような操作を考えよう。

質問: さてSとTは、両方とも「飛行機の切符とホテルの予約」を取るというトランザクション(transaction)を実行したい。

一般的に複数のリソースを使うトランザクションでは、すべてをロックしてから処理をおこない、不要になったリソースからアンロックすることにより、矛盾を避けることができる。これを2 phase lock (2相ロック)という。しかし、2相ロックだけでは、デッドロックは、避けることはできない。

読みだしの場合は、複数のプロセスから読みだしがあってもよい。これを利用して並列度を上げることが考えられる。これを可能にするにはロックに段階をもうける。

shared lock どうしは、複数同時にかかる。しかし、exclusive lockは、shared lock , exclusive lock ともにlockする。

select/client/server

ロックは結構難しい概念なので、より簡単な方法として、クライアント・サーバモデルというのを使う場合がある。この場合は、サーバと呼ばれるプロセスを立ち上げ、サービスの要求はすべて、そこに転送される。サービスは要求が到着した順に処理される。この時に、Unix ではtcp socket とselect というシステム・コールによりメッセージの選択が行われる。

この方法では、メッセージの到着順序により整合性が保たれる。しかし、クライアント間の並列性がなくなるため、パフォーマンスは劣化する。

さらにこの欠点を緩和するために、サーバをマルチスレッド化することが行われている。この場合は、サーバ内部で同期機構をまた別に使う必要がある。同期機構としてはセマフォやロックが使われる。

アボート

多数のユーザがデータベースにアクセスする時に、2相ロックを使うとデータベースの矛盾を防ぐことができる。しかし、デッドロックは防ぐことができない。ロックするデータに順序付けをすればデッドロックは防ぐことができるが、平行実行の制限が大きくなるのと、データの順序づけが難しいので、あまり好まれない。

実際には、トランザクション一つにつきロックを一つだけとるような方法が簡単であり効果的だ。しかし、この方法は一度にたくさんのアクセスが来る場合には適さない。

もし、データのアクセス頻度が大きく、デッドロックは稀にしか起きないのならば、「取りあえずロックしていく。ロックがとれないようだったら、しばらく待って、あきらめる」という方法がある。(楽観的平行制御 Optimistic Concurrency Control)

この場合、あきらめたトランザクションは、今まで行った作業の取り消しをおこなう必要がある。これをトランザクションの アボート(abort)という。アボートは、ディスクアクセスなどに失敗した場合、その他、アプリケーションの都合によっても起きる。

例前の例題で、飛行機だけ予約が取れても、ほてるだけ予約が取れても、役にたたない。もし、それぞれの残りが一つの場合、SとTが飛行機とホテルを別々に予約できてしまう。(そして、お互いにキャンセル待ちに入る...) そうしないためには、飛行機とホテルをセットにすれば良かった。

セットにしない場合でも、飛行機とホテルの予約をとって、どちらかが取れなかったらアボートするという方法でも良い。この時にも、予約の順序を決めると、それぞれが一つづつ残っているのに誰も予約できなかったというようなこと防ぐことができる。

カスケーディングアボート

一つのトランザクションがアボートしたとする。もし、そのトランザクションのデータを他のトランザクションが使っていたとすると、そのトランザクションはだめになってしまう。つまり、そのトランザクションもアボートしなければならない。このようにアボートが連鎖的に起こることをカスケーディングアボート(Cascading Abort)という。

2相ロックを使っていれば、通常はロックによるアボートでは、カスケーディングアボートは起こらない。しかし、その他の要因によるアボートではカスケーディングアボートが無制限に起きる可能性がある。

これを防ぐには、2相ロックの解除を徐々にではなく、一度に行えば良い。(狭義の2相ロック)しかし、この方法もアクセス頻度が大きい場合には並列度を下げるので嫌われることが多い。

コミットとログ

アボートは、トランザクション自身が指示することもできる。SQL文では、という操作によって行う。

普通、データベースシステムは、どのトランザクションがコミットしたかを記録している。これはログ(log)と呼ばれる。 何もしなければログはどんどん大きくなっていく。カスケーディングアボートに備えるために、ずーとログを取っておかなくてはならないからである。

ある時点で、データベースの状態をとっておき、それを正規の状態と決めれば、その時点より前のログを取っておく必要はない。それはバックアップ(backup)と呼ばれる。バックアップの後は、明示的にトランザクションログを消さなくてはならないデータベースも多い。<P>

Unix には、sync というコミットに近い動作がある。これは、アプリケーションからは書き込みは終わっているが、OSはディスクにデータを書き込んでいない状態を解消する。したがって、Unix上のファイルシステムをもとにしたデータベースは本当の意味で安全になることはない。多くのデータベースではファイルシステムを経由せずに直接ディスクを操作することでこれを回避している。

Unixでのロック

宿題

C で書いたflock_test.c または、 Perlで書いた,flock_test.pl を 用いて、この授業のデッドロックを2相ロックで再現してみよ。また、2相ロックでない場合に矛盾が生じる例を示せ。(注) sleep などを使わないとうまくdead lock しないことがある。

宿題

「軽量プロセスの作成とスケジューリング」を、さ来週までに、おこなうこと。レポートはメールで 

    Subject: Practice on Operating System Lecture 11/7
というように、課題を出した日付をサブジェクトに入れたメールで提出して下さい。サブジェクトを間違えないこと!

宿題は毎週出るので提出が延びるとはまりますので気を付けてください。

Shinji KONO / Tue Nov 21 12:19:36 2000