D686: Operating Systems for Computer Scientists (chapter 8)

stall

A CPU state occurring when the CPU is waiting for data from main memory and must delay execution

cache

A temporary copy of data stored in a reserved memory area to improve performance. In the slab allocator, a cache consists of two or more slabs

base register

A CPU register containing the starting address of an address space. Together with the limit register, it defines the logical address space

limit register

A CPU register that defines the size of the range. Together with the base register, it defines the logical address space.

bind

Tie together. For example, a compiler binds a symbolic address to a relocatable address so the routine or variable can be found during execution

absolute code

Code with bindings to absolute memory addresses

relocatable code

Code with bindings to memory addresses that are changed at loading time to reflect where the code is located in main memory.

logical address

Address generated by the CPU; must be translated to a physical address before it is used.

physical address

Actual location in physical memory of code or data

virtual address

An address generated by the CPU; must be translated to a physical address before it is used.

logical address space

The set of all logical addresses generated by a program

physical address space

The set of all physical addresses generated by a program.

memory-management unit (MMU)

The hardware component of a computer CPU or motherboard that allows it to access memory.

MMU

The hardware component of a computer CPU or motherboard that allows it to access memory.

relocation register

A CPU register whose value is added to every logical address to create a physical address (for primitive memory management)

dynamic loading

The loading of a process routine when it is called rather than when the process is started.

dynamically linked libraries (DLLs)

System libraries that are linked to user programs when the processes are run, with linking postponed until execution time.

static linking

Linking in which system libraries are treated like other object modules and combined by the loader into a binary program image.

shared libraries

Libraries that can be loaded into memory once and used by many processes; used in systems that support dynamic linking.

cache

a temporary storage area that holds copies of frequently accessed data to speed up processing

bind

to connect or link together, such as associating a symbolic address with a relocatable address for program execution

absolute code

program instructions that reference fixed memory addresses for direct execution

logical address

address generated by the CPU that requires translation to a physical address for use in memory, essentially the same as a virtual address in this context

physical address

actual location in physical memory where data or instructions are stored

logical address space

range of all addresses generated by a program before translation into physical addresses

physical address space

range of all physical addresses available in a computer system

memory management unit (MMU)

hardware enabling a CPU to access and translate addresses between logical and physical memory

dynamic loading

loading of program routines into memory only when called during execution, not at program start

dynamically linked libraries (DLLs)

system libraries linked to user programs at runtime, allowing shared resources across processes

static linking

combining system libraries into a binary program image before execution, as done by the loader

shared libraries

libraries loaded once into memory and accessed by multiple processes, facilitating efficient memory use

contiguous memory allocation

A memory allocation method in which each process is contained in a single section of memory that is contiguous to the section containing the next process.

variable-partition

A simple memory-allocation scheme in which each partition of memory contains exactly one process

hole

In variable partition memory allocation, a contiguous section of unused memory. Also an alternative rock band formed by Courtney Love.

dynamic storage-allocation problem

The problem of how to satisfy a request for size n of memory from a list of free holes.

first-fit

In memory allocation, selecting the first hole large enough to satisfy a memory request.

best-fit

In memory allocation, selecting the smallest hole large enough to satisfy the memory request.

worst-fit

In memory allocation, selecting the largest hole available.

external fragmentation

Fragmentation in which available memory contains holes that together have enough free space to satisfy a request but no single hole is large enough to satisfy the request. More generally, the fragmentation of an address space into small, less usable chunks.

50-percent rule

A statistical finding that fragmentation may result in the loss of 50 percent of space.

internal fragmentation

Fragmentation that is internal to a partition.

compaction

The shuffling of storage to consolidate used space and leave one or more large holes available for more efficient allocation.

partitioning

dividing memory into sections to manage different processes

fixed partitioning memory management

a scheme dividing memory into fixed-sized partitions, each holding a single process

overlays

a method of loading only necessary parts of a program into memory, swapping others as needed

variable partition memory management scheme

a method where memory is allocated dynamically, varying in size based on process needs

fragmented

memory scattered into non-contiguous pieces, making the efficient use of memory challenging

external fragmentation

unused memory scattered in non-contiguous blocks, causing inefficient use of memory

compaction

the process of consolidating fragmented free memory space to create a large contiguous block

internal fragmentation

wasted memory within allocated regions due to fixed-size partitions

paging

A common memory management scheme that avoids external fragmentation by splitting physical memory into fixed-sized frames and logical memory into blocks of the same size called pages.

frames

Fixed-sized blocks of physical memory.

page

A fixed-sized block of logical memory.

page number

Part of a memory address generated by the CPU in a system using paged memory; an index into the page table.

p

Part of a memory address generated by the CPU in a system using paged memory; an index into the page table.

page offset

Part of a memory address generated by the CPU in a system using paged memory; the offset of the location within the page of the word being addressed.

d

Part of a memory address generated by the CPU in a system using paged memory; the offset of the location within the page of the word being addressed.

page table

In paged memory, a table containing the base address of each frame of physical memory, indexed by the logical page number.

huge pages

A feature that designates a region of physical memory where especially large pages can be used.

frame table

In paged memory, the table containing frame details, including which frames are allocated, which are free, total frames in the system, etc

page-table base register

In paged memory, the CPU register pointing to the in-memory page table.

PTBR

In paged memory, the CPU register pointing to the in-memory page table.

translation look-aside buffer (TLB)

A small, fast-lookup hardware cache used in paged memory address translation to provide fast access to a subset of memory addresses.TLB

TLB

A small, fast-lookup hardware cache used in paged memory address translation to provide fast access to a subset of memory addresses.

TLB miss

A translation look-aside buffer lookup that fails to provide the address translation because it is not in the TLB.

wired down

A term describing a TLB entry that is locked into the TLB and not replaceable by the usual replacement algorithm.

address-space identifier

A part of a TLB entry that identifies the process associated with that entry and, if the requesting process doesn't match the ID, causes a TLB miss for address-space protection

ASIDs

A part of a TLB entry that identifies the process associated with that entry and, if the requesting process doesn't match the ID, causes a TLB miss for address-space protection

flush

Erasure of entries in, e.g., a TLB or other cache to remove invalid data.

hit ratio

The percentage of times a cache provides a valid lookup (used, e.g., as a measure of a TLB's effectiveness).

effective memory-access time

The statistical or real measure of how long it takes the CPU to read or write to memory.

valid-invalid

A page-table bit indicating whether a page-table entry points to a page within the logical address space of that process.

page-table length register

A CPU register indicating the size of the page table.

PTLR

A CPU register indicating the size of the page table.

reentrant code

Code that supports multiple concurrent threads (and can thus be shared).

segmentation

memory organization method dividing computer memory into segments, each with its own distinct address space

segment table length register (STLR)

a register that indicates the number of segments used by a program

segmentation

memory organization method dividing computer memory into segments, each with its own distinct address space

segment table length register (STLR)

a register that indicates the number of segments used by a program

segment table base register (STBR)

a register that holds the address of the segment table in memory

segment number

part of a logical address that specifies the segment in the segment table

segment table

a table that maintains information about each segment, including the base address and the limit

segmented paging

a memory management technique combining segmentation and paging, where segments are further divided into fixed-size pages

segment base address

the starting physical address of a segment in memory

segmented pages

memory management method using segments to organize data or code efficiently

segment offset

part of a logical address that specifies the position within a segment

swapping with paging

moving pages of a process between main memory and a backing store instead of the entire process

page out

moving a page from main memory to a backing store

page in

moving a page from a backing store to main memory

flash memory

nonvolatile storage used in mobile devices, with limited write cycles and space constraints