Department of Electrical Engineering and Computer Science MASSACHUSETTS INSTITUTE OF TECHNOLOGY 6 824 Fall 2002 Midterm Exam Answers The average score was 55 out of 80 Here s the distribution 10 Number of Students 8 6 4 2 0 0 10 20 30 40 Score 50 60 70 80 6 824 Fall 2002 Midterm Exam Answers Page 2 of 10 I Interaction of Architecture and O S Design 1 10 points Look at the paper The Interaction of Architecture and Operating System Design by Anderson et al The authors discuss two worrying trends First that the performance of new microprocessors is relatively worse for O S code than for application code Second that new operating systems perform less well than old operating systems Suppose I spend most of my time using latex to format 150 page documents I upgrade from a CVAX microprocessor running Mach 2 5 to an R3000 running Mach 3 0 The R3000 s manufacturer claims that it runs applications 6 7 times faster than the CVAX see the bottom row of Table 1 in the paper However I find that my new setup runs my latex jobs only X times faster where X 6 7 Which of the two worrying trends is likely to be the largest contributor to the gap between X and 6 7 and why Base your argument on the evidence in Tables 1 and 7 Answer Table 1 shows that the R3000 runs O S primitives only about 4 times as fast as the CVAX which is quite a bit less than 6 7 However Table 7 shows that latex only spends about 5 of its time in O S primitives so the first trend will only have about a 3 effect on latex run time Table 7 shows that moving from Mach 2 5 to Mach 3 0 adds about 17 to latex run time on the R3000 Thus the second trend has a greater effect than the first 6 824 Fall 2002 Midterm Exam Answers Page 3 of 10 II Flash 2 10 points Look at the right hand end of Figure 10 in Flash An efficient and portable Web server The value for MT is about 50 megabits second while the value for SPED is about 37 megabits second What are the main reasons why MT s performance in this situation is higher than SPED s performance Answer Figure 10 shows that MT and SPED perform about the same if all requests are served from the cache They would probably also perform similarly if all documents had to be read from the disk because they would both be limited by disk speed There s only a substantial performance difference when some requests come from the cache and some come from disk in that case MT can serve from the cache while waiting for the disk while SPED cannot 6 824 Fall 2002 Midterm Exam Answers Page 4 of 10 III Atomic List Insert Suppose you want to maintain a linked list of integers using this code struct Element int x Element next struct Element list 0 void insert int x Element n new Element n x x n next list A list n B If you run the following example code list will end up holding 33 followed by 22 void example insert 22 insert 33 You want to use insert in a multi threaded operating system kernel that runs on a machine with multiple CPUs list is a global variable and more than one thread might want to insert elements into the list You re worried that two concurrent calls to insert may lead to incorrect results One reasonable solution would be to acquire a lock before the line marked A and release it after the line marked B However you ve read in the Fast Mutual Exclusion and Scheduler Activations papers that locks don t always perform well for example a thread might be pre empted or interrupted while holding the lock preventing other threads from making progress You would like to be able to perform a non blocking atomic linked list insert Non blocking means that if thread T1 is executing the insert routine and is pre empted and control is passed to thread T2 T2 would be able to execute insert without waiting for T1 Note that insert would be blocking if you used locks While reading the operating system source you notice that it implements locks as follows struct Lock unsigned int locked 6 824 Fall 2002 Midterm Exam Answers Page 5 of 10 void acquire struct Lock l int my thread id while CMPXCHG l locked 0 my thread id 1 void release struct Lock l l locked 0 The call to CMPXCHG is actually a single instruction on the CPU you re using the Intel PentiumPro The CMPXCHG instruction takes three operands a memory address and two values in registers If the contents of memory at that address are equal to the first value CMPXCHG writes the second value to the memory otherwise CMPXCHG doesn t change memory CMPXCHG sets a condition code to tell you whether it wrote memory CMPXCHG does its work atomically Addresses are 32 bits wide and CMPXCHG reads and writes 32 bit values in memory The CPU hardware implements CMPXCHG something like this int CMPXCHG addr v1 v2 int ret 0 condition code Stop all memory activity on all other CPUs and start ignoring interrupts if addr v1 addr v2 ret 1 Resume other activity and stop ignoring interrupts return ret It occurs to you that you might be able to use CMPXCHG to update the linked list directly without using locks thus achieving non blocking atomic insert 6 824 Fall 2002 Midterm Exam Answers Page 6 of 10 3 15 points Write a new version of insert that uses CMPXCHG is atomic and is nonblocking You only need to specify the code that replaces lines A and B of the original insert Answer void insert int x Element n new Element n x x do n next list while CMPXCHG list n next n 0 6 824 Fall 2002 Midterm Exam Answers Page 7 of 10 IV NFS 4 5 points Consider the NFS protocol described in the 1985 paper Design and Implementation of the Sun Network File System How does an NFS client cope with the fact that networks do not deliver all packets Answer The NFS client keeps re sending each RPC until the client receives a reply from the server You re logged into a workstation running UNIX Your home directory is on a file server and your workstation uses NFS to talk to the file server NFS operates as described in the 1985 paper Your workstation is the only client of the file server You are in an empty directory you try to create a new directory using mkdir you get an error message back from the mkdir command but you find that somehow the new directory was created anyway That is you experience a terminal session like this one ls l mkdir d mkdir d File exists ls l total 1 drwxrwxr x 2 yourname 512 Oct 28 12 27 d …