Operating Systems

Synchronization
 Hardware based solution

2
 Hardware synchronization
Synchronization hardware i.e. hardware-based solution for the critical section problem
which introduces the hardware instructions that can be used to resolve the critical section
problem effectively. Hardware solutions are often easier and also improves the efficiency of
the system.
The hardware-based solution to critical section problem is based on a simple tool
i.e. lock. The solution implies that before entering into the critical section the process must
acquire a lock and must release the lock when it exits its critical section. Using of lock also
prevent the race condition.

3
 Hadware synchronization
• The hardware synchronization provides two kinds of hardware instructions that
are TestAndSet and Swap. We will discuss each of the instruction briefly. But before
jumping on to the instructions let us discuss what conditions they must verify to resolve
the critical section problem.
1. Mutual Exclusion: The hardware instruction must verify that at a point in time only one
process can be in its critical section.
2. Bounded Waiting: The processes interested to execute their critical section must not wait
for long to enter their critical section. (Not preserved)
3. Progress: The process not interested in entering its critical section must not block other
processes from entering into their critical section.

4
 Hardware synchronization
• In Test and Set the shared variable is a lock that is initialized to false.
• There is a shared lock variable which can have value 0 or 1
• Before a process enters it enquires about the lock .
• If it is locked it keeps on waiting till it becomes free
• If it is set to 0 then process will take lock and executes in critical section.
• Example

5
6
7
 Semaphores
• Semaphore is simply a variable that is non-negative and
shared between threads. A semaphore is a signaling
mechanism, and a thread that is waiting on a semaphore
can be signaled by another thread. It uses two atomic
operations, 1) Wait, and 2) Signal for the process
synchronization.
• A semaphore either allows or disallows access to the
resource, which depends on how it is set up.
• Wait (P): an operation that decrements the integer value of a semaphore by
one. If the integer value becomes negative, the semaphore blocks the entity
that executed the wait operation and adds it to the semaphore queue. If not,
the entity receives an access unit and can enter in the critical section
• Signal (V): an operation that increments the integer value of a semaphore by
one
• However, it is relevant to highlight that, although providing mutual exclusion,
binary semaphores aren’t the same as mutexes. Semaphores are, by definition, signaling mechanisms,
while mutexes are locking mechanisms.

8
 Characteristics
• It is a mechanism that can be used to provide
synchronization of tasks.
• It is a low-level synchronization mechanism.
• Semaphore will always hold a non-negative integer value.

9
 • A semaphore is an integer variable that is useful for solving a variety of synchronization
problems. It imposes deliberate constraints that help programmers avoid errors.
Moreover, it makes the solution more organized, making the programs portable and
efficient. It can be accessed only through two standard atomic operations: wait() and
signal(). An entity is the one that tries to access a shared resource. The entity can be a
process or a thread.
• There are certain requirements, which guarantees synchronization, they are :
• Mutual Exclusion
• Progress
• Bounded wait

10
 Types of Semaphores

•The two common kinds of semaphores are

•Counting semaphores
•Binary semaphores.

11
 Binary semaphore
1. A Binary Semaphore is a semaphore whose integer value range over 0 and 1.
2. It is nothing, but similar to a lock, with two values: 0 and 1. Here 0 means busy, while 1
means free.
3. The idea behind using a binary semaphore is that, it allows only one process at a time to
enter the critical section(thus allowing it to access the shared resource).
4. Here, 0 represents that a process or a thread is in the critical section(i.e. it is accessing the
shared resource), while the other process or thread should wait for it to complete. On the
other hand, 1 means that no process is accessing the shared resource, and the critical section
is free.
5. It guarantees mutual exclusion since no two processes can be in the critical section at any
point in time.
6. Since it is just a variable, which holds an integer value, it cannot guarantee bounded waiting.
It might happen, that a process may never get a chance to enter the critical section, which
may lead to its starvation. And we don’t want that.

12
 Counting Semaphore
