Module - 2

MULTI-THREAD PROGRAMMING

Karthik M N, CS&D, MUSE Module 2

 Module 2
● Multi-threaded Programming: Overview;
● Multithreading models; Thread Libraries; Threading issues.
● Process Scheduling: Basic concepts; Scheduling Criteria; Scheduling
Algorithms;
● Multiple-processor scheduling; Thread scheduling.
● Process Synchronization: Synchronization: The critical section problem;
Peterson’s solution; Synchronization hardware;
● Semaphores; Classical problems of synchronization; Monitors.

Karthik M N, CS&D, MUSE Module 2 2

 Multithreaded Programming: Introduction
● A thread is the basic unit of CPU utilization.
● A thread consists of
○ Thread ID
○ Program Counter (PC)
○ Register-set
○ Stack

Karthik M N, CS&D, MUSE Module 2 3

 ● Threads share the code-section and data-section with other threads in the
same process.
● A traditional (or heavyweight) process has a single thread of control.
● A multithreaded process can perform multiple tasks simultaneously with
multiple threads of control.

Karthik M N, CS&D, MUSE Module 2 4

Karthik M N, CS&D, MUSE Module 2 5
 Motivation for Multithreaded Programming
1. Modern Software Packages:
● Most software on PCs today is multithreaded.
● Example: A word processor may have:
○ Thread 1: Displaying graphics
○ Thread 2: Responding to keystrokes
○ Thread 3: Performing grammar checking

Karthik M N, CS&D, MUSE Module 2 6

 2. Handling Multiple Tasks:

● A single application may need to perform multiple similar tasks.

● Example: A web server creates a separate thread for each client request,
enabling it to handle several requests concurrently.

3. RPC Servers:

● RPC servers are multithreaded.

● They service messages using concurrent threads for each request.

Karthik M N, CS&D, MUSE Module 2 7

 4. Multithreaded OS Kernels:

● Many OS kernels are multithreaded.

● Multiple threads operate in the kernel, each performing specific tasks like
device management or interrupt handling.

Karthik M N, CS&D, MUSE Module 2 8

 Benefits of Multithreaded Programming
● Responsiveness
○ A program continues running even if part of it is blocked.
○ Improves user experience and system interactivity.
■ Example: A web browser loads images and videos while responding to user inputs.
● Resource Sharing
○ Threads share memory and resources of the same process.
○ Allows multiple threads to execute different tasks within the same address space.
■ Example: A text editor allows typing while auto-saving the document in the background.

Karthik M N, CS&D, MUSE Module 2 9

 ● Economy
○ Creating and managing threads is less costly than creating processes.
○ Context switching between threads is faster than between processes.
■ Example: A database server handles multiple client queries using threads instead of
separate processes.
● Utilization of Multiprocessor Architectures
○ Threads can run in parallel on multiple processors.
○ Enhances system performance through parallel execution.
■ Example: Video rendering software splits tasks among multiple CPU cores to speed up
processing.

Karthik M N, CS&D, MUSE Module 2 10

 Multithreading Models
Threads can be supported at two levels:

● User-Level Threads: Managed by user libraries without kernel involvement.

(or) Managed at the user level, without kernel support.
● Kernel-Level Threads: Managed directly by the Operating System.

Karthik M N, CS&D, MUSE Module 2 11

 Three Multithreading Models:

● Many-to-One Model
○ Multiple user threads are mapped to a single kernel thread.
○ Efficient but cannot utilize multiple cores.
■ Example: Some older languages' thread libraries like GNU Portable Threads.
■ Limitation: If one user thread blocks, the entire process is blocked.

Karthik M N, CS&D, MUSE Module 2 12

 ● One-to-One Model
○ Each user thread is mapped to a separate kernel thread.
○ Allows concurrency but creates overhead if too many threads exist.
■ Example: Windows and Linux Pthreads (POSIX threads).
■ Advantage: Provides true parallelism on multiprocessor systems.
■ Disadvantage: Creating too many kernel threads can slow down performance.

Karthik M N, CS&D, MUSE Module 2 13

 ● Many-to-Many Model
○ Multiple user threads are mapped to multiple kernel threads.
○ Multiple user threads are mapped to an equal or smaller number of kernel threads.
○ Allows scalability and efficient resource management.
■ Example: Solaris and modern Linux threading models.
■ Advantage: Balances flexibility and efficiency by allowing more user threads without
overloading kernel threads.

Karthik M N, CS&D, MUSE Module 2 14

 Difference Between Process and Thread

Process Thread

A program in execution. A segment within a process.

Heavyweight process. Lightweight process.

Takes more time for creation and termination. Takes less time for creation and termination.

Expensive – requires a large Process Control

Cheaper – requires a smaller PCB as threads share
Block (PCB) as each process has its own
code and memory within the process.
code, memory, and resources.

Takes more time for context switching. Takes less time for context switching.

Threads within a process share the same memory

Each process has its own memory space.
space.
Karthik M N, CS&D, MUSE Module 2 15
 Process Thread

Communication between processes requires

IPC (Interprocess Communication) Threads can communicate easily as they share
mechanisms like message passing or shared memory within the same process.
memory.

Example: Running multiple applications Example: A web browser using different threads for
(browser, text editor, media player). loading pages, rendering UI, and handling user input.

Karthik M N, CS&D, MUSE Module 2 16

 Process Scheduling
CPU Scheduling & Multiprogramming

● Objective:
○ Ensure the CPU is utilized at all times by running some process, maximizing efficiency.
○ Ensuring some process is always running.
● Multiprogramming Concept:
○ Enables multiple processes to share CPU time, reducing idle time.

Karthik M N, CS&D, MUSE Module 2 17

 Key Components of Process Scheduling:
● Ready Queue: Stores processes waiting for CPU execution.
● Short-Term Scheduler (CPU Scheduler): Selects a process from the ready
queue to execute.
● Dispatcher: Transfers CPU control to the selected process.
● Dispatch Latency: Time taken to stop one process and start another.

❏ Example: In a multitasking OS, when multiple applications (browser, text

editor, media player) are open, process scheduling ensures smooth switching
between them.

Karthik M N, CS&D, MUSE Module 2 18

 Scheduling Criteria
When selecting a CPU scheduling algorithm, the following criteria are considered:

● CPU Utilization
○ Keep the CPU as busy as possible, maximize CPU usage.
○ Ideal range: 40% (light load) to 90% (heavy load).
● Throughput
○ Measures work done: number of processes completed per time unit.
○ Long processes may complete one process per hour, short ones may complete ten per
second.

Karthik M N, CS&D, MUSE Module 2 19

 ● Turnaround Time
