The set of pages which a process is currently using. Larger working set means that more of the process's pages need to be in memory; a small set means that the process is using only a few pages. Working set typically changes as a program runs.
Set page to 'not readable' (fault on read), and 'not writable' (fault on write).When a read fault occurs for the page, set the 'accessed' bit, mark the page as readable, and restart the faulted instruction.
When a write fault occurs, set both 'accessed' and 'dirty' bits, mark the page as readable and writable, and restart the instruction.
Uses the accessed bit and dirty bit as the MSB and LSB of a 2-bit priority number:Evicts pages with lower priority numbers first.
accessed dirty priority 0 0 0 0 1 1 1 0 2 1 1 3
(Context ID: value assigned to a process's address space to distinguish the same page numbers in different processes' address spaces in the TLB. The translation lookaside buffer matches virtual addresses on both page number and context ID.)
Advantage is that TLB does not need to be flushed on a context switch: just load a different context ID into the MMU's 'current context' register.
Bitmap: memory-efficient (only one bit overhead per allocation unit), but slow on allocation (must search for runs of consecutive 0 bits).
Linked-list: faster (than the bitmap method), but larger overheads (one list node per hole and per block). Must explicitly merge holes.
Advantages: memory-efficient (no list of allocated blocks), fast (only holes are searched).
Disadvantages: difficult to merge holes because the hole list is sorted in random order (deallocated blocks placed at the end of the hole list). (In fact the AmigaOS doesn't merge holes, sometimes leading to awful memory fragmentation.)
If the block's 'buddy' is also free, merge them (producing a block twice the size), and deallocate the merged block (remembering to remove the buddy from its free block list).
If the block's buddy is not on the free list, just add the block to the list.
The buddy of a block is a block which is adjacent and which, when combined with the block, produces a block twice the size, on an address which is divisible by the combined block size.
There is a different free block list for every (power of two) block size.