/* Programming Assignment 3: Exercise D
 *
 * Now that you have a working implementation of semaphores, you can
 * implement a more sophisticated synchronization scheme for the car
 * simulation.
 *
 * Study the program below.  Car 1 begins driving over the road, entering
 * from the East at 40 mph.  After 900 seconds, both Car 3 and Car 4 try to
 * enter the road.  Car 1 may or may not have exited by this time (it should
 * exit after 900 seconds, but recall that the times in the simulation are
 * approximate).  If Car 1 has not exited and Car 4 enters, they will crash
 * (why?).  If Car 1 has exited, Car 3 and Car 4 will be able to enter the
 * road, but since they enter from opposite directions, they will eventually
 * crash.  Finally, after 1200 seconds, Car 2 enters the road from the West,
 * and traveling twice as fast as Car 4.  If Car 3 was not coming from the
 * opposite direction, Car 2 would eventually reach Car 4 from the back and
 * crash.  (You may wish to experiment with reducing the initial delay of
 * Car 2, or increase the initial delay of Car 3, to cause Car 2 to crash
 * with Car 4 before Car 3 crashes with Car 4.)
 *
 *
 * Exercises
 *
 * 1. Modify the procedure driveRoad such that the following rules are obeyed:
 *
 *  A. Avoid all collisions.
 *
 *  B. Multiple cars should be allowed on the road, as long as they are
 *  traveling in the same direction.
 *
 *  C. If a car arrives and there are already other cars traveling in the
 *  SAME DIRECTION, the arriving car should be allowed enter as soon as it
 *  can. Two situations might prevent this car from entering immediately:
 *  (1) there is a car immediately in front of it (going in the same
 *  direction), and if it enters it will crash (which would break rule A);
 *  (2) one or more cars have arrived at the other end to travel in the
 *  opposite direction and are waiting for the current cars on the road
 *  to exit, which is covered by the next rule.
 *
 *  D. If a car arrives and there are already other cars traveling in the
 *  OPPOSITE DIRECTION, the arriving car must wait until all these other
 *  cars complete their course over the road and exit.  It should only wait
 *  for the cars already on the road to exit; no new cars traveling in the
 *  same direction as the existing ones should be allowed to enter.
 *
 *  E. This last rule implies that if there are multiple cars at each end
 *  waiting to enter the road, each side will take turns in allowing one
 *  car to enter and exit.  (However, if there are no cars waiting at one
 *  end, then as cars arrive at the other end, they should be allowed to
 *  enter the road immediately.)
 *
 *  F. If the road is free (no cars), then any car attempting to enter
 *  should not be prevented from doing so.
 *
 *  G. All starvation must be avoided.  For example, any car that is
 *  waiting must eventually be allowed to proceed.
 *
 * This must be achieved ONLY by adding synchronization and making use of
 * shared memory (as described in Exercise C).  You should NOT modify the
 * delays or speeds to solve the problem.  In other words, the delays and
 * speeds are givens, and your goal is to enforce the above rules by making
 * use of only semaphores and shared memory.
 *
 * 2. Devise different tests (using different numbers of cars, speeds,
 * directions) to see whether your improved implementation of driveRoad
 * obeys the rules above.
 *
 * IMPLEMENTATION GUIDELINES
 *
 * 1. Avoid busy waiting. In class one of the reasons given for using
 * semaphores was to avoid busy waiting in user code and limit it to
 * minimal use in certain parts of the kernel. This is because busy
 * waiting uses up CPU time, but a blocked process does not. You have
 * semaphores available to implement the driveRoad function, so you
 * should not use busy waiting anywhere.
 *
 * 2. Prevent race conditions. One reason for using semaphores is to
 * enforce mutual exclusion on critical sections to avoid race conditions.
 * You will be using shared memory in your driveRoad implementation.
 * Identify the places in your code where there may be race conditions
 * (the result of a computation on shared memory depends on the order
 * that processes execute).  Prevent these race conditions from occurring
 * by using semaphores.
 *
 * 3. Implement semaphores fully and robustly.  It is possible for your
 * driveRoad function to work with an incorrect implementation of
 * semaphores, because controlling cars does not exercise every use of
 * semaphores.  You will be penalized if your semaphores are not correctly
 * implemented, even if your driveRoad works.
 *
 * 4. Control cars with semaphores: Semaphores should be the basic
 * mechanism for enforcing the rules on driving cars. You should not
 * force cars to delay in other ways inside driveRoad such as by calling
 * the Delay function or changing the speed of a car. (You can leave in
 * the delay that is already there that represents the car's speed, just
 * don't add any additional delaying).  Also, you should not be making
 * decisions on what cars do using calculations based on car speed (since
 * there are a number of unpredictable factors that can affect the
 * actual cars' progress).
 *
 * GRADING INFORMATION
 *
 * 1. Semaphores: We will run a number of programs that test your
 * semaphores directly (without using cars at all). For example:
 * enforcing mututal exclusion, testing robustness of your list of
 * waiting processes, calling signal and wait many times to make sure
 * the semaphore state is consistent, etc.
 *
 * 2. Cars: We will run some tests of cars arriving in different ways,
 * to make sure that you correctly enforce all the rules for cars given
 * in the assignment.  We will use a correct semaphore implementation for
 * these tests so that even if your semaphores are not correct you could
 * still get full credit on the driving part of the grade.  Think about
 * how your driveRoad might handle different situations and write your
 * own tests with cars arriving in different ways to make sure you handle
 * all cases correctly.
 *
 *
 * WHAT TO TURN IN
 *
 * You must turn in two files: mykernel3.c and p3d.c.  mykernel3.c should
 * contain you implementation of semaphores, and p3d.c should contain
 * your modified version of InitRoad and driveRoad (Main will be ignored).
 * Note that you may set up your static shared memory struct and other
 * functions as you wish. They should be accessed via InitRoad and driveRoad,
 * as those are the functions that we will call to test your code.
 *
 * Your programs will be tested with various Main programs that will exercise
 * your semaphore implementation, AND different numbers of cars, directions,
 * and speeds, to exercise your driveRoad function.  Our Main programs will
 * first call InitRoad before calling driveRoad.  Make sure you do as much
 * rigorous testing yourself to be sure your implementations are robust.
 */

