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.
| Week of |
Topic(s) and Papers |
| 29 January |
Introduction
| Readings |
Silberschatz & Galvin: Ch. 1,2,3.
Stallings: 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 |
Imagine that a program has performed the seqence
of calls:
fd = open("/dev/null", O_RDONLY);
read(fd, &mybuf, 10);
Using the online Linux kernel source at http://lxr.linux.no/source,
for kernel version 2.2.16, list, in order, in
outline style, every function called from kernel
entry at sys_read (in
fs/read_write.c) to the device read
function for /dev/null (read_null in
drivers/char/mem.c), assuming the call is
successful. You can ignore SMP code.
Solution
|
|
| 5 February |
Process Control and Scheduling
|
| 12 February |
Process Synchronization
| Readings |
Silberschatz & Galvin: Ch. 6.
Stallings: 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.
|
|
| 19 February |
Deadlocks
| Readings |
Silberschatz & Galvin: Ch. 7.
Stallings: Ch. 6.
|
| 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.
|
|
| 26 February |
Memory Management
| Readings |
Silberschatz & Galvin: Ch. 8.
Stallings: Ch. 7.
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.
|
|
| 5 March |
Virtual Memory
| Readings |
Silberschatz & Galvin: Ch. 9.
Stallings: Ch. 8.
|
| 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.
|
|
| 12 March |
File Systems
| Readings |
Silberschatz & Galvin: Ch. 10, 11.
Stallings: Ch. 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.
|
|
| 26 March |
File System and Disk Management
| Readings |
Silberschatz & Galvin: Ch. 11,13.
Stallings: Ch. 12,11.
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.
|
|
| 2 April |
Access Control and Security
| Readings |
Silberschatz & Galvin: Ch. 19,20.
Stallings: Ch. 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.
|
|
| 9 April |
Microkernels and Distributed Systems
|
| 16 April |
Discussion
|
| 23 April |
Final Exam
|
| 30 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.
|
|
