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 14 Jan

What are OSes? / Logistics

 [  |
screencapture (browser: 12:30pm 3:30pm;download: 12:30pm 3:30pm)| audio only: 12:30pm 3:30pm
 ]
Anderson&Dahlin: 1.1-2
Arpaci-Dusseau: 2, 3
Silberchartz: 1, 2.1-5, 3.1
  • Logistics
  • 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)
Thu 16 Jan

Exceptions / Context Switching

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

The Unix API 1

 [  |
screencapture (browser: 12:30pm 3:30pm;download: 12:30pm 3:30pm)| audio only: 12:30pm 3:30pm
 ]
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()
Quiz 01 (post-quiz for week 1) due 12:15 (released 2020-01-16)
Thu 23 Jan

The Unix API 2

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

The Unix API 3 / Scheduling 1

 [  |
screencapture (browser: 12:30pm 3:30pm;download: 12:30pm 3:30pm)| audio only: 12:30pm 3:30pm
 ]
Anderson&Dahlin: 7.1, 7.5
Arpaci-Dusseau: 7.2-9
Silberchartz: 3.2, 6.2-3

(add deadline)

  • 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 2020-01-23)
Thu 30 Jan

Scheduling 2

 [  |
screencapture (browser: 12:30pm 3:30pm;download: 12:30pm 3:30pm)| audio only: 12:30pm 3:30pm
 ]
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 (start)
Quiz 03 (post-quiz for week 3) released, due 2020-02-04 12:15
Fri 31 Jan
shell checkpoint due at 11:59pm
Week 4
Tue 04 Feb

Scheduling 3

 [  |
screencapture (browser: 12:30pm 3:30pm;download: 12:30pm 3:30pm)| audio only: 12:30pm 3:30pm
 ]
Anderson&Dahlin: 7.4, 4.1-4, 5.1
Arpaci-Dusseau: 26.-26.5, 27.1-2
Silberchartz: 5.1-4
  • approximating SJF: multi-level feedback scheduling (finish)
  • proportional share scheduling
    • lottery scheduling
  • Linux’s Completely Fair Scheduler
  • (if time) real-time scheduling
Quiz 03 (post-quiz for week 3) due 12:15 (released 2020-01-30)
Thu 06 Feb

Threads / Synchronization 1: Locks 1

 [  |
screencapture (browser: 12:30pm 3:30pm;download: 12:30pm 3:30pm)| audio only: 12:30pm 3:30pm
 ]
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 (start)
Quiz 04 (post-quiz for week 4) released, due 2020-02-11 12:15
Fri 07 Feb
shell due at 11:59pm
lottery scheduler released
Week 5
Tue 11 Feb

Synchronization 2: Locks 2, Mutexes

 [  |
screencapture (browser: 12:30pm 3:30pm;download: 12:30pm 3:30pm)| audio only: 12:30pm 3:30pm
 ]
Anderson&Dahlin: 5.3-4, 5.8
Arpaci-Dusseau: 30, 31
Silberchartz: 5.5-8
  • locks (con’t)
  • aside: standard container rules
  • disabling interrupts for locks, continued
  • load/store reordering
  • cache coherency, MSI and snooping
  • spinlocks
  • atomic operations: test-and-set, CAS
  • false sharing
Quiz 04 (post-quiz for week 4) due 12:15 (released 2020-02-06)
Thu 13 Feb

Synchronization 3: Monitors and Semaphores

 [  |
screencapture (browser: 12:30pm 3:30pm;download: 12:30pm 3:30pm)| audio only: 12:30pm 3:30pm
 ]
Anderson&Dahlin: 5.5, ?6.2
Arpaci-Dusseau: 29, 31.5
Silberchartz: 5.7-9
  • atomic operation example
  • barriers
  • avoiding busy waits: mutexes
  • monitors
    • producer/consumer with monitors
  • intuition for using monitors
