Operating System — Unit 2

Process, Thread, Scheduling Complete

Exam Guide
Q1 Process vs Thread + Creation/Termination + State Diagram

Q2 FCFS, SJF, RR Scheduling — Gantt Charts + Avg WT & TAT

Q3 Round Robin (q=3) + Priority Scheduling — Gantt + Calculations

Q4 Process vs Program Differences

Q5 OS Services + Multiprocessor OS Types

Q6 Multiprogramming vs Multitasking vs Multiprocessing vs Distributed OS

Q7 Process Definition + State Transition Diagram

Q8 Threads + User Level vs Kernel Level Threads

Q9 SJF + RR Scheduling (P1=6,P2=8,P3=5,P4=25)

Q10 FCFS,SJF,Priority,RR — All Scheduling with Priority (5 processes)

Q11 Process Creation Events

Q12 PCB — Process Control Block + Fields

Q13 3-State Process Diagram

Q14 Preemptive + Non-Preemptive Priority Scheduling Gantt Charts

Q15 Process + States + Data Structures

Q16-Q18 Multithreading, Thread Structure, PCB

Q19 Schedulers + Queuing Diagram

Q20 Distributed System + Characteristics

Q21-Q22 5-State Process Transition Diagram

Q23 Disk Arm Scheduling Algorithms

Q1, Q4, Q7, Q15, Q22. Process vs Thread + State Diagram

What is a Process?
A process is a program in execution. When you run a program, the OS creates a process. A process includes
the program code, current activity (Program Counter), registers, stack, heap, and data segment.
Analogy: A recipe (program) vs cooking the dish (process). Same recipe can be cooked multiple times = same
program can have multiple processes!

What is a Thread?
A thread is the smallest unit of CPU execution within a process. A process can have multiple threads that
share the same memory and resources but run independently.
Analogy: A process is a restaurant kitchen. Threads are individual chefs — they share the same kitchen (memory)
but each cooks a different dish independently!

Difference Between Process and Thread:

Parameter Process Thread

Definition Program in execution Smallest unit of execution within process

Memory Own separate memory space Shares memory with other threads

Creation Heavy — takes more time & resources Light — fast creation

Communication Inter-Process Communication (IPC) needed Direct — shared memory

Context Switch Slow — saves/restores full state Fast — less state to save

Crash Effect One process crash doesn't affect others One thread crash can kill process

Resources Each process has own PCB, memory, files Shares PCB, memory, files of process

Overhead High overhead Low overhead

Example Chrome, MS Word (each app = process) Each browser tab = thread

Process vs Program:

Parameter Program Process

Nature Passive — just a set of instructions Active — program being executed

Storage Stored on disk (static) Exists in RAM (dynamic)

Lifetime Permanent until deleted Temporary — exists while running

Resources Needs no resources Needs CPU, memory, I/O

Example [Link] file on disk Running Notepad window

How to Create a Process:

A process can be created in the following ways:

Event Description

System Initialization When OS boots, several processes are created (init process, daemon processes)

System Call by Running Process A running process calls fork() to create a child process

User Request User double-clicks an icon — OS creates a new process

 Batch Job Submission OS creates a process to run a submitted batch job

// Creating process using fork() in UNIX

#include <unistd.h>
int main() {
int pid = fork(); // Create child process
if(pid == 0)
printf("Child process running\n");
else
printf("Parent process, child PID = %d\n", pid);
return 0;
}

How to Terminate a Process:

Reason Description

Normal Exit Process completes execution and calls exit() — voluntary

Error Exit Process encounters unrecoverable error (divide by zero)

Fatal Error OS kills process due to invalid memory access, illegal instruction

Killed by Another Process Parent kills child using kill() system call

Resource Unavailable OS terminates process when it requests unavailable resources

Process State Transition Diagram (5-State):

NEW (Process --> READY (Waiting for -->dispatch RUNNING (Using

created) admit CPU) <--timeout CPU)

| I/O or event wait v

I/O done --> (event WAITING/BLOCKED

complete) (I/O or event wait)

| exit() v

TERMINATED
(Process done)

State Description Example

NEW Process just created, not yet started Just double-clicked an app icon

READY Process waiting in queue for CPU App loaded, waiting for CPU turn

RUNNING Process currently using the CPU App actively executing code

WAITING/BLOCKED Process waiting for I/O or event App reading from hard disk

TERMINATED Process finished execution App closed, resources freed

Q2. CPU Scheduling — FCFS, SJF, Round Robin

Process Table:
Process Arrival Time CPU Burst Time

P1 0 7

P2 3 2

P3 4 3

P4 4 1

P5 5 3

(i) FCFS — First Come First Serve

Processes are scheduled in the order they arrive. Non-preemptive — once a process starts, it runs to
completion.

Execution Order: P1 → P2 → P3 → P4 → P5
Gantt Chart:

P1 P2 P3 P4 P5
0-7 7-9 9-12 12-13 13-16

