Please enable JavaScript.

Coggle requires JavaScript to display documents.

Paging (:dagger_knife:TLB (:heavy_dollar_sign:translate page number to…

- - - - :icecream:examples
        
        :one:Linux: four-level page table
        
        :two:Windows: two-level page table
      - :checkered_flag:解决page table可能过大的问题
        
        :zap:一个进程的逻辑地址空间时4GB,如果每个page的大小是4KB,那么总共要1M的页表项,并且每个页表项大小为4Bytes,那么总共要1MB的连续内存空间(用来当做page table),显然不合理
        
        :pushpin:页表项大小是4Bytes
        
        :apple:页表项
        
        :explode:page table里的每个元素,比如存储<page number, offset>
        
        :pencil2:calculation
      - :snowflake:break up the logical address space into multiple page tables
        
        :bread:如果程序需要4GB逻辑地址空间,而实际只需要12MB,这时我们假设1个page table=1K个页表项=(1K * 4K = )4MB,那么我们在二级页表的前提下,我们只需要4个page table就可以了(1个顶级页表 + 12 / 4 = 3 个内部页表)
        
        :arrow_right:4个page table实际占用4 * 4K = 16 KB内存,而如果一级页表肯定要占用4GB / 4K * 4B = 4M内存
        
        :arrow_right:节约内存
        
        :cherry_blossom:简单来说,就是允许把连续的4M空间给分散开来了
      - :dagger_knife:two-level page table
        
        :cherry_blossom:address reprensation
        
        :star: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
        
        :question:页表项的结构都是怎么样的?最左边的是不是划分成3个,而中间的还是2个
    - - :warning:物理内存越来越大,所有用途越来越小
      - :mega:哈希页表
      - :heavy_dollar_sign:page number => frame number
        
        :bread:page number => (hash function) => hashed value => (lookup page table) => page number
      - :question:Does the page table stores the hashed value and a chain of frame numbers?
        
        :question: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)
        
        :question:So one hashed value should not correspond to one chain?
    - - :cherry_blossom:principle
        
        :explode:pid + page number => frame number
      - :sweat_drops:searching is time-consuming
        
        :maple_leaf:hash table
      - :musical_note:decreases memory needed to store each page table
      - :poultry_leg: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?
        
        :palm_tree:An inverted page table :32
        
        :pencil2:\( 2^{16} / 2^{11} = 2^5 \)
        
        :bread:inverted的意思是原来是按logical page对page table的offset,而inverted paging是按physical page对page table的offset算的, 所以如果这个page table只需要表示"物理地址的frame个数"个entries就可以了
  - - - :radioactive_sign:page number / frame number
        
        :explode:编号,第几个page/frame
      - :moneybag:contents
        
        :one:subscript
        
        :explode:page number
        
        :two:content
        
        :one:frame number
        
        :two:valid-invalid bit
        
        :explode:A frame is valid if it is used in logical address space
    - - \( Where \)
        
        :explode:page table is kept in main memory
      - :moneybag:PTBR + PRLR
        
        :one:Page-table base register
        
        :explode:pointer to page table
        
        :two:Page-table length register
        
        :explode:the length of the page table
- - - - :star:includes page table & data / instruction
    - - :explode:percentage of times that a page number is found in the associative registers
  - - - :explode:\( EAT = \alpha (\epsilon + t) + (1 - \alpha) (\epsilon + t + t) \)
      - :bread:如果TLB中有page number,那么只要访问TLB和存储data/instruction的内存就可以了;而如果TLB中没有page number,那么需要访问TLB,存储page table的内存和存储data/instruction的时间
    - - :explode:\( EAT = t + t \)
- - - - :explode:the memory can store up to 32 bytes data
- - - - 是指logical address相同还是physical address相同