COMP 242: Advanced Operating Systems

Instructor

Prasun Dewan, Sitterson 150. Class meets on MW, 12:30-1:45, in Room SN11. Tentative office hours: MW, 4-5pm, available any time for short questions, or make an appointment.

Teaching Assistant

Salil Sane, Sitterson 307 (Office hours to be announced).

Overview

This is a graduate-level course in the design and implementation of operating systems. The specific goals are 1) to study the implementation of an operating system, 2) to introduce you to research literature, and 3) to show you abstractions, underlying design choices, tradeoffs, and their consequences. It will be assumed you have taken an undergraduate course in the design and use of traditional operating systems. The course will augment your understanding of operating systems by addressing both new topics such as multiprocessor systems and discussing in-depth the implementation of familiar concepts such as interprocess communication. The topics covered will be related but complementary to the ones you may have seen in CS 203 and CS 243. We will study single-processor, multiprocessor, and distributed operating systems; stationary and mobile systems, and hierarchical, object-oriented, and microkernel-based implementations. The course will also introduce you to real-time systems which are covered in-depth in CS 232. You will implement the microkernel of a distributed operating system based on the Xinu implementation framework. In addition, you will write a survey of three/four papers on an emerging OS area of your choice. A good place to look for these papers in the latest SOSP (Symposium on Operating Systems Principles) proceedings. Most of the papers are on the web ( http://www-ece.rice.edu/SOSP15/paper-list.html ). You can contact me for the ones that are not online.

Text and Reference Material

(1) Comer, Operating System Design - The Xinu Approach, Prentice-Hall , 1988 (PC Edition).

(2) Singhal and Shivaratri, Advanced Operating Systems, McGraw Hill, 1994. Sid Chatterjee uses this book also for CS 203.

(3) Research papers addressing concepts not covered in the text, listed below.

(4) I plan to create and distribute a set of class notes for the course. The URL http://www.cs.unc.edu/~dewan/242/f97/notes/notes.html points to the notes I used last time I taught this course. It will give you an idea of what to expect in this offering.

Grading Policy

A grade will be assigned based on performance on programming assignments, written assignments, and exams. Exams will constitute 45% of the grade and assignments will constitute the other 55%. Class participation and extra credit will be used to decide if a borderline grade should be upgraded. You are encouraged to discuss the assignments with fellow students but required to write/code the solutions/programs individually. Also you cannnot use solutions from previous offerings of the course. Not following these rules is a violation of the honour code policy.

242 Home Page

I have created a 242 Home Page ( http://www.cs.unc.edu/~dewan/242/s99 ), where I will put the assignments and other handouts.

Tentative Schedule

The following is a tentative 15-week schedule.

(1) Function and Structure of an Operating System, Xinus, Heavyweight and Lightweight processes.

(2) Process Management.

(3) Interprocess Communication: Message Passing and other Schemes.

(4) Distributed IPC: Internetworking and Kernel-Based Remote Procedure Call.

(5) Input/Output: Device Driver Organization and Terminal Driver.

(6) Process Coordination: Duality of Operating System Structures, Synchronizing Abstract Data Types.

(7) File Management: File Operations and Physical Representation.

(8) Protection: Access Matrix, Unix, AFS, and Multics Protection

(9) Protection: Capability- and Object- Based Operating Systems

(10) Multiprocessor Systems: Cocurrency Abstractions, Time and Space Scheduling

(11) Multiprocessor Systems: Dynamic Scheduling/User-Level RPC

(12) Distributed Systems: Implementing Distributed Memory and Process Migration

(13) Mobile Systems: Scheduling, IPC, and File Access

(14) Real-Time Systems: Scheduling

(15) Organization of Operating Systems: Hierarchical, Object-, Monitor- Microkernel-, Server-, and Application- Based Implementations.

Tentative Assignments

(1) Implement Process Management (Due Week 4).

(2) Implement Message Passing (Due Week 6).

(3) Implement Distributed Message Passing and Time Management (Due Week 8).

(4) Homework (Due Week 9).

(5) Implement Distributed Terminal Driver (Due Week 11).

(6) Implement Shell ( Due Week 13).

(7) Write Paper (on topic of your choice) (Due Week 15).

Papers

1. Mike Accetta, Robert Baron, William Bolosky, David Golub, Richard Rashid, Avadis Tevanian, and Michael Young, Mach: A New Kernel Foundation for UNIX Development.

2. Gregory R. Andrews and Fred B. Schneider, Concepts and Notations for Concurrent Programming, ACM Computing Surveys, pp. 1-43 (1983).

3. Brian B. Bershad, Thomas E. Anderson, Edward D. Lazowska, and Henry M. Levy, User-Level Interprocess Communication for Shared Memory Multiprocessor Systems, ACM Transactions on Computer Systems Vol. 9(2)(1991).

4. Andrew D. Birrel and Bruce Jay Nelson, Implementing Remote Procedure Calls, ACM TOCS Vol. 2(1)(February 1984).

5. Michael J. Feeley, William E. Morgan, Fredric H. Pighin, Anna R. Karlin, Henry M. Levy, and Chandramohan A. Thekkath, Implementing Global Memory Management in a Workstation Cluster, Proceedings of the 15th Symposium on Operating System Principles, (1995).

6. John Ionnidis, Dan Duchamp, and Gerald Q. Maguire, IP- Based Protocols for Mobile Internetworking.

7. Kirk L. Johnson, M. Frans Kaashoek, and Deborah A. Wallach, CRL: High-Performance All-Software Distributed Shared Memory, Proceedings of the 15th Symposium on Operating System Principles, (1995).

8. Anthony D. Joseph, Alan F. deLespinasse, Joshua A. Tauber, David K. Gifford, and M. Frans Kaashoek, Rover: A Toolkit for Mobile Information Access, Proceedings of the 15th Symposium on Operating System Principles, (1995).

9. Lauer, H.C and Needham, R.M, On the Duality of Operating System Structures, ACM Operating System Review Vol. 13(2) pp. 3-19 (April 1979).

10. John Liedtke, On Micro-Kernel Construction, Proceedings of the 15th Symposium on Operating System Principles, (1995).

11. Cathy McCann, Raj Vaswani, and John Zahorjan, A Dynamic Processor Allocation Strategy for Multiprogrammed Shared-Memory Multiprocessors, ACM Transactions on Computer Systems, pp. 145-178 (1993).

12. Lily B. Mummert, Maria R. Ebling, and M. Satyanarayanan, Exploiting Weak Connectivity for Mobile File Access, Proceedings of the 15th Symposium on Operating System Principles, (1995).

13. Quarterman and Silberschatz, 4.2BSD and 4.3BSD as Examples of the UNIX System, ACM Computing Surveys, ().

14. J. A. Stankovic, Misconceptions About Real-Time Computing, IEEE Computer Vol. 21(10) pp. 10-19 (October 1988).

15. Mark Weiser, Brent Welch, Alan Demers, and Scott Shenker, Scheduling for Reduced CPU Energy, Usenix First Symposium on Operating Systems Design and Implementation, (1995).

16. N. Wirth, Toward a Discipline of Real-Time Programming, CACM Vol. 20(8) pp. 577-583 (Aug. 1977).

17. W. Wulf, E. Cohen, W. Corwin, A. Jones, R. Levin, C. Pierson, and F. Pollack, Hydra: The Kernel of a Multiprocessor Operating System, CACM Vol. 17(6)(June 1974).