FCFS Calculations:
Process | AT | BT | CT | TAT = CT-AT | WT = TAT-BT
--------|----|----|-----|-------------|------------
P1 | 0 | 7 | 7 | 7 - 0=7 | 7 - 7 = 0
P2 | 3 | 2 | 9 | 9 - 3=6 | 6 - 2 = 4
P3 | 4 | 3 | 12 | 12 - 4=8 | 8 - 3 = 5
P4 | 4 | 1 | 13 | 13 - 4=9 | 9 - 1 = 8
P5 | 5 | 3 | 16 | 16 - 5=11 | 11 - 3 = 8

Average Turnaround Time = (7+6+8+9+11)/5 = 41/5 = 8.2 ms

Average Waiting Time = (0+4+5+8+8)/5 = 25/5 = 5.0 ms

(ii) SJF — Shortest Job First (Non-Preemptive)

At each scheduling point, the process with the SHORTEST burst time among available processes is selected.
t=0: Only P1 available → Run P1 (BT=7), completes at t=7
t=7: Available: P2(BT=2), P3(BT=3), P4(BT=1), P5(BT=3)
Shortest: P4(BT=1) → Run P4, completes at t=8
t=8: Available: P2(BT=2), P3(BT=3), P5(BT=3)
Shortest: P2(BT=2) → Run P2, completes at t=10
t=10: Available: P3(BT=3), P5(BT=3) → Tie: P3 first
Run P3 (BT=3), completes at t=13
t=13: Run P5 (BT=3), completes at t=16

Gantt Chart:

P1 P4 P2 P3 P5
0-7 7-8 8-10 10-13 13-16

SJF Calculations:
Process | AT | BT | CT | TAT = CT-AT | WT = TAT-BT
--------|----|----|-----|-------------|------------
P1 | 0 | 7 | 7 | 7 - 0 = 7 | 7 - 7 = 0
P4 | 4 | 1 | 8 | 8 - 4 = 4 | 4 - 1 = 3
 P2 | 3 | 2 | 10 | 10 - 3 = 7 | 7 - 2 = 5
P3 | 4 | 3 | 13 | 13 - 4 = 9 | 9 - 3 = 6
P5 | 5 | 3 | 16 | 16 - 5 =11 | 11 - 3 = 8

Average Turnaround Time = (7+4+7+9+11)/5 = 38/5 = 7.6 ms

Average Waiting Time = (0+3+5+6+8)/5 = 22/5 = 4.4 ms

(iii) Round Robin — Time Quantum = 2

Each process gets CPU for a fixed time (quantum=2ms). If not finished, goes back to end of ready queue.
Time Quantum = 2ms

t=0: P1 arrives. Run P1 [0-2], remaining=5

t=2: P2 arrived(t=3? no, t=2 check): only P1 in queue → P1 runs
Actually at t=2: P2 not arrived yet. Continue P1 [2-3] when P2 arrives
Run P1 [2-4], P1 remaining=3. At t=3 P2 arrived, at t=4 P3,P4 arrived
t=4: Queue: P2(BT=2),P3(BT=3),P4(BT=1). Run P2 [4-6], P2 done!
t=6: Queue: P3(BT=3),P4(BT=1),P1(rem=3),P5(arr t=5). Run P3 [6-8],rem=1
t=8: Queue: P4(BT=1),P1(rem=3),P5(BT=3),P3(rem=1). Run P4[8-9], P4 done!
t=9: Queue: P1(rem=3),P5(rem=3),P3(rem=1). Run P1[9-11],rem=1
t=11: Queue: P5(rem=3),P3(rem=1),P1(rem=1). Run P5[11-13],rem=1
t=13: Queue: P3(rem=1),P1(rem=1),P5(rem=1). Run P3[13-14], P3 done!
t=14: Queue: P1(rem=1),P5(rem=1). Run P1[14-15], P1 done!
t=15: Run P5[15-16], P5 done!

Gantt Chart (q=2):

P1 P1 P2 P3 P4 P1 P5 P3 P1 P5
0-2 2-4 4-6 6-8 8-9 9-11 11-13 13-14 14-15 15-16

Process | AT | BT | CT | TAT = CT-AT | WT = TAT-BT

--------|----|----|-----|-------------|------------
P1 | 0 | 7 | 15 | 15-0 = 15 | 15-7 = 8
P2 | 3 | 2 | 6 | 6-3 = 3 | 3-2 = 1
P3 | 4 | 3 | 14 | 14-4 = 10 | 10-3 = 7
P4 | 4 | 1 | 9 | 9-4 = 5 | 5-1 = 4
P5 | 5 | 3 | 16 | 16-5 = 11 | 11-3 = 8

Average Turnaround Time = (15+3+10+5+11)/5 = 44/5 = 8.8 ms

Average Waiting Time = (8+1+7+4+8)/5 = 28/5 = 5.6 ms

Comparison Summary — Q2:

Algorithm Avg Turnaround Time Avg Waiting Time Best For

FCFS 8.2 ms 5.0 ms Simple, non-preemptive

SJF 7.6 ms 4.4 ms Minimum avg wait time

