Process Fundamentals and Multitasking

Multiprogramming and Process Concurrency

Multiprogramming enables multiple programs to reside in memory and execute simultaneously, thereby improving CPU utilization and overall system efficiency. This is achieved by logically abstracting independent program counters for each program, allowing them to execute in a concurrent, interleaved manner. A concurrent environment exists when, over a given time interval, two or more programs on a single processor are in a state of having begun execution but not yet finished, with their execution order not predetermined. Programs executed in such an environment are termed concurrent programs.

Process Definition and Attributes

A process is defined as an instance of a program in execution, specifically an active entity comprising a program, its associated data, and execution context operating on a dataset. It serves as the fundamental unit for resource allocation and scheduling by the operating system.

Key attributes of a process include:

• Dynamism: Processes can be dynamically created, executed, and terminated.
• Concurrency: Multiple processes can execute simultaneously within the system.
• Independence: Each process operates as an independent entity and is the primary unit for acquiring operating system resources.
• Asynchrony: Processes execute independently and progress at unpredictable rates.
• Structure: A process is composed of its executable code (text section), associated data, and a Process Control Block (PCB).

Process Control Block (PCB)

The Process Control Block is a kernel data structure containing all information necessary to describe and control a process. It is the sole mechanism by which the operating system perceives a process's existence, establishing a one-to-one correspondence. The collection of all PCBs is known as the process table.

Primary components stored within a PCB are:

1. Process Identification: Unique Process ID (PID), user ID, and process group relations.
2. Process State Information: Current state (e.g., running, ready, blocked), priority, and scheduling parameters.
3. Process Control Information: Pointers for process queues, inter-process communication structures, and program entry points.
4. Memory Management Pointers: Details of the allocated address space, page table pointers, and memory usage statistics.
5. Accounting Information: CPU time used, time limits, and other resource usage data.
6. CPU State (Context): Saved register contents (program counter, stack pointer, status word, general-purpose registers) when the process is not actively executing on the CPU.

Process Lifecycle and State Transitions

Processes transition through several distinct states during their lifetime. The three fundamental states are:

• Running: The process's instructions are currently being executed by a CPU core.
• Ready: The process is loaded in memory and prepared to execute but is waiting for a CPU core to become available.
• Blocked/Waiting: The process cannot proceed because its waiting for an external event, such as I/O completion or a signal from another process.

Extended state models incorporate additional states:

• New: The process is being created (PCB allocated, address space initialized).
• Terminated: The process has finished execution but its entry in the process table remains for cleanup (resource deallocation, data collection).
• Suspended: The process's memory image is swapped out to secondary storage to free up main memory. It may be suspended while ready (Suspend Ready) or blocked (Suspend Blocked).

State transitions are managed by the operating system kernel via specific events (e.g., I/O request, scheduler dispatch, timer interrupt).

Process Scheduling Queues

To manage processes in various states, the OS maintains several queues, typically implemented as linked lists of PCBs.

• Ready Queue: Holds all processes in the Ready state, awaiting CPU time.
• Device/Wait Queues: Multiple queues exist for processes blocked on specific I/O devices or events.

Processes move between these queues as their state changes. The OS scheduler selects processes from the Ready Queue to allocate CPU time.

Process Control Operations

Process control involves primitives—indivisible, atomic operations—that facilitate state transitions. Key primitives include:

• create(): Allocates a new PCB, address space, and initializes process state to New/Ready.
• terminate(): Reclaims all resources held by a process and removes its PCB.
• block(): Moves a running process to a blocked state, typically invoked when it must wait for an event.
• wakeup(): Moves a blocked process to the ready state when the awaited event occurs.
• schedule(): Invokes the scheduler to select the next process to run.

UNIX/Linux Examples:

• fork(): Creates a new child process by duplicating the calling parent process, employing Copy-on-Write (COW) for efficiency.
• exec(): Replaces the current process's memory space with a new program.
• wait() & exit(): Used for process synchronization and termination.

Process Context and Address Space

