G22.3250
Honors Operating Systems

Spring 1999 -- Vijay Karamcheti


Announcements

FINAL EXAM IS ON MAY 11, 1999: 1:00-3:00pm, 102 WWH
Office hours have been changed to Thursdays, 4:15pm - 5:15pm.

Homework 2 is due April 06, 1999.

Project 3 is due May 06, 1999.
Contact Lourdes Santana (santana@cs.nyu.edu) for access to the 7th Floor of the Broadway building.
Contact Ayal Itzkovitz (ayali@cs.nyu.edu) for setting up accounts and general technical guidance.

Handouts and lecture slides for Lectures 1-13, 15-19, 22-26 are now available.
Follow the links from the appropriate lecture entry in the schedule.

General Information

Lectures: Tuesdays and Thursdays, 1:20pm-2:35pm,
102 CIWW
Office Hours: Thursdays, 4:15pm-5:15pm and by appointment,
715 Broadway, Room 704
phone: (212) 998-3496
email: vijayk@cs.nyu.edu
Mailing List: To subscribe send email to majordomo@cs.nyu.edu.
In the body of the message, simply write: subscribe g22_3250_001_sp99

To post to the mailing list, send email to g22_3250_001_sp99.

Prerequisites

One undergraduate course in algorithms, and one in C or C++ programming.

Description

This course will cover both basic and some advanced operating systems concepts, focusing primarily on uniprocessors. The emphasis will be on understanding general concepts that are applicable to a wide range of operating systems, rather than a discussion of the features of any one specific system. Topics that will be covered include: Process Management, Storage Management, I/O Systems, Protection and Security, Encryption, Extensible OSes, and Fault Tolerance, and two case studies: Linux and Windows-NT.

The course is intended for full-time Ph.D. students and will cover a lot of ground relatively quickly. To make sure that you don't fall behind in the course, I urge you to complete the assigned readings for each lecture and take full advantage of the office hours.

Course Structure

The course will consist of lectures based on material from the textbook (required), supplemented with seminal research papers from the reading list given below. Grading for the course will be based upon a handful of written and programming assignments, critiques of the research papers, and two exams (a mid-term and a final).

Textbook

Abraham Silberschatz and Peter Baer Galvin,
Operating System Concepts, Fifth Edition,
Addison-Wesley, 1998.

Reading List

Process Management
[Laue78] Lauer, H.C., and Needham, R.M., On the Duality of Operating System Structures, Proc. Second Int'l Symposium on Operating Systems, IRIA, October 1978, reprinted in Operating Systems Review, Vol. 13, No. 2, April 1979, pp. 3-19.
[Bers90] Bershad, B.N., Anderson, T.E., Lazowska, E.D., and Levy, H.M., Lightweight Remote Procedure Call, ACM Transactions on Computer Systems, Vol. 8, No. 1 (February 1990), pp. 37-55.
[Wald94] Waldspurger, C. A., and Weihl, W. A., Lottery Scheduling: Flexible, Proportional-Share Resource Management, First Symposium on Operating Systems Design and Implementation, November 1994, pp. 1-11.

Storage Management
[Denn80] Denning, P.J., Working Sets, Past and Present, IEEE Transactions on Software Engineering, SE-6, 1 (January 1980), pp. 64-84.
[Tall95] Talluri, M., Hill, M.D., and Khalidi, Y.A., A New Page Table for 64-bit Address Spaces, Proceedings of the 15th Symposium on Operating System Principles, Operating Systems Review, Vol. 29, No. 5, December 1995, pp. 184-200.

File Systems
[Rose92] Rosenblum, M., and Ousterhout, J.K., The Design and Implementation of a Log-Structured File System, ACM Transactions on Computer Systems, Vol. 10, No. 1 (February 1992), pp. 26-52.

Protection and Security
[Wall97] Wallach, D.S., Balfanz, D., Dean, D., and Felten, E.W., Extensible Security Architecture for Java, Proceedings of the 16th Symposium on Operating System Principles, Operating Systems Review, Vol. 31, No. 5, December 1997, pp. 116-128.

Encryption
[Voyd85] Voydock, V.L., and Kent, S.T., Security in High-Level Network Protocols, IEEE Communications, July 1985, pp. 12-24.