Round Robin (q=2) 8.8 ms 5.6 ms Interactive, fair

Q3. Round Robin (q=3) + Priority Scheduling

Process Table:
Process Burst Time Priority (5=highest)

P1 10 3

P2 2 2

P3 6 5

P4 8 4

P5 4 1
All processes arrive at time 0.

Round Robin (q=3):

Queue order (all arrive t=0): P1,P2,P3,P4,P5

t=0-3: P1 runs [0-3], P1 rem=7

t=3-5: P2 runs [3-5], P2 done! (BT=2, only 2ms left)
t=5-8: P3 runs [5-8], P3 rem=3
t=8-11: P4 runs [8-11], P4 rem=5
t=11-14:P5 runs [11-14] -- wait P5 BT=4, so [11-14]→only 3ms, P5 rem=1
t=14-17:P1 runs [14-17], P1 rem=4
t=17-20:P3 runs [17-20], P3 done! (rem=3, uses 3ms)
t=20-23:P4 runs [20-23], P4 rem=2
t=23-24:P5 runs [23-24], P5 done! (rem=1)
t=24-27:P1 runs [24-27], P1 rem=1
t=27-29:P4 runs [27-29], P4 done! (rem=2)
t=29-30:P1 runs [29-30], P1 done! (rem=1)

Gantt Chart RR(q=3):

P1 P2 P3 P4 P5 P1 P3 P4 P5 P1 P4 P1
0-3 3-5 5-8 8-11 11-14 14-17 17-20 20-23 23-24 24-27 27-29 29-30

Process | BT | CT | TAT=CT-0 | WT=TAT-BT

--------|----|----|----------|----------
P1 | 10 | 30 | 30 | 30-10=20
P2 | 2 | 5 | 5 | 5- 2= 3
P3 | 6 | 20 | 20 | 20- 6=14
P4 | 8 | 29 | 29 | 29- 8=21
P5 | 4 | 24 | 24 | 24- 4=20

Average Turnaround Time = (30+5+20+29+24)/5 = 108/5 = 21.6 sec

Average Waiting Time = (20+3+14+21+20)/5 = 78/5 = 15.6 sec

Priority Scheduling (Non-Preemptive):

Highest priority process runs first. Priority 5 = highest, 1 = lowest.

Execution Order: P3(5) → P4(4) → P1(3) → P2(2) → P5(1)

Gantt Chart Priority:

P3 P4 P1 P2 P5
0-6 6-14 14-24 24-26 26-30

Process | BT | Priority | CT | TAT=CT-0 | WT=TAT-BT

--------|----|----|----|----|----------
P3 | 6 | 5 | 6 | 6 | 6-6 = 0
P4 | 8 | 4 | 14 | 14 | 14-8 = 6
 P1 | 10 | 3 | 24 | 24 | 24-10 =14
P2 | 2 | 2 | 26 | 26 | 26-2 =24
P5 | 4 | 1 | 30 | 30 | 30-4 =26

Average Turnaround Time = (6+14+24+26+30)/5 = 100/5 = 20.0 sec

Average Waiting Time = (0+6+14+24+26)/5 = 70/5 = 14.0 sec

Q3 Comparison:
Algorithm Avg TAT Avg WT

Round Robin (q=3) 21.6 sec 15.6 sec

Priority Scheduling 20.0 sec 14.0 sec

Q5. OS Services + Multiprocessor OS Types

Operating System Services:

Service Description Example

Program Execution Load and run programs Running [Link]

I/O Operations Manage all I/O devices Print a document

File System Create/delete/read/write files Save Word document

Communication Process to process messaging Chat application

Error Detection Detect and handle errors Blue screen, disk error

Resource Allocation Distribute CPU/memory fairly Task Manager

Accounting Track resource usage per user Cloud billing

Protection Control access to resources Login, file permissions

User Interface CLI or GUI interface Windows Desktop, Terminal

Networking Manage network connections Connect to WiFi

Multiprocessor Operating System Types:

A Multiprocessor OS manages a computer system with two or more CPUs connected to a single shared
memory.

1. Symmetric Multiprocessing (SMP)

• All processors are equal — any processor can run any task
• All processors share the same memory and I/O bus
• Most common type used today
• Example: Modern Intel/AMD multi-core systems
Example: Windows, Linux on multi-core PC

2. Asymmetric Multiprocessing (AMP)

• One MASTER processor controls the system
• Other SLAVE processors execute assigned tasks
• Master handles scheduling and OS functions
• Simpler but less efficient than SMP
Example: Old mainframe systems

3. Massively Parallel Processing (MPP)

• Hundreds or thousands of CPUs
• Each processor has its own memory
• Connected via high-speed network
• Used for supercomputers and big data
Example: IBM Sequoia, NASA supercomputers

4. NUMA (Non-Uniform Memory Access)

• Multiple processors each with local memory
• Can access remote memory but slower
• Better scalability than SMP
• Used in high-performance servers
Example: AMD EPYC, Intel Xeon servers
Q6. Multiprogramming vs Multitasking vs Multiprocessing vs Distributed OS

