Transcript Week-10

Module 6: Process Synchronization
Operating System Concepts with Java – 8th Edition
6.1
Silberschatz, Galvin and Gagne ©2009
Semaphore Implementation with
no Busy waiting
 Processes block themselves instead of busy waiting
 Unblocked when some other process releases
semaphore
 Maintain a waiting queue for each semaphore

value (of type integer)

pointer to next record in the list
 Two operations:

block – place the process invoking the operation on the
appropriate waiting queue.

wakeup – remove one of processes in the waiting queue
and place it in the ready queue.
Operating System Concepts with Java – 8th Edition
6.2
Silberschatz, Galvin and Gagne ©2009
Semaphore Implementation with
no Busy waiting (Cont.)
 Implementation of acquire():
 Implementation of release():
Operating System Concepts with Java – 8th Edition
6.3
Silberschatz, Galvin and Gagne ©2009
Semaphore Implementation with
no Busy waiting (Contd.)
 Semaphore value can be negative
 Can use any order for waking up blocked processes

Some might cause unbounded wait
 Important to ensure atomicity of acquire() and
release()
 Disable interrupts during acquire() and release()

Works for single processor environments
 Use software solutions to the critical sections
problem
Operating System Concepts with Java – 8th Edition
6.4
Silberschatz, Galvin and Gagne ©2009
Deadlocks
 Deadlock -- Two or more processes are waiting
indefinitely for an event that can be triggered by only
one of the waiting processes
 Let S and Q be two semaphores initialized to 1
 Solutions to be discussed in next chapter
 Starvation – Process waiting indefinitely within a
semaphore
Operating System Concepts with Java – 8th Edition
6.5
Silberschatz, Galvin and Gagne ©2009
Priority Inversion
 Semaphores can mess up process priorities
 A lower priority process may hold a semaphore that a
higher priority process needs
 A more complex scenario

Low, medium and high priority processes

Low priority process holds a semaphore, high priority process
needs to acquire

Low priority process is pre-empted by medium priority process
that does not need the semaphore
 Priority-Inheritance protocol

A process holding a semaphore will inherit the highest priority
that is waiting on the resource
Operating System Concepts with Java – 8th Edition
6.6
Silberschatz, Galvin and Gagne ©2009
Classical Problems of Synchronization
 Bounded-Buffer Problem
 Readers and Writers Problem
 Dining-Philosophers Problem
Operating System Concepts with Java – 8th Edition
6.7
Silberschatz, Galvin and Gagne ©2009
Bounded-Buffer Problem
 Buffer with ‘N’ slots
 Each slot holds one item
 Producers continuously generate items and want to
insert into the buffer

Must wait if buffer has no empty slots
 Consumers continuously remove items from the buffer

Must wait if buffer has no items
 Only one producer/consumer should be accessing the
buffer at any given time
Operating System Concepts with Java – 8th Edition
6.8
Silberschatz, Galvin and Gagne ©2009
Bounded-Buffer Solution Outline
 Semaphore mutex initialized to the value 1

mutex is for synchronization (prevent simultaneous
access to shared buffer)
 Semaphore full initialized to the value 0

full indicates how many items are there in the buffer
 Semaphore empty initialized to the value N

empty indicates number of empty slots in buffer
Operating System Concepts with Java – 8th Edition
6.9
Silberschatz, Galvin and Gagne ©2009
Bounded-buffer producer
Operating System Concepts with Java – 8th Edition
6.10
Silberschatz, Galvin and Gagne ©2009
Bounded-buffer consumer
Operating System Concepts with Java – 8th Edition
6.11
Silberschatz, Galvin and Gagne ©2009
Bounded-buffer factory
Operating System Concepts with Java – 8th Edition
6.12
Silberschatz, Galvin and Gagne ©2009
Bounded-Buffer
Operating System Concepts with Java – 8th Edition
6.13
Silberschatz, Galvin and Gagne ©2009
Bounded-Buffer insert()
Operating System Concepts with Java – 8th Edition
6.14
Silberschatz, Galvin and Gagne ©2009
Bounded-buffer remove()
Operating System Concepts with Java – 8th Edition
6.15
Silberschatz, Galvin and Gagne ©2009
Readers-Writers Problem
 A data set is shared among a number of concurrent
