Process Management

In an operating system, a process is an instance of a program in execution. It's more than just the program code; it includes the current activity, represented by the program counter, processor registers, the process stack (containing temporary data like function parameters, return addresses, and local variables), and a data section (containing global variables). As a program executes, it becomes a process. A process is a dynamic entity, while a program is a static one.

The operating system is responsible for managing these processes. This management involves several key activities, including creating and deleting processes, suspending and resuming processes, and providing mechanisms for processes to communicate and synchronize with each other. Process management is a core function of the operating system, ensuring efficient utilization of the CPU and other system resources.

Process States

A process can be in one of several states during its lifetime. These states represent the current status of the process within the system. The common process states are:

• New: The process is being created.
• Running: The process is currently executing instructions on the CPU.
• Waiting: The process is waiting for some event to occur, such as the completion of an I/O operation or the reception of a signal.
• Ready: The process is waiting to be assigned to the CPU for execution. It is ready to run but is currently in the queue.
• Terminated: The process has finished execution.

Process Control Block (PCB)

Each process is represented in the operating system by a Process Control Block (PCB), also known as a task control block. The PCB is a data structure that stores all the essential information about a process. Key information stored in a PCB includes:

• Process State: The current state of the process (new, running, waiting, ready, terminated).
• Process ID (PID): A unique identifier assigned to each process.
• Program Counter (PC): Indicates the address of the next instruction to be executed.
• CPU Registers: The contents of the CPU registers for the process when it was last switched out.
• CPU-Scheduling Information: Process priority, pointers to scheduling queues, and other scheduling parameters.
• Memory-Management Information: Pointers to base-register and limit-register values or page tables.
• Accounting Information: CPU time used, time limits, execution ID, account numbers, etc.
• I/O Status Information: List of I/O devices allocated to the process, list of open files, etc.

The PCB acts as a ledger for each process, allowing the operating system to keep track of its activities and manage its resources effectively. When the CPU switches from one process to another, it must save the state of the current process in its PCB and load the saved state of the new process from its PCB. This process is called a context switch.

Process Scheduling

Process scheduling is a fundamental operating system function that determines which process in the ready queue will be allocated the CPU next. The goal of process scheduling is to maximize CPU utilization and throughput while minimizing response time, turnaround time, and waiting time. Different scheduling algorithms exist, each with its own strengths and weaknesses, suited for different types of systems (e.g., batch, interactive, real-time).

Scheduling Queues

Operating systems typically use several queues to manage processes:

• Job Queue: Consists of all processes in the system.
• Ready Queue: Consists of all processes that are residing in main memory and are ready or waiting to be executed.
• Device Queues: Consists of processes that are waiting for a particular I/O device.

Processes move between these queues as they transition through different states. For example, a process moves from the ready queue to the running state when it gets the CPU, and from the running state to a device queue when it requests an I/O operation.

Scheduling Criteria

Several criteria are used to evaluate the performance of scheduling algorithms:

• CPU Utilization: Keep the CPU busy most of the time.
• Throughput: Number of processes completed per unit of time.
• Turnaround Time: The interval from the time of submission of a process to its completion.
• Waiting Time: The total time spent by the process in the ready queue.
• Response Time: The time from the submission of a request until the first response is produced.

Common Scheduling Algorithms

Here are some of the most common process scheduling algorithms:

First-Come, First-Served (FCFS)

This is the simplest scheduling algorithm. Processes are executed in the order they arrive in the ready queue. It is a non-preemptive algorithm, meaning once a process starts executing, it runs until it completes or voluntarily releases the CPU.

Example: Processes P1, P2, P3 arrive with burst times 24, 3, and 3 respectively. If they arrive in order P1, P2, P3, the waiting times would be: P1: 0 P2: 24 (waits for P1) P3: 24 + 3 = 27 (waits for P1 and P2) Average waiting time = (0 + 24 + 27) / 3 = 17.

FCFS can lead to the "convoy effect," where a long process at the front of the queue can cause a long wait for all subsequent processes.

Shortest-Job-Next (SJN) / Shortest-Job-First (SJF)

This algorithm selects the process with the smallest next CPU burst time to execute next. SJF can be either preemptive or non-preemptive.

