Operating System Fundamentals: Processes, Memory, Concurrency, Scheduling
Operating System Processes
Process View: The Illusion of Exclusivity
A process is essentially a running instance of a program. One of the key abstractions that the Operating System (OS) provides is the illusion that each process has exclusive access to the CPU and memory. However, in reality, the CPU and memory are shared among multiple processes.
How the Illusion is Created
- CPU Time Sharing: The OS rapidly switches between processes (context switching) so that it seems each process has its own CPU.
- Memory Virtualization: Each process gets its own virtual address space, making it appear that the entire memory is available to that process alone.
Process Memory Layout Explained
The view of memory refers to how a process perceives its allocated memory, which is logically divided into several segments:
Memory Layout Segments
- Text (Code) Segment:
- Contains the executable code of the program.
- Usually marked as read-only to prevent accidental modification.
- Data Segment:
- Contains global and static variables.
- Subdivided into:
- Initialized Data Segment: Variables that are explicitly initialized.
- Uninitialized Data Segment (BSS): Variables that are declared but not initialized (set to zero by default).
- Heap Segment:
- Used for dynamically allocated memory during runtime (via
malloc()
ornew
). - Grows upwards as more memory is allocated.
- Used for dynamically allocated memory during runtime (via
- Stack Segment:
- Stores function call frames, local variables, and return addresses.
- Grows downwards as more function calls are nested.
- Environment Segment:
- Holds environment variables and program arguments.
- Typically located just below the stack.
Memory Layout Illustration
High Memory | Stack | | ↓ | | Environment | | Heap | | ↑ | | Uninitialized Data| | Initialized Data| | Code | Low Memory
Function Call Operations & Stack Setup
When a function call occurs, several operations take place to manage the stack and registers:
Caller’s Responsibility Before Function Call
- Push Arguments: The caller pushes arguments onto the stack.
- Call Instruction: The address of the next instruction (
%rip
) is pushed onto the stack.
Callee’s Responsibility During Execution
- Save Caller’s Frame Pointer (
%rbp
): The current base pointer is saved to the stack. - Set Up the New Frame Pointer (
%rbp
): The stack pointer (%rsp
) is copied to%rbp
. - Allocate Space for Local Variables: Adjust
%rsp
to reserve space.
Stack Cleanup After Function Execution
- Restore Frame Pointer: The saved
%rbp
is popped back. - Return Instruction: The saved
%rip
(return address) is popped and control is transferred back to the caller.
Key Registers in OS Operations
%rbp
(Base Pointer): Points to the base of the current stack frame.%rsp
(Stack Pointer): Points to the top of the stack.%rip
(Instruction Pointer): Holds the address of the next instruction to execute.
Process Control Block (PCB) Details
A Process Control Block (PCB) is a data structure used by the OS to store information about a process. It contains:
- Process State: Running, waiting, blocked, etc.
- Program Counter: The address of the next instruction.
- CPU Registers: Values of all the registers for the process.
- Memory Management Info: Page tables and segment information.
- Accounting Information: CPU usage, user IDs, etc.
- I/O Status: Open files and I/O devices in use.
The OS maintains the PCB to manage context switching and track processes.
Process Creation & System Calls
Process Creation: Fork and Exec
fork()
: Creates a new process by duplicating the calling process.exec()
: Replaces the current process image with a new program.wait()
: Makes a process wait for its child processes to terminate.
Mode Switching: User to Kernel Mode
- A system call transitions the CPU from user mode to kernel mode to safely execute privileged operations.
System Call vs. Function Call
- A function call is a normal subroutine call within user space.
- A system call involves crossing the user-to-kernel boundary to request OS services.
Common System Calls
open()
: Opens a file.read()
: Reads data from a file.write()
: Writes data to a file.close()
: Closes a file.
Concurrency Fundamentals
Concurrency Basics
Concurrency involves executing multiple processes or threads simultaneously. It helps utilize CPU resources efficiently but also introduces challenges such as race conditions.
Processes vs. Threads
- Processes: Use
fork()
andexec()
to create and execute separate instances. They have independent memory spaces. - Threads: Use threading libraries (e.g., POSIX threads) to create multiple threads within a single process. They share the same memory space.
Race Conditions & Data Races
A race condition occurs when the behavior of software changes due to the unpredictable timing of threads accessing shared resources.
Mutex (Mutual Exclusion)
A mutex ensures that only one thread can access a critical section at a time.
Mutex Operations
- Init: Initialize the mutex.
- Lock: Acquire the mutex (blocking if already held).
- Unlock: Release the mutex.
Implementation Techniques
- Disabling Interrupts: Prevents context switching, but not practical for long operations.
- Spinlocks: Threads busy-wait while attempting to acquire the lock.
- Peterson’s Algorithm: A software-based solution that ensures mutual exclusion between two processes.
Condition Variables
Condition variables enable threads to wait for specific conditions to become true.
Operations
- Wait: Put the calling thread to sleep while releasing the associated mutex.
- Typically implemented using a
while
loop to check the condition.
- Typically implemented using a
- Signal: Wake up one waiting thread.
- Broadcast: Wake up all waiting threads.
Monitor (Concurrency Paradigm)
A Monitor is a high-level concurrency construct that encapsulates data and operations while providing mutual exclusion.
Mike Dahlin’s Coding Standard
- All methods within a monitor are protected by a mutex.
- Never sleep while holding a mutex.
- Use condition variables for waiting and signaling.
Deadlock Explained
A deadlock occurs when two or more processes are permanently blocked because each is holding a resource the other needs.
Four Conditions of Deadlock
- Mutual Exclusion: Only one process can access a resource at a time.
- Hold and Wait: A process holding resources can request more.
- No Preemption: Resources cannot be forcibly taken from a process.
- Circular Wait: A set of processes are waiting on each other in a circular chain.
Avoiding Deadlock
- Partial Ordering of Locks: Always acquire locks in a predetermined order.
- Resource Allocation Graphs: Detect circular dependencies.
Therac-25 Case Study
The Therac-25 was a medical radiation therapy machine that caused several patient deaths due to software errors and lack of hardware interlocks. The primary issue was race conditions that led to incorrect dose administration. The tragedy highlighted the importance of safety-critical system testing and concurrency control.
Scheduling Algorithms
Preemptive vs. Non-Preemptive Scheduling
- Preemptive: Allows the OS to interrupt a running process.
- Non-Preemptive: Process runs to completion once started.
Metrics for Evaluation
- Turnaround Time: Total time taken from submission to completion.
- Waiting Time: Time spent in the ready queue.
- Response Time: Time from submission to the first response.
- System Throughput: Number of processes completed per unit time.
- Fairness: Ensures equal opportunity for all processes.
Common Scheduling Algorithms
- First-Come, First-Served (FCFS):
- Non-preemptive.
- Simple but can cause the Convoy Effect.
- Shortest Job First (SJF):
- Non-preemptive.
- Optimal for minimizing average waiting time.
- Shortest Time to Completion First (STCF):
- Preemptive version of SJF.
- Can suffer from starvation of long processes.
- Round Robin (RR):
- Preemptive.
- Uses a time quantum to switch between processes.
- Multi-Level Feedback Queue (MLFQ):
- Adapts to process behavior.
- Provides both responsiveness and fairness.
- Fair Share Scheduling:
- Ensures equal resource sharing among processes or users.
Virtual Memory Concepts
Virtual Memory provides:
- Memory Protection: Isolates processes to prevent interference.
- Illusion of Large Memory: Uses disk space as secondary storage.
- Efficient Memory Usage: Shares code among processes.
Address Translation (VM to PM)
The Translation Lookaside Buffer (TLB) speeds up virtual-to-physical address mapping.
Page Tables
- Organize memory into pages (logical) and frames (physical).
- Multi-level page tables reduce memory usage.
Multi-Level Page Table Translation
- L1 Table: Holds pointers to L2 tables.
- L2 Table: Holds pointers to L3 tables.
- L3 Table: Holds pointers to L4 tables.
- L4 Table: Contains physical frame numbers.
Page Fault Handling
A Page Fault occurs when a requested page is not in memory.
- Triggers a page replacement algorithm to load the page from disk.
Important Registers in Memory Management
%rip
(Instruction Pointer): Holds the address of the next instruction.%rsp
(Stack Pointer): Points to the top of the current stack frame.%rbp
(Base Pointer): Points to the base of the current stack frame.%rdi
,%rsi
,%rdx
,%rcx
,%r8
,%r9
: Used for passing arguments in x86-64 calling conventions.%rax
(Accumulator): Typically used for return values.%rbx
: Callee-saved register (preserved across function calls).%rflags
: Holds status flags (like zero or carry).
OS Concepts Cheat Sheet
Concurrency
- Processes:
fork()
,exec()
- Threads:
pthread_create()
- Race Conditions: Use mutexes (init, lock, unlock).
- Condition Variables: Use wait, signal, broadcast.
Deadlock Prevention
- Ensure partial ordering of lock acquisition.
Scheduling Algorithms
- Preemptive: RR, STCF
- Non-Preemptive: FCFS, SJF
- Advanced: MLFQ, Fair Share
- Metrics: Turnaround, Waiting, Response, Throughput, Fairness
Virtual Memory
- Translation: Multi-level page tables (L1-L4).
- TLB: Speeds up address translation.
- Page Fault: Triggers disk read and page replacement.
Registers
%rip
: Next instruction.%rsp
: Stack top.%rbp
: Frame base.%rax
: Return value.%rdi
,%rsi
,%rdx
: Argument passing.