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 / Deadlock

 [ 
slides (preliminary)
 ]
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

 [ 
slides (preliminary)
 ]
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

Virtual Memory 1

 [ 
slides (preliminary)
 ]
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
  • page table tricks
    • allocate on demand
    • copy-on-write
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
  • memory mapped files
    • POSIX mmap
    • /proc/$$/maps
  • demand paging
  • the page cache
  • Linux process memory map data structures
  • dirty bits and simulating them
Fri 01 Mar
Quiz 07 (post-quiz for week 7) released, due 2019-03-05 12:15
pool due at 11:59pm
Week 8
Mon 05 Mar

Midterm Review

Thu 07 Mar

Midterm

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

Virtual Memory 3: Page Replacement

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
Thu 21 Mar

Virtual 4 / I/O

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
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 2 / Filesystems 1

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)
Quiz 08 (post-quiz for week 10) due 12:15 (released 2019-03-22)
Thu 28 Mar

Filesystems 2

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

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.
Quiz 09 (post-quiz for week 11) due 12:15 (released 2019-03-29)
Thu 04 Apr

Filesystems 4 / Distributed Systems 0

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
Fri 05 Apr
Quiz 10 (post-quiz for week 12) released, due 2019-04-09 12:15
FAT reading checkpoint due at 11:59pm
Week 13
Tue 09 Apr

Sockets / Distributed Systems 1

Anderson&Dahlin: [missing]
Arpaci-Dusseau: 48
Silberchartz: 17.6?
Quiz 10 (post-quiz for week 12) due 12:15 (released 2019-04-05)
Thu 11 Apr

Distributed Systems 2: RPC / Network filesystems

Anderson&Dahlin:
Arpaci-Dusseau: 49-50
Silberchartz:
  • FTP extremely briefly
  • remote procedure calls
  • network filesystems
  • stateful versus stateless
  • caching
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: Failure

  • fail-stop
  • two-phase commit
  • briefly: distributed consensus
Quiz 11 (post-quiz for week 13) due 12:15 (released 2019-04-12)
Thu 18 Apr

Access Control

  • 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

Anderson&Dahlin: 10.2
Arpaci-Dusseau: B
Silberchartz:
  • 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)
Wed 25 Apr

Virtual Machines 2

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

Final Exam Review

Week 17
Thu 09 May

Final Exam (section 002)

9AM.

Fri 10 May

Final Exam (section 001)

2PM.