オペレーティングシステム:信号量とパイプ

11127 ワード

第10章:信号量と管路
信号量信号量相互反発アクセス条件を用いた同期管路経典同期問題哲学者の食事問題読者-書く者問題
10.1信号量(Semaphore)
レビュー

同時問題マルチスレッド同時発生によるリソース競合

同期概念協調マルチスレッドによる共有データへのアクセスは、いずれの時点でも1つのスレッドのみが臨界領域コード

を実行する.

は、同期が正しい方法を保証する下位ハードウェアが高レベルのプログラミング抽象

をサポートすることを保証する.
しんごうりょう

信号量は、オペレーティングシステムが提供する共有リソースアクセスを調整する方法であるソフトウェア同期は、平等なスレッド間の同期交渉メカニズムであるオペレーティングシステムが管理者であり、プロセス用信号量でシステムリソースの数を表す

よりも高い地位にある.

Dijkstraが1960年代に提案した初期のオペレーティングシステムの主な同期メカニズムは現在はあまり使われていない(しかしコンピュータ科学研究では非常に重要である)

信号量は抽象的なデータ型であり、1つの整数(sem)変数と2つの原子動作からなる

である.

P()(Prolaag(オランダ語で減らそうと試みる))sem 1をsem<0のように減らし、待機に入ります.そうしないと

に続きます.

V()(Verhoog(オランダ語で増加))semプラス1 sem<=0のように、待機プロセス

を起動します.
しんごうりょうとくせい

信号量は、保護整数変数の初期化が完了すると、P()とV()の動作修正のみでオペレーティングシステムによって保証され、PV動作は原子動作

である.

P()はブロック可能であり、V()はブロックされない

は通常、信号量が「公平」であると仮定するスレッドが無期限にP()操作でブロックされないと仮定信号量が先進的な先頭に並ぶのを待つスピンロックは先進的な先頭に立たない.スピンロックはCPUを占有していつでも調べる必要があるため、臨界領域の使用者が退去したときに調べ終わったばかりで、次の侵入者が誰がそれを調べると

に入る可能性がある.
信号量の実現

ClassSemaphore {
    int sem;
    WaitQueue q;
} 

Semaphore :: P() {
    sem --;
    if (sem<0) {
        Add this thread t to q;
        block(P);
    }
}

