Advanced Readings

CS422/522: Operating Systems, Spring 2006, Yale University

1. Historical Perspective

E. W. Dijkstra. The Structure of the THE Multiprogramming System. Communications of the ACM 11(5), May 1968.
D. M. Ritchie and K. Thompson. The UNIX Timesharing System. Communications of the ACM 17(7), July 1974.
K. Thompson. Unix Implementation. Bell System Technical Journal, 57(6), pp. 1931-1946, July 1978.
B. W. Lampson. Hints for Computer System Design. Proc. of the 9th ACM Symposium on Operating Systems Principles, pp. 33-48, October 1983.

2. Structure and Organization

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. Communications of the ACM 23(2), pp. 81-92, February 1980.
M. Accetta, R. Baron, W. Bolosky, D. Golub, R. Rashid, A. Tavanian, and M. Young. Mach: A New Kernel Foundation for Unix Development. Proc. of the Summer 1986 USENIX Conference, pp. 93-112, June 1986.
D. Golub, R. Dean, A. Forin, and R. Raashid. Unix as an Application Program. Proc. of the Summer 1990 USENIX Conference, pp. 87-95, June 1990.
H. Massalin and C. Pu. Theads and Input/Output in the Synthesis Kernel. Proc. of the 12th ACM Symposium on Operating Systems Principles, pp. 191-201, December 1989.
T. Anderson, H. Levy, B. Bershad, and E. Lazowska. The Interaction of Architecture and Operating System Design. Proc. of the 4th Conference on Architecture Support for Programming Languages and Operating Systems, pp. 108-119, April 1991.
J. Chase, H. Levy, M. Feeley, and E. Lazowska. Sharing and Protection in a Single Address Space Operating System. ACM Trans. on Computer Systems, November 1994.
B. Bershad, S. Savage, P. Pardyak, E. Sirer, M. Fiuczynski, D. Becker, C. Chambers, and S. Eggers. Extensibility, Safety and Performance in the SPIN Operating System. Proc. of the 15th ACM Symposium on Operating Systems Principles, pp. 267--284, December 1995.
J. Liedtke. On Micro-Kernel Construction. Proc. of the 15th ACM Symposium on Operating Systems Principles, pp. 237-250, December 1995.
E. Bugnion, S. Devine, and M. Rosenblum. Disco: Running Commodity Operating Systems on Scalable Multiprocessors. Proc. of the 16th ACM Symposium on Operating Systems Principles, pp. 143-156, December 1997.
B. Ford, G. Back, G. Benson, J. Lepreau, A. Lin, and O. Shivers. The Flux OSKit: A Substrate for OS and Language Research. Proc. of the 16th ACM Symposium on Operating Systems Principles, pp. 38-51, December 1997.
G. Back, P. Tullmann, L. Stoller, W. C. Hsieh, and J. Lepreau. Java Operating Systems: Design and Implementation. Technical Report UUCS-98-015, Univ. of Utah, August 1998.

3. Threads and Concurrency

A. Birrell. An Introduction to Programming with Threads. Research Report 35, DEC Systems Research Center, January 1989.
C.A.R. Hoare. Monitors: An Operating System Structuring Concept, Communications of the ACM 17(10), pp. 549-557, October 1974.
C.A.R. Hoare. Communicating Sequential Processes. Communications of the ACM 21(8), pp. 666-677, August 1978.
B. W. Lampson and D. D. Redell. Experience with Processes and Monitors in Mesa. Communications of the ACM 23(2), pp. 105-117, February 1980.
M. Herlihy. A Methodology for Implementing Highly Concurrent Data Structures. Proc. of the 2nd ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming, pp. 197-206, March 1990.
T. Anderson, B. Bershad, E. Lazowska, and H. Levy. Scheduler Activations: Effective Kernel Support for the User-Level Management of Parallelism. ACM Trans. on Computer Systems 10(1), pp. 53-79, Feburary 1992.
S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. Anderson. Eraser: A Dynamic Race Detector for Multithreaded Programs. ACM Transaction on Computer Systems, 15(4), November 1997.

4. Communication and Networking