1. A counting semaphore is a semaphore that has multiple values of the counter.
The value can range over an unrestricted domain.
2. It is a structure, which comprises a variable, known as a semaphore variable that
can take more than two values and a list of task or entity, which is nothing but
the process or the thread.
3. The value of the semaphore variable is the number of process or thread that is to
be allowed inside the critical section.
4. The value of the counting semaphore can range between 0 to N, where N is the
number of the number of process which is free to enter and exit the critical
section.
5. As mentioned, a counting semaphore can allow multiple processes or threads to
access the critical section, hence mutual exclusion is not guaranteed.
6. Since multiple instances of process can access the shared resource at any time,
counting semaphore guarantees bounded wait. Using such a semaphore, a
process which enters the critical section has to wait for the other process to get
inside the critical section, implying that no process will starve.

13
 • Semaphores are typically used to coordinate
access to resources, with the semaphore count
initialized to the number of free resources.
Threads then atomically increment the count when
resources are added and atomically decrement the
count when resources are removed.
• When the semaphore count becomes zero, no more
resources are present. Threads that try to
decrement the semaphore when the count is zero
block until the count becomes greater than zero.

14
 Difference b/w semaphores

15
 Issue
• Busy waiting
• Deadlocks

16
 Semaphore Numerical
• A counting semaphore S is initialized to 10. Then, 6 P operations
and 4 V operations are performed on S. What is the final value of
S?
• We know-
• P operation also called as wait operation decrements the value of semaphore variable by 1.
• V operation also called as signal operation increments the value of semaphore variable by 1.
•
• Thus,
• Final value of semaphore variable S
• = 10 – (6 x 1) + (4 x 1)
• = 10 – 6 + 4

• =8

17
 Classical problems of
synchronization
• Bound-Buffer problem
. Dining Philosophers problem
.Readers and writers problem

18
 Bounded Buffer Problem
• Also known as the Producer-Consumer problem. In this
problem, there is a buffer of n slots, and each buffer is
capable of storing one unit of data. There are two processes
that are operating on the buffer – Producer and Consumer.
The producer tries to insert data and the consumer tries to
remove data.
• If the processes are run simultaneously they will not yield
the expected output.
• The solution to this problem is creating two semaphores, one full and the other
empty to keep a track of the concurrent processes.

19
 • Producer: creates copies of a resource.
• • Consumer: uses up copies of a resource.

• • Buffers: used to hold information after producer has

created it but before consumer has used it.
Signaling: keeping control of producer and consumer (e.g.,
preventing overrun of the producer).
Constraints (definition of what is ‘‘correct’’).

20
 Synchronization with producer and
consumer
• A bounded buffer with capacity N has can store N data items. The places used to store
the data items inside the bounded buffer are called slots. Without proper
synchronization the following errors may occur.
• The producers doesn’t block when the buffer is full.
• A Consumer consumes an empty slot in the buffer.
• A consumer attempts to consume a slot that is only half-filled by a producer.
• Two producers writes into the same slot.
• Two consumers reads the same slot.
• And possibly more …

21
 Implemetation

• To implement the bounded buffer a finite size array in

memory is shared by a number for producer and consumer
threads.
• Producer threads “produce” an item and place the item in the
array.
• Consumer threads remove an item from the array and
“consume” it.
• In addition to the shared array, information about the state of
the buffer must also be shared.
• Which slots in buffer are free?
• To which slot should the next data item be stored?
• Which parts of the buffer are filled?

• From which slot should the next data item be read?

22
 Synchronize producer and consumer
• Producers must block if the buffer is full. Consumers must block if the
buffer is empty. Two counting semaphores can be used for this.
• Use one semaphore named empty to count the empty slots in the
buffer.
• Initialise this semaphore to N.

• A producer must wait on this semaphore before writing to the

buffer.
• A consumer will signal this semaphore after reading from the buffer.
• Use one semaphore named data to count the number of data items
in the buffer.
• Initialise this semaphore to 0.
• A consumer must wait on this semaphore before reading from the
buffer.
• A producer will signal this semaphore after writing to the buffer.

23
 Reader writer problem
• The readers-writers problem relates to an object such as a file that is shared between multiple
processes. Some of these processes are readers i.e. they only want to read the data from the object
and some of the processes are writers i.e. they want to write into the object.
• The readers-writers problem is used to manage synchronization so that there are no problems
with the object data. For example - If two readers access the object at the same time there is no
problem. However if two writers or a reader and writer access the object at the same time, there
may be problems.
• To solve this situation, a writer should get exclusive access to an object i.e. when a writer is
accessing the object, no reader or writer may access it. However, multiple readers can access the
object at the same time.
• This can be implemented using semaphores

