Study guide: Virtual Memory Management

Course Outline

  1. Page Table Size and Reduction
  2. Hierarchical Page Tables
  3. Hashed and Inverted Page Tables
  4. Demand Paging and Page Faults
  5. Thrashing
  6. Segmentation and Address Translation
  7. Combined Paging and Segmentation
  8. Multilevel Page Table Calculation

1. Page Table Size and Reduction

โ˜… Must-know

  • With a 32-bit virtual address, 4 KB pages, and 4-byte page-table entries, a single-level page table has 1,048,576 entries and occupies 4 MB per process.

Further detail

  • Page-table size can be reduced using:
    • hierarchical page tables
    • hashed page tables
    • inverted page tables

2. Hierarchical Page Tables

Key Concepts & Definitions

  • Hierarchical paging: Divides the virtual address space into multiple page tables, effectively paging the page table itself.

โ˜… Must-know

  • In a two-level page table for a 32-bit virtual address space with 4 KB pages, the address is divided into a 10-bit outer-table index, a 10-bit inner-table index, and a 12-bit page offset.

Further detail

  • The VAX minicomputer was sold between 1977 and 2000 and used a 32-bit virtual address space with 512-byte pages, divided into four 2ยณโฐ-byte sections.

  • A VAX virtual address uses 2 bits to specify the section, 21 bits for the page number within that section, and 9 bits for the page offset.

  • For a 64-bit virtual address with 4 KB pages and 4-byte entries, an inner page table has 2ยนโฐ entries and fits in one page, but the outer page table has 2โดยฒ entries and occupies 2โดโด bytes.

  • A 64-bit system may require up to seven paging levels, causing seven memory accesses to translate a virtual address; this is considered unacceptable.

Memory Hook

Picture a page table itself split across pages, with each address choosing a table before choosing a page.

3. Hashed and Inverted Page Tables

Key Concepts & Definitions

  • Hashed page table: Hashes the virtual page number to a table location whose entry points to a linked list of entries sharing that hash value.
  • Inverted page table: Has one entry for each real memory page and one page table for all processes in the system.

Essential Points

  • Each hashed page-table list element contains:
    • the virtual page number
    • the mapped page-frame value
    • a pointer to the next element
  • Hashed address translation hashes the virtual page number, searches the linked list for a matching virtual page number, and returns the corresponding page-frame address.
  • Each inverted page-table entry stores the virtual address of the page held in that real memory location and information about the process that owns the page.

๐Ÿ“Œ An inverted page table reduces page-table memory use but increases search time; hashing can reduce that search time at the cost of one extra memory access.

Memory Hook

Hashed tables start from a virtual page number; inverted tables start from each real memory page.

4. Demand Paging and Page Faults

Key Concepts & Definitions

  • Demand paging: Loads pages into physical memory only when they are needed during program execution.

โ˜… Must-know

  • A valid-invalid bit marked valid indicates that a page is in main memory, while an invalid bit indicates that it is not in memory and will cause a page fault when referenced.
  • ๐Ÿ”„ To handle a page fault, the operating system: validates the reference and aborts if it is invalid, allocates a frame for a valid page that is not resident, loads the page from disk into the frame, updates the page table, marks the page valid, restarts the instruction that caused the fault

Further detail

  • Demand paging:
    • reduces memory consumption
    • provides faster response times
    • can support more users

๐Ÿ“Œ A lazy pager loads individual pages only when needed, whereas a lazy swapper swaps all pages of a process as a whole.

Memory Hook

Validate, allocate, load, update, mark valid, restart.

5. Thrashing

Key Concepts & Definitions

  • Thrashing: Occurs when a process spends most of its time constantly swapping pages in and out because it does not have enough frames.

โ˜… Must-know

  • Thrashing causes low CPU utilization because processes spend most of their time paging instead of doing useful work.

Further detail

  • Low CPU utilization caused by thrashing may prompt the operating system to add more processes, worsening the thrashing problem.

Memory Hook

Too few frames โ†’ constant paging โ†’ low CPU utilization.

6. Segmentation and Address Translation

Key Concepts & Definitions

  • Segmentation: Divides virtual memory into multiple virtual address spaces called segments and reflects the user's view of memory.

โ˜… Must-know

  • A segmented virtual address is a pair โŸจs,dโŸฉ, where s identifies the segment and d is the offset within it.

๐Ÿ“Œ A segmented logical address is an error if its offset is outside the segment limit; otherwise its physical address is the segment base plus the offset.

Further detail

  • A C compiler may create separate segments for:

    • code
    • global variables
    • the heap
    • each thread's stack
    • the standard C library
  • Each segment-table entry contains a segment base, which gives the segment's starting physical address, and a segment limit, which gives its length.

  • With segment 2 starting at physical address 4300, virtual address โŸจ2,53โŸฉ resolves to physical address 4353.

  • With segment 3 starting at physical address 3200, virtual address โŸจ3,852โŸฉ resolves to physical address 4052.

  • Virtual address โŸจ0,1222โŸฉ is invalid because segment 0 is 1000 bytes long and offset 1222 exceeds its limit.

Memory Hook

A segment uses a base and a limit; paging maps pages to frames.

7. Combined Paging and Segmentation

โ˜… Must-know

  • On the Intel Pentium, the segmentation unit translates a virtual address into a linear address, and the paging unit translates the linear address into a physical address.

Further detail

  • The Intel Pentium supports both pure segmentation and segmentation combined with paging.

8. Multilevel Page Table Calculation

โ˜… Must-know

  • For that system, the page offset uses 11 bits, leaving 53 bits for the page number; dividing 53 by 9 index bits per level and rounding up gives 6 page-table levels.

Further detail

  • With 64-bit virtual addresses, 2048-byte pages, and 4-byte entries, each page table page holds 512 entries, requiring 9 index bits per level.

Test yourself

Take a 18-question practice quiz on Virtual Memory Management, with every answer explained.

1. A process uses a 32-bit virtual address space, 4 KB pages, and 4-byte page-table entries. How large is its single-level page table?

2. A system designer wants to reduce the memory required for page tables. Which set names methods that can do this?

Take the quiz โ†’

Study with flashcards

Memorize the key concepts of Virtual Memory Management with 45 flashcards.

How many entries does a single-level page table have with a 32-bit virtual address and 4 KB pages?

1,048,576 entries.

How much memory does that page table occupy per process with 4-byte entries?

4 MB.

How does hierarchical paging organize virtual address space?

It divides the virtual address space into multiple page tables, effectively paging the page table itself.

See the flashcards โ†’

Related classes

Make your own study guides

Upload your class notes and Revizly writes a study guide, a quiz and flashcards in about a minute.

Study guide maker