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

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

Multiprogramming and Dual-Mode Operation

 [  ]
Anderson&Dahlin: 2.1-6
Arpaci-Dusseau: 3.2, 4.1, 4.3-5, 6.2-3
Silberchartz: ???

Sorry, no screencapture. I added some diagrams to the posted slides to try to partially compensate.

  • System calls in xv6 (continued)
  • Other exception handling
  • Context switches generally
  • Context switches in xv6
  • Interrupt disabling
Fri 31 Aug
xv6 introduction released
Week 2
Tue 04 Sep

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
  • Process control blocks
  • POSIX versus Unix
  • Process creation and management: fork(), exec*(), wait()
  • Shells, generally
Thu 06 Sep

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 07 Sep
Quiz 01 (post-quiz for week 2) released, due 2018-09-11 09:15
xv6 introduction due at 11:59pm
shell released
Week 3
Tue 11 Sep

Scheduling 1

 [  |
screencapture (webm; browser) | audio only
 ]
Anderson&Dahlin: 7.1, 7.5
Arpaci-Dusseau: 7.2-9
Silberchartz: 3.2, 6.2-3
  • 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
  • scheduling metrics: fairness, response time, throughput
  • FCFS, RR
  • priority scheduling
Quiz 01 (post-quiz for week 2) due 09:15 (released 2018-09-07)
Thu 13 Sep

Scheduling 2

 [  |
screencapture (webm; browser) | audio only
 ]
Anderson&Dahlin: 7.1,
Arpaci-Dusseau: 8, 9, 25,
Silberchartz: 6.7
  • SJF, SRTF
  • approximating SJF: multi-level feedback scheduling
  • proportional share scheduling
    • lottery scheduling
Fri 14 Sep
Quiz 02 (post-quiz for week 3) released, due 2018-09-18 09:15
shell due at 11:59pm
Week 4
Tue 18 Sep

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
  • Linux’s Completely Fair Scheduler
  • (if time) real-time scheduling
  • pthreads API — pthread_create, pthread_join
Quiz 02 (post-quiz for week 3) due 09:15 (released 2018-09-14)
lottery scheduler released
Thu 20 Sep

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
  • 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
  • load/store reordering
Fri 21 Sep
Quiz 03 (post-quiz for week 4) released, due 2018-09-25 09:15
Week 5
Tue 25 Sep

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
  • load/store reordering, finished
  • 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 (appears on life HW)
Quiz 03 (post-quiz for week 4) due 09:15 (released 2018-09-21)
Thu 27 Sep

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 28 Sep
Quiz 04 (post-quiz for week 5) released, due 2018-10-02 09:15
lottery scheduler due at 11:59pm
life released
Week 6
Tue 02 Oct

