Operating System

Karzan Hussein Sharif, PhD

Week 4_Session-1

1
 Introduction
• Synchronization: is the way by which processes that share the same
memory space are managed in an operating system.

• It helps maintain the consistency of data by using variables or hardware

so that only one process can make changes to the shared memory at a
time.

• For example: Process P1 tries changing data in a particular memory

location. At the same time another process P2 tries reading data from
the same memory location.
2
Cont.

Three synchronized process sharing same resource

3
 Cont.
• What is the purpose of having this concept in every OS?
1. Main purpose of synchronization is the sharing of resources without
interference using Mutex (Mutual Exclusion ).

2. The other purpose is the coordination of the process interactions in an

operating system.

So, synchronization is produced when processes need to execute

concurrently.
4
 Mutex (Mutual Exclusion)
A mutex (short for mutual exclusion) is a synchronization primitive used in
concurrent programming to protect shared resources (like data or critical
sections of code) from being accessed simultaneously by multiple threads
or processes. mutex = [Link]()

def critical_section():
with mutex:
# code that modifies shared data

• The main purpose of a mutex is to ensure that only one thread or

process can access the shared resource at any given time.
5
 Data Consistency in Synchronization
• Concurrent access to shared resources can result in data inconsistency.

In order to prevent data inconsistency, we need to implement mechanisms to

ensure the order of execution of cooperating processes.

• Example:

➢consumer-producer problem that fills all the buffers.

➢Solution: having an integer count that keeps track of the number of full buffers.
6
 Cont.
The integer count is initially set to 0. It is incremented by the producer
after it produces a new buffer item and is decremented by the consumer
after it consumes a buffer item.
Producer Consumer

while (true) { while (true){

while(counter == BUFFER_SIZE); while (counter == 0);
buffer [in] = nextProduced; nextConsumed = buffer[out];
in = (in + 1) % BUFFER_SIZE; out = (out + 1) % BUFFER_SIZE;
counter++; counter--;
} }
7
 Concurrent Access Behavior
• Three critical problems (or concepts) that occur when multiple processes
or threads access shared resources in an operating system without proper
synchronization.

1. Race Condition.

2. Critical Section.

3. Deadlock.
8
 1. Race Conditions
• It occurs when a device or system attempts to perform two or more
operations at the same time.

• Because of the nature of the device or system, the operations must be

done in the proper sequence in order to be implemented correctly.

• This situation happens due to multiple thread are executing in a manner

that is different than the order in which the threads must execute.

9
 Cont.
The solution for such problem is: by using synchronization primitives like
(Mutex) to ensure that shared resources are accessed in a controlled and
synchronized manner, preventing concurrent access and the associated
race conditions.
mutex = [Link]() # Step 1: Create a Mutex

def access_shared_resource():the Section # Step 2: Use the Mutex to Protect

with mutex:

# Your code to access the shared resource goes here

10
 2. Critical Sections
• A critical section is essential in a concurrent system to prevent multiple
threads or processes from accessing shared resources simultaneously,
ensuring the correctness of the program's execution.

• Critical section refers to a part of the code or a segment of a program

where shared resources (such as variables, memory, or files) are
accessed by multiple threads or processes.

➢When one process in critical section, no other may be in its critical

section. 11
 Cont.
The solution for such problem is: Mutex, which only one process can be
inside the critical section at any time. If any other processes require the
critical section, they must wait until it is free.

• Progress: If a process is not using the critical section, then it should not stop
any other process from accessing it.

• Bounded Waiting: Each process must have a limited waiting time. It should
not wait endlessly to access the critical section.

12
 Semaphore

Semaphores provide a powerful mechanism and can be used to solve a

variety of synchronization problems including:

• Managing access to shared data structures.

• Controlling the number of concurrent threads or processes accessing a

resource.

• Coordinating activities between threads or processes in a producer-

consumer scenario. 13
 Cont.
A semaphore uses two atomic operations for process synchronization: • Imagine a parking lot with 3
spaces (S = 3):
• Wait operation: Decreases the semaphore value and may cause the
• Each car that arrives does
calling process to wait if the resource is not available. wait(S):
wait(S){ • If a spot is available, it
while (S<=0);
parks (decreases S)
S--;
• If no spot is available
}
(S == 0), it waits
• Signal operation: Increases the semaphore value, signaling that a
resource has been released and another waiting process can proceed. • Each car that leaves does
signal(S) to free a spot
signal(S){
(increases S)
S++;

}
14
 Semaphore Types
