Simulation of traffic scheduling on a crossroad with multiple threads (OS lab)

traffic.cpp

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <unistd.h>
#include <pthread.h>
#include <algorithm>
// #define TEST_OUTPUT

using std::deque;
#ifdef TEST_OUTPUT
pthread_mutex_t outputLock;
#endif

// Base class entrance
// Entrances of the road is modeled with this class
// Derivants of the class must be singleton
class Entrance {
public:
    // Entrance mutexes
    pthread_mutex_t mutex;
    // Entrance mutex for cond
    pthread_mutex_t condMutex;
    // Conditions for changes of the waiting queue
    pthread_cond_t changes;
    // Queue of cars waiting for their turn to head towards a direction
    deque<int> waitingCars;
protected:
    Entrance() {
        pthread_mutex_init(&mutex, NULL);
        pthread_mutex_init(&condMutex, NULL);
        pthread_cond_init(&changes, NULL);
    }
};

class NorthEntrance: public Entrance {
private:
    static Entrance *instance;
    NorthEntrance(): Entrance() {}
public:
    static Entrance &getInstance() {
        if(instance) return *instance;
        instance = new NorthEntrance();
        return *instance;
    }
};
Entrance *NorthEntrance::instance = NULL;

class WestEntrance: public Entrance {
private:
    static Entrance *instance;
    WestEntrance(): Entrance() {}
public:
    static Entrance &getInstance() {
        if(instance) return *instance;
        instance = new WestEntrance();
        return *instance;
    }
};
Entrance *WestEntrance::instance = NULL;

class SouthEntrance: public Entrance {
private:
    static Entrance *instance;
    SouthEntrance(): Entrance() {}
public:
    static Entrance &getInstance() {
        if(instance) return *instance;
        instance = new SouthEntrance();
        return *instance;
    }
};
Entrance *SouthEntrance::instance = NULL;

class EastEntrance: public Entrance {
private:
    static Entrance *instance;
    EastEntrance(): Entrance() {}
public:
    static Entrance &getInstance() {
        if(instance) return *instance;
        instance = new EastEntrance();
        return *instance;
    }
};
Entrance *EastEntrance::instance = NULL;

// Abstract base class Road
// Road's derivants must be a singleton
class Road {
public:
    // Car mutexes
    pthread_mutex_t mutex;
    // Mutex for the condition
    pthread_mutex_t condMutex;
    // Conditions for changes of the queue
    pthread_cond_t changes;
    // Show which car is occupying the road
    int car;
    bool isBusy() {return !!car;}
    // Queue of cars waiting for the road's occupation
    deque<int> waitingCars;
    virtual bool findDeadlock() = 0;
protected:
    Road(): car(0) {
        pthread_mutex_init(&mutex, NULL);
        pthread_cond_init(&changes, NULL);
    }
};

class RoadA: public Road {
private:
    static Road *instance;
    RoadA(): Road() {}
public:
    static Road &getInstance() {
        if(instance) return *instance;
        instance = new RoadA();
        return *instance;
    }
    // Override
    bool findDeadlock();
};

class RoadB: public Road {
private:
    static Road *instance;
    RoadB(): Road() {}
public:
    static Road &getInstance() {
        if(instance) return *instance;
        instance = new RoadB();
        return *instance; 
    }
    // Override
    bool findDeadlock();
};

class RoadC: public Road {
private:
    static Road *instance;
    RoadC(): Road() {}
public:
    static Road &getInstance() {
        if(instance) return *instance;
        instance = new RoadC();
        return *instance; 
    }
    // Override
    bool findDeadlock();
};

class RoadD: public Road {
private:
    static Road *instance;
    RoadD(): Road() {}
public:
    static Road &getInstance() {
        if(instance) return *instance;
        instance = new RoadD();
        return *instance; 
    }
    // Override
    bool findDeadlock();
};

// Definitions of the class members
Road *RoadA::instance = NULL;
bool RoadA::findDeadlock() {
    return RoadB::getInstance().isBusy()
        && RoadC::getInstance().isBusy()
        && RoadD::getInstance().isBusy();
}

Road *RoadB::instance = NULL;
bool RoadB::findDeadlock() {
    return RoadA::getInstance().isBusy()
        && RoadC::getInstance().isBusy()
        && RoadD::getInstance().isBusy();
}

Road *RoadC::instance = NULL;
bool RoadC::findDeadlock() {
    return RoadA::getInstance().isBusy()
        && RoadB::getInstance().isBusy()
        && RoadD::getInstance().isBusy();
}

