CHAPTER TWO

PROCESSES AND PROCESS MANAGEMENT

2.1 The Process Concept

What is a Process?
A process is a program that is currently executing.
👉 A program is passive (stored on disk)
👉 A process is active (running in memory)

Example:
 [Link] on disk → Program
 When you open Chrome browser → It becomes a process
Components of a Process
1. Text Section: This contains the executable instructions of the program. It is typically a
read-only section in memory.
2. Stack: The stack holds temporary data such as function parameters, return addresses, and
local variables. It grows and shrinks dynamically as functions are called and return.
3. Data Section: This section contains global and static variables that are initialized and
used by the process.
4. Heap: The heap is used for dynamic memory allocation during the process's runtime. It
grows as the process allocates memory dynamically.
2.1.1 Process Control Block (PCB)
The Process Control Block (PCB) is a critical data structure maintained by the operating system
to manage processes.
Why PCB is Needed?
Modern operating systems are multitasking systems.
Example:
 Chrome running
 VS Code running
 Music player running
 Antivirus running

The CPU switches between them very quickly

To do this, the OS must:
1. Save the current process state
2. Restore the next process state
This information is stored in the PCB.
2.1.2 Components of PCB
 Process ID (PID): A unique identifier for the process.
 Process State: Indicates whether the process is running, ready, waiting, etc.
 Program Counter: Tracks the next instruction to execute.
 CPU Registers: Stores the current state of the CPU for the process.
 Memory Management Information: Details about the process's memory layout,
including stack, heap, and data sections.
 I/O Information: Tracks the input/output devices and files used by the process.
 Priority and Scheduling Information: Helps the OS decide the execution order of
processes.
 Accounting Information: Tracks resource usage, such as CPU time and memory.
2.1.3 Process State
Definition
A process state describes the current status of a process during its execution.
Since multiple processes share one CPU, a process cannot run all the time.
It moves between different states depending on what it is doing.

new ready running terminated

waiting

1. New State
  Process is being created.
 OS is preparing PCB and allocating memory.
📌 Example:
When you double-click Chrome, the process is in New state before execution starts.
2. Ready State
 Process is loaded into memory.
 Waiting for CPU allocation.
 It is ready to execute but CPU is busy.
📌 Example:
You open 5 applications.
Only one runs. The others wait in the Ready Queue.
3. Running State
 Process is currently executing on CPU.
📌 Example:
When typing in Word, that process is in Running state.
Important:
👉 In single-core CPU → only ONE process can be running at a time.
4. Waiting (Blocked) State
 Process is waiting for I/O operation.
 Waiting for resource (disk, printer, network).
📌 Example:
When saving a file to disk → process waits for disk response.
It cannot continue until the event finishes.
5. Terminated State
 Process has finished execution.
 OS releases memory and resources.
 PCB is deleted.
📌 Example:
When you close Notepad → it enters Terminated state.
2.1.4 PCB And Context Switching
 A context switch is the mechanism by which an operating system switches the CPU from
executing one process to executing another.

 Modern operating systems are multitasking: multiple processes share the CPU.
 Context switching allows the CPU to switch between processes quickly, giving the
illusion of parallel execution.
Example:
 On your computer, you can browse the internet while a file is downloading in the
background. This is possible because the OS switches the CPU between processes.
Key Point: Context includes CPU registers, program counter, stack pointer, and memory
management information.
Process Context
The context of a process consists of all information needed by the CPU to resume execution of a
process:
1. Processor State
o Program Counter (PC)
o Stack Pointer (SP)
o CPU registers
2. Memory Management Information
o Page tables
o Segment tables
3. Process State Information
o Process ID
o Priority
o Status (Ready, Waiting, Running)
4. I/O Information
o Open files
o I/O devices used
Context Switching Steps
1. Interrupt occurs:
o Timer or I/O triggers the OS to take control.
2. Save state of current process:
o CPU registers, program counter, stack pointer, and other info are saved in the
process control block (PCB).
3. Update process state:
o Change the status of the current process (e.g., Running → Ready or Waiting).
4. Select next process:
o OS chooses the next process to run (from ready queue).
5. Load state of next process:
o Restore CPU registers, program counter, stack pointer, etc., from its PCB.
6. Resume execution:
o CPU starts executing the next process from where it left off.

2.2 The Threads Concept

Definition:
A thread is the smallest unit of CPU execution inside a process.
 A process may contain multiple threads
 Threads share:
o Code section
o Data section
o Heap
 Each thread has its own:
