Definition

Race condition

A race condition exists when the outcome is correct only for certain interleavings of concurrent process steps.

Interleaved execution

Execution in which instructions from different processes are mixed because an operation may be interrupted between machine instructions.

Atomic operation

An atomic operation appears to happen all at once: other processes cannot observe intermediate states.

Mutual exclusion

A synchronization property that allows only one process at a time to execute a conflicting critical section.

Critical section

A section of code that accesses shared data/resources and must execute in isolation from conflicting processes.

Mutex / lock

A synchronization mechanism used to execute a critical section in isolation. Acquire the lock before the critical section and release it afterward.

Dining Philosophers problem

Five philosophers share five chopsticks; each philosopher needs both neighboring chopsticks to eat, and each chopstick can be used by at most one philosopher at a time.

Producer-Consumer problem

Producers create items and consumers use them; a shared buffer is used to handle differences in their speeds.

Semaphore

A synchronization variable manipulated through atomic P (wait/down) and V (signal/up) operations.

P(S) / wait(S)

It waits until the semaphore permits entry and then decreases/reserves the semaphore value.

V(S) / signal(S)

It increases/releases the semaphore value and can allow a waiting process to proceed.

Counting semaphore

A general semaphore with an integer value; it can represent multiple available units of a resource.

Binary semaphore

A semaphore with a Boolean value. P waits for true and sets it false; V sets it true.

Monitor

A higher-level synchronization construct that encapsulates shared data and operations, provides critical-section behavior implicitly, and provides signaling explicitly.

Peterson's algorithm

A mutual-exclusion algorithm for two processes using only shared variables, simple loads/stores, flags, and a turn variable.

Livelock

Processes keep executing steps but no process makes progress.

Deadlock

A set of processes is deadlocked when every process in the set waits for an event that can only be caused by another process in the set.

Process

A process is an abstraction of a program in execution.

PCB

A Process Control Block is the operating system's bookkeeping record for a process and is used to save its execution context when the process is interrupted.

Multiprogramming

The ability of an operating system to make multiple programs progress on a single-processor machine by repeatedly switching among processes.

User mode

A CPU protection mode in which only a restricted set of instructions can be executed.

Kernel mode

A privileged/unrestricted CPU mode in which the CPU can execute any instruction, including privileged instructions.

Mode switch

A change in CPU execution mode from user to kernel or kernel to user.

Thread

An execution flow within a single address space.

IPC

Inter Process Communication: mechanisms that allow processes to communicate and exchange information/data.

Shared-memory IPC

A portion of main memory is accessible to multiple processes; a change by one process is immediately visible to the others.

Message passing

Processes communicate by sending byte-sequence messages that can be stored in a queue/mailbox until received.

fork()

Creates a replica child process whose process image is identical to the invoking process except for identifiers; parent and child have distinct address spaces.

exec()

Replaces the current process image with a new process image for the specified program.

getpid()

The process identifier of the currently executing process.

wait()

The parent waits for a child process to finish before continuing past the wait.

Primary storage

Storage directly accessible by the CPU, including main memory (RAM), registers, and cache.

Secondary storage

Storage not directly accessible by the CPU; it is accessed through I/O channels, such as HDDs and SSDs.

Tertiary storage

Storage not directly accessible by the CPU and typically used for offline storage, such as magnetic tape and optical disc.

Compile-time address binding

If the memory location is known at compile time, the compiler generates absolute code with addresses bound to that location.

Load-time address binding

The compiler generates relocatable code and the addresses are bound when the process is loaded, provided it will not move during execution.

Execution-time address binding

Binding is delayed until run time when a process may move during execution; hardware performs the translation.

Relocatable code

Code that assumes the process address space starts at 0 and can be relocated to a chosen physical location.

MMU

The Memory Management Unit is special hardware used to perform address translation at run time.

Static partitioning

Main memory is divided into fixed partitions; it is also called fixed partitioning.

Internal fragmentation

Unused space inside an allocated fixed partition because the process does not use the entire block.

Dynamic partitioning

Memory is partitioned at run time as processes arrive.

Hole

A maximal contiguous block of free memory.

First-Fit

Choose the first hole large enough for the process, searching from the beginning of the hole list.

Next-Fit

Choose the first hole large enough, starting where the previous search stopped and wrapping around if needed.

Best-Fit

Choose the smallest hole that is still large enough for the process.

Worst-Fit

