/** SHARED **/
int count = 0;

/** PRODUCER **/
while ( true )
{
 item = produce_next_item();
 if ( count == N )
   go_to_sleep();
 add_to_buffer( item );
 count++;
 if ( count == 1 )
   wake_up_consumer();
}

/**
 ** count++;
 **
 **  load r1, count
 **  incr r1
 ** store r1, count
 **
 **/

/** CONSUMER **/
while ( true )
{
 if ( count == 0 )
   go_to_sleep();
 item = remove_from_buffer();
 count--;
 if ( count == N-1 )
   wake_up_producer();
 consume_item( item );
}

====================================

/** SHARED **/
semaphore empty_slots = N;
semaphore full_slots = 0;
semaphore mutex = 1;

/** PRODUCER **/
while ( true )
{
 item = produce_an_item();

 wait( empty_slots );  /* block */
   wait( mutex );
     add_to_buffer( item );
   signal( mutex );
 signal( full_slots );
}

/** CONSUMER **/
while ( true )
{
  wait( full_slots );  /* block */
   wait( mutex );
     item = remove_from_buffer();
   signal( mutex );
 signal( empty_slots );

 consume_item( item );
}

====================================

Readers-Writers Problem:

(1) Any number of readers and writers are allowed

(2) Readers can simultaneously read from the database

(3) Only one writer can write to the database at any given time

(4) If a writer is writing, no readers may read

(5) No starvation amongst readers and writers

/** SHARED **/
int read_count = 0;
semaphore mutex_read_count = 1;
semaphore mutex_write = 1;

/** WRITER **/
while ( true )
{
 non_critical_section_writer();
 wait( mutex_write );
   write_operations();
 signal( mutex_write );
}

/** READER **/
while ( true )
{
 wait( mutex_read_count );
   read_count++;
   if ( read_count == 1 )
     wait( mutex_write );  /* prohibit writes */
 signal( mutex_read_count );

 read_operations();

 wait( mutex_read_count );
   read_count--;
   if ( read_count == 0 )
     signal( mutex_write );  /* allow writes */
 signal( mutex_read_count );

 non_critical_section_reader();
}

Avoid Starvation:
(1) Give writers priority.  If a process
   is waiting to write, no reader is allowed
   to read.  But readers may starve.  As long
   as writers are writing, readers may never
   get access to read.

(2) To solve this problem, if no writer is
   waiting to write, any reader that wants
   to read is allowed to read.  As soon as
   a writer wants to write, the writer is
   allowed to write.  Once the writer is done,
   all of the currently blocked/waiting readers
   can read.

(3) Enforce alternation between readers and
   writers to prevent starvation.

====================================

In general, each process:
(a) requests resource(s)
(b) acquires resource(s) if available;
    waiting/blocking otherwise
(c) uses resource(s) for a finite period of time
(d) releases resource(s)

Disadvantages of deadlock:
(1) Both processes are blocked indefinitely
(2) Held resources are unavailable


Deadlock requirements:
(1) Mutual exclusion: a resource is used by
    only one process at a time
(2) Hold and wait: process holding 1+ resources
    is waiting for 1+ other resources to become
    available
(3) No preemption: once a resource is acquired,
    only the process that acquired it can
    release it
(4) Circular wait - cycle in the graph

P = { P1, P2, P3 }
R = { R1, R2, R3 }  <== "resource types"
acquired edges = { (R1,P1), (R2,P2), (R3,P3) }
request edges = { (P1,R2), (P2,R3) }


Dining Philosophers Problem:
-----------------------------
/** SHARED **/
semaphore fork[] = { 1, 1, 1, 1, 1 };

/** PHILOSOPHER i */
while ( true )
{
 think();   /* non-critical section */

 /* obtain left-hand side fork */
 wait( fork[i] );
   wait( fork[i+1%5] );  /* obtain rhs fork */
     eat();  /* critical section */
   signal( fork[i+1%5] );
 signal( fork[i] );
}


Avoid deadlock:
---------------
(a) philosopher picks up both forks in a
   mutex critical section
(b) allow at most four philosophers to be
   sitting at the table
(c) use an asymmetric approach: each odd-numbered
   philosopher picks up lhs first; each even-
   numbered philosopher picks up rhs first