o Program Counter
o Registers
o Stack
Thread Structure
Process
├── Thread 1 (PC, Registers, Stack)
├── Thread 2 (PC, Registers, Stack)
└── Thread 3 (PC, Registers, Stack)
Shared: Code, Data, Heap

Why Threads?
To improve:
 Responsiveness
 Performance
 CPU utilization
Real Example – Web Browser
Google Chrome:
 Thread 1 → Render webpage
 Thread 2 → Handle user input
 Thread 3 → Download file
 Thread 4 → Play video
All run inside one process.

Types of Threads
User-Level Threads
 Managed by user library
 Fast to create
 If one blocks → all block
Kernel-Level Threads
 Managed by OS
 Can run independently
 More overhead
Advantages of Threads
✔ Faster than processes
✔ Less memory usage
Disadvantages
❌ Race condition
❌ Crash affects entire process

2.3 Inter-Process Communication (IPC)

2.3.1 Introduction
Modern operating systems support multiprogramming and multitasking, allowing multiple
processes to execute concurrently. However, many of these processes are not isolated; they must
cooperate to complete larger tasks.
Inter-Process Communication (IPC) is the mechanism that enables such cooperation.
IPC allows processes to:
 Exchange information
 Share system resources
 Coordinate execution
 Synchronize access to shared data
Without IPC, complex systems like banking platforms, telecom billing systems, and university
registration portals could not function properly.
2.3.2 Process Concepts Related to IPC
Independent Processes
 Do not share data
 Do not affect each other
 Execute separately
Example: A calculator application running while music plays
Cooperating Processes
 Share data
 Share resources
 Affect each other’s execution
Example (Ethiopian Banking System):
 Process 1: ATM withdrawal
 Process 2: Account balance update
 Process 3: SMS notification
These processes must communicate to maintain system correctness.
2.3.3 Need for Inter-Process Communication
IPC is required for several reasons:
1. Information Sharing
Example: University student portal database accessed by multiple departments.
2. Computation Speedup
Large tasks are divided into smaller subtasks.
Example:
 Payroll processing in government offices
Parallel execution improves performance.
3. Modularity
Complex systems are divided into modules:
 Payment module
 Authentication module
 Notification module
These modules must communicate.
4. Convenience
Allows multitasking:
 Browsing
 Downloading
 Listening to music simultaneously
2.3.4 IPC Models
There are two fundamental IPC models:

inter-process
communication

shard memorey meassage passing

1) Shared Memory Model

 In shared memory, processes share a common memory region.
 It is the fastest IPC method because no data copying is required.
Working Mechanism
1. Process A creates shared memory.
2. OS maps it into A’s address space.
3. Process B attaches the same memory.
4. Both processes read/write data.
Synchronization Requirement
Since multiple processes access the same memory:
 Race conditions may occur
 Data inconsistency may happen
Therefore, synchronization tools are required:
 Mutex, Semaphore, Monitor
Advantages
 Very high speed
 Efficient for large data
Disadvantages
 Complex implementation/
 Requires synchronization
 Risk of deadlock
2) Message Passing Model
 Processes communicate by sending and receiving messages.
 No shared memory exists.
Characteristics
 Kernel managed
 Built-in synchronization
 Suitable for distributed systems
Advantages
 Easier to implement
 Safer
 Works across network
Disadvantages
 Slower than shared memory
 Message copying overhead

2.4 Process Scheduling

Process Scheduling is the mechanism used by the Operating System (OS) to decide Which
process gets the CPU, when, and for how long.

There are two categories of scheduling:

1. Non-preemptive: Here the resource can’t be taken from a process until the process
completes execution. The switching of resources occurs when the running process
terminates and moves to a waiting state.
2. Preemptive: Here the OS allocates the resources to a process for a fixed amount of time.
During resource allocation, the process switches from running state to ready state or from
waiting state to ready state. This switching occurs as the CPU may give priority to other
processes and replace the process with higher priority with the running process.

In a multiprogramming system, many processes compete for one CPU. The scheduler ensures
fairness and efficiency.

Scheduling Criteria
Scheduling criteria are standards used to evaluate CPU scheduling algorithms.

(i) CPU Utilization

 Percentage of time CPU is busy.
 Goal: Maximize (close to 100%).
busy time
CPU Utilization= x 100
total time
👉 High utilization = better performance.

(ii) Throughput
 Number of processes completed per unit time.
 Goal: Maximize.
Example:
If 50 processes finish in 10 seconds → Throughput = 5 processes/sec.

(iii) Turnaround Time (TAT)

 Total time from process arrival to completion.
 Goal: Minimize.

TAT=Completion Time−Arrival time

 (iv)Waiting Time (WT)

 Time spent waiting in ready queue.

 Goal: Minimize.
