Stanford University Computer Science Department CS 140 Final Exam Dawson Engler Winter 1999Name: __________________________________Please initial the bottom left corner of each page.This is an open-book exam. You have 120 minutes to answer as many questions as possible. Thenumber in parenthesis at the beginning of each question indicates the number of points given tothe question. Write all of your answers directly on the paper. Make your answers as concise aspossible. Sentence fragments ok.Stanford University Honor Code:In accordance with both the letter and the spirit of the Honor Code, I did not cheat on this exam.Signature: ____________________________________________Problem Points Score1-4 165-7 228-9 2510 2011 2712-13 38Total 148True False QuestionsEach question is worth 4 points. Please answer each question as true or false and concisely state the intuition behind your answer.1) Without “free” (deallocate) it is easy to write a “malloc” implementation that never fragments memory.(True/false)2) You run a workload using a fixed-size 1 MB (megabyte) buffer cache and notice that there are manydisk references. If you repartition main memory to increase the buffer cache size to 2 MB, theworkload may actually run significantly slower. (True/false)3) You profile your file system and notice that over the course of the day the system used 6200 files,whose total size in bytes was 100 times larger than the size of the file system’s buffer cache. A cachecannot provide much benefit for this type of workload. (True/false)4) You install new network hardware that you’ve purchased from a “MORE BITS NOW!!!” infomercial.Unfortunately, you notice that packets arrive out of order much more frequently than on it than on theold network. The new network is more likely to be connection-based rather than connection-less.(True/false)Short Answer questions5) [6 points] You conceive of a get-rich scheme of retrofitting virtual memory onto old governmentcomputers. To save time, you base your virtual memory system on the MIPS architecture, whichwhen a TLB fault occurs, does the following three actions:1). Writes the program counter of the faulting instruction into the special register “epc.”2). Writes the faulting virtual address into the special register “badva.”3). Changes to privileged mode and transfers control to a kernel TLB handler.If a translation for badva exists, the OS installs it and jumps to the program counter value held in epc. If notranslation exists, the OS signals an exception. What problem do actions (1) and (2) cause for “mapped”page tables? (I.e., page tables that are mapped using virtual memory.)6) [6 points] Recall that we can enforce security policies using either technical mechanisms (e.g., lockson doors) or social mechanisms (e.g., laws against stealing). The Stanford Honor code is an exampleof a social mechanism used to enforce a security policy. State two assumptions that the Honor Codemakes that a technical approach would not need. (Hint, consider why leland requires passwords.) Insituations where these assumptions are valid state an attack it prevents that a more technical approachwould have difficulty with.)7) [10 points] Consider the following switch attached to a single 100MB/s incoming link and a single100MB/s outgoing link.a) [5 points] If we view incoming packets as jobs, and the switch as a processor, what CPU algorithmdoes the above system correspond to?b) [5 points] What weakness of that scheduling algorithm do you expect to see replicated here? Whatpacket feature can you control to minimize this problem? switch100 MB/SecMBMB/SecMB/sec100 MB/SecMBMB/SecMB/secAB8) [15 points] Threads on a new multithreaded WWW browser periodically query a nearby WWW serverto retrieve documents. On average, a browser’s thread performs a query every N instructions. Eachrequest to the server incurs an average latency of T milliseconds before the answer is received.a) [5 points] For N = 2,000 instructions and T = 1 millisecond, what is the smallest number of suchthreads that would be required to keep a single 100 MIPS processor (i.e., executing 100 millioninstructions per second) 100% busy? Assume the context switch time is instantaneous and that thescheduler is optimalb) [5 points] Unfortunately, context switches are not instantaneous. Assume that a context switch takes Cinstructions to perform. Recalculate your answer to part (a) for C = 500 instructions.c) [5 points] Excited by your calculations, you add threads to your system. However, system throughputimproves by a much smaller amount than part (b) would suggest. Give two features of a computersystem that could be the reason for this dismal outcome.9) [10 points] You have written a mark and sweep garbage collector for use on a single processormachine. The collector is woken up once a second by a timer interrupt and:1) Disables all interrupts.2) Finds all active memory.3) Compacts memory into a two contiguous address ranges, where one range holds all free memory,the other all allocated memory4) Sets malloc’s global heap pointer to point to the new range of free memory.5) Reenables interrupts.a) [5 points] Assume only one garbage collection thread can run at a time and the application is singlethreaded. Does the locking discipline in the following code guarantee mutual exclusion for the global heappointer? (Why or why not?) int lock; void *heap; void *malloc(unsigned nbytes) { /* … */ lock = 1; heap = (char *)heap + nbytes; lock = 0; /* … */ } void initiate_gc(void) {if(lock)return; /* find free memory */heap = new_heap; /* reset heap */}b) [5 points] A program that formerly paged heavily runs significantly faster when your garbage collectoris used. What is a likely reason for this? (Assume that you have determined that the program does notleak memory.)10) [20 points] Suppose the longest packet you can transmit on the Internet can contain 480 bytes ofuseful data, you are using a lock-step end-to-end protocol, and you are sending data from California toyour geeky cousin at MIT (go team). You have measured the round-trip delay and found that it isabout 100 milliseconds. (A lock-step protocol is one where you must wait for the recipient to send anacknowledgement of
View Full Document
Unlocking...