Essential Operating System Principles

Posted on Aug 13, 2025 in Computers

Process Control Block (PCB) Essentials

The Process Control Block (PCB) is a fundamental data structure maintained by the operating system for every process. It contains all the information needed to manage and control a process. The PCB is essential for process scheduling, context switching, and execution.

Key Components of a PCB

Here are the main components typically stored in a PCB:

• Process ID (PID): Unique identifier for the process.
• Process State: Current status (e.g., Ready, Running, Waiting, Terminated).
• Program Counter: Address of the next instruction to be executed.
• CPU Registers: Values of the CPU registers when the process is not running (for context switch).
• Memory Management Info: Base and limit registers, page tables, segment tables, etc.
• Scheduling Info: Priority, pointers to scheduling queues, etc.
• Accounting Info: CPU usage, process start time, execution time, etc.
• I/O Status Info: List of I/O devices assigned, open files, etc.
• Parent/Child Info: Information about parent and child processes (for process hierarchy).

PCB in the Process Lifecycle

When a process is:

• Created: A PCB is initialized and stored.
• Running: The OS refers to the PCB to track execution.
• Switched Out (Context Switch): The current state (Program Counter, registers, etc.) is saved in the PCB.
• Terminated: The PCB is deleted from the process table.

Context Switching with PCB

Context switching means switching the CPU from one process to another. During this operation:

1. The OS saves the state of the current process in its PCB.
2. It loads the state of the next scheduled process from its PCB.
3. The CPU resumes execution of the new process.

Deadlock Management Strategies

Deadlocks are a critical challenge in operating systems. Deadlock detection, deadlock prevention, and deadlock avoidance are the main methods for handling deadlocks. Details about these are given as follows:

Methods for Handling Deadlocks

1. Ignoring Deadlocks: It might be preferable to ignore the issue if the risk of a deadlock is sufficiently low and the cost of avoiding one is sufficiently high. For instance, if a deadlock occurs on a PC once every 100 years, a reboot may be less painful than the limitations required to stop it.

2. Deadlock Detection & Recovery: Deadlocks can be detected by the resource scheduler as it keeps track of all the resources allocated to different processes. After a deadlock is detected, it can be handled using recovery methods:

   • All the processes involved in the deadlock are terminated. This approach is not very useful as all progress made by the processes is destroyed.
   • Resources can be preempted from some processes and given to others until the deadlock situation is resolved.

3. Deadlock Avoidance: This method aims to avoid deadlocks by careful resource scheduling, ensuring that the system never enters an unsafe state.

4. Deadlock Prevention: It is important to prevent a deadlock before it can occur. So, the system checks each transaction before it is executed to make sure it does not lead to a deadlock. If there is even a slight possibility that a transaction may lead to a deadlock, it is never allowed to execute.

Operating System Schedulers

Operating systems employ various schedulers to manage processes and allocate CPU time efficiently.

Types of OS Schedulers

1. Long-Term Scheduler (Job Scheduler)

   A long-term scheduler, also known as a job scheduler, determines which programs should be admitted to the system for processing. It selects and loads processes into memory for execution with the help of CPU scheduling. It provides a balanced combination of jobs, such as I/O-bound and processor-bound, and controls the degree of multiprogramming. A stable degree of multiprogramming means that the average rate of process creation and the average departure rate of processes leaving the system are equal.

2. Short-Term Scheduler (CPU Scheduler)

   A short-term scheduler, also known as a CPU scheduler, selects a process from the multiple processes that are in the ready state in order to execute it and allocates the CPU to one of them. It is faster than long-term schedulers and is also called a dispatcher as it makes the decision on which process will be executed next.

   The primary distinction between these two schedulers lies in the frequency of execution. The short-term scheduler must select a new process for the CPU frequently. A process may execute for only a few milliseconds before waiting for an I/O request. Often, the short-term scheduler executes at least once every 100 milliseconds. Because of the short time between executions, the short-term scheduler must be fast.

3. Medium-Term Scheduler (Swapping)

   The medium-term scheduler removes processes from memory (and from active contention for the CPU), thereby reducing the degree of multiprogramming. At some later time, the process can be reintroduced into memory, and its execution can be continued where it left off. This scheme is called swapping. The process is swapped out and is later swapped in by the medium-term scheduler. Swapping is necessary to improve the process mix. This scheduler controls the degree of multiprogramming and is in charge of handling the swapped-out processes.