WT=Turnaround Time−Burst time

(v) Response Time (RT)

 Time from arrival until first response.
 Goal: Minimize.
RT=First Start Time−Arrival Time
Scheduling algorithms

Process Scheduler schedules different processes to be assigned to the CPU based on particular
scheduling algorithms. There are six popular process scheduling algorithms which we are going
to discuss in this chapter −

 First-Come, First-Served (FCFS) Scheduling

 Shortest-Job-Next (SJN) Scheduling
 Priority Scheduling
 Shortest Remaining Time
 Round Robin (RR) Scheduling
 Multiple-Level Queues Scheduling

1. First Come First Serve (FCFS)

 Jobs are executed on first come, first serve basis.

 It is a non-preemptive
 Easy to understand and implement.
 Its implementation is based on FIFO queue.
 Poor in performance as average wait time is high.
Example

Process Arrival time Brust time

P1 0 4
P2 1 3
P3 2 2
Execution Order: P1 → P2 → P3

2. Shortest Job Next (SJN)

  This is also known as shortest job first, or SJF
 This is a non-preemptive, pre-emptive scheduling algorithm.
 Best approach to minimize waiting time.
 Easy to implement in Batch systems where required CPU time is known in advance.
 Impossible to implement in interactive systems where required CPU time is not
known.
 The processer should know in advance how much time process will take.
Example
Process AT BT
P1 0 6
P2 1 2
P3 2 4

Execution:
At time 0 → P1 runs (only available)
After 6 → choose shortest (P2)
Then P3
Order: P1 → P2 → P3
3. Priority Based Scheduling
 Priority scheduling can be either non-preemptive or preemptive algorithm and one of
the most common scheduling algorithms in batch systems.
 Each process is assigned a priority. Process with highest priority is to be executed
first and so on.
 Processes with same priority are executed on first come first served basis.
 Priority can be decided based on memory requirements, time requirements or any
other resource requirement.
Example
Process AT BT
P1 0 5
P2 1 3
P3 2 4
 Execution (Preemptive):
P1 starts →
At time 1, P2 arrives (higher priority) → P1 interrupted
Order:
P2 → P3 → P1
4. Shortest Remaining Time
 Shortest remaining time (SRT) is the preemptive version of the SJN algorithm.
 The processor is allocated to the job closest to completion but it can be
preempted by a newer ready job with shorter time to completion.
 Impossible to implement in interactive systems where required CPU time is
not known.
 It is often used in batch environments where short jobs need to give
preference.
Example
Process AT BT
P1 0 8
P2 2 4

Execution:
0–2 → P1
At 2 → P2 arrives (shorter)
P1 interrupted
Order: P1 | P2 | P1 ||
5. Round Robin Scheduling
 Round Robin is the preemptive process scheduling algorithm.
 Each process is provided a fix time to execute, it is called a quantum.
 Once a process is executed for a given time period, it is preempted and other
process executes for a given time period.
 Context switching is used to save states of preempted processes.
Example
Time Quantum = 2
 Process AT BT
P1 0 5
P2 1 4

Execution:
P1(2) → P2(2) → P1(2) → P2(2) → P1(1)
6. Multiple-Level Queues Scheduling
Multiple-level queues are not an independent scheduling algorithm. They make use of other
existing algorithms to group and schedule jobs with common characteristics.
 Multiple queues are maintained for processes with common characteristics.
 Each queue can have its own scheduling algorithms.
 Priorities are assigned to each queue.
For example, CPU-bound jobs can be scheduled in one queue and all I/O-bound jobs in another
queue. The Process Scheduler then
alternately selects jobs from each queue and assigns them to the CPU based on the algorithm
assigned to the queue.

2.5 Process Synchronization

Definition
Process Synchronization ensures that two or more processes can execute concurrently
without interfering with each other when sharing resources.
 Critical in multithreaded/multiprogramming systems.
 Prevents race conditions, data inconsistency, and deadlocks.
2.5.1 Critical Section Problem
 Critical Section (CS): Part of the program where shared resources are accessed.
 Goal: Only one process at a time can execute in CS.
Conditions to Solve critical section Problem:
1. Mutual Exclusion: Only one process in CS at a time.
2. Progress: If no process is in CS, a process waiting should enter CS.
3. Bounded Waiting: No process waits forever.
Example (Ethiopian Bank ATM):
Two ATMs accessing the same account. If both read and update balance at the same time →
wrong balance → race condition.

Race Condition
 Occurs when two or more processes access shared data concurrently and the final
