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

Practice vocabulary flashcards covering process synchronization, memory management systems (including paging and virtual memory), page replacement algorithms, and file system implementation strategies based on lecture notes.

Process Synchronization

The coordination of process or thread behavior so that they work together to solve a problem and avoid destructive interference.

Dining Philosophers Problem

A classic synchronization problem where philosophers must share chopsticks (resources) without causing starvation or deadlock.

Monitor

A high-level synchronization construct, such as the Chopstick Manager, that encapsulates data and procedures to ensure safe access to shared resources.

Shared Memory

A type of Interprocess Communication where processes exchange data by reading and writing to a shared memory segment on the same host with low overhead.

Message Passing

An Interprocess Communication model using a post-office facility where processes communicate via $\text{send(dst, msg)}$ and $\text{recv(src, msg)}$ operations.

Name Registry

A central server or mechanism, like DNS, where processes register their names so others can query and find their PID for communication.

Synchronous Message Passing

A communication model where the sender blocks until the receiver is ready to receive the message, ensuring both parties are synchronized.

Asynchronous Message Passing

A communication model where the sender does not wait for the receiver to get the message, requiring the system to provide buffering.

MMU (Memory Management Unit)

Hardware that translates logical addresses to physical addresses and generates interrupts for invalid memory accesses.

Logical Address Space

The independent view of memory provided to a process, ranging from $0$ to a limit $m$.

Contiguous Allocation

A memory management scheme where each process resides in a single fixed-size partition defined by a base and a limit register.

Physical Address Translation (Contiguous)

The calculation performed by the MMU: $\begin{cases} \text{physical\_address} = \text{logical\_address} + \text{base} & \text{if } \text{logical\_address} < \text{limit} \\ \text{generate interrupt} & \text{otherwise} \end{cases}$

External Fragmentation

Wasted memory that occurs when many small holes of free space appear between allocated partitions as processes are created and destroyed.

Internal Fragmentation

Wasted memory that occurs when a process is allocated a fixed-size block that is larger than the requested amount.

Buddy System

An allocation scheme that manages memory in chunks of powers of $2$, merging adjacent free \"buddies\" to reduce external fragmentation.

Swapping

A memory management strategy where an entire process is saved to disk and another process is loaded into memory to run.

Segmentation

A memory management scheme where a process is divided into separate segments like Code, Data, Heap, and Stack, each with its own base and limit.

Paging

A scheme that divides process memory into equal-sized pages and physical memory into equal-sized frames to eliminate external fragmentation.

Page Table

A per-process data structure stored in the kernel that maps page numbers to the $20$-bit frame numbers where they are resident.

TLB (Translation Look-Aside Buffer)

A specialized hardware cache that stores recently used page-number-to-frame-number translations to speed up memory access.

TLB Expected Translation Time

The average time to translate an $n$-level page table, calculated as: $0.99 \times 1\,ns + 0.01 \times (n \times 15 + 1)\,ns$.

Demand Paging

A virtual memory implementation where pages are only loaded into physical frames when they are actually accessed by the process.

Resident Page

An allocated page currently assigned to a frame in physical memory, indicated by a valid bit of $1$ in the page table.

Nonresident Page

An allocated page that is not in physical memory but may be stored on disk, indicated by a valid bit of $0$ and a non-zero frame field.

Copy-On-Write

An optimization for process creation where the parent and child share the same physical pages until one process attempts a write operation.

Guard Page

A read-only page placed at the end of a stack that triggers an interrupt to notify the OS when the stack needs to grow.

Dirty Bit

A hardware-supported bit in the page table entry that is set when a page is modified, used to determine if it must be written to disk upon eviction.

Belady’s Anomaly

A disadvantage of the FIFO page replacement algorithm where adding more frames can unexpectedly result in a higher number of page faults.

Optimal Page Replacement (OPT)

A provably optimal but unimplementable algorithm that replaces the page that will not be used for the longest period of time.

LRU (Least Recently Used)

A page replacement algorithm that evicts the page that has not been accessed for the longest period of time.

Second Chance (Clock) Algorithm

An LRU approximation that uses a circular queue and a reference bit to give recently accessed pages a \"second chance\" before being evicted.

File Control Block (FCB)

A data structure, such as a Unix I-node, that stores file metadata including identifier, permissions, size, and data block locations.

Hard Link

A directory entry that maps a filename directly to an existing file identifier (I-node number) on the file system.

Soft (Symbolic) Link

A directory entry that contains a path to another file rather than a direct reference to a file identifier.

Storage Access Cost

The time required to read or write a disk block, calculated as $S + R + T$, where $S$ is seek time, $R$ is rotational latency, and $T$ is transmission time.

Indexed Allocation

An allocation strategy used by Unix where the FCB stores pointers to data blocks and multi-level indirect blocks to support various file sizes.

Superblock

A persistent disk structure that stores the I-node map, free lists, and disk configuration necessary for managing the file system.

Unified Buffer Cache

A cache that stores recently used file blocks in memory, whether accessed via the File API or memory mapping, to improve performance.

Journaling

A file system consistency technique that logs all operations to a journal file contiguously before committing them to the disk in optimal order.

Log-Structured File System

A file system that performs all updates by appending them contiguously to a log, never modifying existing blocks in place.