SRL Publications Projects Courses







600.318/418: Operating Systems

Spring 2001 Syllabus (Preliminary)  

This course provides an introduction to operating systems. Topics covered include processes and process management, concurrency and synchronization, scheduling and resource management, file systems and storage systems, access control and security.

The course involves homework, examinations, and extensive systems programming assignments. It is probably a mistake that the course is listed as a three credit course. We are working to correct this. Students looking for a better sense of course expectations may wish to examine the slides for the Welcome lecture online.

The in-class lecture supplements the reading. Students are expected to do all reading assignments on time. This behavior will be encouraged by the occasional unannounced online quiz.

The syllabus that follows is a work in progress!

Week of Topic(s) and Papers
29 January



Silberschatz & Galvin: Ch. 1,2,3.
Stallings: Ch. 1, 2.


Welcome Lecture: [Slides] [Handouts]
Overview Lecture: [Slides] [Handouts]


History of operating system development. Role of an operating system. Evolution of hardware and operating systems. Course structure and plan.


Imagine that a program has performed the seqence of calls:

    		    fd = open("/dev/null", O_RDONLY);
    		    read(fd, &mybuf, 10);

Using the online Linux kernel source at, for kernel version 2.2.16, list, in order, in outline style, every function called from kernel entry at sys_read (in fs/read_write.c) to the device read function for /dev/null (read_null in drivers/char/mem.c), assuming the call is successful. You can ignore SMP code.


5 February

Process Control and Scheduling


Silberschatz & Galvin: Ch. 4, 5.
Stallings: Ch. 3,4,9.
Mercer et al.: Processor Capacity Reserves: Operating System Support for Multimedia Applications


Process Control Lecture: [Slides] [Handouts]


Programs in motion: processes, threads, and actors. Process states, queueing, and context switching. Thread models (user vs. system). Scheduling strategies and preemption. Multilevel schedulers. Fairness. The problem of ad hoc policy.

12 February

Process Synchronization


Silberschatz & Galvin: Ch. 6.
Stallings: Ch. 5.


Process Synchronization Lecture: [Slides] [Handouts]


The problem with unrestricted concurrency. Race conditions and critical sections. Software meachanisms. The Bakery Algorithm. Hardware mechanisms: atomic instructions, disabling interrupts. Operating system mechanisms: semaphores. The producer/consumer problem. The readers/writers problem. Care and feeding of philosophers. Monitors and condition variables.

19 February



Silberschatz & Galvin: Ch. 7.
Stallings: Ch. 6.


Deadlocks Lecture: [Slides] [Handouts]


Definition of deadlock. Railroads in Indianna. Conditions for deadlock. Resource allocation graphs. Methods for prevention, avoidance, and detection. Safe states. The Bankers Algorithm. An integrated solution.

26 February

Memory Management


Silberschatz & Galvin: Ch. 8.
Stallings: Ch. 7.
Bonwick: The Slab Allocator: An Object-Caching Kernel Memory Allocator


Memory Management Lecture: [Slides] [Handouts]


Rubber, roads, and operating systems. Allocation strategies for main memory. The problem of fragmentation. Overlays and placement algorithms for fixed partitions. Dynamic partitioning strategies. External fragmentation. The Buddy System. Swapping and relocation. Segmentation vs. position independent code.

Address translation, page tables, and paging. Implementations of page tables (hierarchical, hashed). TLBs and the performance impact of memory hierarchies. Memory protection and multilevel paging mechanisms. Complications of page sharing and need for inverted page tables.

The address space as a resource: understanding the proper relationship between actors, processes, and address spaces.

5 March

Virtual Memory


Silberschatz & Galvin: Ch. 9.
Stallings: Ch. 8.


Virtual Memory Lecture: [Slides] [Handouts]


Making something out of nothing: revisiting the swapping concept. Demand paging vs. prefetching. Page faults and architecture support for paging. Performance implications of memory hierarchies. Page replacement policies and ageing strategies (FIFO, LRU, Stack algorithms). Working sets and the problem of shared pages. Second chance algorithms. Page buffering and why clean frames are better than free frames. Frame allocation policies and the recurring problem of ad hoc policy in monolithic systems. Pinning. Thrashing. Variable page sizes.

12 March

File Systems


Silberschatz & Galvin: Ch. 10, 11.
Stallings: Ch. 12


File Systems Lecture: [Slides] [Handouts]


Definition of a ``file'' and purpose of a file system. Files and file attributes. Conventional file protection mechanisms. Why they do not work. Operations on files. Files as a generic interface for I/O channels. Access methods for files.

Directories and directory organization. Operations on directories. Single level, two level, and multilevel directories. Acyclic graph directories. General graph directories. Protection.

File sharing and consistency semantics. File system components and the architecture of a file system. File allocation policies and storage management strategies. Linked vs. hierarchical file structures. Log structured file systems.

26 March

File System and Disk Management


Silberschatz & Galvin: Ch. 11,13.
Stallings: Ch. 12,11.
Ruemmler and Wilkes: An Introduction to Disk Drive Modeling


File Systems II, Disk Management Lecture: [Slides] [Handouts]


Free space management. Directories as a type of file. Consistency and the problem of directory updates. Why general directory graphs are a bad idea. Backup and recovery. Block (buffer) caching. Ram disks. Placement, interleaving, and update ordering. Disk drive mechanics and performance. Interleaving and disk scheduling.

2 April

Access Control and Security


Silberschatz & Galvin: Ch. 19,20.
Stallings: Ch. 15.
Lampson: Protection


Protection and Security Lecture: [Slides] [Handouts]


Domains of protection. Domain structure. Domain implementation in UNIX. The Lampson Access Matrix. Access Control Lists (ACLs) and Capabilities. The Safety Problem. The confinement problem. Why users are not subjects. Enforceable vs. political security policies.

9 April

Microkernels and Distributed Systems


Silberschatz & Galvin: Ch. 16,17.
Stallings: Ch. 13,14.
Golub et al.: UNIX as an Application Program
Bershad and Chen: The Impact of Operating System Structure on Memory System Performance
Hartig et al.: The Performance of Microkernel-Based Systems


Other Kernels Lecture: [Slides] [Handouts]


Innovations in operating system structure. Hardware vs. software distribution. Microkernels and distributed systems. Remote procedure calls. Distributed name transparency. Remote caching and cache update/invalidation. Stateless vs. stateful file servers. Replication. Process migration.

16 April


23 April

Final Exam

30 April

Advanced Topics


EROS: A Fast Capability System.


Persistent systems. The shrinking boundary between operating systems and language runtimes. Current directions in operating system design. Open projects in SRL.