Как разрешить нескольким потокам доступ к критическому разделу, который соответствует условию в C ++

Question

! [Railroad]: http://www.cs.tut.fi/~rinn/htyo/design/pics/railroad.png

Я пытаюсь создать программное обеспечение для моделирования поездов, едущих по железной дороге, как показано выше.Проблемы параллелизма проистекают из следующих граничных условий:

* Каждый участок пути является ОДНЫМ ВРЕМЯ за один раз: когда поезд начинает идти в одном направлении, не может быть никаких других поездов, идущих в противоположном направлении (примечание: это позволяет использовать несколько поездов в одном и том же направлении).

* Когда поезд начался на участке, он ДОЛЖЕН перейти к следующему участку / перекрестку (другими словами: в середине участка пути нет разворота)

* Поезда НЕ должны иметь определенного расписания (их общее движение может быть случайным во всей сети треков).

* Места обмена / переключения путей могут быть «волшебными» вощущение, что любое количество поездов может находиться на них (в ожидании), все поезда могут проходить друг в друга в любом направлении внутри них.

Мой план состоял бы в том, чтобы создать 2 переменные, одна из которых содержала бы текущее направление движения поездов на пути, а вторая - подсчет количества поездов на пути.Идея состоит в том, чтобы сначала проверить, разрешено ли поезду входить на путь (другими словами, направление на пути == направление отходящего поезда ИЛИ, если путь пуст), а затем увеличить количество поездов на пути.Когда последний поезд на пути прибудет к следующему перекрестку, переменная направления будет установлена ​​на 0, что позволит любым поездам получать доступ к пути.

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

В случае, если это полезно, вот реализация до сих пор: railroad.cc

#include <chrono>
#include <thread>
#include <iostream>
#include <mutex>
#include <atomic>
#include "railroad.hh"


std::atomic_int lock = 0;
std::mutex cout_mutex;
Railroad::Railroad(std::vector<Track> tracks, std::vector<int> junctions, std::vector<Train> trains):
    tracks(tracks), junctions(junctions), trains(trains)
{

}

bool Railroad::moveTrain(int id)
{
    for(int i = 0; i < 10; i++){
        std::this_thread::sleep_for(std::chrono::milliseconds(std::rand()%300));
        bool finished = false;
        int target_id = rand()%6;
        int start;
        for(auto train_it = trains.begin(); train_it != trains.end(); train_it++){
            if(finished){
                break;
            }
            if(train_it->getId() == id){
                start = train_it->getLocation();
                train_it->setMoving(true);
                for(auto track_it = tracks.begin(); track_it != tracks.end(); track_it++){
                    if(track_it->id == target_id){
                        finished = true;
                        if(start == track_it->point2){
                            track_it->in_use == true;
                            cout_mutex.lock();
                            std::cout << "Train " << id
                                      << " started moving on track "
                                      << target_id << std::endl;
                            cout_mutex.unlock();
                            std::this_thread::sleep_for(std::chrono::milliseconds(std::rand()%1000));
                            train_it->setLocation(track_it->point1);
                            train_it->setMoving(false);
                            cout_mutex.lock();
                            std::cout<< "Train " << id << " has arrived from "
                                     << start << " to " << track_it->point1
                                     <<std::endl;
                            cout_mutex.unlock();
                            break;
                        }
                        else if(start == track_it->point1){
                            track_it->in_use == true;
                            cout_mutex.lock();
                            std::cout << "Train " << id << " started moving on track "
                                      << target_id << std::endl;
                            cout_mutex.unlock();
                            std::this_thread::sleep_for(std::chrono::milliseconds(std::rand()%1000));
                            train_it->setLocation(track_it->point2);
                            train_it->setMoving(false);
                            cout_mutex.lock();
                            std::cout<< "Train " << id << " has arrived from " << track_it->point1 << " to " << track_it->point2 <<std::endl;
                            cout_mutex.unlock();
                            break;
                        }
                        else{
                            cout_mutex.lock();
                            std::cout<< "Train " << id << " cannot access "<<track_it->id << std::endl;
                            cout_mutex.unlock();
                            break;
                        }
                    }
                }
            }
        }
    }
}

main.cpp

#include <iostream>
#include <memory>
#include <random>
#include <thread>
#include "railroad.hh"