Road *RoadD::instance = NULL;
bool RoadD::findDeadlock() {
    return RoadA::getInstance().isBusy()
        && RoadB::getInstance().isBusy()
        && RoadC::getInstance().isBusy();
}

// Base class for cars
// +---+---+
// | 3 | 2 |
// +---+---+
// | 4 | 1 |
// +---+---+
//       ^ Entrance of the car
class Car {
public:
    int id;
    Car(int id_): id(id_) {}
    virtual ~Car() {}
    virtual Entrance &getEntrance() = 0;
    virtual Road &getRoad1() = 0;
    virtual Road &getRoad2() = 0;
    virtual Road &getRoad3() = 0;
    virtual Road &getRoad4() = 0;
    virtual std::string getDirectionStr() = 0;
    virtual std::string getLeftStr() = 0;
};

class NorthCar: public Car {
public:
    NorthCar(int id_): Car(id_) {}
    ~NorthCar() {}
    Entrance &getEntrance() { return NorthEntrance::getInstance(); }
    Road &getRoad1() { return RoadA::getInstance(); }
    Road &getRoad2() { return RoadB::getInstance(); }
    Road &getRoad3() { return RoadC::getInstance(); }
    Road &getRoad4() { return RoadD::getInstance(); }
    std::string getDirectionStr() { return "north"; }
    std::string getLeftStr() { return "east"; }
};

class WestCar: public Car{
public:
    WestCar(int id_): Car(id_) {}
    ~WestCar() {}
    Entrance &getEntrance() { return WestEntrance::getInstance(); }
    Road &getRoad1() { return RoadB::getInstance(); }
    Road &getRoad2() { return RoadC::getInstance(); }
    Road &getRoad3() { return RoadD::getInstance(); }
    Road &getRoad4() { return RoadA::getInstance(); }
    std::string getDirectionStr() { return "west"; }
    std::string getLeftStr() { return "north"; }
};

class SouthCar: public Car {
public:
    SouthCar(int id_): Car(id_) {}
    ~SouthCar() {}
    Entrance &getEntrance() { return SouthEntrance::getInstance(); }
    Road &getRoad1() { return RoadC::getInstance(); }
    Road &getRoad2() { return RoadD::getInstance(); }
    Road &getRoad3() { return RoadA::getInstance(); }
    Road &getRoad4() { return RoadB::getInstance(); }
    std::string getDirectionStr() { return "south"; }
    std::string getLeftStr() { return "west"; }
};

class EastCar: public Car{
public:
    EastCar(int id_): Car(id_) {}
    ~EastCar() {}
    Entrance &getEntrance() { return EastEntrance::getInstance(); }
    Road &getRoad1() { return RoadD::getInstance(); }
    Road &getRoad2() { return RoadA::getInstance(); }
    Road &getRoad3() { return RoadB::getInstance(); }
    Road &getRoad4() { return RoadC::getInstance(); }
    std::string getDirectionStr() { return "east"; }
    std::string getLeftStr() { return "south"; }
};

