OPERATING SYSTEMS (UE24CS242B)

Unit 1 – Operating-System Services, Design and Implementation

Operating-System Services
An operating system provides an environment for the execution of programs.
It also offers services to both users and programs, making the system easier, safer, and more
efficient to use.
A View of Operating-System Services

This diagram illustrates how users and programs interact with the operating system through
various services.
User-Oriented Operating-System Services
Operating systems provide a set of services that are directly useful to users.
1. User Interface (UI)
Almost all operating systems provide a user interface to interact with the system.
Types of user interfaces:
• Command-Line Interface (CLI)
Uses command interpreters (shells) to accept text commands.
• Graphical User Interface (GUI)
Uses windows, icons, menus, and mouse interactions.
• Batch Interface
Commands are executed in batches with no user interaction.
2. Program Execution
The operating system must be capable of:
• Loading a program into memory
• Running the program
• Terminating execution
o Normally (successful completion)

Pavan A C (pavanac@[Link]) 1
 o Abnormally (error condition)
This service ensures smooth execution and cleanup of programs.
3. I/O Operations
A running program may require input/output operations, such as:
• Reading from a file
• Writing to a file
• Accessing I/O devices (keyboard, printer, disk, etc.)
The OS provides uniform access to I/O devices, hiding hardware complexities.
File-System Related Services
4. File-System Manipulation
The file system is one of the most important components of an OS.
Programs may need to:
• Read and write files
• Create and delete files and directories
• Search for files
• List file information
• Manage permissions
The OS ensures data integrity and controlled access.
5. Communications
Processes may need to exchange information:
• On the same computer
• Across different computers over a network
Communication mechanisms include:
• Shared memory
• Message passing, where packets are moved by the OS
This service is essential for multiprogramming and distributed systems.
Error Detection Services
6. Error Detection
The operating system must constantly monitor for errors that may occur in:
• CPU
• Memory
• I/O devices

Pavan A C (pavanac@[Link]) 2
 • User programs
For each type of error:
• OS takes appropriate corrective action
• Ensures system consistency and correctness
Debugging facilities provided by the OS help programmers and users identify issues
efficiently.
System-Oriented Operating-System Services
Apart from user-oriented services, the OS also provides services to ensure efficient system
operation.
7. Resource Allocation
When multiple users or jobs run concurrently:
• OS must allocate resources fairly and efficiently
Resources include:
• CPU cycles
• Main memory
• File storage
• I/O devices
Scheduling and allocation policies determine how resources are shared.
8. Accounting
The operating system keeps track of:
• Which users use the system
• How much of each resource is used
• Type of resources consumed
Accounting information is useful for:
• System tuning
• Usage analysis
• Billing in shared or cloud environments
9. Protection and Security
Protection and security are critical in multiuser and networked systems.
• Protection
o Ensures that processes do not interfere with each other
o Controls access to system resources
• Security

Pavan A C (pavanac@[Link]) 3
 o Protects the system from external attacks
o Requires user authentication
o Prevents unauthorized access to devices and data
System Calls
System calls provide the interface between a program and the operating system.
• They allow programs to request services from the OS
• Usually written as high-level language routines
• Internally implemented in assembly or low-level code
Types of System Calls
System calls are grouped into six major categories:
1. Process Control
o Create, terminate, load, execute processes
2. File Manipulation
o Read, write, create, delete files
3. Device Manipulation
o Request and release devices
o Read/write device data
4. Information Maintenance
o Get/set system and process information
5. Communications
o Message passing
o Shared memory operations
6. Protection
o Control access permissions
o Set user privileges
Example of a System Call
Consider the execution of a printf() statement in a C program:
1. User program calls printf()
2. C library intercepts the call
3. C library invokes the system call write()
4. OS performs the write operation
5. Return value is passed back to the user program

Pavan A C (pavanac@[Link]) 4
This shows how user-level functions interact with kernel services.
Operating-System Design and Implementation
Designing an OS is a complex software engineering task.
Design Goals
Design starts by defining goals and specifications, influenced by:
• Hardware platform
• Type of system (desktop, server, mobile, embedded)
User Goals
• Easy to use
• Easy to learn
• Reliable
• Safe
• Fast
System Goals
• Easy to design, implement, and maintain
• Flexible
• Reliable
• Error-free
• Efficient
Policy vs Mechanism
A key principle in OS design is the separation of policy and mechanism.
• Policy: What will be done?
• Mechanism: How will it be done?
Separating the two:
• Increases flexibility
• Allows policy changes without modifying mechanisms
Example:
Using a timer mechanism to enforce a policy that prevents a process from running too long.
Implementation of Operating Systems
OS implementation varies widely.
Evolution
• Early operating systems → Assembly language
• Later → System programming languages (Algol, PL/1)

Pavan A C (pavanac@[Link]) 5
 • Modern OS → Mainly C and C++
Typical Language Usage
• Lowest levels → Assembly
• Kernel core → C
• System programs → C, C++, scripting languages (Python, Perl, Shell)
Trade-offs
• High-level languages:
o Easier to maintain and port
o Slightly slower
• Emulation:
o Allows OS to run on non-native hardware
o Performance overhead exists

Pavan A C (pavanac@[Link]) 6
 OPERATING SYSTEMS (UE24CS242B)
