Operating Systems: Process Synchronization, Memory Management, and File Systems

Process Synchronization: Concepts and Definitions

• Process Synchronization Goal: To coordinate process and thread behavior so they work together effectively to solve problems.

• Key Keywords:

  • Coordinate Behavior: Managing how entities interact.

  • Destructive Interference: Preventing processes from corrupting each other's data.

  • Deadlock: A state where processes are stuck waiting for each other indefinitely.

  • Starvation: When a process is perpetually denied necessary resources.

  • Scheduler Independence: Designing solutions that do not rely on specific behavior from the thread scheduler.

  • Maximize Concurrency: Allowing as many threads as possible to run simultaneously without interference.

  • Trade-off: Simpler synchronization solutions often reduce the level of concurrency.

The Dining Philosophers Problem

• Problem Description:

  • Philosophers alternate between eating, talking, and sleeping.

  • To eat, a philosopher requires two chopsticks (one on the left, one on the right).

  • Two philosophers sitting next to each other cannot use the same chopstick at the same time.

  • The challenge is preventing philosophers from starving while maintaining safety.

• The Model:

  • Each Philosopher is represented as a thread.

  • Each chopstick is represented as a shared resource.

• Standard Philosopher Logic: Philosopher() { init() while( 1 ) { think() acq_chopsticks() eat() rel_chopsticks() sleep() } }     

Solutions to the Dining Philosophers Problem

• Simple Solution: A Global Lock:

  • A single lock protects the entire table. Only one philosopher can acquire the lock and eat at a time.

  • Pros: Very simple to implement and easy to prove safety.

  • Cons: Severely restricts concurrency as only one person can eat, regardless of how many chopsticks are available.