Quiz 05 (post-quiz for week 5) released, due 2020-02-18 12:15
Fri 14 Feb
lottery scheduler due at 11:59pm
life released
Week 6
Tue 18 Feb

Synchronization 4: Semaphores and Monitors con't / Reader+Writer Locks

 [  |
screencapture (download: 12:30pm; browser: 12:30pm ) | audio only: 12:30pm | 3:30pm videos without audio: download browser )
 ]
Anderson&Dahlin: 6.2, 6.5
Arpaci-Dusseau: 32
Silberchartz: 7.1-6

Audio for the 3:30 PM lecture is not available, sorry.

  • monitor exercises
  • counting semaphores
    • producer/consumer with counting semaphores
  • relating monitors and counting semaphores
  • reader/writers problem
    • POSIX rwlocks
    • reader/writers with monitors
Quiz 05 (post-quiz for week 5) due 12:15 (released 2020-02-13)
Thu 20 Feb

Synchronization 5: Reader+Writer con't / Deadlock

 [  |
screencapture (browser: 12:30pm 3:30pm;download: 12:30pm 3:30pm)| audio only: 12:30pm 3:30pm
 ]
Anderson&Dahlin: 4.9, 6.3, 8.2-3
Arpaci-Dusseau: 33
Silberchartz: 4.5
  • reader/writers problem (con’t)
    • reader or writer priority
  • deadlock
    • definition: resources and conditions
    • examples
  • deadlock prevention
  • (briefly) deadlock detection
Quiz 06 (post-quiz for week 6) released, due 2020-02-25 12:15
Fri 21 Feb
life due at 11:59pm
pool released
Week 7
Mon 24 Feb

(drop deadline)

Tue 25 Feb

Virtual Memory 1

 [  |
screencapture (browser: 12:30pm 3:30pm;download: 12:30pm 3:30pm)| audio only: 12:30pm 3:30pm
 ]
Anderson&Dahlin: 8.2-3, 9.5-7
Arpaci-Dusseau: 13, 15, 18-22.4
Silberchartz: 8.1-2, 8.5-7, 9.2-6, 9.7
  • (briefly) event-based programming/message passing
  • review(?) of virtual memory
  • xv6 paging (start)
Quiz 06 (post-quiz for week 6) due 12:15 (released 2020-02-20)
Thu 27 Feb

Virtual Memory 2

 [  |
screencapture (browser: 12:30pm 3:30pm;download: 12:30pm 3:30pm)| audio only: 12:30pm 3:30pm
 ]
Anderson&Dahlin: 8.2-3, 9.5-7
Arpaci-Dusseau: 13, 15, 18-22.4
Silberchartz: 8.1-2, 8.5-7, 9.2-6, 9.7
  • xv6 paging (con’t)
  • page table tricks
    • allocate on demand
    • copy-on-write
Quiz 07 (post-quiz for week 7) released, due 2020-03-04 12:15
Fri 28 Feb
pool due at 11:59pm
Week 8
Tue 03 Mar

Midterm Review

 [ 
screencapture (browser: 12:30pm 3:30pm;download: 12:30pm 3:30pm)| audio only: 12:30pm 3:30pm
 ]

notes 12:30pm 3:30pm

Thu 05 Mar

Midterm

Fri 06 Mar
xv6 paging+protection released
Week 9
Tue 10 Mar

Spring Break

(no class)
Thu 12 Mar

Spring Break

(no class)
Week 10
Mon 16 Mar

(withdraw deadline)

Tue 17 Mar

Extended Spring Break / Online Class Prep

(no class)
Thu 19 Mar