First-Come, First-Served (FCFS) Scheduling

The First-Come, First-Served (FCFS) algorithm is the simplest CPU scheduling approach. With this scheme, the process that requests the CPU first is allocated the CPU first. The implementation of the FCFS policy is easily managed with a FIFO queue and is a non-preemptive scheduling algorithm. Jobs are executed in the order of their arrival.

FCFS Advantages and Disadvantages

The advantage of the algorithm is that it is very simple to understand and easy to implement. One of the main disadvantages is that the average waiting time can be considerably long.

FCFS Scheduling Example

Consider the following set of processes that arrive at time 0, with the length of the CPU burst time given in milliseconds:

If the processes arrive in the order P1, P2, P3 and are served in First-Come, First-Served order, we get the result shown in the following Gantt chart. A Gantt chart illustrates a particular schedule, including the start and finish times of each of the participating processes:

| P1        | P2  | P3    |
0           9     12      17

The waiting time of process P1 is 0 milliseconds, for P2 it is 9 milliseconds, and for process P3 the waiting time is 12 milliseconds.

The average waiting time is:

(0 + 9 + 12) / 3 = 7 milliseconds.

The waiting time of the processes and the average waiting time change with the order of arrival of the processes for execution. Thus, the sequence of arrival of the jobs into the system plays an important role in the amount of time the jobs spend waiting for execution.

Memory Fragmentation in Operating Systems

Memory fragmentation occurs when user processes are loaded and unloaded from main memory, and processor blocks are kept in memory. Various spaces are left after loading and swapping processes that other processes cannot use due to their size.

Types of Memory Fragmentation

• Internal Fragmentation: Whenever a memory block is allocated to a process, and the process happens to be smaller than the total amount of requested memory, a free space is ultimately created within this memory block. This unused free space within an allocated block causes internal fragmentation.

• External Fragmentation: This exists when enough total memory space exists to satisfy a request, but it is not contiguous; storage is fragmented into a large number of small, non-adjacent holes.

Semaphore Types for Process Synchronization

Semaphores are synchronization primitives used in operating systems to control access to shared resources and prevent race conditions.

Counting Semaphores

These are integer-value semaphores with an unrestricted value domain. Counting semaphores are used to coordinate resource access, where the semaphore count represents the number of available resources. If resources are added, the semaphore count is automatically incremented, and if resources are removed, the count is decremented. If the initial count is 0, the counting semaphore should be created in the unavailable state. However, if the count is greater than 0, the semaphore is created in the available state, and the number of tokens it has equals its count.

Binary Semaphores

Binary semaphores are similar to counting semaphores but their value is restricted to 0 and 1. The wait operation only works when the semaphore is 1, and the signal operation succeeds when the semaphore is 0. It is sometimes easier to implement binary semaphores than counting semaphores.

Inter-Process Communication (IPC)

Inter-Process Communication (IPC) mechanisms enable processes to communicate and synchronize their actions. A message system allows processes to communicate with each other without resorting to shared variables.

IPC Operations

An IPC facility typically provides two operations:

1. send(message) – message size can be fixed or variable.
2. receive(message)

If processes P and Q wish to communicate, they need to:

1. Establish a communication link between them.
2. Exchange messages via send/receive operations.

Communication Link Implementation

Communication links can be implemented in various ways:

1. Physical: E.g., shared memory, hardware bus.
2. Logical: E.g., logical properties.

Direct Communication

In direct communication, processes must name each other explicitly:

• send(P, message) – send a message to process P.
• receive(Q, message) – receive a message from process Q.

Properties of a direct communication link:

• Links are established automatically.
• A link is associated with exactly one pair of communicating processes.
• Between each pair, there exists exactly one link.
• The link may be unidirectional, but is usually bidirectional.

Indirect Communication (Mailboxes)

In indirect communication, messages are directed to and received from mailboxes (also referred to as ports).

• Each mailbox has a unique ID.
• Processes can communicate only if they share a mailbox.

Properties of an indirect communication link:

