Operating System Concepts and Principles

The provided text offers a comprehensive exploration of operating system fundamentals, particularly focusing on process management and memory management. It differentiates between programs and processes, explaining how multiprogramming enhances CPU utilization through preemptive and non-preemptive scheduling. The text details process states and operations, along with an in-depth examination of synchronization mechanisms like lock variables, Peterson’s solution, and semaphores, addressing critical section problems such as mutual exclusion, progress, and bounded waiting. Furthermore, it thoroughly explains paging as a non-continuous memory allocation technique, including multi-level paging and various page replacement algorithms like FIFO, optimal, and LRU, while also introducing the concept of threads as lightweight processes that facilitate resource sharing and parallelism in multicore architectures.

Program vs. Process: Computing’s Core Distinction

A program and a process are distinct concepts in computing, though closely related. Understanding their differences is fundamental to grasping how an operating system manages computational tasks.

Here’s a breakdown of their characteristics and distinctions:

Program:
A program is essentially a passive entity. It represents code written in a high-level language that has been compiled into an executable form, such as a .exe file consisting of a list of instructions.
A program resides on the hard disk (secondary storage) and is considered “dead” or “as good as dead” because it does not actively use computer resources.
Think of a program as the “body” without a “soul” – it exists but is not alive or active.
Process:
A process is an active entity; it is a program in execution. It is the “instance of a program”.
When an executable file (program) is loaded from the hard disk into the main memory (RAM) for execution, it becomes a process.
A process is “alive” and actively uses computer resources.
The CPU cannot execute a program directly from the hard disk because hard disks are slow; it requires the program to be loaded into the faster main memory first. This is a “Golden Rule”: any program that has to be executed must be stored in the main memory.
The operating system loads the executable file into main memory, and then the CPU performs the sequential execution of its instructions.
A process is also referred to as the “locus of control” for the operating system. Similar to how people are the locus of control for a government, the process is the OS’s control point within the computer. It’s described as the “soul” in the “body” of a program.

In summary, the key difference lies in their state and location:

Program = Code in Hard Disk
Process = Program in Execution (in Main Memory)

This distinction is crucial for memory management and scheduling, as the operating system interacts with processes, not static programs, to manage tasks and resources.

Multiprogramming Operating Systems: Core Concepts and Benefits

Multiprogramming Operating Systems are fundamental to how modern computers manage and execute tasks. They represent a significant advancement over earlier, simpler operating systems by allowing multiple programs to reside in memory and contend for CPU access.

Definition and Core Concept

A multiprogramming operating system is one in which the operating system has the ability to load multiple programs from the hard disk into the main memory (RAM). Unlike a uniprogramming operating system, which can hold only a single program in memory at a time, multiprogramming allows several ready-to-run programs to be present in the main memory simultaneously.

The key distinction is that while multiple programs are loaded and available, the CPU can only execute or work upon a single program at a time, even in multiprocessor systems. The operating system rapidly switches the CPU among these loaded programs, giving the impression of multiplexing or concurrent execution.

Objectives and Benefits

The primary objective of a multiprogramming operating system is to maximize CPU utilization, efficiency, and throughput. This is achieved by addressing the major drawback of uniprogramming operating systems: CPU idleness.

In a uniprogramming system, if the single loaded program requires I/O services (e.g., waiting for user input or disk access), the CPU becomes idle, leading to less efficiency and throughput. Multiprogramming solves this by ensuring that if one program goes to I/O services, there are other ready-to-run programs available for execution, preventing the CPU from becoming idle. This decreases CPU idleness and significantly increases CPU utilization, efficiency, and throughput.

Relationship to Other Concepts

Program vs. Process: A program is passive code residing on the hard disk. When a program (executable file) is loaded from the hard disk into main memory for execution, it becomes an active entity called a process. Multiprogramming involves loading multiple programs into memory, which then become processes.
Memory Management: For a program to be executed, it must be stored in the main memory – this is known as the “Golden Rule” and the “stored program concept”. The operating system loads these executable files into the main memory. The capacity of the operating system to manage multiple ready-to-run programs in main memory is often referred to as the degree of multiprogramming. The long-term scheduler is responsible for bringing new processes from the job queue (disk) to the ready queue (main memory), thereby controlling the degree of multiprogramming.
CPU Scheduling: Once multiple processes are in main memory (in the ready state), the operating system employs CPU scheduling algorithms to decide which process gets CPU time. The process state transition diagram, which includes a “ready state,” is indicative of a multiprogramming operating system.
Multitasking: The terms “multiprogramming” and “multitasking” are often used interchangeably, with the Unix family typically referring to “programs” and the Windows family to “tasks”. A multitasking operating system is essentially a preemptive multiprogramming operating system.