Virtual Memory 3: mmap, page cache (intro)

 [  |
screencapture (browser: 12:30pm 3:30pm;download: 12:30pm webm mp4 3:30pm webm mp4)| audio only: 12:30pm 3:30pm
| 12:30pm Zoom recording| 3:30pm Zoom recording ]
Anderson&Dahlin: 9.5
Arpaci-Dusseau: 22.5-22.12
Silberchartz: 9.6, 9.9-10
  • memory mapped files, POSIX mmap
    • /proc/$$/maps
  • demand paging
  • the page cache
  • Linux process memory map data structures
  • page replacement
Quiz 08 (post-quiz for week 10) released, due 2020-03-24 12:15
Fri 20 Mar
Week 11
Mon 23 Mar
Tue 24 Mar

Virtual 4

 [ 
slides (preliminary)
 |
screencapture (browser: 12:30pm 3:30pm;download: 12:30pm webm mp4 3:30pm webm mp4)| audio only: 12:30pm 3:30pm
| 12:30pm Zoom recording| 3:30pm Zoom recording ]
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 (ideal)
    • ideal: Belady’s MIN
    • ideal possible: LRU
  • working set model
  • accessed bits and simulating them
  • dirty bits
  • page replacement algorithms (possible)
    • second chance
    • SEQ
Quiz 08 (post-quiz for week 10) due 12:15 (released 2020-03-19)
Wed 25 Mar
xv6 paging+protection checkpoint due at 11:59pm
Thu 26 Mar

Virtual 5 / I/O 1

 [  |
screencapture (browser: 12:30pm 3:30pm;download: 12:30pm webm mp4 3:30pm webm mp4)| audio only: 12:30pm 3:30pm
| 12:30pm Zoom recording| 3:30pm Zoom recording ]
Anderson&Dahlin: 13.2, 13.4
Arpaci-Dusseau: 36, [missing FAT], 40
Silberchartz: 12.4-6, 10.2, 10.4
  • non-LRU replacement
    • handling scanning, readahead
  • device files
  • device drivers and interrupts
    • “top” and “bottom” halves
    • device interface
    • devices as magic memory
    • aside on I/O space
Quiz 09 (post-quiz for week 11) released, due 2020-03-31 12:15
Fri 27 Mar
Week 12
Tue 31 Mar

I/O 2 / Filesystems 1

 [  |
screencapture (browser: 12:30pm 3:30pm;download: 12:30pm webm mp4 3:30pm webm mp4)| audio only: 12:30pm 3:30pm
| 12:30pm Zoom recording| 3:30pm Zoom recording ]
Anderson&Dahlin: 12.1-2, 13.3 (FAT, FFS), 13.4
Arpaci-Dusseau: 37, 44, 39-41
Silberchartz: 12.4-6
  • direct memory access
  • disk interface: sectors
  • FAT: linked lists on disk
Quiz 09 (post-quiz for week 11) due 12:15 (released 2020-03-26)
Wed 01 Apr
xv6 paging+protection due at 11:59pm
FAT reading released
Thu 02 Apr

Filesystems 2

 [  |
screencapture (browser: 12:30pm 3:30pm;download: 12:30pm webm mp4 3:30pm webm mp4)| audio only: 12:30pm 3:30pm
| 12:30pm Zoom recording| 3:30pm Zoom recording ]
Anderson&Dahlin: 13.3 (NTFS), 13.5, 14.1-2
Arpaci-Dusseau: 37, 41
Silberchartz: 12.4-12.7, 10.7

(12pm lecture videos are all from the Zoom recording due to difficulties with local recording.)

  • hard disks
  • SSDs
  • the inode concept
  • double- and triply-indirect blocks
Quiz 10 (post-quiz for week 12) released, due 2020-04-07 12:15
Fri 03 Apr
Week 13
Tue 07 Apr

Filesystems 4

 [  |
screencapture (browser: 12:30pm 3:30pm;download: 12:30pm webm mp4 3:30pm webm mp4)| audio only: 12:30pm 3:30pm
| 12:30pm Zoom recording| 3:30pm Zoom recording ]
Anderson&Dahlin: 14.1
Arpaci-Dusseau: 42, 47
Silberchartz: 12.7, 17.1, 17.3-5
  • locality: block groups
  • extents
  • write-ahead logging and journaling filesystems (start)
