Lock *l1, *l2;
			void p() {
			  l1->Acquire();
			  l2->Acquire();
			  code that manipulates data that l1 and l2 protect
			  l2->Release();
			  l1->Release();
			}
			void q() {
			  l2->Acquire();
			  l1->Acquire();
			  code that manipulates data that l1 and l2 protect
			  l1->Release();
			  l2->Release();
			}
			

• Mutual Exclusion: Only one thread can hold lock at a time.
• Hold and Wait: At least one thread holds a lock and is waiting for another process to release a lock.
• No preemption: Only the process holding the lock can release it.
• Circular Wait: There is a set t₁, ..., t_n such that t₁ is waiting for a lock held by t₂, ..., t_n is waiting for a lock held by t₁.

• First, most locking abstractions offer an operation that tries to acquire the lock but returns if it cannot. We will call this operation TryAcquire. Use this operation to try to acquire the lock that you need to acquire out of order.
• If the operation succeeds, fine. Once you've got the lock, there is no problem.
• If the operation fails, your code will need to release all locks that come after the lock you are trying to acquire. Make sure the associated data structures are in a state where you can release the locks without crashing the system.
• Release all of the locks that come after the lock you are trying to acquire, then reacquire all of the locks in the right order. When the code resumes, bear in mind that the data structures might have changed between the time when you released and reacquired the lock.

			int d1, d2;
			// The standard acquisition order for these two locks
			// is l1, l2.
			Lock *l1, // protects d1
			     *l2; // protects d2
			// Decrements d2, and if the result is 0, increments d1
			void increment() {
			  l2->Acquire();
			  int t = d2;
			  t--;
			  if (t == 0) {
			    if (l1->TryAcquire()) {
			      d1++;
			    } else {
			      // Any modifications to d2 go here - in this case none
			      l2->Release();
			      l1->Acquire();
			      l2->Acquire();
			      t = d2;
			      t--;
			      // some other thread may have changed d2 - must recheck it
			      if (t == 0) {
			        d1++;
			      }
			    }
			    l1->Release();
			  }
			  d2 = t;
			  l2->Release();
			}
			

• Restrict the way in which processes will request resources to prevent deadlock.
• Require processes to give advance information about which resources they will require, then use algorithms that schedule the processes in a way that avoids deadlock.
• Detect and eliminate deadlock when it occurs.

• Mutual Exclusion - To eliminate mutual exclusion, allow everybody to use the resource immediately if they want to. Unrealistic in general - do you want your printer output interleaved with someone elses?
• Hold and Wait. To prevent hold and wait, ensure that when a process requests resources, does not hold any other resources. Either asks for all resources before executes, or dynamically asks for resources in chunks as needed, then releases all resources before asking for more. Two problems - processes may hold but not use resources for a long time because they will eventually hold them. Also, may have starvation. If a process asks for lots of resources, may never run because other processes always hold some subset of the resources.
• Circular Wait. To prevent circular wait, order resources and require processes to request resources in that order.

			Avail[j] = number of resource j available
			Max[i,j] = max number of resource j that process i will use
			Alloc[i,j] = number of resource j that process i currently has
			Need[i,j] = Max[i,j] - Alloc[i,j]
			

• There is a pool of runnable processes contending for the CPU.
• The processes are independent and compete for resources.
• The job of the scheduler is to distribute the scarce resource of the CPU to the different processes ``fairly'' (according to some definition of fairness) and in a way that optimizes some performance criteria.

• IO Bound processes: processes that perform lots of IO operations. Each IO operation is followed by a short CPU burst to process the IO, then more IO happens.
• CPU bound processes: processes that perform lots of computation and do little IO. Tend to have a few long CPU bursts.

• Running - process is running on CPU.
• Ready - ready to run, but not actually running on the CPU.
• Waiting - waiting for some event like IO to happen.

• When process switches from running to waiting. Could be because of IO request, because wait for child to terminate, or wait for synchronization operation (like lock acquisition) to complete.
• When process switches from running to ready - on completion of interrupt handler, for example. Common example of interrupt handler - timer interrupt in interactive systems. If scheduler switches processes in this case, it has preempted the running process. Another common case interrupt handler is the IO completion handler.
• When process switches from waiting to ready state (on completion of IO or acquisition of a lock, for example).
• When a process terminates.

• CPU Utilization: Keep CPU utilization as high as possible. (What is utilization, by the way?).
• Throughput: number of processes completed per unit time.
• Turnaround Time: mean time from submission to completion of process.
• Waiting Time: Amount of time spent ready to run but not running.
• Response Time: Time between submission of requests and first response to the request.
• Scheduler Efficiency: The scheduler doesn't perform any useful work, so any time it takes is pure overhead. So, need to make the scheduler very efficient.

• Waiting Time? (24 + 27) / 3 = 17
• Turnaround Time? (24 + 27 + 30) = 27.
• Throughput? 30 / 3 = 10.

• Waiting Time? (3 + 3) / 2 = 6
• Turnaround Time? (3 + 6 + 30) = 13.
• Throughput? 30 / 3 = 10.

• CPU usage field = CPU usage field / 2
• Priority = CPU usage field / 2 + base priority

• Priority = CPU usage field / 2 + base priority + nice value