Operating System Lecture No.5

軽量プロセス (Thread)

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 則

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

     T = t / (t * (1-P) + t * P /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 の使い分け

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

multi-cast

Amdahl則

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

Amdal 則の図

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

Process Synchronization

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

• login_count = login_count + 1 で、これをn回繰り返したら、login_count は n 増加する。
• 周辺LSIのC0レジスタに、10byteのコマンドを逐次書き込む
• 預金口座の入金-出金は、残高に等しい
• すべてのプロセスが終了した後に、コマンドaを実行する

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

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

    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 は 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

直列可能性 Serializability

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

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

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

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

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

可能な実行

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

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

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

直列可能でない場合は、二つの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 間の競合( race condition )によるエラーは再現性が低い。一見、ちゃんと動く。

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

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

Atomic な操作

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

     movl count, %eax
     addl $1, %eax
     movl %eax, 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

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

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

モデル検証ツール

バグを調べるときには、バグを表す性質の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

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

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

Docker/JavaPathFinder/

問題5.2

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

PathFinder の問題

Java のannotation

同期の階層的実装

• Hardware level
  • read-modify-write
  • disable interrupt (割り込み禁止)
  • bus arbitration
  • switching network
• Memory level
  • read-modify-write
  • spin-lock
• thread level, kernel level
  • semaphor
  • critical-section
  • schedular
  • barrier
  • fuzzy barrier
• programming language level
  • monitor
  • guard
  • trigger
  • message passing
• process level
  • lock
  • select
  • wait
  • read-wait

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

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

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

さまざまな同期機構

逐次システム上の疑似並列システムでは、割り込まれない区間であるを作れば同期機構を作ることができる。これは、例えば割り込み禁止や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になっている。

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

• ファイル

• device

• socket

• mmap

• named pip

• shared memory

通常プロセスでの同期

• fork / wait

• flock, lockf, ioctl

• select

• SYS V IPC
  • semaphor
  • shared memory
  • message

Lock and Transaction