outcome depends on order of execution.
Example:
Process Action
P1 Read balance $100
P2 Read balance $100
P1 Deposit $50 → balance $150
P2 Withdraw $30 → balance $70 (should be $120)
Wrong result → race condition.
2.5.2 Synchronization Mechanisms
Mutex Locks
 Mutex (Mutual Exclusion Object): Allows only one process to enter CS.
 Operation: Lock () → CS → Unlock ()
Example:
ATM transaction process:
1. Acquire lock
2. Update balance
3. Release lock
Semaphores

A semaphore is an integer variable used for process synchronization to control access to

shared resources.

 Ensures mutual exclusion and prevents race conditions.

 Can be binary (0 or 1) or counting (≥0).

Types of Semaphore
 Type Value Use
Binary Semaphore 0 or 1 Mutual exclusion (like a mutex)
Counting Semaphore 0, 1, 2,… Manage multiple identical resources

Operations on Semaphore

1. wait () / P () → Decrement value

o If value < 0 → process waits
2. signal () / V () → Increment value
o If value ≤ 0 → wake up waiting process

Example – Binary Semaphore (Mutex)

Scenario: Bank account accessed by two ATMs

 Initial: semaphore S = 1

Process P1 (ATM1):

wait(S) // S = 0, enter critical section

update balance
signal(S) // S = 1, leave critical section

Process P2 (ATM2):

wait(S) // If S = 0, P2 waits
update balance
signal(S)

Result: Only one ATM updates balance at a time → no race condition

Example – Counting Semaphore

Scenario: 3 printers shared among 5 processes

 Initialize semaphore S = 3
 Each print job:

wait(S) // occupy printer

print document
signal(S) // release printer

Result: At most 3 processes print simultaneously

Monitors
  High-level synchronization construct.
 Combines mutex + condition variables.
 Only one process executes in the monitor at a time.
Example:
Producer-Consumer problem.
2.5.3 Classical Synchronization Problems

1. Producer-Consumer Problem
 Shared buffer between producer (writes) and consumer (reads).
 Avoid buffer overflow and underflow using semaphores.
Example (University Lab):
 Producer → lab server updates marks
 Consumer → student portal reads marks
2. Reader-Writer Problem
 Many readers can read simultaneously.
 Writers require exclusive access.
Example (Bank):
 Multiple ATMs read balance
 Only one process can update balance
3. Dining Philosophers Problem
 Demonstrates deadlock and resource allocation problem.
 Philosophers = processes
 Forks = shared resources
Example:
 5 ATMs sharing 5 database connections → need proper synchronization

2.6 Deadlock

A deadlock occurs when two or more processes are waiting for resources held by each
other, and none can proceed.

 System becomes stuck.

 Common in multiprogramming/multithreading systems.
Example (Ethiopian Bank ATM):

 P1 holds printer, wants scanner

 P2 holds scanner, wants printer
 Both wait forever → deadlock

Necessary Conditions for Deadlock (Coffman Conditions)

All 4 conditions must hold simultaneously:

Condition Description
Mutual Exclusion Only one process can use a resource at a time
Hold and wait Process holds a resource and waits for others
No Preemption Resource cannot be forcibly taken from process
Circular Wait Chain of processes exists where each wait for next

Resource Allocation Graph (RAG)

 Graphical way to detect deadlock.

 Nodes: Processes (P1, P2) and Resources (R1, R2)
 Edges:
o Request → from process to resource
o Assignment → from resource to process

Cycle in graph = potential deadlock

Methods to Handle Deadlock

I. Deadlock Prevention

Break one Coffman condition to prevent deadlock.

Example:

1. Mutual Exclusion: Share read-only resources

2. Hold and Wait: Request all resources at once
3. No Preemption: Preempt resources if needed

II. Deadlock Avoidance

 Use resource allocation strategies to avoid unsafe states.

 Banker’s Algorithm: Checks if resource allocation keeps system safe.

Example:

 Bank checks if ATM requests can be safely allocated before granting them.
III. Deadlock Detection and Recovery

 Let deadlock occur, then detect & recover.

 Detection: Check for cycles in RAG
 Recovery:
o Terminate a process
o Preempt resources

Example:

 University registration server detects 2 students waiting on each other → terminate one
registration session

2.7 STARVATION
Definition:

Starvation occurs when a process waits indefinitely because other higher-priority processes
keep taking the CPU or resources.

 Process is ready but never gets executed.

 Common in priority-based scheduling.

Cause

 High-priority processes continuously arrive → low-priority processes never run.

 Improper resource allocation or scheduling policy.

Solution
Aging: Gradually increase the priority of waiting processes over time until they get executed.