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

- Some words on MESA style monitors (used in Nachos!) 
	- signaler keeps the lock and cpu, the waiter is put
	  on the ready Q ( so use wait() inside a while loop and recheck
	  the condition! )
	- waiter releases the lock and goes to sleep atomically, when
	  it wakes it is on the ready Q

- Types of resources
	- preemptable resources can be taken away with little or no problem
		(eg cpu, memory), and can be scheduled
	- non-preemtable resources cause a problem if they are taken away 
		(eg disk, semaphores, terminal, printer), 
		and must be allocated 

- Deadlock is concerned with allocating resources.
- Deadlock is a situation in which each thread in a set is waiting
  for something from some other thread waiting in the set. Since
  each is waiting, non can proceed.

- Conditions for deadlock
 1. limited access (mutex, bounded buffer)
 2. no preemption allowed
 3. multiple independent requests wait while holding a resource
 4. circular chain requests

- Approaches to deadlock problem
	- detection, detect deadlock and fix it, database solution
	- avoidance, OS solution
	   1. must eliminate one of the four deadlock conditions (hard!)
	   2. only make allocations that are "safe" (Banker's Algorithm)

- A safe state is one in which deadlock is not inevitable (ie there
  exists a sequence of task completions which lead to all tasks completed). 
  A safe allocation is one that leads to a safe state. 

- An unsafe state leads to deadlock.

- The Banker's Algorithm is used to compute a safe sequence of tasks.

--------------------------------------------------------------------------
	Banker's Algorithm
--------------------------------------------------------------------------
 k is a resource 
 for each thread x
 max(x,k) is max #k to be used by x
 alloc(x,k) is #k currently allocated to x
 need(x,k) is #k still needed by x
 avail(k) is #k currently available 

	If all threads can finish with no additional resources,
		need(x) <= avail(k) for all k and x
		state = safe

	Else for all threads do
		Find a thread x, such that
		  need(x,k) <= avail(k) 

	If not found
		state = unsafe

	If found release resources 
		mark x = finished
		avail(k) = avail(k) + alloc(x)


Below is the state of our system at each step 1, 2, 3. 
We begin with avail(k)=20.

	Process		Alloc		Max	Avail
	------		-----		---	-----
1.	 A		90		100	 20
2.	 B		50		110	110
3.	 C		30		160	160
						190

--------------------------------------------------------------------------