PadhaikoAll subjects

Process description, states and control · Scheduling algorithms

Operating System (ENCT 254)

Open in the Padhaiko app

2.1 Process description, states and control

A process is fundamentally defined as a program in execution. While a program is a passive entity—a compiled binary executable file residing statically on secondary storage (disk)—a process is an active entity occupying main memory, possessing an execution context that includes the Program Counter (PC), CPU registers, stack pointer, and allocated system resources.

Definition

Process

A Process is the basic unit of work in modern time-sharing operating systems, comprising program machine instructions, current processor activity, dedicated memory segments, and associated operating system control records.

Memory Anatomy of an Active Process

When an executable is loaded from disk into physical memory, the operating system structures its virtual address space into four distinct memory segments:

Virtual Address Space Layout of a ProcessText
 +---------------------------------------------------+ High Memory (0xFFFFFFFF)
 | Stack (Local variables, function frames, returns) |
 |                    |                              |
 |                    v (Grows downward)             |
 |                                                   |
 |                    ^ (Grows upward)               |
 |                    |                              |
 | Heap (Dynamically allocated via malloc/new)       |
 +---------------------------------------------------+
 | Uninitialized Data Segment (BSS: zero-filled)     |
 +---------------------------------------------------+
 | Initialized Data Segment (Global & static vars)   |
 +---------------------------------------------------+
 | Text Segment (Read-only machine instructions)     |
 +---------------------------------------------------+ Low Memory (0x00000000)
Memory Segment Roles
SegmentMutabilityGrowth DirectionTypical Contents & Purpose
Text SegmentRead-OnlyFixed sizeContains the compiled machine code instructions executed by the CPU. Marked read-only so multiple instances of the same program can safely share code pages.
Data SegmentRead/WriteFixed sizeContains global and static variables. Split into Initialized Data (variables assigned values in source code) and BSS (uninitialized data initialized to zero by the loader).
Heap SegmentRead/WriteGrows upwardMemory dynamically managed at runtime by programmers via allocation calls (malloc(), calloc(), or new in C/C++). Managed by memory allocators until freed via free().
Stack SegmentRead/WriteGrows downwardContains temporary execution frames: function parameters, local variables, return addresses, and saved registers. Allocates on function invocation and pops upon function return.

Process States and Lifecycle Transitions

As a process executes, its execution condition changes across distinct operational states.

The 5-State Process Model

In standard memory-resident systems, a process moves through five primary states:

5-State Process Lifecycle DiagramText
      +------------+   Admit    +------------+
      |    New     | ---------> |   Ready    | <---------+
      +------------+            +------------+           |
                                    |     ^              |
                           Dispatch |     | Interrupt /  |
                                    |     | Time slice   |
                                    v     |              |
                                +------------+           |
                                |  Running   |           |
                                +------------+           |
                                    |                    |
                         I/O or     |     I/O or         |
                         Event wait |     Event complete |
                                    v                    |
                                +------------+           |
                                |  Blocked   | ----------+
                                |  (Waiting) |
                                +------------+
                                    |
                           Exit     v
                                +------------+
                                | Terminated |
                                +------------+
5-State Definitions and Triggers
StateOperational ConditionEntry TriggerExit Trigger
NewThe process is in the process of being created, but has not yet been admitted to the pool of executable processes.User launches application / fork() executed.Long-term scheduler admits process into main memory.
ReadyThe process resides in main memory and is prepared to run, waiting for CPU allocation.Process admitted, I/O completion, or preempted from Running.Short-term scheduler (dispatcher) allocates the CPU.
RunningMachine instructions of the process are actively being executed on a CPU core.Dispatcher selects the process from Ready queue.Timer interrupt expires (to Ready), I/O wait occurs (to Blocked), or process exits.
Blocked (Waiting)The process cannot execute until an external event or I/O operation completes.System call for file read, network packet wait, or semaphore lock.External I/O device finishes operation; hardware interrupt moves process to Ready.
TerminatedThe process has finished execution and released its memory, awaiting parent status reaping.Normal termination via exit() or fatal error/kill signal.Parent process calls wait() to harvest exit status and delete the PCB.

The 7-State Process Model with Suspended States

When the degree of multiprogramming exceeds physical RAM capacity, the operating system swaps processes out to secondary storage (paging file/swap partition). This introduces two suspended states:

AspectReady-Suspended StateBlocked-Suspended State
LocationSwapped out to secondary storage (disk)Swapped out to secondary storage (disk)
ReadinessReady to run immediately once loaded back into physical RAMBlocked waiting for an I/O event; cannot run even if loaded into RAM
Transition TriggerSwapped out from Ready queue due to memory pressure, or transitioned from Blocked-Suspended upon I/O finishSwapped out from Blocked queue by medium-term scheduler to free physical frames

Process Control Block (PCB)

The Process Control Block (also termed the Task Control Block) is a central kernel data structure (struct task_struct in Linux) that encapsulates everything the operating system knows about an individual process.

Definition

Process Control Block (PCB)

A Process Control Block (PCB) is a dedicated kernel data structure maintained for every active process, containing execution state, registers, memory maps, scheduling parameters, and resource accounting metadata required to pause and resume the process transparently.

A standard PCB stores eight essential categories of information:

  1. Process Identification: Unique numeric Process ID (PID), Parent Process ID (PPID), and User ID (UID).
  2. Process State: Current condition (New, Ready, Running, Blocked, Suspended, or Zombie).
  3. Program Counter (PC): Hardware address of the next machine instruction to be fetched and executed when the process resumes.
  4. CPU Registers: Saved register contents (accumulator, data registers, index registers, stack pointer, and status flags).
  5. CPU Scheduling Information: Scheduling priority, nice value, virtual runtime (vruntime), and pointers to scheduling queues.
  6. Memory Management Information: Page table pointers, segment descriptors, and base/limit registers defining the process address space.
  7. Accounting Information: Cumulative CPU time utilized, time slice expiration limits, and account numbers.
  8. I/O Status Information: List of open file descriptors, allocated I/O channels, and pending device requests.

Context Switching

A context switch is the mechanism by which the CPU suspends execution of a currently running process, saves its state into its PCB, and loads the saved execution context of a newly scheduled process from its PCB.

Context Switch Execution TimelineText
Process P0                          Operating System Kernel                 Process P1
==========                          =======================                 ==========
Executing instructions ...
   |
   | Timer Interrupt / System Call
   v
[Interrupt occurs] ----------------> Save execution state
                                     into PCB_P0
                                     Update state (Running -> Ready)
                                           |
                                           | Run Scheduler Algorithm
                                           v
                                     Select PCB_P1
                                     Load register state
                                     and page table from PCB_P1
                                     Update state (Ready -> Running)
                                           |
[P0 remains idle in Ready queue]           v
                                     Restore PC & jump to code ---------> Executing instructions ...

Process Creation and Termination: fork(), exec(), wait(), and exit()

In POSIX operating systems, process lifecycles are governed by four fundamental system calls:

AspectZombie ProcessOrphan Process
StatusA process that has finished execution via exit(), but whose entry still remains in the process table.A process that continues running after its parent process has terminated without waiting for it.
Resource UsageHolds no code, data, or heap memory; consumes only a single slot in the kernel Process Table.Normal running process occupying active memory and CPU cycles.
ResolutionCleaned up ("reaped") when the parent invokes wait() to read its termination exit code.Automatically adopted by the root init or systemd process (PID 1), which periodically invokes wait() to reap it.
HazardAccumulating thousands of zombies exhausts available kernel PIDs, preventing new processes from spawning.Generally harmless; handled smoothly by the system init daemon.

CPU-Bound vs. I/O-Bound Processes

Operating systems categorize workloads into two execution profiles:


2.2 Scheduling algorithms

The CPU scheduler is the core operating system component that selects which process from the Ready queue will be assigned to an available CPU core.

CPU scheduling decisions are handled by three distinct tiers of schedulers:

  1. Long-Term Scheduler (Job Scheduler): Selects programs from disk spool pools and loads them into memory as ready processes. It directly regulates the degree of multiprogramming.
  2. Medium-Term Scheduler (Swapper): Removes processes temporarily from physical RAM to swap space on disk during intense memory contention, reducing the active multiprogramming level.
  3. Short-Term Scheduler (CPU Scheduler / Dispatcher): Executes hundreds of times per second, selecting an active memory-resident process from the Ready queue and dispatching it to the CPU.