24
 • The Problem Statement
• There is a shared resource which should be accessed by
multiple processes. There are two types of processes in
this context. They are reader and writer. Any number
of readers can read from the shared resource
simultaneously, but only one writer can write to the
shared resource. When a writer is writing data to the
resource, no other process can access the resource.
A writer cannot write to the resource if there are non
zero number of readers accessing the resource at that
time.

25
 From the above problem statement, it is
evident that readers have higher priority than
writer. If a writer wants to write to the resource,
it must wait until there are no readers currently
accessing that resource.
Here, we use one mutex m and
a semaphore w. An integer
variable read_count is used to maintain
the number of readers currently accessing the
resource. The variable read_count is
initialized to 0. A value of 1 is given initially
to m and w.
Instead of having the process to acquire lock on
the shared resource, we use the mutex m
to
make the process to acquire and release lock
whenever it is updating
the read_count variable.
26
 Code for writer

27
 Code for reader

28
 • As seen above in the code for the writer, the writer just waits on
the w semaphore until it gets a chance to write to the resource.
• After performing the write operation, it increments w so that the next
writer can access the resource.
• On the other hand, in the code for the reader, the lock is acquired
whenever the read_count is updated by a process.
• When a reader wants to access the resource, first it increments
the read_count value, then accesses the resource and then
decrements the read_count value.
• The semaphore w is used by the first reader which enters the critical
section and the last reader which exits the critical section.
• The reason for this is, when the first readers enters the critical section,
the writer is blocked from the resource. Only new readers can access
the resource now.
• Similarly, when the last reader exits the critical section, it signals the
writer using the w semaphore because there are zero readers now and
a writer can have the chance to access the resource.

29
 Dinning Philosophers Problem
• The dining philosopher's problem is the classical problem of synchronization which
says that Five philosophers are sitting around a circular table and their job is to think
and eat alternatively. A bowl of noodles is placed at the center of the table along with
five chopsticks for each of the philosophers. To eat a philosopher needs both their
right and a left chopstick. A philosopher can only eat if both immediate left and right
chopsticks of the philosopher is available. In case if both immediate left and right
chopsticks of the philosopher are not available then the philosopher puts down their
(either left or right) chopstick and starts thinking again.
• The dining philosopher demonstrates a large class of concurrency control problems
hence it's a classic synchronization problem

30
 Pictorial representation

31
 Here's the Solution

From the problem statement, it is clear that a philosopher can think for an
indefinite amount of time.
But when a philosopher starts eating, he has to stop at some point of time.
The philosopher is in an endless cycle of thinking and eating.
An array of five semaphores, stick[5], for each of the five chopsticks.

32
 • When a philosopher wants to eat the rice, he will wait for the chopstick at his left
and picks up that chopstick. Then he waits for the right chopstick to be available,
and then picks it too. After eating, he puts both the chopsticks down.
• But if all five philosophers are hungry simultaneously, and each of them pickup
one chopstick, then a deadlock situation occurs because they will be waiting for
another chopstick forever. The possible solutions for this are:
• A philosopher must be allowed to pick up the chopsticks only if both the left and
right chopsticks are available.
• Allow only four philosophers to sit at the table. That way, if all the four
philosophers pick up four chopsticks, there will be one chopstick left on the table.
So, one philosopher can start eating and eventually, two chopsticks will be
available. In this way, deadlocks can be avoided.

33
 Monitors
• Monitors are a synchronization construct that were created to overcome the
problems caused by semaphores such as timing errors.
• Monitors are abstract data types and contain shared data variables and procedures.
The shared data variables cannot be directly accessed by a process and procedures
are required to allow a single process to access the shared data variables at a time

34
35
 • Only one process can be active in a monitor at a time. Other
processes that need to access the shared variables in a monitor
have to line up in a queue and are only provided access when
the previous process release the shared variables.

36
 Advantages of Monitors
• Monitors are easy to implement than semaphores.
• Mutual exclusion in monitors is automatic while in semaphores, mutual exclusion needs
to be implemented explicitly.
• Monitors can overcome the timing errors that occur while using semaphores.
• Shared variables are global to all processes in the monitor while shared variables are
hidden in semaphores.

37
 Semaphore Monitor

38
39