A. D. Birrell and B. J. Nelson. Implementing Remote Procedure Calls. ACM Trans. on Computer Systems 2(1), pp. 39-59, February 1984.
B. N. Bershad, T. E. Anderson, E. D. Lazowska, and H. M. Levy. Lightweight Remote Procedure Call. ACM Trans. on Computer Systems 8(1), pp.37-55, February 1990.
T. von Eicken, D. E. Culler, S. C. Goldstein, and K. E. Schauser. Active Messages: a Mechanism for Integrated Communication and Computation. Proc. of the 19th Int. Symp. on Computer Architecture, pp. 256-266, May 1992.
J. Liedtke. Improving IPC by Kernel Design. Proc. of the 14th ACM Symp. on Operating Systems Principles, pp. 175-187, December 1993.
P. Druschel and L. L. Peterson. Fbufs: A High-Bandwidth Cross-Domain Transfer Facility. Proc. of the 14th ACM Symp. on Operating Systems Principles, pp. 189-202, December 1993.
R. M. Metcalfe and D. R. Boggs. Ethernet: Distributed Packet Switching For Local Computer Networks. Communications of the ACM 19(7), pp. 395-404, July 1976.
N. C. Hutchinson and L. L. Peterson. The x-Kernel: An Architecture for Implementing Network Protocols. IEEE Trans. on Software Engineering, 17(1), pp. 64-76, January 1991.
E. A. Brewer, R. H. Katz, et al. A Network Architecture for Heterogeneous Mobile Computing. IEEE Personal Communications, October 1998.
D. L. Tennenhouse and D. J. Wetherall. Towards an Active Network Architecture. Proc. Multimedia Computing and Networking'96, January 1996.
A. Fox, S. Gribble, Y. Chawathe, E. Brewer, and P. Gauthier. Cluster-based Scalable Network Services. Proc. of the 16th ACM Symp. on Operating Systems Principles, pp. 78-91, October 1997.

5. Virtual Memory

H. M. Levy and P. Lipman. Virtual Memory Management in VAX/VMS. Computer 15(3), pp. 35-41, March 1982.
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. Proc. of the 2nd International Conference on Architectural Support for Programming Languages and Operating Systems, pp. 31-39, October 1987.
M. Young, A. Tevanian, R. Rashid, D. Golub, J. Eppinger, J. Chew, W. Bolosky, D. Black, R. Baron, The Duality of Memory and Communication in the Implementation of a Multiprocessor Operating System. Proc. of the 11th ACM Symp. on Operating Systems Principles, pp. 63-76, November 1987.
K. Li and P. Hudak. Memory Coherence in Shared Virtual Memory Systems. ACM Trans. on Computer Systems 7(4), pp. 321-359, November 1989.
D. Scales and K. Gharachorloo. Towards Transparent and Efficient Software Distributed Shared Memory. Proc. of the 16th ACM Symp. on Operating Systems Principles, pp. 157-169, Oct. 1997.

6. File Systems and IO

M. K. McKusick, W. N. Joy, S. J. Leffler, and R. S. Fabry. A Fast File System for UNIX. ACM Trans. on Computer Systems 2(3), pp. 181-197, August 1984.
M. Satyanarayanan, J. H. Howard, D. A. Nichols, R. N. Sidebotham, A. Z. Spector, and M. J. West. The ITC Distributed File System: Principles and Design. Proc. of the 10th ACM Symposium on Operating Systems Principles, pp. 35-50, December 1985.
D. A. Patterson, G. Gibson, and R. H. Katz. A Case for Redundant Array of Inexpensive Disks (RAID). Proc. ACM SIGMOD International Conference on Management of Data, pp. 109-116, June 1988
M. N. Nelson, B. B. Welch, and J. K. Ousterhout. Caching in the Sprite Network File System. ACM Trans. on Computer Systems 6(1), pp. 134-154,February 1988.
J. H. Howard, M. L. Kazar, S. G. Menees, D. A. Nichols, M. Stayanayanan, R. N. Sidebotham, and M. J. West. Scale and Performance in a Distributed File System. ACM Trans. on Computer Systems 6(1), pp. 51-81, February 1988.
D. K. Gifford, P. Jouvelot, M. Sheldon, and J. O'Toole. Semantic File Systems. Proc. of the 12th ACM Symposium on Operating Systems Principles, pp. 16-25, October 1991.
J. J. Kistler and M. Satyanarayanan. Disconnected Operation in the Coda File System. Proc. of the 13th Symposium on Operating Systems Principles, pp. 213-225, October 1991.
M. Rosenblum and J. K. Ousterhout. The Design and Implementation of a Log-Structured File System. ACM Trans. on Computer Systems 10(1), pp. 26-52, February 1992.
C. Thekkath, T. Mann, and E. Lee. Frangipani: A Scalable Distributed File System. Proc. of the 16th ACM Symposium on Operating Systems Principles, pp. 224-237, October 1997.
V. Pai, P. Drushel, and W. Zwaenepoel. IO-Lite: A Unified I/O Buffering and Caching System. Proc. of the 3rd Symposium on Operating Design and Implementation, New Orleans, pp. 15-28, February 1999.

7. Protection and Security