Extensible Operating Systems
[Lied95] Liedtke, J., On Micro-Kernel Construction, Proceedings of the 15th Symposium on Operating System Principles, Operating Systems Review, Vol. 29, No. 5, December 1995.
[Bers95] Bershad, B.N., Savage, S., Pardyak, P., Sirer, E.G., Fiuczunski, M., Becker, D., Chambers, C., and Eggers, S., Extensibility: Safety and Performance in the SPIN Operating System, Proceedings of the 15th Symposium on Operating System Principles, Operating Systems Review, Vol. 29, No. 5, December 1995, pp. 267-284.
[Engl95] Engler, D.R., Kaashoek, M.F., and O'Toole Jr., J., Exokernel: An Operating System Architecture for Application-Specific Resource Management, Proceedings of the 15th Symposium on Operating System Principles, Operating Systems Review, Vol. 29, No. 5, December 1995, pp. 251-266.

Fault Tolerance
[Borg89] Borg, A., Blau, W., Graetsch, W., Herrman, F., and Oberle, W., Fault-tolerance under UNIX, ACM Transactions on Computer Systems, Vol. 7, No. 1, February 1989, pp. 1-24.

Syllabus and Tentative Schedule

Lecture slides and a class synopsis will be added to the following schedule after the completion of each lecture.

1/19 Lecture 1 Overview: Administrivia and Introduction
Reading: OSC Chap. 1
Lecture Slides Handout 1
1/21 Lecture 2 Overview: Operating-System Structures
Reading: OSC Chap. 2-3
Lecture Slides
1/26 Lecture 3 Process Management: Processes and Threads
Reading: OSC Sec. 4.1-4.5
Lecture Slides
1/28 Lecture 4 Process Management: Interprocess Communication
Reading: OSC Sec. 4.5-4.7, [Laue78], [Bers90]
Lecture Slides
2/02 Lecture 5 Process Management: CPU Scheduling
Reading: OSC Sec. 5.1-5.4
Lecture Slides
2/04 Lecture 6 Process Management: Scheduling Algorithms
Reading: OSC Sec. 5.5-5.7, [Wald94]
Lecture Slides
2/09 Lecture 7 Process Management: Synchronization
Reading: OSC Sec. 6.1-6.4
Lecture Slides
2/11 Lecture 8 Process Management: Synchronization (contd.)
Reading: OSC Sec. 6.5-6.6
Lecture Slides
2/16 Lecture 9 Process Management: Language Support for Concurrency
Reading: OSC Sec. 6.7 + other stuff
Lecture Slides Project 1
2/23 Lecture 10 Process Management: Deadlocks
Reading: OSC Sec. 7.1-7.4
Lecture Slides
2/25 Lecture 11 Process Management: Deadlock Avoidance and Recovery
Reading: OSC Sec. 7.5-7.9
Lecture Slides
3/02 Lecture 12 Storage Management: Memory Management
Reading: OSC Chap. 8
Lecture Slides
3/04 Lecture 13 Storage Management: Virtual Memory
Reading: OSC Chap. 9
Lecture Slides
3/09 --- MID-TERM EXAM ---
3/11 Lecture 14 Storage Management: Virtual Memory (contd.)
Reading: [Denn80], [Tall95]
3/16 --- Spring Break ---
3/18 --- Spring Break ---
3/23 Lecture 15 Storage Management: File Systems
Reading: OSC Chap. 10
Lecture Slides
3/25 Lecture 16 Storage Management: File Systems (contd.)
Reading: OSC Chap. 11, [Rose92]
Lecture Slides
3/30 Lecture 17 I/O Systems: Secondary Storage Structure
Reading: OSC Chap. 13
Lecture Slides
4/01 Lecture 18 Protection
Reading: OSC Chap. 19
Lecture Slides
4/06 Lecture 19 Security
Reading: OSC Chap. 20
Lecture Slides
4/08 Lecture 20 Language-based Protection and Security
Reading: [Wall97]
4/13 Lecture 21 Case Study: Windows NT
Reading: OSC Chap. 23
4/15 Lecture 22 Case Study: UNIX/Linux
Reading: OSC Chap. 21-22
Lecture Slides
4/20 Lecture 23 Advanced Topics: Encryption
Reading: [Voyd85]
Lecture Slides
4/22 Lecture 24 Advanced Topics: Encryption (contd.)
Lecture Slides
4/27 Lecture 25 Advanced Topics: Extensible OSes
Reading: [Lied95]
Lecture Slides
4/29 Lecture 26 Advanced Topics: Extensible OSes (contd.)
Reading: [Bers95], [Engl95]
Lecture Slides