一、作業系統
(一) Paging
- Physical address space of a process can be noncontiguous; process is allocated physical memory whenever the latter is available
- Avoids external fragmentation
- Avoids problem of varying sized memory chunks
- Divide physical memory into fixed-sized blocks called frames
- Size is power of 2, between 512 bytes and 16 Mbytes
- Divide logical memory into blocks of same size called pages
- Keep track of all free frames
- To run a program of size
N
pages, need to findN
free frames and load program - Set up a page table to translate logical to physical addresses
- Backing store likewise split into pages
- Still have Internal fragmentation
- Calculating internal fragmentation
- Page size = 2,048 bytes
- Process size = 72,766 bytes
- 35 pages + 1,086 bytes
- Internal fragmentation of 2,048 - 1,086 = 962 bytes
- On average fragmentation = 1 / 2 frame size
- So small frame sizes desirable?
- But each page table entry takes memory to track
- Page sizes growing over time
- Solaris supports two page sizes – 8 KB and 4 MB
- Process view and physical memory now very different
- By implementation process can only access its own memory
(二) Address Translation Scheme
- 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
- Page number
(三) Implementation of Page Table
- Page table is kept in main memory
- Page-table base register (PTBR) points to the page table
- Page-table length register (PTLR) indicates size of the page table
- In this scheme every data/instruction access requires two memory accesses
- One for the page table and one for the data / instruction
- The two memory access problem can be solved by the use of a special fast-lookup hardware cache called associative memory or translation look-aside buffers (TLBs)
- Some TLBs store address-space identifiers (ASIDs) in each TLB entry – uniquely identifies each process to provide address-space protection for that process
- Otherwise need to flush at every context switch
- TLBs typically small (64 to 1,024 entries)
- On a TLB miss, value is loaded into the TLB for faster access next time
- Replacement policies must be considered
- Some entries can be wired down for permanent fast access
(四) Effective Access Time
(五) Memory Protection
- Memory protection implemented 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
- Valid-invalid bit attached to each entry in the page table
valid
indicates that the associated page is in the process’ logical address space, and is thus a legal pageinvalid
indicates that the page is not in the process’ logical address space- Or use page-table length register (PTLR)
- Any violations result in a trap to the kernel
(六) Shared Pages
- Shared code
- One copy of read-only (reentrant) code shared among processes (i.e., text editors, compilers, window systems)
- Similar to multiple threads sharing the same process space
- Also useful for interprocess communication if sharing of read-write pages is allowed
- Private code and data
- Each process keeps a separate copy of the code and data
- The pages for the private code and data can appear anywhere in the logical address space
(七) Structure of the Page Table
- Memory structures for paging can get huge using straight-forward methods
- Consider a 32-bit logical address space as on modern computers
- Page size of 4 KB (2^12^)
- Page table would have 1 million entries (2^32^ / 2^12^)
- If each entry is 4 bytes -> 4 MB of physical address space / memory for page table alone lot
- Don’t want to allocate that contiguously in main memory
- Hierarchical Paging
- Hashed Page Tables
- Inverted Page Tables
Hierarchical Page Tables
- Break up the logical address space into multiple page tables
- A simple technique is a two-level page table
- We then page the page table
Two-Level Page-Table Scheme
- Example
- A logical address (on 32-bit machine with 1K page size) is divided into
- a page number consisting of 22 bits
- a page offset consisting of 10 bits
- Since the page table is paged, the page number is further divided into
- a 12-bit page number
- a 10-bit page offset
- Thus, a logical address is as follows
- where p 1 is an index into the outer page table, and p 2 is the displacement within the page of the inner page table
- Known as forward-mapped page table
- A logical address (on 32-bit machine with 1K page size) is divided into
Three-level Paging Scheme
Hashed Page Tables
- Common in address spaces > 32 bits
- The virtual page number is hashed into a page table
- This page table contains a chain of elements hashing to the same location
- Each element contains (1) the virtual page number (2) the value of the mapped page frame (3) a pointer to the next element
- Virtual page numbers are compared in this chain searching for a match
- If a match is found, the corresponding physical frame is extracted
- Variation for 64-bit addresses is clustered page tables
- Similar to hashed but each entry refers to several pages (such as 16) rather than 1
- Especially useful for sparse address spaces (where memory references are non-contiguous and scattered)
Inverted Page Table
- Rather than each process having a page table and keeping track of all possible 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, with information about the process that owns that page
- Decreases memory needed to store each page table, but increases time needed to search the table when a page reference occurs
- Use hash table to limit the search to one — or at most a few — page-table entries
- TLB can accelerate access
- But how to implement shared memory?
- One mapping of a virtual address to the shared physical address