feb27-18.md

Feb 27 2018

Inverted Page Tables

• Index on frame number, not virtual address. 

Translation Lookaside Buffer

• Each virtual memory access can cause two physical memory addresses
  1. Fetch the page table entry
  2. Fetch the data
• Fix: add caches 

Steps

1. CPU checks TLB (Translation Lookaside Buffer)
2. Check page table entry in TLB?
   • If Yes, CPU generates physical address
   • If No, access page table and check if page is in main memory
     • If page is not found, raise page fault, read page from disk and transfer it to main memory
     • If page is found, CPU generates physical address, update the TLB

Page size

• Small Page Size
  • less internal fragmentation
  • more pages per process => larger page tables => large portion of page tables in virtual memory
  • more pages benefits from principal of locality => page faults low
• Large Page Size
  • secondary memory transfers larger blocks of data better
  • pages tend to be farther away from recent reference => higher page faults

Segmentation

• Allows programmer to view memory of multiple address spaces and segments
• Advantages
  • Simplifies handling of data structures by having one structure per segment
  • Allows programs to be altered and recompiled independently by having code and data contain their own segments
  • Shares data among processes by sharing a segment
  • Protection by protecting segments

Segment Tables

• Starting address corresponds to segment in main memory
• Each entry contains the length of the segment
• 2 bits are needed to determine if segment is in main memory and if it was modified since loading into main memory 

Combining Paging and Segmentation

• Each element contains a process, 1 segment table per process, 1 page table per segment
• Segment is visible to programmer, paging is transparent 

OS Designer needs to make 3 decisions:

1. Does the system need virtual memory?
2. Paging, segmentation, or both?
3. Which algorithms for memory management?
   • Fetch policy
   • Placement policy
   • Replacement policy
   • Cleaning policy
   • Load control

---

Fetch Policy

• Determines when a page should be brought into main memory
• Demand paging: only bringing pages into main memory when a reference is made to location on the page => lots of page faults in the beginning of process
• Prepaging: brings in more pages than needed to improve efficiency

Placement Policy

• Determines where in real memory a process piece is to reside
• Important when segmenting a system

Replacement Policy

• Determines which page to replace
• Should remove the page that is least likely to be referenced in the future -> principle of locality
• Frame locking
  • Restricts placement policy
  • If frame is locked, cannot be replace
  • Tracks locked/unlocked via lock bit w/each frame

Optimal policy

• Replaces the page where the time to the next reference is the longest
• Impossible to have perfect knowledge of future events

Least Recently Used (LRU)

• Uses principal of locality
• Replaces the page that has not been referenced for the longest time
• By principal of locality, this page is least likely to be referenced in the near future
• Performance is nearly as good as optimal algorithm
• Each page needs to be tagged with the time of last reference => overhead w/clock algorithms

First-in, first-out (FIFO)

• Page that has been in memory the longest is replaced
• Assumes old page will not be referenced soon again
• Pages are removed in a round-robin style
• Simplest to implement

Clock Policy (approximates LRU)

• Adds an additional bit, the "use bit"
• Use bit = 1 when page first loaded into memory
• Use bit = 1 when page is referenced
• When time to replace a page, first frame encountered with the use bit = 0 is replaced
• Each use bit = 0 when searching for a replacement 


Number of page faults in increasing order: OPT < LRU < CLOCK < FIFO