○ Total time from process submission to completion.
○ Includes waiting time in memory, ready queue, execution, and I/O operations.
● Waiting Time
○ Time spent in the ready queue waiting for CPU allocation.
○ Does not include I/O execution time.
● Response Time
○ Time from request submission to first response.
○ Important in interactive systems.
○ Measures time to start responding, not time for the full output.
● Fairness
○ Ensuring all processes get CPU time fairly.

Karthik M N, CS&D, MUSE Module 2 20

 ❏ Example:
● In a real-time system, response time is critical (e.g., airbag deployment in
cars).
● In batch systems, throughput and turnaround time are prioritized (e.g.,
payroll processing).

Karthik M N, CS&D, MUSE Module 2 21

 Scheduling Algorithms - Overview
CPU Scheduling

● Decides which process in the ready queue gets CPU time.

● Ensures efficient use of the CPU and optimizes process performance.

Karthik M N, CS&D, MUSE Module 2 22

 Scheduling Algorithms
FCFS Scheduling (First Come First Served)

● Processes are scheduled in the order they arrive in the ready queue.
● Simple but may cause long waiting times for processes.

Round Robin Scheduling

● Each process is assigned a fixed time slice or quantum.

● Processes are executed in a circular order, one after another.

Karthik M N, CS&D, MUSE Module 2 23

 SJF Scheduling (Shortest Job First)

● Processes with the shortest burst time are executed first.

● Optimal for minimizing average waiting time but difficult to predict burst time.

SRT Scheduling (Shortest Remaining Time)

● Preemptive version of SJF.

● The process with the shortest remaining burst time is executed next.

Karthik M N, CS&D, MUSE Module 2 24

 Priority Scheduling

● Each process is assigned a priority.

● The process with the highest priority is executed first.
● Can be preemptive or non-preemptive.

Multilevel Queue Scheduling

● Processes are divided into multiple queues based on priority.

● Each queue has its own scheduling algorithm.
● High-priority processes are executed first.

Multilevel Feedback Queue Scheduling

● Similar to Multilevel Queue, but processes can move between queues based
on their behavior.
● Allows more flexibility in adjusting priority dynamically.
Karthik M N, CS&D, MUSE Module 2 25
 Key Scheduling Metrics in OS
Arrival Time (AT)
● The time at which a process enters the ready queue and is ready for
execution.
Burst Time (BT)
● The total time required by a process for execution on the CPU.
● Includes only CPU execution time (not waiting time).
Completion Time (CT)
● The time at which a process finishes execution.

Karthik M N, CS&D, MUSE Module 2 26

 Turnaround Time (TAT)

● The total time taken by a process from arrival to completion.

● Formula: 𝑇𝐴𝑇=𝐶𝑇−𝐴𝑇

Waiting Time (WT)

● The total time a process spends waiting in the ready queue.

● Formula: 𝑊𝑇=𝑇𝐴𝑇−𝐵𝑇

Response Time (RT)

● The time from process arrival to its first CPU execution.

● Formula: 𝑅 𝑇 = First Execution Start Time − 𝐴 𝑇
○ Important in time-sharing systems.

Karthik M N, CS&D, MUSE Module 2 27

 FCFS Scheduling
First Come First Serve (FCFS) Scheduling

● The process that requests the CPU first is allocated the CPU first.
● Implemented using a FIFO (First In, First Out) queue.

Implementation Steps:

1. When a process enters the ready queue, its PCB is linked to the tail of the
queue.
2. When the CPU is free, it is allocated to the process at the queue’s head.
3. The running process is removed from the queue once execution is complete.

Karthik M N, CS&D, MUSE Module 2 28

 Advantages of FCFS Scheduling
● Simple and easy to implement.
● No preemption, reducing interrupt overhead.
● Suitable for batch systems where fairness is important.
Disadvantages of FCFS Scheduling
● Convoy Effect – Small processes wait for large processes to complete.
● Non-preemptive – Once a process starts execution, it cannot be interrupted.
● Poor for time-sharing systems where quick response is needed.
● High average waiting time, leading to inefficiency.
● Low CPU and device utilization.
● Poor response time, making it unsuitable for interactive environments.

Karthik M N, CS&D, MUSE Module 2 29

 FCFS Scheduling - Example & Problems
Given Data:
Burst Time (BT)
Process
in milliseconds

P1 24

P2 3

P3 3

Gantt Chart: P1 P2 P3

0 24 27 30

Karthik M N, CS&D, MUSE Module 2 30

 Calculations:

Turnaround Time
Arrival Burst Time Completion Time Waiting Time
Process (TAT = CT - AT) or
Time (AT) (BT) (CT) (WT = TAT - BT)
(TAT = WT + BT)

P1 0 24 24 24 0

P2 0 3 27 27 24

P3 0 3 30 30 27

Observations:

● Average Turnaround Time (TAT) = (24 + 27 + 30) / 3 = 27 ms

● Average Waiting Time (WT) = (0 + 24 + 27) / 3 = 17 ms

Karthik M N, CS&D, MUSE Module 2 31

 Issues with FCFS:

● Convoy Effect: Short processes (P2, P3) have to wait for a long process (P1)
to finish.
● Higher Average Waiting Time: Due to non-preemptive nature, short processes
suffer delays.
● Not Suitable for Time-Sharing Systems: Poor response time and inefficient
CPU utilization.

Karthik M N, CS&D, MUSE Module 2 32

 Problem 2: We will calculate the Completion Time (CT), Turnaround Time (TAT),
and Waiting Time (WT) for the processes when they arrive in the order P2, P3, P1.

Given Data:
Burst Time (BT)
Process
in milliseconds

P2 3

P3 3

P1 24

Gantt Chart: P2 P3 P1

0 3 6 30

Karthik M N, CS&D, MUSE Module 2 33

 Calculations:

Turnaround Time
Arrival Burst Time Completion Time Waiting Time
Process (TAT = CT - AT) or
Time (AT) (BT) (CT) (WT = TAT - BT)
(TAT = WT + BT)

P2 0 3 3 3 0

P3 0 3 6 6 3

P1 0 24 30 30 6

Observations:

● Average Turnaround Time (TAT) = (3 + 6 + 30) / 3 = 13 ms

● Average Waiting Time (WT) = (0 + 3 + 6) / 3 = 3 ms

Karthik M N, CS&D, MUSE Module 2 34

 Observations

● The average waiting time (AWT) is reduced when shorter processes (P2, P3)
are scheduled before longer ones.
● This reduces the turnaround time for smaller jobs compared to the previous
FCFS order (P1, P2, P3).
● However, FCFS still suffers from the Convoy Effect, as P1, a long process,
causes delay for any later-arriving short processes.

Karthik M N, CS&D, MUSE Module 2 35

 Problem 3: Consider an example where the processes have different arrival times
and are scheduled using FCFS (First Come, First Served).

Given: Arrival Burst Time (BT)

Process
Time (AT) in milliseconds

P1 0 24

P2 2 3

P3 4 3

Gantt Chart P1 P2 P3

