C++でバイナリセマフォークラスを実装する

Question

私は自分のクラスの一つでスケジューラーに取り組んでいます。基本的には、一度に実行できるスレッドは1つだけです。セマフォー・クラスを使用して、これらのスレッドがCPUを待っているスレッドをシミュレートするようにブロックすることができます。

問題は、間違ったタイミングでスレッドがブロックされ、間違ったタイミングで実行されているように見えることです。私は、セマフォの概念的な理解とそれを実装する方法が不足しているのだろうかと思っていました。私は私の実装についていくつかのフィードバックを得ることができるかどうか疑問に思っていた。インストラクターは、私がどのような方法で変更していない、このヘッダファイルを提供：

class Semaphore { 
private: 
    int    value; 
    pthread_mutex_t m; 
    pthread_cond_t c; 

public: 

    /* -- CONSTRUCTOR/DESTRUCTOR */ 

    Semaphore(int _val); 

    //~Semaphore(); 

    /* -- SEMAPHORE OPERATIONS */ 

    int P(); 
    int V(); 
}; 

これはPOSIXのものを使用して、私の実装です：あなたはmutexをロック無視されている

Semaphore::Semaphore(int _val){ 
    value = _val; 
    c = PTHREAD_COND_INITIALIZER; 
    m = PTHREAD_MUTEX_INITIALIZER; 
} 

int Semaphore::P(){ 
    if(value <= 0){ 
     pthread_cond_wait(&c, &m); 
    } 
    value--; 
} 

int Semaphore::V(){ 
    value++; 
    if(value > 0){ 
     pthread_cond_signal(&c); 
    } 
} 

Answer 1

。

第2に、バイナリセマフォではなく、カウントセマフォーです。バイナリセマフォは唯一の2つの状態があり、そのためbool変数が適切である：

class Semaphore { 
private: 
    bool   signaled; // <- changed 
    pthread_mutex_t m; 
    pthread_cond_t c; 

    void Lock() { pthread_mutex_lock(&m); }   // <- helper inlines added 
    void Unlock() { pthread_mutex_unlock(&m); } 
public: 

    /* -- CONSTRUCTOR/DESTRUCTOR */ 

    Semaphore(bool); 

    //~Semaphore(); 

    /* -- SEMAPHORE OPERATIONS */ 

    void P(); // changed to void: you don't return anything 
    void V(); 
}; 

のImpl：

// consider using C++ constructor initializer syntax. 

Semaphore::Semaphore(bool s){  // don't use leading underscores on identifiers 
    signaled = s; 
    c = PTHREAD_COND_INITIALIZER; // Not sure you can use the initializers this way! 
    m = PTHREAD_MUTEX_INITIALIZER; // they are for static objects. 

    // pthread_mutex_init(&m); // look, this is shorter! 
} 

void Semaphore::P(){ 
    Lock();    // added 
    while (!signaled){ // this must be a loop, not if! 
     pthread_cond_wait(&c, &m); 
    } 
    signaled = false; 
    Unlock(); 
} 

void Semaphore::V(){ 
    bool previously_signaled; 
    Lock(); 
    previusly_signaled = signaled; 
    signaled = true; 
    Unlock(); // always release the mutex before signaling 
    if (!previously_signaled) 
     pthread_cond_signal(&c); // this may be an expensive kernel op, so don't hold mutex 
} 

Answer 2

あなたのカウンティングセマフォアルゴリズムは、whileループを逃すと、不必要にセマフォを通知しています。

添加ロックとオリジナルロジック、（他の回答を参照）

int Semaphore::P(){ 
    Lock(); 
    if(value <= 0){ 
     pthread_cond_wait(&c, &m); 
    } 
    value--; 
    Unlock(); 
} 

int Semaphore::V(){ 
    Lock(); 
    value++; 
    if(value > 0){ 
     pthread_cond_signal(&c); 
    } 
    Unlock(); 
} 

正しい方法：効率について

int Semaphore::P(){ 
    Lock(); 
    while (value <= 0){ // not if 
     pthread_cond_wait(&c, &m); 
    } 
    // value is now > 0, guaranteed by while loop 
    value--; 
    // value is now >= 0 
    Unlock(); 
} 

int Semaphore::V(){ 
    Lock(); 
    int prior_value = value++; 
    Unlock(); 

    // E.g. if prior_value is 50, should we signal? Why? 

    if (prior_value == 0) // was not signaled previously, now is. 
     pthread_cond_signal(&c); 
} 

、ミューテックス内の信号するか否かについての情報を収集し、しかしミューテックスの外側で信号を出します。ミューテックスは、コンテンションを追加して同時実行を減らすため、できるだけ少ない機械命令で保持する必要があります。シグナル操作には数百回のサイクルが必要です（待ち行列の操作を行うためにカーネルに移動する）。

偽のウェークアップがある可能性があるため、条件変数を待つときにループを使用する必要があります。また、ミューテックスの外側に信号を送ると、条件信号が常に「意図された」スレッドに行くとは限りません。 unlockとsignalの間に、スレッドが入ってきてPを呼び出してミューテックスを減らすことができます。次に、条件で目を覚ますものがテストを再評価する必要があります。そうでない場合、テストが正しく行われません。