(10) Paging

Question 1

Describe an address translation scheme

Answer 1

Address generated by CPU is divided into

Page number (p) - used as an index into a page table which contains base address of each page in physical memory.
Page offset (d) - combined with base address to define the physical memory address that is sent to the memory unit.

Question 2

Describe how a page table is implemented

Answer 2

Page table is kept in main memory
Page table base register (PTBR) points to page table
Page table length register (PTLR) indicates size of the page table
Every data/instruction access requires two memory accesses - one for the page table and one for the data/instruction
Solve two memory access problem by using special fast-lookup hardware cache (TLB)
Store address-space identifiers (ASIDs) in each TLB entry
TLBs typically small (64 to 1024 entries)
On a TLB miss the value is loaded into the TLB for faster access next time.
Replacement policies must be considered
Some entries can be wired down for fast access.

Question 3

Describe memory protection implementation

Answer 3

By associating protection bit with each frame.
To indicate if read-only or read-write access is allowed
Can also add more bits to indicate page execute-only and so on.

Question 4

Describe the valid-invalid bit in memory protection

Answer 4

“valid” indicates that the associated page is in the process’ logical address space and so is a legal page
“invalid” indicates that the page is not the process’ logical address space

Question 5

Describe a hierarchical page table

Answer 5

Break up the address space into multiple page tables.

We then page the page table.

Question 6

Describe an inverted page table

Answer 6

Rather than each process having a page table and keeping tack of all logical pages, track all physical pages.
One entry for each real page of memory.
Entry consists of -the virtual address of the page stored in that real memory location -information about the process that owns that page.
This decreases memory needed to store each page table but increases time needed to search the table when a page reference occurs

Question 7

What functionality is enhanced by page tables?

Answer 7

Code (instructions) is read only so a bad pointer can’t change the program code.
Dereferencing a null pointer is an error caught by hardware (don’t use first page of virtual address space mark it as invalid so references to address 0 cause an interrupt.
Inter process memory protection (my XYZ is different to your XYZ)
Shared libraries
Generalise use of shared memory
Copy-on-write