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