MODULE – III PART A

Define CPU Scheduling and Explain Scheduling Criteria

Explanation

In a multiprogramming operating system, several processes reside in memory at the same

time and compete for the use of the CPU. Since the CPU can execute only one process at a
time, the operating system must decide which process should be allocated the CPU next.
This decision-making process is known as CPU scheduling and is a core function of process
management.

Example

When multiple programs such as a compiler, media player, and text editor are running
simultaneously, the operating system switches the CPU among these processes so that each
process gets a fair share of CPU time and the system remains responsive.

Main Answer

CPU Scheduling is the process by which the operating system selects one process from the
ready queue and allocates the CPU to it. The decision is made by the CPU scheduler,
which aims to optimize system performance and resource utilization.

Scheduling Criteria

To evaluate and compare different CPU scheduling algorithms, the following scheduling
criteria are used:

1. CPU Utilization
It refers to the percentage of time the CPU is busy executing processes.

Goal: Maximize CPU utilization.

2. Throughput
It is the number of processes completed per unit time.

Goal: Maximize throughput.

 3. Turnaround Time
Turnaround time is the total time taken from process submission to process
completion.

Goal: Minimize turnaround time.

4. Waiting Time
Waiting time is the total time a process spends waiting in the ready queue.

Goal: Minimize waiting time

5. Response Time
Response time is the time taken from submission of a request until the first response
is produced.

Goal: Minimize response time.

These criteria help in selecting an appropriate scheduling algorithm depending on system

requirements such as batch processing, interactive systems, or real-time systems.

Explain FCFS Scheduling Algorithm

Explanation

In CPU scheduling, processes waiting for CPU time are organized in a queue. One of the
simplest scheduling approaches is to allocate the CPU to processes in the order in which
they arrive. This method follows a straightforward rule and is easy to understand and
implement.

Example

If three processes arrive at the ready queue in the order P1, P2, and P3, the CPU is allocated
first to P1. After P1 finishes execution, the CPU is given to P2, and then to P3, irrespective of
their burst times.

Main Answer
First-Come, First-Served (FCFS) Scheduling Algorithm is a non-preemptive CPU
scheduling algorithm in which the process that arrives first in the ready queue is
allocated the CPU first.

In FCFS scheduling:

 Processes are executed strictly in arrival order.

 Once a process gets the CPU, it runs until completion or until it requests I/O.
 The ready queue is implemented using a FIFO (First-In First-Out) queue.

Characteristics of FCFS Scheduling

1. Non-Preemptive
The running process cannot be interrupted until it finishes execution.
2. Simple Implementation
FCFS is easy to implement and understand since it uses a FIFO queue.
3. Fair in Arrival Order
Every process gets a chance to execute based on arrival time.

Advantages

 Simple and easy to implement

 No starvation
 Suitable for batch systems

Disadvantages

 Convoy Effect:
Short processes may wait for a long process to finish, increasing average waiting
time.
 Poor response time for interactive systems
 Not suitable for time-sharing environments

Explain SJF Scheduling (Preemptive and Non-Preemptive)

Explanation

CPU scheduling algorithms differ in how they select the next process for execution. One
important approach is to schedule processes based on their CPU burst time. The idea is that
a process with a shorter CPU burst should be executed before a process with a longer burst to
reduce waiting time. This concept forms the basis of the Shortest Job First (SJF) scheduling
algorithm.

Example

If three processes arrive with CPU burst times of 2 ms, 5 ms, and 10 ms, the process with a 2
ms burst is scheduled first, followed by the 5 ms process, and then the 10 ms process. This
ordering minimizes the average waiting time.

Main Answer

Shortest Job First (SJF) Scheduling is a CPU scheduling algorithm in which the process
with the smallest next CPU burst time is selected for execution.

SJF scheduling is optimal because it minimizes the average waiting time for a given set of
processes. However, it requires knowledge or prediction of the CPU burst time.

SJF scheduling can be implemented in two forms:

1. Non-Preemptive SJF Scheduling

In non-preemptive SJF, once a process is allocated the CPU, it runs to completion even if a
shorter job arrives later.

Characteristics:

 CPU is assigned to the process with the shortest burst time among the ready processes
 No interruption of the running process
 Simple to implement compared to preemptive SJF

Limitation:
A long process may block shorter processes that arrive after CPU allocation.

2. Preemptive SJF Scheduling (Shortest Remaining Time First – SRTF)

In preemptive SJF, also called Shortest Remaining Time First (SRTF), the CPU is
allocated to the process with the smallest remaining execution time.

Characteristics:
  If a new process arrives with a shorter remaining time than the currently running
