Operating Systems

Process Concept & Process Scheduling

Complete Exam-Ready Notes

Covers All 35 Questions | Diagrams | Tables | Formulas

 PART 1: PROCESS CONCEPT

Q1. What is a Process?

A process is a program in execution — an active entity that requires resources (CPU, memory, I/O) to
complete its task. Unlike a program (passive), a process is dynamic and changes state over time.

A process consists of:

• Text section – the program code
• Program Counter (PC) – address of the next instruction
• Stack – temporary data (function parameters, return addresses, local variables)
• Heap – dynamically allocated memory at runtime
• Data section – global variables

Q2. What is a Program?

A program is a passive entity — a file stored on disk containing a list of instructions. It has no execution
activity. When a program is loaded into memory and executed, it becomes a process. Two processes may
be associated with the same program (e.g., two users running the same editor).

Q3. Difference between Program and Process

Aspect Program Process

Nature Passive (static file on disk) Active (executing entity)

Existence Permanent on disk until deleted Temporary – exists only during execution

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

State Has no state Has states: New, Ready, Running, Waiting, Terminated

Instance One program → multiple processes Each process is one instance of a program

Example [Link] on disk Firefox window running in memory

Q4. What is a Process Control Block (PCB)? Explain each part.

The PCB (also called Task Control Block) is a data structure maintained by the OS for every process. It
acts as the identity card of a process and is used during context switching.

PCB Field Description

Process ID (PID) Unique integer identifier for each process

Process State Current state: New / Ready / Running / Waiting / Terminated

Program Counter Address of the next instruction to execute

CPU Registers All register values saved when process is interrupted

Memory Management Info Base/limit registers, page tables, segment tables

I/O Status Info List of open files, I/O devices allocated

Accounting Info CPU time used, time limits, process priority

Parent Process ID PID of the process that created this process

Priority Used by scheduler to determine execution order

Q5. Draw and Explain the Diagram of Process States
A process passes through the following 5 states during its lifetime:

State Description Transition

New Process is being created; resources allocated → Ready (admitted)

Ready Process loaded in memory, waiting for CPU → Running (scheduler dispatch)

Running CPU is executing the process instructions → Waiting / Ready / Terminated

Waiting (Blocked) Process waiting for I/O or event to complete → Ready (I/O complete)

Terminated Process finished; OS releases resources Final state

State Transition Diagram (text representation):

New ■■(admit)■■■ Ready ■■■(I/O done)■■ Waiting ■ ▲ ▲ dispatch■ ■interrupt ■I/O
wait ▼ ■ ■ Running ■■■■■■■■■■■■■ ■ (exit)▼ Terminated

Q7. Why is Process Scheduling Used?

Process scheduling is used in multiprogramming to maximize CPU utilization. When one process waits for
I/O, the CPU is switched to another process. Scheduling ensures:
• CPU is never idle — always executing some process
• Fair allocation of CPU time among all processes
• Higher throughput — more processes completed per unit time
• Reduced waiting and turnaround times for users

Q8. Discuss the Ready Queue

The ready queue is a set of all processes residing in main memory, ready and waiting to execute on the
CPU. It is typically a linked list of PCBs. The short-term scheduler selects a process from the ready queue
and allocates the CPU to it.

Q9. Discuss the Device Queue

Each I/O device has its own device queue containing processes that have issued I/O requests to that
device and are waiting for it to complete. Once the I/O is done, the process moves from the device queue
back to the ready queue.

Q10. Why is a Scheduler Used?

A scheduler selects processes from queues and allocates system resources (CPU, memory). Without a
scheduler, processes would compete chaotically. The scheduler ensures orderly, efficient execution.

Q11. Long-Term, Short-Term and Medium-Term Schedulers

Scheduler Also Called Function Frequency

Long-Term Job Scheduler Selects jobs from job pool (disk) and loads Infrequent
into main memory
(seconds/minutes)
(ready queue). Control

Short-Term CPU Scheduler Selects process from ready queue and allocates
Very frequent
CPU. Dispatcher
(ms) carries out the sw

Medium-Term Swapper Removes processes from memory (swap out)

Moderate
to reduce degree of multiprogramming

Q12. What is Context Switching?

 Context switching is the mechanism by which the CPU switches from executing one process to another.
The OS saves the state of the current process in its PCB and loads the saved state of the new process.

Steps in Context Switch:

• 1. Interrupt/timer fires → OS takes control
• 2. Save current process state (PC, registers, etc.) into its PCB
• 3. Short-term scheduler selects the next process
• 4. Load next process state from its PCB
• 5. CPU resumes execution of new process
■ Context switching is pure overhead — no useful work is done during the switch. Frequent switching degrades
performance.

Q13. What is a Dispatcher? Why is it Used?

The dispatcher is the module that gives control of the CPU to the process selected by the short-term
scheduler. It performs:
• Context switching – saving and loading process states
• Switching to user mode – after kernel mode operations
• Jumping to the correct location in the user program to resume
■ Dispatcher Latency = time taken to stop one process and start another. Lower latency = better performance.

Q14. What is a Parent Process?

A parent process is any process that creates one or more child processes using system calls like fork()
(UNIX) or CreateProcess() (Windows). The first process in UNIX is init (PID=1), which is the parent of all
processes.

Q15. What is a Child Process?

A child process is a new process created by a parent process. The child inherits attributes from the parent
(open files, environment variables). After fork(), the child is an almost exact copy of the parent. The child
can either execute the same program as the parent or load a new program using exec().

Q16. Explain fork() System Call for Process Creation (with Program)
fork() creates a new process by duplicating the calling process. After fork():
• Return value = 0 in the child process
• Return value = child's PID in the parent process
• Return value = -1 if fork() fails
#include <stdio.h> #include <unistd.h> int main() { pid_t pid = fork(); if (pid == 0)
{ printf("Child: PID=%d\n", getpid()); } else if (pid > 0) { printf("Parent: Child
PID=%d\n", pid); wait(NULL); // wait for child to finish } else { printf("Fork
failed!\n"); } return 0; }

Q17. When a Process Creates a New Process — Possibilities in Terms of Execution

After fork(), two execution possibilities exist:
• 1. Parent and child execute CONCURRENTLY — both run at the same time (typical in multitasking).
• 2. Parent WAITS until child terminates — parent calls wait() and blocks until child finishes.
Two possibilities for address space:
• Child is a DUPLICATE of parent — has same program and data (default in fork()).
• Child has a NEW PROGRAM loaded — child calls exec() to replace its memory with a new program.
Q18. When is a Process Terminated and Under What Conditions?
A process terminates when it finishes executing its last statement and calls exit(). The OS deallocates all
resources.

Normal Termination:
• Process calls exit() after completing its task
• Main function returns (implicit exit())

Abnormal / Forced Termination (by Parent or OS):

• Child exceeds allocated resources
• Task assigned to child is no longer required
• Parent is terminating and OS doesn't allow orphans (cascading termination)
• SIGKILL / SIGTERM signals sent to the process

Q19. What is Cascading Termination?

When a parent process terminates, all its children (and their descendants) are also terminated
automatically by the OS. This is called cascading termination. UNIX/Linux implements this — when init
terminates, all processes terminate.

Q20. Define Zombie Process

A zombie process is a process that has completed execution (called exit()) but still has an entry in the
process table because its parent has not yet called wait() to read its exit status. It holds no resources but
occupies a PCB slot.
■ A zombie cannot be killed — it disappears only when the parent reads its exit status via wait().

Q21. Define Orphan Process

An orphan process is a child process whose parent has terminated before the child did. In UNIX/Linux,
orphan processes are adopted by the init process (PID=1), which periodically calls wait() to clean them up.

Q22. What is Inter-Process Communication (IPC)? What are its Advantages?

IPC is a mechanism that allows processes to communicate and synchronize their actions. Processes may
be independent (no data sharing) or cooperating (sharing data).

Advantages of IPC:
• Information sharing — multiple processes access shared data
• Computation speedup — tasks divided into parallel subtasks
• Modularity — system divided into cooperating modules
• Convenience — users work on multiple tasks simultaneously

Q24. Discuss IPC Communication Methods

1. Shared Memory:
A region of memory is shared between cooperating processes. Processes read/write to this region directly.
Very fast (no kernel involvement after setup). Used in Producer-Consumer problem.

2. Message Passing:
Processes communicate by sending and receiving messages via the OS kernel. No shared memory
needed. Easier to implement in distributed systems.

Property Direct Communication Indirect Communication

Setup Link established automatically between sender-receiver

Messages sent to/from mailboxes (ports)
 Naming Must explicitly name the other process Use mailbox ID, not process name

Example send(P, msg), receive(Q, msg) send(mailbox_A, msg), receive(mailbox_A, msg)

Flexibility Less flexible (hard-coded links) More flexible (many processes share one mailbox)

Symmetry vs Asymmetry:
• Symmetric: Both sender and receiver name each other explicitly.
• Asymmetric: Only sender names the receiver; receiver can receive from any process.

Q25. Independent vs Co-operating Process

Aspect Independent Process Co-operating Process

Data Sharing No shared data Shares data with other processes

Effect of others Unaffected by other processes Can affect and be affected by others

IPC needed? No Yes (shared memory / message passing)

Example Calculator app Producer-Consumer, web server threads

Q26. Difference b/w Shared Memory and Message Passing

Aspect Shared Memory Message Passing

Speed Faster (no kernel after setup) Slower (kernel involvement)

Data size Suitable for large data Better for small messages

Synchronization Must be handled by programmer OS provides synchronization

Setup Harder (need explicit memory segment) Easier (send/receive calls)

Distribution Works on single machine best Works well in distributed systems

Q27. What is Synchronization? Discuss its Types.

Process synchronization ensures that cooperating processes coordinate their execution to maintain data
consistency and avoid race conditions.

Types:
• Mutex (Mutual Exclusion): Only one process in critical section at a time. Implemented via mutex locks,
semaphores.
• Semaphore: Integer variable with only wait() and signal() operations. Binary semaphore (0/1) = mutex.
Counting semaphore = multiple instances.
• Monitor: High-level synchronization construct with condition variables (wait/signal). Mutual exclusion is
built in.
• Condition Variables: Used with monitors. A process can wait on a condition and be signaled when it
becomes true.

Q28. Why is Buffering Used? Discuss Different Types of Buffers.

Buffering is used to hold data temporarily while it is being transferred between two processes or between a
process and a device. It resolves speed mismatches between producer and consumer.

Buffer Type Description

Zero-capacity (No buffer) No messages queued. Sender must wait until receiver is ready (rendezvous).

Bounded capacity Finite queue of n messages. Sender waits only if queue is full.
 Unbounded capacity Unlimited queue. Sender never waits. Receiver waits if queue is empty.

Q29. What is a Thread?

A thread is the smallest unit of CPU execution within a process. Also called a lightweight process. A single
process can have multiple threads that share the process's memory and resources but each thread has its
own PC, registers, and stack.

Q30. Difference b/w Process and Thread

Aspect Process Thread

Definition Program in execution Unit of execution within a process

Memory Own separate address space Shares address space with other threads

Creation overhead High (separate memory, PCB) Low (shares process resources)

Communication IPC required (slow) Direct memory sharing (fast)

Context switch Expensive Cheap

Crash effect Crash = only that process affected Crash = entire process may crash

Q31. Difference b/w Multiprogramming and Multitasking

Aspect Multiprogramming Multitasking

Focus Keep CPU busy by loading multiple jobs in Allow

memorymultiple tasks to run for a single user

User interaction Minimal (batch style) High (interactive)

CPU switching When current job does I/O Based on time-sharing (time slices)

Example Old batch systems Modern OS (Windows, Linux)

Q32. Discuss User-Level Thread (ULT) and Kernel-Level Thread (KLT)

Aspect User-Level Thread (ULT) Kernel-Level Thread (KLT)

Managed by Thread library in user space OS Kernel

Kernel awareness Kernel unaware of threads Kernel knows and manages threads

Context switch Fast (no mode switch needed) Slow (requires kernel mode switch)

Parallelism No true parallelism (kernel sees 1 process)True parallelism on multi-core

Blocking If one thread blocks, all block Only the blocking thread blocks

Example POSIX Pthreads (user-mode), Java green threads

Windows threads, Linux pthreads (NPTL)
 Q33-35: Multithreading, Pthreads, RPC, Pipes, Sockets

Q33. What is Multithreading? Discuss its Models.

Multithreading is the ability of an OS to support multiple threads within a single process. Benefits:
responsiveness, resource sharing, economy, scalability.

Model Description Pros Cons

Many-to-One Many ULTs → 1 KLT Fast thread management Blocking blocks all; no parallelism

One-to-One Each ULT → 1 KLT True parallelism; blocking OK Creating thread = OS thread (expensive)

Many-to-Many Many ULTs → Many KLTs (≤ ULT count)

Flexible; true parallelism Complex to implement

Two-level (Hybrid) Many-to-many + some one-to-one Most flexible Most complex

Q34. What are Pthreads and Java Threads?

Pthreads (POSIX Threads):
• POSIX standard API for thread creation and synchronization in C/C++.
• Functions: pthread_create(), pthread_join(), pthread_exit(), pthread_mutex_lock()
• Supported on UNIX/Linux systems.

Java Threads:
• Java supports threads natively via the Thread class or Runnable interface.
• JVM maps Java threads to OS threads (typically one-to-one on modern JVMs).
• Methods: start(), run(), sleep(), join(), synchronized keyword for mutual exclusion.

Q35. What is RPC, PIPE, and Socket?

RPC (Remote Procedure Call):
• Allows a process to call a procedure on a remote machine as if it were local.
• OS hides network details using stubs. Client stub packages parameters (marshalling); server stub
unpacks them.

PIPE:
• A conduit allowing two processes to communicate. Created by pipe() system call.
• Ordinary pipes: unidirectional, parent-child only. Named pipes (FIFOs): bidirectional, any processes.
• Data written to write-end is read from read-end in FIFO order.

Socket:
• An endpoint for communication across a network. Identified by IP address + Port number.
• Types: TCP socket (connection-oriented, reliable) and UDP socket (connectionless, fast).
• Socket API: socket(), bind(), listen(), accept(), connect(), send(), recv()
 PART 2: PROCESS SCHEDULING

Q1. Preemptive vs Non-Preemptive Scheduling

Aspect Preemptive Non-Preemptive

CPU release CPU can be taken away mid-execution CPU released only when process finishes or blocks

Interrupts Timer/priority interrupts allowed No interrupts during execution

Response time Better (high-priority runs sooner) Worse (must wait for current process)

Overhead Higher (frequent context switches) Lower

Examples SRTF, Round Robin, Priority (preemptive) FCFS, SJF, Priority (non-preemptive)

Starvation Possible for low-priority Possible for long jobs (FCFS)

Q2. Scheduling Criteria

Criterion Goal Formula

CPU Utilization Keep CPU as busy as possible (aim 40–90%) CPU busy time / total time × 100%

Throughput Maximize processes completed per unit time # processes / time unit

Turnaround Time (TAT) Minimize time from submission to completion TAT = Completion Time − Arrival Time

Waiting Time (WT) Minimize time spent in ready queue WT = TAT − Burst Time

Response Time Time from submission to first response First CPU start − Arrival Time

Q3. Short Note on FCFS, SJF, RR, Priority — Advantage & Disadvantage
1. FCFS – First Come First Served
Processes are served in order of arrival. Simple queue (FIFO). Non-preemptive.
• ■ Advantage: Simple to implement, no starvation
• ■ Disadvantage: Convoy effect — short jobs wait behind long ones. High avg waiting time.

2. SJF – Shortest Job First

Process with smallest burst time runs first. Non-preemptive. Preemptive version = SRTF.
• ■ Advantage: Minimum average waiting time — provably optimal
• ■ Disadvantage: Cannot know future burst time; starvation of long processes (Aging fixes this)

3. Round Robin (RR)

Each process gets a fixed time quantum (q). After q expires, process goes back to end of ready queue.
Preemptive. Best for time-sharing systems.
• ■ Advantage: Fair, no starvation, good response time for interactive systems
• ■ Disadvantage: Higher avg TAT if q is small; lots of context switching overhead
■ Rule: If q is very large → RR becomes FCFS. If q is very small → too much overhead.
4. Priority Scheduling
Each process assigned a priority; highest priority runs first. Can be preemptive or non-preemptive.
• ■ Advantage: Important processes get CPU immediately
• ■ Disadvantage: Starvation — low-priority processes may never run
■ Solution to starvation: Aging — gradually increase priority of waiting processes over time.
Q4. Multilevel Queue Scheduling
The ready queue is divided into multiple separate queues based on process type (e.g., system, interactive,
batch). Each queue has its own scheduling algorithm and fixed priority over lower queues.
• Foreground queue (interactive): Round Robin
• Background queue (batch): FCFS
• Processes cannot move between queues once assigned.
■ Problem: Low-priority queues may starve if higher queues are always busy.

Q5. Multilevel Feedback Queue Scheduling

Similar to multilevel queue but processes CAN MOVE between queues based on their behavior. If a
process uses too much CPU → moved to lower-priority queue. If it waits too long → promoted to
higher-priority queue (aging).
• Most flexible and complex scheduling algorithm
• Parameterized by: number of queues, algorithm per queue, upgrade/demote criteria, initial queue
assignment
■ Most modern OS (Linux, Windows) use variants of multilevel feedback queues.

Q8. What is Aging?

Aging is a technique to prevent starvation in priority scheduling. The idea is to gradually increase the
priority of a process that has been waiting in the ready queue for a long time. Eventually, the process's
priority becomes high enough that it gets the CPU. This ensures every process eventually runs, even
low-priority ones.
 PART 3: SCHEDULING NUMERICALS

Given Data from Question Paper:

Process Burst Time (BT) Arrival Time (AT)

P1 7 2

P2 4 1

P3 3 3

P4 5 6

(a) FCFS — First Come First Served (Non-Preemptive)

Sort by Arrival Time: P2(AT=1) → P1(AT=2) → P3(AT=3) → P4(AT=6)

Process AT BT Start Time Finish Time TAT = FT-AT WT = TAT-BT

P2 1 4 1 5 4 0

P1 2 7 5 12 10 3

P3 3 3 12 15 12 9

P4 6 5 15 20 14 9

Avg Waiting Time (FCFS) = (0+3+9+9)/4 = 21/4 = 5.25 ms

Avg TAT (FCFS) = (4+10+12+14)/4 = 40/4 = 10 ms

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

At each decision point, pick the process with smallest BT among arrived processes.
t=1: P2 arrives (BT=4) → runs. t=5: P1(7),P3(3) arrived → pick P3(BT=3). t=8: P1(7),P4 not yet → P1.
t=15: P4 runs.

Process AT BT Start Finish TAT WT

P2 1 4 1 5 4 0

P3 3 3 5 8 5 2

P1 2 7 8 15 13 6

P4 6 5 15 20 14 9

Avg Waiting Time (SJF) = (0+2+6+9)/4 = 17/4 = 4.25 ms

Avg TAT (SJF) = (4+5+13+14)/4 = 36/4 = 9 ms

(c) SRTF — Shortest Remaining Time First (Preemptive SJF)

At each new arrival, compare remaining time of running process vs new process. Run the shorter one.
t=1: P2 arrives, runs (RT=4). t=2: P1 arrives(RT=7) > P2(RT=3) → P2 continues. t=3: P3
arrives(RT=3)=P2(RT=2) → P2 continues (tie: running). t=5: P2 done. P1(7),P3(3) ready → P3 runs. t=6:
P4 arrives(5) > P3(2) → P3 continues. t=8: P3 done. P1(7),P4(5) → P4 runs. t=13: P4 done → P1 runs.
t=20: P1 done.

Process AT BT Finish TAT = FT-AT WT = TAT-BT

P1 2 7 20 18 11

P2 1 4 5 4 0
P3 3 3 8 5 2

P4 6 5 13 7 2

Avg Waiting Time (SRTF) = (11+0+2+2)/4 = 15/4 = 3.75 ms

Avg TAT (SRTF) = (18+4+5+7)/4 = 34/4 = 8.5 ms

(c) Round Robin — Time Quantum = 2 ms

Processes enter queue in order of arrival. Each gets 2ms CPU time, then rotated.
Execution order: P2(1-3)→P1(3-5)→P3(5-7)→P2(7-8,done)→P1(8-10)→P4(10-12)→P1(12-14)→P4(14-1
6)→P1(16-18)→P4(18-19,done)→P1(19-20,done)

Process AT BT Finish Time TAT = FT-AT WT = TAT-BT

P1 2 7 20 18 11

P2 1 4 8 7 3

P3 3 3 7 4 1

P4 6 5 19 13 8

Avg Waiting Time (RR, q=2) = (11+3+1+8)/4 = 23/4 = 5.75 ms

Avg TAT (RR, q=2) = (18+7+4+13)/4 = 42/4 = 10.5 ms

COMPARISON SUMMARY
Algorithm Avg WT (ms) Avg TAT (ms) Type

FCFS 5.25 10 Non-preemptive

SJF 4.25 9 Non-preemptive

SRTF 3.75 ■ Best 8.5 ■ Best Preemptive

RR (q=2ms) 5.75 10.5 Preemptive

■ SRTF gives the best (lowest) avg waiting time and TAT among all algorithms shown.

QUICK FORMULA REFERENCE

Formula Definition

TAT = Completion Time − Arrival Time Total time from submission to completion

Waiting Time = TAT − Burst Time Time spent waiting in ready queue

Response Time = First CPU Start − Arrival Time Time until first CPU response

Avg WT = Σ(WT) / n Sum of all WTs divided by number of processes

Avg TAT = Σ(TAT) / n Sum of all TATs divided by number of processes

CPU Utilization = Busy Time / Total Time × 100 Percentage CPU is busy

Throughput = # Processes / Time Unit Number of processes completed per time unit