Section notes for CS162 
Section #4, February 19, 2002
Barbara Hohlt <hohltb@cs.berkeley.edu>

- A Semaphore is an integer value and a list of threads (or processes)
	that, apart from intialization, can be accessed only through 
	two standard atomic operations.  (definition in practice)

   - P() is an atomic operation that decrements the semaphore by 1 and
	waits for a semphore to become non-negative. 'Proberen' means to 
      	'test' in Dutch.

   - V() is an atomic operation that increments the semaphore by 1, waking up
	a waiting process, if any. 'Verhogen' means 'increment' in Dutch.
 	
  - Binary semphores (values are 1 or 0) can be used for mutual exclusion and
	have their initial values intialized to 1.

  - Counting semphores can be used for scheduling and
	have their initial values intialized to 0.

   semaphore {
	integer value;
	list L;	// list of threads (or processes) 
   } S;

   P(): S.value = S.value -1;
	if S.value < 0
		add this thread to S.L;
		sleep(this thread );

   V(): S.value = S.Value + 1;
	if S.value <= 0
		remove thread T from S.L;
		wake(one thread);


- A Lock provides mutual exclusion to the shared data.

- Condition variables are a queue of threads waiting for something _inside_
  a critical section.  Rule: must hold lock when doing condition variable 
  operations.  Key idea with condition variables: make it possible to go to 
  sleep inside the critical section, by _atomically_ releasing a lock at 
  same time we go to sleep. 

- A Monitor is a lock and zero or more condition variables for 
  managing concurrent access to shared data.

--------------------------------------------------------------------------
	Producers and Consumers using Interrupts
--------------------------------------------------------------------------
   int numCokes = 0;
   LinkedList waitingConsumers;
   LinkedList waitingProducers;

   Producer() {
     interrupt.disable();
     while (numCokes == MAXCOKES) {
       waitingProducers.add(myThread);
       myThread.sleep();  // interrupts still disabled
     }
     numCokes++;
     while (consumer = waitingConsumers.next()) {
       consumer.ready();
     }
     interrupt.enable();
   }

   Consumer() {
     interrupt.disable();
     while (numCokes == 0) {
       waitingConsumers.add(myThread);
       myThread.sleep();
     }
     numCokes--;
     while (producer = waitingProducers.next()) {
       producer.ready();
     }
     interrupt.enable();
   }

--------------------------------------------------------------------------
	Producers and Consumers using Condition Variables 
--------------------------------------------------------------------------

  Lock lock;
  Condition wantToAdd = new Condition(lock);
  Condition wantToTake = new Condition(lock);

  Producer() {
    lock.acquire();
    while (numCokes == MAXCOKES) { // Like a semaphore.P()
      wantToAdd.sleep(); // Lock released!
    }
    numCokes++;   // Lock reacquired!
    wantToTake.wakeAll();          // Like a semaphore.V()
    lock.release();
  }

  Consumer() {
    lock.acquire();
    while (numCokes == 0) {        // Like a semaphore.P()
      wantToTake.sleep(); // Lock released!
    }
    numCokes--;  // Lock reacquired
    wantToAdd.wakeAll();           // Like a semaphore.V()
    lock.release();
  }
--------------------------------------------------------------------------

- This is much nicer
- Question: What if we changed 'wakeAll()' to 'wake()' in the above?
  - Answer: Would have to wait for another producer or consumer
    to come around before the next producer or consumer would wake up!
- Note that we're really building "semaphores" when we do it this way!
- So different synchronization primitives are more useful or convenient
  in different situations.