Parameter Multiprogramming Multitasking Multiprocessing Distributed OS

Definition Multiple programs in memory

Multiplesimultaneously
tasks share CPU
Multiple
rapidlyCPUs in one system
Multiple computers work as one

CPU Single CPU Single CPU Multiple CPUs Multiple computers

Goal Maximize CPU utilization

Fast user response Increase throughput Resource sharing across network

Switching On I/O wait Time-based (quantum)Parallel execution Network-based

User Feel One at a time Simultaneous Actually parallel Single system

Memory Shared RAM Shared RAM Shared RAM Separate memories

Example Early mainframes Windows, Linux Modern multi-core PC Google, Amazon AWS

Speed Moderate Fast response Fastest Depends on network

Quick Summary:
• MULTIPROGRAMMING — Keep CPU busy by loading multiple programs in RAM
• MULTITASKING — Switch between tasks so fast that user feels all run simultaneously
• MULTIPROCESSING — Actually run tasks in parallel using multiple CPUs
• DISTRIBUTED OS — Run tasks across multiple computers connected by network
Q8, Q16, Q17. Threads — User Level vs Kernel Level

What is a Thread?
A thread (also called Lightweight Process) is the basic unit of CPU utilization. It consists of a Thread ID,
Program Counter, Register Set, and Stack. Threads within the same process share code, data, and OS
resources.

Thread Structure:

THREAD 1 PC | Registers | Stack THREAD 2 PC | Registers | Stack THREAD 3 PC | Registers | Stack

SHARED: Code Segment | Data Segment | OS Resources (files, signals)

Types of Threads:

1. User Level Threads (ULT):

• Managed by USER-LEVEL thread library (not OS kernel)
• Kernel doesn't know about these threads — sees only one process
• Thread switching done without kernel involvement (fast!)
• If one thread blocks (I/O), entire process blocks
• Cannot run truly parallel on multiple CPUs
• Examples: POSIX Pthreads, Java threads (green threads)
2. Kernel Level Threads (KLT):
• Managed directly by the OS KERNEL
• Kernel knows and schedules each thread individually
• If one thread blocks, others continue (no process-wide blocking)
• Can truly run in parallel on multiple CPUs
• Thread switching requires kernel mode switch (slower)
• Examples: Windows threads, Linux pthreads (NPTL)
Parameter User Level Threads Kernel Level Threads

Management User-level library OS Kernel

Speed Faster (no kernel call) Slower (kernel call needed)

Blocking Whole process blocks Only that thread blocks

Parallelism Cannot use multiple CPUs Can use multiple CPUs

Overhead Low overhead Higher overhead

Portability Portable across OS OS-specific

Examples Green threads, Pthreads Windows, Linux NPTL

When is each type BETTER?

Situation Better Choice Reason

Frequent thread switching User Level No kernel mode switch overhead

I/O-heavy applications Kernel Level One thread blocks, others continue

Multi-CPU parallelism Kernel Level Only KLT can use multiple CPUs

Portability needed User Level Not OS-specific

Real-time systems Kernel Level Better scheduling control

Large number of threads User Level Lower memory/creation overhead

Q9. SJF + RR Scheduling (All arrive at t=0)

Process Table:
Process CPU Burst Time

P1 6

P2 8

P3 5

P4 25

SJF (Shortest Job First — Non-Preemptive):

Order by burst time: P3(5) → P1(6) → P2(8) → P4(25)

P3 P1 P2 P4
0-5 5-11 11-19 19-44

Process | BT | CT | TAT | WT=TAT-BT

--------|----|----|-----|----------
P3 | 5 | 5 | 5 | 5-5 = 0
P1 | 6 | 11 | 11 | 11-6 = 5
P2 | 8 | 19 | 19 | 19-8 =11
P4 | 25 | 44 | 44 |44-25 =19

Average Waiting Time = (0+5+11+19)/4 = 35/4 = 8.75 ms

Average Turnaround Time = (5+11+19+44)/4 = 79/4 = 19.75 ms

Round Robin (q=4):

Queue: P1,P2,P3,P4 (all at t=0)
t=0-4: P1 runs, rem=2
t=4-8: P2 runs, rem=4
t=8-12: P3 runs -- P3 BT=5, so [8-12] rem=1
t=12-16:P4 runs, rem=21
t=16-18:P1 runs [16-18], P1 done!
t=18-22:P2 runs [18-22], P2 done!
t=22-23:P3 runs [22-23], P3 done!
t=23-27:P4 runs [23-27], rem=17
t=27-31:P4 runs [27-31], rem=13
t=31-35:P4 runs [31-35], rem=9
t=35-39:P4 runs [35-39], rem=5
t=39-43:P4 runs [39-43], rem=1
t=43-44:P4 runs [43-44], P4 done!

P1 P2 P3 P4 P1 P2 P3 P4
0-4 4-8 8-12 12-16 16-18 18-22 22-23 23-44

