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

This year we have two updated textbooks. If you have already purchased the non-updated 6th edition of Operating Systems Concepts that will be fine. You really do need the latest version of Understanding the Linux Kernel

The syllabus that follows is a work in progress!

Week of Topic(s) and Papers
26 January

Introduction

Readings

Deitel et al.: Ch. 1,2.

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

2 February

Process Control and Scheduling

Readings

Deitel et al.: Ch. 3, 4, 8.
Mercer et al.: Processor Capacity Reserves: Operating System Support for Multimedia Applications

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.

9 February

Process Synchronization

Readings

Deitel et al.: Ch. 5.

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.

16 February

Deadlocks

Readings

Deitel et al.: Ch. 7.

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.

23 February

Memory Management

Readings

Deitel et al.: Ch. 9, 10.
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.

1 March

Virtual Memory

Readings

Deitel et al.: Ch. 11.

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.

8 March

File Systems

Readings

Deitel et al.: Ch. 13.

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.

22 March

File System and Disk Management

Readings

Deitel et al.: Ch. 12.
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.

29 March

Access Control and Security

Readings

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

5 April

NOTE THAT EVERYTHING FROM HERE DOWN IS TENTATIVE.

Microkernels and Distributed Systems

Readings

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.

12 April

Discussion

19 April

Final Exam Prep

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