Synchronization 4: Monitors continued / Reader+Writer Locks / Deadlock

 [  |
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
  • reader/writers problem (con’t)
  • POSIX rwlocks
Quiz 04 (post-quiz for week 5) due 09:15 (released 2018-09-28)
Thu 04 Oct

Synchronization 5

 [  |
screencapture (webm; browser) | audio only
 ]
Anderson&Dahlin: 4.9, 6.3, 8.2-3
Arpaci-Dusseau: 33
Silberchartz: 4.5
  • deadlock
    • definition: resources and conditions
    • examples
  • deadlock prevention
  • deadlock detection and resource acquisition graphs
Fri 05 Oct
Quiz 05 (post-quiz for week 6) released, due 2018-10-10 23:59
life checkpoint due at 11:59pm
Week 7
Tue 09 Oct

Reading Day

(no class)
Thu 11 Oct

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
  • xv6 paging
  • system calls and memory protection
  • page table tricks
    • allocate on demand
    • copy-on-write
Fri 12 Oct
Quiz 06 (post-quiz for week 7) released, due 2018-10-16 09:15
life due at 11:59pm
Week 8
Tue 16 Oct

Midterm Review

 [ 
screencapture (webm; browser) | audio only
 ]
Quiz 06 (post-quiz for week 7) due 09:15 (released 2018-10-12)
Thu 18 Oct

Midterm

Fri 19 Oct
Week 9
Tue 23 Oct

Virtual Memory 2: mmap, page cache

 [  |
screencapture (webm; browser) | audio only
 ]
Anderson&Dahlin: 9.6, 9.5
Arpaci-Dusseau: 21-22.4
Silberchartz: 9.7, 9.2, 9.4-6
  • memory mapped files
    • POSIX mmap
    • /proc/$$/maps
  • demand paging
  • the page cache
  • Linux process memory map data structures
  • dirty bits and simulating them
xv6 paging+protection released
Thu 25 Oct

Virtual Memory 3: Page Replacement

 [  |
screencapture (webm; browser) | audio only
 ]
Anderson&Dahlin: 9.5
Arpaci-Dusseau: 22.5-22.12
Silberchartz: 9.6, 9.9-10
  • page replacement algorithms
    • ideal: Belady’s MIN
    • ideal possible: LRU
  • working set and Zipf models
  • accessed bits
  • page replacement algorithms (better)
    • clock algorithm and variants
Fri 26 Oct
Quiz 07 (post-quiz for week 9) released, due 2018-10-30 09:15
Week 10
Tue 30 Oct

Virtual 4 / I/O

 [  |
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
  • non-LRU replacement
    • handling scanning — readahead
    • fairness and page replacement
  • device drivers and interrupts
    • “top” and “bottom” halves
    • device interface
    • devices as magic memory
Quiz 07 (post-quiz for week 9) due 09:15 (released 2018-10-26)
Thu 01 Nov

I/O 2 / 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
  • devices and device drivers continued
    • aside on I/O space
    • direct memory access
  • disk interface: sectors
  • FAT: linked lists on disk
  • hard disks (start)
Fri 02 Nov
Quiz 08 (post-quiz for week 10) released, due 2018-11-06 09:15
xv6 paging+protection due at 11:59pm
FAT reading released
Week 11
Tue 06 Nov

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
  • hard disks (finish)
  • SSDs
  • the inode concept
  • double- and triply-indirect blocks
  • hard links and symbolic links
  • locality: block groups
Quiz 08 (post-quiz for week 10) due 09:15 (released 2018-11-02)
Thu 08 Nov

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
  • extents
  • trees on disk
  • RAID
  • ordering writes carefully
  • fsck, etc.
Fri 09 Nov
Quiz 09 (post-quiz for week 11) released, due 2018-11-15 09:15
Week 12
Mon 12 Nov
FAT reading checkpoint due at 11:59pm
Tue 13 Nov

Filesystems 4 / Distributed Systems 0

 [  |
screencapture (webm; browser) | audio only
 ]
Anderson&Dahlin: 14.1, 13.3(copy-on-write FSs), [missing]
Arpaci-Dusseau: 42, 48
Silberchartz: 12.7, 17.1, 17.3-5
  • snapshots
  • write-ahead logging and journaling filesystems
  • (if time) log-structured filesystems
  • reasons for distribution, briefly
Thu 15 Nov

Sockets / Distributed Systems 1

 [  |
screencapture (webm; browser) | audio only
 ]
Anderson&Dahlin: [missing]
Arpaci-Dusseau: 48
Silberchartz: 17.6?
Quiz 09 (post-quiz for week 11) due 09:15 (released 2018-11-09)
Fri 16 Nov
Quiz 10 (post-quiz for week 12) released, due 2018-11-20 09:15
FTP server released
Week 13
Mon 19 Nov
FAT reading due at 11:59pm
Tue 20 Nov

Distributed Systems 2: RPC / Network filesystems

 [  |
screencapture (webm; browser) | audio only
 ]
Anderson&Dahlin:
Arpaci-Dusseau: 49-50
Silberchartz:
  • FTP extremely briefly
  • remote procedure calls
  • network filesystems
  • stateful versus stateless
  • caching
Quiz 10 (post-quiz for week 12) due 09:15 (released 2018-11-16)
Thu 22 Nov
(no class)
Fri 23 Nov
Week 14
Tue 27 Nov

Distributed Systems 3: Failure

 [  |
screencapture (webm; browser) | audio only
 ]
  • fail-stop
  • two-phase commit
  • briefly: distributed consensus
Thu 29 Nov

Access Control

 [  |
screencapture (webm; browser) | audio only
 ]
  • access control lists
  • user IDs on Unix
  • /bin/login
  • set-user-ID
  • capabilities
Fri 30 Nov
Quiz 11 (post-quiz for week 14) released, due 2018-12-04 09:15
Week 15
Tue 04 Dec

Virtual Machines

 [  |
screencapture (webm; browser) | audio only
 ]
Anderson&Dahlin: 10.2
Arpaci-Dusseau: B
Silberchartz:
  • trap and emulate
  • reflecting exceptions
  • software support for virtualized virtual memory
  • (if time) alternate OS designs (microkernels, hypervisor as OS, etc.)
Quiz 11 (post-quiz for week 14) due 09:15 (released 2018-11-30)
Thu 06 Dec

Final Exam Review

 [ 
screencapture (webm; browser) | audio only
 ]
Fri 07 Dec
FTP server due at 11:59pm
Week 16
Mon 10 Dec

Final Exam