0 24 27 30

Karthik M N, CS&D, MUSE Module 2 36

 Step-by-Step Execution using FCFS:

● At time 0, P1 arrives and starts executing since the CPU is free.

● At time 2, P2 arrives, but must wait since P1 is still running.
● At time 4, P3 arrives, but it also waits since P1 is still running.
● At time 24, P1 finishes, and P2 starts execution.
● At time 27, P2 finishes, and P3 starts execution.
● At time 30, P3 finishes execution.

Karthik M N, CS&D, MUSE Module 2 37

 Calculating Completion Time (CT), Turnaround Time (TAT), and Waiting Time
(WT):

Turnaround Time
Arrival Burst Time Completion Time Waiting Time
Process (TAT = CT - AT) or
Time (AT) (BT) (CT) (WT = TAT - BT)
(TAT = WT + BT)

P1 0 24 24 24 0

P2 2 3 27 25 22

P3 4 3 30 26 23

Observations:
● Average Turnaround Time (TAT) = (24 + 25 + 26) / 3 = 25 ms
● Average Waiting Time (WT) = (0 + 22 + 23) / 3 = 15 ms

Karthik M N, CS&D, MUSE Module 2 38

 Observations:
Higher Waiting Times
● Because P1 has a long burst time, P2 and P3 must wait longer, increasing their
Waiting Time (WT).
● This is known as the "Convoy Effect" in FCFS scheduling.
Turnaround Time (TAT) Increases for Later Processes
● Since FCFS does not preempt processes, later-arriving processes (P2, P3)
experience high TAT because they must wait for earlier processes to complete.
Poor Response Time for Short Processes
● Shorter jobs (P2, P3) suffer as they have to wait for longer jobs (P1) to finish.

Karthik M N, CS&D, MUSE Module 2 39

 SJF Scheduling
Shortest Job First Scheduling
● The CPU is assigned to the process that has the smallest next CPU burst.
● If two processes have the same length CPU burst, FCFS scheduling is used
to break the tie.
Advantages
● SJF is optimal, i.e., it gives the minimum average waiting time for a given set
of processes.
Disadvantages
● Determining the length of the next CPU burst is difficult.

Karthik M N, CS&D, MUSE Module 2 40

 Types of SJF Scheduling

1. Non-Preemptive SJF
● The current process is allowed to finish its CPU burst before switching.
2. Preemptive SJF (SRTF Scheduling)
● If a new process has a shorter next CPU burst than what is left of the
executing process, the current process is preempted.

Karthik M N, CS&D, MUSE Module 2 41

 SJF Scheduling - Example & Problems
Given Data: Non-Preemptive SJF Process
Burst Time (BT)
in milliseconds

P1 6

P2 8

P3 7

P4 3

Gantt Chart: P4 P1 P3 P2

0 3 9 16 24

Karthik M N, CS&D, MUSE Module 2 42

 Calculations:

Turnaround
Arrival Burst Time Completion Waiting Time Time (TAT = CT -
Process
Time (AT) (BT) Time (CT) (WT = TAT - BT) AT) or
(TAT = WT + BT)

P1 0 6 9 3 3+6=9

P2 0 8 24 16 6 + 8 = 24

P3 0 7 16 9 9 + 7 = 16

P4 0 3 3 0 0+3=3

Observations:

● Average Waiting Time (WT) = (3 + 16 + 9 +0) / 4 = 7 ms

● Average Turnaround Time (TAT) = (9 + 24 + 16 + 3) / 4 = 13 ms
Karthik M N, CS&D, MUSE Module 2 43
 Preemptive Shortest Job First (SJF) Scheduling
● A preemptive SJF algorithm will preempt the currently executing process if a
new process arrives with a shorter remaining CPU burst.
● A non-preemptive SJF algorithm allows the currently running process to finish
its CPU burst before scheduling another.

Karthik M N, CS&D, MUSE Module 2 44

 Key Characteristics of SRTF

● Preemptive version of Shortest Job First (SJF).

● Process with the shortest remaining burst time is always scheduled next.
● Preempts the current process if a new process arrives with a shorter burst
time.
● Reduces waiting time and turnaround time compared to non-preemptive SJF

Karthik M N, CS&D, MUSE Module 2 45

 SJF - SRTF Scheduling - Example & Problems
Given Data: Preemptive SJF Arrival Time
Burst Time
Process (BT) in
(AT)
milliseconds

P1 0 8

P2 1 4

P3 2 9

P4 3 5

Gantt Chart: P1 P2 P4 P1 P3

0 1 5 10 17 26

Karthik M N, CS&D, MUSE Module 2 46

 Gantt Chart (SRTF) execution order
1) At t = 0, only P1 has arrived → CPU starts with P1.
2) At t = 1, P2 arrives with a smaller burst time (4ms) than P1’s remaining (7ms)
→ P2 preempts P1.
3) At t = 2, P3 arrives (burst time 9) → P2 keeps executing (since 4 < 9).
4) At t = 3, P4 arrives (burst time 5) → P2 keeps executing (since 4 < 5).
5) At t = 5, P2 completes → P4 (burst time 5) takes over as it is the shortest
remaining.
6) At t = 10, P4 completes → P1 resumes execution.
7) At t = 17, P1 completes → P3 (the only remaining process) starts.
8) At t = 26, P3 completes.

Karthik M N, CS&D, MUSE Module 2 47

 Calculations:

Turnaround Time
Arrival Burst Time Completion Waiting Time
Process (TAT = CT - AT) or
Time (AT) (BT) Time (CT) (WT = TAT - BT)
(TAT = WT + BT)

P1 0 8 17 17 - 0 = 17 17 - 8 = 9

P2 1 4 5 5-1=4 4-4=0

P3 2 9 26 26- 2 = 24 24 - 9 = 15

P4 3 5 10 10 - 3 = 7 7-5=2

Observations:

● Average Waiting Time (WT) = (9 + 0 + 15 +2) / 4 = 6.5 ms

● Average Turnaround Time (TAT) = (17 + 4 + 24 + 7) / 4 = 13 ms
Karthik M N, CS&D, MUSE Module 2 48
 Pros and Cons
Advantages:

● Minimizes average waiting time compared to FCFS and non-preemptive SJF.

● Efficient for short processes that arrive frequently.
● Better CPU utilization by avoiding long waiting times for small processes.

Disadvantages:

● Starvation: Longer processes may suffer from indefinite postponement.

● Difficult to predict CPU burst times accurately.
● More complex to implement due to frequent context switching.

Karthik M N, CS&D, MUSE Module 2 49

 Conclusion
● SRTF (Preemptive SJF) is an efficient scheduling algorithm that minimizes
waiting time and turnaround time.
● It is best suited for systems with frequent short processes.
● The main challenge is accurately predicting burst times and avoiding
starvation.

