‌The University of Texas at Austin‌

CS 372H Introduction to Operating Systems: Honors: Spring 2010 FINAL EXAM

• This exam is 3 hours. Stop writing when “time” is called. You must turn in your exam; we will not collect them. Do not get up or pack up in the final ten minutes. The instructor will leave the room 3 hours and 3 minutes after the exam begins and will not accept exams outside the room.

• There are 28 questions in this booklet. Many can be answered quickly. Some may be harder than others, and some earn more points than others. You may want to skim all questions before starting.

• This exam is closed book and notes. You may not use electronics: phones, PDAs, calculators, etc. You may refer to TWO two-sided 8.5×11” sheet with 10 point or larger Times New Roman font, 1 inch or larger margins, and a maximum of 60 lines per side.

• If you find a question unclear or ambiguous, be sure to write any assumptions you make.

• Follow the instructions: if they ask you to justify something, explain your reasoning and any im- portant assumptions. Write brief, precise answers. Rambling brain dumps will not work and will waste time. Think before you start writing so you can answer crisply. Be neat. If we can’t understand your answer, we can’t give you credit!

• To discourage guessing and brain dumps, we will, except where noted, give 25%-33% of the credit for any problem left completely blank. If you attempt a problem, you start at zero points for the problem. Note that by problem we mean numbered questions for which a point total is listed. Sub- problems with no points listed are not eligible for this treatment. Thus, if you attempt any sub- problem, you may as well attempt the other sub-problems in the problem.

• The exception is the True/False problems. There, we grade by individual True/False item: cor- rect items earn positive points, blank items earn 0 points, and incorrect items earn negative points. However, the minimum score on any question—that is, any group of True/False items—is 0. Don’t overthink all of this. What you should do is: if you think you might know the answer, then answer the problem. If you know you don’t know the answer, then leave it blank.

• Don’t linger. If you know the answer, give it, and move on.

• Write your name and UT EID on this cover sheet and on the bottom of every page of the exam.

Do not write in the boxes below.

1. Interrupts, concurrency, scheduling (12 points total)

   1. [2 points] What are the three ways that a CPU executing in user mode (that is, executing instructions from a user-level process) can switch to supervisor mode (and presumably execute kernel instructions)? (Hint: we have discussed this question in class, using the phrase, “What are the three ways that the kernel gets invoked?”)

      1. Interrupts from a device.

      2. Traps, often used for invoking system calls. Confusingly, on the x86, the int instruction gener- ates traps.

      3. Exceptions, such as divide by zero, illegal memory access, or execution of an illegal opcode.

   2. [2 points] Pat Q. Hacker from the midterm is back. Pat gets a job writing an operating system. Pat is told by the company’s marketing department that the kernel needs to be correct only on a machine with a single CPU. Pat’s manager imposes a further requirement: it is unacceptable to write a kernel in which hardware interrupts are always disabled (this manager really dislikes the approach that JOS takes). Given these requirements, Pat decides to leave interrupts on all the time. Pat’s kernel has data shared between the device interrupt handlers (meaning the code that runs when an external I/O event happens) and other kernel code. Pat reasons that no special steps to protect this shared data are needed because a single CPU can do only one thing at a time.

      State whether Pat’s reasoning is correct, and justify your answer briefly below:

      Pat’s reasoning is incorrect. If Pat’s kernel code is interrupted, then the interrupt handler might run and invalidate an invariant (for example, imagine that the other kernel code is fixing up a linked list, and the interrupt handler needs to enqueue to this linked list). To get around this, Pat needs to protect data that is shared between the interrupt handlers and other kernel code. To do so, Pat probably needs to disable interrupts when messing with data that the interrupt handler also modifies. Doing so ensures the invariant that if the interrupt handler is modifying the data, then the other kernel code is not (and vice-versa).

   3. [8 points] In this problem, you will implement a monitor to help a set of drivers (modeled as threads) synchronize access to a set of five keys and a set of ten cars. Here is the problem setup:

      • The relationship between the keys and the cars is that key 0 operates cars 0 and 1, key 1 operates cars 2 and 3, etc. That is, key i works for cars 2i and 2i + 1.

      • If a key is being used to operate one car, it cannot be used to operate the other.

      • A driver requests a particular car (which implies that the driver needs a particular key). However, there may be many more drivers than cars. If a driver wants to go driving but cannot get its desired car or that car’s key, it waits until the car and key become available. When a driver finishes driving, it returns its key and notifies any drivers waiting for that key that it is now free.

      • You must allow multiple drivers to be out driving at once, and you must not have busy waiting or spin loops.

      • We repeat: there could be many, many instances of driver() running, each of which you can assume is in its own thread, and all of which use the same monitor, mon.

      On the next page, fill in the monitor’s remaining variable(s) and implement the monitor’s

      take key() and return key() methods. Follow the coding standards given in class.

      typedef enum {FREE, IN_USE} key_status; class Monitor {

      public:

      Monitor() { memset(&keys, FREE, sizeof(key_status)*5); }

      ~Monitor() {}

      void take_key(int desired_car); void return_key(int desired_car);

      private:

      Mutex mutex; key_status keys[5];

      /* YOU MUST ADD MATERIAL BELOW THIS LINE */

      };

      void driver(thread_id tid, Monitor* mon, int desired_car) {

      /* you should not modify this function */ mon->take_key(desired_car);

      drive();

      mon->return_key(desired_car);

      }

      void Monitor::take_key(int desired_car) {

      /* YOU MUST FILL IN THIS FUNCTION. Note that the argument refers to the desired car. */

      }

      void Monitor::return_key(int desired_car) {

      /* YOU MUST FILL IN THIS FUNCTION. Note that the argument refers to the desired car. */

      }

      /* easiest way to extend monitor is with just a single condition variable (could also have one condition variable for each key) */

      class Monitor {

      …..

      Cond cond;

      };

      void Monitor::take_key(int desired_car)

      {

      int which_key = desired_car / 2; acquire(&mutex);

      while (keys[which_key] != FREE) { wait(&mutex, &cond);

      }

      keys[which_key] = IN_USE; release(&mutex);

      }

      void Monitor::return_key(int desired_car)

      {

      int which_key = desired_car / 2; acquire(&mutex);

      keys[which_key] = FREE; cond_broadcast(&mutex, &cond); release(&mutex);

      }