Unit 1 – Process Concept (Process Management)
Process Concept
An operating system executes a variety of programs:
• Batch systems → execute jobs
• Time-shared systems → execute user programs or tasks
In operating-system literature, the terms job and process are often used interchangeably.
Process vs Program
• A program is a passive entity
o Stored on disk as an executable file
• A process is an active entity
o A program in execution
A program becomes a process when:
• Its executable file is loaded into memory
• Execution begins (via GUI click, command line, script, etc.)
One program can have multiple processes
• Example: Multiple users running the same editor simultaneously
Process Concept – Memory Representation
A process consists of several parts in memory:
1. Text Section
o Program code
o Instructions to be executed
2. Current Activity
o Program Counter
o Processor Registers
3. Stack
o Temporary data
o Function parameters
o Return addresses
o Local variables
4. Data Section
o Global and static variables

Pavan A C (pavanac@[Link]) 1
 5. Heap
o Dynamically allocated memory during runtime
Memory Layout of a C Program

This layout explains how different segments of a program are organized in memory during
execution.
Memory Layout of a Process

Pavan A C (pavanac@[Link]) 2
Process State
As a process executes, it changes state.
Common Process States
1. New
o Process is being created
2. Running
o Instructions are currently being executed
3. Waiting
o Process is waiting for an event (e.g., I/O completion)
4. Ready
o Process is waiting to be assigned to a CPU
5. Terminated
o Process has finished execution

Process Control Block (PCB)

Each process is represented in the operating system by a Process Control Block (PCB)
(also called Task Control Block).
Contents of Process Control Block
The PCB contains all information needed to manage a process:
• Process state
o New, ready, running, waiting, terminated
• Program counter
o Address of next instruction to execute
• CPU registers
o Contents of all process-specific registers
• CPU scheduling information

Pavan A C (pavanac@[Link]) 3
 o Priority
o Scheduling queue pointers
• Memory-management information
o Memory allocated to the process
• Accounting information
o CPU time used
o Elapsed time
o Time limits
• I/O status information
o I/O devices allocated
o List of open files
CPU Switch from Process to Process
When the CPU changes from executing one process to another, the system performs a
context switch.

Process Scheduling
The objective of process scheduling is to:
• Maximize CPU utilization
• Support time sharing
• Ensure fairness among processes
A process scheduler selects a process for execution on the CPU.
Scheduling Queues
The operating system maintains several scheduling queues:
1. Job Queue

Pavan A C (pavanac@[Link]) 4
 o All processes in the system
2. Ready Queue
o Processes in main memory
o Ready to execute
3. Device Queues
o Processes waiting for I/O devices
Processes migrate among these queues during execution.
Ready Queue and I/O Device Queues

Representation of Process Scheduling

Schedulers
Short-Term Scheduler (CPU Scheduler)
• Selects the next process to execute on the CPU
• Invoked very frequently (milliseconds)
• Must be extremely fast
• Often the only scheduler in a system

Pavan A C (pavanac@[Link]) 5
Long-Term Scheduler (Job Scheduler)
• Selects processes to be admitted into the ready queue
• Invoked infrequently (seconds or minutes)
• Controls the degree of multiprogramming
• May be slow
Types of Processes
Processes are broadly classified as:
1. I/O-Bound Process
o Spends more time doing I/O
o Many short CPU bursts
2. CPU-Bound Process
o Spends more time doing computation
o Few long CPU bursts
The long-term scheduler tries to maintain a good mix of both.
Medium-Term Scheduler
A medium-term scheduler may be introduced to:
• Reduce the degree of multiprogramming
Swapping
• Process is removed from memory
• Stored on disk
• Later brought back to continue execution

Context Switch
A context switch occurs when:
• CPU switches from one process to another
Steps involved:
1. Save the state of the current process in its PCB
2. Load the saved state of the next process
Key Points

Pavan A C (pavanac@[Link]) 6
 • Context switch time is overhead
• No useful work is done during switching
• Time depends on:
o Hardware support
o PCB complexity
• Some CPUs support multiple register sets to reduce switch time
Operations on Processes
The operating system must provide mechanisms for:
• Process creation
• Process termination
Process Creation
• A parent process can create child processes
• Child processes may create further processes
• Forms a process tree
Each process is identified by a Process ID (PID).
Resource Sharing Options
• Parent and child share all resources
• Child shares a subset of parent’s resources
• Parent and child share no resources
Execution Options
• Parent and child execute concurrently
• Parent waits until child terminates
Process Creation using fork()
• fork() creates a new process
• Child process is a duplicate of the parent
• Address space is copied
To run a different program:
• exec() is used
• Replaces the process memory with a new program
UNIX Example
• fork() → creates child process
• exec() → loads new program into child

Pavan A C (pavanac@[Link]) 7
C Program – Forking Separate Process

Process Termination
A process terminates when:
• It executes its last statement
• Calls the exit() system call
Termination Details
• Status value returned from child to parent
• Parent retrieves status using wait()
• OS deallocates all process resources
Parent Terminating Child
Parent may terminate a child using abort() if:
• Child exceeds allocated resources
• Task assigned to child is no longer needed
• Parent itself is terminating
Cascading Termination
Some operating systems do not allow a child to exist without a parent.
• If parent terminates → all children terminate
• This is called cascading termination
• Initiated by the operating system
Zombie and Orphan Processes
• Zombie process
o Child terminates
o Parent has not called wait()
• Orphan process
o Parent terminates before child
o Child is adopted by init/system process
Important Scenarios
• What happens if parent terminates before child?

Pavan A C (pavanac@[Link]) 8
 • What happens if child terminates before parent (parent sleeping)?