• Solution 2: A Chopstick Manager (Monitor):

  • A central manager uses a monitor to track chopstick states.

  • Logic: monitor ChopstickManager { bool busy[N] // N chopsticks condition avail[N] acquire_chopsticks(right) { left = (right + 1) % N if (busy[right]) avail[right].wait() busy[right] = true if (busy[left]) avail[left].wait() busy[left] = true } release_chopsticks(right) { left = (right + 1) % N busy[right] = false avail[right].signal() busy[left] = false avail[left].signal() } }         

  • Pros: Uses a short global lock only during the acquisition/release phase.

  • Cons: The manager itself can become a bottleneck (where the flow of operations is restricted or delayed).

• Bad Solution: Left then Right:

  • Every philosopher picks up their left chopstick first, then the right.

  • Risk: If everyone picks up their left chopstick simultaneously, a deadlock occurs because no one can pick up their right chopstick.

• Solution 3: Randomized Solution:

  • Philosophers flip a coin to decide whether to pick up the left or right chopstick first.

  • Pros: Simple and works in almost all practical cases.

  • Cons: It is not $100\%$ guaranteed to avoid deadlock, though the probability is extremely low.

• Solution 4: Alternating Solution with IDs:

  • Philosophers alternate picking order based on their unique ID (odd positions pick left first, even positions pick right first).

  • Pros: Maximizes concurrency and guarantees no deadlock.

  • Cons: Requires philosophers to have and know their unique IDs.

• Solution 5: Alternating Solution without Assigned IDs:

  • Philosophers generate their own IDs dynamically using a shared sequence number.

  • Get ID Logic: int globalSeq = 0 int getId() { int tmp lock() tmp = globalSeq++ unlock() return tmp }         

Synchronizing Linked Lists

• List Operations:

  • Find(key): Returns the item with the specified key or null.

  • Insert(key, item): Inserts an item into a list ordered by key.

  • Delete(key): Removes the item associated with a key.

• Thread-Safety Analysis:

  • Concurrent Find() and Insert()/Delete(): Generally safe if only one thread is modifying pointers; the find operation simply follows the existing trail.

  • Concurrent Inserts: Not safe. If two threads insert in the same location, one node may be lost.

  • Concurrent Deletes: Not safe. Deleting adjacent nodes simultaneously can break the list structure.

• Synchronization Options:

  • Global Lock: Locks the entire list for any insertion or deletion. Easy but kills concurrency.

  • Per-Node Locking: Only locking the specific nodes being modified.

    • Rule: To delete or insert, the previous node must be locked first. Nodes must be locked in a consistent front-to-back order to avoid deadlocks.

    • Problem: There is a race condition between following a link and acquiring the lock on the target node. If the node is deleted after the link is followed but before the lock is acquired, the thread is stranded.

• Fixing Per-Node Locking:

  • Walk and Lock: Lock every node sequentially while traversing the list. Very expensive.

  • Segment Locking: Locking groups of nodes to balance complexity and concurrency.

  • Delete Flag: Add a flag to nodes to mark them as deleted. If a thread hits a deleted node while trying to acquire a lock, it restarts from the head.

Interprocess Communication (IPC)

• IPC Forms:

  • Shared Memory: Processes communicate by reading and writing to a specific shared memory region.

  • Message Passing: Processes exchange data via messages mediated by the Operating System.

  • Signals: Asynchronous notifications sent between processes.

  • Pipes: A direct stream-based connection between processes.

• Shared Memory Model:

  • Analogy: A blackboard in a classroom where anyone can read or write.

  • Attributes: Very efficient, low overhead, and works well locally. Requires synchronization tools like locks or monitors to maintain consistency.

  • Limitations: Hard to debug, doesn't work across multiple machines, and difficult to manage correctly.

• Message Passing Model:

  • Analogy: A post-office or telephone model.

  • Functionality: The OS provides a "post-office" facility (kernel queues) where messages are enqueued for specific recipients.

  • Operations:

    • send(dst, msg)

    • recv(src, msg)

    • recvany(msg)

  • Process Naming: Processes can be identified by PID, Thread ID, or a Name Registry (similar to a phone book or DNS).

• Message Passing Synchronization:

  • Synchronous Send: The sender blocks until the receiver is ready and the message is copied. This requires no buffering (analogy: Telephone).

  • Asynchronous Send: The sender enqueues the message and continues immediately. This requires a buffer to store messages until the receiver is ready (analogy: Postcard).

Memory Management and the MMU

• Memory Definition: A physical byte array where each element has a unique address in the range $0..n-1$.

• Memory Management Unit (MMU):

  • A hardware component that all CPU memory accesses must pass through.

  • Roles: Creates the logical address space, translates logical addresses to physical addresses, and generates interrupts (bus faults) for invalid access.

• Address Spaces:

  • Physical Address Space: The actual range of physical memory hardware.

  • Logical Address Space: The independent view of memory provided to a process.

  • Analogy: Pre-Copernican (Viewed from the Earth/Process) vs. Post-Copernican (Viewed from the Sun/Hardware).

  • Benefits of Separation: Allows programs to be loaded anywhere in memory, provides consistent internal pointers across different runs, and enables multiple processes to coexist.

Contiguous Allocation

• Mechanism: Memory is divided into fixed-size partitions. Every process is assigned exactly one partition.

• Registers: Each partition is defined by a Base (start address) and a Limit (size).

• Translation Logic: if logical_address < limit: physical_address = logical_address + base else: generate memory fault interrupt &nbsp;&nbsp;&nbsp;&nbsp;

• Fragmentation:

  • External Fragmentation: As processes are created and deleted, small, non-contiguous holes appear in physical memory that cannot fit new processes.

  • Internal Fragmentation: Occurs when memory is allocated in fixed blocks that are larger than the requested size (e.g., allocating a $4\,KB$ block for a $4\,byte$ variable).

• Allocation Strategies:

  • First Fit: Allocate the first hole found that is big enough. Fast but not always optimal.

  • Best Fit: Search the entire list for the smallest hole that fits. Reduces wasted space initially but creates tiny, unusable fragments.

  • Worst Fit: Allocate from the largest available hole. Intended to leave larger remaining holes but prevents large memory requests from being satisfied later.

• Alternative Solutions:

  • Compaction: Moving all allocated chunks to one end of memory to consolidate free space. This is expensive and impossible if pointers cannot be updated.

  • The Buddy System: Memory is allocated in powers of $2$. When a block is freed, it is merged with its "buddy" (the other half of the original split block). Logic is $O(\log(n))$.

Segmentation and Paging

• Segmentation: A process is divided into multiple segments of varying sizes (Code, Data, Heap, Stack). Each segment has its own base/limit pair. This reduces external fragmentation of the process but increases MMU complexity.

• Paging:

  • Physical Memory is divided into fixed-size Frames (usually $4\,KB$).

  • Logical Memory is divided into same-sized Pages.

  • A Page Table maps page numbers to frame numbers.

  • Address Translation: The logical address is split into a Page Number (upper bits) and an Offset (lower 12 bits for $4\,KB$ pages). The frame number replaces the page number to create the physical address.

• Multi-Level Page Tables:

  • Standard page tables for a $32-bit$ space ($4\,MB$) are too large for most processes to store in memory entirely.

  • Solution: A two-level table where a "Top-level" table points to smaller "Second-level" tables. If a range of memory isn't used, the second-level table is never allocated, saving massive amounts of space.

• Translation Look-Aside Buffer (TLB):

  • A fast hardware cache for recently used page translations.

  • Performance Math: If a memory access takes $15\,ns$ and a TLB access takes $1\,ns$, with a $99\%$ hit rate in an $n$-level table, the expected time is approx $1 + 0.15n\,ns$.

  • Context Switches: When switching processes, the TLB must either be flushed (erased) or must store Address Space IDs to prevent one process from accessing another's frames.

Virtual Memory and Demand Paging

• Virtual Memory: Decouples the logical view of memory from physical reality. This allows processes to be larger than the total physical RAM of the computer.

• Demand Paging: Pages are only loaded into physical memory when they are accessed.

• Page States:

  1. Unallocated: Not yet requested; uses no space.

  2. Resident: Allocated and currently in physical RAM (Valid bit $= 1$).

  3. Nonresident: Allocated but stored on disk (Valid bit $= 0$, Frame # $\\neq 0$).

• Mechanics of a Page Fault:

  1. CPU tries to access a page.

  2. MMU sees invalid bit.

  3. OS finds a free frame, loads the page from disk, updates the page table, and restarts the instruction.

Performance Optimizations in Virtual Memory

• Copy-On-Write (COW):

  • When a process forks, instead of copying all memory, the parent and child share the same pages marked as Read-Only.

  • If either tries to write, a page fault occurs, and the OS makes a dedicated copy of just that page then marks it Read-Write.

• Guard Pages: Used for stack allocation. A page at the end of the stack is marked read-only. Accessing it triggers a fault, signaling the OS to grow the stack by allocating a new frame and moving the guard page further down.

• Shared Libraries: System libraries (like stdlib) are loaded once into physical memory and mapped into the logical space of every process, saving RAM.

Page Replacement Algorithms

• Victim Selection: When RAM is full and a new page is needed, a "victim" page must be evicted to disk.

• Dirty Bit: A hardware bit that tracks if a page was modified. If a victim page is NOT dirty (not modified), it does not need to be written to disk, making eviction faster.

• Algorithms:

  • FIFO (First-In, First-Out): Simplest but prone to Belady's Anomaly (adding more frames can actually increase page faults).

  • OPT (Optimal): Evict the page that will not be used for the longest time in the future. Impossible to implement as it requires knowing the future.

  • LRU (Least Recently Used): Evict the page not accessed for the longest time. Hardware-intensive (requires timestamps or a stack).

  • Second Chance (Clock) Algorithm: Uses a circular queue and a Reference Bit. If the bit is $1$, give it a "second chance" by clearing the bit and moving on. The first page found with a bit of $0$ is evicted.

The File System Abstraction

• Definition: A file is a stream of bytes. The OS uses the same API to access data whether it is on a disk, a keyboard, or a network socket.

• File Types:

  • Regular Files: Persistent data on storage.

  • Directories: Special files mapping names to identifiers.

  • Hardware/Virtual Devices: Located in /dev (e.g., /dev/null, /dev/random).

  • Pipes/Sockets: IPC communication channels.

• File API (POSIX):

  • open(path, flags): Locates the File Control Block (FCB).

  • read(fd, buffer, size) and write(fd, buffer, size): Move the internal Offset pointer.

  • lseek(fd, offset, whence): Manually moves the offset for random access.

• Data Structures:

  • File Control Block (FCB): Stores metadata (Owner, size, I-node number, location). Does NOT store the file name.

  • System-Wide Open File Table (SWOFT): Tracks every file currently open by any process in the system.

  • File Descriptor Table: A per-process table mapping small integers (FDs) to entries in the SWOFT. Standard FDs: $0 = stdin$, $1 = stdout$, $2 = stderr$.

File System Implementation

• Disk Anatomy: Platters subdivided into Tracks, which are further divided into Sectors (usually $512\,bytes$).

• Block API: The OS treats storage as a contiguous sequence of Blocks (usually $4\,KB$ or $8\,KB$).

• Storage Allocation Strategies:

  1. Contiguous: Fast but suffers from external fragmentation.

  2. Linked: No fragmentation but terrible random access performance.

  3. Indexed (Unix File System): Uses I-nodes.

• Unix I-node Structure:

  • 12 Direct Pointers: Points to data blocks ($48\,KB$ total).

  • Single Indirect: Points to a block of pointers ($1024 \times 4\,KB = 4\,MB$).

  • Double Indirect: Points to blocks of indirect pointers ($4\,GB$).

  • Triple Indirect: Supports Terabyte-level files.

• The Superblock: A critical block storing the I-node map, free lists, and the Clean Flag (used to detect improper shutdowns).

Reliability and Performance

• Unified Buffer Cache: Caches blocks recently read from disk. Uses LRU for eviction.

• Consistency: Metadata and Data must be written in a specific order to avoid corruption during crashes.

  • Correct Order: Data Blocks $\\rightarrow$ Indirect Blocks $\\rightarrow$ I-Node Blocks.

• Journaling: Logs operations to a journal before performing them. In a crash, the OS simply replays the journal instead of scanning the whole disk.

• Log-Structured File System: Never updates blocks in place. It appends all new data and metadata to the end of a continuous log. This makes writes extremely fast but requires expensive "garbage collection" (free space recovery) later.

• Links:

  • Hard Link: Multiple directory entries pointing to the same I-node ID.

  • Soft (Symbolic) Link: A directory entry containing a text path to another file. Can point to non-existent files ("broken links").