Process | BT | CT | TAT | WT=TAT-BT

--------|----|----|-----|----------
P1 | 6 | 18 | 18 | 18-6 =12
P2 | 8 | 22 | 22 | 22-8 =14
P3 | 5 | 23 | 23 | 23-5 =18
P4 | 25 | 44 | 44 |44-25 =19

Average Waiting Time = (12+14+18+19)/4 = 63/4 = 15.75 ms

Average Turnaround Time = (18+22+23+44)/4 = 107/4 = 26.75 ms
Q10. FCFS, SJF, Priority, RR(q=1) — All at t=0

Process Table:
Process Burst Time Priority (1=highest)

P1 8 5

P2 1 1

P3 3 2

P4 2 4

P5 5 3
Note: Lower priority number = HIGHER priority

(i) FCFS:

Order: P1→P2→P3→P4→P5

P1 P2 P3 P4 P5
0-8 8-9 9-12 12-14 14-19

P1: CT=8, TAT=8, WT=0

P2: CT=9, TAT=9, WT=8
P3: CT=12, TAT=12, WT=9
P4: CT=14, TAT=14, WT=12
P5: CT=19, TAT=19, WT=14
Avg TAT=(8+9+12+14+19)/5=62/5=12.4 Avg WT=(0+8+9+12+14)/5=43/5=8.6

(ii) SJF (Non-Preemptive):

Order by BT: P2(1)→P4(2)→P3(3)→P5(5)→P1(8)

P2 P4 P3 P5 P1
0-1 1-3 3-6 6-11 11-19

P2: CT=1, TAT=1, WT=0

P4: CT=3, TAT=3, WT=1
P3: CT=6, TAT=6, WT=3
P5: CT=11, TAT=11, WT=6
P1: CT=19, TAT=19, WT=11
Avg TAT=(1+3+6+11+19)/5=40/5=8.0 Avg WT=(0+1+3+6+11)/5=21/5=4.2

(iii) Non-Preemptive Priority (lower number = higher priority):

Order: P2(pri=1)→P3(pri=2)→P5(pri=3)→P4(pri=4)→P1(pri=5)

P2 P3 P5 P4 P1
0-1 1-4 4-9 9-11 11-19

P2: CT=1, TAT=1, WT=0

P3: CT=4, TAT=4, WT=1
P5: CT=9, TAT=9, WT=4
P4: CT=11, TAT=11, WT=9
P1: CT=19, TAT=19, WT=11
Avg TAT=(1+4+9+11+19)/5=44/5=8.8 Avg WT=(0+1+4+9+11)/5=25/5=5.0

(iv) Round Robin (q=1):

Each process gets 1ms at a time. Remaining after each round:
Initial: P1=8,P2=1,P3=3,P4=2,P5=5
t=0-1:P1, t=1-2:P2(done!,CT=2), t=2-3:P3, t=3-4:P4, t=4-5:P5
t=5-6:P1, t=6-7:P3, t=7-8:P4(done!,CT=8), t=8-9:P5
 t=9-10:P1, t=10-11:P3(done!,CT=11), t=11-12:P5
t=12-13:P1, t=13-14:P5
t=14-15:P1, t=15-16:P5
t=16-17:P1, t=17-18:P5(done!,CT=18)
t=18-19:P1(done!,CT=19)

P1 P2 P3 P4 P5 P1 P3 P4 P5 P1 P3 P5 P1 P5 P1 P5 P1 P5 P1

P1: CT=19, TAT=19, WT=19-8=11

P2: CT=2, TAT=2, WT=2-1=1
P3: CT=11, TAT=11, WT=11-3=8
P4: CT=8, TAT=8, WT=8-2=6
P5: CT=18, TAT=18, WT=18-5=13
Avg TAT=(19+2+11+8+18)/5=58/5=11.6 Avg WT=(11+1+8+6+13)/5=39/5=7.8

Q10 Final Comparison:

Algorithm Avg TAT (ms) Avg WT (ms)

FCFS 12.4 8.6

SJF (Non-Preemptive) 8.0 4.2

Priority (Non-Preemptive) 8.8 5.0

Round Robin (q=1) 11.6 7.8

Q11. Process Creation Events

What Triggers Process Creation?

1. System Initialization (Boot Time)

When OS starts, several processes are automatically created: • Foreground processes (user-facing) •
Background processes (daemons/services) Example: init process in Linux (PID=1) — parent of all processes

2. Process Creation by Another Process (fork())

A running process can create a child process using fork() system call. Child inherits parent's resources and
starts executing. Example: Shell creates child process to run a command

3. User Request
User launches an application: • Double-click icon → OS creates process • Type command in terminal → shell
creates process Example: Opening Chrome creates a new process

4. Initiation of a Batch Job

In batch systems, OS creates processes to handle submitted batch jobs. Jobs queued and processed
automatically. Example: Payroll processing on mainframe

5. Interrupt Handling
When an interrupt occurs, OS may create a service process to handle it. Example: Network data arrives → OS
creates process to handle it

