1. No efficient solution to always avoid deadlock. 
    Get A
...
Get B
...
Release A
...
Release B

    Get B
...
Get A
...
Release B
...
Release A

  3. 2 categories of resource-Reusaable, and consumable.
  4. Reusable:
    1. Processors,
    2. I/O channels,
    3. main and secondary memory,
    4. devices
    5. data structures such as files, databases, and semaphores
    6. Deadlock occurs if each process holds one resource and requests the other
    7. Example: 2 processes each need 200K. There is 250K available. If each grabs 100K, and then they try to grab the remaining... deadlock.
  5. Consumable:
    1. Interrupts,
    2. signals,
    3. messages,
    4. information in I/O buffers
    5. Example, 2 processes do a receive before doing a send.
  6. Conditions for possible deadlock:
    1. Mutual exclusion - Only one (or at least a finite number)process may use a resource at a time
    2. Hold-and-wait - A process may hold allocated resources while awaiting assignment of others
    3. Preemption - No resource can be forcibly removed form a process holding it
    4. Actual deadlock also requires circular wait.
  7. Dealing with deadlock:
    1. Prevent
    2. Avoid
    3. Detect
  8. Preventing
    1. Not much we can do about mutual exclusion
    2. Hold and Wait - require process to request all resources at once.
    3. Preemption - processes can lose resource and must re-request.
    4. Circular wait - set order or resource requests.
  9. Avoidance - decide realtime whether to allow a request for a resource.
    1. A process is only started if the maximum claim of all current processes plus those of the new process can be met. Not optimal
    2. Banker's Algorithm.

    3. Safe state is where there is SOME order to run all processes to completion.

    4. When a process makes a request for a set of resources, assume that the request is granted, Update the system state accordingly, Then determine if the result is a safe state. If so, grant the request and, if not, block the process until it is safe to grant the request.
    5. Less restrictive than prevention.
  10. Deadlock detection
    1. Detect and break deadlock.

      Mark all processes that have been allocate 0 resources.
      \( W = V \)
      Find process i s.t. \( Q_i \leq W \)
      \(W = W + A_i\)
      repeat until no i, or all processes are marked.

    2. Any process unmarked is deadlocked.
    3. Abort all deadlocked processes
    4. Back up each deadlocked process to some previously defined checkpoint, and restart all process (Risk of deadlock recurring)
    5. Successively abort deadlocked processes until deadlock no longer exists
    6. Successively preempt resources until deadlock no longer exists
  11. Dining philosophers.
    1. Deadlock
    2. Odd grabs left, even grabs right.
    3. Room semaphore.
  12. Linux mechanisms.
    1. Pipes
    2. msgsnd and msgrcv
    3. Semaphores
    4. Atomic ops:
      1. atomic_read(atomic_t *v)
      2. atomic_set(atomic_t *v,int i)
      3. atomic_add(int i,atomic_t *v) ...
      4. atomic_dec_and_test(atomic_t *v)...
    5. spinlocks
    6. reader-writer semaphores