process, the CPU is preempted
 Provides better response time for short processes
 More suitable for time-sharing systems

Limitation:
Higher overhead due to frequent context switches.

Explain Priority Scheduling Algorithm

Explanation

In a multiprogramming environment, not all processes are equally important. Some processes
require immediate attention, while others can wait. To handle this, the operating system uses
priority scheduling, where each process is assigned a priority, and the CPU is allocated
based on this priority value.

Example

In an operating system, a system process such as memory management may be given higher
priority than a user application like a text editor. As a result, the system process is scheduled
first whenever it is ready to execute.

Main Answer

Priority Scheduling is a CPU scheduling algorithm in which the CPU is allocated to the
process with the highest priority.

 Each process is assigned a priority number.

 Processes with higher priority are executed before processes with lower priority.
 If two processes have the same priority, they are scheduled using FCFS.

Priority scheduling can be implemented in two forms:

1. Non-Preemptive Priority Scheduling

In non-preemptive priority scheduling:

  Once a process gets the CPU, it continues execution until completion.
 Even if a higher-priority process arrives, it must wait.

2. Preemptive Priority Scheduling

In preemptive priority scheduling:

 The CPU can be preempted if a higher-priority process arrives.

 The running process is interrupted and returned to the ready queue.

Issues in Priority Scheduling

Starvation:
Low-priority processes may never get CPU time if high-priority processes continuously
arrive.

Aging:
A solution to starvation where the priority of a waiting process is gradually increased over
time, ensuring eventual execution.

Explain Round Robin Scheduling Algorithm

Explanation

In time-sharing and interactive systems, the CPU must be shared fairly among all active
processes so that each process gets regular access to the CPU. Round Robin (RR)
scheduling is designed to meet this requirement by assigning CPU time to processes in small,
fixed time units called time quanta.

Example

Assume three processes P1, P2, and P3 are in the ready queue and the time quantum is 4 ms.
The CPU is allocated to P1 for 4 ms, then to P2 for 4 ms, and then to P3 for 4 ms. If a process
does not finish within its time quantum, it is preempted and placed at the end of the ready
queue.
Main Answer

Round Robin (RR) Scheduling is a preemptive CPU scheduling algorithm in which each
process is assigned the CPU for a fixed time quantum in a cyclic order.

In Round Robin scheduling:

 The ready queue is treated as a circular FIFO queue.

 The CPU scheduler selects the first process from the ready queue.
 A timer interrupts the CPU after one time quantum.
 If the process is not completed, it is preempted and added to the end of the ready
queue.

Characteristics of Round Robin Scheduling

1. Preemptive in Nature
The CPU is preempted after the time quantum expires.
2. Fair CPU Allocation
Each process gets an equal share of CPU time.
3. Time Quantum Selection
o If the time quantum is too large, RR behaves like FCFS.
o If the time quantum is too small, overhead increases due to frequent context
switches.

Advantages

 Provides good response time for interactive systems

 Prevents starvation
 Simple and fair scheduling policy

Disadvantages

 Performance depends heavily on the size of the time quantum

 Higher context switching overhead for very small time quantam.

Solve numerical problems on FCFS, SJF and RR.

Explain Multilevel Queue Scheduling with Diagram

Explanation

In some operating systems, processes can be permanently classified into different groups
based on their characteristics such as process type or priority. To manage such systems
efficiently, the operating system uses multilevel queue scheduling, where each group of
processes is placed in a separate ready queue with its own scheduling policy.

Example

An operating system may separate system processes, interactive user processes, and batch
processes into different queues. System processes may be given higher priority, while batch
processes may be scheduled only when the system is idle.

Main Answer

Multilevel Queue Scheduling is a CPU scheduling algorithm in which the ready queue is
divided into multiple separate queues, each having its own priority level and scheduling
algorithm.

Characteristics of Multilevel Queue Scheduling

 Each queue has a fixed priority.

 Processes are permanently assigned to a queue.
 CPU scheduling is performed among queues as well as within a queue.
 Lower-priority queues are executed only if higher-priority queues are empty.

Typical Multilevel Queue Structure

A common multilevel queue scheduling system consists of the following queues (from
highest to lowest priority):

1. System Processes Queue

o Highest priority
o Uses priority or FCFS scheduling
2. Interactive Processes Queue
o Medium priority
o Uses Round Robin scheduling
 3. Batch Processes Queue
o Lowest priority
o Uses FCFS scheduling

Scheduling Between Queues

Scheduling between queues can be done using:

 Fixed-priority preemptive scheduling

(Higher-priority queue preempts lower-priority queues)
 Time-slice scheduling among queues
(Each queue gets a fixed portion of CPU time)