• Non-preemptive SJF: Once a process starts executing, it runs until it completes its CPU burst.
• Preemptive SJF (Shortest-Remaining-Time-First - SRTF): If a new process arrives with a CPU burst length less than the remaining time of the currently executing process, the CPU is preempted.

Example (Non-preemptive SJF): Processes P1, P2, P3 arrive with burst times 6, 8, 7 respectively. If they arrive at the same time, the order would be P1 (6), P3 (7), P2 (8). Waiting times: P1: 0 P3: 6 (waits for P1) P2: 6 + 7 = 13 (waits for P1 and P3) Average waiting time = (0 + 6 + 13) / 3 = 6.33.

The main problem with SJF is predicting the future CPU burst time. It's difficult to know the exact length of the next CPU burst.

Priority Scheduling

In this algorithm, each process is assigned a priority, and the CPU is allocated to the process with the highest priority. Priorities can be assigned either internally or externally.

• Internal priorities: Determined by factors like time limits, memory usage, number of open files, etc.
• External priorities: Based on factors external to the process, such as importance of the user or application.

Priority scheduling can be preemptive or non-preemptive. A major issue with priority scheduling is starvation, where low-priority processes may never get to execute if there is a constant supply of high-priority processes. This can be mitigated using aging, where the priority of a process is increased over time.

Round Robin (RR)

RR is a preemptive scheduling algorithm designed for time-sharing systems. It is similar to FCFS but with preemption based on a time slice, called a quantum. Each process gets the CPU for a small amount of time (quantum). If the process is still running at the end of its quantum, the CPU is preempted, and the process is placed at the end of the ready queue.

The performance of RR depends heavily on the size of the quantum.

• If the quantum is very large, RR behaves like FCFS.
• If the quantum is very small, RR can lead to a high number of context switches, increasing overhead.

Example: Processes P1, P2, P3 arrive with burst times 24, 3, 3. Quantum = 4. 1. P1 runs for 4ms. Remaining time: 20. Ready queue: P2, P3, P1. 2. P2 runs for 3ms. Completes. Ready queue: P3, P1. 3. P3 runs for 3ms. Completes. Ready queue: P1. 4. P1 runs for 4ms. Remaining time: 16. Ready queue: P1. 5. P1 runs for 4ms. Remaining time: 12. Ready queue: P1. 6. P1 runs for 4ms. Remaining time: 8. Ready queue: P1. 7. P1 runs for 4ms. Remaining time: 4. Ready queue: P1. 8. P1 runs for 4ms. Completes. Waiting times: P1: (24-4) + (20-4) + (16-4) + (12-4) + (8-4) = 20 + 16 + 12 + 8 + 4 = 60ms (Total time spent waiting in ready queue) P2: 4ms P3: 4 + 3 = 7ms Average waiting time = (60 + 4 + 7) / 3 = 71 / 3 = 23.67ms.

Multilevel Queue Scheduling

This algorithm partitions the ready queue into several separate queues, each with its own scheduling algorithm. For example, foreground (interactive) processes might use RR, while background (batch) processes might use FCFS. Processes are permanently assigned to a queue, often based on memory, process type, or priority. Scheduling between queues is also needed, typically using fixed-priority preemptive scheduling.

Multilevel Feedback Queue Scheduling

This is a more general version of multilevel queue scheduling. It allows processes to move between queues. If a process uses too much CPU time, it is moved to a lower-priority queue. Conversely, if a process waits too long in a lower-priority queue, it might be moved to a higher-priority queue. This prevents starvation and allows the system to adapt to the process's behavior.

Inter-Process Communication (IPC)

Processes often need to communicate with each other to share information or coordinate their activities. Inter-Process Communication (IPC) refers to the mechanisms provided by the operating system that allow processes to exchange data and signals. This is crucial for building complex applications where different parts of the application might run as separate processes.

Common IPC Mechanisms

Operating systems provide several ways for processes to communicate:

Shared Memory

In this approach, a region of memory is designated as shared between processes. One process can write data into the shared memory, and another process can read from it. This is generally the fastest IPC method because data does not need to be copied between processes. However, it requires careful synchronization to avoid race conditions where multiple processes try to access and modify the shared data simultaneously.