Karthik M N, CS&D, MUSE Module 2 50

 Problem 2:

Given Data: Burst Time

Arrival Time
Process (BT) in
(AT)
milliseconds

P1 0 12

P2 2 4

P3 3 6

P4 8 5

Gantt Chart:

P1 P2 P3 P4 P1

0 2 6 12 17 27

Karthik M N, CS&D, MUSE Module 2 51

 Calculations:

Turnaround Time
Arrival Burst Time Completion Waiting Time
Process (TAT = CT - AT) or
Time (AT) (BT) Time (CT) (WT = TAT - BT)
(TAT = WT + BT)

P1 0 12 27 27 - 0 = 27 27 - 12 = 15

P2 2 4 6 6-2=4 4-4=0

P3 3 6 12 12 - 3 = 9 9-6=3

P4 8 5 17 17 - 8 = 9 9-5=4

Observations:

● Average Waiting Time (WT) = (15 + 0 + 3 +4) / 4 = 5.5 ms

● Average Turnaround Time (TAT) = (27 + 4 + 9 + 9) / 4 = 12.25 ms
Karthik M N, CS&D, MUSE Module 2 52
 Priority Scheduling
● A priority is associated with each process.
● The CPU is allocated to the process with the highest priority.
● Equal-priority processes are scheduled in FCFS order.

Karthik M N, CS&D, MUSE Module 2 53

 Priority Types

● Internally-defined priorities:
● Computed based on measurable quantities.
● Examples: Time limits, memory requirements, number of open files.

Externally-defined priorities:

● Determined by external factors.

● Examples: Importance of the process, political factors.

Karthik M N, CS&D, MUSE Module 2 54

 Pros and Cons
Advantages

● Supports multitasking systems.

● Supports both preemptive and non-preemptive scheduling.
● Provides good response time for high-priority tasks.

Disadvantage

● Indefinite Blocking:
○ Low-priority processes may wait indefinitely for CPU time.

Karthik M N, CS&D, MUSE Module 2 55

 Solution to Indefinite Blocking

● Aging:
○ Increases the priority of a process the longer it waits.
○ Ensures fairness in CPU allocation.

❏ Priority Scheduling ensures efficient CPU allocation based on priority.

❏ It can be preemptive or non-preemptive.
❏ Aging helps prevent indefinite blocking of low-priority processes.

Karthik M N, CS&D, MUSE Module 2 56

 Priority Scheduling - Example & Problems
Given Data: Non-Preemptive Priority Scheduling

Burst Time
Process (BT) in Priority
milliseconds

P1 10 3

P2 1 1

P3 2 4

P4 1 5

P5 5 2

Karthik M N, CS&D, MUSE Module 2 57

 Arrange Processes by Priority (Lower value = Higher Priority)

● Since this is non-preemptive priority scheduling, processes will execute in

order of their priority.
● If two processes have the same priority, FCFS is used.
Process Priority

P2 1

P5 2

P1 3

P3 4

P4 5

Karthik M N, CS&D, MUSE Module 2 58

 Construct the Gantt chart

● P2 executes first (0-1)

● P5 executes next (1-6)
● P1 executes next (6-16)
● P3 executes next (16-18)
● P4 executes last (18-19)

Gantt Chart P2 P5 P1 P3 P4

0 1 6 16 18 19

Karthik M N, CS&D, MUSE Module 2 59

 Calculations:
Turnaround
Arrival Burst Completion Time (TAT = CT - Waiting Time
Process Priority
Time (AT) Time (BT) Time (CT) AT) or (WT = TAT - BT)
(TAT = WT + BT)

P2 0 1 1 1 1 0

P5 0 5 2 6 6 1

P1 0 10 3 16 16 6

P3 0 2 4 18 18 16

P4 0 1 5 19 19 18

Observations:
● Average Waiting Time (WT) = (0 + 1 + 6 +16 + 18) / 4 = 8.2 ms
● Average Turnaround Time (TAT) = (1 + 6 + 16 + 18 + 19) / 5 = 12 ms
Karthik M N, CS&D, MUSE Module 2 60
 Priority Scheduling - Example & Problems
Given Data: Preemptive Priority Scheduling

Burst Time
Arrival
Process (BT) in Priority
TIme (AT)
milliseconds

P1 0 6 4

P2 3 5 2

P3 3 3 6

P4 5 5 3

Karthik M N, CS&D, MUSE Module 2 61

 Construct the Gantt chart
● Time 0-3 → P1 runs (No other process has arrived).
● Time 3 → P2 (priority 2) arrives and preempts P1 (priority 4).
● Time 3-5 → P2 runs.
● Time 5 → P4 arrives (priority 3), but P2 (priority 2) continues since it has
higher priority.
● Time 5-8 → P2 finishes execution.
● Time 8-13 → P4 runs (next highest priority).
● Time 13-16 → P1 resumes (as P3 has lower priority).
● Time 16-19 → P3 runs (last process left).

P1 P2 P4 P1 P3
Gantt Chart
0 3 8 13 16 19

Karthik M N, CS&D, MUSE Module 2 62

 Calculations:

Turnaround
Arrival Burst Time Completion Time (TAT = CT - Waiting Time
Process Priority
Time (AT) (BT) Time (CT) AT) or (WT = TAT - BT)
(TAT = WT + BT)

P1 0 6 4 16 16 10

P2 3 5 2 8 5 0

P3 3 3 6 19 16 13

P4 5 5 3 13 8 3

Observations:
● Average Waiting Time (WT) = (10 + 0 + 13 + 3) / 4 = 6.5 ms
● Average Turnaround Time (TAT) = (16 + 5 + 16 + 8) / 4 = 11.25 ms
Karthik M N, CS&D, MUSE Module 2 63
 Round Robin Scheduling
● Designed especially for time-sharing systems.
● Similar to FCFS scheduling but with preemption.
● A small unit of time is called a time quantum (or timeslice).
● Time quantum typically ranges from 10 to 100 ms.
● The ready queue is treated as a circular queue.

Karthik M N, CS&D, MUSE Module 2 64

 Working of RR Scheduling

● Processes are placed in a queue.

● The CPU executes each process for a fixed time quantum.
● If a process is not completed, it is moved to the back of the queue.
● The next process in the queue gets CPU time.
● This cycle repeats until all processes are completed.

Karthik M N, CS&D, MUSE Module 2 65

 Pros and Cons
Advantages
● Supports preemptive scheduling, preventing long waiting times.
● Fair CPU allocation among all processes.
● Good response time for interactive users.
● Suitable for multi-user and time-sharing systems.
Disadvantage
● Turnaround time depends on the size of the time quantum.
● Smaller time quantum leads to more context switches, increasing overhead.
● Higher average waiting time compared to SJF.
● Complex implementation due to frequent context switching.

