Operating System

Designed and Presented by

Dr. Ayman Elshenawy Elsefy
Dept. of Systems & Computer Eng..
AL-AZHAR University
Email :
[email protected]

Chapter 6: Process Synchronization

1.1
 Module 6: Process Synchronization

• Background
• The Critical-Section Problem
• Peterson’s Solution
• Synchronization Hardware
• Semaphores
• Classic Problems of Synchronization
• Monitors
• Synchronization Examples
• Atomic Transactions
 Background
• Independent Process: cannot affect /affected by the other executing processes in
the system (Does not share data with any other process) .
• Cooperative Process: can affect /affected by the other executing processes in the
system:
• Shares data with other processes.
• Require an Inter-Process Communication (IPC) mechanism that allow them to
exchange data and Information using IPC models (Shared memory or Message
passing).
• Concurrent access to shared data may result in data inconsistency problem
(consumer-producer problem).
• Solution:
• A mechanisms to ensure the orderly execution of cooperating processes.
• A solution to the consumer-producer problem that fills all the buffers.
• Having an integer count that keeps track of the number of full buffers.
• Initially, count is set to 0.
• It is incremented / decremented by the producer after it produces/consumes
a buffer.
 Producer-consumer

• The producer and consumer routines are correct separately.

• They may not function correctly when executed concurrently.
• Let count = 5 and the producer and consumer processes execute
the statements “++count” and “--count” concurrently.
• Count may be 4, 5, or 6! And correct count == 5.
 Race Condition:
• counter++ • Several processes access and manipulate the
same data concurrently and the output depends
register1 = counter
on the particular order.
register1 = register1 + 1
counter = register1 • Different parts of the system manipulate
resources.
• counter– – • With the growth of multicore systems,
register2 = counter multithreaded applications.
register2 = register2 - 1 • Any changes that result from such activities not to
count = register2 interfere with one another

• Consider this execution interleaving with “count = 5” initially:

S0: producer execute register1 = counter {register1 = 5}
S1: producer execute register1 = register1 + 1 {register1 = 6}
S2: consumer execute register2 = counter {register2 = 5}
S3: consumer execute register2 = register2 - 1 {register2 = 4}
S4: producer execute counter = register1 {count = 6 }
If S4 and S5
S5: consumer execute counter = register2 {count = 4} are
reserved
 Critical Section Problem
• Critical section: is the segment of code of process used for changing common
variables, updating table, writing file, etc.
• The critical-section problem is to design a protocol that the processes can use to
cooperate.
• Each process must request permission to enter its critical section (execute
section of code called the entry section).
• The critical section may be followed by executing section of code exit
section.
• The remaining code is the remainder section.
 Critical Section Solution
• A solution to the critical-section problem must satisfy the following three
requirements:

• Kernel mode may be preemptive (a kernel-mode process will run until it

exits kernel mode) or non-preemptive ( because there is only one active
process at a time so it is free from race conditions).
• kernel code it self is subject to several possible race conditions.
• Example 1: a kernel data structure that have a list of all open files in the system
to be modified. If two processes were to open files concurrently.
• Example 2: data structures for maintaining memory allocation, It is up to kernel
developers to ensure that the OS is free from such race conditions.
 Peterson’s Solution
• Two process solution P1, P2
• The two processes share two variables int Turn & boolean Interest[2]:
• int turn : indicates whose turn it is to enter the critical section ( turn =1 means P1 is allowed
to execute in its critical section, turn =1 means P1 is allowed to execute in its critical section)
• The flag array interest[2 ) s used to indicate if a process is ready to enter its critical
section.
• Boolean interest[2] // interest [i] = true implies that process Pi is ready!
• For example, if flag[i] is true, this value indicates that Pi is ready to enter its critical
section.

• Pi enters its critical section only if either interest[j] == false or turn == i.

• if both processes can be executing in their critical sections at the same time, then
interest[0] == interest [1] == true. And the value of turn can be either 0 or 1
but cannot be both.
 Synchronization Hardware
• 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 systems OS using this not broadly
scalable
• Problems:
• Disabling interrupts on a multiprocessor can be time consuming.
• It is not wise to give the user the power of turning INT on and off ( one make it on and forget to turn it off)

• Modern machines provide special atomic hardware instructions

• Atomic = non-interruptable
• Either test memory word and set value
• Or swap contents of two memory words
Solution to Critical-section Problem Using Locks
 TestAndSet Instruction
• The important characteristic of this instruction is that it is executed atomically.
• If two get-and-set instructions are executed simultaneously (each on a different
CPU), they will be executed sequentially in some arbitrary order.
 Semaphore
• The hardware-based solutions to the critical-section problem are
complicated for application programmers to use.
• A synchronization tool called a semaphore can be used.
• A semaphore S contains an integer variable that initialized and
accessed only through two standard operations: acquire() and
release().
• Modifications to the integer value of the semaphore in the acquire()
and release() operations must be executed indivisibly (only one thread
can modify the semaphore at a time).
• OS often distinguish between counting and binary semaphores.
• Counting semaphore, The value can range over an unrestricted
domain.
• Binary semaphore The value can range only between 0 and 1 (known
mutex locks in some OS).
 Semaphore - Usage