#include <stdio.h>
#include "aux.h"
#include "sys.h"
#include "umix.h"

void InitRoad (void);
void driveRoad (int from, int mph);

struct {        // structure of variables to be shared
    int eastGateSem;
    int westGateSem;
    int roadSem[NUMPOS+1];
    int waitingWest;
    int waitingEast;
    int mtxEnter;
    int mtxRoad;
    int carsOnRoadFromE;
    int carsOnRoadFromW;
} shm;

void Main ()
{
    InitRoad ();

    /* The following code is specific to this particular simulation,
     * e.g., number of cars, directions, and speeds.  You should
     * experiment with different numbers of cars, directions, and
     * speeds to test your modification of driveRoad.  When your
     * solution is tested, we will use different Main procedures,
     * which will first call InitRoad before any calls to driveRoad.
     * So, you should do any initializations in InitRoad.
     */
/*
    if (Fork () == 0) {
        Delay (200);            // car 2
        driveRoad (WEST, 80);
        Exit ();
    }

    if (Fork() == 0) {
        Delay(1500);
        driveRoad(WEST, 60);
        Exit();
    }

    if (Fork() == 0){
        Delay(1700);
        driveRoad(WEST, 80);
        Exit();
    }

    if (Fork() == 0) {
        Delay(1800);
        driveRoad(EAST, 60);
        Exit();
    }

    if (Fork() == 0) {
        Delay(3000);
        driveRoad(WEST, 60);
        Exit();
    }

    if (Fork() == 0) {
        Delay(3300);
        driveRoad(EAST, 80);
        Exit();
    }

    if (Fork() == 0) {
        Delay(3500);
        driveRoad(WEST, 60);
        Exit();
    }

    driveRoad (WEST, 60);           // car 1
*/
/*
    //Step 4 tests

    if (Fork() == 0) {
        Delay(300);
        driveRoad(WEST, 50);
        Exit();
    }if (Fork() == 0) {
        Delay(300);
        driveRoad(WEST, 50);
        Exit();
    }if (Fork() == 0) {
        Delay(300);
        driveRoad(WEST, 50);
        Exit();
    }

    if (Fork() == 0) {
        Delay(300);
        driveRoad(EAST, 50);
        Exit();
    }if (Fork() == 0) {
        Delay(300);
        driveRoad(EAST, 50);
        Exit();
    }if (Fork() == 0) {
        Delay(300);
        driveRoad(EAST, 50);
        Exit();
    }

    driveRoad (WEST, 60);
    Exit ();
    */
    if (Fork () == 0) {
            Delay (50);          // car 2
            driveRoad (WEST, 60);
            Exit ();
    }

    if (Fork () == 0) {
            Delay (100);         // car 3
            driveRoad (EAST, 50);
            Exit ();
    }

    driveRoad (WEST, 10);           // car 1

    Exit ();
}