Preemptive vs. Non-Preemptive Scheduling

AspectNon-Preemptive SchedulingPreemptive Scheduling
CPU RelinquishmentA process retains the CPU until it terminates or voluntarily blocks for an I/O operation.The OS can interrupt a running process and force it back into the Ready queue when a higher-priority task arrives or a time slice expires.
Hardware RequirementDoes not strictly require a hardware interval timer.Requires a hardware interval timer generating periodic hardware interrupts.
OverheadMinimal context switching overhead; simpler to implement.Higher overhead due to frequent state saving, queue shuffling, and cache invalidation.
ResponsivenessPoor interactive responsiveness; short interactive tasks can starve behind long CPU-bound jobs.High responsiveness; ideal for modern interactive time-sharing systems.
AlgorithmsFCFS, standard SJF, HRNN.SRTF, Round Robin, Priority Preemptive, Linux CFS.

CPU Scheduling Performance Criteria

Operating system architects optimize scheduling algorithms across five standard quantitative metrics:


2.2.1 First Come First Serve (FCFS)

First Come, First Serve (FCFS) is the simplest, non-preemptive scheduling policy. Processes are allocated the CPU strictly in the chronological order of their arrival in the Ready queue, managed via a standard FIFO queue.


2.2.2 Shortest Job First (SJF)

Shortest Job First (SJF) is a non-preemptive scheduling algorithm that assigns the CPU to the process possessing the smallest upcoming CPU burst time. When two processes have identical burst times, FCFS is used as a tie-breaker.

Theorem

Optimality of Shortest Job First

Shortest Job First (SJF) is provably optimal: for a fixed set of concurrent processes arriving simultaneously, SJF yields the absolute minimum average waiting time among all scheduling algorithms.

Proof

Moving a shorter process ahead of a longer process decreases the waiting time of the short process by more than it increases the waiting time of the long process, reducing the net cumulative sum of waiting times across all tasks.

Predicting Future CPU Bursts via Exponential Smoothing

In general-purpose operating systems, future CPU burst lengths cannot be known in advance. The OS estimates upcoming burst length from historical measurements using an exponential moving average:

where is the actual duration of the -th CPU burst, is the historical predicted burst, and is a smoothing weighting factor.


2.2.3 Shortest Remaining Time (SRT)

Shortest Remaining Time (SRT)—also known as Shortest Remaining Time First (SRTF)—is the preemptive variant of Shortest Job First.

Whenever a new process arrives in the Ready queue, the scheduler compares its required burst time against the remaining burst time of the currently executing process:

SRTF provides superior average waiting times compared to non-preemptive SJF for interactive workloads, but incurs higher context switching overhead.


2.2.4 Round Robin (RR)

Round Robin (RR) is designed specifically for time-sharing systems. It is an inherently preemptive algorithm where the Ready queue is structured as a circular FIFO queue.

The operating system defines a small unit of execution time called a time quantum (or time slice, typically ):

  1. The CPU scheduler dispatches the process at the head of the Ready queue.
  2. A hardware timer is set to interrupt when the quantum expires.
  3. If the process completes its burst or blocks for I/O before the timer expires, it releases the CPU voluntarily.
  4. If the process is still running when the quantum expires, the timer interrupt fires, the process is preempted, and it is placed at the tail of the Ready queue.
Impact of Time Quantum Length in Round RobinText
 If Quantum q is Extremely Large (q -> inf):
   Every process finishes its CPU burst within its single slice.
   ==> Round Robin degrades into First Come First Serve (FCFS).

 If Quantum q is Extremely Small (q -> 0):
   Processes switch every few microseconds.
   ==> Processor Sharing (each of N processes appears to run at 1/N speed),
       but massive context switch overhead destroys actual system throughput.

A practical rule of thumb in operating system design is that approximately of CPU bursts should be shorter than the time quantum .


2.2.5 Highest Response Ratio Next (HRNN)

Highest Response Ratio Next (HRNN) is a non-preemptive scheduling policy developed to eliminate the starvation vulnerability of Shortest Job First while retaining its high throughput advantages.

Whenever the CPU becomes free, the scheduler computes the Response Ratio () for every process currently waiting in the Ready queue:

where:


2.2.6 Completely Fair Scheduler (CFS) used in Linux

