Operating System Lecture No.5

Menu


軽量プロセス (Thread)

軽量プロセスは、Threads または LWP (Light weight process )と呼ばれる、メモリ空間を切り替えない仮想プロセッサのみのプロセスである。仮想的に複数の計算の流れを実現することができる。メモリ空間の切替えがない分、並行プログラム(Concurrrent Programming)を高速に実現できる。
POSIX Thread 標準的なAPI
Java class Thread によるAPI

Threadは、時分割(Time Sharing)方式で実行される場合と、複数のCPUにThread が割り当てられて実行される場合がある。sched_yields() などを用いて、手動でThreadを切替えることも行われていた。

種類 実装 スケジュール
User level threads プロセス内部でCPUコンテキストを手動切り替えるライブラリを提供する 手動 non-preemptive
Kernel level threads OSのKernelによりthreadsを管理する Kernel によるpreemptive
Parallel threads Threadsを複数のCPUに割り当てる Kernel による

Thread は、他のAPI (システムコールや、データ構造)と干渉するので、注意して使用する必要がある。Thread での実行と両立するAPIを、Thread Safe と呼ぶことがある。


Amdahl 則

たくさん CPU があっても、並列化の度合が低いと、性能が上がらない。CPU が n 個あって、並列化の比率 P とする。実行時間t が、どれくらいになるか。

     T = t * (1-P) + t * P /n

になる。これの逆数*tをグラフにすると高速化率になる。

     T = t / (t * (1-P) + t * P /n )

P = 0 だと 1 で、P = 1 だと n (n倍の速度で動く)

例えば、n = 2,6,24 だと、

 plot [0:1] (1 / ( 1-x + x / 24  )),(1 / ( 1-x + x / 6  )),(1 / ( 1-x + x / 2  ))

となる。

Grapher


Process と Threads の使い分け

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

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

Threadsからは通常のライブラリ (libc など) を呼び出すことになるが、そのライブラリが固有の状態を持っていると、複数のThreadsから呼び出した時に不都合なことになる。そういう不都合が起きないライブラリを Re-entrant (自己再入可能)または、Threads safe という。

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

並列実行には、Pthread または OPen CL / Metal を使うことができる。

    https://developer.apple.com/metal/
    https://developer.apple.com/search/index.php?q=Open+CL

ここから、情報と例題を取れます。

プログラム言語上にはいろんなものが提案されてる。

    Package java.util.concurrent
    Posix Threads
    Scala
    Erlang


thread pool

Thread はプロセスと同じでスケジューラに入れなければならないので、Kernel が関与する。したがって 作成のコストはかなり高い。そこで、前もって決まった数の Thread を先に>作っておいて、それを再利用する。

CPUをフルに使用したければ CPUの数だけThreadを用意する。CPUの数よりも大きい数を用意してもオーバーヘッドが増えるだけになる。少なすぎると能力を生かせない。

I/O待ちが多いアプリケーションの場合はセッションの数だけ用意する。

golang は default で thread pool を使っている。golang を複数プロセスで使う場合は thread pool が干渉しないように注意する必要がある。


synchronized queue

作成してある Thread には Synchronized queue を使ってアクセスする。いろいろな種類があるので使い分けることになる。


multi-cast

同じような仕事を配るにはmulti-castを使用する。


Amdahl則

Amdahl 則があるので、恒常的に並列性を維持する必要がある。

Amdal 則がよくわかるような図を書いてみよう。

Amdal 則の図


問題5.1 Amdal 則を実測し可視化する

Amdahl 則の実装

Process Synchronization

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


何故、同期が必要なのか?

 

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

 

要求仕様の例

以下のような例を考えてみよう。ai はプロセスiに対してローカルでプロセス毎に別とする。count は、すべてのプロセスで共有されているとする。

    [操作A_i] 
    a_i = count;    
    [操作Bi] 
    a_i += 1;
    [操作C_i] 
    count = a_i;

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

    count は 256
    [操作A1]  by User 1    a1==256
       count == 256
    [操作B1]  by User 1    a1==257
       count == 256
    [操作C1]  by User 1    a1==257
       count == 257
    [操作A2]  by User 2    a2==257
       count == 257
    [操作B2]  by User 2    a2==258
       count == 257
    [操作C2]  by User 2    a2==258
       count == 258

もちろん、count は258になることが期待される。

    count は 256
    [操作A1]  by User 1    a1==256
       count == 256
    [操作A2]  by User 2    a2==256
       count == 256
    [操作B1]  by User 1    a1==256
       count == 256
    [操作C1]  by User 1    a1==257
       count == 257
    [操作B2]  by User 2    a2==256
       count == 257
    [操作C2]  by User 2    a2==257
       count == 257

この実行順序では、257 になってしまう。


直列可能性 Serializability

並列実行される動作の集りを考える。
    [操作A_i] 
    a_i = count;    
    [操作Bi] 
    a_i += 1;
    [操作C_i] 
    count = a_i;

この集りが、並列実行された時に、実行結果が、集りを個々に順々に実行したのと同じ結果になることを、直列可能実行と言う。直列可能実行が保証されるような集りを transaction と言う。

