cs350/kern/synchprobs/traffic_synch.c

#include <types.h>
#include <lib.h>
#include <synchprobs.h>
#include <synch.h>
#include <opt-A1.h>

/*
 * This simple default synchronization mechanism allows only vehicle at a time
 * into the intersection.   The intersectionSem is used as a a lock.
 * We use a semaphore rather than a lock so that this code will work even
 * before locks are implemented.
 */

/*
 * Replace this default synchronization mechanism with your own (better) mechanism
 * needed for your solution.   Your mechanism may use any of the available synchronzation
 * primitives, e.g., semaphores, locks, condition variables.   You are also free to
 * declare other global variables if your solution requires them.
 */

/*
 * replace this with declarations of any synchronization and other variables you need here
 */
static struct lock * globlock;
typedef struct cv cv;

// This section contains global vars and useful functions to work with them. As well as the structs used for them
typedef struct car
{
  Direction origin;
  Direction dest;
  bool old;
  car * next;
  cv * cv;
} car;

typedef struct list
{
  car * front;
  car * back;
} list;

list * queue = NULL;
list * active = NULL;

// car initializer/allocator
struct car * newcar(Direction origin, Direction dest)
{
  car * temp = kmalloc(sizeof(car));
  
  if(!(temp))
  {
    panic("Failed to create a car.");
  }
  
  temp->origin = origin;
  temp->dest = dest;
  temp->old = 0;
  temp->next = NULL;
  temp->cv = NULL;
}

// list initializer/allocator
struct list * newlist()
{
  list * temp = kmalloc(sizeof(list));
  
  if(!(temp))
  {
    panic("Could not allocate list.");
  }
  
  temp->front = NULL;
  temp->back = NULL;
}

// puts a car into the queue, at the front if old is true, the back otherwise
void enqueue(car * newcar)
{
  if (!(queue->back))
  {
    queue->front = newcar;
    queue->back = newcar;
  }
  
  if (newcar->old) // if the car is "old", let it go first. be nice to your elders
  {
    car * temp = queue->front;
    queue->front = newcar;
    newcar->next = temp;
    
    return;
  }
  
  queue->back->next = newcar;
  queue->back = newcar;
}

// push a car to the end of the active list
void push(car * newcar)
{
  if (!(active->front))
  {
    active->front = newcar;
    active->back = newcar;
  }
  
  active->back->next = newcar;
  active->back = newcar;
}

// remove an element from the front of the queue
struct car * pop()
{
  if (!(queue->front))
  {
    return NULL;
  }
  
  if (queue->front == queue->back)
  {
    queue->back == NULL;
  }
  
  car * temp = queue->front;
  queue->front = queue->front->next;
  return temp;
}

// called when a car clears the intersection
void clearint(car * done)
{
  car * temp = active->front;
  car * temp2 = NULL;
  
  while(temp != done)
  {
    temp2 = temp;
    temp = temp>next;
  }
  
  // first element of the list is being removed
  if (!(temp2))
  {
    active->front = active->front->next;
    goto SKIP1;
  }
  
  temp2->next = temp->next;
  SKIP1:
  
  if (temp->cv) // if this car was blocking something
  {
    cv_broadcast(temp->cv, globlock); // wake all/inform them you're all good
    kfree(temp->cv);
  }
  
  kfree(temp);
}

// cleans up a list
void dellist(list * dead)
{
  car * temp = dead->front;
  
  while (temp)
  {
    car * temp2 = temp->next;
    kfree(temp->cv);
    kfree(temp);
    temp = temp2;
  }
  
  kfree(dead);
}

// returns true if a car is turning right
bool rightturn(car * car)
{
  int temp = car->origin - car->dest;
  return (temp == 1 || temp == -3);
}

/*
 * The simulation driver will call this function once before starting
 * the simulation
 *
 * You can use it to initialize synchronization and other variables.
 *
 */
void intersection_sync_init()
{
  globlock = lock_create("lightlock");
  
  if (!(globlock))
  {
    panic("Failed to create lock!");
  }
  
  queue = newlist();
  active = newlist();
}

/*
 * The simulation driver will call this function once after
 * the simulation has finished
 *
 * You can use it to clean up any synchronization and other variables.
 *
 */
void intersection_sync_cleanup()
{
  KASSERT(queue);
  KASSERT(active);
  
  dellist(queue);
  dellist(active);
  lock_destroy(globlock);
}


/*
 * The simulation driver will call this function each time a vehicle
 * tries to enter the intersection, before it enters.
 * This function should cause the calling simulation thread
 * to block until it is OK for the vehicle to enter the intersection.
 *
 * parameters:
 *    * origin: the Direction from which the vehicle is arriving
 *    * destination: the Direction in which the vehicle is trying to go
 *
 * return value: none
 */

void intersection_before_entry(Direction origin, Direction destination)
{
  lock_acquire(globlock);
  car * new = newcar(origin, destination);
  
  RESTART:
  
  // Nothing in intersection, so proceed
  if (!(active->front))
  {
    push(new);
    lock_release(globlock);
    return;
  }
  else // things are in the intersection
  {
    car * temp = active->front;
    
    while (temp)
    {
      if (temp->origin == new->origin || (temp->origin == new->dest && temp->dest == new->origin) || (temp->dest != new->dest && (rightturn(new) || rightturn(temp))))
      {
        temp = temp->next;
        continue;
      }
      else
      {
        enqueue(new);
        new->old = 1; // make new "old", since now it has already waited once
        lock_release(globlock);
        
        // create cv for temp if it doesn't have one yet
        if(!(temp->cv))
        {
          temp->cv = cv_create("carcv");
        }
        
        cv_wait(temp->cv, globlock); // sleep and reacquire lock once woken
        goto RESTART; // now we have to make sure there's nothing else screwing us over
      }
    }
    
    push(new);
    lock_release(globlock);
  }
}


/*
 * The simulation driver will call this function each time a vehicle
 * leaves the intersection.
 *
 * parameters:
 *    * origin: the Direction from which the vehicle arrived
 *    * destination: the Direction in which the vehicle is going
 *
 * return value: none
 */

void intersection_after_exit(Direction origin, Direction destination)
{
  car * temp = active->front;
  
  while (temp)
  {
    if (temp->origin == origin && temp->dest == destination)
    {
      clearint(temp);
      break;
    }
    else
    {
      temp = temp->next;
    }
  }
}