• How to determine the state of a process?
These are handled using process tables and system calls like wait().

Pavan A C (pavanac@[Link]) 9
 OPERATING SYSTEMS (UE24CS242B)
Unit 1 – System Calls for Process Management & Life Cycle of an I/O Request
System Calls for Process Management
System calls provide the mechanism through which a process requests services from the
operating system related to process creation, execution, synchronization, and termination.
Process Identifiers (PID)
• Every process is assigned a unique process identifier (PID).
• PID is a non-negative integer.
• PID is the only universally known identifier that uniquely identifies a process.
• PIDs are often embedded into other identifiers to ensure uniqueness.
PID Reuse
• Although PIDs are unique at any instant, they are reused after processes terminate.
• UNIX systems use algorithms to delay PID reuse so that newly created processes do
not get recently used PIDs, avoiding confusion.
fork() System Call
• An existing process creates a new process by calling fork().
• The newly created process is called the child process.
Return Values
• Child process → returns 0
• Parent process → returns PID of the child
• Error → returns -1
Behavior
• Child is an exact copy of the parent.
• Child receives a copy of:
o Data segment
o Heap
o Stack
• Both parent and child continue execution from the instruction following fork().

vfork() System Call

• vfork() creates a new process without copying the address space of the parent.
• Assumes the child will immediately call:

Pavan A C (pavanac@[Link]) 1
 o exec() or
o exit()
Key Characteristics
• Child shares the parent’s address space temporarily.
• Guarantees that child runs first.
• Parent is suspended until the child:
o Calls exec() or
o Calls exit()
Return Values
• Child → 0
• Parent → PID of child
• Error → -1
vfork() is faster than fork() but must be used carefully.
exit() – Process Termination
A process can terminate normally in the following ways:
1. Returning from main()
2. Calling exit()
3. Calling _exit() or _Exit()
4. Returning from the start routine of the last thread
5. Calling pthread_exit() from the last thread
Abnormal Termination
A process can terminate abnormally by:
1. Calling abort()
2. Receiving certain signals
3. Last thread responding to a cancellation request
Kernel Actions on Termination
Regardless of termination type:
• Kernel closes all open file descriptors
• Kernel releases all memory used by the process
wait() and waitpid()
These system calls allow a parent process to synchronize with its child processes.
Possible Behaviors

Pavan A C (pavanac@[Link]) 2
A process calling wait() or waitpid() can:
1. Block
o If all child processes are still running
2. Return immediately
o If a child has already terminated and is waiting
3. Return error
o If the process has no children
If called after receiving SIGCHLD, wait() returns immediately.
Return Values
• Returns PID of child on success
• Returns 0 if state hasn’t changed
• Returns -1 on failure
waitid()
• waitid() allows finer control over which child process to wait for.
• Uses separate arguments instead of combining PID and process group.
Return Values
• 0 → success
• -1 → error
exec() Family of System Calls
• When a process calls an exec() function:
o The current process image is completely replaced
o New program starts execution at its main() function
Important Points
• PID does NOT change
• No new process is created
• Text, data, heap, and stack are replaced
Return Value
• Returns -1 on error
• Does not return on success

Pavan A C (pavanac@[Link]) 3
getpid() and getppid()
• getpid()
→ Returns the PID of the calling process
• getppid()
→ Returns the PID of the parent process
If the original parent has terminated:
• Process is re-parented
• Parent PID changes to the new parent (usually init/system process)
Race Condition
A race condition occurs when:
• Multiple processes access shared data
• Final result depends on execution order
Race Conditions with fork()
• After fork(), parent and child execute concurrently
• It is unpredictable which one runs first
• Logic depending on execution order can fail
Waiting and Polling
If a process wants to:
• Wait for a child → use wait()
• Wait for a parent → polling loop may be used
Problem with Polling
• Polling wastes CPU time
• Process wakes periodically just to check a condition
Solution
• Use signaling mechanisms instead of polling
• Signals avoid race conditions and CPU wastage

Pavan A C (pavanac@[Link]) 4
Life Cycle of an I/O Request – Overview
• An I/O request is made by a running process to access an input or output device.
• Input devices: keyboard, mouse, network
• Output devices: display, printer
• I/O operations are much slower than CPU operations.
• The operating system acts as an intermediary between processes and hardware.
The I/O life cycle defines the steps from request initiation to completion.
I/O Request Initiation and Kernel Processing
• Process initiates I/O using system calls:
o read(), write(), open()
• Control switches from user mode to kernel mode
• Kernel:
o Validates parameters
o Checks file descriptors and permissions
• OS identifies:
o Target device
o Corresponding device driver
• Request is packaged into a kernel I/O data structure
• Request is placed in the device I/O queue
• Request may be:
o Blocking
o Non-blocking
Device Driver and I/O Execution
• Device driver:
o Acts as a bridge between OS and hardware
o Converts generic I/O request into device-specific commands
• Device controller starts the I/O operation
• Requesting process:
o Is moved to Waiting (Blocked) state
• OS performs a context switch
• CPU executes other ready processes
This overlap improves CPU utilization and throughput

Pavan A C (pavanac@[Link]) 5
I/O Completion and Process Resumption
• Device completes the I/O operation
• Device generates an interrupt
• CPU transfers control to Interrupt Service Routine (ISR)
• ISR:
o Verifies completion
o Handles errors if any
• Blocked process moved to Ready state
• Scheduler selects the process
• Process resumes execution
• Control returns to user mode
• System call completes