The Completely Fair Scheduler (CFS) is the default CPU scheduling algorithm for standard tasks in the Linux kernel (introduced in Linux 2.6.23 to replace the older scheduler).

Unlike traditional multi-level priority queue schedulers, CFS models an "ideal multi-tasking CPU" on real hardware: on a machine running processes, each process should theoretically receive an equal fraction of processing power simultaneously.

Virtual Runtime (vruntime)

To track fairness, CFS maintains a 64-bit integer called vruntime (virtual runtime) for each task:

Red-Black Tree Architecture

CFS organizes all runnable tasks inside a self-balancing Red-Black Tree (struct rb_node):

Linux CFS Red-Black Tree StructureText
                       [ vruntime = 45 ms ]
                              /      \
                             /        \
              [ vruntime = 20 ms ]   [ vruntime = 80 ms ]
                     /
                    /
        *Leftmost Node*
      [ vruntime = 8 ms ]  <-- Scheduler picks this task in O(1) time!

Worked Out Examples

Example 2.1

2.1

Consider the following set of four processes arriving in the Ready queue with specified Arrival Times (AT) and CPU Burst Times (BT) in milliseconds:

ProcessArrival Time (AT)Burst Time (BT)
  1. Draw the Gantt chart and compute the average Turnaround Time and Waiting Time under First Come First Serve (FCFS).
  2. Draw the Gantt chart and compute the average Turnaround Time and Waiting Time under non-preemptive Shortest Job First (SJF).

Evaluating FCFS scheduling: Under FCFS, processes run to completion in the order of arrival: .

Gantt Chart:

|   P1 (8)   |  P2 (4)  |     P3 (9)    |   P4 (5)   |
0            8          12              21           26

Calculating completion times (), turnaround times (), and waiting times ():

  • : , ,
  • : , ,
  • : , ,
  • : , ,

Averages:

Evaluating non-preemptive SJF scheduling:

  • At : Only has arrived; runs from to .
  • At : (), (), and () have all arrived. Shortest is . runs from to .
  • At : Remaining ready processes are () and (). Shortest is . runs from to .
  • At : runs from to .

Gantt Chart:

|   P1 (8)   |  P2 (4)  |   P4 (5)   |     P3 (9)    |
0            8          12           17              26

Calculating metrics:

  • : , ,
  • : , ,
  • : , ,
  • : , ,

Averages:

Answer:
  1. FCFS: Average Waiting Time = , Average Turnaround Time = .
  2. SJF (non-preemptive): Average Waiting Time = , Average Turnaround Time = .
Example 2.2

2.2

Compute the execution schedule, completion times, and average waiting time under Shortest Remaining Time First (SRTF) for the following workload:

ProcessArrival Time (AT)Burst Time (BT)

Tracking preemption decisions chronologically:

  • : arrives () and begins running.
  • : arrives (). has executed , with remaining burst . Because remaining time () is strictly less than remaining time (), preempts .
  • : arrives (). has executed , with remaining burst . Because remaining time () is strictly less than remaining time (), preempts .
  • : runs to completion at ().
  • : arrives (). Ready queue contains: (remaining ), (remaining ), and (remaining ). Shortest remaining job is (). resumes and runs from ().
  • : Ready queue contains (remaining ) and (remaining ). Shortest is . runs from ().
  • : Only remains (). runs from ().

Constructing Gantt Chart and metrics:

|  P1 (2) |  P2 (2) | P3 (1) |  P2 (2) |   P4 (4)   |     P1 (5)     |
0         2         4        5         7            11               16

Metrics table:

  • : , ,
  • : , ,
  • : , ,
  • : , ,

Averages:

Answer:

Under SRTF:

  • Completion Times: , , , .
  • Average Turnaround Time = .
  • Average Waiting Time = .
Example 2.3

2.3

Compute the execution order, individual turnaround times, and average waiting time under Round Robin (RR) scheduling with time quantum for the following processes:

ProcessArrival Time (AT)Burst Time (BT)

Tracing Ready queue dynamics with :

  • : arrives; runs (remaining ). During this slice, (at ), (at ), and (at ) arrive. Queue: .
  • : runs (remaining ). Queue: .
  • : runs (remaining ). Queue: .
  • : runs (remaining ). Queue: .
  • : runs (remaining ). Queue: .
  • : runs (remaining ). terminates at (). Queue: .
  • : runs (remaining ). Queue: .
  • : runs (remaining ). terminates at (). Queue: .
  • : runs (remaining ). terminates at (). Queue: .
  • : runs (remaining ). terminates at ().

