Paging

-
  • A page is a sequence of N bytes where N is a power of 2.
  • Let's assume that we have 1M of RAM. RAM is also called physical memory.
  • We can subdivide the RAM into 4K pages. Thus 1M / 4K = 256 pages. 
  • Thus, our RAM has 256 physical pages, each holding 4K.
Fig 1: Address translation from virtual to physical

Page Table

How is an address translated from virtual to physical?
Fig 2: Page Table

  • First, like the cache, we split up a 32 bit virtual address into a virtual page (which is like a tag) and a page offset.
  • We must convert the virtual page number to a physical page number.
For example,
  • The virtual page consists of 20 bits. 
  • A page table is a data structure which consists of 220 page table entries (PTEs). 
  • The page table as an array of page table entries, indexed by the virtual page number.
  • The page table's index starts at 0, and ends at 220 - 1.
  • Suppose your program generates a virtual address. You'd extract bits B 31-12 to get the virtual page number. 
  • Use that as an index into the above page table to access the page table entry (PTE).
  • Each PTE consists of a valid bit and a 20 bit physical page (it's 20 bits, because we assume we have 1M of RAM, and 1M of RAM requires 20 bits to access each byte). 
  • If the valid bit is 1, then the virtual page is in RAM, and you can get the physical page from the PTE. 
  • This is called a page hit, and is basically the same as a cache hit.
  • If the valid bit is 0, the page is not in RAM, and the 20 bit physical page is meaningless.
  • This means, we must get the disk page corresponding to the virtual page from disk and place it into a page in RAM. This is called a page fault.

Comments

Post a Comment

Popular posts from this blog

Pentium microprocessors

-
Image
A 32-bit microprocessor introduced by Intel in 1993. It contains 3.3 million transistors. Since 1993, Intel has developed the Pentium III and more recently the Pentium 4 microprocessors.   Pentium III Pentium III Mainboard Layout Intel builds on the technology it developed with the Pentium II microprocessors.  The Pentium III processor comes with a Synchronized Dynamic Random Access Memory (SDRAM), allowing for an extremely fast transfer of data between the microprocessor and the memory. 70 new instructions, called Streaming SIMD Extensions, enhance multimedia and 3D performance.  Launched February 1999 - Available in speed levels of 450, 500, 550, and 600MHz. 32KB of Level 1 Cache (operating at CPU's full core speed). 512KB of Level 2 Cache (operating at ½ of CPU's core speed). 100 MHz bus speed. The branch prediction/recovery pipeline was doubled to include 10-stages from the P-II.   Pentium IV The next generation of microprocessors from Intel. Pe
Read more

Multilevel Organization of Cache Memory

-
Image
A multilevel cache hierarchy consists of n levels of caches. C1, C2, .......,Ci,....... Cn. A processor reference is serviced by the cache closest to the processor that contains the data.  At the same time that cache provides information to the caches on the path between itself and the processor. Multilevel cache hierarchy for multi- processors neither a local LRU nor a global LRU. Where all references to a Ci cache are percolated to its parent for rear-ranging the LRU stack at the Ci+i level. Multilevel caches Another issue is the fundamental tradeoff between cache latency and hit rate.  Larger caches have better hit rates but longer latency. To address this tradeoff, many computers use multiple levels of cache, with small fast caches backed up by larger, slower caches. Multi-level caches generally operate by checking the smallest level 1 (L1) cache first. If it hits, the processor proceeds at high speed.  If the smaller cache misses, the next larger cache (L2) is c
Read more