Computer Science 161

Instructions

Exam Policy Statement

1. True False (20 points)

Answer true if the statement is always true; otherwise answer false. If you feel that there is ambiguity and that affects your answer, feel free to explain your logic.

1. A uniprocessor with only single-threaded processes does not need synchronization.
2. Threads waiting on a CV will be granted the CV lock on a FIFO basis.
3. If a processor supports virtual memory, then it must have a TLB.
4. A drum served the same purpose as modern day harddrives.
5. The job of the operating system has always been to allow the hardware to be used as efficiently as possible.
6. Operating systems as an area of intellectual investigation arose in the 60's when it was an open question whether one could construct a layer of software that allowed hardware to be used efficiently.
7. Most of the types of problems identified in early operating systems have been solved today.
8. Loadable kernel modules are the modern-day solution to extensible operating systems, providing all the features that were desired by the extensible OS community.
9. The transition from user mode to supervisor mode requires hardware support.
10. It is possible to handle page faults without hardware support.

2. Short Answer & Multiple Choice (24 points)

Answer the following questions in as few sentences as necessary.

1. (5 points) On a trap, what information must the kernel save or figure out.
2. (5 points) You have been asked to design a TLB for a new processor. Your manager would like to understand the tradeoffs involved in deciding whether to implement a 2-way set associative TLB or a 16-way set associative TLB. What do you tell him/her? Which would you advise selecting for the design. (Assume that both TLBs will hold exactly the same number of mappings.)
3. (5 points) Jack and Jill are arguing about page replacement schemes. One of them claims that MRU -- replacing the most recently used page would be a monumentally stupid replacement policy. The other argues that if you focus only on data pages, then there are workloads for which it would be optimal. What do you think?
4. (5 points) You are writing a C program and you've created a nice clean design with a reasonably short main program and a small library implemented in a separate file. You want functions in both files to share a common, global debug parameter, so you put:

   extern int debug;
   

   in both files. Each file compiles cleanly by itself, but when you go to build your program, you get the error:

   Undefined symbols for architecture x86_64:
     "_debug", referenced from:
           _main in foo.o
   

   Why are you getting this error? Explain this first in high level terms and then in lower level detail referring to the various segments in which the debug variable is/is not defined.
5. (2 points) Which is true of a modern operating system kernel (select only one):
   1. The kernel code is always executing.
   2. The kernel only stores resource state, it does not execute code.
   3. The kernel code executes when the kernel process is scheduled.
   4. The kernel code executes in response to hardware interrupts and system calls.
   5. None of the above
6. (2 points) You have a bunch of CS161 students who are frantically writing code and periodically compiling it while the CS205 students are running a bunch of long simulations. Which scheduling algorithm would be best for the workload described? (select only one):
   1. FCFS
   2. Lottery Scheduling
   3. MLFQ
   4. Round Robin

   3. Synchronization (20 points)

   For each synchronization problem described below, select the best synchronization primitives to solve the problem. You may use each primitive as many times as you need to. Briefly (1-2 sentences), explain why you chose the primitive you did. Select the synchronization primitive from the following list:
   • Counting semaphore
   • Binary semaphore
   • Lock (w/out a CV)
   • Lock and condition variable
   1. A common problem in soccer collisions between players jumping for headers (this often leads to concussions). They've decided that clever CS161 students could easily solve this problem with a synchronization primitive that would arbitrate which player got to jump up for the header (such primitives would have to be very high performance). Which primitive would you suggest?
   2. Professor Seltzer was making pancakes for hungry teenagers. The pancakes come out in batches of three. She'd like a synchronization primitive that would allocate pancakes to teenagers without fighting. (There is no need to worry about leftovers between batches -- all pancakes are consumed pretty much instantly.) Suggestions?
   3. You are competing in a new Olympic event called a distributed relay. One team member has to run one lap at the Harvard track. The next team member must run a lap at the Yale track. The third team member runs a lap at Brown track and the last team member runs a lap at the Columbia track. Each runner must not start until the previous runner has completed his/her lap. Natually, the traditional passing of the baton or slapping of the hands won't work, so they've turned to you, as a savvy CS161 student, to provide the proper synchronization. What mechanism do you use?
   4. Competition for parking in Cambridge has become brutal due to the massive quantities of snow accumulating on our streets. The traditional use of space-savers (things like cones or lawn chairs that mark a spot as being "owned" because someone invested the physical labor in shoveling it out) has become too contentious and the Cambridge Department of Public Works is looking for a better solution. They've decided to have neighborhoods hand out parking tokens and any car without a visible token will be towed to the far reaches of the universe. Each neighborhood has a token checkin point and cars must drive to the checkin point to obtain a token for a specific spot and return a token when they leave a spot (cars that do not return tokens within seven minutes of leaving a spot are subject to enormous fines). They would like the checkin points to operate as efficiently as possible, allocating and deallocating spots in parallel as much as possible. What synchronization primitive(s) should they use?
   5. It is well known that graduate students (as well as many others) are motivated by free food. After the first couple of years (once classes are complete), a graduate student's day consists mostly of doing research and periodically checking email to determine if anyone has announced any free food lately. Unfortunately, the better research is going, the less likely students are to check email, and by the time they get to the location of the free food, it's often gone. (While they could configure their mail to alert them every time a new message comes in, most messages do not concern free food, so this would be quite distracting.) There must be a better way -- can you propose use of a synchronization primitive that would let them receive/see messages only when they concerned free food?

   4. Virtual Memory (18 points)

   Open RISC is a specification for a family of open-source, synthesizable RISC microprocessor cores. The OpenRISC 1000 MMU supports:
   • Both 32-bit and 64-bit address spaces.
   • Multiple page sizes.
   • Hardware support for page tables.
   • Context IDs (CID) that allow multiple processes to be translated by the hardware without changing hardware registers.
   32-bit address translation takes place as follows (depicted below):
   1. We form a 36-bit address by prepending the process's address with a four bit context ID.
   2. The top 23 bits of the 36-bit address form the virtual page number.
   3. The low 13 bits are the page offset.
   4. The CID and level 1 page index are used to index into an L1 Page Directory.
   5. The physical page number from the L1 Page Directory is added to the level 2 page index to form an index into the L2 Page Table.
   6. The physical page number from the L2 PTE is concatenated with the page offset to form a phyiscal address
   
   
   A page table entry is as shown:
   
   where:
   • Bits 0-3 indicate cache behavior (you can ignore them)
   • Bit 4 is an accessed (use) bit.
   • Bit 5 is a dirty bit.
   • Bits 6-8 indicate the page protection.
   • Bit 9 is a link bit and can be ignored for now.
   • Bits 10-31 are the physical page number.
   1. (2 points) What is the smallest page this architecture supports?
   2. (2 points) The hardware allows for treating this as a segmented architecture by ignoring the L2 page tables. In such a configuration, how large are segments?
   3. (2 points) What is the largest physical address you can construct using segments?
   4. (4 points) There are only 4 bits of Context ID -- is it possible to run more than 16 processes on this architecture? If so, how?
   5. (4 points) Although OpenRISC provides hardware support for page tables, it also allows software management. Name one thing that you could do using software management that you cannot do in the hardware.
   6. (4 points) Knowing only what you know about this architecture, how would you propose dealing with the operating system's memory management? Would you run it mapped? Unmapped? Why?