Explain Multilevel Feedback Queue Scheduling

Explanation of the Topic

In practical systems, a process’s behavior may change over time. Some processes start as
CPU-bound and later become I/O-bound, or vice versa. To adapt to such dynamic behavior,
the operating system uses multilevel feedback queue scheduling, which allows processes to
move between queues based on their execution characteristics.

Example

A newly created process is placed in a high-priority queue. If it uses the CPU for a long time
without blocking, it is moved to a lower-priority queue. If a process frequently performs I/O
and uses little CPU time, it remains in or is promoted to a higher-priority queue.

Main Answer

Multilevel Feedback Queue Scheduling is a CPU scheduling algorithm in which multiple

ready queues are maintained, and processes can move between these queues based on
their CPU burst behavior and aging policies.

Unlike multilevel queue scheduling, processes are not permanently assigned to a single
queue.
Key Characteristics

 Multiple queues, each with a different priority

 Each queue may use a different scheduling algorithm
 Processes can move up or down between queues
 Designed to approximate Shortest Job First (SJF) scheduling

Rules Governing Multilevel Feedback Queues

A multilevel feedback queue scheduler is defined by the following parameters:

1. Number of Queues
The system maintains several queues with different priority levels.
2. Scheduling Algorithm for Each Queue
o Higher-priority queues usually use Round Robin
o Lower-priority queues often use FCFS
3. Method for Promoting a Process
If a process waits too long in a lower-priority queue, it may be moved to a higher-
priority queue (aging).
4. Method for Demoting a Process
If a process uses too much CPU time, it is moved to a lower-priority queue.
5. Time Quantum Assignment
Higher-priority queues are assigned smaller time quanta, while lower-priority
queues have larger or no time quantum.

PART B – (Process Synchronization)

Explain Critical Section Problem and Its Requirements

Explanation

In a multiprogramming environment, multiple processes or threads may execute concurrently

and share common resources such as variables, files, or data structures. If these shared
resources are accessed simultaneously without proper control, it can lead to inconsistent or
incorrect results. The problem of ensuring correct access to shared resources is known as the
critical section problem.
Example

Consider two processes updating a shared variable that stores a bank account balance. If both
processes read and update the balance at the same time without coordination, the final value
may be incorrect. To prevent this, access to the update code must be controlled.

Main Answer

The critical section problem refers to the challenge of designing a mechanism such that no
two processes execute their critical sections simultaneously, while still allowing efficient
and fair execution.

A critical section is a part of a program where shared data is accessed or modified.

Each process has the following structure:

 Entry section – requests permission to enter the critical section

 Critical section – accesses shared resources
 Exit section – releases permission
 Remainder section – remaining code

Requirements for a Solution to the Critical Section Problem

Any correct solution to the critical section problem must satisfy the following three
requirements:

1. Mutual Exclusion

If one process is executing in its critical section, no other process is allowed to enter its
critical section.

This ensures that shared resources are accessed by only one process at a time.

2. Progress

If no process is executing in its critical section and some processes wish to enter, the
selection of the next process cannot be postponed indefinitely.

Only processes that are not in their remainder sections can participate in the decision.
3. Bounded Waiting

There must be a limit on the number of times other processes are allowed to enter their
critical sections after a process has requested entry and before that request is granted.

This prevents starvation of processes.

A solution that satisfies all three requirements ensures correctness, fairness, and efficiency
in concurrent execution.

Illustrate Peterson’s Solution to Critical Section Problem

Explanation of the Topic

Peterson’s solution is a software-based synchronization technique that provides a correct

solution to the critical section problem for two processes. It uses shared variables and busy
waiting to ensure that only one process enters the critical section at a time while satisfying all
correctness requirements.

Example

Consider two processes, P0 and P1, that need to update a shared variable. Peterson’s solution
ensures that when one process is updating the variable, the other process waits until the
update is completed.

Main Answer

Peterson’s Solution is a classical algorithm that solves the critical section problem for two
concurrent processes using the following shared variables:

 boolean flag[2]
Indicates whether a process wants to enter the critical section
 int turn
Indicates whose turn it is to enter the critical section
Algorithm Structure

For process Pi (where i = 0 or 1 and j = 1 − i):

Entry Section:

 flag[i] = true;
 turn = j;
 while (flag[j] && turn == j); (busy wait)

Critical Section:

 Process Pi executes its critical section

Exit Section:

 flag[i] = false;

Remainder Section:

 Remaining code of the process

Working of Peterson’s Solution

 When a process wants to enter the critical section, it sets its flag to true.
 It then gives priority to the other process by setting turn.
 If the other process also wants to enter and it is the other’s turn, the process waits.
 Only one process can pass the while condition at a time.