Types of Multiprogramming

Multiprogramming can be categorized into two types:

Non-Preemptive Multiprogramming: In this type, a program voluntarily releases the CPU, typically when its instructions are complete, or it needs I/O services, or a system call occurs. An example of a uniprogramming system (which is implicitly non-preemptive as there’s no other program to preempt) is MS-DOS.
Preemptive Multiprogramming: This involves the forceful deallocation of a program from the CPU by the operating system, often based on priority or time slices. Modern operating systems like Windows, Linux, Unix, and Mac are preemptive operating systems, as preemption improves responsiveness.

Drawbacks of Multiprogramming

While highly beneficial, multiprogramming operating systems, especially non-preemptive ones, can have drawbacks:

Starvation or Indefinite Waiting: Longer programs or those with lower priority might suffer from indefinite waiting if higher priority or shorter jobs continuously arrive and take CPU time.
Lack of Interactiveness and Responsiveness: In non-preemptive systems, a single long-running program can make the system feel unresponsive. Preemptive multiprogramming (multitasking) aims to solve this by ensuring all programs get a chance to run.

Architectural Requirements

Implementing a multiprogramming operating system requires specific hardware capabilities:

DMA Compatible Secondary Storage Devices: Hard disks and other I/O devices must be efficient in transferring data between themselves and main memory using Direct Memory Access (DMA).
Memory System Supporting Address Translation: The system needs a Memory Management Unit (MMU) to translate logical addresses (generated by programs) into physical addresses (actual memory locations). This is crucial for security, preventing programs from directly accessing or corrupting each other’s memory space or the operating system’s memory.
CPU Supporting Dual Mode Operation: The CPU must operate in at least two modes: user mode (non-privileged, for user applications) and kernel mode (privileged, for operating system routines and direct hardware access). This protects the operating system from buggy or malicious user programs.

In essence, multiprogramming is the foundation for modern operating systems, allowing efficient use of the CPU by keeping it busy with multiple active processes, despite inherent challenges like resource management, scheduling, and ensuring fairness.

Operating System Process States Explained

In an operating system, a process is a program in execution. During its lifetime, a process undergoes several phases, moving through various states from its inception to its completion. This progression is represented through a process state transition diagram.

Initially, a process typically passes through five fundamental states:

New State
Ready State
Running State
Blocked/Wait State
Terminate State

As operating systems evolved, two additional states were introduced to manage memory more efficiently:

Suspend Block State
Suspend Ready State

Let’s discuss each state and the transitions between them in detail:

Core Five Process States

New State:

This is the initial state where a process is created.
Resource allocation for the process happens in this state.
Processes in the new state are programs (executable files) residing on the hard disk, ready to be loaded into main memory. The job queue corresponds to the new state.

Ready State:

After creation and resource allocation, the process is moved to the ready state.
Processes in this state are ready to run on the CPU.
Multiple processes can reside in the ready state, waiting for CPU access. The existence of a “ready state” implies a multiprogramming operating system. The ready queue holds the Process Control Blocks (PCBs) of these ready processes.
From the ready state, the long-term scheduler brings processes from the job queue (disk) to the ready queue (main memory), controlling the degree of multiprogramming.

Running State:

From the ready state, the operating system chooses one process (via scheduling) and gives the CPU the right to execute its instructions (via dispatching).
At any given time, only one program will run on a single CPU, even in multiprocessor systems, one CPU works on one program.
While a process is said to “move to CPU,” it actually remains in main memory; the CPU gains control to execute its instructions.
The process will continue executing instructions on the CPU until it completes, requires I/O, or is preempted.

Blocked/Wait State:

A process transitions from the running state to the blocked state if it needs to perform an I/O operation (e.g., reading from a device, waiting for user input, or disk access) or needs to execute a system call that requires the OS’s service.
When a process enters the blocked state, the operating system takes back the CPU’s rights for execution, and the process waits in main memory for the I/O or system call to complete.
The operating system performs the actual I/O operation on behalf of the process.
Once the I/O or system call is completed, the process is moved back to the ready state to await its next turn on the CPU. The blocked queue (or device queue) holds PCBs of processes waiting for specific I/O devices.

Terminate State:

A process moves from the running state to the terminate state when all its instructions have been executed.
In this state, resource deallocation happens, meaning all resources previously given to the process are taken back by the OS.
A process must be in the running state to terminate; there is only one path to termination, and that comes from the running state.

Location of Processes in States

Processes in the ready, running, and blocked/wait states are all present in the main memory (RAM).
In the new state, a program is on the hard disk, entering main memory.
In the terminate state, it is leaving main memory.

Multiprogramming and Preemption

The process state transition diagram, particularly the presence of a “ready state,” indicates a multiprogramming operating system.
Non-preemptive multiprogramming: A process voluntarily releases the CPU, typically upon completion of instructions, needing I/O services, or a system call.
Preemptive multiprogramming (Multitasking): The operating system can forcefully deallocate a process from the CPU, often based on priority or time slices, and put it back into the ready state. Modern OS like Windows and Linux are preemptive.

Capacity of States

There can be multiple processes (theoretically infinite) in the ready and blocked states, limited only by the capacity of RAM and the OS’s ability to manage them.
At most one process can be in the running state per CPU. If a system has ‘n’ CPUs (multiprocessor system), then ‘n’ processes can be in the running state simultaneously.

Suspension and Resumption (Additional States)

The operating system may need to move processes from main memory to hard disk to improve performance or efficiency, especially when the main memory becomes overcrowded (high degree of multiprogramming). This is called suspension. Bringing a process back from disk to memory is called resumption. The medium-term scheduler handles process suspension and resumption.

Suspend Block State:
A process in the blocked state (waiting for I/O) can be moved from main memory to the hard disk to free up main memory for more active processes.
This transition occurs when the OS needs to manage resources or pause processes, for instance, if the user switches applications.
While in this state, the process is still waiting for its I/O operation to complete, but it is swept out of main memory and placed onto disk storage.
Suspend Ready State:
Once the I/O operation a suspended-blocked process was waiting for is complete, the process transitions to the suspended ready state.
In this state, the process is logically ready to run, but it is still residing on the disk.
From suspend ready, a process needs to be brought back to main memory (a process known as swapping or loading) before it can move to the ready state and be scheduled for CPU execution.

Desirable State for Suspension: The ready state is the most desirable state for suspension because the process is neither actively running nor performing I/O, making it less disruptive to move. However, processes can also be suspended from the running or blocked states, though these are generally less desirable and often indicated by dotted lines in transition diagrams.

Queuing Diagrams

Process states are closely related to scheduling queues. The state queuing diagram illustrates how processes move between these queues, managed by various schedulers:

Job Queue: Corresponds to the New state, holding programs ready to be loaded into memory.
Ready Queue: Corresponds to the Ready state, containing PCBs of processes ready for CPU execution.
Block Queue (Device Queue): Corresponds to the Blocked state, containing PCBs of processes waiting for specific I/O services.
Suspend Queue: Corresponds to the Suspend Block and Suspend Ready states, holding processes moved from memory to disk.

Understanding process states and their transitions is fundamental to comprehending how operating systems manage computation, resources, and ensure efficient CPU utilization.

Page Replacement Algorithms in Operating Systems

In an operating system, page replacement is a crucial aspect of virtual memory management, specifically within the context of demand paging. The need for page replacement arises when a running process attempts to access a page that is not currently present in the main memory (RAM) but resides on the hard disk. This event is known as a page fault. Since main memory has a limited capacity compared to the larger virtual address space (which is typically mapped onto the disk), not all pages of a program can reside in RAM simultaneously. When a page fault occurs and all available frames (equal-sized units of physical memory that hold pages) are already occupied, the operating system must choose a page currently in memory to evict (or replace) to make space for the newly demanded page.

The selection of which page to evict is determined by a page replacement algorithm. These algorithms aim to minimize the number of future page faults, thereby improving system performance.

A fundamental concept in understanding page replacement algorithms is the reference string. A reference string is a sequence representing the “set of successfully unique Pages referred in the given list of virtual addresses”. The term “successfully unique” is important because if a page is accessed repeatedly after being loaded into memory, it will not trigger a page fault each time. A reference string has a length (total references) and a number of unique pages, which reflects the process’s size in terms of pages.

Page Fault Handling Process

When a page fault occurs:

The currently running process is blocked because the required page needs to be read from the disk, which is an I/O operation.
The operating system’s Virtual Memory Manager takes control of the CPU, requests the page from the Disk Manager, and the page is copied from the hard disk to main memory.
If an empty frame is available in main memory, the new page is simply placed there.
If no empty frames are available, a victim page must be selected from the existing pages in memory using a page replacement algorithm. This victim page is swapped out (moved back to disk, especially if it’s been modified, which is known as a “dirty” page), and the newly demanded page is swapped in.
The page table is updated to reflect the new page-to-frame mapping.
The blocked process is moved back to the ready state to continue execution.

Page Replacement Algorithms

The sources discuss several page replacement algorithms:

1. FIFO (First-In, First-Out)
Mechanism: This algorithm replaces the page that has been in memory for the longest time. It selects the page that was brought into memory first as the victim, based on the principle of “the first to come will be the first to go out”.
Characteristic: FIFO algorithms can suffer from Bélády’s Anomaly.
2. Optimal Page Replacement
Mechanism: This algorithm replaces the page that will not be used for the longest duration of time in the future.
Characteristic: It is considered the optimal algorithm as it produces the minimum number of page faults. However, it is not implementable in real systems because it requires knowledge of future page accesses, which is generally impossible to predict. It serves as a benchmark to evaluate the performance of other algorithms.
3. LRU (Least Recently Used)
Mechanism: This algorithm replaces the page that has not been used for the longest duration of time in the past. It’s essentially the inverse logic of the Optimal algorithm, looking backward in time instead of forward.
Characteristic: LRU generally performs well and does not suffer from Bélády’s Anomaly. It is often implemented using a stack to keep track of page recency. Many operating systems implement LRU or its variations due to its good performance.
4. MRU (Most Recently Used)
Mechanism: This algorithm replaces the page that has just been used. It’s the opposite of LRU.
5. Counting-Based Algorithms
These algorithms track the frequency of page accesses:
LFU (Least Frequently Used): Replaces the page with the least count of references. When a page is swapped in, its count is set to one.
MFU (Most Frequently Used): Replaces the page with the highest count of references.

LRU Approximations

Because truly implementing LRU (e.g., with a perfect stack or by tracking exact times) can be complex or costly, operating systems often use approximations:

1. Reference Bit Algorithm
Mechanism: Each page in the page table is associated with a reference bit. If a page is referred to during the current epoch (a time quantum), its reference bit is set to 1; otherwise, it remains 0. The algorithm scans the page table and victimizes the first page it finds with a reference bit of 0.
Characteristic: This approximation fails if all pages have their reference bits set to 1 (meaning all pages have been referred in the current epoch).
2. Additional Reference Bit Algorithm
Mechanism: This is an enhancement to the reference bit, where more than one reference bit (e.g., eight) is associated with each page to store a history of past epochs. When an epoch completes, the bits are left-shifted, and the newest bit is set to 0. This allows looking further back in time to find a less recently used page.
3. Second Chance / Clock Algorithm
Mechanism: This algorithm uses a circular queue (like a clock) and combines the time of loading with the reference bit. When a page is to be replaced, the algorithm inspects pages in FIFO order. If a page’s reference bit is 0, it is chosen as the victim. If its reference bit is 1, it is given a “second chance” by setting its bit to 0 and moving to the next page in the queue. If all pages have a 1 reference bit, the algorithm will eventually cycle back to pages that were given a second chance and now have a 0 bit.
Characteristic: When all reference bits are 1, it reverts to FIFO-like behavior and can therefore suffer from Bélády’s Anomaly.
4. Enhanced Second Chance / Not Recently Used (NRU)
Mechanism: This algorithm prioritizes pages based on both their reference bit (R) and modified/dirty bit (M). It uses a priority order to select a victim, from highest priority (best victim) to lowest priority (worst victim):
00: Page not referred, clean (highest priority to evict)
01: Page not referred, modified
10: Page referred, clean
11: Page referred, modified (lowest priority to evict as it’s active and needs saving).

Bélády’s Anomaly

Bélády’s Anomaly (or anomaly) is a counter-intuitive phenomenon where, for certain page replacement algorithms, increasing the number of allocated page frames in main memory can sometimes lead to an increase in the number of page faults. This goes against the natural expectation that more memory should lead to fewer page faults. The anomaly primarily occurs with FIFO and FIFO-based algorithms. It is attributed to the “stack property of replacement”. Algorithms like Optimal and LRU generally do not suffer from this anomaly.

Relationship to Threshing

