CSE 221 Winter
Graduate Operating Systems
Last edited 22 January 2003.
Keith Marzullo, marzullo@cs, x4-3729, APM
4824. Office hours Tu/Th 10-12 or by appointment.
Class meets on Tuesdays and Thursdays 5-6:20
in Peterson 103
The purpose of this course is to teach
computer software system structures from a design point of view. We will
look at different structuring techniques, and we will examine their usage
in both important historical systems and in modern systems.
There is no textbook for this class. You
will instead read a set of papers that I'll make available to you as the
class progresses. I'll try to make all of the papers available via the
web, but there may be some that I'll need to pass out.
Your grade will be computed as follows:
You're expected to critically read all
of the papers. Part of your grade will be based on class participation,
which I'll force (as gracefully as possible) by calling on you. I'll introduce
each paper and start the discussion, but at some point I'll turn to you
for details and insight. In doing so, my goal is to have a more active
discussion than one normally has in a classroom setting.
You will do a project for the class, and
it will be due on Friday, March 14 at midnight. You can work by yourself
or in teams of up to four students, but I will expect an amount of work
commensurate with the size of the team.
I would like to receive by no later
than February 6 a project proposal from each team. The proposal
Send them to me via e-mail. I'll review the
proposal, and meet with you if necessary to discuss your ideas. I won't
accept a project whose proposal I didn't first accept. You can send in
your proposals before the due date, of course.
The team members.
A brief (one or two paragraph) description
of the topic and why it is interesting.
Your plan of attack.
I would like your project to address a
concrete and quantifiable aspect of computer systems. Here are some project
There have been some influential papers written
on some aspect of system performance that have affected the way we design
systems. Two examples are:
"Measurements of a Distributed File System"
by Mary G. Baker et. al in SOSP 13.
Jim Gray, ``A Census of Tandem System Availability
between 1985 and 1990,'' IEEE Transactions on Reliability, vol. 39, Oct
We'll see more cited in the papers
we cover this quarter. Are the observations in these papers still valid?
If so, why have they remained valid considering the huge changes that have
taken place since? If not, then how have they changed, and what does this
imply about operating system structure?
More generally, the design of an operating
system depends on the underlying hardware and its performance. If you don't
know these values, then a system you design may not be useful. Come up
with a set of metrics and measure them for a real system. The metrics should
include: memory access times, page fault penalty (ratio of page fault service
time to memory access time), min, average and maximum disk access time,
page fault rate, the effects of changing file cache size, the access time
to read a page from a remote file server, procedure invocation time, context
switch overhead as a function of the instruction cycle time.
In the same vein, there have been architectural
changes that operating systems haven't fully caught up with. For example,
64-bit words allows for a huge physical memory space; how should it be
managed? For such a topic, you could survey the current work in the area
and add your own thoughts about the different approaches.
Some of the systems (notably, some appearing
in the ACM Symposium on Operating System Principles) are available for
interested researchers. This is done so that the experimental results can
be independently verified. Try to verify the results. Be suspicious; try
changing the parameters to see if agree or disagree with their conclusions.
There will be a written final on Monday,
March 17, from 7 to 10 PM, in Peterson 103. It will contain approximately
six questions based on the papers in the reading list. It will be a "closed
book" final; you won't be allowed to bring in the papers nor any notes.
Here is a copy
of the final I gave last Spring quarter.
Here are the papers that we'll be discussing
in class. The date at the end of each entry is the earliest date that the
paper will be discussed.
Note that this is an incomplete list; I'll
be completing it as quickly as possible.
Kernel Design and Concurrency
Edsger W. Dijkstra, The
Structure of the THE Multiprogramming System. Communications of
the ACM, 11(5):341-346, May 1968. January
P. B. Hansen, The Nucleus
of a Multiprogramming System. Communications of the ACM, 13(4):
238-241, April 1970, pp. 238-241. January
D. G. Bobrow, J. D. Burchfiel, D. L. Murphy,
and R. S. Tomlinson, TENEX, a Paged Time Sharing System
for the PDP-10.
Communications of the ACM, 15(3): 135-143, March
1972. January 14.
Review of concurrency
principles. January 14.
C. A. R. Hoare, Monitors:
An Operating System Structuring Concept, Communications of the ACM,
(17)10:549-557, October, 1974. January
B. W. Lampson and D.
D. Redell, Experience with processes and monitors
in Mesa. Communications of the ACM, February 1980, 23(2):105-117. January
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):81-92, February
1980. January 23.
H. C. Lauer and R. M.
Needham. On the Duality of Operating System Structures.
In Proceedings of the Second International Symposium on Operating Systems,
IRIA, Oct. 1978 (reprinted in Operating Systems Review 13(2):3-19, April
1979. January 23.
J. K. Ousterhout, Why
Aren't Operating Systems Getting Faster as Fast as Hardware? In Proceedings
of the USENIX Summer Conference, pp. 247-256, June 1990. January
H. Haertig, M. Hohmuth,
J. Liedtke, S. Schoenberg, J. Wolter, The Performance
of Micro-Kernel-Based Systems. In Proceedings of the 16th ACM Symposium
on Operating Systems Principles, Saint Malo, France, 5-8 October 1997,
pages 66-77. January 30.
M. K. McKusick, W. N.
Joy, S. J. Leffler, and R. S. Fabry, A Fast File System
for UNIX. ACM Transactions on Computer Systems 2(3):181-197, August
1984. January 30.
M. Rosenblum and J.
Ousterhout, The Design and Implementation of a Log-Structured
File System. ACM Transactions on Computer Systems, February 1992, 10(1):26-52.
Peter M. Chen, Wee Teck
Ng, Subhachandra Chandra, Christopher Aycock, Gurushankar Rajamani, and
David Lowell. The Rio File Cache: Surviving Operating
System Crashes. In Proceedings of the Seventh International Conference
on Architectural Support for Programming Languages and Operating Systems,
SIGPLAN Notices 31(9):74-83, September 1996. February
Protection and Security
A. Bensoussan, C. T Clingen, and R. C. Daley.
Multics virtual memory: Concepts and design. Communications of the
ACM, May 1972, 15(5):308-318. February 6.
Ö. Babaoglu and W. Joy. Converting
a swap-based system to do paging in an architecture lacking page-referenced
bits. In Proceedings of the Eighth Symposium on Operating Systems Principles,
Pacific Grove, CA, USA, 14-16 December 1981, pages 78-86. February
R. Rashid et. al, Machine-independent
virtual memory management for paged uniprocessor and multiprocessor architectures.
IEEE Transactions on Computers, August 1988, 37(8): 896-908. February
Michael J. Feeley, William E. Morgan, Frederic
H. Pighin, Anna R. Karlin, and Henry M. Levy, Implementing
Global Memory Management in a Workstation Cluster. Proceedings of the
15th ACM Symposium on Operating Systems Principles, Dec. 1995, 29(5): 201-212.
W. Wulf, E. Cohen, W. Corwin, A. Jones, R.
Levin, C. Pierson, and F. Pollack, HYDRA: The Kernel
of a Multiprocessor System. Communications of the ACM 17(6):337-345,
June 1974. February 13.
J. H. Saltzer, Protection
and the control of information sharing in Multics. Communications of
the ACM, July 1974, 17(7):388-402. February 18.
B. Lampson, Protection.
Operating Systems Review, January 1974, 8(1):18-24. February
Communications and Distributed Systems
D. M. Ritchie, A stream
input-output system. AT&T Bell Laboratories Technical Journal,
62(8):1897-1910, October 1984. February 20.
V. S. Pai, P. Druschel, and W. Zwaenepoel,
A Unified Buffering and Caching System. In Proceedings of the Third
Symposium on Operating Systems Design and Implementation (OSDI'99), New
Orleans, LA, February 1999, pp. 15-28. February
R. F. Rashid and G. G. Robertson, Accent:
A communication oriented network operating system kernel, Proc. Eighth
Symposium on Operating Systems Principles, Operating Systems Review, 15(5):
64-75, December 1981. February 25.
D. R. Cheriton and W. Zwaenepoel, The
Distributed V Kernel and its Performance for Diskless Workstations,
Proc. Ninth Symposium on Operating Systems Principles, Operating Systems
Review, 17(5): 129-140, November 1983. February
A. Birell and B. J. Nelson, Implementing
RPC. ACM Transactions on Computer Systems 2(1):39-59, February 1984.
M. D. Schroeder, A. D. Birrell, and R. M.
Needham. Experience with Grapevine: the growth
of a distributed system. ACM Transactions on Computer Systems, February
1984, 2(1):3-23. March 4.
Brian N. Bershad, Thomas E. Anderson, Edward
D. Lazowska, and Henry M. Levy, Lightweight Remote Procedure
Call, Proc. Twelfth Symposium on Operating Systems Principles, pp.
102-113, December 1989. March 4.
J. H. Saltzer, D. P. Reed, and D. D. Clark,
arguments in system design. ACM Transactions on Computer Systems, November
1984, 2(4):277-288. March 6.
D. D. Clark, The structuring
of systems using upcalls. In Proceedings of the Tenth ACM Symposium
on Operating Systems Principles, Orcas Island, WA, USA, 1-4 December 1985,
pp. 171-180. March 6.
Andrea Arpaci-Dusseau and Remzi Arpaci-Dusseau,
Information and Control in Gray-Box Systems,
Proc. Eighteenth ACM Symposium on Operating Systems Principles, pp.
43-56, October 2001.
Dawson Engler et. al.,
Bugs as Deviant Behavior: A General Approach to Inferring Errors in Systems Code,
Proc. Eighteenth ACM Symposium on Operating Systems Principles, pp.
57-72, October 2001.
Butler W. Lampson,
Hints for Computer System Design,
ACM Operating Systems Review 15, 5 (October 1983), pp. 33-48.