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