Process Scheduling

Module 2
 Arrival time (AT) Arrival time is the time at which the process arrives in ready queue.
Burst time (BT) or CPU time of the process Burst time is the unit of time in which a particular process
completes its execution.
Completion time (CT) Completion time is the time at which the process has been terminated.
Turn-around time (TAT) The total time from arrival time to completion time is known as turn - around time.
TAT can be written as,

Turn-around time (TAT) = Completion time (CT) - Arrival time (AT)

TAT = Burst time (BT) + Waiting time (WT)

 Waiting time (WT) Waiting time is the time at which the process waits for its allocation while the previous
process is in the CPU for execution. WT is written as,

Waiting time (WT) = Turn-around time (TAT) - Burst time (BT)

Response time is the time at which CPU has been allocated to a particular process first time.

In case of non-preemptive scheduling, generally Waiting time and Response time is same.

Gantt chart is a visualization which helps to scheduling and managing particular tasks in a project. It is used while
solving scheduling problems, for a concept of how the processes are being allocated in different algorithms.
FCFS
In FCFS algorithm, the process that requests the CPU first is allocated in the CPU first. The implementation of
FCFS algorithm is managed with FIFO (First in first out) queue. FCFS scheduling is non-preemptive.

Non preemptive means, once the CPU has been allocated to a process, that process keeps the CPU until it
executes a work or job or task and releases the CPU, either by requesting I/O.

1. Arrival: Processes enter the system and are placed in a queue in the order they arrive.
2. Execution: The CPU takes the first process from the front of the queue, executes it until it is complete, and
then removes it from the queue.
3. Repeat: The CPU takes the next process in the queue and repeats the execution process.
SJF
This algorithm associates with each process the length of the process’s next CPU burst.
When the CPU is available, it is assigned to the
Priority Scheduling
● A priority is associated with each process, and the CPU is allocated to the process with the highest priority.
Equal-priority processes are scheduled in FCFS order.

● An SJF algorithm is simply a priority algorithm where the priority (p) is the inverse of the (predicted) next
CPU burst. The larger the CPU burst, the lower the priority, and vice versa.
Aging - Solution to Starvation
Aging is a scheduling technique used to prevent starvation by gradually increasing the priority of processes waiting too long in
the system.
● Ensures fairness, as long-waiting processes eventually get CPU time.
● Often combined with algorithms like priority scheduling or round-robin to balance short-term efficiency with
long-term fairness.

For example, if priorities range from 127 (low) to 0 (high), a waiting process can move up one level every 15 minutes,
ensuring even the lowest-priority process eventually gets executed.
Round-Robin Scheduling
The round-robin (RR) scheduling algorithm is designed especially for time-sharing systems. It is similar to FCFS
scheduling, but preemption is added to enable the system to switch between processes.

A small unit of time, called a time quantum or time slice, is defined. A time quantum is generally from 10 to 100
milliseconds in length. The ready queue is treated as a circular queue.
Multilevel Queue Scheduling is a CPU scheduling technique used in operating systems to manage processes by
dividing them into multiple queues based on specific characteristics, such as priority, process type, or resource
requirements. Each queue operates independently and may use a different scheduling algorithm.

Key Features

● Queue Division: Processes are categorized into distinct queues, such as:
● System processes
● Interactive processes
● Batch processes
● Background processes
● Priority Levels: Each queue is assigned a priority. Higher-priority queues are served before lower-priority
ones.
● Scheduling Algorithms: Different queues can use different scheduling algorithms, such as:
● First-Come, First-Served (FCFS)
● Round Robin (RR)
● Shortest Job Next (SJN)
● Fixed Assignment: Once a process is assigned to a queue, it remains there permanently.
 ● Processes are classified and assigned to specific queues.
● The CPU scheduler selects processes from the highest-priority queue first.
● If a queue is empty, the scheduler moves to the next lower-priority queue.
● Within a queue, the assigned scheduling algorithm determines the order of execution.

Advantages

● Specialized Handling: Different types of processes can be handled efficiently using tailored scheduling
algorithms.
● Priority Management: Critical processes are executed first, ensuring responsiveness.

Disadvantages

● Starvation: Lower-priority queues may suffer from starvation if higher-priority queues are always busy.
● Inflexibility: Processes cannot move between queues, which may lead to inefficiencies.
Multilevel feedback queue scheduling algorithm, in contrast, allows a process to move between queues.
The idea is to separate processes according to the characteristics of their CPU bursts.

If a process uses too much CPU time, it will be moved to a lower-priority queue.

This scheme leaves I/O-bound and interactive processes in the higher-priority queues. In addition, a
process that waits too long in a lower-priority queue may be moved to a higher-priority queue. This form
of aging prevents starvation.
In general, a multilevel feedback queue scheduler is defined by the following parameters:

● The number of queues