Karthik M N, CS&D, MUSE Module 2 66

 RR Scheduling - Example & Problems
Given Data:

Time Quantum: 4 milliseconds

Burst Time (BT) in

Process
milliseconds

P1 24

P2 3

P3 3

Karthik M N, CS&D, MUSE Module 2 67

 Construct the Gantt chart

● Process P1 runs for 4ms, remaining 20ms.

● Process P2 runs for 3ms and completes.
● Process P3 runs for 3ms and completes.
● Process P1 gets another 4ms, remaining 16ms.
● Process P1 continues this pattern until completion.

Gantt Chart P1 P2 P3 P1

0 4 7 10 30

Karthik M N, CS&D, MUSE Module 2 68

 Calculations:

Turnaround
Arrival Burst Time Completion Time (TAT = CT - Waiting Time
Process
Time (AT) (BT) Time (CT) AT) or (WT = TAT - BT)
(TAT = WT + BT)

P1 0 24 30 30 6

P2 0 3 7 7 4

P3 0 3 10 10 7

Observations:
● Average Waiting Time (WT) = (6 + 4 + 7) / 3 = 5.66 ms
● Average Turnaround Time (TAT) = (30 + 7 + 10) / 3 = 15.66 ms
Karthik M N, CS&D, MUSE Module 2 69
 Observations
Average Waiting Time (WT)
● WT is calculated as: (6 + 4 + 7) / 3 = 5.66 ms
● Lower waiting time improves response time.
Average Turnaround Time (TAT)
● TAT is calculated as: (30 + 7 + 10) / 3 = 15.66 ms
● Determines overall execution time from arrival to completion.
Preemptive Nature of RR Scheduling
● If a process's CPU burst exceeds 1-time quantum, it is preempted.
● The process is placed back in the ready queue.
● Ensures fairness in time-sharing systems.

Karthik M N, CS&D, MUSE Module 2 70

 Impact of Time Quantum Size
● RR performance depends on time quantum selection.
● Large Time Quantum:
○ RR behaves like FCFS scheduling.
○ Longer response time for short processes.

Small Time Quantum:

● Leads to frequent context switching.
● Increased CPU overhead.
● Appears as "processor sharing," where each process gets 1/N th of CPU speed.

❏ RR scheduling balances fairness and efficiency.

❏ Choosing an optimal time quantum is critical.
❏ Best suited for time-sharing and multi-user systems.

Karthik M N, CS&D, MUSE Module 2 71

 Problem 2:

Given Data: Time Quantum = 2 ms

Burst Time
Arrival Time
Process (BT) in
(AT)
milliseconds

P1 0 5

P2 1 4

P3 2 2

P4 4 1

Karthik M N, CS&D, MUSE Module 2 72

 Answer:
Gantt chart:

P1 P2 P3 P4 P1 P2 P1

0 2 4 6 7 9 11 12

● Average Waiting Time (WT) = 4.75 ms

● Average Turnaround Time (TAT) = 7.75 ms

Karthik M N, CS&D, MUSE Module 2 73

 Problem 3:

Given Data: Time Quantum = 2 ms

Burst Time
Arrival Time
Process (BT) in
(AT)
milliseconds

P1 0 10

P2 1 1

P3 2 2

P4 4 1

P5 10 5

Karthik M N, CS&D, MUSE Module 2 74

 Answer:
Gantt chart:

P1 P2 P1 P3 P4 P1 P5 P1 P5 P1 P5

0 2 3 5 7 8 10 12 14 16 18 19

● Average Waiting Time (WT) = 3.6 ms

● Average Turnaround Time (TAT) = 7.4 ms

Karthik M N, CS&D, MUSE Module 2 75

 Problem - PS

For the given data, compute the average Turnaround time & average Waiting time
by using following Algorithms

1. FCFS Process Arrival Time (AT)

Burst Time (BT)
in milliseconds
2. SJF
3. SRT P1 0 3

4. Round-robin P2 1 6

P3 4 4

P4 6 2

Karthik M N, CS&D, MUSE Module 2 76

 Answers:
FCFS

● Average Waiting Time (WT) = 3.5 ms

● Average Turnaround Time (TAT) = 7.25 ms

Karthik M N, CS&D, MUSE Module 2 77

 SJF

● Average Waiting Time (WT) = 3 ms

● Average Turnaround Time (TAT) = 6.75 ms

Karthik M N, CS&D, MUSE Module 2 78

 SRTF

● Average Waiting Time (WT) = 2.5 ms

● Average Turnaround Time (TAT) = 6.25 ms

Karthik M N, CS&D, MUSE Module 2 79

 RR

● Average Waiting Time (WT) = 4.5 ms

● Average Turnaround Time (TAT) = 8.25 ms

Karthik M N, CS&D, MUSE Module 2 80

 Multilevel Queue Scheduling
● Multilevel Queue Scheduling is useful for situations where processes can be
classified into different groups.
○ Example: Foreground (interactive) and Background (batch) processes.
● The ready-queue is divided into multiple separate queues.

Karthik M N, CS&D, MUSE Module 2 81

 Classification of Process
● Processes are permanently assigned to one queue based on:
○ Memory size
○ Process priority
○ Process type
● Each queue has its own scheduling algorithm.

Karthik M N, CS&D, MUSE Module 2 82

 Multilevel Queue Structure
● The ready queue is divided into multiple queues.
● Each queue follows a specific scheduling policy.
● Example:
○ Foreground queue: Uses Round Robin (RR)
○ Background queue: Uses First Come First Serve (FCFS)
● Example distribution: 80% CPU time for foreground, 20% for background.

Karthik M N, CS&D, MUSE Module 2 83

 Scheduling Among Queues
● Scheduling must be done among different queues.
● Commonly implemented as fixed-priority preemptive scheduling:
○ Example: Foreground queue has absolute priority over background queue.
● Alternative method: Time slice allocation
○ Example: 80% CPU to foreground, 20% to background.

Karthik M N, CS&D, MUSE Module 2 84

 Example of Multilevel Queue Scheduling
● Consider a system with the following queues:
a. System Processes – Highest priority (Fixed priority scheduling)
b. Interactive Processes – Medium priority (Round Robin scheduling)
c. Batch Processes – Lowest priority (FCFS scheduling)
● The CPU scheduler selects processes from the highest-priority queue first.

Karthik M N, CS&D, MUSE Module 2 85

 Advantages
● Efficient process management for different types of workloads.
● Better response time for interactive processes.
● Flexibility in choosing scheduling policies for each queue.
● Fixed priority and time slice allocation improve CPU utilization.

Karthik M N, CS&D, MUSE Module 2 86

 Disadvantages
● Starvation: Lower-priority processes may suffer indefinite blocking.
● Inflexible: Once a process is assigned to a queue, it cannot move.
● Complex implementation compared to other scheduling algorithms.
● Resource underutilization if a queue remains empty.