Choose the largest hole that is large enough for the process.

External fragmentation

Free memory exists but is split into separate holes, making it difficult to find one sufficiently large contiguous block.

Compaction

Relocating allocated blocks/processes so small holes merge into a larger contiguous free block.

Segmentation

A program is divided into variable-length modules called segments, such as code, stack, data, and heap segments.

Base (segmentation)

The starting physical address where the segment resides.

Limit (segmentation)

The length of the segment.

Paging

A non-contiguous memory-allocation scheme that divides virtual memory into fixed-size pages and physical memory into equal-size frames.

Page table

It stores the mapping from virtual page numbers to physical frame numbers, along with other attributes.

TLB

A small, low-latency cache in the MMU that stores page-to-frame mappings for a small subset of pages.

TLB hit

The requested page-to-frame mapping is found in the TLB.

TLB miss

The mapping is not in the TLB, so the page table must be consulted.

TLB hit ratio

The fraction of memory references for which the required page mapping is found in the TLB.

Virtual memory

A memory-management approach in which only part of a process image needs to be in main memory at a time.

Principle of locality

During a given period, a process typically accesses only a small portion of its address space; also called locality of reference.

Spatial locality

Referencing memory addresses near previously referenced addresses.

Temporal locality

Referencing memory addresses that were referenced in the past.

Demand paging

Load pages into memory only as they are needed/referenced.

Page fault

A page fault occurs when a valid page is referenced but is not currently in main memory.

Valid / present bit

Whether the referenced page is currently in memory.

Random page replacement

Choose a page to replace randomly.

FIFO page replacement

Replace the page that has been in memory the longest.

Belady's anomaly

For FIFO, increasing the number of frames can sometimes increase the number of page faults.

LRU page replacement

Replace the page that has not been referenced for the longest time in the past.

NRU

Not Recently Used: an approximation of LRU that uses reference and modify bits and favors recently referenced pages.

NRU reference bit

It is set whenever the page is referenced and is cleared periodically.

NRU modify bit

It is set whenever the page is modified.

NFU

Not Frequently Used: approximates page usefulness using a count of references and favors pages referenced more frequently.

Aging algorithm

An approximation that periodically shifts reference information into a counter so recent references matter more than old ones.

Second-Chance page replacement

A FIFO-style algorithm that gives a referenced page another chance instead of immediately replacing it.

Thrashing

A condition in which a process/system spends excessive time moving pages between memory and backing storage instead of executing useful work.

Working-set idea

Keep the set of pages a process has been actively referencing during a recent window in memory.

Copy-on-write

Parent and child initially share pages; a page is copied only when one process attempts to modify it.

Platter

A disk surface on which data is magnetically recorded.

Track

A circular path on the surface of a platter.

Cylinder

The set of tracks at the same arm position across platter surfaces.

Sector

A fixed-size subdivision of a track and the smallest unit of data transfer in the disk description.

Seek time

Time taken to move/locate the disk arm to the specified track containing the desired data.

Rotational latency

Time waiting for the desired sector to rotate under the read/write head.

Transfer time

Time required to actually read or write the requested data once positioned.

FCFS disk scheduling

Service disk requests in the order in which they arrive.

SSTF disk scheduling

Service the pending request requiring the shortest seek from the current head position.

SCAN disk scheduling

Move the head in one direction servicing requests, then reverse direction and continue servicing requests.

C-SCAN

Service requests in one direction only; at the end, return to the beginning without servicing requests on the return trip.

LOOK

A modified SCAN algorithm that reverses after the last request in the current direction instead of traveling all the way to the end of the disk.

C-LOOK

The circular version of LOOK: service in one direction and travel only as far as the last request rather than the physical end of the disk.

RAID

A scheme that combines multiple disks to improve performance and/or provide fault tolerance.

Striping in RAID

Distributing data across multiple disks.

Fault tolerance in RAID

Using redundant information so data can remain available/recoverable despite disk failures.

File

A file is a unit of persistent storage on a computer system and a named collection of related information stored on secondary storage.

Directory

A file-system structure used to organize files and map names to stored file information.

Single-level directory

A directory structure with only one directory, the root.

General access control

Use an access-control list to explicitly specify the type of access each user has to a file or directory.

Limited access control

Classify users broadly as owner, group, and others, and specify permissions for each category.

Hybrid access control (1)

Use limited access control by default and add an access-control list when finer-grained control is needed.