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

Phone

410-516-4650

Instructor Email

cs418instructors@cs.jhu.edu

Course Mailing List

cs418@cs.jhu.edu (You must subscribe!)
From the account you wish to subscribe, send a message to majordomo@cs.jhu.edu with "subscribe cs418" as the body.

Week of Topic(s) and Papers
28 January

Introduction

Readings

Silberschatz 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

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

4 February

Memory Management

Readings

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

Homework

Homework 1: Due February 4 at 10 AM.

11 February

Virtual Memory

Readings

Silberschatz et al.: Ch. 9.

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.

Project

Project 1: Slab Allocator [PDF]

18 February

Process Control and Scheduling

Readings

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

25 February

Process Synchronization

Readings

Silberschatz et al.: Ch. 6.

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.

3 March

Deadlocks

Readings

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

Project

Project 1 Due: 3 March

Project 2: Kernel Keyboard Logger [PDF]

10 March

File Systems

Readings

Silberschatz et al.: Ch. 10, 11.

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.

17 March

SPRING BREAK

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

24 March

File System and Disk Management

Readings

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

31 March

Access Control and Security

Readings

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

Project

Project 2 Due: 30 March

Project 3: Transactional Block Store [PDF]

7 April

Microkernels

Readings

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

Slides

Other Kernels Lecture: [Slides] [Handouts]

Lecture

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.

Audio

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

14 April

Virtual Machines

Slides

Virtual Machines Lecture [Slides] [Handouts]

Lecture

TBA

21 April

Advanced Topics

Lecture

TBA

28 April

Conclusion and Review

Lecture

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

Project

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.