Karthik M N, CS&D, MUSE Module 2 87

 ❏ Multilevel Queue Scheduling effectively organizes different process types.
❏ It ensures priority-based scheduling but may suffer from starvation.
❏ Often used in systems requiring clear process separation and prioritization.

Karthik M N, CS&D, MUSE Module 2 88

 Multilevel Feedback Queue Scheduling
● A process may move between queues.
● The basic idea: Separate processes according to the features of their CPU
bursts.
● Key Concept
○ If a process uses too much CPU time, it is moved to a lower-priority queue.
○ I/O-bound and interactive processes stay in higher-priority queues.
○ Prevents starvation using aging: A process waiting too long in a lower-priority queue is moved
to a higher-priority queue.

Karthik M N, CS&D, MUSE Module 2 89

 Characteristics
● Dynamic Priority Adjustment: Process priority changes over time.
● Multiple Queues: Each queue has a different priority level.
● Time Sharing: CPU time is allocated based on queue priority.
● Preemptive Scheduling: Higher-priority queues can preempt lower-priority
queues.

Karthik M N, CS&D, MUSE Module 2 90

 Key Parameters
● The number of queues.
● The scheduling algorithm for each queue.
● The promotion criteria for upgrading a process.
● The demotion criteria for downgrading a process.
● The initial queue assignment for a new process.

Karthik M N, CS&D, MUSE Module 2 91

 Example
● Queue 1: Highest priority, Round Robin (RR) with a short time quantum.
● Queue 2: Medium priority, Round Robin with a longer time quantum.
● Queue 3: Lowest priority, FCFS (First-Come, First-Served).
● A process starts in Queue 1 and moves to lower queues if it exceeds time
limits.

Karthik M N, CS&D, MUSE Module 2 92

 Advantage and Disadvantages
1. Advantages
a. Reduces response time for interactive processes.
b. Prevents starvation through aging.
c. Efficiently handles different types of processes.
2. Disadvantages
a. Complex implementation.
b. Requires tuning of queue parameters for optimal performance.

Karthik M N, CS&D, MUSE Module 2 93

 ❏ Multilevel Feedback Queue Scheduling dynamically adjusts process priorities.
❏ It balances CPU-bound and I/O-bound processes efficiently.
❏ Ideal for time-sharing systems with diverse workloads.

Karthik M N, CS&D, MUSE Module 2 94

 Process Synchronization
● Process synchronization is required when multiple processes share
resources.
● Ensures orderly execution of cooperating processes.
● Prevents issues like race conditions and data inconsistency.

Karthik M N, CS&D, MUSE Module 2 95

 Cooperating Process
● A cooperating process can affect or be affected by other processes.
● Two types of cooperating processes:
○ Processes that share a logical address space (code and data).
○ Processes that share data through files or messages.

Karthik M N, CS&D, MUSE Module 2 96

 Need for Synchronization
● Concurrent access to shared data may lead to inconsistencies.
● Example: Two processes updating a shared bank balance at the same time.
● Synchronization ensures:
○ Data integrity.
○ Avoidance of race conditions.
○ Proper execution order.

Karthik M N, CS&D, MUSE Module 2 97

 Critical Section Problem
● Critical Section: A section of code where shared resources are accessed.
● Problem: Ensuring that only one process enters the critical section at a time.
● Solution: Synchronization mechanisms to control access to the critical
section.

Karthik M N, CS&D, MUSE Module 2 98

 Requirements for Synchronization
● Mutual Exclusion: Only one process executes in the critical section at a time.
● Progress: If no process is in the critical section, one must be allowed to enter.
● Bounded Waiting: Each process gets a fair chance to enter the critical
section.

Karthik M N, CS&D, MUSE Module 2 99

 Synchronization Mechanism
● Peterson’s Solution: Software-based approach for two processes.
● Locks: Prevents multiple processes from entering the critical section
simultaneously.
● Semaphores: Integer-based synchronization tool using wait() and signal().
● Monitors: High-level synchronization construct for process coordination.

Karthik M N, CS&D, MUSE Module 2 100

 Semaphores
● A semaphore is a synchronization tool represented by an integer variable.
● Types of semaphores:
○ Binary Semaphore: Takes values 0 or 1 (acts like a lock).
○ Counting Semaphore: Takes non-negative integer values.
● Operations:
○ wait() (also called P operation)
○ signal() (also called V operation)

Karthik M N, CS&D, MUSE Module 2 101

 Classic Synchronization Problems
● Bounded Buffer (Producer-Consumer) Problem: Ensures producers and
consumers access the buffer correctly.
● Readers-Writers Problem: Manages access to shared data by multiple
readers and writers.
● Dining Philosophers Problem: Avoids deadlock and starvation in resource
sharing scenarios.

Karthik M N, CS&D, MUSE Module 2 102

 Deadlock and Starvation
● Deadlock: Processes wait indefinitely for resources held by others.
● Starvation: Low-priority processes wait indefinitely while high-priority
processes proceed.
● Solution: Implement proper scheduling and priority mechanisms.

Karthik M N, CS&D, MUSE Module 2 103

 Producer - Consumer Problem
● A Producer process produces information that is consumed by a Consumer
process.
● To allow the producer and consumer process to run concurrently, a Bounded
Buffer can be used where the items are filled in a buffer by the producer and
emptied by the consumer.
● The original solution allowed at most BUFFER_SIZE - 1 items in the buffer at
the same time.
● To overcome this deficiency, an integer variable counter, initialized to 0, is
added.
● counter is incremented every time when a new item is added to the buffer and
is decremented every time when one item is removed from the buffer.

Karthik M N, CS&D, MUSE Module 2 104

 Code for Producer Process
while (true) {
// Produce an item
while (counter == BUFFER_SIZE);
buffer[in] = item;
in = (in + 1) % BUFFER_SIZE;
counter++;
}

Karthik M N, CS&D, MUSE Module 2 105

 Code for Consumer Process
while (true) {
while (counter == 0);
item = buffer[out];
out = (out + 1) % BUFFER_SIZE;
counter--;
// Consume the item
}

Karthik M N, CS&D, MUSE Module 2 106

 Race Condition
When the Producer and Consumer routines are correct separately, they may not
function correctly when executed concurrently.

Illustration:

● Suppose that the value of counter is currently 5, and the producer and
consumer execute counter++ and counter-- concurrently.
● The value of the counter may become 4, 5, or 6, but the only correct result is
counter == 5.
● The concurrent execution of counter++ and counter-- results in interleaved
execution orders, leading to inconsistencies.

Karthik M N, CS&D, MUSE Module 2 107

 Execution Interleaving - Example
S0: Producer executes register1 = counter → register1 = 5

S1: Producer executes register1 = register1 + 1 → register1 = 6

S2: Consumer executes register2 = counter → register2 = 5

