Eine Semaphor-Implementation mit Petersons N-Prozess-Algorithmus

Question

Ich brauche Feedback zu meinem Code für folgende Aussage, bin ich auf dem richtigen Weg?

Problemstellung:

a. Implementieren Sie eine Semaphor-Klasse mit einem privaten int und drei öffentlichen Methoden: init, wait und signal. Die Warte- und Signalmethoden sollten sich wie von einem Semaphor erwartet verhalten und müssen bei ihrer Implementierung den Petersonschen N-Prozessalgorithmus verwenden.

b. Schreiben Sie ein Programm, das 5 Threads erstellt, die gleichzeitig den Wert einer gemeinsamen Ganzzahl aktualisieren, und verwenden Sie ein Objekt der Semaphor-Klasse, das in Teil a) erstellt wurde, um die Korrektheit der gleichzeitigen Aktualisierungen sicherzustellen.

Hier ist mein Arbeitsprogramm:

#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

Sie müssen den Mutex freizugeben, während in der Warteschleife zu drehen.

Der Test passiert, weil die Threads sehr wahrscheinlich ihre Funktionen von Anfang bis Ende ausführen, bevor es einen Kontextwechsel gibt, und damit jeder beendet, bevor der nächste überhaupt startet. Sie haben also keine Konkurrenz über den Semaphor. Wenn Sie das täten, blieben sie bei einem Kellner stehen, der sich mit angehaltenem Mutex drehte, sodass niemand auf den Zähler zugreifen und den Spinner freigeben konnte.

Hier ist ein Beispiel, das funktioniert (obwohl es immer noch ein Initialisierungsrennen hat, das sporadisch nicht korrekt gestartet wird). Es sieht komplizierter aus, hauptsächlich deshalb, weil es die eingebauten atomaren Operationen des gcc verwendet. Diese werden benötigt, wenn Sie mehr als einen einzelnen Kern haben, da jeder Kern seinen eigenen Cache hat. Die Deklaration der Zähler 'volatile' hilft nur bei der Compiler-Optimierung - für das, was effektiv SMP ist, erfordert die Konsistenz des Caches eine prozessübergreifende Cache-Ungültigkeit, was bedeutet, dass spezielle Prozessoranweisungen verwendet werden müssen. Sie können versuchen, sie durch z.B. counter ++ und counter-- (und dasselbe für 'shared') - und beobachten, wie es auf einer Multi-Core-CPU nicht funktioniert. (Für weitere Details über die gcc atomare Ops, siehe 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; 
}