[OS]Process Synchronization and Mutual Exclusion

Process Synchronization

• Multiple programming system
• Synchronization

Asynchronous and Concurrent

• Asynchronous
• Concurrent

Terminologies

• Shared data(Critical data)

• Critical section

  Mutual Exclusion

  Mutual Exclusion Methods

• Mutual exclusion primitives
  • enterCS( ) primitive
  • exitCS( ) primitive

Requirements for ME primitives

• Mutual exclusion
• Progress
• Bounded waiting

Mutual Exclusion Solution

• SW solutions
  • Dekker’s algorithm, Peterson’s algorithm
  • Dijkstra’s algorithm
• HW solution
  • TestAndSet (TAS) instruction
• OS supported SW solution
  • Spinlock
  • Semaphore
  • Eventcount/sequencer
• language-Level solution
  • Monitor

SW Solutions

• N-Process Mutual Exclusion
  • Dijkstra
  • Knuth
  • Lamport
  • Brinch Hansen
• SW solution’s weakness
  • Slow
  • Complex
  • Busy waiting
    • Inefficient

Synchornization Hardware

• TestAndSet (TAS) instruction
• Machine instruction
  • Atomicity, Indivisible
• Busy waiting
  • Inefficient

Me with TAS Instruction

• N-Proc4ess mutual exclusion

do
{
    waiting[i] = true;
    key = true;
    while (waiting[i] && key)
        key = TestAndSet(&lock);
    waiting[i] = false;

    j = (i + 1) % n;
    while ((j != i) && !waiting[j])
        j = (j + 1) % n;
    if (j == i)
        lock = false;
    else
        waiting[j] = false;
} while (true);

HW Solution

• Strength
  • Simple
• Weakness
  • Busy waiting
    • Inefficient

OS supported SW solutions

Spinlock

• Available on multiprocessor system only
• Busy waiting

Semaphore

• No busy waiting
• starvation problem

Eventcount/Sequencer

• No busy waiting
• No starvation
• More low-level control is possible than semaphore.

Hight-level Mechanism

• Monitor
  • Strength
    • Eazy to use
    • low Deadlock error
  • Weakness
    • Available in supported languages only

---

Reference

Process Synchronization and Mutual Exclusion