Реализация бинарного класса семафоров в C ++ - PullRequest
Новая
       7

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

1 голос
/ 24 марта 2012

Итак, я работаю над планировщиком в одном из моих классов. По сути, мы притворяемся, что одновременно может выполняться только один поток. Мы должны использовать класс семафоров, чтобы позволить этим потокам блокировать себя для имитации потока, ожидающего ЦП.

Проблема в том, что потоки, кажется, блокируются в неправильное время и выполняются в неправильное время. Мне было интересно, если мне не хватает некоторого концептуального понимания семафора и как его реализовать. Мне было интересно, могу ли я получить некоторые отзывы о моей реализации. Инструктор предоставил этот заголовочный файл, который я никак не изменил: 

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

Ответы [ 2 ]

9 голосов
/ 24 марта 2012

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

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

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

Исходная логика с добавленными блокировками (см. Другой ответ): 

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

...