/* Our tests will call your versions of InitRoad and driveRoad, so your
 * solution to the car simulation should be limited to modifying the code
 * below.  This is in addition to your implementation of semaphores
 * contained in mykernel3.c.
 */

void InitRoad ()
{
    /* do any initializations here */
    // init some shared memory (regshm here!)
    // initialize semaphores (traffic lights)
    Regshm ((char *) &shm, sizeof (shm));       // register as shared

    shm.eastGateSem = Seminit(0);
    shm.westGateSem = Seminit(0);
    shm.mtxEnter = Seminit(1);
    shm.mtxRoad = Seminit(1);
    for (int i = 1; i < NUMPOS+1; i++) {
        shm.roadSem[i] = Seminit(1);
    }
    shm.waitingWest = 0;
    shm.waitingEast = 0;
    shm.carsOnRoadFromE = 0;
    shm.carsOnRoadFromW = 0;
}

#define IPOS(FROM)  (((FROM) == WEST) ? 1 : NUMPOS)

void driveRoad (from, mph)
    int from;           // coming from which direction
    int mph;            // speed of car
{
    int c;              // car ID c = process ID
    int p, np, i;           // positions

    c = Getpid ();          // learn this car's ID

    Wait(shm.mtxEnter);
    if (shm.carsOnRoadFromW >= 0 && shm.carsOnRoadFromE == 0 && shm.waitingEast == 0 && from == WEST) {
        shm.carsOnRoadFromW++;
        EnterRoad(from);
        Signal(shm.mtxEnter);
    }
    else if (shm.carsOnRoadFromE >= 0 && shm.carsOnRoadFromW == 0 && shm.waitingWest == 0 && from == EAST){
        shm.carsOnRoadFromE++;
        EnterRoad(from);
        Signal(shm.mtxEnter);
    }
    else if ((shm.carsOnRoadFromW > 0 && from == EAST) ||
                   (shm.carsOnRoadFromE > 0 && shm.waitingWest > 0 && from == EAST)) {
        shm.waitingEast++;
        Signal(shm.mtxEnter);
        Wait(shm.eastGateSem);
        shm.waitingEast--;
        shm.carsOnRoadFromE++;
        EnterRoad(from);
    }
    else if ((shm.carsOnRoadFromE > 0 && from == WEST)  ||
                     (shm.carsOnRoadFromW > 0 && shm.waitingEast > 0 && from == WEST)) {
        shm.waitingWest++;
        Signal(shm.mtxEnter);
        Wait(shm.westGateSem);
        shm.waitingWest--;
        shm.carsOnRoadFromW++;
        EnterRoad(from);
    }
    else {
        Signal(shm.mtxEnter);
    }

    PrintRoad ();
    Printf ("Car %d enters at %d at %d mph\n", c, IPOS(from), mph);
    for (i = 1; i < NUMPOS; i++) {
        if (from == WEST) {
            p = i;
            np = i + 1;
        } else {
            p = NUMPOS + 1 - i;
            np = p - 1;
        }

        Delay (3600/mph);
        Wait(shm.roadSem[np]);
        ProceedRoad ();
        Signal(shm.roadSem[p]);
        Wait(shm.mtxRoad);
        PrintRoad ();
        Printf ("Car %d moves from %d to %d\n", c, p, np);
        Signal(shm.mtxRoad);

        if (from == WEST) {
            if (shm.waitingEast == 0 && shm.waitingWest > 0) {
                Signal(shm.westGateSem);
            }
        }
        else {
            if (shm.waitingWest == 0 && shm.waitingEast > 0) {
                Signal(shm.eastGateSem);
            }
        }
    }

    Delay (3600/mph);
    ProceedRoad ();
    Signal(shm.roadSem[np]);
    Wait(shm.mtxRoad);
    PrintRoad ();
    Printf ("Car %d exits road\n", c);
    if (from == WEST) {
        if (--shm.carsOnRoadFromW == 0 && shm.waitingEast > 0) {
            Signal(shm.eastGateSem);
        }
    }
    else {
        if (--shm.carsOnRoadFromE == 0 && shm.waitingWest > 0) {
            Signal(shm.westGateSem);
        }
    }
    Signal(shm.mtxRoad);
}