using namespace std;

int main()
{
    std::vector<Track> tracks;
    tracks.push_back({0,0,2, false});
    tracks.push_back({1, 2, 3, false});
    tracks.push_back({2, 3, 0, false});
    tracks.push_back({3, 0, 1, false});
    tracks.push_back({4, 1, 2, false});
    tracks.push_back({5, 1, 3, false});

    std::vector<int> junctions;
    std::vector<Train> trains;

    trains.push_back({0,0,false});
    trains.push_back({1,1,false});
    trains.push_back({2,2,false});
    junctions.push_back(0);
    junctions.push_back(1);
    junctions.push_back(2);
    junctions.push_back(3);
    Railroad* railroad = new Railroad(tracks, junctions, trains);

    std::thread t1(&Railroad::moveTrain,railroad,0);
    std::thread t2(&Railroad::moveTrain,railroad,1);
    std::thread t3(&Railroad::moveTrain,railroad,2);


    t1.join();
    t2.join();
    t3.join();
}

Answer 1

По сути, вы хотите, чтобы поезд, который стремится войти на конкретную колею, ждал, пока на ней не останется ни одного поезда, либо направление всех поездов на коле совпадает с направлением движения вашего поезда. Один из способов решить эту проблему - использовать std :: condition_variable . Переменная условия позволяет блокировать поток до тех пор, пока конкретное условие не станет истинным (отсюда и название). Для каждого трека у вас есть счетчик, подсчитывающий количество поездов на пути. Вы можете использовать либо отдельную переменную, либо просто знак счетчика, чтобы отслеживать текущее направление на дорожке (например, против часовой стрелки считается положительным, по часовой стрелке отрицательным). Всякий раз, когда поезд хочет войти в путь, он проверяет, равен ли счетчик нулю или направление совпадает с направлением, в котором он хочет идти. Если это не так, он ждет, когда это условие станет истинным. Поскольку счетчик может быть изменен одновременно, доступ к счетчику должен быть заблокирован мьютексом. Вы приобретаете мьютекс и проверяете счетчик. Если счетчик таков, что вы можете войти в трек, вы обновляете счетчик, разблокируете мьютекс и продолжаете. Если счетчик таков, что вы не можете в данный момент ввести дорожку, вы вызываете wait для вашей условной переменной. При вызове wait вы должны передать блокировку, которую вы сейчас удерживаете. Операция ожидания над условной переменной атомарно переводит ваш поток в спящий режим и освобождает мьютекс, так что другие потоки могут делать что-то со счетчиком в это время (в противном случае условие никогда не станет истинным). Всякий раз, когда поезд покидает путь, он захватывает блокировку, обновляет счетчик и, если это был последний поезд, который должен выйти, уведомляет переменную условия. Эта операция уведомления активирует все потоки, ожидающие в настоящее время переменную условия. В каждом из этих потоков ожидающий вызов, заблокированный потоком, будет повторно запрашивать мьютекс и возвращаться. Таким образом, потоки, один за другим, снова проверяют, выполняется ли условие, которого они ожидали, в настоящее время. Если да, они могут продолжить, если нет, они продолжают ждать.

Вероятно, было бы лучше всего инкапсулировать все это в классе, например:

#include <mutex>
#include <condition_variable>

enum class Direction
{
    CCW = 1,
    CW = -1
};

class Track
{
    int counter = 0;

    std::mutex m;
    std::condition_variable track_free;

    static int sign(Direction direction)
    {
        return static_cast<int>(direction);
    }

    bool isFree(Direction direction) const
    {
        return (sign(direction) > 0 && counter >= 0) || (sign(direction) < 0 && counter <= 0);
    }

public:
    void enter(Direction direction)
    {
        std::unique_lock lock(m);

        while (!isFree(direction))
            track_free.wait(lock);

        counter += sign(direction);
    }

private:
    bool release(Direction direction)
    {
        std::lock_guard lock(m);
        counter -= sign(direction);
        return counter == 0;
    }

public:
    void exit(Direction direction)
    {
        if (release(direction))
            track_free.notify_all();
    }
};

и тогда ваши поезда просто звонят, например,

track.enter(Direction::CW);

для ввода трека и

track.exit(Direction::CW);

когда они уходят & hellip;