Page replacement policies are closely related to the problem of threshing. Threshing is a state of excessive paging activity, characterized by a very high page fault rate. When the operating system increases the degree of multiprogramming (number of processes in memory) beyond a certain limit in a system with limited RAM, each process receives fewer frames. This scarcity of frames leads to frequent page faults, causing processes to spend most of their time blocked, waiting for pages to be swapped in from disk. This results in low CPU utilization and a significant degradation of system performance. Effective page replacement algorithms, by minimizing page faults, help in preventing or mitigating threshing.

The Fork System Call: Process Creation and Management

The fork system call is a fundamental concept in operating systems, primarily used for process creation. When fork is executed, it results in the creation of a child process. This child process is an exact replica of the parent process, meaning all the code and resources allocated to the parent are duplicated for the child.

Here’s a detailed discussion of the fork system call based on the provided sources:

Definition and Basic Functionality:
The execution of the fork system call leads to the creation of child processes.
It is a special type of function known as a system call, which is invoked to request services from the operating system kernel.
fork is defined and implemented within the OS kernel, signifying it as an operating system routine.
Mode Shifting for Execution:
Since fork is an OS kernel routine, it cannot be directly executed by user mode programs.
To execute fork (or any kernel-level service), a mode shift is required from user mode to kernel mode. This is because kernel-level programs are privileged and run atomically (non-preemptively), unlike user applications.
When an OS routine like fork is compiled, it generates a Supervisory Call (SVC), which, at runtime, produces a software interrupt (or trap).
This interrupt triggers an Interrupt Service Routine (ISR). The ISR’s primary tasks are to change the mode bit in the Processor Status Word (PSW) register from 1 (user mode) to 0 (kernel mode) and then find the address of the fork routine in the OS’s dispatch table.
After the fork instructions are executed atomically in kernel mode, the mode bit is reset from 0 to 1 (kernel to user mode) for security purposes, returning control to the user application.
Child Process Characteristics and Execution Flow:
The code of the child process is an exact replica of the parent process.
All the resources that were allocated to the parent process are also duplicated for the child.
Execution in the child process starts from the next statement immediately after the fork call in the code, continuing until the end of the program. Although the lines of code before the fork are copied into the child, they are not re-executed by the child.
Child and parent processes are independent; there is no master-slave relationship between them.
A child of a child is also considered a child to the original parent.
Memory and Address Space Relationship:
While the child and parent processes have the same virtual address space (as their code is identical), their physical addresses will be different because they are two distinct processes residing in memory. If you print the virtual address of a variable in both parent and child, they will appear the same.
fork inherently leads to redundancy as extra copies of code and data are created in memory.
Return Value of fork:
The fork system call can return three types of values:
Positive Value (typically the child’s Process ID): This value is returned to the parent process.
Zero (0): This value is returned to the child process.
Negative Value: This indicates that the execution of fork was a failure (e.g., due to insufficient resources).
Operating systems use this return value to distinguish between the parent and child processes and execute specific code blocks accordingly (e.g., using if (fork() == 0) for child-specific code and else for parent-specific code).
Impact on Number of Processes and Output:
If a program contains n fork calls, it will result in 2^n total processes (including the original parent process).
Consequently, if a printf statement appears after the fork calls, it will be executed 2^n times (assuming no conditional blocks restrict execution to specific processes).
The number of child processes specifically created by n fork calls is 2^n – 1 (subtracting the original parent).
Examples provided in the sources illustrate this:
One fork call results in two “hello” prints.
Three fork calls result in eight “hello” prints (2^3 = 8).
Interaction with C Constructs (Loops, Conditionals):
fork can be used within loops. If a fork is inside a loop that runs n times, and the fork is executed in each iteration, it can lead to a significant number of child processes (2^n).
Conditional statements (if/else) are often used with the fork return value to specify code that should only be executed by the parent or the child. Code outside these conditional blocks is executed by both parent and child processes.

In summary, the fork system call is a powerful mechanism for concurrency in operating systems, allowing a process to duplicate itself. Its behavior is intricate, involving kernel-level operations, precise control over execution flow, and distinct handling of parent and child processes through its return value.

Operating Systems Course for Beginners

By Amjad Izhar
Contact: amjad.izhar@gmail.com
https://amjadizhar.blog

Affiliate Disclosure: This blog may contain affiliate links, which means I may earn a small commission if you click on the link and make a purchase. This comes at no additional cost to you. I only recommend products or services that I believe will add value to my readers. Your support helps keep this blog running and allows me to continue providing you with quality content. Thank you for your support!

Operating System Concepts and Principles

Program vs. Process: Computing’s Core Distinction