Реализация двоичного класса семафора в C++

Question

Итак, я работаю над планировщиком в одном из моих классов. В принципе, мы притворяемся, что за один раз может выполняться только один поток. Мы должны использовать класс семафора, чтобы позволить этим потокам блокировать себя, чтобы имитировать поток, ожидающий 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 материал:

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

Вы пренебрегаете заблокировать мьютекс.

Во-вторых, у вас есть счетный семафор, а не двоичный семафор. Бинарный семафор имеет только два состояния, и поэтому 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

Ваш алгоритм подсчета семафор отсутствует время цикла, и сигналы семафора без необходимости.

Оригинальная логика, с добавлением замков (см другой ответ):

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 и уменьшить мьютексы. Затем тот, который просыпается при условии, должен переоценить тест, иначе он будет действовать неправильно.