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 ))
となる。
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 則がよくわかるような図を書いてみよう。
問題5.1 Amdal 則を実測し可視化する
Amdahl 則の実装Process Synchronization
複数のプロセス(process)は、単一のプロセッサ(Processor)、または、複数のプロセッサ上で動作している。このプロセスがおたがいに協調して動作するためには、なんらかの形で、プロセス同士のタイミングをとる必要がある。これを、プロセスの同期 (Sychronization)と呼ぶ。
何故、同期が必要なのか?
プログラムが、要求された仕様を満たすことを 整合(consistent) という。一般的な整合性(Consistency)は、並列に動作するプログラムが直列可能(Serializable)である場合にのみ得られる。並列環境下で直列可能性を保証するためには、同期機構が必要となる。(consitentの反対はinconsitent (矛盾)、従って、整合のことを無矛盾ともいう)
要求仕様の例
- 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;これを複数のユーザが同時に行うと困ったことが起きる。もちろん、プロセスの内部での実行順序は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() を使って、エラーが出ないことを確認する。
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==1x を1にすれば成立するので f(x) はsatisfiable
述語 g(x) ≡ x*x < 0どうやっても成立しないので g(x) はunsatisfiable
述語 h(x) ≡ x*x >= 0x の値を何にしても成り立つので 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-coreinstall 方法
http://babelfish.arc.nasa.gov/trac/jpf/wiki/install/startant を使って build する。
Java PathFinder は Docker を使う方が良い。
問題5.2
PathFinder を使って、Thread を用いたプログラムが要求仕様を満たしていることを検証しよう。golang のモデル検査器があればそれを使っても良い。
Java のannotation
Thread Safety annotaion同期の階層的実装
同期は、いろいろなレベルで行われる。- 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は以下のような回路になっている。
さまざまな同期機構
並列システムでは、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になっている。
通常プロセスでの共有資源
- ファイル
- device
- socket
- mmap
- named pip
- shared memory
通常プロセスでの同期
- fork / wait
- flock, lockf, ioctl
- select
- SYS V IPC
- semaphor
- shared memory
- message
Lock and Transaction
同期機構で実現したいのはConsistencyである。ただ、やみくもに同期機構を使ってもConsistencyは得られない。例えば、lock によって直列可能性を得るには、きまった方法によりlockをかける必要がある。一つのresource (資源)しかない場合には、lock は自明であるが、複数のresourceがある場合には、lock をかける順序を工夫する必要がある。この問題は、データベースの理論と同じ問題である。