UW Operating Systems
  Qualifying Exam

Past exams

Reading list

Textbooks

• A. Silberschatz, P. B. Galvin, and G. Gagne. Operating System Concepts. Wiley Publishing, 3 most recent editions (currently 7-9)
  1. Chapters 1-12 (Introduction through Mass Storage)
• R. Arpaci-Dusseau and A. Arpaci-Dusseap. Operating Systems: Three Easy Pieces. Arpaci-Dusseau Books, Version 0.8 (May 2014) or later.
  1. Processes and Scheduling (Chapters 4-9)
  2. Virtual Memory (Chapters 13-22)
  3. Concurrency and Synchronization (Chapters 26-32)
  4. File Systems and Storage (Chapters 36-44)
  5. Optional: Distributed Systems (Chapters 47-49, includes NFS and AFS)

Kernels

1. P. B. Hansen. The nucleus of a multiprogramming system. Commun. ACM, 13(4):238-241, 1970.
2. D. M. Ritchie and K. Thompson. The unix time-sharing system. Commun. ACM, 17(7):365-375, 1974.
3. W. Wulf, E. Cohen, W. Corwin, A. Jones, R. Levin, C. Pierson, and F. Pollack. Hydra: the kernel of a multiprocessor operating system. Commun. ACM, 17(6):337-345, 1974.
4. D. D. Redell, Y. K. Dalal, T. R. Horsley, H. C. Lauer, W. C. Lynch, P. R. McJones, H. G. Murray, and S. C. Purcell. Pilot: an operating system for a personal computer. Commun. ACM, 23(2):81-92, 1980.
5. D. R. Engler, M. F. Kaashoek, and J. O'Toole, Jr. Exokernel: an operating system architecture for application-level resource management. In SOSP '95: Proceedings of the fifteenth ACM symposium on Operating systems principles, 1995. ACM.
6. E. Bugnion, S. Devine, K. Govil, and M. Rosenblum. Disco: running commodity operating systems on scalable multiprocessors. ACM Trans. Comput. Syst., 15(4):412-447, 1997.
7. Rob Pike, Dave Presotto, Sean Dorward, Bob Flandera, Ken Thompson, Howard Trickey, Phil Winterbottom. Plan 9 from Bell Labs. Computing Systems, 8(3):221-2254, 1995.

   Distributed Systems

8. L. Lamport. Time, clocks, and the ordering of events in a distributed system. Commun. ACM, 21(7):558-565, 1978.
9. K. M. Chandy and L. Lamport. Distributed snapshots: determining global states of distributed systems. ACM Trans. Comput. Syst., 3(1):63-75, 1985.
10. A. D. Birrell and B. J. Nelson. Implementing remote procedure calls. ACM Trans. Comput. Syst., 2(1):39-59, 1984.
11. M. D. Schroeder, A. D. Birrell, and R. M. Needham. Experience with grapevine: the growth of a distributed system. ACM Trans. Comput. Syst., 2(1):3-23, 1984.
12. M. L. Powell and B. P. Miller. Process migration in demos/mp. SIGOPS Oper. Syst. Rev., 17(5):110-119, 1983.
13. T. J. LeBlanc and J. M. Mellor-Crummey. Debugging parallel programs with instant replay. IEEE Trans. Comput., 36(4):471-482, 1987.
14. L. Lamport, R. Shostak, and M. Pease. The byzantine generals problem. ACM Trans. Program. Lang. Syst., 4(3):382-401, 1982.
15. J. Dean and S. Ghemawat. MapReduce: simplified data processing on large clusters. In OSDI'04: Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, 2004. USENIX Association.
16. G. DeCandia, D. Hastorun, M. Jampani, G. Kakulapati, A. Lakshman, A. Pilchin, S. Sivasubramanian, P. Vosshall, and W. Vogels. Dynamo: amazon's highly available key-value store. SIGOPS Oper. Syst. Rev., 41(6):205-220, 2007.
17. I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan. Chord: A scalable peer-to-peer lookup service for internet applications. In SIGCOMM '01: Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, 2001. ACM.

    Memory Management