Process Creation Steps:

Step 1: Assign unique Process ID (PID)
Step 2: Allocate memory (code, data, stack, heap)
Step 3: Initialize Process Control Block (PCB)
Step 4: Set initial priority
Step 5: Create required data structures
Step 6: Put process in READY queue
Q12, Q18. PCB — Process Control Block

What is a PCB?
A Process Control Block (PCB) is a data structure maintained by the OS for every process. It contains all
information the OS needs to manage a process. Think of it as the process's ID card or passport.
Analogy: PCB is like a student's record card in school — contains name, roll number, marks, attendance,
everything about that student!

PCB Structure Diagram:

PROCESS CONTROL BLOCK (PCB)

Process ID (PID)

Process State (New/Ready/Running/Blocked/Terminated)

Program Counter (PC) — address of next instruction

CPU Registers (Accumulator, Index, Stack Pointer...)

Memory Management Info (Base/Limit registers, page table)

I/O Status (Open files, I/O devices allocated)

Accounting Info (CPU time, time limits, process number)

CPU Scheduling Info (Priority, pointers to scheduling queues)

Field Purpose Example Value

Process ID (PID) Unique identifier for process PID = 1234

Process State Current state of process READY, RUNNING, BLOCKED

Program Counter Address of next instruction to execute 0x00401A3F

CPU Registers All register values saved on context switch AX=5, BX=10, SP=0xFF

Memory Info Base/limit addresses, page table pointer Base=4000, Limit=2000

I/O Status List of open files and I/O devices [Link], printer1

Priority Scheduling priority value Priority = 5

CPU Time Used Accounting — how much CPU used so far 45ms

Parent PID PID of parent process PPID = 1200

Q14. Preemptive + Non-Preemptive Priority Scheduling

Process Table:
Process Burst Time Priority Arrival Time

P1 10 5 0

P2 1 1 1

P3 2 3 2

P4 1 4 3

P5 5 2 4
Note: Lower number = HIGHER priority. (Priority 1 = most important)

(i) Non-Preemptive Priority Scheduling:

t=0: Only P1 available → Start P1 (runs to completion since non-preemptive)
P1 runs [0-10]
t=10: All others arrived. Remaining: P2(pri=1),P3(pri=3),P4(pri=4),P5(pri=2)
Highest priority = P2(pri=1) → Run P2 [10-11]
t=11: Remaining: P3(pri=3),P4(pri=4),P5(pri=2)
Highest priority = P5(pri=2) → Run P5 [11-16]
t=16: Remaining: P3(pri=3),P4(pri=4)
Highest priority = P3(pri=3) → Run P3 [16-18]
t=18: Only P4 left → Run P4 [18-19]

Non-Preemptive Gantt Chart:

P1 P2 P5 P3 P4
0-10 10-11 11-16 16-18 18-19

Process | AT | BT | CT | TAT=CT-AT | WT=TAT-BT

--------|----|----|----|-----------|-----------
P1 | 0 | 10 | 10 | 10-0=10 | 10-10=0
P2 | 1 | 1 | 11 | 11-1=10 | 10-1 =9
P3 | 2 | 2 | 18 | 18-2=16 | 16-2 =14
P4 | 3 | 1 | 19 | 19-3=16 | 16-1 =15
P5 | 4 | 5 | 16 | 16-4=12 | 12-5 =7

Avg TAT = (10+10+16+16+12)/5 = 64/5 = 12.8 ms

Avg WT = (0+9+14+15+7)/5 = 45/5 = 9.0 ms

(ii) Preemptive Priority Scheduling:

