CS 440
Week 6 Summary
Chapter 5: Concurrency
Operating systems are concerned with managing processes and threads. This arises in three situations:
  1. Multiprogramming
  2. Multiprocessing
  3. Distributed processing
Here are the important concepts for this chapter:
  1. critical section
  2. deadlock
  3. livelock
  4. mutual exclusion
  5. race condition
  6. starvation
Here are difficulties associated with concurrency:
  1. Sharing of resources can be a problem because of the need for synchronization
  2. Sharing of resources can also cause a problem called deadlock
  3. Error checking is a problem because trying to recreate a error condition may be difficult
Here is an example of a synchronization problem. Two processes are accessing a variable x that has a value of 3. Process P1 will increment x, and process P2 will add two to the value. The final value for x should be 6 (3 + 1 + 2). However imagine the following situation:
  1. P1 obtains the value of x - it has x as 3
  2. P1 is interrupted and P2 enters the processor and obtains the value of x also 3
  3. P1 interrupts P2 and increments the value of x and writes it back out to memory so that x is now 4
  4. P2 enters the processor and since it already has the value of x as 3 proceeds to update its value to 5
  5. P2 writes out x and its value is finally 5
The final value of x can be 4, 5, or 6 depending on the ordering of the processes. This is called a race. The section of code where x is read its value is changed and the result is written to memory is called a critical section.

The solution to this problem is to allow only one process to execute in the critical section and that a process once entering the critical section is not interrupted until it leaves the critical section. This is called mutual exclusion.

Difficulties arise when a process P1 is allocated a resource but is not ready to run and another process P2 is ready to run once it has acquired the resource that was allocated to P1. This situation can keep both processes from running and is called deadlock. A similar situation is when a process is never able to acquire a resource that is needed for it to run so this process never has a chance to run. This is called starvation.

There are several ways to enforce mutual exclusion:
  1. hardware support for mutual exclusion
    • interrupt disabling - a process is prevented from being interrupted - cost is high since cuts back on multiprogramming
    • test and set - done atomically.  See code on page 214 (busy-wait)
    • adv: simple, works on different hardware configurations. disadv: Busy waiting, starvation and deadlock possible
  2. semaphores: 
    • operations: initialize, wait, and signal
    • counting/general or binary
    • initialize set to 0 or 1, wait - if 0 then process blocked, otherwise  set semaphore to 0 and execute, and signal if process is blocked then unblock otherwise set to 1. These are all done atomically.
  3. monitor
  4. message passing.
semaphores
To handle the previous problem that was discussed using semaphores:

//program doP1P2
    binSemaphore s = 1
    int x = 3
   
    process P1() {
       wait(s)
       x = x + 2
       signal(s)
    }

    process P2() {
       wait(s)
       x = x + 3
       signal(s)
    }
   
void main() {
   parbegin(P1,P2)
}
 
monitors - place critical section code inside monitor. Only one process allowed in monitor at one time.
message passing - three kinds
  1. blocking send and receive
  2. non-blocking send and blocking receive
  3. non-blocking send and receive.
When messages are passed that is called a rendezvous
Can have direct or indirect addressing of message passing.