Section 3 - D686 - Operating Systems

Chapter 8 and 9 + section test

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

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

modify bit/dirty bit

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

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.

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

What is an advantage of using virtual memory in an operating system?

Allows programs to use more memory

How does demand paging optimize memory usage?

Loads only the necessary parts of a program

What happens when a process tries to access a page that is not currently in memory?

A page fault occurs.

What is pure demand paging?

Loading pages only when needed

Which mechanism is used to handle page faults efficiently in demand paging?

Valid-invalid bit

What is the purpose of page replacement in memory management?

Replace less frequently used pages

Which algorithm replaces the page not used for the longest time?

Least recently used

What is a disadvantage of the optimal page replacement algorithm?

It requires future knowledge of reference strings.

How does the translation look-aside buffer (TLB) enhance memory management?

By speeding up address translation

What is thrashing in memory management?

When the CPU spends excessive time swapping pages

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 space address

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.

dynamic storage allocation

the process of assigning and freeing memory during a program's run time as needed

memory protection

a method to control and restrict how programs access memory in a computer, preventing errors and security issues

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

What defines a logical address space using base and limit registers?

Base and limit registers

How do base and limit registers contribute to hardware address protection?

By defining the range of accessible addresses

Which process binds logical addresses to physical addresses?

Address binding

Which characteristic differentiates a logical address space from a physical address space?

Logical address space is used by the CPU, while physical address space is used by memory.

Which mechanism protects memory from being accessed incorrectly?

Memory protection

How is memory allocated and managed in a system?

By using fixed and variable partitions

What ensures that each process has its own separate memory space?

Memory protection

Which issue is caused by fixed partition memory management?

Internal fragmentation

What causes external fragmentation in memory management?

Dynamic allocation of memory blocks

What is the 50% rule in memory management?

50% of memory is lost to fragmentation.

A page number is represented by 10 bits. How many entries are in the page table?

2¹⁰

A 32-bit address is divided into 20 bits for the page number and 12 bits for the offset. ______ is the page number and ______ is the offset for the logical address 0x139A4BD7.

0x139A4, 0xBD7

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 (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 (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 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).