Module 2
Module 2
Process and threads
Contents
Contents
• Process and programs
• Process states
• Process concept
• Process Control Block (PCB)
• Context switching
• Process scheduling
• CPU scheduling algorithms
• Operations on processes
• Interprocess Communication (IPC)
• Multithreading models
2
Process and programs
Process and programs
• Program: A passive set of instructions stored on disk (e.g., .exe,
.out, .sh files).
• Process: An active instance of a program in execution. It
includes:
– Program Counter (PC)
– Stack (function calls, parameters)
– Heap (dynamically allocated memory)
– Data section (global/static variables)
– Registers
3
Process and programs
Process and programs
Aspect Program Process
Nature Passive (code) Active (execution)
Stored in Disk Memory (RAM)
Lifecycle Static Dynamic
4
Process states
Process states
• A process undergoes multiple states during its lifetime:
– new: The process is being created
– ready: The process is waiting to be assigned to a processor
– running: Instructions are being executed
– waiting: The process is waiting for some event to occur
– terminated: The process has finished execution
5
Process states
Process states
6
Process concept
Process concept
• Components of a Process:
– Program Counter: Tracks next instruction.
– Registers: Store intermediate data.
– Stack: Holds function calls and local variables.
– Heap: Dynamic memory allocation.
– Data Section: Global variables.
• Process Control Block (PCB): OS uses PCB to manage
processes.
• Context Switching: The process of saving the current state of a
CPU and loading another process's state. It allows multitasking.
7
Process Control Block (PCB)
Process Control Block (PCB)
▪ Process state – running, waiting, etc
▪ Program counter – location of instruction to next execute
▪ CPU registers – contents of all process-centric registers
▪ CPU scheduling information- priorities, scheduling queue
pointers
▪ Memory-management information – memory allocated to
the process
▪ Accounting information – CPU used, clock time elapsed
since start, time limits
▪ I/O status information – I/O devices allocated to process,
list of open files
8
Context Switch
Context Switch
• When CPU switches to another process, the system must save the
state of the old process and load the saved state for the new
process via a context switch.
• Context of a process represented in the PCB.
• Context-switch time is overhead; the system does no useful work
while switching
▪ The more complex the OS and the PCB → the longer the context switch
• Time dependent on hardware support
▪ Some hardware provides multiple sets of registers per CPU → multiple
contexts loaded at once
9
CPU Switch From Process to Process
CPU Switch From Process to Process
10
Process scheduling
Process scheduling
• Maximize CPU use, quickly switch processes onto CPU for time
sharing.
• Process scheduler selects among available processes for next
execution on CPU.
• Maintains scheduling queues of processes:
▪ Job queue – set of all processes in the system
▪ Ready queue – set of all processes residing in main memory, ready
and waiting to execute
▪ Device queues – set of processes waiting for an I/O device
▪ Processes migrate among the various queues
11
Process scheduling
Process scheduling
• Scheduling Criteria:
– CPU Utilization: Amount of time the CPU is actively working
– Throughput: The number of processes completed per unit time.
– Turnaround Time: The total time taken from process submission to its
completion.
– Waiting Time: The total time a process spends in the ready queue (waiting for
CPU).
– Response Time: Time from process submission to the first time it gets the CPU.
• Types of Schedulers:
– Long-Term Scheduler (Job Scheduler): Selects processes from job pool and loads
them into memory.
– Short-Term Scheduler (CPU Scheduler): Selects from ready queue for execution.
– Medium-Term Scheduler: Swaps out processes to reduce memory load.
12
CPU scheduling algorithms
CPU scheduling algorithms
• Scheduling Algorithms:
– FCFS (First Come First Serve)
– SJF (Shortest Job First)
– Round Robin
– Priority Scheduling
• Objectives of Process Scheduling:
– Max CPU utilization, Max throughput, Min turnaround time, Min
waiting time, Min response time
13
First- Come, First-Served (FCFS) Scheduling
First- Come, First-Served (FCFS) Scheduling
Process Burst Time
P1 24
P2 3
P3 3
• Suppose that the processes arrive in the order: P1 , P2 , P3
The Gantt Chart for the schedule is:
P1 P2 P3
24 27 30
• Turn around time = completion time – arrival time
0
P1 = 24-0 = 24 P2 = 27-0 = 27 P3 = 30-0 = 30
• Average TAT : (24+27+30)/3
• Waiting time = TAT - BT
P1 = 0 P2 = 24 P3 = 27
• Average waiting time: (0 + 24 + 27)/3
14
Shortest-Job-First (SJF) Scheduling
Shortest-Job-First (SJF) Scheduling
• SJF is optimal – gives minimum average waiting time for a given set of processes
Process Burst Time
P1 6
P2 8
P3 7
P4 3
• SJF scheduling chart
P4 P1 P3 P2
0 3 9 16 24
• TAT : P1=9 P2=24 P3=16 P4=3
• ATAT : (9+24+16+3)/4
• Waiting time = P1=9-6=3 P2=24-8=16 P3=16-7=9 P4=3-3=0
• Average waiting time : (3 + 16 + 9 + 0) / 4 15
Shortest-remaining-time-first
• We add the concepts of varying arrival times and preemption to the analysis.
Process Arrival Time Burst Time
P1 0 8
P2 1 4
P3 2 9
P4 3 5
• Preemptive SJF Gantt Chart
P1 P2 P4 P1 P3
0 1 5 10 17 26
• TAT= P1=17-0=17 P2=5-1=4 P3=26-2=24 P4=10-3=7
• ATAT=(17+4+24+7)/4
• Waiting time= Completion time – Arrival Time – Burst Time
P1=(17-0-8)=9 P2=(5-1-4)=0 P3=(26-2-9)=15 P4=(10-3-5)=2
• Average waiting time = (9+0+15+2)/4 = 26/4 = 6.5 msec 16
Round Robin (RR)
• Example of RR with Time Quantum (q) = 4
Process Burst Time
P1 24
P2 3
P3 3
• The Gantt chart is:
P1 P2 P3 P1 P1 P1 P1 P1
0 4 7 10 26 30
14 18 22
• q should be large compared to context switch time
• q usually 10ms to 100ms, context switch < 10 μsec
AT BT CT TAT WT ATAT=(30+7+10)/3
P1 0 24 30 30 6 AWT=(6+4+7)/3
P2 0 3 7 7 4
P3 0 3 10 10 7 17
Non-Preemptive)
Priority Scheduling(Non-Preemptive)
• A priority number (integer) is associated with each process.
Process Burst Time Priority
P1 1 1
P2 5 2
P3 2 4
P4 6 5
P5 5 3
• Priority scheduling Gantt Chart
P1 P2 P5 P3 P4
0 1 6 11 13 19
AT BT CT TAT WT
P1 0 1 1 1 0 ATAT=(1+6+13+19+11)/5
P2 0 5 6 6 1
P3 0 2 13 13 11 AWT=(0+1+11+13+6)/5
P4 0 6 19 19 13
18
P5 0 5 11 11 6
Priority Scheduling(Preemptive)
Process AT BT Priority CT TAT WT
P1 0 9 4 19 19 10
P2 1 5 2 9 8 3
P3 2 3 1 5 3 0
P4 4 7 5 26 22 15
P5 5 2 3 11 6 4
P1 P2 P3 P2 P5 P1 P4
0 1 2 5 9 11 19 26
Average Waiting Time = 10+3+0+15+4=6.4 units
Average Turnaround Time = 19+8+3+22+6=11.6 units
Process scheduling
Process scheduling
Algorithm Description Use Case
FCFS First Come First Serve Simple batch systems
SJF Shortest Job First Minimizes average wait time
Round Robin Time-slice based Time-sharing systems
Priority Based on priority value Real-time systems
20
Operations on processes
Operations on processes
• Process Creation:
– Parent creates a child process via system calls like fork(), exec().
– Child can: Run concurrently with parent, Be a duplicate (copy of parent),
Load a different program.
• Process Termination:
– Process finishes execution or is aborted.
– Use exit() system call.
– Parent may use wait() to wait for child termination.
• Other Operations:
– Suspend/resume
– Inter-process communication setup
21
Interprocess Communication (IPC)
Interprocess Communication (IPC)
• Processes within a system may be independent or cooperating
• Cooperating process can affect or be affected by other processes,
including sharing data
• Reasons for cooperating processes:
▪ Information sharing
▪ Computation speedup
▪ Modularity
▪ Convenience
• Cooperating processes need interprocess communication (IPC)
22
Interprocess Communication (IPC)
Interprocess Communication (IPC)
• Two models of IPC :
– Shared Memory:
• Multiple processes access a common memory region.
• Faster but requires synchronization (mutex, semaphores).
– Message Passing:
• Processes communicate using messages (send/receive).
• Safer but can be slower.
• Mechanisms:
– Pipes (unnamed and named), Message Queues, Sockets, Signals,
Semaphores and Mutex
23
Communications Models
Communications Models
(a) Message Passing (b) Shared Memory
Two operations are
used in Message
Passing:
send(message)
receive(message)
24