/*
  The task is to synchronise the code and avoid all kind of "busy-wait". The
  solution can and should replace relevant part of the code with locks and
  semaphores. (Coniditionals optional, if you prefer)

  There are:
  - 10 philosophers
  - A round table with 5 seats
  - A bowl of food in the middle of the table
  - 2 staff members that refills the bowl
  - A plate per seat, and a fork between each plate 

  Requirements for eating:
  - Each philosopher needs a seat.
  - A philosopher needs the 2 forks next to their plate.
  - There has to be food in the bowl.
  - If the bowl is empty the philosopher leaves the table
  - A philosopher should be able to eat at the same time as other
  philosophers

  Note: The functions that are not defined can be assumed to be thread safe
  (synchronised)

  Remember, no deadlocks!
*/

// begin of dummy declarations that are only
// designed to get the code through compiler
typedef enum     { false, true } bool;
struct semaphore { int count; };
struct lock      { int owner; };
struct condition { int placeholder; };

// The five functions are thread-safe.
void cook_more_rations();
void eat_randomly_long_time();
void sleep_randomly_long_time();
void swap(int*, int*);

void sema_init(struct semaphore*, int);
void sema_down(struct semaphore*);
void sema_up(struct semaphore*);

void lock_init(struct lock*);
void lock_acquire(struct lock*);
void lock_release(struct lock*);

void cond_init (struct condition*);
void cond_wait (struct condition*, struct lock*);
void cond_signal (struct condition*, struct lock*);

int atomic_swap(int*, int);
int test_and_set(int *);
int compare_and_swap(int *, int, int);
// end of dummy declarations

bool seat_taken[5];
//bool fork_taken[5];
struct lock fork_taken[5];
int  rations_of_food = 0;

struct lock food_lock;
struct lock seat_lock;
struct semaphore seat_avail;

void init() // executed before threads
{
  for (int i = 0; i < 5; ++i)
  {
    seat_taken[i] = false;
//    fork_taken[i] = false;
    lock_init(&fork_taken[i]);
  }
  
  lock_init(&food_lock);
  lock_init(&seat_lock);
  sema_init(&seat_avail, 5);
}

void clerk_thread() // two of those
{
  for ( ; ; )
  {
    // Add more food to table
    lock_aquire(&food_lock)
    rations_of_food = rations_of_food + 1;
    lock_release(&food_lock)
      
    cook_more_rations();
  }
}

void philosopher_thread() // ten of those
{
	for ( ; ; )
  {
    int seat_no = 0;

    sema_down(&seat_avail);

    // Homework:
    //   You may use one lock per seat instead of one lock for
    //   entire array to get more fine-grained sunchronization.
    //   This will allow more thread running the loop
    //   which mean higher parallellism (as long as the extra
    //   locking/unlocking overhead does not cancel the gains).
    //   You will need to restructure the loop so that you can lock
    //   the entire critical section within the loop.
    lock_aquire(&seat_lock);
    {
      // Find a free seat.
      while ( seat_taken[seat_no] )
        seat_no = (seat_no + 1) % 5;
      seat_taken[seat_no] = true;
    }
    lock_release(&seat_lock);

    // Grab two forks.
    int fork1 = seat_no;
    int fork2 = (seat_no + 1) % 5;

    // Make sure to take lowest numbered fork first to avoid a buildup of a circular hold-and-wait.
    // Taking locks in defined order ensure we try already locked locks before possible free ones.
    // We can still have hold-and-wait, but the wait will always be on a higher numbered lock than the held ones.
    if (fork1 > fork2)
    {
      swap(fork1, fork2);
    }
    // Other proposals to avoid deadlocking:
    //  Only allow the two philosphers that can eat in (one will get the shared fork and finish, but now philosophers do not use waiting time to find their seat)
    //  Make sure each philosopher tries to grab both forks before any other philosopher tries to grab a fork (How?)
    //  Release grabbed fork if second is occupied (can be complicated and may lead to livelock?)
    //  Put forks in tray at center and allow to take any two (but this changes the set problem!)

    // while ( fork_taken[fork1] )
    //   ;
    // fork_taken[fork1] = true;
    
    // while ( fork_taken[fork2] )
    //   ;
    // fork_taken[fork2] = true;

    // After observation that each loop above behave as lock_aquire we replace them with locks!
    lock_aquire ( &fork_taken[fork1] );
    lock_aquire ( &fork_taken[fork2] );

    // Check for food. Eat, or leave hungry.
    if (rations_of_food > 0)
    {
      // Homework:
      //   Synch error here! We forgot rations_of_food is read in the if-condition above!
      //
      //   Can you figure out what kind of error this lead to?
      //   Look for what range of values should be possible for
      //   rations_of_food (according to code logic) and how unsuitable
      //   thread switch may get the value outside that range.
      //
      //   Where do the critical section start (where do you move lock_aquire)?
      //
      //   Then, what about lock_release? Will the lock always be released now?)
      lock_aquirae(&food_lock)
      rations_of_food = rations_of_food - 1;
      lock_release(&food_lock)

      eat_randomly_long_time();
    }
    // Homework:
    //   One suggestion was to instead remain at the table waiting for food.
    //   What do you need to change to wait until food becomes available?
    //   Well done you will en up with less and simpler code!

    // Replace forks and leave seat.
    lock_release ( &fork_taken[fork1] );
    lock_release ( &fork_taken[fork2] );

    // This code changes seat_taken array while other thread may read
    // it and thus should have synchronization unless you know for
    // sure that architecture, memory model or compiler optimizations
    // will not cause problems.
    //
    // Consider the sequence:
    //  (1) A reading thread (in while at top) just saw seat 0 as "occupied" and ar interrupted
    //  (2) The thread occuping seat 0 runs and change the seat to "free"
    //  (3) When the reading thread continues /it has false information about the seat/!
    //      The reading thread believes "occupied" but the seat is actually "free".
    //
    // Observing false information is a typical synchronization issue.
    // Arguing that this sequence will not cause a problem is valid,
    // but consider an architecture with out-of-order execution or a
    // compiler that does its best to optimize the CPU pipeline, moving
    // instructions that do not have dependencies. Unless there is a
    // barrier the instruction may be moved to right after the last
    // use of the involved variables. Locking provids that barrier.    
    // Unaware of other threads the compiler may sometimes even decide
    // to remove variables altogher*.
    lock_aquire(&seat_lock);
    seat_taken[seat_no] = false;
    lock_release(&seat_lock);

    // Digest the food.
    sleep_randomly_long_time();

    sema_up(&seat_avail);
  }
}


// *Try this code on godbolt.org and set complier flag -O2 to get a brief
// impression of what the compiler may do. What happens to the wait-loop?
bool locked{false};
int i{0};

int main()
{
    while (locked)
        ;
    locked = true;

    i = 1 + 2 + 3 + 4 + 5;

    locked = false;
}

// Output
main:
        mov     DWORD PTR i[rip], 15
        xor     eax, eax
        mov     BYTE PTR locked[rip], 0
        ret
j:
        .zero   4
i:
        .zero   4
locked:
        .zero   1