Correctness Properties

Peterson’s solution satisfies all three requirements of the critical section problem:

1. Mutual Exclusion
Only one process can be in the critical section at any time.
2. Progress
If no process is in the critical section, one of the requesting processes will be selected
without delay.
3. Bounded Waiting
A process will not wait indefinitely to enter the critical section.

Limitations
  Works only for two processes
 Uses busy waiting, which wastes CPU cycles
 Assumes atomic read and write operations

Explain Synchronization Hardware

Explanation

In concurrent systems, multiple processes or threads may attempt to access shared data
simultaneously. Software-only solutions to synchronization may not always be reliable due to
race conditions. To overcome this, modern computer systems provide hardware support for
synchronization, which allows the operating system to implement safe and efficient mutual
exclusion mechanisms.

Example

When two processes attempt to update a shared variable at the same time, hardware
instructions ensure that only one process performs the update at a time by executing certain
operations atomically.

Main Answer

Synchronization hardware refers to special hardware instructions provided by the CPU

that help implement mutual exclusion and solve the critical section problem safely.

These instructions execute atomically, meaning they cannot be interrupted once started.

Hardware Synchronization Techniques

1. Interrupt Disabling

 On a single-processor system, mutual exclusion can be achieved by disabling

interrupts.
 When interrupts are disabled, the currently running process cannot be preempted.

Limitation:
  Not suitable for multiprocessor systems
 Disabling interrupts for long durations degrades system performance

2. Atomic Instructions

Modern processors provide special atomic instructions to support synchronization.

a) Test-and-Set Instruction

 Tests the value of a memory location and sets it in one atomic operation.
 Used to implement spinlocks.

Working:

 If the lock is already set, the process waits (busy waiting).

 If not set, the process acquires the lock and enters the critical section.

b) Compare-and-Swap Instruction

 Compares the contents of a memory location with an expected value.

 If equal, it updates the memory location atomically.

Working:

 Ensures that updates occur only if the value has not changed.

Explain Mutex Locks

Explanation

In concurrent systems, multiple processes or threads may try to access shared resources at
the same time. To prevent race conditions and ensure data consistency, the operating system
provides synchronization mechanisms. One of the most basic and widely used
synchronization tools is the mutex lock.
Example

Consider two threads updating a shared counter. If both threads update the counter
simultaneously, the result may be incorrect. By using a mutex lock, only one thread is
allowed to update the counter at a time, while the other thread waits.

Main Answer

A mutex lock (mutual exclusion lock) is a synchronization mechanism used to ensure that
only one process or thread can access a critical section at a time.

A mutex lock provides two basic operations:

 acquire() – used to lock the critical section

 release() – used to unlock the critical section

Working of Mutex Locks

 Before entering the critical section, a process must acquire the mutex lock.
 If the lock is already held by another process, the requesting process waits.
 Once the process exits the critical section, it releases the lock.
 The lock then becomes available for another waiting process.

Thus, mutex locks enforce mutual exclusion.

Characteristics of Mutex Locks

1. Binary Lock
A mutex can have only two states: locked or unlocked.
2. Ownership
Only the process or thread that acquires the lock is allowed to release it.
3. Busy Waiting (Spinlock)
In some implementations, a waiting process continuously checks for lock availability,
leading to busy waiting.

Explain Semaphore Usage and Implementation

Explanation

When multiple processes or threads execute concurrently and share resources, simple mutual
exclusion mechanisms may not be sufficient. To handle more complex synchronization
requirements such as process coordination, signaling, and resource counting, operating
systems use semaphores. Semaphores are one of the most powerful and widely used
synchronization tools.

Example

Consider a printer shared by multiple processes. Only a fixed number of processes should be
allowed to access the printer at a time. A semaphore can be used to control and limit access to
the printer resource.

Main Answer

A semaphore is a synchronization variable used to control access to shared resources by

multiple processes or threads.

A semaphore is accessed only through two atomic operations:

 wait() (also called P operation)

 signal() (also called V operation)

Semaphore Operations

Let S be a semaphore variable.

wait(S)

 Decrements the value of semaphore S

 If the value becomes negative, the process is blocked and placed in a waiting queue

wait(S) {
while (S <= 0)
; // busy wait
S--;
}

signal(S)

 Increments the value of semaphore S

 If processes are waiting, one process is awakened
signal(S) {
S++;
}

Types of Semaphores

1. Binary Semaphore

 Semaphore value is either 0 or 1

 Used to implement mutual exclusion
 Similar to a mutex lock

Usage:
Protecting a critical section

