Peterson의 N 프로세스 알고리즘을 사용하는 세마포어 구현

Question

다음 코드는 내 코드에 대한 피드백이 필요합니다. 올바른 경로에 있습니까?

문제 설명 :

a. private int와 세 개의 public 메소드 인 init, wait 및 signal을 가진 세마포어 클래스를 구현하십시오. wait 및 signal 메소드는 세마포어에서 예상대로 작동해야하며 구현시 Peterson의 N 프로세스 알고리즘을 사용해야합니다.

b. 동시 업데이트의 정확성을 보장하기 위해 공유 정수의 값을 동시에 업데이트하고 부분 a)에서 만든 세마포어 클래스의 객체를 사용하는 5 개의 스레드를 만드는 프로그램을 작성하십시오. 대기 루프에서 회전하는 동안이 뮤텍스를 해제 할 필요가

#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

:

여기 내 작업 프로그램입니다.

문맥 전환이 있기 전에 스레드가 그 기능을 실행할 확률이 매우 높으므로 테스트가 제대로 수행되기 때문에 각 스레드가 시작되기 전에 완료됩니다. 따라서 세마포어에 대한 논쟁은 없습니다. 그렇게했다면, 뮤텍스를 들고 돌아가는 한 웨이터와 붙잡혀 누군가가 카운터에 접근하지 못하게하고 회 전자를 놓지 못하게됩니다.

다음 예제는 작동하지만 (예 : 초기화 레이싱으로 인해 산발적으로 올바르게 실행되지 않을 수 있음) 작동하는 예제입니다. 주로 gcc에 내장 된 원자 연산을 사용하기 때문에 더 복잡해 보입니다. 이는 각 코어가 자체 캐시를 가지고 있기 때문에 하나 이상의 코어가있을 때마다 필요합니다. 카운터를 '휘발성 (volatile)'으로 선언하면 컴파일러 최적화에 도움이됩니다. SMP가 무엇인지에 대해서는 캐시 일관성을 위해서는 프로세서 간 캐시 무효화가 필요합니다. 이는 특별한 프로세서 명령어를 사용해야한다는 것을 의미합니다. 예를 들면 다음과 같이 교체 할 수 있습니다. 카운터 ++ 및 카운터 - ('공유'와 동일) - 멀티 코어 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; 
}