Peterson's Nプロセスアルゴリズムを使用したセマフォーの実装

Question

次のステートメントのために私のコードにフィードバックが必要ですが、私は正しいパスですか？

問題文：

a。プライベートintと3つのパブリックメソッド（init、wait、signal）を持つセマフォークラスを実装します。 waitメソッドとsignalメソッドは、セマフォから期待どおりに動作する必要があり、実装にはPetersonのNプロセスアルゴリズムを使用する必要があります。

b。共有整数の値を同時に更新する5つのスレッドを作成し、パートa）で作成したセマフォクラスのオブジェクトを使用して同時更新の正確性を保証するプログラムを作成します。待ちループで回転させながら、あなたがミューテックスを解放する必要が

#include <iostream> 
#include <pthread.h> 

using namespace std; 

pthread_mutex_t mid;     //muted id 
int shared=0;       //global shared variable 
class semaphore { 
    int counter; 
public: 
    semaphore(){ 
    } 
    void init(){ 
     counter=1;      //initialise counter 1 to get first thread access 
    } 
    void wait(){ 
     pthread_mutex_lock(&mid);   //lock the mutex here 
     while(1){ 
      if(counter>0){    //check for counter value 
       counter--;    //decrement counter 
       break;     //break the loop 
      } 

     } 
     pthread_mutex_unlock(&mid);  //unlock mutex here 
    } 
    void signal(){ 
     pthread_mutex_lock(&mid);  //lock the mutex here 
      counter++;     //increment counter 
      pthread_mutex_unlock(&mid); //unlock mutex here 
     } 

}; 
semaphore sm; 
void* fun(void* id) 
{ 
    sm.wait();       //call semaphore wait 
    shared++;       //increment shared variable 
    cout<<"Inside thread "<<shared<<endl; 
    sm.signal();      //call signal to semaphore 
} 


int main() { 

    pthread_t id[5];     //thread ids for 5 threads 
    sm.init(); 
    int i; 
    for(i=0;i<5;i++)     //create 5 threads 
    pthread_create(&id[i],NULL,fun,NULL); 
    for(i=0;i<5;i++) 
    pthread_join(id[i],NULL);   //join 5 threads to complete their task 
    cout<<"Outside thread "<<shared<<endl;//final value of shared variable 
    return 0; 
} 

Answer 1

：

は、ここに私の作業プログラムです。

コンテキストスイッチが実行される前にスレッドが機能を実行する可能性が非常に高いため、各スレッドが終了する前に終了するため、テストが行​​われます。したがって、セマフォーには競合がありません。そうした場合、ミューテックスを持っている1人のウェイターが止まって、誰もカウンターにアクセスできず、スピナーを解放するのを防ぐことができます。

ここでは動作する例があります（初期設定の競合があり、散発的に正しく起動しない場合があります）。主にgcc組み込みのアトミック操作を使用しているため、より複雑に見えます。各コアには独自のキャッシュがあるため、複数のコアがある場合は常にこれらが必要です。カウンタのvolatileを宣言するだけで、コンパイラの最適化に役立ちます.SMPはキャッシュの一貫性のためにプロセッサ間キャッシュの無効化が必要なため、特別なプロセッサ命令を使用する必要があります。たとえば、次のように置き換えることができます。 counter ++とcounter-（そして 'shared'と同じ） - マルチコアCPU上でどう動かないか観察する。 （gcc原子操作の詳細については、https://gcc.gnu.org/onlinedocs/gcc-4.8.2/gcc/_005f_005fatomic-Builtins.htmlを参照してください）

#include <stdio.h> 
#include <pthread.h> 
#include <unistd.h> 
#include <stdint.h> 


class semaphore { 
    pthread_mutex_t lock; 
    int32_t counter; 
public: 
    semaphore() { 
     init(); 

    } 
    void init() { 
     counter = 1;   //initialise counter 1 to get first access 
    } 

    void spinwait() { 
     while (true) { 
      // Spin, waiting until we see a positive counter 
      while (__atomic_load_n(&counter, __ATOMIC_SEQ_CST) <= 0) 
       ; 

      pthread_mutex_lock(&lock); 
      if (__atomic_load_n(&counter, __ATOMIC_SEQ_CST) <= 0) { 
       // Someone else stole the count from under us or it was 
       // a fluke - keep trying 
       pthread_mutex_unlock(&lock); 
       continue; 
      } 
      // It's ours 
      __atomic_fetch_add(&counter, -1, __ATOMIC_SEQ_CST); 
      pthread_mutex_unlock(&lock); 
      return; 
     } 
    } 

    void signal() { 
     pthread_mutex_lock(&lock); //lock the mutex here 
     __atomic_fetch_add(&counter, 1, __ATOMIC_SEQ_CST); 
     pthread_mutex_unlock(&lock); //unlock mutex here 
    } 

}; 

enum { 
    NUM_TEST_THREADS = 5, 
    NUM_BANGS = 1000 
}; 

// Making semaphore sm volatile would be complicated, because the 
// pthread_mutex library calls don't expect volatile arguments. 

int shared = 0;  // Global shared variable 
semaphore sm;   // Semaphore protecting shared variable 

volatile int num_workers = 0; // So we can wait until we have N threads 


void* fun(void* id) 
{ 
    usleep(100000);     // 0.1s. Encourage context switch. 


    const int worker = (intptr_t)id + 1; 

    printf("Worker %d ready\n", worker); 

    // Spin, waiting for all workers to be in a runnable state. These printouts 
    // could be out of order. 
    ++num_workers; 
    while (num_workers < NUM_TEST_THREADS) 
     ; 

    // Go! 

    // Bang on the semaphore. Odd workers increment, even decrement. 
    if (worker & 1) { 
     for (int n = 0; n < NUM_BANGS; ++n) { 
      sm.spinwait(); 
      __atomic_fetch_add(&shared, 1, __ATOMIC_SEQ_CST); 
      sm.signal(); 
     } 
    } else { 
     for (int n = 0; n < NUM_BANGS; ++n) { 
      sm.spinwait(); 
      __atomic_fetch_add(&shared, -1, __ATOMIC_SEQ_CST); 
      sm.signal(); 
     } 
    } 

    printf("Worker %d done\n", worker); 

    return NULL; 
} 


int main() { 

    pthread_t id[NUM_TEST_THREADS]; //thread ids 

    // create test worker threads 
    for(int i = 0; i < NUM_TEST_THREADS; i++) 
     pthread_create(&id[i], NULL, fun, (void*)((intptr_t)(i))); 

    // join threads to complete their task 
    for(int i = 0; i < NUM_TEST_THREADS; i++) 
     pthread_join(id[i], NULL); 

    //final value of shared variable. For an odd number of 
    // workers this is the loop count, NUM_BANGS 
    printf("Test done. Final value: %d\n", shared); 
    const int expected = (NUM_TEST_THREADS & 1) ? NUM_BANGS : 0; 
    if (shared == expected) { 
     puts("PASS"); 
    } else { 
     printf("Value expected was: %d\nFAIL\n", expected); 
    } 

    return 0; 
}