COMP 730: Operating Systems

Prerequisite: Comp 530(142) or equivalent

Distribution area: Systems

Meets programming product requirement: Yes

Project: Build the kernel of a distributed operating system

Instructor

Prasun Dewan, Sitterson 150. Class meets on TR,12:30-1:45, in Room SN155. Tentative office hours: TR, 3:30-4:30pm, available any time for short questions, or make an appointment. Email: dewan@cs.unc.edu

Overview

This is a graduate-level course on the design and implementation of modern operating systems. It will be assumed you have taken an undergraduate course in operating systems. The topics covered will be related but complementary to the ones you may have seen in CS 633 (203) and CS 243 (734). We will study single-processor, multiprocessor, and distributed operating systems; and microkernel-based implementations. You will implement the microkernel of a distributed operating system based on the Xinu thread implementation; and implement a distributed terminal service on top of the microkernel. As this is a semester-wide project in which each assignment is layered on top of previous assignments, it meets the programming product requirement. The order of topics in the course has been carefully chosen to give the necessary background for the assignments. However, the course will cover material that goes far beyond the projects. In particular, it will be not tied to any one OS design or implementation. We will start by defining an OS and, using first principles, cover a large design and implementation space.

Text and Reference Material

(1) Doug Comer, Operating System Design - The Xinu Approach, Prentice-Hall There are several versions of this book – the PC edition will probably be the most useful one for this course. The book is available at Amazon.

(2) David Solomon, Inside Windows NT, Microsoft Press (Microsoft Programming Series), ISBN 1-57231-677-2

(3) I plan to create and distribute a set of class notes for the course. The URL is http://www.cs.unc.edu/~dewan/242/s07/notes/index.html

(4) Research papers listed below. Hard copies are in the Colab (Sitterson 155).

Grading Policy

A grade will be assigned based on performance on programming assignments, written assignments, and exams. Exams will constitute 50% of the grade and assignments will constitute the other 50%. There will be a midterm and a non-cumulative final. 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 cannot use solutions from previous offerings of the course. Not following these rules is a violation of the honor code policy.

Course Home Page

I have created a course home page ( http://www.cs.unc.edu/~dewan/242/s07 ), where I will put the assignments and other handouts.

Tentative Schedule

The following is a tentative schedule.

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

(2) Process Management.

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

(4) Design and Implemenatation of Remote Procedure Call.

(5) Interrupt Processing and Real-Time Clock Management

(6) Device Driver Organization and Terminal Driver.

(7) Process Coordination: Duality of Operating System Structures

(8) Transactions in Operating Systems.

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

(10) Protection: Capabilities and Object- Based Operating Systems

(11) Multiprocessor Systems: Concurrency Abstractions, Time and Space Scheduling

(12) Organization of Operating Systems: Single and multi-address space, server-based, microkernels

(13) Distributed Systems: Organization and Process Migration

Assignments

(1) Process Management.

(2) Message Passing.

(3) Distributed Message Passing, distributed semaphores, and Real-time Clock Management.

(4) Distributed Terminal Service

(5) Teleconferencing.

To reduce the workload, I have excluded two assignments from the set I have given in the past. One of them is a shell implementation as many undergrad classes cover it. The other is a survey on three OS papers – it appears that you will get enough opportunity to write such surveys given the new proposal on grad studies. The programming assignments, together, implement a distributed micro kernel. They are different from those you may have done in 243 (734) in that they implement rather than use distributed abstractions. Thus 730 (242) is to 734 (243) what a compiler course is to a programming language course.

Papers used for course material

These papers will be covered implicitly by the notes without making explicit references to them. You can read them for additional depth.

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).