Как реализовать семафор? Это реализация правильная или неисправная? - PullRequest
Новая
       19

Как реализовать семафор? Это реализация правильная или неисправная?

0 голосов
/ 14 июня 2019

Я хочу реализовать класс семафоров.И пользователь в stackoverflow отметил, что моя реализация не работает правильно.

Сначала я сделал это так: 

class sem_t {
    int count;
public:
    sem_t(int _count = 0) : count(_count) {};
    void up() {
        this->count++;
    }
    void down() {
        while (this->count == 0)
            std::this_thread::yield();
        this->count--;
    }
};

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

class sem_t {
    int count;
    std::mutex mutualExclusion;
public:
    sem_t(int _count = 0) : count(_count) {};
    void up() {
        this->mutualExclusion.lock();
        this->count++;
        this->mutualExclusion.unlock();
    }
    void down() {
                this->mutualExclusion.lock();
        while (this->count == 0)
            std::this_thread::yield();
        this->count--;
        this->mutualExclusion.unlock();
    }
};

Но в случае использования этого подхода при попытке отсоединить нить я получил сообщение о том, что мьютекс былуничтожен, пока занят, потому что один поток может удерживать мьютекс, а затем уступать, после чего поток отсоединяется и возникает ошибка (это решение нормально?).Затем я попытался изменить этот код и остановился на следующей конструкции: 

class sem_t {
    int count;
    std::mutex mutualExclusion;
public:
    sem_t(int _count = 0) : count(_count) {};
    void up() {
        this->mutualExclusion.lock();
        this->count++;
        this->mutualExclusion.unlock();
    }
    void down() {
        while (this->count == 0)
            std::this_thread::yield();
        this->mutualExclusion.lock();
        this->count--;
        this->mutualExclusion.unlock();
    }
};

Но я думаю, что это решение также является ошибочным, поскольку оно может привести к той же проблеме, что и первое решение.

* 1015Итак, какова правильная реализация? Хочу заметить, что я пытался реализовать с условной переменной , но я пытаюсь реализовать семафор без условной переменной , и если вы хотите предложить какое-то решение с условной переменной опишите, пожалуйста, как метод ожидания условной переменной работает.

[Редактировать]

Мой полный код с использованием самостоятельно реализованного семафора: 

#include "pch.h"
#include <iostream>
#include <vector>
#include <mutex>
#include <thread>
#include <chrono>

class sem_t {
    int count;
    std::mutex mutualExc;
public:
    sem_t(int _count = 0) : count(_count) {};
    void up() {
        mutualExc.lock();
        this->count++;
        mutualExc.unlock();
    }
    void down() {
        mutualExc.lock();
        while (this->count == 0) {
            mutualExc.unlock();
            std::this_thread::yield();
            mutualExc.lock();
        }
        this->count--;
        mutualExc.unlock();
    }
};

#define N 5
#define THINKING 0
#define HUNGRY 1
#define EATING 2

std::mutex mx;
std::mutex coutMX;
char philosopherState[N] = { THINKING };
sem_t philosopherSemaphores[N] = { 0 };

void testSetState(short i) {
    if (philosopherState[i] == HUNGRY && philosopherState[(i + 1) % N] != EATING && philosopherState[(i + N - 1) % N] != EATING) {
        philosopherState[i] = EATING;
        philosopherSemaphores[i].up();
    }
}

void take_forks(short i) {
    ::mx.lock();
    philosopherState[i] = HUNGRY;

    testSetState(i);
    ::mx.unlock();
    philosopherSemaphores[i].down();
}
void put_forks(short i) {
    ::mx.lock();
    philosopherState[i] = THINKING;

    testSetState((i + 1) % N);
    testSetState((i + N - 1) % N);
    ::mx.unlock();
}

void think(short p) {
    for (short i = 0; i < 5; i++) {
        coutMX.lock();
        std::cout << "Philosopher N" << p << " is thinking!" << std::endl;
        coutMX.unlock();
        std::this_thread::sleep_for(std::chrono::milliseconds(500));
    }
}
void eat(short p) {
    for (short i = 0; i < 5; i++) {
        coutMX.lock();
        std::cout << "Philosopher N" << p << " is eating!" << std::endl;
        coutMX.unlock();
        std::this_thread::sleep_for(std::chrono::milliseconds(500));
    }
}

void philosopher(short i) {
    while (1) {
        think(i);
        take_forks(i);
        eat(i);
        put_forks(i);
    }
}

int main()
{
    std::vector<std::thread*> threadsVector;
    for (int i = 0; i < N; i++) {
        threadsVector.push_back(new std::thread([i]() { philosopher(i); }));
    }

    std::this_thread::sleep_for(std::chrono::milliseconds(15000));

    for (int i = 0; i < N; i++) {
        threadsVector[i]->detach();
    }

    return 0;
}

Ошибка, которая возникает (возникает только при запуске программы в режиме выпуска или отладки в Visual Studio)

This error only occurs while running program in visual studio

The console when error occurs

1 Ответ

2 голосов
/ 14 июня 2019

Последняя попытка действительно неверна, поскольку может случиться так, что несколько потоков вызовут down одновременно, и все успешно пройдут 

    while (this->count == 0)
        std::this_thread::yield();

строки, и тогда все они уменьшат счетчик до возможного отрицательного значения.значение: 

    this->mutualExclusion.lock();
    this->count--;
    this->mutualExclusion.unlock();

Таким образом, проверка и обновление значения счетчика должны выполняться атомарно.

Если вы хотите сохранить занятый цикл, самый простой способ - просто вызвать unlock до выходаи lock после, поэтому сравнение и уменьшение будут выполняться под одной и той же блокировкой: 

void down() {
    this->mutualExclusion.lock();
    while (this->count == 0) {
        this->mutualExclusion.unlock();
        std::this_thread::yield();
        this->mutualExclusion.lock();
    }
    this->count--;
    this->mutualExclusion.unlock();
}

Также вы можете использовать std::unique_lock guard, который блокирует мьютекс в конструкторе и разблокирует в деструкторе, поэтому мьютексне будет случайно оставлен в заблокированном состоянии: 

void down() {
    std::unique_lock<std::mutex> lock(this->mutualExclusion);
    while (this->count == 0) {
        lock.unlock();
        std::this_thread::yield();
        lock.lock();
    }
    this->count--;
}

Чтобы справиться с ошибкой "muxed уничтожен во время занятости", вам нужно либо иметь флаг, чтобы остановить фоновые потоки, и ждать, пока они завершатся с joinof detach: 

#include <atomic>

...

std::atomic<bool> stopped{ false };

void philosopher(short i) {
    while (!stopped) {
        ...
    }
}

...

int main()
{
    ...

    stopped = true;
    for (int i = 0; i < N; i++) {
        threadsVector[i]->join();
    }
    return 0;
}

или, если вы действительно не хотите заботиться об освобождении статических ресурсов, вы можете позвонить std :: quick_exit вместо detach и return: 

int main()
{
    ...
    std::this_thread::sleep_for(std::chrono::milliseconds(15000));
    std::quick_exit(0);
}
...