Converting a Swap-Based System to Do Paging in an Architecture Lacking Page-Referenced Bits

Problem

	Berkeley guys wanted to make their Unix on VAX-11/780(VMS) a paging system
	VAX-11/780 supports paging (has page table and valid bit) but does NOT have reference bit

Goal

Implement a page replacement algorithm such as LRU or Clock which needs to use reference bit

How to simulate reference bit

	Reference bit unset: unset valid bit -> the page becomes reclaimable valid bit = false, but page is still in memory and its content is same as that in disk
	Reference bit set: a reference to the page is made -> page fault -> handler recognize that the page is in reclaimable state -> handler sets the valid bit and not brings the page from disk
	Reference bit simulation is a lot slower than hardware implementation -> Page replacement should consider this fact -> simple and efficient policy!

Page Replacement Policy: Modified Global Clock!

	Partition frames into a free pool of pages and pages being involved in the loop of clock
	The size of the free pool drops below threshold -> Clock policy is triggered
	Also scan rate is controlled based on the amount of free pages Clock algorithm scans pages at the default rate(100 pages/sec) The size of the free pool drops further -> Scan rate increase up to the maximum rate The max scan rate is set so that at most 10% of CPU time is used by clock scanning

The Advantage of Modified Global Clock

	Simple & fast
	Load control can get a hint from the size of the free pool
	Writing dirty pages back to disk distributes uniformly over time due to scan rate control

Changes to Swap-based System

	Address space copying at the time of fork could be very expensive <- some pages could be in disk => Copy-on-write or vfork is a solution. vfork is taken in this case
	Pages of the process are brought into memory on demand

Load Control

	Swap-out criterion: the oldest amongst the n largest processes Large process: make more room Oldest: fair scheduling. Note that this is different from short-term scheduling
	Swap-in criterion: the smallest job first with aging
	Swap-in does not bring pages of the process. Pages will get brought into memory on demand

Pre-Paging and Clustered Cleaning

	When a page is brought into memory, adjacent blocks are pre-paged The referenced page is added to the clock loop Pre-paged blocks are added to the tail of free pool
	The set of modified pages are clustered and cleaned together Pages are placed at adjacent blocks of swap area

Evaluation

Pros It is proven that global clock is efficient enough that it could run effectively even on the system without reference bit The idea of free pool, pre-paging, and clustered cleaning are good vfork is first introduced