S3: Consumer executes register2 = register2 - 1 → register2 = 4

S4: Producer executes counter = register1 → counter = 6

S5: Consumer executes counter = register2 → counter = 4

● Incorrect State: counter == 4, indicating that four buffers are full, when in fact, five should be
full.
● If execution order is reversed at S4 and S5, counter == 6, another incorrect state.

Karthik M N, CS&D, MUSE Module 2 108

 Race Condition
● A situation where several processes access and manipulate the same data
concurrently, and the outcome depends on the execution order.
● To prevent race conditions, ensure that only one process at a time
manipulates the counter variable.
● This requires process synchronization mechanisms such as:
○ Mutex locks
○ Semaphores
○ Monitors

Karthik M N, CS&D, MUSE Module 2 109

 Solution - Process Synchronization
● Mutual exclusion ensures that only one process modifies shared variables at
a time.
● Synchronization mechanisms like semaphores and monitors help manage
concurrent access.
● Critical Section Problem:
○ Each process must request permission to enter its critical section.
○ Solutions should satisfy Mutual Exclusion, Progress, and Bounded Waiting conditions.

Karthik M N, CS&D, MUSE Module 2 110

 The Critical Section Problems
● A system consists of n processes: {P0, P1, ..., Pn-1}.
● Each process has a critical section, where it updates shared data.
● The goal: Ensure only one process executes in its critical section at a time.

Karthik M N, CS&D, MUSE Module 2 111

 ● When one process is in its critical section, others must wait.
● A protocol must be designed to manage access to the critical section.
● Key challenge: Prevent simultaneous access leading to data inconsistency.

Karthik M N, CS&D, MUSE Module 2 112

 Process Structure
● A typical process Pi follows this structure:
1. Entry Section - Request access to the critical section.
2. Critical Section - Perform operations on shared resources.
3. Exit Section - Release control.
4. Remainder Section - Perform other non-critical tasks.

Karthik M N, CS&D, MUSE Module 2 113

 Requirements for a Solution
A correct solution must satisfy the following properties:

● Mutual Exclusion
○ If one process is in its critical section, others must wait.
● Progress
○ If no process is in its critical section, waiting processes must decide who enters next.
○ No indefinite delays.
● Bounded Waiting
○ There is a limit on how many times other processes can enter before a waiting process gets its
turn.

Karthik M N, CS&D, MUSE Module 2 114

 Mutual Exclusion:

● Ensures that only one process executes in the critical section at any time.
● Prevents race conditions and inconsistent shared data.

Progress:

● If no process is in the critical section, other processes should be able to enter

without unnecessary delays.
● Avoids deadlock scenarios.

Bounded Waiting:

● Ensures fairness.
● No process should starve while waiting for access to the critical section.

Karthik M N, CS&D, MUSE Module 2 115

 ❏ The Critical Section Problem is a fundamental issue in process
synchronization.
❏ Solutions must ensure Mutual Exclusion, Progress, and Bounded Waiting.
❏ Essential for maintaining consistency in concurrent systems.

Karthik M N, CS&D, MUSE Module 2 116

 Peterson’s Solution to a Critical Section Problem
● Peterson’s Solution is a classic software-based approach to the Critical
Section Problem.
● Ensures mutual exclusion, progress, and bounded waiting.
● Restricted to two processes that alternate execution between their critical and
remainder sections.

Karthik M N, CS&D, MUSE Module 2 117

 Limitations
● Not guaranteed to work on modern computer architectures due to hardware
optimizations.
● Still useful for understanding the complexities of process synchronization.

Karthik M N, CS&D, MUSE Module 2 118

 Assumptions
● Two processes (P0 and P1 or Pi and Pj where j = 1 - i).
● Processes alternate execution between their critical sections and remainder
sections.
● Uses two shared data variables: turn and flag.

Karthik M N, CS&D, MUSE Module 2 119

 Shared Data Variables
1. The two processes share two variables:
a. int turn → Determines whose turn it is to enter the critical section.
b. boolean flag[2] → Indicates if a process is ready to enter its critical section.

2. If flag[i] = true, it means Pi wants to enter its critical section.

Karthik M N, CS&D, MUSE Module 2 120

 Peterson’s Algorithm
// Process Pi

flag[i] = true; // Indicate desire to enter

turn = j; // Give turn to other process

while (flag[j] && turn == j);

// Critical Section

flag[i] = false; // Exit Section

● The process sets its flag and gives the turn to the other process.
● It waits until the other process is not in its critical section or it is its turn.
● After exiting, it resets its flag.

Karthik M N, CS&D, MUSE Module 2 121

 Peterson’s Algorithm for Process Pi
flag[i] = true; // Indicate that Pi wants to enter CS

turn = j; // Give priority to the other process

while (flag[j] && turn == j); // Wait if Pj wants to enter

// Critical Section

flag[i] = false; // Exit CS

Karthik M N, CS&D, MUSE Module 2 122

 Peterson’s Algorithm for Process Pj
flag[j] = true; // Indicate that Pj wants to enter CS

turn = i; // Give priority to the other process

while (flag[i] && turn == i); // Wait if Pi wants to enter

// Critical Section

flag[j] = false; // Exit CS

Karthik M N, CS&D, MUSE Module 2 123

 Ensuring Mutual Exclusion - Proof
● Only one process can enter the critical section at a time.
● The while loop prevents both processes from executing in their critical
sections simultaneously.

1. Condition for entry: while(flag[j] && turn == j);

2. If both processes try to enter, turn is set to either i or j.
3. Only one process can proceed at a time because turn prevents both from
entering simultaneously.
4. Conclusion: Mutual exclusion is guaranteed.

Karthik M N, CS&D, MUSE Module 2 124

 Progress - Proof
Progress: If no process is in the critical section, then only those wishing to enter
will decide who goes first.

● If Pj is not ready (flag[j] = false), Pi enters immediately.

● If both want to enter, only the process given the turn enters.
● Conclusion: No indefinite blocking; progress is ensured.

Karthik M N, CS&D, MUSE Module 2 125

 Bounded Waiting - Proof
Bounded Waiting: Each process gets a fair chance to enter; no indefinite
postponement (starvation) occurs.

● A process can only be blocked if the other keeps re-entering.

● Turn variable ensures fairness by alternating access.
● Conclusion: A process enters after at most one execution of the other
process.

Karthik M N, CS&D, MUSE Module 2 126

 Advantages
● Simple software-based solution.
● Does not require special hardware instructions.
● Ensures mutual exclusion, progress, and bounded waiting.

Karthik M N, CS&D, MUSE Module 2 127

 Disadvantages
● Limited to only two processes.
● Inefficient on modern architectures.
● Requires busy waiting (active looping in while condition).

Karthik M N, CS&D, MUSE Module 2 128

 Conclusion