● The scheduling algorithm for each queue
● The method used to determine when to upgrade a process to a higher- priority queue
● The method used to determine when to demote a process to a lower- priority queue
● The method used to determine which queue a process will enter when that process
needs service
A critical section is a part of a program where shared resources (like memory, files, or
variables) are accessed by multiple processes or threads. To avoid problems such as race
conditions and data inconsistency, only one process/thread should execute the critical
section at a time using synchronization techniques.

Three important conditions need to be satisfied to ensure that processes do not interfere
with each other while trying to access shared resources are

Mutual exclusion,

Progress,

Bounded Waiting.
Mutual Exclusion Only one process or thread can execute in the critical section at a given
time. If two or more processes access shared resources (like variables or files) at the same
time without control, data inconsistency or corruption may occur. If process Pi is executing
in its critical section, then no other processes can be executing in their critical sections.

Progress If no process is executing in its critical section and some processes wish to enter
their critical sections, then only those processes that are not executing in their remainder
sections can participate in deciding which will enter its critical section next, and this
selection cannot be postponed indefinitely.

Bounded Waiting

There must be a limit on how many times other processes are allowed to enter the critical
section before a waiting process gets its turn. It is important to prevent starvation, where
one process waits indefinitely while others repeatedly enter the critical section.
A situation like this, where several processes access and manipulate the same data
concurrently and the outcome of the execution depends on the particular order in which the
access takes place, is called a race condition.

To guard against the race condition above, we need to ensure that only one process at a
time can be manipulating the variable counter. To make such a guarantee, we require that
the processes be synchronized in some way.
Entry Section
● The process requests permission to enter the critical section.
● Synchronization tools (e.g., mutex, semaphore) are used to control access.

Critical Section: The actual code where shared resources are accessed or modified.
Exit Section: The process releases the lock or semaphore, allowing other processes to
enter the critical section.
Remainder Section: The rest of the program that does not involve shared resource access

General approaches are used to handle critical sections:

 Preemptive Kernels: A preemptive kernel allows the operating system to interrupt or
preempt a process even when it is running in kernel mode.

Non-Preemptive Kernels: A non-preemptive kernel does not allow interruption of a

process that is running in kernel mode.

Critical Section Problem

Deadlock When two or more threads or processes wait for each other to release a critical
section, it can result in a deadlock situation in which none of the threads or processes can
move.

Starvation When a thread or process is repeatedly prevented from entering a critical

section, it can result in starvation, in which the thread or process is unable to progress.

Overhead When using critical sections, threads or processes must acquire and release locks
or semaphores, which can take time and resources.
Critical section
do{

flag=1;

while(flag); // (entry section)

// critical section

if (!flag)

// remainder section

} while(true);
Solution

acquireLock();

Process Critical Section

releaseLock();

A thread must acquire a lock prior to executing a critical section. The lock can be acquired
by only one thread.
classical problems in synchronization

It is standard scenarios used in operating systems and concurrent programming to

demonstrate and test synchronization mechanisms such as semaphores, mutexes, and
monitors. They focus on managing resource sharing and avoiding issues like deadlock or
race conditions.

● The Bounded-Buffer Problem(Producer-Consumer)

● The Readers –Writers Problem
● The Dining-Philosophers Problem
The Bounded-Buffer Problem (Producer-Consumer)

● Scenario: Producers generate data and place it into a buffer, while consumers remove data from the buffer.

● Challenges: Avoiding buffer overflow (producers writing to a full buffer) and underflow (consumers reading
from an empty buffer), and ensuring data consistency when multiple producers or consumers access the buffer.

● Synchronization Tools: Semaphores (for counting full/empty slots and controlling access), mutex (for mutual
exclusion).

Readers-Writers Problem
● Scenario: A shared database can be read by multiple readers at the same time, but writers need exclusive
access.
● Challenges: Preventing readers and writers from accessing the database simultaneously; ensuring fairness (no
starvation of readers or writers).
● Synchronization Tools: Mutexes and semaphores to control reader and writer access.
Dining Philosophers Problem
● Scenario: Multiple philosophers sit at a table, each needing two chopsticks (shared resources) to eat. They
alternate between thinking and eating.

● Challenges: Preventing deadlock (all philosophers pick up one chopstick and wait forever for the second),
starvation (some philosophers never get to eat).

● Synchronization Tools: Semaphores, monitors, or resource allocation strategies.

Mutex and semaphore are synchronization primitives used in operating systems to manage access to shared
resources and solve concurrency problems.

Definition: A mutex (Mutual Exclusion Object) is a locking mechanism used to ensure that only one thread or
process can access a resource at any given time.
Operations: Lock and unlock.
Ownership: Only the process that locks the mutex can unlock it.
Use Case: Ideal for protecting a single shared resource (e.g., a file or buffer) so that only one thread uses it at a time.

