OS Chapter 6

Chapter 6\u00A0Process Synchronization

Background

Concurrent access to shared data may result in data inconsistency

Maintaining data consistency requires mechanisms to ensure the orderly execution of cooperating processes

consumer-producer problem

Suppose that we wanted to provide a solution to the consumer-producer problem that fills all the buffers.\u00A0

We can do so by having an integer count that keeps track of the number of full buffers. \u00A0

Producer

while (true) {\u00A0 \u00A0 \u00A0\u00A0 \u00A0 \u00A0 \u00A0 \u00A0 /* \u00A0produce an item and put in nextProduced \u00A0*/\t \u00A0 \u00A0 \u00A0while (counter == BUFFER_SIZE)\t\t\t; // do nothing\t\t \u00A0 \u00A0 \u00A0 buffer [in] = nextProduced;\t\t \u00A0 \u00A0 \u00A0 in = (in + 1) % BUFFER_SIZE;\t\t \u00A0 \u00A0 \u00A0 counter++;} \u00A0\u00A0

Consumer

while (true) \u00A0{\u00A0 \u00A0 \u00A0 \u00A0while (counter == 0)\u00A0 \u00A0 \u00A0 \u00A0; // do nothing\u00A0 \u00A0 \u00A0 \u00A0nextConsumed = \u00A0buffer[out];\u00A0 \u00A0 \u00A0 \u00A0 out = (out + 1) % BUFFER_SIZE;\u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0counter--;/* \u00A0consume the item in nextConsumed \u00A0*/}

Race Condition

counter++ could be implemented as\u000B \u00A0 \u00A0 register1 = counter\u000B \u00A0 \u00A0 register1 = register1 + 1\u000B \u00A0 \u00A0 counter = register1counter-- could be implemented as\u000B \u00A0 \u00A0 register2 = counter\u000B \u00A0 \u00A0 register2 = register2 - 1\u000B \u00A0 \u00A0 count = register2Consider this execution interleaving with “count = 5” initially:S0: producer execute register1 = counter \u00A0 {register1 = 5}\u000BS1: producer execute register1 = register1 + 1 \u00A0 {register1 = 6} \u000BS2: consumer execute register2 = counter \u00A0 {register2 = 5} \u000BS3: consumer execute register2 = register2 - 1 \u00A0 {register2 = 4} \u000BS4: producer execute counter = register1 \u00A0 {count = 6 } \u000BS5: consumer execute counter = register2 \u00A0 {count = 4}

The Critical-Section Problem

Each process has critical section that is segment of code

Critical section problem is to design protocol to solve this

Solution to Critical-Section Problem

Bounded Waiting - \u00A0A bound must exist on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is grantedAssume that each process executes at a nonzero speed\u00A0No assumption concerning relative speed of the n processes

Peterson’s Solution

The two processes share two variables:int turn;\u00A0Boolean flag[2]

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

The flag array is used to indicate if a process is ready to enter the critical section.\u00A0flag[i] = true implies that process Pi is ready!

do {\u00A0\t\tflag[i] = TRUE;\u00A0\t\tturn = j;\u00A0\t\twhile (flag[j] && turn == j);\u00A0\t\tcritical section\u00A0\t\tflag[i] = FALSE;\u00A0\t\tremainder section\u00A0\t} while (TRUE);\u00A0

Provable that\u00A0Mutual exclusion is preservedProgress requirement is satisfiedBounded-waiting requirement is met

Synchronization Hardware

concept

Many systems provide hardware support for critical section code

Uniprocessors – could disable interrupts

Currently running code would execute without preemption

Generally too inefficient on multiprocessor systemsOperating systems using this not broadly scalable

Modern machines provide special atomic hardware instructions

Atomic = non-interruptable

Either test memory word and set value

swap contents of two memory words

Solution to Critical-section \u000BProblem Using Locks

do {\u00A0\t\tacquire lock\u00A0\t\t\tcritical section\u00A0\t\trelease lock\u00A0\t\t\tremainder section\u00A0\t} while (TRUE);\u00A0

TestAndSet Instruction

boolean TestAndSet (boolean *target)\u00A0 \u00A0 \u00A0 \u00A0 \u00A0 {\u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0boolean rv = *target;\u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0*target = TRUE;\u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0return rv:\u00A0 \u00A0 \u00A0 \u00A0 \u00A0 }

Solution using TestAndSet

do {\u00A0 \u00A0 \u00A0 \u00A0while ( TestAndSet (&lock ))\u00A0 \u00A0 \u00A0 \u00A0 ; // do nothing\u00A0 \u00A0 \u00A0 \u00A0 // \u00A0 \u00A0critical section\u00A0 \u00A0 \u00A0 \u00A0 lock = FALSE;\u00A0 \u00A0 \u00A0 \u00A0// \u00A0 \u00A0 \u00A0remainder section\u00A0} while (TRUE);

Swap Instruction

Solution using Swap

Shared Boolean variable lock initialized to FALSE; Each process has a local Boolean variable key

Semaphores

Introduction

Synchronization tool that does not require busy waiting\u00A0

Semaphore S – integer variable

Two standard operations modify S: wait() and signal()

Can only be accessed via two indivisible (atomic) operations

wait (S) {\u00A0\u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0while S = 0\t\t \u00A0 \u00A0 \u00A0 \u00A0 \u00A0; // no-op\u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 S--;\u00A0 \u00A0 \u00A0 }signal (S) {\u00A0\u00A0 \u00A0 \u00A0 \u00A0 S++;\u00A0 \u00A0 \u00A0}

Semaphore as \u000BGeneral Synchronization Tool

Counting semaphore – integer value can range over an unrestricted domain

Binary semaphore – integer value can range only between 0 \u000Band 1; can be simpler to implementAlso known as mutex locks

Can implement a counting semaphore S as a binary semaphore

Provides mutual exclusion

Semaphore mutex; \u00A0 \u00A0// \u00A0initialized to 1do {\twait (mutex);\u00A0 \u00A0 \u00A0 \u00A0 \u00A0// Critical Section\u00A0 \u00A0 \u00A0signal (mutex);\t\t// remainder section} while (TRUE);

Semaphore Implementation

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

Note that applications may spend lots of time in critical sections and therefore this is not a good solution

Semaphore Implementation \u000Bwith no Busy waiting

With each semaphore there is an associated waiting queue

Each entry in a waiting queue has two data items:\u00A0value (of type integer)\u00A0pointer to next record in the list

Two operations:block – place the process invoking the operation on the appropriate waiting queuewakeup – remove one of processes in the waiting queue and place it in the ready queue

Deadlock and Starvation

Deadlock – two or more processes are waiting indefinitely for an event that can be caused by only one of the waiting processes

Starvation – indefinite blocking \u00A0A 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 processSolved via priority-inheritance protocol

Classic Problems of Synchronization

Classical problems used to test newly-proposed synchronization schemes

Bounded-Buffer Problem

Readers and Writers Problem

Dining-Philosophers Problem

Bounded-Buffer Problem ( producer-consumer problem)

The structure of the producer process\tdo \u00A0{\u000B\u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0// \u00A0 produce an item in nextp\u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0wait (empty);\u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0wait (mutex);\u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0// \u00A0add the item to the \u00A0buffer\u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 signal (mutex);\u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 signal (full);\u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0} while (TRUE);

The structure of the consumer process\u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0do {\u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 wait (full);\u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 wait (mutex);\u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0// \u00A0remove an item from \u00A0buffer to nextc\u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 signal (mutex);\u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 signal (empty);\u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 // \u00A0consume the item in nextc\u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0} while (TRUE);

Readers-Writers Problem

A data set is shared among a number of concurrent processesReaders – only read the data set; they do not perform any updatesWriters \u00A0 – can both read and write\u000BProblem – allow multiple readers to read at the same timeOnly one single writer can access the shared data at the same timeSeveral variations of how readers and writers are treated – all involve prioritiesShared DataData setSemaphore mutex initialized to 1Semaphore wrt initialized to 1Integer readcount initialized to 0

The structure of a writer process\u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 do {\u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 wait (wrt) ;\u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0// \u00A0 \u00A0writing is performed\u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 signal (wrt) ;\u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0} while (TRUE);

The structure of a reader process\tdo {\u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0wait (mutex) ;\u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0readcount ++ ;\u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0if (readcount == 1) \u00A0\t\t\t \u00A0 \u00A0 \u00A0 \u00A0 \u00A0wait (wrt) ;\u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0signal (mutex)\u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0// reading is performed\u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 wait (mutex) ;\u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 readcount \u00A0- - ;\u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 if (readcount \u00A0== 0) \u00A0\t\t\t \u00A0 \u00A0 \u00A0 \u00A0 signal (wrt) ;\u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 signal (mutex) ;\u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 } while (TRUE);

The structure of Philosopher i:do \u00A0{\u00A0\u00A0 \u00A0 \u00A0 \u00A0 \u00A0 wait ( chopstick[i] );\t \u00A0 \u00A0 wait ( chopStick[ (i + 1) % 5] );\t \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 // \u00A0eat\t \u00A0 \u00A0 signal ( chopstick[i] );\t \u00A0 \u00A0 signal (chopstick[ (i + 1) % 5] );\u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0 \u00A0// \u00A0think} while (TRUE);

Deadlock\u00A0Starvation

Monitors