Pavan A C (pavanac@[Link]) 6
 OPERATING SYSTEMS (UE24CS242B)
Unit 1 – CPU Scheduling
CPU Scheduling – Basic Concepts
In a computer system with a single CPU core, only one process can execute at a time. All
other processes must wait until the CPU becomes free and they are scheduled again.
The main objective of multiprogramming is to:
• Keep the CPU busy at all times
• Maximize CPU utilization
To achieve this:
• Several processes are kept in main memory
• When one process has to wait (usually for I/O), the OS:
o Takes the CPU away from that process
o Assigns the CPU to another ready process
This cycle continues, ensuring that the CPU rarely remains idle.
CPU Scheduling in Multicore Systems
On a multicore system, the same concept is extended:
• Each processing core should be kept busy
• Scheduling decisions are made independently for each core
• Improves overall system throughput and performance
CPU Scheduling – Need for Multiprogramming
In a simple system without multiprogramming:
• A process executes until it must wait (typically for I/O)
• During this waiting period, the CPU remains idle
• CPU time is wasted and no useful work is done
Multiprogramming allows the OS to:
• Switch the CPU to another ready process
• Use waiting time productively
This makes CPU scheduling a fundamental OS function.
Alternating Sequence of CPU and I/O Bursts
Process execution consists of an alternating sequence of CPU bursts and I/O bursts.
• CPU burst → process is executing instructions
• I/O burst → process is waiting for I/O completion
Maximum CPU utilization is achieved when:

Pavan A C (pavanac@[Link]) 1
 • CPU bursts of one process overlap with I/O bursts of another

CPU–I/O Burst Cycle

• Execution pattern:
o CPU burst → I/O burst → CPU burst → I/O burst → …
• CPU scheduling algorithms focus mainly on:
o The distribution of CPU burst times
Understanding this cycle is essential for designing efficient schedulers.
Histogram of CPU-Burst Times
The duration of CPU bursts:
• Varies widely among processes
• Follows a characteristic frequency distribution
Observations
• I/O-bound processes
o Many short CPU bursts
• CPU-bound processes
o Few long CPU bursts
This distribution is important when:
• Designing
• Evaluating
• Comparing CPU scheduling algorithms

Pavan A C (pavanac@[Link]) 2
CPU Scheduler
The CPU scheduler (short-term scheduler):
• Selects a process from the ready queue
• Allocates the CPU to that process
Ready Queue Organization
The ready queue may be organized in various ways:
• FIFO queue
• Priority queue
• Tree
• Unordered linked list
Each entry in the queue is a Process Control Block (PCB).
Preemptive Scheduling
CPU scheduling decisions can occur when a process:
1. Switches from running → waiting
2. Switches from running → ready
3. Switches from waiting → ready
4. Terminates
Scheduling Types
• Cases 1 and 4 → Non-preemptive
• Cases 2 and 3 → Preemptive
Issues in Preemptive Scheduling
When preemption occurs:
• Shared data access must be handled carefully
• Preemption while executing in kernel mode must be considered
• Interrupts may occur during critical OS operations
Examples
• Windows 3.x → Non-preemptive
• Windows 95 onwards → Preemptive
• Macintosh OS → Uses preemptive scheduling
Preemptive vs Non-Preemptive Scheduling
Problems with Preemptive Scheduling
• Can cause race conditions

Pavan A C (pavanac@[Link]) 3
 • Occurs when:
o One process is preempted while updating shared data
o Another process accesses inconsistent data
Solution
• Preemptive kernels use:
o Mutex locks
o Other synchronization mechanisms
Most modern operating systems are:
• Fully preemptive, even in kernel mode
Dispatcher
The dispatcher is a module that:
• Gives control of the CPU to the process selected by the short-term scheduler
Dispatcher Functions
• Performs context switch
• Switches CPU to user mode
• Jumps to the correct location in the user program
Dispatch Latency
• Time taken to:
o Stop one process
o Start another process
• Important performance metric
Scheduling Criteria
Scheduling algorithms are evaluated based on the following criteria:
1. CPU Utilization
o Percentage of time CPU is busy
2. Throughput
o Number of processes completed per unit time
3. Turnaround Time
o Time from submission to completion of a process
4. Waiting Time
o Total time a process spends waiting in the ready queue
5. Response Time

Pavan A C (pavanac@[Link]) 4
 o Time from request submission to first response
o Important in time-sharing systems
Scheduling Algorithm Optimization Criteria
An ideal scheduling algorithm should aim to:
• Maximize
o CPU utilization
o Throughput
• Minimize
o Turnaround time
o Waiting time
o Response time
Different scheduling algorithms optimize different criteria based on system goals.

Pavan A C (pavanac@[Link]) 5
 OPERATING SYSTEMS (UE24CS242B)
Unit 1 – CPU Scheduling Algorithms – FCFS and SJF
Scheduling Algorithms
Scheduling algorithms decide which process gets the CPU and for how long.
In this lecture, we study:
• First-Come, First-Served (FCFS)
• Shortest-Job-First (SJF) and its preemptive form
First-Come, First-Served (FCFS) Scheduling
FCFS is the simplest CPU scheduling algorithm.
Characteristics
• Processes are executed in the order they arrive
• Uses a FIFO queue
• Non-preemptive algorithm
• Once CPU is allocated, the process runs until completion or I/O wait
FCFS Example – Case 1
Suppose the processes arrive in the order: P₁, P₂, P₃