1. Counting semaphore: can have values greater than 1, are used to
control access to resources with multiple instances, such as a fixed
number of permits in a resource pool. They allow you to limit the
number of threads or processes that can access a resource
simultaneously.

2. Binary semaphore: integer value can range only between 0 and 1 (for
simple mutual exclusion), ensuring that only one thread or process can
access a particular resource at a time.
15
 3. Deadlock

• 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 (A process may never be removed from

the semaphore queue in which it is already been suspended).

16
 Semaphore vs Mutex
1. Count vs. Binary: Semaphores can have a count greater than 1, allowing them to
control access to a finite number of resources. Mutex are binary, meaning they have
only two states to deal with.

2. Complexity: Semaphores can be more complex to use correctly, as they provide

various options and require careful management of their counts. Mutex are simpler to
use for basic mutual exclusion scenarios.

3. Use Cases: Semaphores are often chosen for scenarios involving resource pools,
signaling, or when multiple instances of a resource need to be coordinated. Mutex are
typically used when you need to protect a critical section of code to ensure only one
thread can access it at a time for data consistency.
17
 Classical Problems of Synchronization

Classical problems are used to test newly-proposed synchronization

schemes:

1. Bounded-Buffer Problem

2. Readers and Writers Problem

3. Dining-Philosophers Problem

18
 1. Bounded-Buffer Problem
Also known as the producer-consumer problem, in this scenario:

• The buffer has a limited capacity (N items).

• Multiple producer processes generate data and attempt to add it to the buffer.

• Multiple consumer processes remove data from the buffer.

• Producers should wait if the buffer is full, and consumers should wait if the
buffer is empty.

• There should be no race conditions when accessing the buffer.

19
 Cont.
Solution: to solve the bounded buffer problem, synchronization
mechanisms like semaphores or Mutex are used to coordinate the
activities of producers and consumers. The common approach to solving
the problem:

• Maintain two semaphores:

1. Empty: Initialized to N, representing the number of empty slots in the

buffer.

2. Full: Initialized to 0, indicating the number of filled slots in the buffer.

20
 2. Readers-Writers Problem

In this scenario, a dataset is shared among a number of concurrent

processes to use it, read from and write into a specific resource.

• The problem is how to allow multiple readers to read at the same time,
and how only one single writer can access the shared data at the same
time.

21
 Cont.
Solution: is to ensure that readers and writers can access the shared resource in a
way that maintains data integrity and prevents race conditions.

• Maintain Two Counters:

1. readers_count: A counter that keeps track of the number of readers currently

accessing the resource.

2. writers_count: A counter that keeps track of the number of writers waiting to

access the resource.

22
 3. Dining-Philosophers Problem
• In this scenario, philosophers spend their lives thinking and eating.

• They don’t interact with their neighbors, try to pick up 2 chopsticks (one
at a time) to eat from bowl.

• They need both to eat, then release both when done.

• Example: If we have 5 philosophers, the shared data will be:

➢Bowl of rice (data set).

➢Semaphore chopstick [5] initialized to 1. 23

 Hardware Synchronization
Hardware synchronization, also known as hardware-level synchronization
or low-level synchronization, involves mechanisms provided by computer
hardware to support synchronization and coordination of tasks, threads,
or processes at a low level of system architecture.

There are three hardware lock algorithm:

1. Test and set

2. Swap and unlock

3. Lock algorithm 24
 1. Test and Set
• Test and set algorithm uses a Boolean variable 'lock'
which is initially initialized to false. This lock variable
determines the entry of the process inside the
critical section of the code.

• Testing a memory location to see if it contains a

certain value and setting the value of that memory
location to a new value if it matches the test value.

• Efficient for short critical sections where a lock is

needed quickly. 25
 2. Swap and Unlock
The Swap function utilizes two Boolean
variables named "lock" and "key", which are
initialized to false at the beginning.

• Works in low-level, hardware-supported

systems where you need atomic operations
for locking.

26
 Cont.

1. Swap Operation: The lock variable is set to 1 (indicating the resource is

locked).

• The thread that is trying to acquire the lock will atomically swap.

2. Unlock Operation: The thread holding the lock sets the lock variable
back to 0 to release it.

• Other threads that were waiting to acquire the lock (or spinning) can
now proceed to acquire it.
27
 3. Lock Algorithm

Lock algorithm is a synchronization mechanism used in operating systems to

prevent multiple threads or processes from accessing shared resources
simultaneously. The lock algorithm helps to ensure that only one thread or
process can access the shared resource at a time, preventing conflicts and data
inconsistencies.

• Works when you need mutual exclusion to prevent race conditions in critical
sections of a program. 28
Any Questions

29