2. Virtual memory and paging (13 points total)

1. [2 points] Circle True or False:

   True / False A virtual memory system that uses paging is vulnerable to external fragmentation.

   False. Paging provides fine-grained allocation of memory, so the only fragmentation that can happen is wastage within a page, which is internal fragmentation.

2. [9 points] Consider a 32-bit computer with the following funky virtual memory architecture:

   • Each page is 2KB (211 bytes).

   • Physical memory is 32 GB (235 bytes). Note: that is not a typo; we do not mean 232 bytes.

   • Associated with each virtual page are 7 bits in the page table, including control and reserved bits. The exact nature of these bits is unimportant for this question. For completeness, they are: three bits controlled by the kernel (PTE_P, PTE_U, and PTE_W); 2 bits controlled by the hardware (Accessed and Dirty); and 2 bits reserved for the kernel (for example, PTE_COW).

   • The machine has a two-level page table structure analogous to the one used in JOS: each process has a page directory, each entry of which points to a page table. Each entry in the page directory has the same number of control and reserved bits as a page table entry.

Below, state the minimum number of bits in a second-level page table entry, and explain briefly:

31 bits. There are 235 bytes of memory and 211 bytes/page, which means there are 224 pages in the machine. That means that the second-level page table has to have at least 24 bits (to be able to select the physical page). Then there are 3 + 2 + 2 = 7 further bits per page, so we need at least 24 + 7 = 31 bits per entry.

Below, state the minimum number of bits in a page directory entry, and explain briefly:

31 bits, again. The reason is the same. The page directory entries need to be able to “resolve” 224 bits since a page table could conceivably live on any physical page. Further, we are given that the number of control and reserved bits is the same in a page directory entry.

Now assume that the entry size is rounded up to the nearest multiple of 4 bytes. Further assume that a page directory or page table must fit on a page. Programs on this machine use 32-bit quantities as instruction operands, but when the operand is an address, not all of these 32 bits are examined by the processor. How many address bits are actually used in this architecture?

29 bits. A page table entry is 4 bytes (per the padding), and a page table is 2KB (because it needs to fit on a page). Thus, a page table can have no more than 512 (29) entries, which means that no more than 9 bits are used to index into the page table. Same for the page directory. Finally, since a page is 2KB, 11 bits of the address determine the offset into the page. Altogether, this is a maximum of 9 + 9 + 11 = 29 bits of address in use.

How large is the per-process virtual memory space?

512 MB only. That is because a process can use only 29 bits of addresses, and 229 = 512 MB. Note that on modern 32-bit x86s, something similar happens: each process gets 232 bytes of virtual address space, but the machine can actually have more physical memory than that.