1) I know I added one here, but I think there are possible "too many"
historical background papers. The historical section is the biggest
section with 6 papers (most sections have only 3-4). Suggestions
include eliminating one (I'd probably cut Hansen if I had to), or moving
them around. If you were to move them around, you could either:
a) Ditch historical section altogether and move Dijkstra, Hansen,
Saltzer & Unix to structure, Dennis to Concurrency, and Multics to VM.
Maybe even cut a bit.
b) just move some (e.g. Multics to VM, Dennis to concurrency, Hansen
to Structure)
c) Make new section called "case studies": include some of Unix,
Pilot, Multics, HYDRA, LOCUS and use this section to show how different
choices can be made across these various issues.
2) The structure section is weak. It has two hydra papers and SPIN.
SPIN is not, by far, the only thing that came from Hydra. If you
rearrange some of the historical stuff (e.g. moving Hansen, which is
short, to Structure), that might help. Alternatively, you could add
some papers on things with more interesting structure. You could pull
in one of those so-so Mach papers (ie "from RIG to Accent to Mach", the
BIG Mach overview paper "Microkernel Operating Systems Architecture and
Mach" from the Microkernels workshop, or "UNIX as an Application
Program" (I have all of these if you want to take a look). Or you could
pull in one of Synthesis, Plan 9, or Ameoba (or others). I wouldn't be
averse to cutting SPIN if you're short on room. Also, as a possible
move you could consider moving Scheduler Activations to structure,
although that might leave structure short.
3) Again, I know I suggested it, but the RT paper isn't up the caliber
of the others. I don't know what to suggest instead though. Here's a
pointer to a good Real-Time Systems class taught at BU, you might look
over some of these:
http://www.cs.bu.edu/~best/crs/cs835/S96/readings.html (particularly,
"Scheduling Algorithms and Operating Systems Support for Real-Time
Systems", or "Implications of Classical Scheduling Results For Real-Time
Systems". Maybe you just cut RT. Another idea is to include the
Synthesis feedback scheduling paper here. I liked it and its been
fairly influential. BTW, the Ousterhout paper I was thinking of is
"Scheduling Techniques for Concurrent Systems". Finally, I think
there's a problem that you don't have EITHER the Lampson/Redell paper on
Monitors in Mesa NOR the Hoare paper. I'd sacrifice Scheduler
Activations or Lottery scheduling for one of these (I favor the Lampson
Redell paper). If you include one of the Herlihy's, this is the place.
4) The communications section looks good. If you want a historical
paper here, I'd suggest the Task Communication in DEMOS paper.
5) I think you could cut one of the Li paper or the Munin paper. Kai's
is first, but the Munin paper has more in it. Your call.
6) File systems looks good. IF you want a historical paper, the Demos
FS paper on the Multics IO paper might work. I know you're not looking
for more papers, but let me at least suggest Garth's TIP paper and Greg
GAnger's "Metadata update"(OSDI-1 best paper) and "Embedded Inode"
(USENIX best paper) paper as recent examples of nice FS papers.
Finally, I notice that there's nothing here on caching. Probably ok,
since its explained in a number of the papers (ie LFS)
7) I think you could cut xFS. ITS a fine paper, but what really basic
thing are you not going to get between reading GRapevine, AFS, and LFS
papers? Also, are you sure you want a separate section called
distributed file systems? While its true that within the big
distributed systems movement of the 80's it was file systems that really
succeeded and the "single system image" ideal championed at the time by
systems like LOCUS and AMoeba failed, this is a particularly 90's view
to take. Even if you do separate it, I'd switch pages between it and
reliability, since it has more in common with distributed applications
than file systems.
8) Looks good.
9) I think these security papers are good (and you might consider
Authentication in TAOS which was also quite good). I'm going to show my
bias now though and suggest that if you had to drop a section that you
should drop security.
Finally, if you had to cut papers, here would be my list:
Hansen (although its very short and arguably the first uKernel)
SPIN
Scheduler Activations
RT paper
RPC in x-kernel
Kai Li distributed VM paper
xFS
security papers
The papers I'd most like to see there are:
Mesa Monitors
Swap Synthesis Scheduling paper for RT
maybe Pilot
maybe Mach overview paper
maybe LOCUS
-----Original Message-----
From: tom@emigrant [mailto:tom@emigrant]
Sent: Sunday, August 23, 1998 1:29 AM
To: syn@cs
Subject: revised book list
If people have more suggestions. I'm as interested in
finding stuff to drop as I am finding stuff to add.
tom
-------
1. Historical Background
------------------------
Edsger W. Dijkstra.
The Structure of the "THE" Multiprogramming System.
Communications of the ACM 11(5), May 1968, pp. 341-346.
Per Brinch Hansen.
The Nucleus of a Multiprogramming System.
Communications of the ACM 13(4), April 1970, pp. 238-250.
Jack B. Dennis and Earl C. Van Horn.
Programming Semantics for Multiprogrammed Computations.
Communications of the ACM 9(3), March 1966, pp. 143-155.
A. Bensoussan, C. Clingen, and R. Daley.
The MULTICS Virtual Memory: Concepts and Design.
Communications of the ACM, Vol. 15, No. 5 (May 1972), pp. 308-318.
Jerome H. Saltzer.
Protection and the Control of Information Sharing in Multics.
Communications of the ACM 17(7), July 1974, pp. 388-402.
Dennis M. Ritchie and Ken Thompson.
The UNIX Timesharing System.
Communications of the ACM 17(7), July 1974, pp. 365-375.
2. OS Architecture and Structure
--------------------------------
W. Wulf, E. Cohen, W. Corwin, A. Jones, R. Levin, C. Pierson, and F.
Pollack.
HYDRA: The Kernel of a Multiprocessor Operating System.
Communications of the ACM 17(6), June 1974, pp. 337-344.
R. Levin, E. Cohen, W. Corwin, F. Pollack, and W. Wulf.
Policy/Mechanism Separation in HYDRA.
Proceedings of The Fifth Symposium on Operating Systems Principles,
pp. 132--140.
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. Symp. on Operating Systems Principles, December
1995.
3. Concurrency and Scheduling
-----------------------------
Andrew Birrell, An Introduction to Programming with Threads,
DEC SRC Research Report Number 35, January 1989.
Thomas Anderson, Brian Bershad, Edward Lazowska, and Henry Levy.
Scheduler Activations: Effective Kernel Support for the User-Level
Management of Parallelism.
ACM Trans. on Computer Systems 10(1), Feburary 1992, pp. 53-79.
Carl Waldspurger and William Weihl.
Lottery Scheduling: Flexible Proportional-Share Resource Management.
Proc. of the First USENIX Symposium on Operating Systems Design
and Implementation, November 1994.
Sheng-Chang Cheng, John Stankovic, and Krithivasan Ramamritham.
Scheduling Algorithms for Hard Real-Time Systems -- A Brief Survey.
In Hard Real-Time Systems, John Stankovic and Krithivasan Ramamritham,
IEEE Computer Society, 1988.
4. Communication
----------------
Andrew Birrell and Bruce Nelson.
Implementing Remote Procedure Calls.
ACM Trans. on Computer Systems 2(1), February 1984, pp. 39-59.
Norman Hutchinson, Larry Peterson, Mark Abbott, and Sean O'Malley.
RPC in the x-Kernel: Evaluating New Design Techniques.
Proceedings of the 12th SOSP, December 1989, pp. 91-101.
B. Bershad, T. Anderson, E. Lazowska, and H. Levy.
Lightweight Remote Procedure Call.
Proceedings of the 12th SOSP, December 1989, pp. 102-113.
Thorsten von Eicken, David E. Culler, Seth C. Goldstein, and Klaus E.
Schauser.
Active Messages: A Mechanism for Integrated Communication and
Computation.
Proc. 19th Int. Symposium on Computer Architecture, May 1992, pp.
256-266.
5. Virtual Memory and Distributed Virtual Memory
------------------------------------------------
Henry M. Levy and Peter Lipman. Virtual Memory Management in VAX/VMS.
Computer 15(3), March 1982, pp. 35-41.
Michael Young, Avadis Tevanian, Richard Rashid, David Golub, Jeffrey
Eppinger, Jonathon Chew, William Bolosky, David Black, and Robert Baron.
The Duality of Memory and Communication in the Implementation
of a Multiprocessor Operating System.
Proc. of the 11th Symposium on Operating System Principles, pages 63-76,
November 1987.
Kai Li and Paul Hudak.
Memory Coherence in Shared Virtual Memory Systems.
ACM Trans. on Computer Systems 7(4), November 1989, pp. 321-359.
J. B. Carter, J. K. Bennett, and W. Zwaenepoel.
Implementation and Performance of Munin.
Proc. of the 13th ACM Symp. on Operating Systems Principles, Oct. 1991,
pp. 152-164.
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), Feb. 1994, pp.33-57.
6. File Systems
---------------
Marshall K. McKusick, William N. Joy, Samuel J. Leffler, and Robert S.
Fabry.
A Fast File System for UNIX.
ACM Trans. on Computer Systems 2(3), August 1984, pp. 181-197.
J. Ousterhout, H. Da Costa, D. Harrison, J. Kunze, M. Kupfer, and J.
Thompson.
A Trace-Driven Analysis of the UNIX 4.2 BSD File System.
Proc. of the 10th SOSP, December 1985, pp. 15-24.
Mendel Rosenblum and John K. Ousterhout.
The Design and Implementation of a Log-Structured File System.
ACM Trans. on Computer Systems 10(1), February 1992, pp. 26-52.
7. Distributed File Systems
---------------------------
R. Sandberg, D. Goldberg, S. Kleiman, D. Walsh, and B. Lyon,
Design and Implementation of the Sun Network Filesystem.
Proc. of the 1985 Usenix Summer Conference, June 1985, pp. 119-130.
John H. Howard, Michael L. Kazar, Sherri G. Menees, David A. Nichols,
M. Stayanayanan, Robert N. Sidebotham, and Michael J. West.
Scale and Performance in a Distributed File System.
ACM Trans. on Computer Systems 6(1), February 1988, pp. 51-81.
T. Anderson, M. Dahlin, J. Neefe, D. Patterson, D. Roselli, and R. Wang.
Serverless Network File Systems.
ACM Trans. on Computer Systems 14(1), Feb. 1996.
James Kistler and M. Satyanarayanan.
Disconnected Operation in the Coda File System.
ACM Trans. on Computer Systems 10(1), February 1992, pp. 3-25.
8. Reliability
--------------
J. Gray.
The Transaction Concept: Virtues and Limitations.
Proc. of the Seventh VLDB, September 1981, pp. 144-154.
Bruce G. Lindsay, Laura M. Haas, C. Mohan, Paul F. Wilms and Robert A.
Yost.
Computation and Communication in R*: A Distributed Database Manager.
ACM Trans. on Computer Systems 2(1), February 1984, pp. 24-38.
Kenneth P. Birman.
The Process Group Approach to Reliable Distributed Computing.
Communications of the ACM 36(12), December 1993, pp. 37-53.
John Chapin, Mendel Rosenblum, Scott Devine, Tirthankar Lahiri,
Dan Teodosiu, and Anoop Gupta.
Hive: Fault Containment for Shared-Memory Multiprocessors.
Proc. of the 15th ACM SOSP, pp. 12-25, December 1995.
9. Distributed Applications and Services
--------------------------------------------
Michael D. Schroeder, Andrew D. Birrell and Roger M. Needham.
Experience with Grapevine: The Growth of a Distributed System.
ACM Trans. on Computer Systems 2(1), February 1984, pp.3-23.
Eric Jul, Henry Levy, Norman Hutchinson, and Andrew Black.
Fine-Grained Mobility in the Emerald System.
ACM Trans. on Computer Systems 6(1), February 1988, pp. 109-133.
Douglas B. Terry, Marvin M. Theimer, Karin Peterson, Alan J. Demers,
Mike J. Spreitzer, and Carl H. Hauser.
Managing Update Conflicts in Bayou, a Weakly Connected Replicated
Storage System.
Proceedings of the Fifteenth ACM Symposium on Operating Systems
Principles,
p. 172-183, December, 1995.
10. Security
-----------
Roger M. Needham and Michael D. Schroeder.
Using Encryption for Authentication in Large Networks of Computers.
Communications of the ACM 21(12), December 1978, pp.993-998.
M. Burrows, M. Abadi, and R. Needham.
A Logic of Authentication.
ACM Trans. on Computer Systems, 8(1), Feb. 1990.
11. Experience
--------------
B. Lampson.
Hints for Computer System Design.
IEEE Software, 1(1):11-28, January 1984.
J. Ousterhout.
The Role of Distributed State.
----------
Strongly considered, but left out for now:
David D. Redell, Yogen K. Dalal, Thomas R. Horsley, Hugh C. Lauer,
William C. Lynch, Paul R. McJones, Hal G. Murray, and Stephen C.
Purcell.
Pilot: An Operating System for a Personal Computer.
Communications of the ACM 23(2), February 1980, pp. 81-92.
David Cheriton.
The V Distributed System.
B. Walker, G. Popek, R. English, C. Kline, and G. Thiel.
The LOCUS Distributed Operating System.
Proc. 9th SOSP, October 1983.
Leach et al., Apollo
Butler Lampson and David Redell.
Experience with Processes and Monitors in Mesa.
John Ousterhout, Co-scheduling.
Maurice Herlihy.
A Methodology for Implementing Highly Concurrent Data Structures.
Proc. of the 2nd ACM SIGPLAN Symposium on Principles and Practice
of Parallel Programming, March 1990, pp. 197-206.
Henry Massalin and Calton Pu.
Threads and Input/Output in the Synthesis Kernel.
Proceedings of the 12th SOSP, December 1989, pp. 191-200.
Leslie Lamport.
Time, Clocks, and the Ordering of Events in a Distributed System.
Communications of the ACM, Vol. 21, No. 7 (July 1978), pp. 558-565.
Roger Haskin, et al.
Recovery Management in QuickSilver.
Alfred Z. Spector, et al.
Distributed Transactions for Reliable Systems
Ken Thompson's Turing Lecture.
Victor L. Voydock and Stephen T. Kent.
Security Mechanisms in High-Level Network Protocols.
D. Denning and P. Denning. Data Security.
Computing Surveys, Vol. 11, No. 3 (September 1979), pp. 227-249.