processes

Readers – only read the data set; they do not perform any
updates

Writers – can both read and write
 Problem

Allow multiple readers to read at the same time

Only single writer can access the shared data at the same
time

No simultaneous reads and writes allowed
Operating System Concepts with Java – 8th Edition
6.16
Silberschatz, Galvin and Gagne ©2009
Readers-Writers Solution
 readerCount – Integer indicating how many readers are currently
reading the shared data

Manipulated only by readers

Initialized to zero
 Semaphore mutex initialized to 1

Synchronizing access to the readerCount variable (ensuring only
one reader is manipulating readerCount)
 Semaphore db initialized to 1

Synchronizing access to the data item

Ensuring only one writer is in the critical region or any number of
readers
Operating System Concepts with Java – 8th Edition
6.17
Silberschatz, Galvin and Gagne ©2009
Readers-Writers Problem
 Interface for read-write locks
Operating System Concepts with Java – 8th Edition
6.18
Silberschatz, Galvin and Gagne ©2009
Writer Structure
Operating System Concepts with Java – 8th Edition
6.19
Silberschatz, Galvin and Gagne ©2009
Reader Structure
Operating System Concepts with Java – 8th Edition
6.20
Silberschatz, Galvin and Gagne ©2009
Shared DB
Operating System Concepts with Java – 8th Edition
6.21
Silberschatz, Galvin and Gagne ©2009
ReadLock Methods
Operating System Concepts with Java – 8th Edition
6.22
Silberschatz, Galvin and Gagne ©2009
WriteLock Methods
Operating System Concepts with Java – 8th Edition
6.23
Silberschatz, Galvin and Gagne ©2009
Dining Philosophers Problem
 5 philosopher seated on a round table
 Each philosopher is in a loop of alternate thinking
and eating
 5 chopsticks

Each philosopher has one on each side
 Philosopher can eat when she has two chopsticks

Picks up one chopstick after another

Puts them back one after another
 Array of semaphores (1 for each chopstick)
Operating System Concepts with Java – 8th Edition
6.24
Silberschatz, Galvin and Gagne ©2009
Dining-Philosophers Problem
 Semaphore chopStick [5] initialized to 1
Operating System Concepts with Java – 8th Edition
6.25
Silberschatz, Galvin and Gagne ©2009
Philosopher Structure
Operating System Concepts with Java – 8th Edition
6.26
Silberschatz, Galvin and Gagne ©2009
Deadlocks
 What if all philosophers acquire their right (or left)
chopstick
 Nobody can progress – Deadlock !!!
 Solutions:

Allow philosopher to pick up chopsticks if both
are available (i.e., guard the array of
semaphores in a critical section)

Asymmetric solution – Odd philosophers
acquire left chopstick first whereas even
philosophers acquire right chopstick first
Operating System Concepts with Java – 8th Edition
6.27
Silberschatz, Galvin and Gagne ©2009
Problems with Semaphores

Correct use of semaphore operations:

Correct  mutex.acquire() …. mutex.release()

Incorrect  mutex.acquire () or mutex.release() (or both)

Omitting either mutex.acquire() or mutex.release()
Operating System Concepts with Java – 8th Edition
6.28
Silberschatz, Galvin and Gagne ©2009
Monitors
 Refer to the handout given in class.
If you do not have the handout,
please see the instructor.
Operating System Concepts with Java – 8th Edition
6.29
Silberschatz, Galvin and Gagne ©2009
End of Chapter 6
Operating System Concepts with Java – 8th Edition
6.30
Silberschatz, Galvin and Gagne ©2009