羅左欣 BE STRONG TO BE USEFUL

20170601 [學習筆記] Linux 系統程式 (13)


一、作業系統

(一) 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 find N 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

(三) 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 page
    • invalid 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

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

Similar Posts

Comments