Process Burst Time

P1 24

P2 3

P3 3

Waiting Time
• Waiting time of P₁ = 0
• Waiting time of P₂ = 24
• Waiting time of P₃ = 27
Average Waiting Time
(0 + 24 + 27)/3 = 17

Pavan A C (pavanac@[Link]) 1
FCFS Example – Case 2
Suppose the processes arrive in the order: P₂, P₃, P₁

Waiting Time
• Waiting time of P₂ = 0
• Waiting time of P₃ = 3
• Waiting time of P₁ = 6
Average Waiting Time
(6 + 0 + 3)/3 = 3

Observation
• FCFS does not guarantee minimum average waiting time
• Performance varies greatly when CPU burst times differ significantly

Drawbacks of FCFS Scheduling

Convoy Effect
• Short processes get stuck behind a long process
• Example:
o One CPU-bound process
o Many I/O-bound processes
Additional Issues
• FCFS is non-preemptive
• A process can occupy the CPU for a long time
• Poor choice for time-sharing systems
• Not fair when responsiveness is important

Shortest-Job-First (SJF) Scheduling

SJF associates each process with the length of its next CPU burst.
Scheduling Rule
• Process with the shortest CPU burst is scheduled next
Key Properties

Pavan A C (pavanac@[Link]) 2
 • Optimal scheduling algorithm
• Produces minimum average waiting time
• Can be:
o Non-preemptive (SJF)
o Preemptive (Shortest-Remaining-Time-First)
Main Challenge
• Exact length of next CPU burst is not known in advance
• Must be predicted
Example of SJF Scheduling

Process Burst Time

P1 6

P2 8

P3 7

P4 3

Average Waiting Time (SJF)

(3 + 16 + 9 + 0)/4 = 7

Comparison with FCFS

If FCFS is used:
(0 + 6 + 14 + 21)/4 = 10.25

Observation
• SJF gives better (lower) average waiting time than FCFS

Determining Length of Next CPU Burst

Since actual burst time is unknown, OS predicts it using exponential averaging.

Pavan A C (pavanac@[Link]) 3
Formula
𝜏𝑛+1 = 𝛼𝑡𝑛 + (1 − 𝛼)𝜏𝑛

Where:
• 𝜏𝑛+1 → predicted next CPU burst
• 𝑡𝑛 → actual last CPU burst
• 𝜏𝑛 → previous prediction
• 𝛼→ weighting factor (0 ≤ α ≤ 1)
Notes
• α controls importance of recent history
• Commonly α = 0.5
• SJF preemptive version is called Shortest-Remaining-Time-First (SRTF)
Numerical Example – Exponential Averaging
Given:
• 𝑇1 = 10
• 𝛼 = 0.5
• Previous CPU bursts: 8, 7, 4, 16
Since SJF is non-preemptive, order becomes: 4, 7, 8, 16
Calculations
• 𝑇2 = 0.5 × 4 + 0.5 × 10 = 7
• 𝑇3 = 0.5 × 7 + 0.5 × 7 = 7
• 𝑇4 = 0.5 × 8 + 0.5 × 7 = 7.5
• 𝑇5 = 0.5 × 16 + 0.5 × 7.5 = 11.8
Result
• Predicted 5ᵗʰ CPU burst = 11.8
Prediction Behavior with Different α Values
Special Cases
• α=0
o 𝜏𝑛+1 = 𝜏𝑛
o Recent burst ignored
• α=1
o 𝜏𝑛+1 = 𝑡𝑛
o Only last burst considered

Pavan A C (pavanac@[Link]) 4
Expanded Formula
𝜏𝑛+1 = 𝛼𝑡𝑛 + (1 − 𝛼)𝛼𝑡𝑛−1 + ⋯ + (1 − 𝛼)𝑛+1 𝜏0

Each older burst has less weight, ensuring stability.

Shortest-Remaining-Time-First (SRTF)
• Preemptive version of SJF
• If a new process arrives with shorter remaining burst time, it preempts the running
process
SRTF Example

Average Waiting Time

[(10 − 1) + (1 − 1) + (17 − 2) + (5 − 3)]/4 = 6.5 ms

Pavan A C (pavanac@[Link]) 5
 OPERATING SYSTEMS (UE24CS242B)
Unit 1 – CPU Scheduling Algorithms – Priority & Round Robin
Priority Scheduling
In priority scheduling, a priority number (integer) is associated with each process.
Scheduling Rule
• CPU is allocated to the process with the highest priority
• Convention used: smaller integer ⇒ higher priority
Types
• Preemptive priority scheduling
o A running process can be preempted if a higher-priority process arrives
• Non-preemptive priority scheduling
o Running process continues until it finishes or blocks
Relation to SJF
• SJF is a special case of priority scheduling
• Priority = inverse of the predicted next CPU burst time
Problem in Priority Scheduling – Starvation
Starvation
• Low-priority processes may never get CPU time
• Occurs when high-priority processes continuously arrive
Solution – Aging
• Gradually increase the priority of a process as it waits
• Ensures that every process eventually executes
Example of Priority Scheduling

Average Waiting Time

Pavan A C (pavanac@[Link]) 1
 (6 + 0 + 16 + 18 + 1)/5 = 41/5 = 8.2

Round-Robin (RR) Scheduling

