Paging
🍍Paging
🗡page table
🏛structure
1⃣Hierarchical Paging 分级页表
🍦examples
2⃣Hashed Page Tables
⚠物理内存越来越大,所有用途越来越小
📣哈希页表
3⃣Inverted Page Table 反向(反置)页表
💲translate page number to frame number with offset remaining unchanged
🌸theory
1⃣How to work
☢page number / frame number
💥编号,第几个page/frame
💰contents
1⃣subscript
💥page number
2⃣content
1⃣frame number
2⃣valid-invalid bit
💥A frame is valid if it is used in logical address space
2⃣implemetation
\( Where \)
💥page table is kept in main memory
💰PTBR + PRLR
1⃣Page-table base register
💥pointer to page table
2⃣Page-table length register
💥the length of the page table
☢concepts
1⃣frames帧, 页框
💥divide physical memory into fixed-sized blocks called frames
🍦Linux & Windows for x86: 4K
2⃣pages页
💥divide logical memory into same size called pages
🍦example
☢concepts
1⃣32-bytes memory
💥the memory can store up to 32 bytes data
➡logical address content
💥<page number, page offset>
⚠generated by CPU
➡2 memory accesses
1⃣page table
2⃣data / instruction
🗡TLB
💲translate page number to frame number with offset remaining unchanged
🔥special fast-lookup hardware cache
Some TLBs store address-space identifiers (ASIDs) in each TLB
entry – uniquely identifies each process to provide address-space
protection for that process
also called associative memroy
✏Effective Access Time
📌suppose
1⃣associative lookup = \( \epsilon \) time unit(TLB访问时间)
2⃣memory cycle time(内存访问时间) is t
⭐includes page table & data / instruction
3⃣Hit ratio \( \alpha \)
💥percentage of times that a page number is found in the associative registers
🍁calc
1⃣with TLB
💥\( EAT = \alpha (\epsilon + t) + (1 - \alpha) (\epsilon + t + t) \)
🍞如果TLB中有page number,那么只要访问TLB和存储data/instruction的内存就可以了;而如果TLB中没有page number,那么需要访问TLB,存储page table的内存和存储data/instruction的时间
2⃣without TLB
💥\( EAT = t + t \)
🍦example
🍎shared pages
1⃣shared codes
🔥read-only
❓Shared code must appear in same location in the logical address space of all processes
是指logical address相同还是physical address相同
2⃣private code and data
🔥separate copy of the code & data
🌸paging with TLB + page table
🏁解决page table可能过大的问题
⚡一个进程的逻辑地址空间时4GB,如果每个page的大小是4KB,那么总共要1M的页表项,并且每个页表项大小为4Bytes,那么总共要1MB的连续内存空间(用来当做page table),显然不合理
📌页表项大小是4Bytes
❄break up the logical address space into multiple page tables
🗡two-level page table
1⃣Linux: four-level page table
2⃣Windows: two-level page table
🌸address reprensation
⭐the outer page table is the one we call page table if we do not apply hierarchical paging. && PBTR + PRLR stores the information of page table => the register only needs to store logical address itself
💲page number => frame number
🍞page number => (hash function) => hashed value => (lookup page table) => page number
❓Does the page table stores the hashed value and a chain of frame numbers?
❓How do we know if a frame in the frames is the one we query since we only knows the hashed value?(given that one hashed value corresponds exactly one chain of frames)
❓So one hashed value should not correspond to one chain?
🌸principle
💥pid + page number => frame number
💦searching is time-consuming
🎵decreases memory needed to store each page table
🍁hash table
🍎页表项
💥page table里的每个元素,比如存储<page number, offset>
🍞如果程序需要4GB逻辑地址空间,而实际只需要12MB,这时我们假设1个page table=1K个页表项=(1K * 4K = )4MB,那么我们在二级页表的前提下,我们只需要4个page table就可以了(1个顶级页表 + 12 / 4 = 3 个内部页表)
➡4个page table实际占用4 * 4K = 16 KB内存,而如果一级页表肯定要占用4GB / 4K * 4B = 4M内存
➡节约内存
🌸简单来说,就是允许把连续的4M空间给分散开来了
❓页表项的结构都是怎么样的?最左边的是不是划分成3个,而中间的还是2个
🍗The BTV operating system has a 21-bit virtual address, yet on certain embedded devices, it has only a 16-bit physical address. It also has a 2-KB page size. How many entries are there in each of the following?
🌴An inverted page table :32
✏\( 2^{16} / 2^{11} = 2^5 \)
🍞inverted的意思是原来是按logical page对page table的offset,而inverted paging是按physical page对page table的offset算的, 所以如果这个page table只需要表示"物理地址的frame个数"个entries就可以了