Gantt chart and quantitative calculation:

| P1(3)| P2(3)| P3(3)| P4(3)| P1(3)| P2(1)| P3(3)| P4(2)| P1(2)| P3(3)|
0      3      6      9      12     15     16     19     21     23     26

Individual metrics:

  • : , ,
  • : , ,
  • : , ,
  • : , ,

Averages:

Answer:

Under Round Robin ():

  • Completion Times: , , , .
  • Average Turnaround Time = .
  • Average Waiting Time = .

Exercises

Process Management and Scheduling Review

Question 1

Illustrate the memory layout of an active process in main memory and describe the function of each segment. List five critical fields stored within a Process Control Block (PCB). [2078, 2075]

Four primary memory segments:

  1. Text Segment (Code): Contains the executable machine code instructions. Marked read-only and shareable across processes executing the same binary.
  2. Data Segment: Holds static and global variables, divided into Initialized Data (assigned explicit values at compile time) and BSS (Uninitialized Data, zero-filled at program startup).
  3. Heap Segment: Dynamically allocated memory requested during runtime via malloc() / new. Grows dynamically upward toward higher memory addresses.
  4. Stack Segment: Allocates activation records for function calls, including return addresses, arguments, and local automatic variables. Grows downward toward lower memory addresses.

Five critical PCB fields:

  1. Process ID (PID): A unique numerical identifier assigned to the process by the kernel.
  2. Process State: The current execution status (Ready, Running, Blocked, etc.).
  3. Program Counter (PC): The address of the next machine instruction to execute.
  4. CPU Registers: Saved register contents (stack pointer, accumulator, general registers) preserved when the process is preempted.
  5. Memory Management Information: Pointers to page tables, segment descriptors, and base/limit registers defining its address space.
Answer:

An active process is organized into Text (code), Data (globals), Heap (dynamic allocations), and Stack (function call frames). The PCB stores process execution context including PID, Process State, Program Counter, CPU Registers, and Memory Management Information.

Question 2

Explain the 7-state process lifecycle model. Why are the Ready-Suspended and Blocked-Suspended states necessary in modern virtual memory operating systems? [2074, 2072]

The 7-State process lifecycle: The standard 5-state model (New, Ready, Running, Blocked, Terminated) assumes all active processes fit completely inside physical main memory. In modern systems, heavy workloads cause main memory overcommitment, prompting the medium-term scheduler to swap process images to disk. This introduces two suspended states:

  1. Ready-Suspended: The process is ready to run as soon as physical RAM becomes available, but its address space is currently swapped out to disk.
  2. Blocked-Suspended: The process is waiting for an I/O event and its address space is simultaneously swapped out to disk.

Why suspended states are necessary:

  • Preventing Memory Starvation: If all resident processes become blocked waiting for I/O, the CPU would sit completely idle while physical RAM remains occupied by blocked tasks. Swapping blocked processes to disk frees up physical page frames so the long-term scheduler can admit ready processes into RAM.
  • System Stability: Swapping out lowest-priority tasks alleviates memory pressure, preventing catastrophic out-of-memory kernel panics.
Answer:

The 7-state model introduces Ready-Suspended and Blocked-Suspended states on secondary storage. They are necessary to free up precious physical RAM when resident processes are blocked, allowing the operating system to load executable ready processes and maintain high CPU productivity without thrashing.

Question 3

A system has a hardware context switch latency of .

  1. Calculate the percentage of CPU time consumed by context switching overhead when the CPU time quantum is set to .
  2. Calculate the context switching overhead percentage when the CPU time quantum is increased to ().
  3. Discuss the trade-off in system behavior between these two choices of time quantum.

Evaluating overhead for : During each scheduling interval, the CPU spends executing process code and performing the context switch:

One-fifth of all CPU cycles are wasted on pure overhead!

Evaluating overhead for :

Overhead is virtually negligible.

Trade-off analysis: A tiny quantum () offers ultra-fast response time for interactive programs, but wastes of system capacity on overhead. A large quantum () achieves near CPU efficiency, but degenerates into FCFS, causing sluggish interactive responsiveness for short user tasks.