2. Counting Semaphore

 Semaphore value can be any non-negative integer

 Used to control access to a finite number of identical resources

Usage:
Managing multiple instances of a resource (e.g., database connections)

Explain Classical Problems of Synchronization

Explanation

In operating systems, synchronization problems are used to illustrate and test

synchronization mechanisms such as semaphores, mutexes, and monitors. These problems
represent common situations where multiple processes or threads share resources and must
coordinate their execution to avoid race conditions, deadlock, and starvation.

The most well-known classical synchronization problems are:

 Bounded Buffer Problem

 Readers–Writers Problem
 Dining Philosophers Problem
a) Bounded Buffer Problem (Producer–Consumer Problem)

Explanation

The bounded buffer problem describes a situation where producer processes generate data
and place it into a buffer, while consumer processes remove data from the buffer. The buffer
has a fixed size, so producers must wait if the buffer is full, and consumers must wait if the
buffer is empty.

Example

A keyboard driver produces keystrokes and places them in a buffer, while an application
consumes these keystrokes. If the buffer is full, the keyboard must wait; if it is empty, the
application must wait.

Main Answer

The bounded buffer problem requires synchronization to ensure:

 Producers do not insert items into a full buffer

 Consumers do not remove items from an empty buffer
 Mutual exclusion while accessing the buffer

It is commonly solved using three semaphores:

 mutex – ensures mutual exclusion

 empty – counts empty buffer slots
 full – counts filled buffer slots

This ensures correct coordination between producers and consumers.

b) Readers–Writers Problem

Explanation

The readers–writers problem deals with a shared data structure that can be accessed by
multiple reader processes or writer processes.

 Readers only read the data and do not modify it

 Writers modify the data and require exclusive access
Example

A database system where multiple users can read records simultaneously, but updates must be
performed exclusively to maintain consistency.

Main Answer

The readers–writers problem requires synchronization to ensure:

 Multiple readers can access the shared data simultaneously

 Writers must have exclusive access
 No reader reads while a writer is writing

Different versions of the problem exist:

 First readers–writers problem: Readers are given priority

 Second readers–writers problem: Writers are given priority

Semaphores or mutex locks are used to control access and maintain data consistency.

c) Dining Philosophers Problem

Explanation

The dining philosophers problem illustrates synchronization issues when multiple processes
compete for a limited number of shared resources arranged in a circular manner.

Example

Five philosophers sit around a circular table with five chopsticks. Each philosopher needs
two chopsticks (left and right) to eat. Philosophers alternate between thinking and eating.

Main Answer

The dining philosophers problem highlights the challenges of:

 Deadlock – all philosophers hold one chopstick and wait for the other
 Starvation – some philosophers may never get to eat

Synchronization solutions ensure that:

  Philosophers pick up chopsticks in a controlled manner
 Deadlock and starvation are avoided

Solutions use:

 Semaphores
 Monitors
 Resource hierarchy techniques

Explain Monitors and Their Usage

Explanation

Low-level synchronization mechanisms such as semaphores and mutex locks are powerful
but difficult to use correctly, often leading to programming errors like deadlock and race
conditions. To overcome these difficulties, a high-level synchronization construct called a
monitor is used. Monitors provide a structured and safer way to achieve process
synchronization.

Example

In a shared buffer system, instead of explicitly using semaphores for mutual exclusion and
synchronization, a monitor can encapsulate the buffer and allow only one process at a time to
execute buffer-related operations, automatically ensuring correctness.

Main Answer

A monitor is a high-level synchronization construct that combines:

 Shared data
 Procedures that operate on the shared data
 Synchronization mechanisms

into a single module.

The key property of a monitor is that only one process can be active inside the monitor at
any time, ensuring mutual exclusion automatically.

Components of a Monitor
A monitor consists of the following components:

1. Shared Data Variables

Variables that are accessed and modified by concurrent processes.
2. Monitor Procedures
Functions that define how shared data can be accessed.
3. Condition Variables
Used to allow processes to wait and be signaled within the monitor.

Condition Variables and Operations

Condition variables support two basic operations:

 wait()
Causes the calling process to suspend execution until a condition is satisfied.
 signal()
Wakes up one waiting process.

When a process executes wait(), it releases the monitor and waits. When another process
executes signal(), a waiting process is resumed.

Usage of Monitors

Monitors are used for:

1. Mutual Exclusion
Ensures that only one process executes critical code at a time.
2. Process Synchronization
Coordinates execution order using condition variables.
3. Safe Resource Sharing
Protects shared data structures from inconsistent access.
4. Simplifying Synchronization Code
Reduces complexity compared to semaphores and mutex locks.