This schedule is tentative more than two weeks in advance.

Textbook chapters that should cover similar material are given from Anderson and Dahlin, Operating Systems: Principles and Practice, Second Edition, our recommended textbook; from Arpaci-Dusseau, Operating Systems: Three Easy Pieces, which is freely and legally available online; and from Silberchartz, Galvin, and Gagne, Operating Systems Concepts, Ninth Edition. (I've tried to keep the readings up-to-date as I move topics around in the schedule, but I may not always have succeeded.)

DateTopicAssignment
Week 1
Tue 15 Jan

What are OSes? / Logistics

 [  |
screencapture (webm; browser) | audio only
 ]
Anderson&Dahlin: 1.1-2
Arpaci-Dusseau: 2, 3
Silberchartz: 1, 2.1-5, 3.1
  • What is an operating system
  • Dual-mode operation; protection; exceptions
  • process VMs
  • Process = thread + address space
  • the Unix/Monolithic kernel design
  • xv6 and Unix
  • System calls (in xv6)
  • logistics
Thu 17 Jan

Multiprogramming and Dual-Mode Operation

 [  |
screencapture (webm; browser) | audio only
 ]
Anderson&Dahlin: 2.1-6
Arpaci-Dusseau: 3.2, 4.1, 4.3-5, 6.2-3
Silberchartz: ???
  • System calls in xv6 (continued)
  • Other exception handling
  • Context switches generally
  • Context switches in xv6 (start)
Fri 18 Jan
Quiz 01 (post-quiz for week 1) released, due 2019-01-22 12:15
xv6 introduction released
Week 2
Tue 22 Jan

Monolithic Kernels, the Unix API 1

 [  |
screencapture (webm; browser) | audio only
 ]
Anderson&Dahlin: 3.5, 2.7, 3.1-3
Arpaci-Dusseau: 4.2, 4.5, 5, 6.2-4
Silberchartz: 3.3-4?, 11.1

It appears that there was an audio problem midway through this recording. You might also look at last semester’s lectures for when similar topics were covered.

  • Context switches in xv6 (finish)
  • Interrupt disabling
  • Process control blocks
  • POSIX versus Unix
  • Process creation and management: fork(), exec*(), wait()
  • Shells, generally
Quiz 01 (post-quiz for week 1) due 12:15 (released 2019-01-18)
Thu 24 Jan

The Unix API 2

 [  |
screencapture (webm; browser) | audio only
 ]
Anderson&Dahlin: 3.2-3, 4.5-6
Arpaci-Dusseau: [missing POSIX API], 7.1
Silberchartz: 11.2, 6.1
  • Unix: everything is a file, stdio, stdout
  • stdio.h versus system calls
  • POSIX file API: pipe(), open(), read(), write(), close()
Fri 25 Jan
Quiz 02 (post-quiz for week 2) released, due 2019-01-29 12:15
xv6 introduction due at 11:59pm
shell released
Week 3
Mon 28 Jan

(add deadline)

Tue 29 Jan

The Unix API 3 / Scheduling 1

 [  |
screencapture (webm; browser) | audio only
 ]
Anderson&Dahlin: 7.1, 7.5
Arpaci-Dusseau: 7.2-9
Silberchartz: 3.2, 6.2-3
  • POSIX API: pipe() (finish)
  • xv6 creating the first process
  • threads versus processes
  • queues of processes and schedulers
    • aside: non-CPU scheduling
  • alternating I/O and CPU bursts
  • the process state machine
Quiz 02 (post-quiz for week 2) due 12:15 (released 2019-01-25)
Thu 31 Jan

Scheduling 2

 [  |
screencapture (webm; browser) | audio only
 ]
Anderson&Dahlin: 7.1,
Arpaci-Dusseau: 8, 9, 25,
Silberchartz: 6.7
  • scheduling metrics: fairness, response time, throughput
  • FCFS, RR
  • priority scheduling
  • SJF, SRTF
  • approximating SJF: multi-level feedback scheduling
Fri 01 Feb
Quiz 03 (post-quiz for week 3) released, due 2019-02-05 12:15
shell checkpoint due at 11:59pm
Week 4
Tue 05 Feb

Scheduling 3 / Threads

 [  |
screencapture (webm; browser) | audio only
 ]
Anderson&Dahlin: 7.4, 4.1-4, 5.1
Arpaci-Dusseau: 26.-26.5, 27.1-2, 28.1-5
Silberchartz: 5.1-4
  • proportional share scheduling
    • lottery scheduling
  • Linux’s Completely Fair Scheduler
  • (if time) real-time scheduling
  • pthreads API — pthread_create (start)
Quiz 03 (post-quiz for week 3) due 12:15 (released 2019-02-01)
Thu 07 Feb

Threads 2 / Synchronization 1: Locks 1

 [  |
screencapture (webm; browser) | audio only
 ]
Anderson&Dahlin: 5.1, 5.3, 5.7
Arpaci-Dusseau: 28.1-14
Silberchartz: 5.4
  • pthreads API — pthread_create, pthread_join
  • some pthreads examples
  • bank account synchronization example / lost write
  • race conditions
  • building locks is tricky: too much milk
  • mutual exclusion / critical sections
  • locks
  • aside: standard container rules
  • disabling interrupts for locks
Fri 08 Feb
Quiz 04 (post-quiz for week 4) released, due 2019-02-12 12:15
shell due at 11:59pm
lottery scheduler released
Week 5
Tue 12 Feb

Synchronization 2: Locks 2, Mutexes

 [  |
screencapture (webm; browser) | audio only
 ]
Anderson&Dahlin: 5.3-4, 5.8
Arpaci-Dusseau: 30, 31
Silberchartz: 5.5-8
  • disabling interrupts for locks, continued
  • load/store reordering
  • cache coherency, MSI and snooping
  • atomic operations: test-and-set, CAS
  • xv6’s spinlock
  • test-and-test-and-set
  • false sharing
  • avoiding busy-waits: mutexes
  • barriers
Quiz 04 (post-quiz for week 4) due 12:15 (released 2019-02-08)
Thu 14 Feb

Synchronization 3: Semaphores and Monitors

 [  |
screencapture (webm; browser) | audio only
 ]
Anderson&Dahlin: 5.5, ?6.2
Arpaci-Dusseau: 29, 31.5
Silberchartz: 5.7-9
  • barriers continued
  • counting semaphores
    • producer/consumer with counting semaphores
  • monitors
    • producer/consumer with monitors (start)
Fri 15 Feb
Quiz 05 (post-quiz for week 5) released, due 2019-02-19 12:15
lottery scheduler due at 11:59pm
life released
Week 6
Tue 19 Feb

Synchronization 4: Monitors continued / Reader+Writer Locks

 [  |
screencapture (webm; browser) | audio only
 ]
Anderson&Dahlin: 6.2, 6.5
Arpaci-Dusseau: 32
Silberchartz: 7.1-6
  • producer/consumer with monitors (continued)
  • intuition for using monitors
  • relating monitors and counting semaphores
  • reader/writers problem
    • reader/writers with monitors
    • reader or writer priority
  • POSIX rwlocks
Quiz 05 (post-quiz for week 5) due 12:15 (released 2019-02-15)
Thu 21 Feb

Synchronization 5: Reader+Writer con't / Deadlock

 [  |
screencapture (webm; browser) | audio only
 ]
Anderson&Dahlin: 4.9, 6.3, 8.2-3
Arpaci-Dusseau: 33
Silberchartz: 4.5
  • reader/writers problem (con’t)
  • deadlock
    • definition: resources and conditions
    • examples
  • deadlock prevention
  • deadlock detection and resource acquisition graphs
Fri 22 Feb
Quiz 06 (post-quiz for week 6) released, due 2019-02-26 12:15
life due at 11:59pm
pool released
Week 7
Tue 26 Feb

Alternatives to Threads / Virtual Memory 1

 [  |
screencapture (webm; browser) | audio only
 ]
Anderson&Dahlin: 8.2-3, 9.6-7
Arpaci-Dusseau: 13, 15, 18-20
Silberchartz: 8.1-2, 8.5-7, 9.3, 9.7
  • (briefly) event-based programming/message passing
  • review: what is virtual memory?
  • xv6 paging
  • system calls and memory protection
Quiz 06 (post-quiz for week 6) due 12:15 (released 2019-02-22)
Thu 28 Feb

Virtual Memory 2: mmap, page cache

 [  ]
Anderson&Dahlin: 9.6, 9.5
Arpaci-Dusseau: 21-22.4
Silberchartz: 9.7, 9.2, 9.4-6
  • page table tricks
    • allocate on demand
    • copy-on-write
  • memory mapped files
    • POSIX mmap
    • /proc/$$/maps
  • demand paging
  • the page cache
Fri 01 Mar
Quiz 07 (post-quiz for week 7) released, due 2019-03-06 23:59
pool due at 11:59pm
Week 8
Tue 05 Mar

Midterm Review

 [ 
screencapture (webm; browser) | audio only
 ]
Thu 07 Mar

Midterm

Fri 08 Mar
xv6 paging+protection released
Week 9
Tue 12 Mar
(no class)
Thu 14 Mar
(no class)
Fri 15 Mar
(no class)
Week 10
Tue 19 Mar

Virtual Memory 3: page cache (part 2), page replacement

 [  |
screencapture (webm; browser) | audio only
 ]
Anderson&Dahlin: 9.5
Arpaci-Dusseau: 22.5-22.12
Silberchartz: 9.6, 9.9-10
  • the page cache (continued)
  • Linux process memory map data structures
  • dirty bits and simulating them
  • page replacement algorithms
    • ideal: Belady’s MIN
    • ideal possible: LRU
  • working set and Zipf models
  • accessed bits
  • page replacement algorithms (possible)
    • second chance
Thu 21 Mar

Virtual 4 / I/O 0

 [  |
screencapture (webm; browser) | audio only
 ]
Anderson&Dahlin: 11.3, 13.2-3
Arpaci-Dusseau: 36, 39, 40.1-4
Silberchartz: 13.2-5, 11.1, 12.1-4
  • page replacement algorithms (possible, con’t)
    • SEQ
    • clock algorithm and variants
  • non-LRU replacement
    • handling scanning and readahead
    • fairness and page replacement
  • device files
Fri 22 Mar
Quiz 08 (post-quiz for week 10) released, due 2019-03-26 12:15
xv6 paging+protection checkpoint due at 11:59pm
Week 11
Tue 26 Mar

I/O 1 / Filesystems 1

 [  |
screencapture (webm; browser) | audio only
 ]
Anderson&Dahlin: 13.3 (FAT), 13.4, 12.1
Arpaci-Dusseau: 36, 37, [missing FAT], 40
Silberchartz: 12.4-6, 10.2, 10.4
  • device drivers and interrupts
    • “top” and “bottom” halves
    • device interface
    • devices as magic memory
    • aside on I/O space
    • direct memory access
  • disk interface: sectors
  • FAT: linked lists on disk (start)
Quiz 08 (post-quiz for week 10) due 12:15 (released 2019-03-22)
Thu 28 Mar

Filesystems 2

 [  |
screencapture (webm; browser) | audio only
 ]
Anderson&Dahlin: 12.1, 12.2, 13.3 (FFS), 13.5
Arpaci-Dusseau: 41
Silberchartz: 12.4-6
  • FAT: linked lists on disk (con’t)
  • hard disks
  • SSDs
  • the inode concept
  • double- and triply-indirect blocks
Fri 29 Mar
Quiz 09 (post-quiz for week 11) released, due 2019-04-02 12:15
xv6 paging+protection due at 11:59pm
FAT reading released
Week 12
Tue 02 Apr

Filesystems 3

 [  |
screencapture (webm; browser) | audio only
 ]
Anderson&Dahlin: 13.3 (NTFS), 13.5, 14.1-2
Arpaci-Dusseau: 38, 42, 47
Silberchartz: 12.4-12.7, 10.7
  • sparse files
  • hard links and symbolic links
  • locality: block groups
  • extents
  • trees on disk
  • RAID (start)
Quiz 09 (post-quiz for week 11) due 12:15 (released 2019-03-29)
Thu 04 Apr

Filesystems 4

 [  |
screencapture (webm; browser) | audio only
 ]
Anderson&Dahlin: 14.1, 13.3(copy-on-write FSs)
Arpaci-Dusseau: 42, 48
Silberchartz: 12.7, 17.1, 17.3-5
  • RAID (finish)
  • ordering writes carefully
  • fsck, etc.
  • write-ahead logging and journaling filesystems
  • snapshots
Fri 05 Apr
Quiz 10 (post-quiz for week 12) released, due 2019-04-10 23:59
FAT reading checkpoint due at 11:59pm
Week 13
Tue 09 Apr

Sockets / Distributed Systems 1

 [  |
screencapture (webm; browser) | audio only
 ]
Anderson&Dahlin: [missing]
Arpaci-Dusseau: 48
Silberchartz: 17.6?
Thu 11 Apr

Distributed Systems 2: RPC / Network filesystems (start)

 [  |
screencapture (webm; browser) | audio only
 ]
Anderson&Dahlin:
Arpaci-Dusseau: 49-50
Silberchartz:
Fri 12 Apr
Quiz 11 (post-quiz for week 13) released, due 2019-04-16 12:15
FAT reading due at 11:59pm
FTP server released
Week 14
Tue 16 Apr

Distributed Systems 3: Network filesystems (finish) / Failure

 [  |
screencapture (webm; browser) | audio only
 ]
  • caching in network filesystems
    • open-to-close consistency
    • callbacks
    • (if time) disconnected operation
  • fail-stop
  • two-phase commit
  • briefly: distributed consensus
  • (if time) maybe start access control?
Quiz 11 (post-quiz for week 13) due 12:15 (released 2019-04-12)
Thu 18 Apr

Access Control

 [  |
screencapture (webm; browser) | audio only
 ]
  • access control lists
  • user IDs on Unix
  • /bin/login
  • set-user-ID
  • capabilities
Fri 19 Apr
Quiz 12 (post-quiz for week 14) released, due 2019-04-23 12:15
FTP server due at 11:59pm
Week 15
Tue 23 Apr

Virtual Machines 1

 [ 
slides (preliminary)
 ]
Anderson&Dahlin: 10.2
Arpaci-Dusseau: B
Silberchartz:
  • sandboxing
  • trap and emulate
  • reflecting exceptions
  • software support for virtualized virtual memory
Quiz 12 (post-quiz for week 14) due 12:15 (released 2019-04-19)
Thu 25 Apr

Virtual Machines 2

  • hardware virtual machine support
  • (if time) alternate OS designs (microkernels, hypervisor as OS, etc.)
Week 16
Tue 30 Apr

Final Exam Review

Quiz 13 (post-quiz for week 15) due 12:15 (released 2019-04-26)
Week 17
Thu 09 May

Final Exam (section 002)

9AM.

Fri 10 May

Final Exam (section 001)

2PM.