This page contains book summaries written by me for the OS/NDS/ARCH
sessions of the system quals.
Some of the paper summaries were written by me, but I was too lazy
to write summaries for all of them.
The others came from other people:
- the other fellows from
the 2002 study group
(summaries);
- Emre
Kiciman and the guys from the 2001 study group (summaries);
- Petros
Maniatis (summaries);
- Armando
Fox and other collaborators to the Treasure
Trove o'Paper Summaries.
The list of papers below may be outdated and there are also papers
that I decided to read that were not
in the original list (I tried to mark all of them with a ).
Well, good luck with the studies.
Books
Modern Operating Systems, 2nd Edition
Andrew S. Tanenbaum
Chap. 1 | Introduction |
Chap. 2 | Processes and Threads |
Chap. 3 | Deadlocks |
Chap. 4 | Memory Management |
Chap. 5 | Input / Output |
Chap. 6 | File Systems |
Chap. 7 | Multimedia Operating System |
Chap. 8 | Multiple Processor Systems |
Chap. 9 | Security |
Chap. 10 | Case Study: Unix and Linux |
Chap. 11 | Case Study: Windows 2000 |
Chap. 12 | Operating System Design |
Distributed Systems: Concepts and Design
George Coulouris et al.
Chap. 1 | Characterization of Distributed Systems |
Chap. 2 | System Models |
Chap. 3 | Networking and Internetworking |
Chap. 4 | Interprocess Communication |
Chap. 5 | Distributed Objects and Remote Invocation |
Chap. 6 | Operating System Support |
Chap. 7 | Security |
Chap. 8 | Distributed File Systems |
Chap. 9 | Name Services |
Chap. 10 | Time and Global States |
Chap. 11 | Coordination and Agreement |
Chap. 12 | Transactions and Concurrency Control |
Chap. 13 | Distributed Transactions |
Chap. 14 | Replication |
Chap. 15 | Distributed Multimedia Systems |
Chap. 16 | Distributed Shared Memory |
Chap. 17 | Case Study: Corba |
Chap. 18 | Case Study: Mach |
Computer Architecture: A Quantitative Approach
John Hennesy and David A. Patterson
Chap. 1 | Fundamentals of Computer Design |
Chap. 2 | Instruction Set Principles and Examples |
Chap. 3 | Pipelining [2] |
Chap. 4 | Advanced Pipelining and Instruction Level Parallelism [2] |
Chap. 5 | Memory-Hierarchy Design |
Chap. 6 | Storage Systems |
Chap. 7 | Interconnection Networks |
Chap. 8 | Multiprocessors [2] |
Parallel Computer Architecture: A Hardware/Software Approach
David Culler and Jaswinder Singh
Chap. 1 | Introduction |
Chap. 2 | Parallel Programs |
Chap. 3 | Programming for Performance |
Chap. 4 | Workload-Driven Evaluation |
Chap. 5 | Shared Memory Multiprocessors |
Chap. 6 | Snoop-Based Multiprocessor Design |
Chap. 7 | Scalable Multiprocessors |
Chap. 8 | Directory-Based Cache Coherence |
Chap. 9 | Hardware/Software Tradeoffs |
Chap. 10 | Interconnection Network Design |
Chap. 11 | Latency Tolerance [2] |
Chap. 12 | Future Directions |
Papers
Virtual Memory
VM1. Virtual Memory, Processes
and Sharing in MULTICS [2]
R C Daley and J B Dennis, Comm of the ACM, Vol 11, No 5, May 1968,
pp 306-312.
VM2. The MULTICS Virtual
Memory: Concepts and Design
A Bensoussan, C T Clingen and R C Daley, Comm of the ACM, Vol 15,
No 5, May 1972, pp 308-318.
VM3. Multics VM -- Tutorial and Reflections
by Paul Green.
VM4. Working Sets, Past and
Present [2]
P J Denning, IEEE Transactions on Software Engineering, SE-6, 1,
Jan 1980, pp 64-84.
VM5. WSCLOCK - A Simple and Effective Algorithm
for Virtual Memory Management
R Carr and J Hennessy, Proc 8th SOSP, Dec 1981, pp 87-95.
VM6. Virtual Memory Management in the VAX/VMS
Operating System
H M Levy and P H Lipman, Computer, Vol 15, No 3, March 1982, pp
35-41.
VM7. A New Page Table for 64-bit
Address Spaces [2]
M Talluri, M D Hill and Y A Khalidi, Proc 15th SOSP, Operating
Systems Review,
Vol 29, No 5, December 1995, pp 184-200.
VM8. Machine-Independent Virtual
Memory Management for Paged Uniprocessor and Multiprocessor Architectures
[2]
R F Rashid et al, IEEE Transactions on Computers, Vol 37, No 8,
August 1988, pp 896-908.
VM9. The Duality of Memory and
Communication in the Implementation of a Multiprocessor Operating System
M Young et al, Proc 11th SOSP, November 1987, pp 63-76.
VM10. Virtual Memory Primitives for User Programs
A W Appel and K Li, Proc 4th ASPLOS, Vol 26, No 4, 1991, pp 96-107.
VM11. Application-Controlled
Physical Memory using External Page-Cache Management [2][3]
K Harty and D Cheriton, Proc 5th ASPLOS, October 1992, pp 187-199.
VM12. Architectural Support for
Translation Table Management in Large Address Space Machines
J. Huck and J. Hays, In Proc. 20th Int. Symp. on Computer Architecture
(ISCA '93),
pages 39--50, San Diego, CA, May 1993.
VM13. Virtual Memory for an
Object-Oriented Language
Ted Kaehler. Byte, 6(8):378--387, August 1981.
Distributed Shared Memory
DSM1. Memory Coherence in Shared
Virtual Memory Systems
K Li and P Hudak, ACM Trans. Computer Systems Vol 7, No 4, Nov
1989, pp 321-359..
DSM2. Implementation and Performance
of Munin
J Carter, J Bennett and W Zwaenepoel, Proceedings of the 13th SOSP,
Oct 1991, pp 152-164.
DSM3. Shared Memory Consistency Models: A Tutorial
S V Adve and K Gharachorloo, Digital Western Research Lab, Tech
Report No 95/7, 1995, .
DSM4. Treadmarks: Shared Memory Computing on Networks of Workstations
C Azma, A L Cox, S Dwarkadas, P Keleher, H Lu, R Rajamony, W Yu
and W Zwaenepoel,
IEEE Computer, Vol 29, No 2, Feb 1996, pp 18-28.
DSM5. Memory Consistency Models
David Mosberger. Technical Report TR93/11, Department of
Computer Science, University of Arizona, 1993.
Synchronization
S1. Communicating Sequential
Processes [2]
C.A.R Hoare, Communications of the ACM, Vol 21, No 8, August 1978,
pp 666-677.
S2. Guarded Commands, Nondeterminancy, and
Formal Derivation of Programs
E.W. Dijkstra, Communications of the ACM, Vol 18, No 8, August
1975, pp 453-457.
S3. Monitors:
An Operating System Structuring Concept [2]
C A R Hoare, Communications of the ACM, Vol 17, No 10,, October
1974, pp 549-557.
S4. Experience with Processes
and Monitors in Mesa [2]
B W Lampson and D D Redell, Communications of the ACM, Vol 23,
No 2, February
1980, pp 105-117.
S5. Threads and Input/Output
in the Synthesis Kernel [2]
H Massalin and C Pu, Proc 12th SOSP, December 1989, pp 191-200.
S6. An Introduction to Programming with Threads
A Birrell, , 1989, .
S7. Practical Considerations
for Non-Blocking Concurrent Objects [2]
B N Bershad, Proc 13th Intl Conf on Distributed Computing Systems,
May 1993, .
S8. On the Duality of Operating
System Structures [2]
H C Lauer and R M Needham, Proc of 2nd SOSP, Operating Systems
Review, Vol 13,
No 2, April 1979, pp 3-19.
Process Scheduling and Migration [Summary]
PSM1. Trace-Driven Modeling
and Analysis of CPU Scheduling in a Multiprogramming System [2]
S W Sherman, F Baskett, and J C Browne, Communications of the ACM,
Vol 15, No 12,
December 1972, .
PSM2. Transparent Process Migration:
Design Alternatives and the Sprite Implementation [2]
F Douglis and J K Ousterhout, Software Practice and Experience,
Vol 21, No 8,
August 1991, pp 757-785.
PSM3. Scheduler Activations:
Effective Kernel Support for the User-Level Management of Parallelism
[2][3]
T Anderson, B Bershad, E Lazowska, and H Levy, ACM Transactions
on Computer Systems,
Vol 10, No 1, February 1992, pp 53-79.
Deadlocks
D1. System
Deadlocks
E G Coffman Jr, M J Elphick, and A Shoshani, Computing Surveys,
Vol 3, No 2,
June 1971, pp 67-78.
File Systems
FS1. Multics Input/Output
System
R J Feiertag and E I Organick, Proc of 3rd SOSP, 1971, pp 35-41.
FS2. Input/Output Optimizations
and Disk Architectures: A Survey
A J Smith, Performance Evaluation, Vol 1, 1981, pp 104-117.
FS3. A Fast File System For
UNIX [2]
M K McKusick, W N Joy, S J Leffler, and R S Fabry, ACM Transactions
on Computer
Systems, Vol 2, No 3, August 1984, pp 181-197.
FS4. Vnodes: An Architecture
for Multiple File System Types in Sun UNIX
S R Kleiman, Proceedings of the Summer Usenix Conference, Atlanta,
GA, 1986, pp 238-247.
FS5. The Cedar File System
David Gifford et al. Communications of the ACM, vol 31, number
3, 1988.
FS6. Reimplementing the Cedar
File System Using Logging and Group Commit
R Hagmann, Proc of 11th SOSP, Operating System Review, Vol 21,
No 5, November 1987,
pp 115-162.
FS7. Evolving the Vnode Interface
D Rosenthal, Proceedings of the Summer Usenix Conference, Anaheim,
CA, June 1990,
pp 107-117.
FS8. The Design and Implementation
of a Log-Structured File System
M Rosenblum and J K Ousterhout, ACM Transactions on Computer Systems,
Vol 10, No 1,
February 1992, pp 26-52.
Distributed File Systems [Summary]
DFS1. Design and Implementation
of the Sun Network Filesystem [2][3]
R Sandberg et al., Proceedings of the Summer 1985 USENIX Conference,
June 1985, .
DFS2. File System Design for an
NFS File Server Appliance
J Hitz, J Lau, and M Malcolm M, USENIX Winter Conference, San Francisco,
CA, 1994, .
DFS3. Leases:
An Efficient Fault-Tolerant Mechanism for Distributed File Cache Consistency
C Gray and D Cheriton, Proc of 12th SOSP, December 1989, .
DFS4. Replication in the Harp
File System [2]
B Liskov, et al., Proc of 13th SOSP, October 1991, .
DFS5. Disconnected Operation
in the Coda File System [2][3]
J J Kistler and M Satyanarayanan, ACM Transactions on Computer
Systems, Vol 10, No 1,
February 1992, pp 3-25.
DFS6. The Zebra Striped Network
File System
J Hartman and J Ousterhout, , Proc of 14th SOSP, December 1993.
DFS7. Serverless Network File
Systems
T Anderson et al, Proc of 15th SOSP, December 1995.
Clocks, Time, and Events
CTE1. Time, Clocks, and Ordering
of Events in a Distributed System
L Lamport, Comm. ACM, Vol 21, No 7, July 1978, pp 558-565.
CTE2. Internet Time Synchronization: the Network
Time Protocol
D L Mills, IEEE Transactions on Communications, vol. 39, no. 10,
Oct. 1991, .
CTE3. Distributed Simulation
and the Time Warp Operating System
D Jefferson et al, Eleventh SOSP, Operating Systems Review, 1987,
Vol 21 No 5, pp 77-93.
Multiprocessor Systems
MS1. Simple But Effective Techniques
for NUMA Memory Management
W Bolosky, R Fitzgerald, and M Scott, Proc of 12th SOSP, Operating
Systems Review,
Vol 23, No 5, December 1989, pp 19-31.
MS2. Operating System Support
for Improving Data Locality on CC-NUMA Compute servers
B Verghese, S Devine, A Gupta, and M Rosenblum, Proc of the Seventh
Intl Conf on
Architectural Support for Programming Languages and Operating Systems,
Cambridge, MA, 1996.
Communication
C1. Implementing Remote Procedure
Calls
A D Birrell and B J Nelson, ACM Transactions on Computer Systems,
Vol 2, No 1,
February 1984, pp 39-59.
C2. Lightweight Remote Procedure
Call [2]
B N Bershad, T E Anderson, E D Lazowska and H M Levy, ACM Transactions
on Computer Systems,
Vol 8, No 1, February 1990, pp 37-55.
Distributed Objects
DO1. The Object Model: A Conceptual Tool for
Structuring Software
A K Jones, In Operating Systems: An Advanced Course R. Bayer, et
al. Ed., Springer-Verlag,
1979, pp 7-16.
DO2. Network Objects
A Birrell, G Nelson, S Owicki and E Wobber, Proceedings of the
14th SOSP, December 1993.
DO3. CORBA: Integrating Diverse
Applications Within Distributed Heterogeneous Environments
Steve Vinoski, IEEE Communications Magazine, Vol. 14, No. 2, February,
1997.
Protection and Security
PS1. A Hardware Architecture
for Implementing Protection Rings [2][3]
M D Schroeder and J H Saltzer, Communications of the ACM, Vol 15,
No 3, March 1972, pp 157-170.
PS2. A Note on the Confinement
Problem
B W Lampson, Communications of the ACM, Vol 16, No 10, October
1973, pp 613-615.
PS3. The Protection of Information
in Computer Systems
J H Saltzer, Proceedings of the IEEE, Vol 63, No 9, September 1975,
pp 1278-1308.
PS4. Data Security [2][3]
D E Denning and P J Denning, Computing Surveys, Vol 11, No 3, September
1979, pp 227-249.
PS5. Guardians and Actions:
Linguistic Support for Robust, Distributed Programs
B Liskov and R Scheifler, ACM Trans. on Programming Languages and
Systems Vol 5, No 3,
July 1983, pp 381-404.
PS6. Reflections on Trusting Trust
K Thompson, Communication of the ACM, Vol 27, No 8, August 1984,
pp 761-763.
PS7. Why Cryptosystems Fail
R J Anderson, Communications of the ACM, Vol 37, No 11, November
1994.
Authentication
A1. Using Encryption for Authentication
in Large Networks of Computers [2]
R M Needham and M D Schroeder, Communications of the ACM, Vol 21,
No 12, December 1978,
pp 993-999.
A2. Kerberos: An Authentication
Service for Open Network Systems
J G Steiner, C Neuman, and J I Schiller, USENIX Winter Conference
Proceedings, February
1988, pp 191-202.
A3.
Limitations of the Kerberos Protocol
S M Bellovin and M Merritt, Computer Comm. Review, Vol 20, No 5,
October 1990, .
A4. The
Evolution of the Kerberos Authentication Service
J Kohl, B C Neuman, and T Ts'o, EurOpen Conference Proceedings,
Norway, May 1991, .
A5. A
Logic of Authentication
M Burrows, M Abadi, and R Needham, ACM Transactions on Computer
Systems, Vol 8, No 1,
February 1990, pp 18-36.
A6. Authentication in Distributed
Systems: Theory and Practice [2]
B Lampson, M Abadi, M Burrows, and E Wobber, Proc of 13th SOSP,
Operating Systems Review, Vol 25,
No 5, October 1991, pp 165-182.
A7. Password Security: A Case
History
R Morris, and K Thompson, Communications of the ACM, Vol 22, No
11, November 1979, pp 594-597.
Name Services
NS1. Designing a Global Name
Service [2]
B W Lampson, ACM Reprint No. 0-89791-198-9/86/0800-0001, September
1986, .
NS2.
Development of the Domain Name System
P V Mockapetris and K J Dunlap, Proc SIGCOMM 88, Computer Communication
Review, Vol 18, No 4,
August 1988, pp 123-133.
NS3. Decentralizing a Global
Naming Service for Improved Performance and Fault Tolerance
D Cheriton and T Mann, ACM Transactions on Computer Systems, Vol
7, No. 2, May 1989, pp 147-183.
Coordination and Agreement
CA1. Weighted Voting for Replicated Data
D Gifford, Proc of 7th SOSP, December 1979.
CA2. Understanding the Limitations
of Causally and Totally Ordered Communication
D Cheriton and D Skeen, Proce of 14th SOSP, December 1993.
Transactions and Recovery
TR1. Recovery Techniques
for Database Systems
J S M Verhofstad, Computing Surveys, Vol 10, No 2, June 1978, pp
167-195.
TR2. The Transaction Concept:
Virtues and Limitations
J Gray, Proc. 7th International Conference on Very Large Data Bases,
September 1981, pp 144-154.
TR3. Operating System Support
for Database Management
M Stonebraker, Communications of the ACM, Vol 24, No 7, July 1981,
pp 412-418.
TR4. Problems in Supporting
Database Transactions in an Operating System Transaction Manager
M Stonebraker, D DuBourdieux, W Edwards,, Operating Systems Review,
Vol 19, No 1, January 1985, pp 6-14.
TR5. Analysis of Transaction
Management Performance
D Duchamp, Proc of 12th SOSP, December 1989, .
TR6. Recovery Management in
QuickSilver
R Haskin, Y Malachi, W Sawdon and G Chan, ACM Trans. on Computer
Systems 6(1), February 1988, pp 82-108.
TR7. The Rio File Cache: Surviving
Operating System Crashes
P M Chen, W T Ng, S Chandra, C Aycock, G Rajamani, and D Lowell,
Proc of the 1996 Intl Conf on
Architectural Support for Programming Languages and Operating Systems,
October 1996.
Fault Tolerance
FT1. Fault Tolerance Under UNIX
A Borg, W Blau, W Graetsch, F Herrmann, and W Oberle, ACM Transactions
on Computer Systems,
Vol 7, No 1, February 1989, pp 1-24.
FT2. A NonStop Kernel
J Bartlett, Proc of 8th SOSP, Operating Systems Review, Vol 11,
No 5, November 1977, pp 23-31.
FT3. Hive: Fault Containment
for Shared-Memory Multiprocessors.
J Chapin, M Rosenblum, S Devine, T Lahiri, D Teodosiu, and A Gupta,
Proc of 15th SOSP, December 1995, .
Computer Networks
CN1. Congestion Avoidance
and Control [2]
V Jacobson, Proc ACM SIGCOMM, 1988, pp 314-329.
CN2. On the Self-Similar Nature
of Ethernet Traffic
W E Leland, M S Taqqu, W Willinger and D V Wilson, Proc ACM SIGCOMM,
1993, pp 183-193.
CN3. The Design and Philosophy of the DARPA
Internet Protocols
David D. Clark. ACM SigComm Symposium, August 1988.
Case Studies in O.S.
CS1. The Structure of the
THE Multiprogramming System
E W Dijkstra, Communications of the ACM, Vol 11, No 5, May 1968,
pp 341-346.
CS2. Multics - The First Seven Years
J Corbato, J H Saltzer, and C T Clingen,, Proc. Spring Joint Computer
Conference, AFIPS,
May 1972, pp 571-583.
CS3. HYDRA: The Kernel of a Multiprocessor
Operating System
W Wulf et al, Communications of the ACM, Vol 17, No 6, June 1974,
pp 337-345.
CS4. VM/370: A study of Multiplicity and Usefulness
L H Seawright, and R A MacKinnon, IBM Systems Journal Vol 18, No
1, 1979, pp 4-17.
CS5. The UNIX Time-Sharing
System
D M Ritchie and K Thompson, The Bell System Technical Journal,
Vol 57, No 6, July-August 1978,
Part 2, pp 1905-1929.
CS6. UNIX Implementation
K Thompson, The Bell System Technical Journal, Vol 57, No 6, July-August
1978, Part 2, pp 1931-1946.
CS7. The Unix Time-Sharing System:
The Unix Shell
S R Bourne, Bell System Technical Journal, Vol 57, No 6, July-August
1978, pp 1971-1990.
CS8. The Evolution of the MVS Operating System
M A Auslander, D C Larkin and A L Scherr,, IBM Journal of Research
and Development, Vol 25,
No 5, September 1981, pp 471-482.
CS9. Observations on the Development
of an Operating System
H C Lauer, Proc of 8th SOSP, Operating Systems Review, Vol 15,
No 5, December 1981, pp 30-36.
Extensibility, MicroKernels and Virtual Machines
EX1. Survey of Virtual Machine
Research
R P Goldberg, Computer, Vol 7, No 6, June 1974, pp 34-45.
EX2. Extensibility: Safety
and Performance in the SPIN Operating System [2]
B N Bershad, S Savage, P Pardyak, E G Sirer, M Fiuczunski, D Becker,
C Chambers, and S
Eggers, Proc of 15th SOSP, December 1995, pp 267-284.
EX3. Exokernel: An Operating
System Architecture For Application-specific Resource Management. [2]
D R Engler, M F Kaashoek, and J O'Toole Jr, Proc of 15th SOSP,
December 1995, pp 251-266.
EX4. A Caching Model of Operating
System Kernel Functionality [2]
D Cheriton and K Duda, Proc of First OSDI, November 1994, pp 179-193.
EX5. On micro-kernel construction
J Liedtke, Proc of 15th SOSP, December 1995.
Case Studies in Distributed Systems
CDS1. The LOCUS Distributed
Operating System
B Walker, et al, Proc of 9th SOSP, October 1983, .
CDS2. Experience with Grapevine:
The Growth of a Distributed System
M Schroeder, A Birrell, and R Needham, ACM Transactions on Computer
Systems, Vol 2, No 1,
February 1984, pp 3-23.
CDS3. VAXclusters: A Closely-Coupled
Distributed System
N P Kronenberg, H M Levy, and W D Strecker, ACM Transactions on
Computer Systems, Vol 4,
No 2, May 1986, pp 130-146.
CDS4. The V Distributed System
D Cheriton, Communications of the ACM, March 1988, .
CDS5. The Sprite Network
Operating System
J Ousterhout et al, IEEE Computer, February 1988, .
CDS6. Amoeba: A Distributed
Operating System for the 1990s
S J Mullender, G van Rossum, A S Tanenbaum, R van Renesse, and
H van Staveren, Computer,
Vol 23, No 5, May 1990, pp 44-53.
CDS7. The Information Bus - An Architecture
for Extensible Distributed Systems
B Oki et al, Proc of 14th SOSP, December 1993, .
CDS8. Plan 9 from Bell Labs
R Pike et al, Computing Systems, Vol 8, No 3, Summer 1995, pp 221-254.
Words of Wisdom
WW1. The Emperor's Old Clothes
C A R Hoare, Communications of the ACM, Vol 24, No 2, February
1981, pp 75-83.
WW2.
Hints for Computer System Design
B W Lampson, Proc 9th SOSP, October 1983, pp 33-48.
WW3. End-to-End Arguments in System Design
J H Saltzer, D P Reed and D D Clark, ACM Transactions on Computer
Systems, Vol 2, No 4,
Nov 1984, pp 277-288.
Others (CS240)
O1. Eliminating Receive Livelocks in an Interrupt-driven
Kernel
Jeffrey C. Mogul.