Answer:
  1. With , context switch overhead is .
  2. With , context switch overhead drops to .
  3. Small quantums improve interactive responsiveness at the cost of high CPU overhead; large quantums maximize throughput but degrade interactive response times.
Question 4

Compute the execution sequence, Gantt chart, and average waiting time under non-preemptive Highest Response Ratio Next (HRNN) for the following processes:

ProcessArrival Time (AT)Burst Time (BT)

Decision point at : Only has arrived. runs non-preemptively from . Completion time .

Decision point at : At , ready processes are (arrived at ) and (arrived at ). Calculating Response Ratios :

  • For : Waiting time , Service time :
  • For : Waiting time , Service time :

Because , is selected to run from . Completion time .

Decision point at : At , ready processes are (arrived at ) and (arrived at ).

  • For : Waiting time , Service time :
  • For : Waiting time , Service time :

Because , is selected to run from . Completion time . Finally, runs from . Completion time .

Gantt chart and quantitative summary:

|   P1 (4)   |   P3 (2)   |      P2 (6)      |   P4 (4)   |
0            4            6                 12           16

Metrics calculation:

  • : , ,
  • : , ,
  • : , ,
  • : , ,

Averages:

Answer:

Under HRNN:

  • Execution order: .
  • Average Turnaround Time = .
  • Average Waiting Time = .
Question 5

Explain how the Completely Fair Scheduler (CFS) in Linux ensures balanced CPU allocation. Describe the role of virtual runtime (vruntime), the red-black tree, and nice values.

Core philosophy of CFS: CFS strives to simulate an ideal multi-tasking hardware model on real processors: each runnable task should receive a proportional slice of CPU processing power concurrently.

Role of vruntime and nice values: CFS tracks execution history using vruntime (virtual runtime), which accumulates the real execution time scaled inversely by task priority weight:

  • Nice Levels ( to ): A lower nice value (e.g., ) indicates high priority and assigns a heavy weight; its vruntime advances very slowly, allowing the task to execute longer before being preempted. A positive nice value advances vruntime quickly.

Red-Black Tree Organization: All runnable tasks are organized into a self-balancing Red-Black Tree keyed strictly by vruntime:

  • The task with the smallest vruntime resides at the leftmost node of the tree.
  • Dispatching the next task takes time by picking the cached leftmost node.
  • When the task completes its execution period, its vruntime is updated, and it is reinserted into the tree in time. Tasks that have received less CPU time naturally drift to the left and are prioritized.
Answer:

Linux CFS achieves fairness by scheduling the task with the smallest vruntime from the leftmost leaf of a red-black tree in time. Nice values alter the rate at which vruntime accumulates: high-priority tasks accumulate virtual runtime slowly, earning greater CPU execution share.

Question 6

Compare Starvation and the Convoy Effect. Explain which scheduling algorithms suffer from each condition, and explain how the technique of Aging solves starvation. [2078, 2073]

Starvation vs. Convoy Effect:

  • Convoy Effect: Occurs in non-preemptive First Come First Serve (FCFS) when a long, CPU-bound process captures the processor, forcing multiple short, I/O-bound processes to wait passively behind it. This degrades overall CPU utilization and device concurrency.
  • Starvation (Indefinite Blocking): Occurs in priority-based schedulers (such as SJF, SRTF, and static Priority Scheduling) when a continuous influx of short or high-priority processes monopolizes the CPU, preventing long or low-priority processes from ever obtaining execution time.

How Aging solves starvation: Aging is a dynamic scheduling technique where the operating system gradually increases the priority of a process the longer it waits in the Ready queue:

  • As time elapses, a low-priority or long job's effective priority steadily rises.
  • Eventually, its accumulated priority exceeds that of newly arriving short jobs, guaranteeing that every process will run within a predictable, bounded waiting timeframe.
Answer:

The Convoy Effect (in FCFS) traps short jobs behind a massive CPU-bound task; Starvation (in SJF/Priority) indefinitely postpones long or low-priority jobs due to incoming higher-priority tasks. Aging resolves starvation by incrementally boosting the priority of waiting processes over time until they are guaranteed execution.

Past exam questions for Operating System

← IntroductionThreads and thread scheduling →