Quiz 7

This quiz covers Chapter 6 of Tanenbaum. Please allow yourself up to 1 hour to take the quiz, and return it to me by 10:00 AM, Tuesday, Novermber 11, if you would like for me to mark it. I will post my answers via the course homepage later that day.

You're the system administrator for a box where you have a choice as to whether the operating system uses a bitmap or hole list for keeping track of which sectors of a disk are allocated or not. You are installing a disk which has 980 cylinders, 2 tracks, and 32 sectors, each with 512 bytes.
1. How many sectors are on the disk?
  980 * 2 * 32 = 62720
2. How many bits wide would you make each entry in the hole list?
  Since the number of sectors can be represented in 16 bits, we could represent each hole as a 16-bit start sector and 16-bit end sector, or a 16-bit start sector and a 16-bit length. In either case, a 32-bit entry would suffice. In the case of a sector number, we might use the high order 10 bits for the cylinder, the next bit for the track, and the final 5 bits for the sector number.
3. The disk will be used to store web documents. The average file size is about 2 Kbytes, and from prior experience you know that file creation time gets precipitously worse when the disk is about 80% full. Assuming that you'll stay under the 80% limit, which approach (bitmap or hole list) will use the least amount of space leaving the largest amount of room for documents?
  The bitmap approach will require 62720 bits (7840 bytes).
  The total space available is 62720 sectors. If only 20% of this is to be reserved for free space, then we would consider the worse case to be 62720 * 20% = 12544 individual sectors separating the free space from the allocated sectors. 12544 holes * 4 bytes (32 bits) per hole = 50176 bytes. Clearly, the bitmap approach would require less space.
You're a team leader for a project at amazon.com in which there are 5 processes (P1-P5) which handle incoming book orders, and 3 processes (P6-P8) which process orders and send e-mail to confirm the order. You've just been given a new staff of bright but inexperienced programmers and you're trying to explain to them how semaphores are used to coordinate the activities of the two sets of processes. You decide an example would be best.
Indicate the state of each of the 8 processes (Running or Sleeping) after each of the following operations. Assume that the semaphore has a value of 0 at the start, and that all processes are running, and that the left-most process is wakened if there are multiple sleeping processes and a process needs to be restarted.
1. P6 issues a DOWN
  P6 sleeps
2. P7 issues a DOWN
  P7 sleeps
3. P1 issues an UP
  P6 wakes
4. P5 issues an UP
  P7 wakes
5. P3 issues a DOWN
  P3 sleeps
6. P4 issues a DOWN
  P4 sleeps
7. P2 issues a DOWN
  P2 sleeps
8. P8 issues an UP
  P2 wakes
9. P8 issues an UP
  P3 wakes
10. P8 issues an UP
  P4 wakes
Explain the difference between a protection fault, segment fault, and page fault in virtual memory operations.
With a protection fault, the type of operation (usually read, execute, write) is not one of the allowed operations for the particular page being requested. With a segment fault, the segment in which the page is located is not present in memory (i.e., swapped out). With a page fault, the requested page is not present in memory (i.e., paged out).
Explain the difference between fragmentation and checkerboarding in virtual memory operations.
According to Tanenbaum, fragmentation is the effect of memory which remains un-used due to the page size. If n+1 bytes are needed for an allocation, and the allocation unit (page size) is n, then two units are required, even though n-1 bytes are "wasted". Checkerboarding is the effect caused by repeated allocation and de-allocation resulting in allocated space separated by unallocated spaces. We say that the free space is "checkerboarded".
Explain the difference between FIFO and LRU as page replacement algorithms in virtual memory operations.
A First In First Out (FIFO) page replacement algorithm keeps track of which pages were requested in which order. If a request for a page finds that the page is not in memory, then the "oldest" page in memory is purged, and the new page is used in its place.
A LRU (Least Recently Used) page replacement algorithm keeps track of which pages were used most recently. If a request for a page finds that the page is not in memory, then the page which was used least recently is purged, and the new page is loaded in its place.