Semaphore Implementation Using Java

 Semaphore Usage
1. Controlling access to a given resource consisting of a finite number of instances.
• The semaphore is initialized to the number of resources available.
• Each thread that wishes to use a resource performs an acquire().
• When a thread releases a resource, it performs a release() operation.
• When the count =0 means that all resources are being used (any thread that
wish to use a resource will block until the count becomes greater than 0).
2. solve various synchronization problems.
• Two concurrently running processes: P1 run S1 and P2 run S2.
• Suppose we require that S2 be executed only after S1 has completed.
• by letting P1 and P2 share a common semaphore synch, initialized to 0.

• Because synch is initialized to 0, P2 will execute S2 only after P1 has invoked

synch.release(),which is after statement S1 has been executed.
 Semaphore Implementation
• Problem: Requires busy waiting.
• While a process is in its critical section, any other process that tries
to enter its critical section must loop continuously in the entry code
(clear problem in a multiprogramming system).
• Busy waiting wastes CPU cycles that some other process might be
able to use productively.

• Solution
• Modify the acquire() and release() semaphore operations.
• Instead, the process continue looping it can block itself.
• The block operation places a process into a waiting queue of the
semaphore and change the state from running to waiting.
• The CPU scheduler can select another process to execute.
• The blocked process should be restarted when some other process
executes a release() operation using wakeup() operation (changes
the process from the waiting state to the ready state).
Semaphore – Solution to require Busy waiting

Semaphore Implementation Using Java

 Deadlock and starvation
• A system consisting of two processes, P0 and P1, each accessing two
semaphores, S and Q, set to the value 1

• Scenario:
• P0 executes S.acquire(), and P1 executes Q.acquire() ➔ S & Q=0.
• P0 executes Q.acquire(), it must wait until P1 executes Q.release().
• P1 executes S.acquire(), it must wait until P0 executes S.release().
• These operations cannot be executed, P0 and P1 are deadlocked.
• DeadLock:
• Two or more processes are waiting indefinitely for an event that can be caused
only by one of the waiting processes.
• indefinite blocking, or starvation
• A processes wait indefinitely within the semaphore (if we add and remove
processes from the list associated with a semaphore in (LIFO) order.
 Priority Inversion
• When a higher-priority process needs to modify kernel data that are
currently being accessed by a lower-priority processes.
• Since kernel data are typically protected with a lock, the higher-priority
process will have to wait for a lower-priority one to finish.
• The situation becomes more complicated if the lower-priority process is
preempted in favor of another process with a higher priority.

• Example: assume three processes, Lpriority < Mpriority < Hpriority. and
process H requires resource R, which is locked by process L.
• Process H would wait for L to finish using resource R.
• If process M becomes runnable, thereby preempting process L.
• Indirectly, a process with a lower priority—process M—has affected how
long process H must wait for L to use resource R.
• Solution:
• Use only one priority.
• The Process that access the resource inherit the high priority
(Priority inheritance Protocol)
 Classical 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
• N buffers, each can hold one item
• Semaphore mutex initialized to the value 1
• Semaphore full initialized to the value 0
• Semaphore empty initialized to the value N
 Dining-Philosophers Problem
• 5 philosophers (PH) spend their lives thinking and
eating. They share a circular table with five chairs,
each belonging to one PH.
• In the center of the table is a bowl of rice, and a
five single chopsticks
• When a PH thinks, she does not interact with
others.
• When he gets hungry and tries to pick up the two
chopsticks that are closest to her.
• A PH may pick up only one chopstick at a time.
• He cannot pick up a chopstick that is already in
the hand of a neighbor.
• When a hungry PH has both her chopsticks at the
same time, she eats without releasing her
chopsticks. Representation of the need
to allocate several resources
• When she is finished eating, she puts down both
of her chopsticks and starts thinking again. among several processes in a
deadlock-free and starvation-
free manner.
 Dining-Philosophers Problem-solution
• Represent each chopstick with a semaphore.
• A PH tries to grab the chopstick by executing an acquire() operation;
• she releases a chopstick by executing the release() operation.

This Solution Have A

Problems & not
Acceptable it has the
possibility of creating
a deadlock
 Dining-Philosophers Problem-solution
• Suppose that all five philosophers become hungry
simultaneously and each grabs her left chopstick.
• All the elements of chopstick will now be equal to 0.
• When each philosopher tries to grab her right chopstick, she will
be delayed forever.
• Possible solutions by placing restrictions on the philosophers:
1. Allow at most four philosophers to be sitting simultaneously at the
table.
2. Allow a philosopher to pick up her chopsticks only if both
chopsticks are available (note that she must pick them up in a
critical section).
3. Use an asymmetric solution; for example, an odd philosopher picks
up first her left chopstick and then her right chopstick, whereas an
even philosopher picks up her right chopstick and then her left
chopstick.
End of Chapter 6