18. R. C. Daley and J. B. Dennis. Virtual memory, processes, and sharing in multics. Commun. ACM, 11(5):306-312, 1968.
19. R. W. Carr and J. L. Hennessy. Wsclock-a simple and effective algorithm for virtual memory management. SIGOPS Oper. Syst. Rev., 15(5):87-95, 1981.
20. R. Rashid, A. Tevanian, M. Young, D. Golub, R. Baron, D. Black, W. Bolosky, and J. Chew. Machine-independent virtual memory management for paged uniprocessor and multiprocessor architectures. SIGARCH Comput. Archit. News, 15(5):31-39, 1987.
21. C. A. Waldspurger. Memory resource management in vmware esx server. SIGOPS Oper. Syst. Rev., 36(SI):181-194, 2002.

    Synchronization and Communication

22. B. W. Lampson and D. D. Redell. Experience with processes and monitors in mesa. Commun. ACM, 23(2):105-117, 1980.
23. B. N. Bershad, T. E. Anderson, E. D. Lazowska, and H. M. Levy. Lightweight remote procedure call. ACM Trans. Comput. Syst., 8(1):37-55, 1990.

    Scheduling

24. T. E. Anderson, B. N. Bershad, E. D. Lazowska, and H. M. Levy. Scheduler activations: effective kernel support for the user-level management of parallelism. In SOSP '91: Proceedings of the thirteenth ACM symposium on Operating systems principles, 1991. ACM.
25. C. A. Waldspurger and W. E. Weihl. Lottery scheduling: flexible proportional-share resource management. In OSDI '94: Proceedings of the 1st USENIX conference on Operating Systems Design and Implementation, 1994. USENIX Association.

    File Systems and Storage

26. M. K. McKusick, W. N. Joy, S. J. Leffler, and R. S. Fabry. A fast file system for unix. ACM Trans. Comput. Syst., 2(3):181-197, 1984.
27. M. Rosenblum and J. K. Ousterhout. The design and implementation of a log-structured file system. ACM Trans. Comput. Syst., 10(1):26-52, 1992.
28. J. H. Howard, M. L. Kazar, S. G. Menees, D. A. Nichols, M. Satyanarayanan, R. N. Sidebotham, and M. J. West. Scale and performance in a distributed file system. ACM Trans. Comput. Syst., 6(1):51-81, 1988.
29. S. Ghemawat, H. Gobioff, and S.-T. Leung. The google file system. SIGOPS Oper. Syst. Rev., 37(5):29-43, 2003.
30. J. Wilkes, R. Golding, C. Staelin, and T. Sullivan. The hp autoraid hierarchical storage system. ACM Trans. Comput. Syst., 14(1):108-136, 1996.
31. R. Sandberg, D. Goldberg, S. Kleiman, D. Walsh, and B. Lyon. Design and implementation of the sun network filesystem. In Proceedings of USENIX Summer Techincal Conference, 1985.

    Protection and Security

32. R. M. Needham and M. D. Schroeder. Using encryption for authentication in large networks of computers. Commun. ACM, 21(12):993-999, 1978.
33. J. G. Steiner, C. Neuman, and J. I. Schiller. Kerberos: An authentication service for open network systems. In USENIX 1988, Feb. 1988.
34. J. Saltzer and M. Schroeder. The protection of information in computer systems. Proceedings of the IEEE, 63(9):1278- 1308, Sept. 1975.

    Fault Tolerance and Reliability

35. M. M. Swift, B. N. Bershad, and H. M. Levy. Improving the reliability of commodity operating systems. In SOSP '03: Proceedings of the nineteenth ACM symposium on Operating systems principles, 2003. ACM.
36. R. Wahbe, S. Lucco, T. E. Anderson, and S. L. Graham. Efficient software-based fault isolation. In SOSP '93: Proceedings of the fourteenth ACM symposium on Operating systems principles, 1993. ACM.
37. D. Engler, D. Y. Chen, S. Hallem, A. Chou, and B. Chelf. Bugs as deviant behavior: a general approach to inferring errors in systems code. SIGOPS Oper. Syst. Rev., 35(5):57-72, 2001.

    Experience Reports

38. J. H. Saltzer, D. P. Reed, and D. D. Clark. End-to-end arguments in system design. ACM Trans. Comput. Syst., 2(4):277-288, 1984.
39. B. W. Lampson. Hints for computer system design. SIGOPS Oper. Syst. Rev., 17(5):33-48, 1983.
40. H. C. Lauer. Observations on the development of an operating system. In SOSP '81: Proceedings of the eighth ACM symposium on Operating systems principles, 1981, ACM.

Copyrights

ACM