#ifdef TEST_OUTPUT
void printConfig(void);
#endif
// Implement the car behavior
void carBehavior(Car &car) {
    // While I'm not the front of the entering cars
    while(car.getEntrance().waitingCars.front() != car.id) {
        // Wait for the condition
        pthread_cond_wait(&car.getEntrance().changes,
            &car.getEntrance().condMutex);
    }
    // Now that I'm the front of the entering cars
    // Lock the entering queue
    pthread_mutex_lock(&car.getEntrance().mutex);

    // Wait for the mutex of road 1
    pthread_mutex_lock(&car.getRoad1().mutex);
    // Detect deadlock
    // If a deadlock occurs
    if(car.getRoad1().findDeadlock()) {
        // Show that the deadlock is being solved
#ifndef TEST_OUTPUT
        std::cout << "DEADLOCK: car jam detected, signaling "
            << car.getLeftStr() << " to go." << std::endl;
#endif
        // Allow the left car to pass first
        car.getRoad1().waitingCars.push_back(car.id);
        // car.getRoad1().waitingCars.push_back(car.id);
    }
    else
    {
        // Push myself in the waiting queue for road 1
        // Because right-handed cars have greater priority to the road's occupation
        // push myself to the front
        car.getRoad1().waitingCars.push_front(car.id);
    }
    // Push myself in the waiting queue for 2
    // as soon as I have asked for road 1
    car.getRoad2().waitingCars.push_back(car.id);
    // Unlock the mutex
    pthread_mutex_unlock(&car.getRoad1().mutex);

    // Wait until I am the front of the queue
    while(car.getRoad1().waitingCars.front() != car.id) {
        // Wait for the condition
        pthread_cond_wait(&car.getRoad1().changes, &car.getRoad1().condMutex);
    }

    // Get the mutex lock
    car.getRoad1().car = car.id;
#ifdef TEST_OUTPUT
    pthread_mutex_lock(&outputLock);
    printConfig();
    pthread_mutex_unlock(&outputLock);
#endif
    pthread_mutex_lock(&car.getRoad1().mutex);
    // Show that I've arrived
#ifndef TEST_OUTPUT
    printf("car %d heading %s arrives at crossing.\n",
        car.id, car.getDirectionStr().c_str());
# endif
    // Since I've entered road, quit from the entering queue
    // Delete myself from the entering queue
    car.getEntrance().waitingCars.erase(
        std::find(car.getEntrance().waitingCars.begin(),
            car.getEntrance().waitingCars.end(), car.id));
    // Unlock the entering queue
    pthread_mutex_unlock(&car.getEntrance().mutex);
    // And signal this
    pthread_cond_broadcast(&car.getEntrance().changes);
    pthread_mutex_unlock(&car.getEntrance().condMutex);
    // Pass the road
    usleep(1000000);

    // While I'm not the front of the waiting queue for road 2
    while(car.getRoad2().waitingCars.front() != car.id) {
        // Wait for the condition
        pthread_cond_wait(&car.getRoad2().changes, &car.getRoad2().condMutex);
    }
    // Get the mutex lock
    car.getRoad2().car = car.id;
#ifdef TEST_OUTPUT
    pthread_mutex_lock(&outputLock);
    printConfig();
    pthread_mutex_unlock(&outputLock);
#endif
    pthread_mutex_lock(&car.getRoad2().mutex);

    // Pop myself from the waiting queue for road 1
    car.getRoad1().waitingCars.erase(
        std::find(car.getRoad1().waitingCars.begin(),
            car.getRoad1().waitingCars.end(), car.id));
    // And signal this
    pthread_cond_broadcast(&car.getRoad1().changes);
    pthread_mutex_unlock(&car.getRoad1().condMutex);
    // Unlock the mutex
    car.getRoad1().car = 0;
#ifdef TEST_OUTPUT
    pthread_mutex_lock(&outputLock);
    printConfig();
    pthread_mutex_unlock(&outputLock);
#endif
    // Unlock road 1
    pthread_mutex_unlock(&car.getRoad1().mutex);

    // Pop myslf from the waiting queue for road 2
    car.getRoad2().waitingCars.erase(
        std::find(car.getRoad2().waitingCars.begin(),
            car.getRoad2().waitingCars.end(), car.id));
    // Sleep for a while, I'm passing
    usleep(1000000);
    // And signal this
    pthread_cond_broadcast(&car.getRoad2().changes);
    pthread_mutex_unlock(&car.getRoad2().condMutex);

    // Now I'm gonna leave
    car.getRoad2().car = 0;
#ifdef TEST_OUTPUT
    pthread_mutex_lock(&outputLock);
    printConfig();
    pthread_mutex_unlock(&outputLock);
#endif
    pthread_mutex_unlock(&car.getRoad2().mutex);
    // And show this
#ifndef TEST_OUTPUT
    printf("car %d heading %s leaves the crossing.\n",
        car.id, car.getDirectionStr().c_str());
#endif
    return;
}

// Car behavior adapters
void *headNorth(void *id) {
    Car *car = new NorthCar(*(reinterpret_cast<int*>(id)));
    carBehavior(*car);
    delete car;
    return NULL;
}
void *headWest(void *id) {
    Car *car = new WestCar(*(reinterpret_cast<int*>(id)));
    carBehavior(*car);
    delete car;
    return NULL;
}
void *headSouth(void *id) {
    Car *car = new SouthCar(*(reinterpret_cast<int*>(id)));
    carBehavior(*car);
    delete car;
    return NULL;
}
void *headEast(void *id) {
    Car *car = new EastCar(*(reinterpret_cast<int*>(id)));
    carBehavior(*car);
    delete car;
    return NULL;
}

