Department of Electrical Engineering and Computer Science MASSACHUSETTS INSTITUTE OF TECHNOLOGY 6 824 Distributed System Engineering Spring 2010 Quiz I Solutions All problems are open ended questions In order to receive credit you must answer the question as precisely as possible You have 80 minutes to answer this quiz Write your name on this cover sheet AND at the bottom of each page of this booklet Some questions may be much harder than others Read them all through first and attack them in the order that allows you to make the most progress If you find a question ambiguous be sure to write down any assumptions you make Be neat If we can t understand your answer we can t give you credit THIS IS AN OPEN BOOK OPEN NOTES QUIZ I xx 26 Name II xx 21 III xx 49 IV xx 4 Total xx 100 max 92 median 66 66 0 12 2 1 00 96 9 5 91 9 0 86 8 5 81 8 0 76 7 5 71 7 0 66 6 5 61 6 0 56 5 5 51 5 0 46 4 5 41 4 0 36 3 5 31 3 0 26 2 5 21 2 0 16 1 5 11 10 5 6 1 Grade histogram for Quiz 1 6 5 4 3 2 1 0 6 824 SPRING 2010 Quiz 1 I Page 3 of 12 YFS Working on Lab 4 Ben Bitdiddle adds a create function to his YFS client the function is responsible for creating files Ben wants to use multiple YFS clients so he also adds locking to his YFS client code He uses a lock per inode and wraps each YFS client function with a call to the lock client s acquire and release passing the inode s inum as the argument Here are some excerpts from yfs client cc error checking code omitted yfs client inum yfs client ilookup inum di std string name std string buf yfs client inum inum 0 lc acquire di ec get di buf parse buf and set inum if file found lc release di return inum int yfs client create inum di std string name inum ci std string buf lc acquire di lc acquire ci ec get di buf add name ci pair to buf ec put di buf ec put ci lc release di lc release ci return OK And from fuse cc yfs client status fuseserver createhelper fuse ino t parent const char name mode t mode struct fuse entry param e e ino yfs ilookup parent name if e ino 0 e ino random 0x80000000 yfs create parent name e ino getattr e ino e attr e attr timeout 0 0 e entry timeout 0 0 return OK Name Page 4 of 12 6 824 SPRING 2010 Quiz 1 1 8 points To Ben s surprise his implementation fails the standard tests given by the 6 824 staff Describe a test on which Ben s program will fail How can Ben fix his code to ensure that his code passes the tests Answer If multiple threads are concurrently creating the same file in the same directory then it is possible for fuseserver createhelper to create multiple files with the same name in the directory The following interleaving of instructions demonstrates the problem Thread 1 e ino yfs ilookup parent name Thread 2 e ino yfs ilookup parent name e ino 0 so execute yfs create parent name e ino e ino 0 so execute yfs create parent name e ino Answer To fix this Ben needs to make the calls to yfs client ilookup and yfs client create atomic in fuseserver createhelper One way to do this is to create a yfs client ilookup wo function that is exactly like yfs client ilookup but does not take out any locks and have yfs client create check while holding the di lock if the file exists using yfs client ilookup wo Name 6 824 SPRING 2010 Quiz 1 Page 5 of 12 In another attempt at correctness Ben modifies his code in yfs client cc as follows yfs client inum yfs client ilookup inum di std string name std string buf yfs client inum inum 0 lc acquire di B ec get di buf parse buf and set inum if file found lc release di return inum int yfs client create inum di std string name inum ci std string buf lc acquire di A ci ilookup di name if ci 0 lc acquire ci ci random 0x80000000 ec get di buf add name ci pair to buf ec put di buf ec put ci lc release ci lc release di return OK And in fuse cc yfs client status fuseserver createhelper fuse ino t parent const char name mode t mode struct fuse entry param e yfs create parent name e ino getattr e ino e attr e attr timeout 0 0 e entry timeout 0 0 return OK Name 6 824 SPRING 2010 Quiz 1 Page 6 of 12 2 6 points To his surprise his code still does not work his code fails to create a file What is the problem and how can he fix it Answer The code will deadlock because a lock for di will be taken on the line labeled A and then the call to ilookup will take out the lock for di again on the line labeled B One way to fix this is to create a yfs client ilookup wo function that is exactly like yfs client ilookup but does not take out any locks and have yfs client create call yfs client ilookup wo instead of yfs client ilookup Now Ben wants to simplify YFS by expanding the extent protocol from get put and remove to read write truncate create lookup etc Every file system operation i e each fuse operation will be handled by the extent server The YFS client will be a proxy for the extent server 3 6 points What are the advantages of executing the file system operations on the extent server Which functions features can he remove from YFS using this scheme Answer Executing all the file system operations on one server means that there is no longer any need to have a lock server and the YFS clients do not have to worry about making calls to the lock server The extent server can use Pthread mutexes to lock critical sections 4 6 points What are disadvantages of moving the file system operations out of the YFS client and into the extent server Answer Since one single machine handles all file system requests from all clients the system proposed by Ben will not be scalable Even though the number of clients can grow the processing capacity of the single extent server will remain constant Ben s scheme does not exploit the processing capacity of the client machines to execute file operations Name 6 824 SPRING 2010 Quiz 1 II Page 7 of 12 Short questions 5 7 points An invocation o1 f o2 on an RMI object o1 takes another RMI object o2 as an argument The method f …