Round-Robin scheduling is designed specifically for time-sharing systems.
Key Characteristics
• Similar to FCFS, but preemption is added
• Uses a fixed time unit called time quantum or time slice
• Typical quantum length: 10–100 milliseconds
• Ready queue is treated as a circular queue
Working
• Each process gets the CPU for at most one time quantum
• If the process does not finish within the quantum:
o It is preempted
o Placed at the end of the ready queue
Round-Robin Scheduling – Example
Given processes (arrival time = 0):

Time quantum = 4 ms

Waiting Time
• P₁ waits for 6 ms (10 − 4)
• P₂ waits for 4 ms
• P₃ waits for 7 ms
Average Waiting Time
(6 + 4 + 7)/3 = 5.66 ms

Pavan A C (pavanac@[Link]) 2
Round-Robin Scheduling – Performance
If:
• n = number of processes in ready queue
• q = time quantum
Then:
• Each process gets 1/n of CPU time
• CPU is allocated in chunks of at most q time units
• A process waits no longer than (n − 1) × q time units for its next turn
Example
• 5 processes
• Time quantum = 20 ms
→ Each process gets 20 ms every 100 ms
Effect of Time Quantum Size
Very Large Time Quantum
• RR behaves like FCFS
• No effective preemption
Very Small Time Quantum
• Too many context switches
• High overhead
• Reduced CPU efficiency
Thus, RR performance depends heavily on the time quantum size.
Example – Effect of Time Quantum
Consider one process with burst time = 10 units
• Quantum = 12
o Process completes in one quantum
o No context switch overhead
• Quantum = 6
o Process needs 2 quanta
o One context switch
• Quantum = 1
o Process needs 10 quanta
o 9 context switches
o Execution slows significantly

Pavan A C (pavanac@[Link]) 3
Practical Considerations
• Modern systems typically use:
o Time quantum = 10–100 ms
• Context switch time:
o Usually < 10 microseconds
• Hence, context-switch overhead is a small fraction of the quantum
Turnaround Time vs Time Quantum
• Turnaround time varies with time quantum
• General guideline:
o 80% of CPU bursts should be shorter than the time quantum
This balances:
• Responsiveness
• Context-switch overhead
• CPU utilization

Pavan A C (pavanac@[Link]) 4
 OPERATING SYSTEMS (UE24CS242B)
Unit 1 – CPU Scheduling Algorithms – MQ, MLFQ & Multiprocessor Scheduling
Multilevel Queue Scheduling
In multilevel queue scheduling, the ready queue is partitioned into multiple separate
queues, based on the type of process.
Typical Queues
• Foreground queue → Interactive processes
• Background queue → Batch processes
Key Characteristics
• Each process is permanently assigned to one queue
• Each queue has its own scheduling algorithm
o Foreground → Round Robin (RR)
o Background → First-Come, First-Served (FCFS)
CPU Scheduling Between Queues
Scheduling must also be done between the queues, not just within a queue.
Methods
1. Fixed Priority Scheduling
o Foreground queue has higher priority than background queue
o All foreground processes are executed before background processes
o Can lead to starvation of background processes
2. Time-Slice Scheduling Between Queues
o Each queue gets a certain percentage of CPU time
o Example:
▪ 80% CPU time → Foreground (RR)
▪ 20% CPU time → Background (FCFS)
Multilevel Queue Scheduling – Priority Behavior
• Each queue has absolute priority over lower-priority queues
• A process in a lower queue cannot execute unless all higher-priority queues are
empty
• If a higher-priority process arrives:
o The currently running lower-priority process is preempted

Pavan A C (pavanac@[Link]) 1
Multilevel Feedback Queue (MLFQ) Scheduling
Multilevel feedback queue scheduling allows processes to move between queues.
Key Idea
• Unlike multilevel queue scheduling:
o Processes are not permanently assigned to a queue
• Supports aging
o Prevents starvation by gradually moving processes to higher-priority queues
Parameters Defining an MLFQ Scheduler
An MLFQ scheduler is defined by:
1. Number of queues
2. Scheduling algorithm for each queue
3. Method used to upgrade a process
4. Method used to demote a process
5. Method used to determine which queue a process enters when it needs CPU service
Example of Multilevel Feedback Queue
Consider three queues:
• Q₀ → Round Robin, time quantum = 8 ms
• Q₁ → Round Robin, time quantum = 16 ms
• Q₂ → FCFS
Execution Rules
1. A new process enters Q₀
2. It receives 8 ms
3. If not completed:
o Moved to Q₁

Pavan A C (pavanac@[Link]) 2
 4. In Q₁:
o Receives 16 ms
5. If still not completed:
o Moved to Q₂ (FCFS)

MLFQ – Queue Priority Rules

• Scheduler always executes processes in Q₀ first
• Q₁ is considered only when Q₀ is empty
• Q₂ is considered only when both Q₀ and Q₁ are empty
Preemption Rules
• Process arriving in Q₀ preempts processes in Q₁ and Q₂
• Process arriving in Q₁ preempts processes in Q₂
This ensures responsiveness for interactive processes.
Multiple-Processor Scheduling
When multiple CPUs are available:
• Load sharing becomes possible
• Scheduling becomes more complex
Asymmetric Multiprocessing (AMP)
Characteristics
• One processor (master) handles:
o Scheduling decisions
o I/O processing
o System activities
• Other processors execute only user code
Advantages
• Simple design
• Only one processor accesses system data structures

Pavan A C (pavanac@[Link]) 3
 • Less synchronization overhead
