Operating Systems I

Tutorial 6

1. What is the meaning of the term 'working set'?

   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.

2. Describe how an OS might simulate 'accessed' and 'dirty' bits for a page, if the hardware does not directly support them.

   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.

3. Say how the NRU (Not Recently Used page replacement algorithm) uses the accessed and dirty bits to decide which pages to evict.

   Uses the accessed bit and dirty bit as the MSB and LSB of a 2-bit priority number:

   accessed	dirty	priority
   0	0	0
   0	1	1
   1	0	2
   1	1	3

   Evicts pages with lower priority numbers first.

4. What would be the advantage in a memory management unit supporting 'context IDs' for processes' address spaces?

   (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.

5. What are the respective pros and cons of bitmap and linked list memory allocation schemes?

   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.

6. The Amiga OS uses the linked-list method of heap allocation. It uses a single list of memory holes. It does not explicitly keep track of allocated memory, but when memory is deallocated, a new hole is created, and added to the end of the list of holes. Think of one advantage and one disadvantage of this method.

   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.)

7. What happens to a memory block in the buddy system when it is deallocated?

   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.