int main(int argc, char **argv)
{
    // Handle the command line arguments
    // which indicates the creation order of the processes
    if(argc < 2) return 0;
    // Thread ids
    pthread_t *tids = new pthread_t[strlen(argv[1])];
    memset(reinterpret_cast<void*>(tids), 0, strlen(argv[1]));
    // Car ids
    int *cids = new int[strlen(argv[1])];
    // Return values of the threads
    void **texits = new void*[strlen(argv[1])];
    // Entrance objects
    Entrance &northEntrance = NorthEntrance::getInstance();
    Entrance &westEntrance = WestEntrance::getInstance();
    Entrance &southEntrance = SouthEntrance::getInstance();
    Entrance &eastEntrance = EastEntrance::getInstance();
#ifdef TEST_OUTPUT
    pthread_mutex_init(&outputLock, NULL);
#endif
    // Create the waiting queue by the argument
    for(int i = 0; argv[1][i]; i++) {
        cids[i] = i + 1;
        switch(argv[1][i]) {
            case 'n':
                northEntrance.waitingCars.push_back(i + 1);
                pthread_create(tids + i, NULL,
                    headNorth, reinterpret_cast<void*>(cids + i));
                break;
            case 'w':
                westEntrance.waitingCars.push_back(i + 1);
                pthread_create(tids + i, NULL,
                    headWest, reinterpret_cast<void*>(cids + i));
                break;
            case 's':
                southEntrance.waitingCars.push_back(i + 1);
                pthread_create(tids + i, NULL,
                    headSouth, reinterpret_cast<void*>(cids + i));
                break;
            case 'e':
                eastEntrance.waitingCars.push_back(i + 1);
                pthread_create(tids + i, NULL,
                    headEast, reinterpret_cast<void*>(cids + i));
                break;
            default: break;
        }
    }
    
    // Join the threads
    for(unsigned i = 0; i < strlen(argv[1]) && tids[i] != 0; i++) {
        pthread_join(tids[i], texits + i);
    }
    // Free spaces
    delete[] tids; delete[] cids; delete[] texits;
    return 0;
}

#ifdef TEST_OUTPUT
void printConfig(void) {
    try {
        printf("   ");
        for(deque<int>::iterator i = RoadC::getInstance().waitingCars.begin();
            i != RoadC::getInstance().waitingCars.end(); i++) printf("%d ", *i);
        printf("\n");
        printf("+--------+--------+\n");
        printf("|        |        |\n");
        printf("|   %3d  |   %3d  |  ", RoadC::getInstance().car, RoadB::getInstance().car);
        for(deque<int>::iterator i = RoadB::getInstance().waitingCars.begin();
            i != RoadB::getInstance().waitingCars.end(); i++) printf("%d ", *i);
        printf("\n");
        printf("|        |        |\n");
        printf("+--------+--------+\n");
        printf("|        |        |\n");
        printf("|   %3d  |   %3d  |  ", RoadD::getInstance().car, RoadA::getInstance().car);
        for(deque<int>::iterator i = RoadA::getInstance().waitingCars.begin();
            i != RoadA::getInstance().waitingCars.end(); i++) printf("%d ", *i);
        printf("\n");
        printf("|        |        |\n");
        printf("+--------+--------+\n");
        printf("   ");
        for(deque<int>::iterator i = RoadD::getInstance().waitingCars.begin();
            i != RoadD::getInstance().waitingCars.end(); i++) printf("%d ", *i);
        printf("\n");
        printf("North waiting: ");
        for(deque<int>::iterator i = NorthEntrance::getInstance().waitingCars.begin();
            i != NorthEntrance::getInstance().waitingCars.end(); i++) printf("%d ", *i);
        printf("\n");
        printf("West waiting: ");
        for(deque<int>::iterator i = WestEntrance::getInstance().waitingCars.begin();
            i != WestEntrance::getInstance().waitingCars.end(); i++) printf("%d ", *i);
        printf("\n");
        printf("South waiting: ");
        for(deque<int>::iterator i = SouthEntrance::getInstance().waitingCars.begin();
            i != SouthEntrance::getInstance().waitingCars.end(); i++) printf("%d ", *i);
        printf("\n");
        printf("East waiting: ");
        for(deque<int>::iterator i = EastEntrance::getInstance().waitingCars.begin();
            i != EastEntrance::getInstance().waitingCars.end(); i++) printf("%d ", *i);
        printf("\n\n");
    }
    catch(std::exception) {}
}
#endif