OPERATING SYSTEM- NOTE 5

MUTUAL EXCLUSION AND

SYNCHRONIZATION
The central themes of Operating System design is concerned with the management
of processes and threads:

●​ Multiprogramming -The management of multiple processes within a

uniprocessor system
●​ Multiprocessing -The management of multiple processes within a
multiprocessor
●​ Distributed Processing -The management of multiple processes executing
on multiple, distributed computer systems

Concurrency is the execution of multiple instruction sequences at the same time

(or seemingly at the same time, as with time-sharing). It is a fundamental concept
in operating systems and modern software design.

●​ Multiple Applications (Inter-application Concurrency)- Invented to

allow processing time to be shared among active applications (switch the
CPU between different running programs).
●​ Structured Applications (Intra-application Concurrency) -This applies
within a single application.
○​ Purpose: It is an extension of modular design and structured
programming, allowing a complex application to be broken down
into multiple, concurrently executing parts (threads).
○​ Mechanism: Modern applications are often implemented as a set of
cooperating threads. For example, a web server might use one thread
to listen for new requests and separate threads to handle each
individual client request concurrently. This improves performance,
responsiveness, and program structure.
●​ Operating System Structure (OS Implementation) - Concurrency is used to
build the operating system itself.
●​ Mechanism: The OS performs many different tasks concurrently,
such as managing memory, handling I/O operations, and scheduling
processes. Treating these functions as concurrent entities
(processes/threads) makes the OS modular, easier to design,
implement, and maintain. For example, a separate process or thread
might be dedicated solely to managing the file system.
Some Key Terms Related to Concurrency:

Atomic Operation

A function or action that is indivisible. It executes completely as a single,

uninterrupted unit. No other concurrent process can observe an intermediate state
or stop the operation once it has started. Atomicity ensures isolation from other
processes.

Critical Section

A section of code within a process that requires access to shared resources and that
must not be executed while another process is in a corresponding section of code.

Deadlock

A condition where two or more processes are unable to proceed because each is
waiting for one of the others to do something .

Livelock

A situation where two or more processes are continuously changing their state in
response to one another's actions. They are not blocked, but they never make
useful progress.

Mutual Exclusion

The requirement that when one process is in the critical section that accesses the
shared resource , no other process may be in the critical section that accesses any
of those shared resources.

Race Condition

A situation in which multiple threads or processes read and write a shared data
item and the final result depends on the relative timing of their execution
Starvation

A state in which a runnable process is overlooked indefinitely by the scheduler;

although it is able to proceed , it is never chosen.

Hardware Serializes Memory Access

The core assumption is that the hardware already handles the very basic problem of
multiple processors trying to access the same memory location at the exact same
nanosecond.

●​ Elementary Mutual Exclusion: This is the bare minimum guarantee. If two

processes try to read or write the exact same memory location at the same
time, the hardware (a memory arbiter) makes them happen one after the
other (serialized).
●​ What this doesn't guarantee: The hardware doesn't guarantee which
process goes first, and it doesn't solve larger problems like protecting an
entire block of code or multiple variables.

Mutual Exclusion: Software Approaches

Software approaches can be implemented for concurrent processes that execute on

a single-processor or a multiprocessor machine with shared main memory

●​ Assuming that we can only access the memory once at a time

●​ We will develop the solution on stages
●​ Dijkstra reported an algorithm for mutual exclusion for two processes,
designed by the Dutch mathematician Dekker
Dekker’s Algorithm

First Attempt

●​ Turn is a shared global variable - If turn = 0, Process 0 is allowed into the

critical section; if turn = 1, Process 1 is allowed.
●​ Busy waiting or Spin waiting- This describes how a process waits for its
turn.
●​ Enforce Mutual exclusion - The mechanism's goal is achieved, only the
process whose ID matches the turn variable can enter the critical section,
ensuring that only one process is inside at any time.
●​ Pace of execution is controlled by the slower process - Process 0 finishes
its work quickly and wants to run again, but it must wait for Process 1 to
complete its slow, full cycle (critical section and remainder section) and set
the turn back to 0. This forces the faster process to wait unnecessarily.
●​ If one process fails, the other will be blocked forever - If Process 1
enters its critical section and then crashes before setting the turn back to 0
(or 1, depending on the implementation), Process 0 will forever be stuck in
its busy-wait loop, waiting for turn to change to its value.
Second Attempt

