Unit 2: Synchronization, scheduling and deadlocks

Inter-process communication (IPC) lets processes exchange data. The two models are shared memory (fast, needs synchronisation) and message passing (send/receive; easier across computers). A race condition occurs when two processes access shared data at the same time and the result depends on the order in which they run.

A critical section is the part of a program that accesses shared data. A solution must satisfy three requirements:

• Mutual exclusion: only one process in its critical section at a time.
• Progress: if no process is in the critical section, one that wants to enter must be allowed to without indefinite delay.
• Bounded waiting: a limit on how many times others can enter before a waiting process gets its turn.

• A mutex lock protects a critical section: a process must acquire() the lock before entering and release() it on leaving. A lock that busy-waits is a spinlock — useful on multiprocessors when waits are short.

cacquire() { while (!available) ; /* busy wait */ available = false; }
release() { available = true; }
/* usage */
acquire();  /* critical section */  release();

A semaphore S is an integer variable accessed only through two atomic operations:

• wait(S) (P): while S ≤ 0 wait; then S = S − 1.
• signal(S) (V): S = S + 1.

A binary semaphore (0 or 1, also called a mutex) gives mutual exclusion; a counting semaphore controls access to a resource with several instances.

wait(mutex);
    /* critical section */
signal(mutex);
    /* remainder section */

A monitor is a high-level construct in which shared data and the procedures that use it are grouped together, and only one process can be active inside the monitor at a time. Condition variables (wait and signal) handle waiting inside it.

c/* n buffers; semaphores: mutex = 1, empty = n, full = 0 */
/* Producer */                       /* Consumer */
do {                                 do {
  produce an item;                     wait(full);
  wait(empty);                         wait(mutex);
  wait(mutex);                         remove item from buffer;
  add item to buffer;                  signal(mutex);
  signal(mutex);                       signal(empty);
  signal(full);                        consume the item;
} while (true);                      } while (true);

• empty counts free slots, full counts filled slots, mutex guards the buffer itself.

c/* rw_mutex = 1, mutex = 1, read_count = 0 */
/* Writer */                         /* Reader */
wait(rw_mutex);                      wait(mutex);
  /* writing */                        read_count++;
signal(rw_mutex);                      if (read_count == 1) wait(rw_mutex);  /* first reader locks out writers */
                                     signal(mutex);
                                       /* reading */
                                     wait(mutex);
                                       read_count--;
                                       if (read_count == 0) signal(rw_mutex); /* last reader lets writers in */
                                     signal(mutex);

• Many readers may read together; a writer needs exclusive access. This "first readers–writers" solution can starve writers.

Preemptive scheduling can take the CPU away from a running process; non-preemptive lets it run until it finishes or blocks.

• Multiprocessor scheduling: asymmetric (one master processor schedules) vs symmetric (each processor self-schedules); processor affinity keeps a process on the same CPU for cache benefits; load balancing (push and pull migration).
• Thread scheduling: kernel schedules kernel-level threads; user-level threads are mapped by the thread library (many-to-one, one-to-one, many-to-many).
• Real-time scheduling: rate-monotonic and earliest-deadline-first.

• Hard real-time systems must meet every deadline (airbag controller); soft real-time systems give priority but tolerate occasional misses (video streaming).

A deadlock is a situation in which a set of processes are blocked forever, each waiting for a resource held by another.

A resource allocation graph shows processes and resources; a cycle indicates a possible deadlock (a certain deadlock if each resource has one instance).

• Prevention: make sure at least one of the four conditions can never hold (for example, request all resources at once, or number resources and request them in order).
• Avoidance: check each request and grant it only if the system stays in a safe state. The Banker's algorithm does this.
• Detection and recovery: allow deadlock, detect it periodically, then recover by terminating processes or preempting resources.

• Recovery: abort all deadlocked processes, abort one at a time until the cycle breaks, or preempt resources (choose a victim, roll back, avoid starvation).