Implementieren einer binären Semaphor-Klasse in C++

Question

Also arbeite ich an einem Scheduler in einer meiner Klassen. Grundsätzlich geben wir vor, dass nur ein Thread gleichzeitig ausgeführt werden kann. Wir sollten eine Semaphor-Klasse verwenden, um es diesen Threads zu ermöglichen, sich selbst zu blockieren, um den Thread zu simulieren, der auf die CPU wartet.

Das Problem ist, die Threads scheinen zur falschen Zeit zu blockieren und zur falschen Zeit auszuführen. Ich habe mich gefragt, ob ich ein konzeptionelles Verständnis eines Semaphors vermisse und wie ich es umsetzen kann. Ich habe mich gefragt, ob ich ein Feedback zu meiner Implementierung bekommen könnte. Der Instruktor vorgesehen, um diese Header-Datei, die ich nicht in irgendeiner Weise geändert:

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(); 
}; 

Dies ist meine Implementierung mit Posix stuff:

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

Sie vernachlässigen den Mutex zu sperren.

Zweitens, was Sie hier haben, ist ein Zähl-Semaphor, kein binärer Semaphor. Ein binärer Semaphor hat nur zwei Zustände, und so eine variable bool geeignet ist:

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

Ihr Zählen Semaphor Algorithmus ist eine while-Schleife fehlt, und signalisiert das Semaphor unnötig.

Original-Logik, mit Schlössern hinzugefügt (siehe andere Antwort):

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(); 
} 

Der richtige Weg:

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); 
} 

Für Effizienz, sammelt Informationen darüber, ob innerhalb des Mutex zu signalisieren oder nicht, aber dann mache das Signal außerhalb des Mutex. Mutexe sollten so wenig Maschinenanweisungen wie möglich enthalten, da sie zu Konflikten führen und die Nebenläufigkeit verringern. Die Signaloperation kann Hunderte von Zyklen benötigen (Auslösung zum Kernel, um eine Warteschlangenmanipulation durchzuführen).

Sie müssen eine Schleife verwenden, wenn Sie auf eine Zustandsvariable warten, da es zu weckenden Wakeups kommen kann. Auch wenn Sie außerhalb des Mutex signalisieren, geht das Condition-Signal nicht immer zum "beabsichtigten" Thread. Zwischen dem unlock und dem signal kann sich ein Thread einklinken und P anrufen und den Mutex dekrementieren. Dann muss derjenige, der bei dieser Bedingung aufwacht, den Test neu bewerten, andernfalls wird er falsch fortfahren.