Symmetric Multiprocessing (SMP)
Characteristics
• Each processor is self-scheduling
• Processes may be:
o In a common ready queue, or
o In separate per-processor queues
• All modern operating systems support SMP
Processor Affinity
Concept
• When a process runs on a processor:
o Its data gets loaded into that processor’s cache
• Migrating the process to another processor:
o Invalidates old cache
o Requires cache repopulation
• This is expensive
To reduce this cost, OS tries to keep a process on the same processor.
Types of Processor Affinity
1. Soft Affinity
o OS attempts to keep a process on the same processor
o Migration is still possible
2. Hard Affinity
o OS allows process to specify which processors it may run on
o Implemented using system calls
Load Balancing
In SMP systems, load must be evenly distributed.
Goal
• Ensure all processors are utilized effectively
Requirement
• Mainly needed when each processor has its own ready queue
Load Balancing Techniques
1. Push Migration

Pavan A C (pavanac@[Link]) 4
 • A periodic task checks processor loads
• Moves processes from overloaded processors to idle or lightly loaded ones
2. Pull Migration
• An idle processor pulls a process from a busy processor
Push and pull migration can be used together.

Pavan A C (pavanac@[Link]) 5
 OPERATING SYSTEMS (UE24CS242B)
Unit 1 – Case Study – Linux & Windows Scheduling Policies
Case Study: Linux / Windows Scheduling Policies
This lecture studies real-world CPU scheduling implementations in two widely used
operating systems:
• Linux
• Microsoft Windows
The goal is to understand how theoretical scheduling concepts are applied in practical OS
designs.

Linux Scheduling Through Version 2.5

Process Scheduling in Early Linux
• Linux kernel used a variation of the traditional UNIX scheduling algorithm
• Limitations:
o Did not support SMP (Symmetric Multiprocessing)
o Poor performance with a large number of processes
• Scheduling decisions were inefficient for modern workloads

Linux Scheduling – Version 2.5

Major improvements were introduced:
Key Features
• Scheduler achieved constant-time scheduling: O(1)
• Added support for SMP systems
• Implemented:
o Processor affinity
o Load balancing across processors
Limitation
• Poor response time for interactive processes
• Not suitable for desktop systems with many short interactive tasks

Linux Scheduling in Version 2.6.23 and Later

Linux introduced the Completely Fair Scheduler (CFS).
Core Ideas

Pavan A C (pavanac@[Link]) 1
 • CFS is the default scheduling algorithm
• Based on scheduling classes
• Each class has a specific priority
• Kernel selects:
o Highest priority task
o From the highest priority scheduling class
Scheduling Classes
• CFS scheduling class
• Real-time scheduling class
• Additional classes can be added

Completely Fair Scheduler (CFS) – CPU Share Model

CFS aims to fairly distribute CPU time among all runnable tasks.
CPU Time Allocation
• Each task receives a proportion of CPU time
• Proportion is based on the nice value
o Range: −20 to +19
o Lower nice value → higher priority → more CPU time
Target Latency
• Time interval in which every runnable task should run at least once
• Target latency increases as number of active tasks increases
• CPU time slices are derived from this target latency

CFS – Virtual Runtime (vruntime)

CFS does not assign traditional priorities.
Virtual Runtime
• Each task maintains a virtual runtime (vruntime)
• Represents how much processor time the task has received
• Includes a decay factor based on priority:
o Lower priority → vruntime increases faster
• Default priority:
o vruntime ≈ actual runtime

Pavan A C (pavanac@[Link]) 2
Task Selection
• Scheduler always selects the task with the lowest vruntime

CFS – Data Structure Used

Balanced Binary Search Tree
• All runnable tasks are stored in a balanced binary search tree
• Key = vruntime
Operations
• Task becomes runnable → inserted into tree
• Task blocks → removed from tree
• Scheduler selects leftmost node (smallest vruntime)
Time Complexity
• Selection requires O(log N) time (N = number of runnable tasks)

CFS – I/O-Bound vs CPU-Bound Processes

Assume:
• Two tasks have the same nice value
• One is I/O-bound
• Other is CPU-bound
Behavior
• I/O-bound task accumulates less vruntime
• CPU-bound task accumulates more vruntime
• Result:
o I/O-bound task gets higher priority
o If I/O-bound task becomes runnable, it preempts CPU-bound task

Pavan A C (pavanac@[Link]) 3
This improves interactive responsiveness.

Linux Real-Time Scheduling

Linux supports POSIX.1b real-time scheduling.
Key Characteristics
• Real-time tasks have static priorities
• Priority range: 0 to 99
• Real-time tasks always preempt normal tasks
Global Priority Mapping
• Nice value −20 → global priority 100
• Nice value +19 → global priority 139
• Real-time priorities exist above normal tasks

Windows Scheduling
Windows uses a priority-based preemptive scheduling algorithm.
Core Principles
• Highest-priority thread always runs
• Scheduling handled by the dispatcher
• Selected thread runs until:
o Preempted by higher-priority thread
o Terminates
o Time quantum expires
o Calls a blocking system call

Windows Priority Scheme

Priority Levels
• 32 priority levels
• Priority 0 → reserved for memory management

Pavan A C (pavanac@[Link]) 4
 • Priority 1–15 → Variable class
• Priority 16–31 → Real-time class
If no runnable thread exists:
• Idle thread executes
Each priority level has its own ready queue.

Windows Priority Classes

