Advanced Operating Systems

Advanced Operating Systems

Session 2

Yayati Gupta
[Link]@[Link]

Mahindra University

December 11, 2024

Yayati Gupta (Mahindra University) Advanced Operating Systems December 11, 2024 1 / 25
Advanced Operating Systems

Outline

1 OS Design Architecture & Tradeoffs

2 Process Management
Basics
How is a process created
Logistics of Process Creation

3 CPU Scheduling

Yayati Gupta (Mahindra University) Advanced Operating Systems December 11, 2024 2 / 25
OS Design Architecture & Tradeoffs
Advanced Operating Systems
OS Design Architecture & Tradeoffs

OS Functionalities (Tradeoffs everywhere)

1 Abstraction
2 Virtualisation
3 Concurrency
4 Persistence
5 Security

Yayati Gupta (Mahindra University) Advanced Operating Systems December 11, 2024 4 / 25
Advanced Operating Systems
OS Design Architecture & Tradeoffs

Design Principles: Mainframes

1 Mainframes
Sequential batch processing (still used)
No virtualization/scheduling needed
because of non-interactive jobs, mostly
CPU bound
2 Minuscule OS: Low-level I/O libraries
3 No protection
Protection introduced later with user vs.
kernel mode separation (system calls)
Monolithic architecture
Figure: Image source: World of Computing

Yayati Gupta (Mahindra University) Advanced Operating Systems December 11, 2024 5 / 25
Advanced Operating Systems
OS Design Architecture & Tradeoffs

Yayati Gupta (Mahindra University) Advanced Operating Systems December 11, 2024 6 / 25
Advanced Operating Systems
OS Design Architecture & Tradeoffs

Design Principles: Mainframes

1 Mainframes
Sequential batch
processing
No virtualiza-
tion/scheduling
2 Minuscule OS:
Low-level I/O libraries
3 No protection
Protection
introduced later
with user vs. kernel
mode separation
Monolithic
architecture
Yayati Gupta (Mahindra University) Advanced Operating Systems December 11, 2024 7 / 25
Advanced Operating Systems
OS Design Architecture & Tradeoffs

Minicomputers/Personal Computers (PCs)

1 Multiprogramming became essential

For better response
I/O bound tasks
2 Need for virtualisation
3 Scheduling algorithms to balance fairness & responsiveness
Windows: Multilevel Feedback Queue Scheduling (MFQS)
Linux: Completely Fair Scheduling (CFS)
macOS: Hybrid scheduling based on priority and round robin policies
4 Kernel Architectures
DOS like: No multiprogramming
Microkernel (modularity, fault isolation)

Yayati Gupta (Mahindra University) Advanced Operating Systems December 11, 2024 8 / 25
Advanced Operating Systems
OS Design Architecture & Tradeoffs

Other kinds of Operating Systems

1 Real Time Operating Systems (RTOS)
Strict deadlines (Fire alarms, automotive systems)
Often periodic (Space shuttle direction navigator, fuel checker, gathering sensor data)
Specialised scheduling algorithms like Rate Monotonic & Earliest Deadline First
2 OSs for high security environments
Govt. and military systems, eg. SELinux
Cloud platforms like Amazon AWS, Google cloud
Strict distinction between user and kernel mode
Tightly controlled IPC
3 Embedded systems
Lightweight, limited resources
TinyOS
No virtualisation

Yayati Gupta (Mahindra University) Advanced Operating Systems December 11, 2024 9 / 25
Process Management
Advanced Operating Systems
Process Management
Basics

Process

1 Program vs Process
2 Fetch-Decode-Execute
3 Multiprogramming (Context Switching)

Yayati Gupta (Mahindra University) Advanced Operating Systems December 11, 2024 11 / 25
Advanced Operating Systems
Process Management
Basics

Process

Yayati Gupta (Mahindra University) Advanced Operating Systems December 11, 2024 12 / 25
Advanced Operating Systems
Process Management
How is a process created

How is a process created

Created by the OS using fork()
// create . c
# include < stdio .h >
# include < unistd .h >
int main ()
{
int x ;
printf ( " % d : Hello World \ n " , getpid ());
x = fork ();
printf ( " % d : x = % d Hello World \ n " , getpid () , x );
}

Rabbit virus/ Fork Bomb (Denial of Service) [lethal as compared to infinite loop/
recursion stack overflow]
pstree
Yayati Gupta (Mahindra University) Advanced Operating Systems December 11, 2024 13 / 25
Advanced Operating Systems
Process Management
How is a process created

Process Creation (contd): Use strace to see all syscalls