Definition: A semaphore is a signaling mechanism, typically represented by an integer variable, used to control
access to one or more resources.
Operations: Wait (P) and Signal (V).
Types:

● Counting Semaphore: Allows a fixed number of threads to access the resource concurrently.
● Binary Semaphore: Works like a mutex (value is 0 or 1).

Ownership: No specific ownership; any process can perform wait/signal operations.

Use Case: Useful for managing a pool of resources (like buffers in producer-consumer problem).
 ● Wait (P) or Down: Decrement the semaphore value. If the result is negative, the process is blocked (waits).

● Signal (V) or Up: Increment the semaphore value. If there are waiting processes, one gets unblocked.
Semaphores are widely used to ensure mutual exclusion and to coordinate process synchronization.

Types of Semaphores
1. Binary Semaphore (Mutex):
● Value can be only 0 or 1.
● Used for strict mutual exclusion.
● If value is 1, the resource is free; if 0, the resource is acquired.
2. Counting Semaphore:
● Value can be any non-negative integer.
● Used to control access to resources with multiple instances (e.g., a pool of printers).
● The count indicates the number of available resources.
Usage of Semaphores
● Mutual Exclusion: Protect critical sections to ensure only one process accesses shared resources at a
time.
● Process Synchronization: Coordinate processes so certain sequences of execution happen correctly.
● Resource Management: For limited resources, counting semaphores track availability.
● Common usage includes:
● Producer-consumer problem
● Reader-writer problem
● Dining philosophers problem

Semaphore Implementation
Semaphores are typically implemented with:
● An integer value.
● A queue for processes waiting on the semaphore.
● The operations are atomic to avoid race conditions.
P (wait) operation

wait(S):

S=S-1

if S < 0:

block the process and add it to the semaphore queue

V (signal) operation

signal(S):

S=S+1

if S <= 0:

remove a process from semaphore queue and wake it up

Example: Controlling Access to a Printer
● Suppose multiple processes need to print.
● Use a binary semaphore initialized to 1:
● Before accessing the printer, process does wait(semaphore).
● When printing is done, process does signal(semaphore).
● This ensures only one print job at a time, preventing conflicts.
A monitor is a high-level synchronization construct that combines mutual exclusion and the
ability to wait (block) for certain conditions to become true, simplifying process synchronization
in concurrent programming.

Key Features of Monitors

● Encapsulation: Monitors encapsulate shared data, the procedures to operate on that data, and
synchronization mechanisms into a single module or object.
● Mutual Exclusion: Only one thread can execute any procedure in the monitor at a time,
ensuring mutual exclusion without explicit locks by the programmer.
● Condition Variables: Monitors include condition variables that threads can use to wait for
and signal conditions, allowing threads to suspend execution until some state changes in the
monitor.
● Automatic Locking: Entering a monitor automatically acquires a lock; exiting releases it.
WORK:
● A thread enters the monitor if no other thread is executing inside it.
● If a thread needs to wait for a condition, it calls wait() on a condition variable and releases the lock
temporarily.
● Another thread can then enter the monitor, modify the state, and call signal() to wake waiting threads
when the condition changes.
● The waiting thread resumes execution once the condition is signaled and the lock is re-acquired.

Advantages
● Higher-level abstraction than semaphores or mutexes, reducing programming complexity and errors.
● Encapsulates data and synchronization together for safer concurrent access.
● Used in many modern programming languages (e.g., Java synchronized methods use monitors
internally)
classical two process and n-process solutions

It is important to control how different processes run at the same time. When multiple processes are working, we
have to control which process can change important information such as the variables in a program at that moment.

Such interference can be prevented by certain techniques, and one of the techniques is Peterson's Algorithm.

Critical-Section Problem

● Concurrent processes accessing shared data can lead to inconsistent results or race conditions.
● To ensure consistency, processes must be synchronized, especially when accessing critical sections of code.

Two-Process Synchronization Solutions

● Peterson's Solution:
● A classical software-based synchronization solution for two processes.
● Uses two shared variables: an array flag indicating intent to enter the critical section, and a variable turn
to resolve conflicts.
Ensures:

● Mutual Exclusion: Only one process in critical section at a time.

● Progress: No process is prevented from entering the critical section if free.
● Bounded Waiting: No starvation occurs and a process will eventually enter the critical section.

n-Process Synchronization Solutions: For multiple processes, more generalized solutions like:

● Bakery Algorithm: Uses numbers (like taking a ticket) to determine the execution order. Processes with
lower ticket numbers enter critical section first.
● Semaphore Mechanisms:
● Semaphores are integer variables accessed only through atomic operations wait() and signal().
● Counting semaphores and binary semaphores are used for managing access to resources.
● Mutex Locks and Monitors: Higher-level abstractions for synchronization.