Windows API defines the following priority classes:
• REALTIME_PRIORITY_CLASS
• HIGH_PRIORITY_CLASS
• ABOVE_NORMAL_PRIORITY_CLASS
• NORMAL_PRIORITY_CLASS
• BELOW_NORMAL_PRIORITY_CLASS
• IDLE_PRIORITY_CLASS
Notes
• All are variable priority classes, except REALTIME
• Each thread also has a relative priority:
o TIME_CRITICAL
o HIGHEST
o ABOVE_NORMAL
o NORMAL
o BELOW_NORMAL
o LOWEST
o IDLE

Windows Thread Priorities

A thread’s numeric priority is determined by:
• Process priority class
• Thread’s relative priority within the class
Base Priority
• Base priority is NORMAL within the class
• If time quantum expires:

Pavan A C (pavanac@[Link]) 5
 o Priority may be lowered
o Never reduced below base priority

Windows Priority Boosting

I/O Completion Boost
• If a thread wakes up after waiting:
o Priority may be temporarily boosted
• Boost depends on:
o What the thread was waiting for
Foreground vs Background
• Windows distinguishes foreground processes
• Foreground process gets 3× priority boost
• This allows:
o Foreground application to run longer
o Better user responsiveness

Pavan A C (pavanac@[Link]) 6
 OPERATING SYSTEMS (UE24CS242B)
Unit 1 – Bash Shell and cron
What is a Shell?
A shell is the Linux command-line interpreter.
• It provides an interface between the user and the kernel
• It reads user commands and executes them
• Commands may be:
o Built-in shell commands
o External programs
o Scripts
o User-defined applications
Example
If the user types:
ls
The shell interprets the command and asks the kernel to execute the ls program.
Shell Command Syntax
Commands entered at the shell prompt follow this syntax:
command [arg1] [arg2] ... [argn]
• Items in [ ] are optional
• Commands may run with or without arguments
Command Processing
1. Shell reads the entire line after pressing Enter
2. Shell parses the input into:
o Command name
o Options
o Filenames
3. Shell searches for the command:
o In the specified path (e.g., ./mycommand)
o Or in directories listed in the $PATH environment variable
4. If syntax is correct, kernel executes the command
Various Shells
Linux supports multiple shells:

Pavan A C (pavanac@[Link]) 1
 • sh
Bourne Shell (original UNIX shell)
• csh, tcsh - C-shell and its enhanced version
• ksh
Korn Shell
• bash
Bourne Again Shell
o Most popular shell
o Default in most Linux distributions
o Developed by GNU
Command to check current shell
echo $SHELL
Environment Variables
• Defined for the current shell
• Inherited by child processes
• Used to pass information to spawned programs
Shell Variables
• Exist only in the current shell
• Not inherited by child shells
• Used for temporary data (e.g., counters, paths)
Naming Convention
• Usually written in uppercase letters
Viewing Environment Variables
env
or
printenv
Common Environment Variables
• SHELL
Shell interpreting the commands (usually bash)
• TERM
Terminal type being emulated
• USER
Current logged-in user
• PWD
Present working directory

Pavan A C (pavanac@[Link]) 2
 • OLDPWD
Previous working directory (cd - uses this)
• PATH
List of directories searched for commands
• HOME
User’s home directory
Common Shell Variables
• BASHOPTS
Options enabled when bash was started
• BASH_VERSION
Bash version in human-readable form
• BASH_VERSINFO
Bash version in machine-readable form
Shell Basics
Creating a Shell Variable
varname=value
Accessing a Variable
echo $varname
Child Shell Behavior
• When a new shell is spawned:
o Shell variables from parent are not available
Exiting Child Shell
exit
Exporting Variables
To make a variable available to child shells:
export varname
Removing a Shell Variable
unset varname
Setting Environment Variables at Login
• Edit the .profile file in the $HOME directory
• Add export commands
Example:
export PATH=$PATH:/my/custom/path
This ensures variables are set automatically on login.

Pavan A C (pavanac@[Link]) 3
Shell Control Flow – if Statement
Shell scripts support conditional execution.
Example: Checking if a File Exists
if [ -f filename ]
then
echo "File exists"
else
echo "File does not exist"
fi
Concept to remember: if evaluates a condition and executes commands accordingly.
Shell Control Flow – Loops
Shell supports looping constructs such as:
• for
• while
• until
Nested Loop
• A loop inside another loop
• Used for multi-level iteration
Example:

Shell Control Flow – break and continue

• break
o Exits the loop immediately
• continue
o Skips the current iteration
o Moves to the next iteration

Pavan A C (pavanac@[Link]) 4
Used to control loop execution flow.

cron
What is cron?
• cron is a daemon (background service)
• Runs continuously after system boot
• Executes scheduled tasks automatically
The cron daemon is called crond.
cron Functionality
• Cron reads instructions from crontab (cron tables)
• Each user can have their own crontab
• Jobs are scheduled using a specific syntax
• Used for:
o Backups
o Log cleanup
o Periodic monitoring
o Automation
Checking cron Jobs
List scheduled cron jobs
crontab -l
Managing cron Service
• Check cron status
• Start cron service if not running
• Cron runs automatically at system boot in most systems
Adding Jobs to cron
Edit crontab
crontab -e

Pavan A C (pavanac@[Link]) 5
This command allows:
• Adding
• Editing
• Deleting cron jobs
cron Syntax
A cron job follows this format:
minute hour day month weekday command

cron Examples
Example: Execute a Program Every Minute
* * * * * command
View cron jobs
crontab -l

Pavan A C (pavanac@[Link]) 6