# include < stdio .h >
# include < unistd .h >

int main () {
int pid = fork (); // Create a child process
if ( pid == 0) { // In the child process
execlp ( " ls " , " ls " , " -l " , NULL ); // Replace child process with ’
perror ( " execlp failed " ); // If exec fails , print error
} else if ( pid > 0) {
printf ( " Parent process , PID : % d \ n " , getpid ());
} else {
perror ( " fork failed " ); // If fork fails , print error
}
return 0;
}
Yayati Gupta (Mahindra University) Advanced Operating Systems December 11, 2024 14 / 25
Advanced Operating Systems
Process Management
Logistics of Process Creation

Process in memory

Yayati Gupta (Mahindra University) Advanced Operating Systems December 11, 2024 15 / 25
Advanced Operating Systems
Process Management
Logistics of Process Creation

Process Control Block

struct task_struct {
pid_t pid ;
pid_t ppid ;
unsigned long state ;
struct sched_entity se ;
struct mm_struct * mm ;
struct file * files ;
struct task_struct * parent ;
// More fields
};

Yayati Gupta (Mahindra University) Advanced Operating Systems December 11, 2024 16 / 25
Advanced Operating Systems
Process Management
Logistics of Process Creation

Process lifecycle and queues

Yayati Gupta (Mahindra University) Advanced Operating Systems December 11, 2024 17 / 25
CPU Scheduling
Advanced Operating Systems
CPU Scheduling

Performance metrics

1 Turnaround Time
2 Waiting Time (WT)
3 Response Time (RT)
4 Throughput
5 CPU Utilization
6 Fairness
7 Context Switching Overhead

Yayati Gupta (Mahindra University) Advanced Operating Systems December 11, 2024 19 / 25
Advanced Operating Systems
CPU Scheduling

FCFS
1 Simple implementation
2 Non preemptive
3 Workload specific
A long process comes first
A bad workload example
P# AT CB IOB CB IOB CB IOB
P0 0 100 6 100 6 100 6
P1 1 1 6 1 6 1 6
P2 1 1 6 1 6 1 6
P3 1 1 6 1 6 1 6
P4 1 1 6 1 6 1 6
P5 1 1 6 1 6 1 6

Yayati Gupta (Mahindra University) Advanced Operating Systems December 11, 2024 20 / 25
Advanced Operating Systems
CPU Scheduling

SJF (A special case of priority scheduling)

1 Priority queue (sorted list/ min heap)
2 Non preemptive
3 Optimal
Can lead to starvation
Estimating the burst time?
User/programmer estimates
Historical data (Exponential Averaging)
Tn+1 = α · tn + (1 − α) · Tn
Tn+1 : Predicted burst time for the next process execution.
Tn : Predicted burst time for the current process.
tn : Actual burst time of the current process.
α (alpha): Weighting factor (0 ≤ α ≤ 1) that determines the influence of the most recent
burst time.
4 Preemptive version: SRTF
Yayati Gupta (Mahindra University) Advanced Operating Systems December 11, 2024 21 / 25
Advanced Operating Systems
CPU Scheduling

Evolving Approaches

1 Computational grids (2015): SVM, KNN, ANN and decision tree based approaches.
2 I/O burst prediction for HPC clusters (2023): Burst aware job scheduling
3 Don’t Stop Me Now: Embedding Based Scheduling for LLMs (2024): Predicting burst
size early using internal embeddings.
4 PREMA: A Predictive Multi-task Scheduling Algorithm For Preemptible Neural
Processing Units(2020): For DNN servers

Yayati Gupta (Mahindra University) Advanced Operating Systems December 11, 2024 22 / 25
Advanced Operating Systems
CPU Scheduling

Round Robin Scheduling

What will happen if the time quantum in the round robin scheduling is too low? What
if it is too high?

Yayati Gupta (Mahindra University) Advanced Operating Systems December 11, 2024 23 / 25
Advanced Operating Systems
CPU Scheduling

Which algorithm to choose?

1 Forecasting efficient scheduling algorithm (2023)

2 Intelligent Algorithm for Automatic Runtime Selection of Scheduling Algorithm Using
Pattern Recognition Techniques (2024)
3 Applying Machine Learning Techniques to Improve Linux Process Scheduling (2005)

Yayati Gupta (Mahindra University) Advanced Operating Systems December 11, 2024 24 / 25
Advanced Operating Systems
CPU Scheduling

Thank You

Questions?

Yayati Gupta (Mahindra University) Advanced Operating Systems December 11, 2024 25 / 25