操作系统（本）2024-11-21 第 7-8 节 ch8 Main Memory.pdf
8.4 Paging（分页，页式存储管理）
复习计组了
Paging
Divide physical memory into fixed-sized blocks called frames(帧、物理块、页框)
Divide logical memory into blocks of same size called pages(页)
Set up a page table（页表）to translate logical to physical addresses
Noncontiguous Allocation
OS keeps track of pages via a page table, when a process of size n pages is ready to execute, OS finds n free frames
即 OS 可以在 main mem 里选任意位置的 page，只要总大小够了就行
每个进程都有一个页表
[!EXAMPLE] Paging Example
process Pi requires 16 bytes of logical memory
下面这图黄色的括号和箭头线往下偏移了点，不要多想
右边的数字不是帧号，而是 byte 序号，帧号从上到下是 0~7
Address Translation Scheme（地址变换）
Address generated by CPU is divided into
- Page number (p) （页号）
- 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
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 (PRLR) 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
can be solved by associative memory or translation look-aside buffers (TLBs) ( 联想寄存器、快表），页表的 cache
[!NOTE] Paging Hardware With TLB
Effective Access Time（有效访问时间）
Effective Access Time (EAT) = \((t+\epsilon ) \alpha + ( t + t + \epsilon) (1 – \alpha)\)
- $\epsilon $ time unit = Associative Lookup 快表访问时间
- memory cycle time 内存访问时间 = \(t\)
- \(\alpha\) = Hit ratio of TLB
Memory Protection
by associating protection bit with each frame - Valid-invalid bit attached to each entry in the page table
valid indicates that the associated page is in the process’ logical address space
这玩意儿用来防止 process 通过 PT 找到了没分配它的 frame
Shared Pages
略
Review Questions
Structure of the Page Table
Hierarchical Paging 分级页表
只用一个页表，在实际的实现中太大了，还得是连续的，不现实
Break up the logical address space into multiple page tables
Two-Level Paging Example
A logical address (on 32-bit machine with 4K page size) is divided into 20 bits page number & 10bits page offset
Since the page table is paged, the page number is further divided into 10-bit page number & 10-bit page offset
更高级的以此类推
Hashed Page Tables
Common in address spaces > 32 bits
The VPN is hashed into a page table, this page table contains a chain of elements hashing to the same location
VPNs are compared in this chain searching for a match
If a match is found, the corresponding physical frame is extracted
Inverted Page Table
倒置页表，反向页表
One entry for each real page of memory
Entry consists of the VA of the page stored in that real memory location, with information about the process that owns that page
例题
2^7 = 128
- 映射
- 页号和页内地址
- 页框号（PPN），有效位
- 内部碎片
- MMU，TLB，各种寄存器
- 高效使用内存