●​ If one process fails outside of the critical section, the other is not [Link]
Process 1 fails in its non-critical work (the remainder section), it never sets
its intention flag (e.g., flag[1] = true). Process 0, upon checking the flag
(while (flag[1] == true)), sees that Process 1 isn't trying to enter, and
proceeds without interruption.
●​ If Process 1 enters the critical section and then fails (crashes) without
resetting its intention flag (flag[1] remains true), Process 0 will get stuck
indefinitely in its busy-wait loop because it constantly sees that Process 1 is
"trying" to enter or is "in" the critical section.
●​ Doesn’t Guarantee Mutual Exclusion-Both processes check the other’s flag
before setting their own [Link] creates a race condition.

Third Attempt

●​ If one process fails outside of the critical section, the other is not blocked
●​ If one process failed inside of the critical section, the other is blocked
●​ Guarantee Mutual Exclusion, but a deadlock may happen
Fourth Attempt

●​ Guarantee Mutual Exclusion

●​ Mutual Courtesy leads to a Livelock

Correct attempt
Peterson Algorithm

●​ Guarantee Mutual Exclusion

●​ No process will monopolize the processor
●​ No process will wait forever
Principles of Concurrency

Concurrent process can be interleaving or overlapping.

Uniprocessor – the relative speed of execution of processes cannot be predicted:

●​ Depends on activities of other processes

●​ The way the OS handles interrupt
●​ Scheduling policies of the OS

Difficulties of Concurrency

●​ Sharing of global resources- Two people try to edit the same document at the
same time → the document becomes confused or corrupted.
●​ Difficult for the OS to manage the allocation of resources optimally - The
operating system must decide: which process gets the CPU now? , Who
should access the printer? , how much memory to give each program?​
This becomes very complex when many processes run together.
●​ Difficult to locate programming errors as results are not deterministic and
reproducible, Example : You test your program 10 times: , 9 times
everything works , 1 time it crashes because two threads accessed the same
variable at the same time .Since the error does not happen every time, it
becomes very difficult to find and fix.

Race Condition

●​ Occurs when multiple processes or threads read and write shared data items
The final result depends on the order of execution
●​ The “loser” of the race is the process that updates last and will determine the
final value of the variable
Operating System Concerns with Concurrency

When concurrency exists, the operating system must deal with several important
design and management issues. Specifically, the OS must:

1. Keep track of all active processes -It should know which processes are running,
waiting, or stopped.

2. Allocate and free resources for each process -This includes memory, CPU time,
files, and other resources, and the OS must manage them efficiently.

3. Protect each process from interference - No process should accidentally modify

another process’s data or use its resources without permission.

4. Ensure correct and predictable process behavior -A process should produce the
correct output regardless of how fast or slow it runs compared to other processes
running at the same time.

Process Interactions
Cooperation Among Processes by Sharing

Sometimes processes interact with each other indirectly by sharing data, even if
they are not explicitly aware of one another.

1. Shared data access

Processes may read or update the same shared data.​

They do not communicate directly, but they know that other processes may also
access these data.

2. Need for cooperation

Because the data are shared, the processes must cooperate to make sure the data are
used and updated correctly.

3. Importance of control mechanisms

The system must include control mechanisms to:

●​ protect the shared data

●​ ensure data integrity (correctness)

4. Concurrency issues

Since the shared data reside on shared resources (like memory and devices), the
classic concurrency problems appear again:

●​ mutual exclusion
●​ deadlock
●​ starvation

5. Reading vs. writing

The only special point here is:

●​ Data can be accessed in two ways: read or write.

●​ Only writing requires mutual exclusion.​
Multiple readers can safely read the same data at the same time.
Cooperation Among Processes by Communication

1. Shared effort

In this type of cooperation, multiple processes work together on a common task.

Their activities are connected through communication.

2. Synchronization through messages

Communication allows processes to synchronize and coordinate what they are

doing, ensuring they work in the correct order.

3. Communication is message-based

Processes typically interact by sending and receiving messages of some kind.

4. Support from language or OS

The ability to send/receive messages may be:

●​ built into the programming language

