SRL Publications Projects Courses

Courses

600.318/600.418

600.328/600.428

600.436

600.438

600.439

600.318/418: Operating Systems


 
Spring 2002 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
28 January

Introduction

Readings

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

Slides

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

Lecture

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

Homework

To be assigned

4 February

Process Control and Scheduling

Readings

Silberschatz & Galvin: Ch. 4, 5, 6.
Mercer et al.: Processor Capacity Reserves: Operating System Support for Multimedia Applications
Anderson et al.: Scheduler Effective Kernel Support for the User-bevel Management of Parallelism

Slides

Process Control Lecture: [Slides] [Handouts]

Lecture

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.

11 February

Process Synchronization

Readings

Silberschatz & Galvin: Ch. 7.

Slides

Process Synchronization Lecture: [Slides] [Handouts]

Lecture

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.

18 February

Deadlocks

Readings

Silberschatz & Galvin: Ch. 8.
J. Liedtke: Improving IPC by Kernel Design

Slides

Deadlocks Lecture: [Slides] [Handouts]

Lecture

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.

25 February

Memory Management

Readings

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

Slides

Memory Management Lecture: [Slides] [Handouts]

Lecture

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.

4 March

Virtual Memory

Readings

Silberschatz & Galvin: Ch. 10.

Slides

Virtual Memory Lecture: [Slides] [Handouts]

Lecture

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.

11 March

File Systems

Readings

Silberschatz & Galvin: Ch. 11, 12.

Slides

File Systems Lecture: [Slides] [Handouts]

Lecture

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.

25 March

File System and Disk Management

Readings

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

Slides

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

Lecture

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.

1 April

Access Control and Security

Readings

Silberschatz & Galvin: Ch. 18,19.
Lampson: Protection

Slides

Protection and Security Lecture: [Slides] [Handouts]

Lecture

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.

8 April

NOTE THAT EVERYTHING FROM HERE DOWN IS TENTATIVE.

Microkernels and Distributed Systems

Readings

Silberschatz & Galvin: Ch. 15,16.
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

Slides

Other Kernels Lecture: [Slides] [Handouts]

Lecture

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.

14 April

Discussion

22 April

Final Exam Prep

28 April

Advanced Topics

Readings

EROS: A Fast Capability System.

Lecture

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