• A link is established only if processes share a common mailbox.
• A link may be associated with many processes.
• Each pair of processes may share several communication links.
• A link may be unidirectional or bidirectional.

Mailbox Operations & Primitives

Common operations for mailboxes include:

• Create a new mailbox.
• Send and receive messages through a mailbox.
• Destroy a mailbox.

Primitives are defined as:

send(A, message)    // send a message to mailbox A
receive(A, message) // receive a message from mailbox A

Mailbox Sharing Scenarios

Consider processes P1, P2, and P3 sharing mailbox A. Process P1 sends; P2 and P3 receive. Who gets the message?

Options for handling this scenario:

• Allow a link to be associated with at most two processes.
• Allow only one process at a time to execute a receive operation.
• Allow the system to select arbitrarily the receiver. The sender is notified who the receiver was.

Resource Allocation Graph (RAG)

A Resource Allocation Graph (RAG) is a directed graph used to represent the state of resource allocation in an operating system. It is particularly useful for understanding and detecting deadlocks, especially in systems with single instances of resources.

RAG Components: Nodes

• Processes (P): Represented as circles (e.g., P1, P2).
• Resources (R): Represented as rectangles/boxes (e.g., R1, R2).

RAG Components: Edges

There are two types of edges (arrows):

• Request Edge (P → R): An arrow from a process to a resource indicates that the process is requesting that resource.

  Example: P1 → R2 (Process P1 is requesting Resource R2)

• Assignment Edge (R → P): An arrow from a resource to a process indicates that the resource is allocated to that process.

  Example: R1 → P1 (Resource R1 is allocated to Process P1)

RAG Example & Deadlock Detection

Situation:

• P1 is holding R1 and requesting R2.
• P2 is holding R2 and requesting R1.

RAG Representation (conceptual):

This situation forms a cycle: P1 → R2 → P2 → R1 → P1.

Cycle in RAG

• Single instance of each resource: A cycle in the RAG implies a deadlock.
• Multiple instances of resources: A cycle does not always imply a deadlock; further analysis is needed.

Deadlock Detection Using RAG

The operating system can traverse the graph to look for cycles. If a cycle is detected, and resources are non-shareable (single instance), a deadlock exists.

Page Replacement Algorithms

Page replacement algorithms determine which memory page to replace when a new page needs to be loaded into a full memory frame. They are crucial for efficient memory management in virtual memory systems.

First-In, First-Out (FIFO) Algorithm

FIFO replaces the oldest page in memory — the one that was loaded first. It uses a queue to track the order of page loads.

1. Pages are inserted into memory in the order they are requested.
2. When a new page needs to be loaded and memory is full, the page at the front of the queue is removed (the oldest), and the new page is added to the back.

Example: Assume 3 page frames and page requests: 1, 2, 3, 4

• Load 1, 2, 3 → memory is full.
• Request 4 → remove 1 (oldest), insert 4.
• New memory: 2, 3, 4.

Least Recently Used (LRU) Algorithm

LRU replaces the page that hasn’t been used for the longest time. This algorithm is based on the idea that pages used recently will likely be used again soon.

1. Keep track of page access history.
2. When a page must be replaced, evict the least recently accessed one.

Example: Assume 3 page frames and page requests: 1, 2, 3, 2, 4

• Load 1, 2, 3 → all pages are in memory.
• Access 2 → mark 2 as recently used.
• Request 4 → remove 1 (least recently used), insert 4.
• New memory: 2, 3, 4.

Pros of LRU:

• Generally better performance than FIFO.
• Reflects real-world usage more accurately.

Cons of LRU:

• More complex to implement.
• Requires tracking access history (using stacks, timestamps, or counters).

Critical Section Problem & Solutions

A critical section is a block of code in a process where shared resources are accessed. Only one process should execute in the critical section at a time to prevent issues like data corruption, race conditions, and inconsistent states.

Conditions for Critical Section Solutions

To solve the critical section problem, any synchronization mechanism must meet these three conditions:

Typical Process Structure

Each process typically follows this structure:

do {
  // Entry Section: Code to request access
  // Critical Section: Access shared resources
  // Exit Section: Release access
  // Remainder Section: Other code
} while (true);