Computer Memory Hierarchy, Virtual Memory, and Page Replacement Algorithms

Memory Hierarchy

1. Registers

2. Cache

3. RAM (main memory)

4. HDD / SDD (hard disk drive / solid state drive

5. Cloud / external / network

Volatile memory

1. Registers

2. Cache

3. RAM

As we go UP the memory hierarchy

+ Speed

- Space

As we go DOWN the memory hierarchy

- Speed

+ Space

MMU (Memory Management Unit)

A hardware component that translates virtual addresses to physical addresses.

TLB (translation lookaside buffer)

cache of recently translated addresses

Thrashing

continuous page evictions followed by page faults

Prepaging

pages are loaded into main memory along with other related pages

fragmentation

processes repeatedly load and unload from memory, leaving small blocks of memory unused

best fit

find a hole that is closest to accomodate size wise

worst fit

always takes the largest available hole

first fit

Allocate the first hole that is big enough

next fit

starts each search at the point of the last allocation.

quick fit

uses an additional DS mapping commonly sized holes to their address

The virtual memory system can assist in performing what tasks?

Moving data from our slow memory (secondary storage) to faster memory (main memory) when it is needed

Evicting a page from main memory when it is determined it is no longer needed.

Allocating virtual addresses to a process rather than physical addresses

Allocating an address space to a process that is larger than the available main memory of the system

To speed up translations, a system may keep a memory cache of recently translated addresses called a

translation lookaside buffer

When is the M bit set in a page table entry?

When the page frame in main memory and its source page in secondary storage are now different

What are some steps that are done as part of the WS Clock Page Eviction Algorithm?

Use current time - time of last to determine if the page is still in the working set.

Second chance on the M bit (to a max amount of writes)

Second chance on the R bit

WS Clock Page Eviction Algorithm steps

1. Store all pages in a clock (circular) data structure

2. When scanning a page:

* Check R (reference) bit

2a. If R = 1

→ Set R = 0

→ Update TLU (time of last use)

→ Skip (not a candidate)

2b. If R = 0

→ Check age: current_time - TLU

* If age < τ (tau)

→ Page is in working set → skip

* If age ≥ τ

→ Page is NOT in working set → candidate for eviction

3. Now check M (modified) bit:

* If M = 0

→ ✅ Evict immediately

* If M = 1

→ Schedule write to disk

→ Set M = 0

→ Skip for now and continue scanning

4. If no page is evicted after full cycle

→ eventually a cleaned page (M = 0) will be evicted

How to map a virtual address to a physical address given a page table

1. count the pages in the table

2. 2^x = num of pages

3. convert virtual address to binary

4. take x num of digits from the left most binary of virtual address and map to page and corresponding page frame

5. take that page frame , remove those leftmost digits and tack the page frame onto the front to get the physical address

getstk()

1. round memory requested up to nearest multiple of 8

2. find the first right-most block that can accomodate the param (nbytes)

3. address returned = base address + amount of free space that can be allocated (attached num _+ block num)

4. If it takes up the whole block -> nodes returned is num of all blocks minus one; if not -> nodes returned is num of all blocks

getmem()

1. round memory requested up to nearest multiple of 8

2. find the leftmost block that cam accomadate the param (nbytes)

3. address returned = base address (num attached)

4. If it takes up the whole block -> nodes returned is num of all blocks minus one; if not -> nodes returned is num of all blocks

Fields in Page Table Entry

-R bit (have you used the page recently)

-M bit (If a page is modified it must be saved before evicting)

-Page frame number (how to construct the physical address)

-Caching disabled (Doesn't put virtual address in the TLB)

-TLU (Time of Last Use, time stamp)

-Present / Absent bit (Inside physical RAM or not, if 1 its on ram if 0 it page faults)

-Protected bit

R Bit

Reference bit indicating if a page was accessed.

M bit

Indicates if a page has been modified.

Page frame number

Physical address of a page in memory

Caching disabled

cache which can be inaccurate, the OS can disable it

Working Set

the set of pages that a process is currently using

Protected Bit

small, hidden memory markers (read/write/execute) that define what a program can do to specific memory locations

Present / Absent Bit

keeps track of which pages are physically present in memory ( 1 if on ram 0 if page faults)

Least Recently Used Page Eviction

Take the last [num of room for pages in memory] pages before eviction -> leftmost page is evicted

NFU w/ Ageing

1. Shift all digit to the right

2a. If the R bit is 1 -> change leftmost digit (should be zero if done correctly) to 1

2b. If R bit is 0 -> do nothing

3. Smallest remaining binary number corresponds to page that must be evicted

Virtual Addressing - Given a sample system, calculate the number of pages needed in a single level paging system as well as how many bits are needed in the virtual address to reference the given page.

1. entire address space size = 2^ [virtual address bits]

2. convert page size to a 2^n value

2e. 64 KB = 2^6 (64) * 2^10 (kb)

3. 2^[virtual address bits] / 2^n (page size) = pages needed

3a. 2^b = pages needed ; the b is the bits needed in the virtual address to reference the given page