●​ or provided by the operating system kernel

5. No need for mutual exclusion

Since processes do not share the same data, there is no need for mutual exclusion.

6. Deadlock and starvation can still occur

Even though they do not share memory, problems such as:

●​ deadlock
●​ starvation​
can still arise when communication or coordination is mishandled.
Requirements for Mutual Exclusion

1. Mutual exclusion must be enforced: Only one process at a time is allowed into
its critical section, among all processes that have critical sections for the same
resource or shared object.

2. A process that halts in its noncritical section must do so without interfering with
other processes.

3. It must not be possible for a process requiring access to a critical section to be

delayed indefinitely: no deadlock or starvation.

4. When no process is in a critical section, any process that requests entry to its
critical section must be permitted to enter without delay.

5. No assumptions are made about relative process speeds or number of processors.

6. A process remains inside its critical section for a finite time only.

Mutual Exclusion: Hardware Support

●​ Interrupt Disabling In a uniprocessor system, concurrent processes cannot

have overlapped execution; they can only be interleaved.
●​ A process will continue to run until it invokes an OS service or until it is
interrupted.
●​ Therefore, to guarantee mutual exclusion, it is sufficient to prevent a process
from being interrupted.
●​ This capability can be provided in the form of primitives defined by the OS
kernel for disabling and enabling interrupts

Disadvantages:

●​ The efficiency of execution could be noticeably degraded because the

processor is limited in its ability to interleave processes
●​ This approach will not work in a multiprocessor architecture.
Special Machine Instructions

Compare and swap Instruction

●​ Also called a “compare and exchange instruction”

●​ A compare is made between a memory value and a test value
●​ If the values are the same a swap occurs
●​ Carried out atomically (not subject to interruption)

Exchange Instruction

Bolt = 0, means no one in critical section. If bolt = 1, then exactly one process is in
its critical section
Advantages

●​ Applicable to any number of processes on either a single processor or

multiple processors sharing main memory
●​ Simple and easy to verify
●​ It can be used to support multiple critical sections; each critical section can
be defined by its own variable

Disadvantages

●​ Busy-waiting is employed Thus while a process is waiting for access to a

critical section it continues to consume processor time
●​ Starvation is possible When a process leaves a critical section and more
than one process is waiting, the selection of a waiting process is arbitrary;
some process could indefinitely be denied access
●​ Deadlock is possible - Only in case of a higher process priority.
1. Which process can be affected by other processes running in the system?

a. Cooperating process​
b. Child process​
c. Parent process​
d. Init process

2. When several processes access the same shared data at the same time and
the final result depends on the order of access, this is called a __________.

a. Dynamic Allocation​
b. Race Condition​
c. Essential Condition​
d. Critical Condition

3. When a process is inside its critical section, no other process accessing the
same shared variable should enter its critical section.

a. True​
b. False

4. Process synchronization can be implemented at the __________.

a. Hardware level​
b. Software level​
c. Both hardware and software levels​
d. None of them

5. Concurrent access to shared data may lead to __________.

a. Data consistency​
b. Data insecurity​
c. Data inconsistency​
d. None of them
6. The section of code where a process updates shared variables, modifies
tables, or writes files is called the __________.

a. Program​
b. Critical section​
c. Synchronizing section​
d. None of them

7. Mutual exclusion means that __________.

a. If a process is executing in its critical section, other processes must also execute
in their critical sections​
b. If a process is executing in its critical section, all system resources must be
blocked​
c. If a process is executing in its critical section, no other process may execute in
its critical section​
d. None of the above

8. Before a process enters its critical section, it must __________.

a. Enter directly​
b. Be terminated​
c. Make a permission or synchronization request​
d. None of the above

9. Processes may use shared variables to synchronize their actions.

a. True​
b. False

10. The hardware instruction that supports mutual exclusion is __________.

a. Compare and Swap​

b. Semaphores​
c. Both of them​
d. None of them
11. An uninterruptible operation is known as __________.

a. Single​
b. Atomic​
c. Static​
d. None

12. The Compare and Swap instruction is executed __________.

a. After a particular process​

b. Atomically​
c. Periodically​
d. None

1. A

2. B

3. A

4. C

5. A

6. B

7. C

8. C

9. A

10. A

11. B

12. B