Quiz 10 (post-quiz for week 12) due 12:15 (released 2020-04-02)
Wed 08 Apr
Thu 09 Apr

Sockets / Distributed Systems 1

 [  |
screencapture (browser: 12:30pm 3:30pm;download: 12:30pm webm mp4 3:30pm webm mp4)| audio only: 12:30pm 3:30pm
| 12:30pm Zoom recording| 3:30pm Zoom recording ]
Anderson&Dahlin: [missing]
Arpaci-Dusseau: 48
Silberchartz: 17.6?
Quiz 11 (post-quiz for week 13) released, due 2020-04-14 12:15
Fri 10 Apr
FAT reading checkpoint due at 11:59pm
Week 14
Tue 14 Apr

Distributed Systems 2: RPC / Failure

 [  |
screencapture (browser: 12:30pm 3:30pm;download: 12:30pm webm mp4 3:30pm webm mp4)| audio only: 12:30pm 3:30pm
| 12:30pm Zoom recording| 3:30pm Zoom recording ]
  • sockets (finish)
  • remote procedure calls
  • fail-stop
  • distributed transactions
Quiz 11 (post-quiz for week 13) due 12:15 (released 2020-04-09)
Wed 15 Apr
Thu 16 Apr

Distributed Systems 3: Failure

 [  |
screencapture (browser: 12:30pm 3:30pm;download: 12:30pm webm mp4 3:30pm webm mp4)| audio only: 12:30pm 3:30pm
| 12:30pm Zoom recording| 3:30pm Zoom recording ]
Anderson&Dahlin:
Arpaci-Dusseau: 49-50
Silberchartz:
  • two-phase commit
  • two-phase assignment
  • very briefly: distributed consensus
Quiz 12 (post-quiz for week 14) released, due 2020-04-23 12:15
Fri 17 Apr
twophase released
Week 15
Mon 20 Apr
Tue 21 Apr

Distributed Systesm 4: NFS / Access Control 1

 [  |
screencapture (browser: 12:30pm 3:30pm;download: 12:30pm webm mp4 3:30pm webm mp4)| audio only: 12:30pm 3:30pm
| 12:30pm Zoom recording| 3:30pm Zoom recording ]
  • network filesystems
  • stateful versus stateless

  • access control lists
  • user IDs on Unix
  • /bin/login
  • set-user-ID
  • TOCTTOU
fatread due 21 April 2020; extended due to department machine issues
Wed 22 Apr
Thu 23 Apr

Virtual Machines

 [  |
screencapture (browser: 12:30pm 3:30pm;download: 12:30pm webm mp4 3:30pm webm mp4)| audio only: 12:30pm 3:30pm
| 12:30pm Zoom recording| 3:30pm Zoom recording ]
Anderson&Dahlin: 10.2
Arpaci-Dusseau: B
Silberchartz:
  • capabilities

  • trap and emulate
  • reflecting exceptions
  • software support for virtualized virtual memory
Quiz 13 (post-quiz for week 15) released, due 2020-04-28 12:15
Quiz 12 (post-quiz for week 14) due 12:15 (released 2020-04-16)
Fri 24 Apr
Week 16
Mon 27 Apr
twophase due at 11:59pm
Tue 28 Apr

Final Exam Review

 [ 
screencapture (browser: 12:30pm 3:30pm;download: 12:30pm webm mp4 3:30pm webm mp4)| audio only: 12:30pm 3:30pm
| 12:30pm Zoom recording| 3:30pm Zoom recording ]
Quiz 13 (post-quiz for week 15) due 12:15 (released 2020-04-23)
Week 17
Mon 04 May

Final Exam

Take home exam, tentatively released by 6PM 2020-05-04. Due 6PM 2020-05-05.