requirement for solving critical section problem

Critical Section
the part of the program where the shared memory is accessed.

The three requirements for solving the critical section problem:

Mutual Exclusion: one process at a time gets in critical section.
Progress: if p_i wants to get in critical section and no process is in critical section

Bound wait: p_i should be able to get critical section with some upper waiting time.

Process Synchronization:
The Producer-Consumer Problem:

Producer:

while(true)
{
    Produce(nextp);
    while(counter == n);   //if buffer is full, wait
    buffer[in] = nextp;
    in = (in + 1) % n;     //mode by n
    counter = counter + 1;
}

Consumer:

while(true)
{
    while(counter == 0); //if buffer is empty, wait
    nextc = buffer[out];
    out = (out + 1) % n;
    counter = counter - 1;
    Consume(nextc);
}

The problem occurred at sharing the same memory space, counter.
If both read and write counter at same time, it will cause inconsistent.
e.g. Both got counter = 3
then producer update it into 4 then consumer writes it into 2.
This looks like that the producer has never updated the information.

Solving the Producer-Consumer Problem using Semaphores:

Semaphores: (Synchronization tool) (Dijkstra 1965)
     It is an integer variable which is accessed through two atomic operations:
                  wait , signal
                  down, up
                  sleep, wakeup
                  P, V (original in Dutch)
    Note: Atomic means that it can not be divided. So, either completed all or not done at all.

Binary semaphore: like a lock variable,0 or 1, a mutual exclusive variable.

Counted semaphore: takes on non-negative values.

2 operations:

up - increase the semaphore

down - if semaphore is 0, block;

class semaphore
{
   public:
      semaphore(int i)     // constructor
       {
         S = i;
       }
      void wait()      // atomic operation
       {
          while(S <= 0);
          S = S - 1;
       }
      void signal()    // atomic operation
       {
          S = S + 1;
       }
   private:
       int S;     //S is a waiting queue.
}

semaphore mutex(1);      //mutual exclusion object: mutex
p_i:
   while(true)
    {
       mutex.wait();
       critical section
       mutex.signal();
       remainder section
    }

Example:
            semaphore S(0);
            p₁:
                Statement 1;
                S.signal();
                Statement 3;
            p₂:
                S.wait();
                Statement 2;

For the sequence of execution,

Statement 1 must happen before Statement 2.
No ordering between Statement 2 and Statement 3.

Busy Waiting - The process is looping or running while waiting.

Two operations (OS level)

Block - allows process to block itself
Wakeup - a process can wakeup another.

Monitor - high level abstraction for process synchronization problem solving.
See Figure 2-13 on page 69:

monitor example
integer i;
condition c;
procedure producer (x);
.
.
.
end;
procedure consummer (x);
.
.
.
end;
end monitor;

See Figure 2-14 on page 71:
An outline of the producer-consumer problem with monitors. Only one monitor procedure at a time is active. The buffer has N slots.

monitor Producer-Consummer

integer full, empty;
condition count;
procedure enter;
begin
if count = N then wait(full);
enter_item;
count := count + 1;
if count = 1 then signal(empty)
end;
procedure remove;
begin
if count = 0 then wait(empty);
remove_item;
count := count - 1;
if count = N - 1 then signal(full)
end;
count := 0;
end monitor;
procedure producer;
begin
   while truedo
   begin
      produce_item;
      Producer-Consummer.enter
   end
end;
procedure consumer;
begin
   while truedo
   begin
     Producer-Consummer.enter;
     consumer_item
   end
end;

Message Passing:

Base on send and receive,

receive generally blocks on nothing to receive
send may or may not block on no receiver.

When send blocks on no receiver, we call this the rendezvous principle.