Semaphore :: V() {
    sem ++;
    if (sem<=0) {
        Remove a thread t from q;
        wakeup(t);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

10.2信号量の使用

信号量分類は、2つの信号量バイナリ信号量に分けることができる:リソース数が0または1リソース信号量:リソース数が任意の非負の値

である.

両者の等価性は、1つに基づいて別の

を実現することができる.

信号量は、反発アクセス臨界領域の反発アクセス制御条件同期スレッド間のイベント待ち

を用いる.

は信号量で臨界領域の反発アクセス

を実現する.

//           ，    1
mutex = new Semaphore(1); //   
mutex -> P(); //         ， 1  0，   ；             ， 0  -1， P        
critical section;
mutex -> V(); //         ，  V  ，       -1  0，        ，                      
1
2
3
4

は、P()およびV()操作をペアで使用するP()操作に対して、相互反発アクセスを保証する必要がある.
信号量で条件同期を実現する
//条件同期信号量を設定し、初期値は0

condition = new Semaphore(0);

//  A                                 B

...M...
condition -> P();
...N... //                       ...X... //    
                                    condition -> v();
                                    ...Y...
1
2
3
4
5
6
7
8
9

条件待ち:スレッドAはスレッドBがXモジュールを実行するのを待ってからNモジュール仮定Bが先にXを実行するのを待っていなければならない.このとき信号量が1になると、Nは直接Aを実行してMを先に実行することができる.このとき信号量は-1になり、ブロックされ、待ち状態に入り、プロセスBはV操作を行い、解放される.このとき信号量は0である.信号量が0以下であると、スレッドが待機していることを示す、このとき待機中のスレッドAを起動し、Nモジュール

を実行する.
生産者-消費者問題
生産者→バッファ→消費者

境界バッファの生産者-消費者問題は、1つまたは複数の生産者がデータを生成した後に1つのバッファに配置する単一の消費者がバッファからデータを取り出す処理は、いつでも1つの生産者または消費者しかバッファ

にアクセスできないことを記述する.

問題解析いつでも1つのスレッドのみがバッファ(反発アクセス)を操作できる場合、消費者は生産者(条件同期)バッファが満タンになるのを待たなければならず、生産者は消費者(条件同期)

を待たなければならない.

は、各制約バイナリ信号量mutexリソース信号量fullBuffersリソース信号量emptyBuffers//信号量を信号量で記述する

を実現する.

CLass BoundedBuffer {
    mutex = new Semaphore(1);
    fullBuffers = new Semaphore(0);
    emptyBuffers = new Semaphore(n);
}                                   

BoundedBuffer :: Deposit(c) {
    emptyBuffer -> P();
    mutex -> P();
    Add c to the buffer;
    mutex -> V();
    fullBuffers -> V();
}

BoundedBuffer :: Remove(c) {
    fullBuffer -> P();
    mutex -> P();
    Remove c from buffer;
    mutex -> V();
    emptyBuffers -> V();
}

使用信号量の難読/開発コード比較困難プログラマは、信号量メカニズムを運用できるエラーが発生しやすい使用信号量が他のスレッドに占有されていることを必要とするデッドロック問題を処理できない

.
10.3管路(Monitor)

信号量が臨界領域を処理する際のいくつかの面倒を改善する

管路はマルチスレッド反発アクセス共有リソースのプログラム構造であり、オブジェクト向けの方法を採用し、スレッドの同期メカニズムを簡素化した.いずれの時点でも管理コードが1つしか実行されていない.管路中のスレッドは管理の反発アクセスを一時的に放棄することができ、イベントが発生すると注

を回復する.

スレッドは臨界領域で実行され、臨界領域の反発アクセスを放棄するには、臨界領域を終了するまで実行されなければならないが、管路は実行中に一時的に放棄することを許可する.放棄後、他のスレッドはスレッド領域

に入ることができる.
パイプストロークの使用

オブジェクト/モジュールにおいて、関連共有データ

が収集される.

管路は、ロック制御管路コードの反発アクセス

を構成する.

0個以上の条件変数0個は、臨界領域

に等しい.
共有データへの同時アクセスの管理

条件変数(Condition Variable)条件変数は、パイプ内の待機メカニズムがパイプに入るスレッドが、リソースが占有されて待機状態に入るため、各条件変数は、1つの待機キュー

に対応する待機原因を表す.

Wait()オペレーションは、待機キュー内で待機中または解放中の反発アクセス

を起動するように自身をブロックする.

Signal()オペレーションは、待機キュー内のスレッドを起動する待機キューが空である場合、等空オペレーション

を実行する.

//      
Class Condition {
    int numWaiting = 0;
    WaitQueue = q;
}

Condition :: wait(lock) {
    numWaiting ++;
    Add this thread t to q;
    release(lock);
    schedule();//need mutex
    require(lock);
}

Condition :: Signal() {
    if (numWaiting>0) {
        Remove a thread from q;
        wakeup(t);//need mutex
        numWaiting --;
    }   
}

生産者-消費者の問題をパイプで解決する

ClassBoundedBuffer {
    ...
    Lock lock;
    int count = 0;
    Condition notFull,notEmpty;
}

BoundedBuffer :: Deposit(c) {
    lock -> Acquire();
    while (count == n)
        notFull.Wait(&lock);
    Add c to the buffer;
    count ++;
    notEmpty.Signal();
    lock -> Release();
}

BoundedBuffer :: Remove(c) {
    lock -> Acquire(c);
    while (count == 0)
        notEmpty.Wait(&lock);
    Remove c from buffer;
    count --;
    notFull.Signal();
    lock -> Release();
}

管理条件変数の解放処理方式
ハンセン管路

l.acquire()
...
x.wait()    //T1    

            //T2        l.acquire()
                            ...
                            x.Signal()
                            ...
            //T1        l.release()

...         //T1      
l.release()

Hoare管路

l.acquire()
...
x.wait()    //T1    

            //T2        l.acquire()
                            ...
            //T2        x.Signal()

...         //T1      
l.release() //T1  

...         //T2      
l.release()

Hansen管路とHoare管路

Hansen管路は主に実際のオペレーティングシステムとJavaで現在実行中のスレッドの優先度がより効率的で、

を1回の切り替えが少ないために使用される.

Hoare管路内部のスレッド優先実行優先角度の考慮がより合理的であり、正確性の証明が容易である

Hansen管路とHoare管路の違い

Hansen-style：Deposit() {
    lock -> acquire();
    while (count == n) {        
        notFull.Wait(&lock);
    }
    Add thing;
    count ++;
    notEmpty.Signal();
    lock -> Release();
}

Hoare-style：Deposit() {
    lock -> acquire();
    if (count == n) {       
        notFull.Wait(&lock);
    }
    Add thing;
    count ++;
    notEmpty.Signal();
    lock -> Release();
}

10.4古典的な同期問題
(一)哲学者の食事問題

問題は、5人の哲学者が円卓を囲んでテーブルの上に5本のフォークを置いていることを説明しています.2人の哲学者の間に1本の哲学者を置く動作には、思考と食事をするときに左右のフォークを同時に手に入れる必要があることを含む.考えているときに、2本のフォークを元の場所に戻すには、哲学者たちの動作が秩序正しく行われることをどのように保証しますか.いつまでもフォークが手に入らない場合はありません.

案1

define N 5 //     
semaphore fork[5]; //      1
void philosopher(int i) //     ：0-4
    while (TRUE)
    {
        think(); //      
        P(fork[i]); //       
        P(fork[(i+1)%N]); //       
        eat(); //    
        V(fork[i]); //       
        V(fork[(i+1)%N]); //       
    }

正しくないと、デッドロック5人が同時に左フォークを手に入れた場合、デッドロック状態になる可能性があります

案2システム資源を十分に利用できないと、すべての資源を1つのパッケージにし、1つのプロセスだけがこのパッケージ全体の資源を占有することができ、それが必要かどうかにかかわらず、このような状況はシステムも正常に運行することができ、ただ効率が低い.

#define N 5 //     
semaphore fork[5]; //      1
semaphore mutex; //     ，   1
void philosopher(int i) //     ：0-4
    while (TRUE)
    {
        think(); //      
        P(mutex); //     ，                    
        P(fork[i]); //       
        P(fork[(i+1)%N]); //       
        eat(); //    
        V(fork[i]); //       
        V(fork[(i+1)%N]); //       
        V(mutex); //     
    }

反発訪問は正しいが、毎回1人しか食事が許されず、性能が悪い.

案3

#define N 5 //     
semaphore fork[5]; //      1
void philosopher(int i) //     ：0-4
    while (TRUE)
    {
        think(); //      
        if (i%2 == 0) {
            P(fork[i]); //       
            P(fork[(i+1)%N]); //       
        } else {
            P(fork[(i+1)%N]); //       
            P(fork[i]); //       
        }   
        eat(); //    
        V(fork[i]); //       
        V(fork[(i+1)%N]); //       
    }

デッドロックなしで複数の人が同時にアクセス可能
(二)読者-書き手問題

問題共有データを記述する2種類の利用者読者:データのみを読み出し、書き込みを変更しない:データを読み出し、変更する読者-書き込み者問題記述:共有データに対する読み書き

「読む-読む」は同一時刻を許容し、

を複数の読者が同時に読むことを許容する.

「読む-書く」は、書く者がいない場合に読者が読むことができ、読者がいない場合に書くことができる

を反発する.

「書く-書く」反発他の書く者がいない場合、書く者は

を書くことができる.
信号量で読者-ライターの問題を解決する
各コンストレイントを信号量で記述する

信号量WriteMutex制御読み書き動作反発初期化1

読者カウントRcountが読込動作中の読者数を0

に初期化する.

信号量CountMutex制御による読者カウントの反発修正を1

に初期化する.

//Writer

P(WriteMutex);
    write;
V(WriteMutex);

//Reader

P(CountMutex);
    if(Rcount == 0) //                 ，            1
        P(WriteMutex);
    ++ Rcount;
V(CountMutex);

read;

P(CountMutex);
    -- Rcount;
    if(Rcount == 0) //                    、
        V(WriteMutex);
V(CountMutex);

特徴:読者優先すなわち後の読者は必ず待っている書く者より先に書く操作

を行う.
読者-ライターの質問:優先ポリシー

読者優先戦略読者が読んでいる状態であれば、その後の読者は直接読者が入り続けるように、書く者は飢餓

にある.

執筆者優先戦略執筆者が準備ができている限り、執筆者はできるだけ早く執筆操作を実行しなければならない.
読者-ライターの問題をパイプで解決する
2つの基本的な方法

Database :: Read() {
    Wait until no writers;
    read database;
    check out - wake up waiting writers;
}

Database :: Write() {
    Wait until no readers/writers;
    write database;
    check out - wake up waiting readers/writers;
}

管路の状態変数

AR=0; //# of active readers
AW=0; //# of active writers
//     >0
WR=0; //# of waiting readers
WW=0; //# of waiting writers
//   >0

Lock lock;
Condition okToRead;
Condition okToWrite;

ソリューションの詳細:読者

AR=0; //# of active readers
AW=0; //# of active writers
WR=0; //# of waiting readers
WW=0; //# of waiting writers
Lock lock;
Condition okToRead;
Condition okToWrite;

Public Database :: Read() {
    //Wait until no writers;
    StartRead();
    read database;
    //check out - wake up waiting writers;
    DoneRead();
}

Private Database :: StartRead() {
    lock.Acquire();
    while ((AW+WW)>0) { //         
        WR++;
        okToRead.wait(&lock);
        WR--;
    }
    AR++;
    lock.Release();
}

Private Database :: DoneRead() {
    lock.Acquire();
    AR--;
    if ((AR==0 && WW)>0) { //         
        okToWrite.signal();
    }
    lock.Release();
}

ソリューションの詳細:ライター

AR=0; //# of active readers
AW=0; //# of active writers
WR=0; //# of waiting readers
WW=0; //# of waiting writers
Lock lock;
Condition okToRead;
Condition okToWrite;

Public Database :: Write() {
    //Wait until no readers/writers;
    StartWrite();
    write database;
    //check out - wake up waiting readers/writers;
    DoneWrite();
}

Private Database :: StartWrite() {
    lock.Acquire();
    while ((AW+AR)>0) { 
        WW++;
        okToWrite.wait(&lock);
        WW--;
    }
    AW++;
    lock.Release();
}

Private Database :: DoneWrite() {
    lock.Acquire();
    AW--;
    if (WW>0) { 
        okToWrite.signal();
    } else if (WR>0) {
        okToRead.broadcast();
    }
    lock.Release();
}

Luaプログラミング(八)協同プログラムの高度な使い方--生産者-消費者問題

STM学習ノート------W 25 Qxx