Each process operates within its own virtual address space, isolating it from other processes. This space typically contains:

• Text Segment: The executable code.
• Data Segment: Global and static variables.
• Heap: Dynamically allocated memory during runtime.
• Stack: Used for function calls, local variables, and return addresses.

Although different processes may have identical virtual addresses (e.g., 0x400000), these map to distinct physical memory locations, ensuring isolation.

Context Switching is the mechanism where the CPU state (register values, program counter, etc.) for the currently running process is saved into its PCB, and the saved state of the next process to run is loaded from its PCB into the CPU registers. This operation is essential for multitasking but incurs overhead.

Threads: Lightweight Processes

Motivation for Threads

Threads, or lightweight processes, were introduced to address limitations in process models, particularly for modern applications like web servers. Key motivations are:

• Application Structure: To model naturally concurrent tasks (e.g., handling multiple client requests).
• Reduced Overhead: Threads within the same process share memory and resources, making creation, termination, and switching much faster than processes.
• Improved Performance: On multi-core systems, threads of a single process can execute in parallel on different cores.

Thread Concepts and Implementation

A thread is a basic unit of CPU utilization within a process. Threads belonging to the same process share its code section, data section, and OS resources (like open files), but each thread has its own thread ID, program counter, register set, and stack.

Thread implementation models:

1. User-Level Threads (ULTs): Managed entirely by a thread library in user space (e.g., Pthreads). The kernel is unaware of them. Advantages include fast thread switching and custom scheduling. A major drawback is that if one thread performs a blocking system call, the entire process (and all its threads) blocks, as the kernel schedules processes, not user-level threads.
2. Kernel-Level Threads (KLTs): Threads are directly supported and managed by the operating system kernel. Blocking calls affect only the calling thread. They allow simultaneous scheduling of threads from the same process on multiple CPUs. The downside is that thread operations (create, switch) require system calls, which are slower.
3. Hybrid Models: Combine ULTs and KLTs, allowing multiple user-level threads to be multiplexed onto a smaller or equal number of kernel threads.

Deadlock in Concurrent Systems

Definition and Necessary Conditions

A deadlock is a state where a set of processes are permanently blocked because each is holding a resource and waiting for a resource held by another process in the set. Four conditions must hold simultaneously for a deadlock to occur:

1. Mutual Exclusion: At least one resource must be held in a non-sharable mode.
2. Hold and Wait: A process must be holding at least one resource while waiting for additional resources.
3. No Preemption: Resources cannot be forcibly removed from a process; they must be released voluntarily.
4. Circular Wait: A circular chain of processes exists where each process waits for a resource held by the next process in the chain.

Resource Allocation Graphs (RAG)

A directed graph used to model system state.

• Process Nodes: Represented by circles.
• Resource Nodes: Represented by rectangles, with dots inside representing instances.
• Assignment Edge: From a resource instance to a process.
• Request Edge: From a process to a resource type. A cycle in the graph indicates a possibility of deadlock. If each resource type has only one instance, a cycle is both necessary and sufficient for deadlock.

Deadlock Handling Strategies

1. Prevention: Design the system to ensure at least one of the four necessary conditions can never hold (e.g., requiring processes to request all resources initially to break "Hold and Wait").
2. Avoidance: Dynamically assess if granting a resource request could lead to an unsafe state (a state that might lead to deadlock). The Banker's Algorithm is a classic avoidence algorithm that only grants requests if the resulting state is guaranteed to be safe.
3. Detection & Recovery: Allow the system to enter a deadlocked state, periodically run a detection algorithm to identify it, and then recover by terminating processes or preempting resources.

Monitors for Synchronization

A monitor is a high-level synchronization construct that encapsulates shared data and the procedures that operate on it. The monitor ensures that only one thread can be active within it at any time, providing mutual exclusion automatically. It also provides condition variables (wait, signal) for threads to block and wake up based on specific conditions, simplifying the design of correct concurrent programs compared to using semaphores or locks directly.