D686: Operating Systems for Computer Scientists (chapter 9)

virtual memory

A technique that allows the execution of a process that is not completely in memory. Also, separation of computer memory address space from physical into logical, allowing easier programming and larger name space.

virtual address space

The logical view of how a process is stored in memory

sparse

In memory management, a term describing a page table that has noncontiguous, scattered entries. A sparse address space has many holes

demand paging

In memory management, bringing in pages from storage as needed rather than, e.g., in their entirety at process load time.

page fault

A fault resulting from a reference to a non-memory-resident page of memory

pure demand paging

A demand paging scheme wherein no page is brought into memory until it is referenced.

locality of reference

The tendency of processes to reference memory in patterns rather than randomly.

swap space

Secondary storage backing-store space used to store pages that are paged out of memory.

free-frame list

A kernel-maintained data structure containing the list of currently available free frames of physical memory.

zero-fill-on-demand

The writing of zeros into a page before it is made available to a process (to keep any old data from being available to the process).

effective access time

The measured or statistically calculated time it takes to access something; e.g., see effective memory-access time.

page-fault rate

A measure of how often a page fault occurs per memory access attempt

anonymous memory

Memory not associated with a file. Pages not associated with a file, if dirty and paged out, must not lose their contents and are stored in swap space as anonymous memory.

demand paging

bringing in parts of a program from storage into memory only when they are needed 

valid-invalid bit

a bit used in the page table to indicate whether a page is currently in memory (valid) or not (invalid) 

page fault

an event that occurs when a process tries to access a page not currently loaded in physical memory, causing the operating system to load the page from secondary storage into memory    

free frame

an available block of physical memory where a page can be loaded from secondary storage 

effective access time (EAT)

a measure of the average time it takes to access a page in memory, considering both memory access time and the overhead associated with page faults

over-allocating

Generally, providing access to more resources than are physically available. In virtual memory, allocating more virtual memory than there is physical memory to back it

page replacement

In virtual memory, the selection of a frame of physical memory to be replaced when a new page is allocated.

victim frame

In virtual memory, the frame selected by the page-replacement algorithm to be replaced

modify bit

An MMU bit used to indicate that a frame has been modified (and therefore must have its contents saved before page replacement).

dirty bit

An MMU bit used to indicate that a frame has been modified (and therefore must have its contents saved before page replacement)

frame-allocation algorithm

The operating-system algorithm for allocating frames among all demands for frames.

page-replacement algorithm

In memory management, the algorithm that chooses which victim frame of physical memory will be replaced by a needed new frame of data.

reference string

A trace of accesses to a resource. In virtual memory, a list of pages accessed over a period of time.

Belady's anomaly

An anomaly in frame-allocation algorithms in which a page-fault rate may increase as the number of allocated frames increases.

optimal page-replacement algorithm

A theoretically optimal page replacement algorithm that has the lowest page-fault rate of all algorithms and never suffers from Belady's anomaly.

least recently used (LRU)

In general, an algorithm that selects the item that has been used least recently. In memory management, selecting the page that has not been accessed in the longest time.

stack algorithm

A class of page-replacement algorithms that do not suffer from Belady's anomaly.

reference bit

An MMU bit indicating that a page has been referenced.

second-chance page-replacement algorithm

A FIFO page replacement algorithm in which, if the reference bit is set, the bit is cleared and the page is not replaced.

clock

In the second-chance page-replacement algorithm, a circular queue that contains possible victim frames. A frame is replaced only if it has not been recently referenced.

least frequently used (LFU)

In general, an algorithm that selects the item that has been used least frequently. In virtual memory, when access counts are available, selecting the page with the lowest count.

most frequently used (MFU)

In general, an algorithm that selects the item that has been used most frequently. In virtual memory, when access counts are available, selecting the page with the highest count.

raw disk

Direct access to a secondary storage device as an array of blocks with no file system.

page replacement algorithm

an algorithm used to select a page to be swapped out of main memory when a new page needs to be loaded

reference string

a sequence of page accesses used to demonstrate and evaluate page replacement algorithms by showing the order in which pages are requested

first in, first out (FIFO) algorithm

page replacement method where the oldest page in memory is replaced first

optimal page replacement

page replacement method that replaces the page that will not be used for the longest period of time in the future

Belady's anomaly

a phenomenon where increasing the available number of page frames in memory may result in an increase in the number of page faults

least recently used (LRU) algorithm

a page replacement method where the page that has not been used for the longest time is replaced when a page fault occurs

allocation of frames

dividing memory into fixed-size chunks assigned to processes

fixed allocation

assigning a set number of frames to each process permanently

proportional allocation

giving frames to processes based on their size or needs

global replacement

selecting a frame from any process for replacement

equal allocation

giving every process the same number of frames

priority replacement algorithm

an algorithm that replaces pages based on priority

thrashing

excessive paging due to insufficient physical memory

working set

the collection of pages most recently used by a process 

local replacement algorithm

an algorithm for managing memory that restricts page replacement to pages within the current process

locality model

a strategy for managing memory based on where and how often pages are accessed

page-fault frequency

how often a page fault occurs during system operations

working-set model

a method of tracking the most recently used pages in memory