Operating Systems Key Concepts: Process States, PCB, Semaphores & Memory

Posted on Oct 16, 2026 in Computers

Process States: A process cycles through: New (created) → Ready (waiting in memory) → Running (executing instructions) → Waiting/Blocked (waiting for an event/IO) → Terminated (finished execution).
PCB Definition: A dedicated kernel data structure containing all information about a specific process.
5 Essential PCB Fields:
1. Process State: Current condition (Ready, Running, etc.).
2. Program Counter (PC): Address of the next instruction to execute.
3. CPU Registers: Accumulators, stack pointers, index registers to save state during context switches.
4. CPU Scheduling Info: Priority levels, scheduling queue pointers.
5. Memory Management Info: Base/limit registers, page/segment tables.

Concept: Preemptive version of Shortest Job First (SJF). CPU is allocated to the process with the least remaining burst time.
Gantt Chart Construction:
\(\begin{array}{|c|c|c|c|c|c|c}\hline \text{P1}&\text{P2}&\text{P3}&\text{P4}&\text{P3}&\text{P1}&\\ \hline 0&1&3&4&5&7&11\\ \hline \end{array}\)
Step-by-Step Metrics:
- P1: Ends at 11. TAT = 11 – 0 = 11. WT = 11 – 5 = 6.
- P2: Ends at 3. TAT = 3 – 1 = 2. WT = 2 – 2 = 0.
- P3: Ends at 7. TAT = 7 – 2 = 5. WT = 5 – 3 = 2.
- P4: Ends at 5. TAT = 5 – 3 = 2. WT = 2 – 1 = 1.
Final Answer: Average Turnaround Time = \((11 + 2 + 5 + 2) / 4 = \mathbf{5.0\text{ ms}}\) (Note: Adjusted based on common standard matrix variants). Average Waiting Time = \((6 + 0 + 2 + 1) / 4 = \mathbf{2.25\text{ ms}}\).

Definition: A protected integer variable used for process synchronization and solving critical-section issues, accessed only via atomic operations.
The 2 Atomic Operations:
- wait(S) [or P(S)]: while (S <= 0); S--; (Decrements and blocks if unavailable)
- signal(S) [or V(S)]: S++; (Increments to release)
Types:
- Binary Semaphore: Integer value ranges strictly between 0 and 1 (functions identically to a Mutex lock).
- Counting Semaphore: Integer value can span an unrestricted domain, used to control access to a finite resource pool containing N identical items.

Definition: A code segment within a process where shared resources (variables, files, tables) are accessed. Concurrent execution causes unexpected race conditions.
The 3 Mandatory Solution Requirements:
1. Mutual Exclusion: If process \(P_{i}\) is executing in its critical section, no other processes can execute in their critical sections for that same shared resource.
2. Progress: If no process is executing in its critical section and some processes want to enter, only those processes not executing in their remainder sections can participate in deciding which process enters next.
3. Bounded Waiting: There must be a limit on the number of times other processes can enter their critical sections after a process has made a request to enter, preventing starvation.

Definition: A memory management scheme that eliminates the need for contiguous physical memory allocation, preventing external fragmentation.
Mechanism:
- Physical memory is divided into fixed-size blocks called Frames.
- Logical memory is divided into blocks of identical size called Pages.
Address Translation: The CPU generates a logical address containing a Page Number (p) and a Page Offset (d). The OS uses a hardware Page Table indexed by p to find the matching physical Frame Number (f). The resulting physical address is calculated as \((f \times Frame\ Size) + d\).

Input Reference String: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 (with 3 frames).
FIFO (First-In, First-Out): Replaces the oldest page in memory.
- Total Page Faults: 15
LRU (Least Recently Used): Replaces the page that has not been used for the longest period of time.
- Total Page Faults: 12
Optimal: Replaces the page that will not be used for the longest duration in the future (requires clairvoyance).
- Total Page Faults: 9

Definition: A permanent stall condition where a set of processes are blocked because each process holds a resource and waits for another resource held by another process in the loop.
The 4 Simultaneous Coffman Conditions:
1. Mutual Exclusion: At least one resource must be held in a non-shareable mode (only one process can use it at a time).
2. Hold and Wait: A process must currently hold at least one resource while waiting to acquire additional resources held by others.
3. No Preemption: Resources cannot be forcibly taken from a process; they must be released voluntarily.
4. Circular Wait: A closed chain of processes exists, where each process waits for a resource held by the next process in the chain.

Definition: A classic deadlock avoidance algorithm used in systems with multiple instances of resources.
Data Structures: Available[m], Max[n][m], Allocation[n][m], and Need[n][m] (where Need = Max – Allocation).
Safety Algorithm Flow:
1. Initialize vectors: Work = Available and Finish[i] = False for all processes.
2. Find an index i such that Finish[i] == False and Need[i] <= Work. If no such i exists, skip to step 4.
3. Update tracking state: Work = Work + Allocation[i], set Finish[i] = True, and return to step 2.
4. If Finish[i] == True for all processes, the system is in a Safe State; otherwise, it is unsafe (deadlock risk).

Problem: How to efficiently allocate a free memory hole of size N from a list of fragmented available blocks.
The 3 Core Strategies:
1. First-Fit: Scans memory from the beginning and allocates the first block that is large enough. Fast execution but leads to fragmentation at the front.
2. Best-Fit: Searches the entire list to allocate the smallest block that is large enough. Leaves tiny, unusable leftover holes but preserves large blocks.
3. Worst-Fit: Searches the entire list to allocate the largest available block. Leaves large leftover fragments that can easily fit future processes, but is highly inefficient.

The 3 Core Structural Approaches:
- Sequential Access: Information is processed in order, one record after another (e.g., standard text editors, compilers). Modeled after legacy magnetic tapes; operations include read_next() and write_next().
- Direct (Relative) Access: Information can be read or written out of order by referencing block numbers directly (e.g., database file storage). Operations are based on a fixed block size, allowing immediate jumps using read(n).
- Indexed Access: Built on top of direct access. An Index Table containing pointers to various blocks is built and kept in memory. The system looks up the pointer in the index first, then accesses the physical block directly, enabling ultra-fast random lookups on massive files.