t=0: P1 arrives (pri=5) → Start P1
t=1: P2 arrives (pri=1 > P1's pri=5 i.e. P2 has HIGHER priority)
Preempt P1! → Run P2 [1-2], P1 rem=9
t=2: P2 done. P3 arrives(pri=3). Remaining: P1(pri=5),P3(pri=3)
P3 has higher priority → Run P3 [2-4], P1 rem=9
t=3: P4 arrives(pri=4). P3 running(pri=3). P3 > P4, continue P3.
t=4: P3 done. P5 arrives(pri=2). Remaining: P1(pri=5),P4(pri=4),P5(pri=2)
P5 highest priority → Run P5 [4-9]
t=9: P5 done. Remaining: P1(pri=5),P4(pri=4)
P4 higher priority → Run P4 [9-10]
t=10: P4 done. Only P1 left → Run P1 [10-19]

Preemptive Gantt Chart:

P1 P2 P3 P5 P4 P1
0-1 1-2 2-4 4-9 9-10 10-19

Process | AT | BT | CT | TAT=CT-AT | WT=TAT-BT

--------|----|----|----|-----------|-----------
 P1 | 0 | 10 | 19 | 19-0=19 | 19-10=9
P2 | 1 | 1 | 2 | 2-1=1 | 1-1 =0
P3 | 2 | 2 | 4 | 4-2=2 | 2-2 =0
P4 | 3 | 1 | 10 | 10-3=7 | 7-1 =6
P5 | 4 | 5 | 9 | 9-4=5 | 5-5 =0

Avg TAT = (19+1+2+7+5)/5 = 34/5 = 6.8 ms

Avg WT = (9+0+0+6+0)/5 = 15/5 = 3.0 ms

Comparison:
Method Avg TAT Avg WT Note

Non-Preemptive Priority 12.8 ms 9.0 ms Running process not interrupted

Preemptive Priority 6.8 ms 3.0 ms Higher priority preempts lower

Q19. Schedulers + Queuing Diagram

Types of Schedulers:

Scheduler Also Called Function Frequency

Long-Term Scheduler Job Scheduler Selects which jobs enter ready queue Infrequent
from job pool
(minutes)

Short-Term Scheduler CPU Scheduler Selects which ready process gets CPU
Very
nextfrequent (ms)

Medium-Term Scheduler Swapper Swaps processes in/out of memory (swapping)

Moderate

Queuing Diagram:

Long-Term Scheduler READY QUEUE (in Short-Term Scheduler

New Jobs (on Disk) CPU (Running)
(admit) RAM) (dispatch)

<-- timeout/preempt

Medium-Term (swap I/O WAIT QUEUE

<-- I/O complete I/O request --> wait
in) (blocked)

The queuing diagram shows how processes flow: New jobs → Long-term scheduler admits them to Ready
Queue → Short-term scheduler picks one for CPU → Process either completes, gets preempted (back to Ready
Queue), or waits for I/O (goes to Wait Queue). Medium-term scheduler swaps processes to/from disk to manage
memory.
Q20. Distributed System + Characteristics

Definition:
A Distributed System is a collection of independent computers that appear to users as a single coherent
system. The computers communicate and coordinate via a network to achieve a common goal.
Examples: Google Search, Amazon AWS, ATM Network, World Wide Web

Characteristics of Distributed Systems:

Characteristic Description Example

1. Resource Sharing All nodes share hardware (printers, disks) and software
Cloud storage
(files, databases).
— multiple users share same disk

2. Openness System can be extended — add new hardware, software,

Adding a services
new server
easily.
to a web farm

3. Concurrency Multiple processes run simultaneously on different1000

machines.
users accessing Google simultaneously

4. Scalability System can grow easily by adding more nodes without

Amazon redesign.
adding more servers during sale

5. Fault Tolerance If one node fails, others continue. System remains

Netflix
operational.
works even if one data center goes down

6. Transparency Users don't know which machine their task runs on

You
—don't
appears
know
single.
which Google server answers your sear

7. Heterogeneity Different types of hardware, OS, networks can coexist.

Windows PCs + Linux servers + Android phones in one

8. Security Distributed systems face more security challenges

SSL/TLS,
— encryption
authentication
needed. tokens
Q21, Q22. 5-State Process Transition Diagram

The Five States:

State Description When Process Enters This State

1. NEW Process is being created When user launches program or fork() is called

2. READY Process is ready, waiting for CPU After creation or after I/O completes

3. RUNNING Process is currently executing on CPUWhen scheduler dispatches it

4. BLOCKED/WAIT Process waiting for event or I/O When process requests I/O or waits for event

5. TERMINATED Process has finished execution When process calls exit() or is killed

State Transitions Explained:

Transition From → To Trigger/Reason

Admit NEW → READY OS accepts process into memory — added to ready queue

Dispatch READY → RUNNING CPU scheduler selects process to run

Interrupt/Timeout RUNNING → READY Time quantum expires or higher priority arrives

I/O or Event Wait RUNNING → BLOCKED Process requests I/O or waits for resource

I/O Complete BLOCKED → READY I/O finishes or event occurs — back to ready

Exit RUNNING → TERMINATED Process completes or calls exit() or is killed

Complete 5-State Diagram:

→ dispatch → ←
NEW → admit → READY RUNNING
timeout ←

↓ I/O wait

← I/O complete BLOCKED

↓ exit

TERMINATED
Q23. Disk Arm Scheduling Algorithms

What is Disk Scheduling?

When multiple processes request disk I/O simultaneously, the OS must decide the order in which disk
requests are served. The goal is to minimize disk arm movement (seek time) and maximize disk throughput.
Key Terms: Seek Time = time to move disk arm to correct track. Rotational Latency = time for correct sector to
come under head. Transfer Time = time to read/write data.

Example Setup:
Disk request queue: 98, 183, 37, 122, 14, 124, 65, 67. Initial head position: 53. Disk has tracks 0–199.

1. FCFS — First Come First Serve:

Serve requests in the order they arrive.
Head starts at 53.
Order: 53→98→183→37→122→14→124→65→67

Movements:
53→98 = 45
98→183 = 85
183→37 = 146
37→122 = 85
122→14 = 108
14→124 = 110
124→65 = 59
65→67 = 2

Total Head Movement = 45+85+146+85+108+110+59+2 = 640 tracks

2. SSTF — Shortest Seek Time First:

Always serve the request CLOSEST to current head position.
Head at 53. Queue: 98,183,37,122,14,124,65,67

Step 1: At 53, closest = 65 → move to 65 (12)

Step 2: At 65, closest = 67 → move to 67 (2)
Step 3: At 67, closest = 37 → move to 37 (30) [wait: 37,14,98,122,124,183]
Step 4: At 37, closest = 14 → move to 14 (23)
Step 5: At 14, closest = 98 → move to 98 (84)
Step 6: At 98, closest = 122 → move to 122 (24)
Step 7: At 122,closest = 124 → move to 124 (2)
Step 8: At 124,closest = 183 → move to 183 (59)

Total = 12+2+30+23+84+24+2+59 = 236 tracks (Much better!)

3. SCAN (Elevator Algorithm):

Head moves in one direction, serves all requests, then reverses.
Head at 53, moving TOWARD higher tracks (ascending).
Queue: 14,37,65,67,98,122,124,183 (sorted)

Go UP: 53→65→67→98→122→124→183→199(end)
Then reverse, go DOWN: 199→37→14

Movements:
53→65 = 12
65→67 = 2
67→98 = 31
98→122 = 24
122→124 = 2
124→183 = 59
 183→199 = 16 (goes to end)
199→37 = 162
37→14 = 23

Total = 12+2+31+24+2+59+16+162+23 = 331 tracks

4. C-SCAN (Circular SCAN):

Head moves in one direction only. When it reaches end, jumps back to start.
Head at 53, moving UP. Queue: 14,37,65,67,98,122,124,183

Go UP: 53→65→67→98→122→124→183→199(end)
Jump to 0 (no service), Go UP: 0→14→37

Movements:
53→199 = 146 (with stops at 65,67,98,122,124,183)
199→0 = 199 (jump, no service)
0→14 = 14
14→37 = 23

Total meaningful movement = 146+199+14+23 = 382 tracks

(C-SCAN provides more uniform wait time than SCAN)

5. LOOK Algorithm:
Like SCAN but head only goes as far as last request — doesn't go to disk end.
Head at 53, moving UP. Requests: 14,37,65,67,98,122,124,183

Go UP to highest (183): 53→65→67→98→122→124→183

Reverse, go DOWN to lowest (14): 183→37→14

Movements:
53→183 = 130 (with stops)
183→14 = 169 (with stops at 37)

Total = 130+169 = 299 tracks (Better than SCAN — no unnecessary movement)

Comparison of Disk Scheduling Algorithms:

Algorithm Total Movement Advantage Disadvantage

FCFS 640 tracks Simple, fair Very high seek time

SSTF 236 tracks Low seek time Starvation of far requests

SCAN 331 tracks No starvation Longer wait for far ends

C-SCAN 382 tracks Uniform wait time Jump to 0 wastes time

LOOK 299 tracks No unnecessary movement Slightly complex

Best Algorithm: SSTF gives minimum total movement. LOOK is best for balanced performance. C-SCAN is best
for uniform response time. FCFS is only used when simplicity is priority.
Master Summary — All Q2 Topics

Topic Key Point Remember

Process Program in execution with own memory Has PCB, states, resources

Thread Lightweight — shares process memory User-level vs Kernel-level

Process vs Program Program=passive/disk, Process=active/RAM Recipe vs Cooking

PCB ID card of process in OS PID, State, PC, Registers, Memory

5 Process States New→Ready→Running→Blocked→Terminated

State transitions with triggers

FCFS First arrived = first served Simple but convoy effect

SJF Shortest burst time first Best avg WT, may starve long jobs

Round Robin Fixed quantum, rotate Fair, good for interactive systems

Priority Highest priority runs first Can starve low-priority processes

Multiprogramming Multiple programs in memory Maximize CPU use

Multitasking Multiple tasks share CPU Fast response to users

Multiprocessing Multiple CPUs True parallelism

Distributed OS Multiple computers as one Fault tolerant, scalable

RTOS Meets strict time deadlines Hard vs Soft RTOS

Schedulers Long/Short/Medium term Job/CPU/Swapper scheduler

Disk FCFS Serve in arrival order Simple, worst performance

Disk SSTF Nearest first Best seek, risk of starvation

Disk SCAN Elevator algorithm Good balance

Disk LOOK SCAN without full sweep Best practical performance

Exam Tips
✓ For scheduling sums: Always make a table with AT, BT, CT, TAT, WT columns.
✓ TAT = Completion Time - Arrival Time
✓ Waiting Time = Turnaround Time - Burst Time
✓ For Gantt charts: Draw them clearly with time markers below.
✓ Process states: Always draw the 5-state diagram with arrows and labels.
✓ PCB: Draw the block diagram — each field in a separate colored box.
✓ Thread question: Always compare ULT vs KLT in a table format.
✓ Disk scheduling: Calculate total head movement step by step with each move.
✓ For Process vs Thread: Use a comparison table — gets full marks.
✓ Priority scheduling: Remember lower number = higher priority (usually).

— End of OS Unit 2 Complete Exam Guide —