SRL Publications Projects Courses







600.318/418: Operating Systems

Spring 2007 Syllabus (Preliminary)  

Last Update: January 26, 2008

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. For undergraduates, it is a four credit course. 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.

Slides have been included from previous years for your reference. The lectures will make infrequent use of these slides and will not follow their structure.

All assignments have a due date and time. If no time is given, the assignment may be returned anytime during the day, and is due before midnight. Assignments which are not turned in before they are due will receive no credit.

We are using a new late policy this year. Each student has five floating late days, of which each can be used to extend the due date of any assignment by 24-hours. When turning in a late assignment, students are required to declare whether they are using late days or are taking no credit. For scheduling purposes, an assignment may have a hard deadline, past which the due date may not be extended.

Office Hours

Thursdays from 2:00 - 4:00 pm in NEB 315 and by appointment.

Office Location

NEB 315



Instructor Email

Course Mailing List (You must subscribe!)
From the account you wish to subscribe, send a message to with "subscribe cs418" as the body.

Week of Topic(s) and Papers
28 January



Silberschatz et al.: 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.


Subscribe to the course mailing list.
Homework 1: [PDF]

4 February

Memory Management


Silberschatz et al.: Ch. 8.
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.


Homework 1: Due February 4 at 10 AM.

11 February

Virtual Memory


Silberschatz et al.: Ch. 9.


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.


Project 1: Slab Allocator [PDF]

18 February

Process Control and Scheduling


Silberschatz et al.: Ch. 3, 4, 5.
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.

25 February

Process Synchronization


Silberschatz et al.: Ch. 6.


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.

3 March



Silberschatz et al.: Ch. 7.


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.


Project 1 Due: 3 March

Project 2: Kernel Keyboard Logger [PDF]

10 March

File Systems


Silberschatz et al.: Ch. 10, 11.


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.

17 March


*** The schedule is extremely provisional after this point ***

24 March

File System and Disk Management


Silberschatz et al.: Ch. 11, 12.
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.

31 March

Access Control and Security


Silberschatz et al.: Ch. 14, 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.


Project 2 Due: 30 March

Project 3: Transactional Block Store [PDF]

7 April



Silberschatz et al.: Ch. 16,17.
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]


Questions of operating system structure. Encapsulation of function, and design of kernel substrates for encapsulation rather than feature set. The argument for microkernels. Core mechanisms of a microkernel, advantages, and disadvantages.


Mon, April 14: [mp3]
Wed, April 16: [mp3]
Fri, April 18: [mp3]

14 April

Virtual Machines


Virtual Machines Lecture [Slides] [Handouts]



21 April

Advanced Topics



28 April

Conclusion and Review


Response to exam review questions (if any) or advanced topic discussion.


Project 3 Due: 27 April

9 May

Final Exam

The final exam can be obtained here [PDF], assigned at 2pm, due by Monday May 12th at 5pm.