Operating Systems 6-7

Critical Section

• A code segment where processes access shared resources that can lead to race condition if modified simultaneously

• Ex: memory, variables, files

Critical Section Problem

• Each process must ask permission to enter critical section in entry section, may follow critical section with exit section, then remainder section

Requirements for solution to critical-section problem

1. Mutual Exclusion

2. Progress

3. Bounded Waiting

Mutual Exclusion

• If process Pi is executing in its critical section,
  then no other processes can be executing in their critical sections

Progress

• If nobody is in the critical section and some processes want to enter, the system must decide who gets to enter next without unnecessary delay.

Bounded Waiting

• Once a process requests entry, there must be a limit on how many times other processes can enter before it gets its turn.

Interrupt-based Solution

• Entry section: disable interrupts

• Exit section: enable interrupts

Two process solution

• Assume that the load and store machine-language
  instructions are atomic; that is, cannot be interrupted

• The two processes share one variable:

  • int turn;

• The variable turn indicates whose turn it is to enter the
  critical section

Peterson’s Solution

• Assume that the load and store machine-language
  instructions are atomic; that is, cannot be interrupted

• The two processes share two variables:

  • int turn;

  • boolean flag[2]

• Variable turn indicates whose turn to enter the
  critical section

• The flag array is used to indicate if a process is ready to
  enter the critical section.

Mutex Locks

• Hardware solutions are complicated and generally inaccessible to application programmers

• Boolean variable indicating if lock is available or not

• Protect a critical section by

  • First acquire() a lock

  • Then release() the lock

• But this solution requires busy waiting

Semaphore

• Synchronization tool that provides more sophisticated ways (than Mutex locks) for processes to synchronize their activities.

• S – integer variable

• Can only be accessed via two atomic operations

  • wait() and signal()

Counting semaphore

• integer value can range over
  an unrestricted domain

Binary semaphore

• integer value can range only between 0 and 1

  • Same as a mutex lock

Semaphore Implementation

• Must guarantee that no two processes can execute the wait() and signal() on the same semaphore at the same time

• Thus, becomes the critical section problem
  where the wait and signal code are placed in the critical
  section

Semaphore Implementation with no Busy waiting

• With each semaphore there is an associated waiting queue

• Each entry in a waiting queue has two data items:

  • Value (of type integer)

  • Pointer to next record in the list

Block Operation

• Place the process invoking the operation on the
  appropriate waiting queue

Wakeup Operation

• Remove one of processes in the waiting queue
  and place it in the ready queue

Liveness

• Refers to a set of properties that a system must satisfy to ensure processes make progress.

• Means that a process will eventually be able to make progress and won’t be stuck waiting to enter CS forever.

Deadlock

• 2 or more processes are waiting indefinitely for an
  event that can be caused by only one of the waiting processes

Starvation

• A process may never be removed from the semaphore queue in which it is suspended

Priority Inversion

• Scheduling problem when lower-priority process
  holds a lock needed by higher-priority process