1
Process Synchronization
- A cooperating process is one that can affect or be affected by other
processes executing in the system.
- Cooperating processes can either
- directly share a logical address space (that is, both code and data)
- or be allowed to share data only through files or messages.
Concurrent access to shared data may result in data inconsistency.
The orderly execution of cooperating processes that share a logical address
space, So that data consistency is maintained.
Producer Consumer Problem
- A producer process produces information that is consumed by a
consumer process.
- One solution to the producer-consumer problem uses shared memory.
- To allow producer and consumer processes to run concurrently, we must
have available a buffer of items that can be filled by the producer and
emptied by the consumer.
- This buffer will reside in a region of memory that is shared by the
producer and consumer processes.
- A producer can produce one item while the consumer is consuming
another item.
- The producer and consumer must be synchronized, so that the consumer
does not try to consume an item that has not yet been produced.
● Race condition: The situation where several processes access – and
manipulate shared data concurrently. The final value of the shared
data depends upon which process finishes last.
● To prevent race conditions, concurrent processes must be
synchronized.
Producer Consumer Problem
Problem: Given the common fixed-size buffer, the task is to make sure that the
producer can’t add data into the buffer when it is full and the consumer can’t
remove data from an empty buffer.
Solution: The producer is to either go to sleep or discard data if the buffer is full.
The next time the consumer removes an item from the buffer, it notifies the
2
producer, who starts to fill the buffer again. In the same manner, the consumer
can go to sleep if it finds the buffer to be empty. The next time the producer
puts data into the buffer, it wakes up the sleeping consumer.
Producer code
Consumer code
3
The Critical-Section Problem
- Consider a system consisting of n processes { Po, P1, ..., Pr}.
- Each process has a segment of code, called a critical section,
in which the process may be changing common variables, updating a table,
writing a file, and so on.
When one process is executing in its critical section, no other process is to be
allowed to execute in its critical section.
That is, no two processes are executing in their critical sections at the same time.
The critical-section problem is to design a protocol that the processes can use to
cooperate.
4
● There are n processes that are competing to use some shared data
● Each process has a code segment, called critical section, in which the shared
data is accessed.
● Each process must ask permission to enter critical section in entry section,
may follow critical section with exit section, then remainder section
Problem – ensure that when one process is executing in its critical section, no other
process is allowed to execute in its critical section.
5
Requirements to be satisfied for a Solution to the Critical-Section Problem:
1. Mutual Exclusion - If process Pi is executing in its critical section, then no other
processes can be executing in their critical sections.
2. Progress - If no process is executing in its critical section and there exist some
processes that wish to enter their critical section, then the selection of the processes
that will enter the critical section next cannot be postponed indefinitely.
3. Bounded Waiting - A 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 granted.
Peterson’s Solution
● Good algorithmic description of solving the problem
● Two process 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]
● 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. flag[i] = true implies that process Pi is ready!
Code:
6
Steps:
● In the solution i represents Process P1 and j represents process P2. Initially the
flags are false.
● When a process wants to execute it’s critical section, it sets it’s flag to true and
turn as the index of the other process.
● This means that the process wants to execute but it will allow the other
process to run first. The process performs busy waiting until the other process
has finished it’s own critical section.
● After this the current process enters it’s critical section and accesses the
shared variables.
● After completing the critical section, it sets it’s own flag to false, indication it
does not wish to execute anymore.
1. Mutual exclusion is preserved
i. Pi enters CS only if: either flag[j] = false or turn = i
2. Progress requirement is satisfied
i. Progress is satisfied as any waiting process can enter their critical
section as soon as existing process in critical section sets its own
flag to false.
3. Bounded-waiting requirement is met
7
Semaphres
sinphy a Vanialle wbid
-A semaphen is a a
bebutn thoead
negikie amdd shared
olve .the Cs
-DE is wed to s in He
synhanszlan
auhieve
-Ato achieve prouss
pro us 3
alliproussing onwironmiit
ingo Vaiabla,that
ASemaphe aused ony
initiaizaon, is
opent from standand eie oferatoy:
thraugh tuo
weltt) k sgn) Sijnal) - > i n e m e t
wait (S) signad (s)
opeition
S--)
shad
Vanialle thut
Semaphne
the pruuss
to it Cs. &
getin
prouss want to
- Jf one Vele,it s is
<eo
S
it has o hek wndstd that
eoei g
Some proLeSS is
the sh
I :
ase
S-
dent| it shos
ses.
te shan Prouss tte senaphoe ahe is
7esoey devent
do, that it ang othn proUas
twats to etCs Iwe shad
the decraPssilde
rusos may be basel
Signde Sigj(sampae S) do
S+t
3
-he mudficion to He jdoyen vade oft the
Semphene the wa'to, amd signad)
eseotd indivsit
mst be esetd
mem One prouss
prruss
Can thha Sane
ot Semapne
I: Binarg Semmaohne :
The
ase | ( )
No otw ploless ane
Assue S -I
Precss Ce) hih wady to aus Cs. wil
pfrcala wat()
But so o it wont he phithed
lome bak
it maley the S+t S=l
will
Its Vabhe Cen 7anye ove
ove nesbitl
domain
Ex. Resom R-Reso
Sne R
S-- )A
Counting Semaphore
1. Definition
o A semaphore used to control access to multiple instances of a
resource.
o Value of semaphore = number of available resources.
2. Key Operations
o wait(S): Decreases semaphore value by 1. If value < 0, process
waits.
o signal(S): Increases semaphore value by 1. Wakes up waiting
process (if any).
3. How it works
o Initial value = total number of resources.
o Each process must wait(S) before using a resource.
o After finishing, process does signal(S) to release the resource.