❏ Peterson’s Solution is a fundamental approach to process synchronization.
❏ Although outdated for modern hardware, it lays the foundation for
understanding synchronization concepts.
❏ Modern systems rely on hardware-based locking mechanisms instead.

Karthik M N, CS&D, MUSE Module 2 129

 Semaphore in Process Synchronization
● A semaphore is an integer variable used to solve various synchronization
problems.
● Semaphores do not require busy waiting.
● They are used to ensure mutual exclusion and prevent race conditions in
concurrent processes.

Karthik M N, CS&D, MUSE Module 2 130

 Semaphore Operation
A semaphore S is accessed through two atomic operations:
● Wait() (also called P operation)
● Signal() (also called V operation)

Definition for Wait() Definition for Signal()

wait(S) { signal(S) {
while (S <= 0); S++;
S--; }
}

These operations must be executed indivisibly to prevent simultaneous modifications by

multiple processes.

Karthik M N, CS&D, MUSE Module 2 131

 Binary Semaphore
● The value of a binary semaphore can only be 0 or 1.
● Also known as mutex locks, as they ensure mutual exclusion.
● Implementation Example:

do {

wait(mutex);

// Critical Section

signal(mutex);

// Remainder Section

}while (TRUE);

● Used in critical-section problems for multiple processes.

Karthik M N, CS&D, MUSE Module 2 132

 Counting Semaphore
● The value of a counting semaphore can range over an unrestricted domain.
● Used to control access to a resource that has multiple instances.
● Implementation:
○ Semaphore initialized to the number of available resources.
○ Process requests resource: wait(semaphore);
○ Process releases resource: signal(semaphore);
● If the semaphore count reaches 0, all resources are in use, and additional
processes must wait.

Karthik M N, CS&D, MUSE Module 2 133

 Comparison of Binary and Counting Semaphore

Feature Binary Semaphore Counting Semaphore

Value
0 or 1 0 to N (unlimited)
Range

Use Case Mutual exclusion (locking) Managing multiple resources

Mutex lock for critical Limiting concurrent access to shared

Example
section resources

Karthik M N, CS&D, MUSE Module 2 134

 ❏ Semaphores are essential for synchronization in concurrent systems.
❏ They help prevent race conditions and ensure proper resource management.
❏ Two types: Binary (mutex) and Counting (for multiple resources).

Karthik M N, CS&D, MUSE Module 2 135

 Classical Problems of Synchronization
1. Bounded-Buffer Problem
2. Readers-Writers Problem
3. Dining Philosophers Problem

Karthik M N, CS&D, MUSE Module 2 136

 Bounded Buffer Problem
Problem Definition

● There is a buffer of n slots, where each slot can store one unit of data.
● Two processes, Producer and Consumer, operate on the buffer.

Conditions

1. The Producer must not insert data when the buffer is full.
2. The Consumer must not remove data when the buffer is empty.
3. The Producer and Consumer should not insert and remove data
simultaneously

Karthik M N, CS&D, MUSE Module 2 137

 Solution Using Semaphores
● N buffers, each holding one item.
● Semaphores Used:
○ mutex (initialized to 1) - Ensures mutual exclusion.
○ full (initialized to 0) - Counts the number of full slots.
○ empty (initialized to N) - Counts the number of empty slots.

Karthik M N, CS&D, MUSE Module 2 138

 Structure of Producer - Consumer Process
Producer Consumer

Karthik M N, CS&D, MUSE Module 2 139

 Reader - Writer Problem
Problem Definition
● There are multiple reader and writer processes accessing a shared database.
● Readers can read the database simultaneously.
● Writers need exclusive access to modify the database.
Conditions
1. Multiple readers can read at the same time.
2. Writers must have exclusive access (no other reader or writer can access the
database during writing).
3. No starvation: Neither readers nor writers should be indefinitely delayed.

Karthik M N, CS&D, MUSE Module 2 140

 Solution Using Semaphores
Semaphores Used:

● mutex (initialized to 1) - Protects shared variable read_count.

● write_lock (initialized to 1) - Ensures mutual exclusion for writers.
● read_count (initialized to 0) - Tracks active readers.

Karthik M N, CS&D, MUSE Module 2 141

 Structure of Reader - Writer Problem

Structure of Writer Process Structure of Reader Process

do { do
{
wait(wrt); wait(mutex);
// performs the write readcount++;
signal(wrt); if (readcount==1)
} while(true); wait(wrt);
signal(mutex);
wait(mutex);
readcount--;
if (readcount == 0)
signal(wrt);
signal(mutex);
} While (true)

Karthik M N, CS&D, MUSE Module 2 142

 Dining - Philosophers Problem
Problem Statement:

Consider five philosophers who spend their lives alternating between thinking and
eating. They share a circular table surrounded by five chairs, each belonging to
one philosopher. In the center of the table is a bowl of rice, and the table is laid
with five single chopsticks.

Karthik M N, CS&D, MUSE Module 2 143

 Rules:

● A philosopher gets hungry and tries to pick up the two chopsticks closest to
them (left and right chopsticks).
● A philosopher may pick up only one chopstick at a time.
● When a hungry philosopher has both chopsticks, they eat without releasing
them.
● After eating, the philosopher puts down both chopsticks and resumes
thinking.

This problem is a simple representation of the need to allocate multiple resources

among multiple processes in a deadlock-free and starvation-free manner.

Karthik M N, CS&D, MUSE Module 2 144

 Solution
One simple solution is to represent each chopstick with a semaphore.

● A philosopher tries to grab a chopstick by executing a wait() operation on that

semaphore.
● They release their chopsticks by executing the signal() operation on the
appropriate semaphores.
● The shared data structure is:

semaphore chopstick[5];

● where all elements of chopstick are initialized to 1.

Karthik M N, CS&D, MUSE Module 2 145

 Structure of Philosopher

Karthik M N, CS&D, MUSE Module 2 146

 Deadlock Prevention Strategies
Several possible remedies to prevent deadlock include:

● Limit the Number of Philosophers:

○ Allow at most four philosophers to be sitting at the table simultaneously.
● Both Chopsticks Must Be Available:
○ A philosopher picks up chopsticks only if both are available at the same time.
● Asymmetric Solution:
○ An odd-numbered philosopher picks up their left chopstick first, then the right one.
○ An even-numbered philosopher picks up their right chopstick first, then the left one.

These solutions help in preventing deadlock and starvation, ensuring fair resource
allocation.

Karthik M N, CS&D, MUSE Module 2 147

 ❏ Synchronization problems are crucial in ensuring correct execution of
concurrent processes.
❏ Semaphores and various synchronization techniques help manage
deadlocks, starvation, and race conditions.
❏ Dining-Philosophers, Bounded-Buffer, and Readers-Writers are classical
problems representing real-world synchronization challenges.

Karthik M N, CS&D, MUSE Module 2 148