Processes and Threads: States, PCB, Scheduling and Deadlock · প্রসেস ও থ্রেড: অবস্থা, পিসিবি, শিডিউলিং ও ডেডলক

1. Program vs process

A program is passive: a file of instructions sitting on disk. A process is that program in execution — active, with a current value of the program counter, registers, a stack, a heap and the resources the OS has given it. One program can have many processes (open the same editor twice → two processes).

A process in memory has four segments: text (the code), data (global/static variables), heap (memory allocated at run time) and stack (function calls and local variables, growing toward the heap).

2. The Process Control Block (PCB)

For every process the OS keeps a Process Control Block, the data structure that is the process from the kernel's point of view. It holds:

• Process ID (PID) and parent PID;
• Process state (new, ready, running, …);
• Program counter — the address of the next instruction;
• CPU registers — saved so execution can resume exactly;
• CPU-scheduling information — priority, queue pointers;
• Memory-management information — base/limit registers, page tables;
• Accounting — CPU time used, time limits;
• I/O status — open files, allocated devices.

On a context switch the OS saves the running process's state into its PCB and loads the next process's state from its PCB. ("Old" is not a PCB state — the states are new, ready, running, waiting, terminated.)

3. Process states (the five-state model)

1. New — being created; the PCB is set up but it is not yet runnable.
2. Ready — has everything except the CPU; waiting in the ready queue.
3. Running — executing on the CPU (only one process per core at a time).
4. Waiting (Blocked) — cannot continue until an event (I/O, a signal, a lock) occurs; not competing for the CPU.
5. Terminated — finished; the OS reclaims its resources.

Two transitions students wrongly draw:

• There is no direct Waiting → Running. When I/O finishes, the process goes to Ready first and waits to be dispatched.
• There is no direct Ready → Waiting. Only a running process can block, because only it can issue an I/O request.

A seven-state extension adds Ready/Suspended and Blocked/Suspended for processes swapped out of memory to disk. In UNIX, a finished process whose parent has not yet collected its exit status is a zombie; a process whose parent died first is an orphan.

4. Context switching

A context switch is the act of saving the state of the running process into its PCB and loading another process's state so the CPU can run it. It is pure overhead — no useful work happens during the switch — so a scheduler that switches too often wastes time. A switch is triggered by a timer interrupt (preemption), an I/O request (the process blocks), or a higher-priority process becoming ready. Thread switches within one process are cheaper than process switches because the address space (memory map) does not change.

5. Threads

A thread is a lightweight unit of execution within a process — the smallest sequence the scheduler handles. A process starts with one thread; a multithreaded process has several, running "at the same time" and sharing the process's resources.

Shared vs private. Threads of one process share the code, data/heap, and open files; each thread has its own stack, registers and program counter. Because they share memory, threads communicate cheaply (no IPC) — but that sharing is also why multithreaded programs are more prone to deadlocks and race conditions, and the main difficulty of multithreading is managing concurrency.

User-level vs kernel-level threads:

	User-level threads (ULT)	Kernel-level threads (KLT)
Managed by	A library in user space; kernel unaware	The OS kernel
Switching	Fast (no kernel trap)	Slower (a system call)
Blocking	One blocking call blocks the whole process	One thread blocks; others keep running
Multicore	Cannot use multiple cores alone	Can run on different cores

Multithreading models map user threads to kernel threads: Many-to-One (fast, but one block stops all; no true parallelism), One-to-One (true concurrency, one kernel thread per user thread — modern Linux and Windows), and Many-to-Many (m user to n ≤ m kernel threads, flexible).

Process vs thread — the exam table:

Aspect	Process	Thread
Definition	Program in execution	Lightweight unit inside a process
Memory	Own separate address space	Shares the process's address space
Creation / switch cost	High (heavy)	Low (light, no address-space change)
Communication	IPC (pipes, sockets, shared memory)	Direct, via shared variables
Fault isolation	One crash does not kill others	A bad thread can crash the whole process

Related terms: multiprogramming keeps several processes in memory so the CPU always has work; multitasking is time-sharing the CPU among tasks so they appear to run together; multiprocessing uses more than one CPU/core to run processes truly at the same time; multithreading runs several threads within one process.

6. fork(): counting processes

On POSIX systems (defined by The Open Group, IEEE Std 1003.1) a process creates a child with fork(). It is called once but returns twice: 0 in the child, and the child's PID in the parent. (UNIX uses fork() to create a process; there is no CreateProcess() in UNIX — that is a Windows call. fork() is POSIX, so it is not available in standard C on native Windows without a POSIX layer.)

How many processes after n consecutive forks? Each fork() doubles the number of processes, so after n calls in a row there are 2ⁿ processes in total (the original plus 2ⁿ − 1 children). Verified by running real fork() code:

Consecutive fork() calls	Total processes	= 2ⁿ
1	2	2¹
2	4	2²
3	8	2³
4	16	2⁴

A classic trap: how many times is a line after a loop of 3 forks printed?

for (int i = 0; i < 3; i++) {
    fork();
    printf("hi\n");
}

The print is inside the loop, so it runs once per process per remaining iteration; the total number of "hi" lines is 2¹ + 2² + 2³ = 2 + 4 + 8 = 14 — the exam answer, and what a terminal shows. (If output is redirected to a file or pipe, the same program prints 24 lines: stdout is then fully buffered, each fork() copies the unflushed "hi" lines into the child, and all 8 final processes flush 3 lines each. Calling fflush(stdout) before fork() avoids this. Both counts were confirmed by real runs.) If the printf were placed after the loop, there would be 2³ = 8 processes and 8 lines.