B. W. Lampson. Protection. Proc. of the 5th Princeton Symposium on Information Sciences and Systems, pp. 437-443, March 1971.
B. W. Lampson. A Note on the Confinement Problem. Communications of the ACM, 16(10), pp. 613-615, October 1973.
J. H. Saltzer and M. D. Schroeder. The Protection of Information in Computer Systems. Proc. of the IEEE 63(9), pp. 1278-1308, September1975.
R. M. Needham and M. D. Schroeder. Using Encryption for Authentication in Large Networks of Computers. Communications of the ACM 21(12), pp.993-998, December 1978.
D. E. Denning and P. J. Denning. Data Security. Computing Surveys, 11(3), pp. 227-249, September 1979.
R. Morris and K. Thompson. Password Security: A Case History. Communications of the ACM, 22(11), pp. 594-597, November 1979.
R. L. Rivest, S. Shamir, and L. Adleman. A Method for Obtaining Digital Signatures and Public Key Cryptosystems. Communications of the ACM, 21(2), pp. 120-126, February 1978.
J. G. Steiner, C. Neuman, and J. I. Schiller. Kerberos: An Authentication Service for Open Network Systems. Proc. of USENIX '88, pp. 191-202, February 1988.
B. Lampson, M. Abadi, M. Burrows, and E. Wobber. Authentication in Distributed Systems: Theory and Practice. ACM Transactions on Computer Systems, 10(4), pp. 265-310, November 1992.
K. Thompson. Reflection on Trusting Trust. Communications of ACM, 27(8), pp. 761-763, August 1984.
N. Haller. The S/Key One-Time Password System. Proc. of the ISOC Symposium on Network and Distributed System Security, February 1994.

8. Distributed Systems

B. Walker, G. Popek, R. English, C. Kline, and G. Thiel. The LOCUS Distributed Operating System. Proc. of the 9th ACM Symposium on Operating Systems Principles, pp. 49-69, October 1983.
M. D. Schroeder, A. D. Birrell, and R. M. Needham. Experience with Grapevine: The Growth of a Distributed System. ACM Trans. on Computer Systems, 2(1), February 1984.
E. Jul, H. Levy, N. Hutchinson, and A. Black. Fine-Grained Mobility in the Emerald System. ACM Trans. on Computer Systems 6(1), pp. 109-133, February 1988.
R. Pike, D. L. Presotto, K. Thompson, and H. Trickey, Plan 9 from Bell Labs, Proc. of 1990 USENIX Conference.
I. Leslie, D. McQuley, R. Black, T. Roscoe, P. Barham, D. Evers, R. Fairbairns, and E. Hyden. The Design and Implementation of an Operating System to Support Distributed Multimedia Application. Journal on Selected Areas in Communications, June 1995.

9. Reliability and Recovery

Jim Gray. The Transaction Concept: Virtues and Limitations. Proc. 7th International Conference on Very Large Data Bases, pp. 144-154, September 1981.
B. M. Oki, B. H. Liskov, and R. W. Scheifler. Reliable Object Storage to Support Atomic Actions. Proc. of the 10th ACM Symposium on Operating Systems Principles, pp. 147-159, December 1985.
A. Borg, W. Blau, W. Graetsch, F. Herrmann, and W. Oberle. Fault Tolerance under UNIX. ACM Trans. on Computer Systems 7(1), pp. 1-24, February 1989.
J. Gray and D. P. Sieworek. High-Availability Computer Systems. Computer 24(9), pp. 39-48, September 1991.
K. R. Birman. The Process Group Approach to Reliable Distributed Computing. Communications of the ACM, 36(12), December 1993.
M. Satyanarayanan, H. H. Mashburn, P. Kumar, D. C. Steere, and J. J. Kistler. Lightweight Recoverable Virtual Memory. ACM Trans. on Computer Systems, 12(1), pp.33-57, February 1994.

10. Miscellaneous

N. G. Leveson and C. S. Turner. An Investigation of the Therac-25 accidents. IEEE Computer, 26(7), pp. 18-41, July 1993.
J. Lions, L. Lebeck, J. Fauquembergue, G. Kahn, W. Kubbat, S. Levedag, L. Mazzini, D. M. Thomson, and C. O'Halloran. ARIANE 5 Flight 501 Failure: Report by the Inquiry Board. European Space Agency Report, Paris, July 1996.
G.E. Reeves. What Really Happened on Mars?. Personal Communication. December 1997.
R. Scheifler and J. Gettys. The X Window System. ACM Trans. on Graphics, 5(2), pp. 79-109, April 1986.
B. Bershad, J. Ellis, and D. Redell. Fast Mutual Exclusion for Processors. Proc. of ASPLOS 1992.
C.A.R. Hoare. The Emperor's Old Clothes. Communications of the ACM, 24(2), pp. 75-83, February 1981.
R. Levin, D. D. Redell, An Evaluation of the 9th SOSP Submissions. Operating Systems Review, 17(3), pp. 35-40, July 1983.