Section notes for CS162 
Section #10, April 9, 2002
Barbara Hohlt <hohltb@cs.berkeley.edu>

- Administrivia
  - New office hours Thur & Fri 10-11 443 Soda
  - Project 3 Initial Design Doc Tue 4/16 
  - Project 3 Design Reviews Thur 4/18 & Fri 4/19 
  - Project 3 Code Due Thur 4/25 

---------------------------------------------------------------------------
 PAGE REPLACEMENT IMPLEMENTATIONS 
---------------------------------------------------------------------------
 -LRU APROXIMATION ALGORITHMS 
  - Clock Page replacement algorithm
    - HW keeps use bit per page frame and sets on every reference
    - On page fault, advance clock hand, OS checks use bit
	1 ==> clear use bit, continue
	0 ==> replace page 
		
    - Keep looping until we get a free page
    - Note that if clock hand goes all the way around (because all
      pages marked as 'used'), then on next sweep through these pages
      will be evicted.

  - N Chance Page Replacement algorithm
    - HW keeps use bit per page frame and sets on every reference
    - OS keeps counter per page frame  - # of sweeps
    - On page fault, advance clock hand, OS checks use bit
	1 ==> clear use bit, clear counter, continue
	0 ==> increment counter, 
		if (counter < N) continue
		else replace page 

  - Second Chance List
    - Memory split into two parts
	- mapped - FIFO, marked r/w, directly accessible to program
	- unmapped - Second Chance List, LRU, marked invalid (but in memory)
    - On page fault, OS checks second chance list
	- if in SCL, 
		move page from SCL to end of FIFO 
		move page from head of FIFO to end of SCL 
		set bits
	- if not in SCL, 
		move page from disk to end of FIFO 
		move page from head of FIFO to end of SCL 
		move page form head of SCL to disk
		set bits

---------------------------------------------------------------------------
   VIRTUAL MEMORY AND PROJECT 3
---------------------------------------------------------------------------
GOOD READING ON VIRTUAL MEMORY
    - "Virtual Memory Management in the VAX/VMS Operating System", 
	H.M. Levy, and P.H. Lipman. 
	IEEE Computer. Vol. 15, No. 3 (March 1982), pp. 35-41. 

SOFTWARE-MANAGED TLB
  - Processor no longer sees page tables
  - Rather, it manages a (small) TLB: an array of type TranslationEntry 
      int vpn
      int ppn
      boolean valid
      boolean readOnly
      boolean used
      boolean dirty
    (Size of TLB is only 4 entries!)
  
  - private TranslationEntry[4] translations in Machine.processor
  - On each memory reference, MIPS processor looks in TLB for matching
    entry and uses it if present
     - entry.vpn must be same as requested vpn, and entry.valid must be set
     - If no entry or not valid, an 'exceptionTLBMiss' is generated by 
	the processor
     - If attempting to write and page is readOnly, an 'exceptionReadOnly'
       is generated
         --> Nothing you need to do about this but cleanly kill the process
     - Sets entry.used and entry.dirty (if writing)

  - For this project you will use a global INVERTED PAGE TABLE:
      - Maps <process ID, vpn> to ppn
      - OK to use standard java.util.Hashtable (but don't depend on its
        synchronization properties!)

  - Dealing with a TLB miss
      - Get faulting vaddr from processor register
      - Look in inverted page table for ppn
      - Find invalid TLB entry (scan TLB)
        - If none, simply overwrite a random TLB entry
      - Write ppn to TLB entry 

  - On context switch
      - Just set all TLB valid bits to false!

DEMAND PAGING
  - Simulate much larger physical memory by using disk as backing store
  - Move contents of memory to/from disk as necessary to provide this
    illusion -> totally transparent to applications

  - Basic idea:
     - TLB miss causes lookup in page tables to find translation
     - If not in the inverted page table...
        - Try to allocate a free page
	- If no free pages, choose a page for eviction 
	  (This is where the clock algorithm comes in)
        - If evicted page is not dirty, just reuse it
	- If evicted page is dirty, write it to the swap file
	- Read faulting page in from swap file
	- Set valid bit of entry to true
	- Write entry to TLB
	- Return from TLB miss

  - Issues
    - Core map - The clock algorithm runs through page frames, so 
	need ppn -> vpn mapping
    - Since the global page table only contains pages that are
	actually in physical memory, must maintain a separate data
	stucture for locating pages in swap
    - What if a page is in use by another process/thread?
    - I.e. we are doing a memory copy to/from the page, or loading it
      from disk?
    - Need to ensure these pages are not touched during page replacement
      - Page "pinning": keep it locked in physical memory for a short
        amount of time
    - What happens if all pages are "pinned" during sweep?
      - Need to sleep until page is no longer "pinned"

  - Format of swap file
    - Start out with a zero-length file
    - Every time we need new space, just grow swap file by one page
    - Reuse free pages (maintain linked-list of free entries)
    - When writing to swap: Find empty swap file page and write
      memory page to it, reset page table entry 
    - When reading from swap: Find swap page number, read swap page 
	into memory, reset page table entry

EVALUATION
  - Evaluation of Page-Replacement Algorithm 
    - Collect stats about page faults
    - Compare your page replacement policy with random 

---------------------------------------------------------------------------
  DISK ARM SCHEDULING
---------------------------------------------------------------------------
- If there is a group of requests to a disk we want to select
  the best order to process.
- FIFO - server requests in order of arrival
- SSTF - shortest seek time first. Go to nearest request
	to current head position (greedy algorithm)
- SCAN - move arm in one direction, servicing requests until 
	it reaches the other end of the disk, then reverse direction and do
	the same thing (elevator algorithm)
- CSCAN - (circular scan) service request only in one direction to
	the end of the disk. Then return arm to beginning of the disk 
- LOOK - Same as SCAN but does not move all the way to the end of the disk
- C-LOOK - Same as CSCAN but does not  move all the way to the end of the disk
 
- Very good exam question would be to demonstrate the order of
  I/O requests processed by different disk scheduling algorithms,
  and characterize the seek time for each approach.

Say we have pending I/O requests at the following tracks:

12 31 7 40

Also assume the disk has 128 tracks (numbered 0-127). Say that the disk 
head starts out at track 0. What is the order and seek time (measured in
number of tracks seeked) for each of the following disk scheduling algorithms?

FIFO:

0      12      31      7      40
  (12)    (19)    (24)   (33)     = 88 seek time

SSTF:

0     7     12      31     40
  (7)   (5)    (19)    (9)        = 40 seek time

SCAN: (Start the disk head at track 15, going down):

15     12     7     0      31     40 
   (3)    (5)   (7)   (31)    (9)     = 55 seek time

CSCAN: (Start the disk head at track 10, going up):

10     12      31     40      127        0     7
   (2)    (19)    (9)    (87)      (127)   (7)   = 251 seek time

LOOK: (Start the disk head at track 15, going down):

15     12     7      31     40 
   (3)    (5)   (24)    (9)     = 41 seek time