7. CPU scheduling (one worked example)

The scheduler picks which ready process runs next. An OS actually has three schedulers:

Scheduler	Also called	Decides	Runs
Long-term	Job scheduler	Which new jobs are admitted into memory (controls the degree of multiprogramming)	Rarely
Short-term	CPU scheduler	Which ready process gets the CPU next	Very often (milliseconds)
Medium-term	Swapper	Which processes to swap out to disk and back (suspend/resume)	Occasionally

The dispatcher is the module that actually hands the CPU to the process the short-term scheduler chose (context switch, switch to user mode, jump to the right instruction); the time it takes is the dispatch latency.

Scheduling criteria — what a good algorithm aims for: maximise CPU utilisation and throughput (processes finished per unit time); minimise turnaround time, waiting time and response time (time from arrival to the first run). The metrics used below (AT = arrival time, BT = burst time, CT = completion time):

• Turnaround time TAT = CT − AT
• Waiting time WT = TAT − BT

The main algorithms:

Algorithm	Preemptive?	Picks	Note
FCFS	No	Earliest arrival	Simple; convoy effect, high waiting time
SJF (also called Shortest Job Next, SJN)	No	Smallest burst	Minimum average waiting time when all jobs are available together (SRTF is optimal when they arrive over time); needs the burst known; can starve long jobs
SRTF	Yes	Smallest remaining burst	Preemptive SJF; even lower waiting; may starve
Priority	Either	Highest priority (in most exam questions a smaller number means higher priority)	Can starve low priority → fix with aging
Round Robin	Yes	Next in queue, time quantum	Fair, good response; overhead if the quantum is tiny
Multilevel (feedback) queue	Yes	Several ready queues by class or priority, each with its own algorithm	In the feedback version a process that uses too much CPU moves to a lower queue, and one that waits long moves up

Worked example. Four processes:

Process	Arrival (AT)	Burst (BT)
P1	0	7
P2	2	4
P3	4	1
P4	5	4

Round Robin, time quantum q = 2 (a newly arrived process joins the ready queue before a just-preempted one; if the preempted process is queued first instead, the averages change to WT 5.75 and TAT 9.75 — always state the rule you use). The Gantt chart:

| P1 | P2 | P1 | P3 | P2 | P4 | P1 | P4 | P1 |
0    2    4    6    7    9    11   13   15   16

Completion times: P1 = 16, P2 = 9, P3 = 7, P4 = 15. The table (all arithmetic verified in Python):

Process	AT	BT	CT	TAT = CT − AT	WT = TAT − BT
P1	0	7	16	16	9
P2	2	4	9	7	3
P3	4	1	7	3	2
P4	5	4	15	10	6

• Average waiting time = (9 + 3 + 2 + 6) ÷ 4 = 20 ÷ 4 = 5.0
• Average turnaround time = (16 + 7 + 3 + 10) ÷ 4 = 36 ÷ 4 = 9.0

For the same four processes, the verified averages under the other algorithms are: FCFS avg WT 4.75; SJF (non-preemptive) avg WT 4.0; SRTF avg WT 3.0 (the lowest, as SJF-type scheduling minimises average waiting time). Note which algorithms can cause starvation: SJF (Shortest Job Next), SRTF and priority (a steady stream of short or high-priority jobs can indefinitely delay a long or low-priority one); FCFS and round robin cannot starve.

8. Deadlock: the Coffman conditions

A deadlock is a set of processes each waiting for a resource held by another in the set, so none can proceed. It needs all four Coffman conditions at once:

1. Mutual exclusion — a resource can be held by only one process at a time.
2. Hold and wait — a process holding at least one resource is waiting for more.
3. No preemption — a resource cannot be forcibly taken; it is released only voluntarily.
4. Circular wait — a closed chain of processes, each waiting for a resource the next one holds.

Break any one condition and deadlock cannot occur — the basis of deadlock prevention. The four conditions are necessary but not sufficient: in a resource-allocation graph, a cycle means deadlock if every resource has a single instance; with multiple instances a cycle is necessary but not sufficient. A single process on its own cannot deadlock, because circular wait needs at least two (in the classic Coffman sense; a thread can still hang itself by re-locking a non-reentrant mutex it already holds). Handling strategies: prevention (deny a condition), avoidance (the Banker's algorithm keeps the system in a safe state), detection and recovery, and the ostrich algorithm (ignore it, as general-purpose OSes mostly do).

A resource-counting result that exams ask: if n processes each need at most m units of a resource with R identical units, the system is deadlock-free as long as n × (m − 1) + 1 ≤ R (give every process m − 1 and one unit is still spare to let someone finish). For example, with R = 6 units and each process needing at most m = 3, up to n = 2 processes are guaranteed deadlock-free (2 × 2 + 1 = 5 ≤ 6), but n = 3 can deadlock — verified by brute-force search.

9. The critical section (in brief)

A critical section is the part of a program that accesses a shared resource and must not run in two processes at once. A correct solution needs three properties: mutual exclusion (at most one process inside), progress (if no one is inside, a waiting process can enter), and bounded waiting (no process waits forever). It is enforced with locks/mutexes, semaphores (Dijkstra's wait/signal), or monitors. A binary semaphore takes only 0 or 1 and works like a lock; a counting semaphore holds any non-negative value and controls access to a pool of identical resources (for example 5 printer slots). Mishandled locks are exactly how the circular-wait condition for deadlock arises.