Example: A producer process generates data and writes it into a shared buffer. A consumer process reads data from the same shared buffer. Both processes need to be synchronized to ensure the producer doesn't write to a full buffer and the consumer doesn't read from an empty buffer.

Message Passing

With message passing, processes communicate by sending and receiving messages to each other. The operating system provides system calls for sending and receiving messages. Message passing can be implemented in two ways:

• Direct Communication: Processes must explicitly name the recipient or sender of the message. Syntax: send(P, message), receive(Q, message).
• Indirect Communication: Messages are sent to and received from mailboxes (or ports). A mailbox can be associated with one or more processes. Syntax: send(A, message), receive(A, message), where A is a mailbox.

Message passing is generally slower than shared memory due to the overhead of copying messages and kernel involvement. However, it simplifies synchronization because the OS can manage the communication flow.

Client-Server Communication

A common pattern in distributed systems and even within a single system is the client-server model. In this model:

• Server Process: Provides a service and waits for requests from clients.
• Client Process: Requests a service from a server.

Communication between clients and servers often uses IPC mechanisms like sockets, remote procedure calls (RPCs), or message queues.

• Sockets: An endpoint for communication. A server binds a socket to a port number, and clients connect to that socket. This is a fundamental mechanism for network communication.
• Remote Procedure Call (RPC): Allows a process to call a procedure (function) in another process on a different machine as if it were a local call. The RPC mechanism handles the message passing and data marshalling/unmarshalling behind the scenes.

Example: A web browser (client) requests a web page from a web server (server). The browser sends an HTTP request (message) to the server's IP address and port. The server processes the request and sends back the web page data (response).

Process Synchronization

Process synchronization is the coordination of concurrent processes that share data or resources. When multiple processes access shared data concurrently, it can lead to inconsistent states and incorrect results due to race conditions. Synchronization mechanisms are needed to ensure that concurrent access to shared resources happens in a controlled and orderly manner.

Race Conditions

A race condition occurs when the outcome of a computation depends on the particular order in which concurrent processes access and manipulate shared data. If not properly managed, the interleaved execution of instructions can lead to unexpected and incorrect results.

Example: The Ticket Counter Problem Imagine two processes, P1 and P2, both trying to buy a ticket from a counter with only one ticket available. Let's say the current number of tickets is 1. The logic might be: 1. Read the current number of tickets (e.g., 1). 2. Decrement the number of tickets (e.g., 1 - 1 = 0). 3. Write the new number of tickets back (e.g., 0). 4. Print "Ticket purchased." If P1 reads the ticket count (1), then P2 reads the ticket count (1) before P1 writes back, both will think there's a ticket available. P1 decrements to 0 and prints "Ticket purchased." Then P2 decrements to -1 and prints "Ticket purchased." This results in two tickets being sold when only one was available.

Critical Section Problem

The critical section problem is a classic synchronization problem. A critical section is a segment of code within a process where the process accesses shared resources. The problem is to design a protocol such that if one process is executing in its critical section, no other process can execute in their critical section.

To solve the critical section problem, any solution must satisfy three conditions:

1. Mutual Exclusion: If process Pi is in its critical section, then no other process Pj can be in its critical section.
2. Progress: If no process is executing in its critical section, and there are processes that wish to enter their critical sections, then only those processes that are not executing in their remainder sections can participate in the decision of which will enter its critical section next, and this selection cannot be postponed indefinitely.
3. Bounded Waiting: There is a bound on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted.

Peterson's Solution

Peterson's solution is a software-based algorithm that solves the critical section problem for two processes. It uses two shared variables:

• boolean flag[2]: `flag[i]` is true if process `Pi` intends to enter its critical section.
• int turn: Indicates whose turn it is to enter the critical section.

The structure for process `Pi` (where `i` is 0 or 1, and `j` is the other process) is:

    do {
        flag[i] = true;
        turn = j;
        while (flag[j] && turn == j) {
            // Wait
        }

        // ----- Critical Section -----
        // Access shared data

        flag[i] = false;
        // ----- Remainder Section -----

    } while (true);
    

How it works:

• A process sets its `flag` to `true` to indicate it wants to enter.
• It then sets `turn` to the other process's index, suggesting it's the other process's turn.
• The `while` loop checks two conditions:
  • `flag[j]`: Is the other process also trying to enter?
  • `turn == j`: Is it really the other process's turn?
• If both conditions are true, the current process waits. This ensures that if both processes want to enter, only the one whose turn it is will proceed.
• If only one process wants to enter, its `flag` will be true, but the other's `flag` will be false, so the `while` loop condition is false, and it enters the critical section.
• When a process exits the critical section, it sets its `flag` back to `false`, allowing other processes to enter.

Peterson's solution satisfies mutual exclusion, progress, and bounded waiting. However, it is typically only practical for two processes and relies on the assumption that load and store operations are atomic. Modern hardware often uses atomic instructions for better performance and reliability.

Semaphores

Semaphores are synchronization primitives that provide a more general and powerful mechanism for controlling access to shared resources and coordinating processes. A semaphore is essentially an integer variable that, apart from initialization, is accessed only through two standard atomic operations:

• wait() (or P()): Decrements the semaphore value. If the value becomes negative, the process executing `wait()` is blocked until the semaphore value is positive again.
• signal() (or V()): Increments the semaphore value. If there are processes blocked on this semaphore, one of them is unblocked.

Both `wait()` and `signal()` operations must be performed atomically, meaning they cannot be interrupted.

Types of Semaphores

1. Binary Semaphore: A semaphore that takes only values 0 and 1. It can be used to implement mutual exclusion, similar to locks. If the value is 1, a process can enter the critical section. If it's 0, the process must wait.
2. Counting Semaphore: A semaphore that can take any integer value. It is useful for managing a resource with a finite number of instances. For example, if there are `N` identical units of a resource, a counting semaphore initialized to `N` can be used. Processes decrement the semaphore before using a resource and increment it after they are done. If the semaphore value drops to 0, it means all resources are in use, and subsequent processes must wait.

Using Semaphores for Synchronization

1. Mutual Exclusion: To protect a critical section, a binary semaphore (initialized to 1) can be used.

    // Initialize semaphore to 1
    semaphore mutex = 1;

    // Process Pi
    do {
        wait(mutex); // Acquire lock

        // ----- Critical Section -----
        // Access shared data

        signal(mutex); // Release lock
        // ----- Remainder Section -----

    } while (true);
    

2. Signaling (Producer-Consumer Problem): Consider a producer-consumer problem where a producer generates items and a consumer consumes them from a shared buffer. We need to ensure the producer doesn't write to a full buffer and the consumer doesn't read from an empty buffer.

We can use three semaphores:

• mutex (binary semaphore, initialized to 1): For mutual exclusion when accessing the buffer.
• empty (counting semaphore, initialized to `N`, where `N` is the buffer size): Counts the number of empty slots in the buffer.
• full (counting semaphore, initialized to 0): Counts the number of full slots in the buffer.

Producer Process:

    do {
        // Produce an item

        wait(empty);  // Decrement empty count (wait if buffer is full)
        wait(mutex);  // Acquire lock for buffer access

        // ----- Add item to buffer -----

        signal(mutex); // Release lock
        signal(full);  // Increment full count (signal that an item is available)

    } while (true);
    

Consumer Process:

    do {
        wait(full);   // Decrement full count (wait if buffer is empty)
        wait(mutex);  // Acquire lock for buffer access

        // ----- Remove item from buffer -----

        signal(mutex); // Release lock
        signal(empty);  // Increment empty count (signal that a slot is now empty)

        // Consume the item
    } while (true);
    

Monitors

Monitors are a higher-level synchronization construct than semaphores. A monitor is a programming language construct that encapsulates shared data and the procedures that operate on that data, along with synchronization mechanisms. It ensures that only one process can be active within the monitor at any given time, providing implicit mutual exclusion.

Monitors also include condition variables, which allow processes to wait for specific conditions to become true within the monitor. The two main operations on condition variables are:

• condition.wait(): Blocks the calling process until another process calls condition.signal().
• condition.signal(): Resumes one process (if any) that is waiting on the condition.

Monitors simplify synchronization by making mutual exclusion implicit and providing structured ways to handle complex waiting conditions.