並列実行の結果、既に始めた transaction の直列可能性が保証されなくなったり、transaction の実行が出来なくなった時には、transaction の実行は取り消されることがある。abort あるいは、cancel と呼ばれる。

並列実行が可能な言語では、

    transaction begin;
    a_i = count;    
    a_i += 1;
    count = a_i;
    transaction end;

見たいな構文が用意されている言語もある。

直列可能な実行では、その順序にそって、要求仕様をtransactionの列が満たしていることを保証できる。


可能な実行

並行実行では個々の命令は任意の順列組合せで実行される。A1,B1,C1 の順序はそのままだが、これにA2,B2,C2がその順序で割り込む。

2次元の場合は以下のような状態遷移図で表される。3次元以上は複雑になってしまう。

組合せの数は、状態遷移の経路数で数えることができる。数えてみよう。n次元ではどうなるか?


直列可能でない場合と同期機構

transaction を実現する、直列可能な実行を実現するために同期機構が必要になる。

直列可能でない場合は、二つのtransacton を構成する操作の間に矛盾した順序がある。これを競合状態、Race condition と呼ぶこともある。

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

Java の例題では、一つのオブジェクトのメソッドを複数のThread から呼び出すという形で競合状態が起きる。

    class T1 {
	int count = 0;
	void work() {
	   count ++;
	}
    }
    thread t2 から t1.work();
    thread t3 から t1.work();

これで、もうダメ。

(1) work() を使って、エラーが(簡単には)出ないことを確認する。

(2) slow_work() を使って、エラーが出ることを確認する。

(3) work() のprintを有効にして、エラーが出るようになることを確認する。


Thread programming の特徴

なんでもない操作でも、thread から同時にアクセスするのは正しくない。

Thread 間の競合( race condition )によるエラーは再現性が低い。一見、ちゃんと動く。

print 文を入れるとバグが出なくなったりする。(print 文が serialize されているため)

正しく動くことを確認するのが難しい。


Atomic な操作

count++ は、一つの塊として処理させるように見える。(atomic)でも、実際は、

     movl count, %eax
     addl $1, %eax
     movl %eax, count

と言うような処理になっている。ここで、%eax は thread 毎にある。count は、共有されている。

Java の synchoronized を使った待ち合わせにより、直列可能な実行にすることが出来る。

C では、 __sync_fetch_and_add を使うことにより、atomic なincrement を可能にすることもできる。Java では、AtomicInteger を使う。

    class T1 {
	int count = 0;
	synchronized void work() {
	   count ++;
	}
    }
    thread t2 から t1.work();
    thread t3 から t1.work();

これでだいじょうぶ。

(4) sync_work() を使って、エラーが出ないことを確認する。

Mercurial のソース

hg clone ssh://urasoe.ie.u-ryukyu.ac.jp//home/hg/teacher/kono/os/ex/ThreadTest


テストと検証、要求仕様

[テスト] 特定のテストだけが動けば良い

[検証] 特定の性質を満たすことを、すべての場合で確認する

述語 f(x)
     ある性質を満たすかどうかを調べる関数、いくつか引数があるのが普通

論理式
     and, or, not などで述語を繋げた式

充足可能性 satisfiable
     性質を満たすことがある

非充足可能性 unsatisfiable
     常にその性質を満たさない

恒真性 valid
     常にその性質を満たす

    述語 f(x) ≡   x==1

x を1にすれば成立するので f(x) はsatisfiable

    述語 g(x) ≡   x*x < 0

どうやっても成立しないので g(x) はunsatisfiable

    述語 h(x) ≡   x*x >= 0

x の値を何にしても成り立つので h(x)は valid


モデル検証ツール

プログラムやプロトコルが、仕様を満たしているかどうかを調べるツール。

バグを調べるときには、バグを表す性質のsatisfiability を調べる。

バグがないことを調べるときには、バグを表す性質のunsatisfiability を調べる。

後者の方が一般的には難しい。

    SPIN 

    http://spinroot.com/spin/whatispin.html

    Java PathFinder 

    http://javapathfinder.sourceforge.net/

Java PathFinder は hg から取って来ること

    http://babelfish.arc.nasa.gov/hg/jpf/jpf-core

install 方法
    http://babelfish.arc.nasa.gov/trac/jpf/wiki/install/start

ant を使って build する。

Java PathFinder は Docker を使う方が良い。


Docker/JavaPathFinder/


問題5.2

PathFinder を使って、Thread を用いたプログラムが要求仕様を満たしていることを検証しよう。

golang のモデル検査器があればそれを使っても良い。

PathFinder の問題


Java のannotation

Thread Safety annotaion

同期の階層的実装

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

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

一番低レベルでは、共有資源(例えば、システムバス)に対するアクセスに対する同期機構が使われる。これは、Bus arbitor と呼ばれる。

例えば、一つの資源と二つの使用者に対するArbitorは以下のような回路になっている。


さまざまな同期機構

並列システムでは、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 をかける順序を工夫する必要がある。この問題は、データベースの理論と同じ問題である。


Shinji KONO / Fri Jan 12 13:39:47 2024