CS 140: Operating Systems and Systems ProgrammingFinal ExamBen PfaffStanford UniversityDepartment of Computer ScienceAugust 12, 2005In recognition of and in the spirit of the Stanford University Honor Code, I certify that Iwill neither give nor receive unpermitted aid on this exam.Name (please print):Signature:• This exam is closed notes and closed book.• No collaboration of any kind is permitted.• You have 180 minutes to complete the exam.• There are 11 questions totalling 100 points. Some questions have multiple parts.• Please check that you have all 7 pages.• Before starting, write your initials on each page, in cas e they become separated during grading.• Please print or write legibly.• Answers may not require all the space provided. Complete but concise answers are encouraged.• SCPD students: If you wish to have the exam returned to you at your company, please attach anSCPD routing slip. Otherwise, we will assume that you will pick up your exam on campus. Routingslips can be obtained just outside the classroom (if you take the exam on campus) or on the SCPDwebsite.Question Points Score1 82 83 124 105 86 127 48 129 910 811 9Total 100page 1 of 7CS 140 Summer 2004–2005 Final Exam Initials:1. Consider a multitasking OS for a symmetric multiprocessing platform. In each of the following situations,state whether you would prefer to use a spinlock or a semaphore for synchronization, and why. If youbelieve that neither is an acceptable choice, explain.(a) (4 points) Incrementing a “hit counter” for a we b server.(b) (4 points) After a “disk read” command has been delivered to a disk device, waiting for the sectorread to complete.2. (8 points) In a Unix-like file system, is the file name stored in a directory or an inode? What file systemfeature (or features) makes this choice more reasonable than the other?page 2 of 7CS 140 Summer 2004–2005 Final Exam Initials:3. Old Unix-like systems did not provide any primitives intended for synchronization of user processes, butthey did provide pipes. A pipe is a channel for transmitting a stream of data, based on a fixed-sizedbuffer (often 4 kB). Reading an empty pipe blocks until data is written. Writing to a pipe whose bufferis full blocks until data is read.(a) (6 points) Explain how to implement a semaphore using a pipe. (Hint: take advantage of the pipe’sblocking semantics.)(b) (6 points) A semaphore implemented as a pipe may deadlock in a situation where a conventionallyimplemented semaphore would not. De scribe the situation.4. (10 points) fd is an open, writable file desc riptor for a zero-length file in a Unix-like file system. Its filepointer is set to an offset of 109bytes. What would each block written by the following function callcontain?write(fd, &data, 1);page 3 of 7CS 140 Summer 2004–2005 Final Exam Initials:5. (8 points) Professor Bob designs a file system that allocates file data using a variable-length array ofextents. Suggest two advantages and two disadvantages of this scheme compared to the data allocationschemes discussed in class.6. One-time passwords.(a) (6 points) Are one-time passwords vulnerable to replay attacks when used for authentication onphysical machines? On virtual machines?(b) (6 points) Are one-time passwords vulnerable to man-in-the-middle attacks on physical machines?On virtual machines?page 4 of 7CS 140 Summer 2004–2005 Final Exam Initials:7. (4 points) Why can salts be made public?8. Alice and Bob have previously exchanged public keys. Now Alice wants to send a confidential messageto Bob.(a) (6 points) What should Alice do? Fill in each blank with one of the following words: signs, encrypts,Alice, Bob, public, private.Alice the message with ’s keythen the res ult with ’s key.(b) (6 points) Could Alice reasonably perform these operations in the opposite order? Why or whynot?page 5 of 7CS 140 Summer 2004–2005 Final Exam Initials:9. (9 points) An architecture supports 4 kB pages and 4 MB superpages. A process uses 4 MB of virtualmemory. Give three reasons why many 4 kB pages might be a better way to map the region than one4 MB superpage. Assume that the process’s memory is properly aligned for a superpage.(1)(2)(3)10. (8 points) We wish to increase the size of a RAID array by adding one new disk. Is it easier to add thenew disk if the array’s RAID level is 4 or 5, and why? You may assume the new disk contains all zeroes.page 6 of 7CS 140 Summer 2004–2005 Final Exam Initials:11. Networking.(a) (3 points) Wired links, such as Ethernet, FDDI, and ATM, do not normally feature encrypted orreliable transmission. What is the justification for this design decision?(b) (6 points) Many wireless links, including all variants of 802.11, do have encryption and reliabilityfeatures. In each case, why make a different design decision for wireless?encryption:reliability:page 7 of
View Full Document
Unlocking...