• 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

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

• Process control blocks
• POSIX versus Unix
• Process creation and management: fork(), exec*(), wait()
• Shells, generally

• Unix: everything is a file, stdio, stdout
• stdio.h versus system calls
• POSIX file API: pipe(), open(), read(), write(), close()

• 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

• SJF, SRTF
• approximating SJF: multi-level feedback scheduling
• proportional share scheduling
  • lottery scheduling

• Linux’s Completely Fair Scheduler
• (if time) real-time scheduling
• 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
• load/store reordering

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

• barriers continued
• counting semaphores
  • producer/consumer with counting semaphores
• monitors
  • producer/consumer with monitors (start)

• 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

• deadlock
  • definition: resources and conditions
  • examples
• deadlock prevention
• deadlock detection and resource acquisition graphs

• (briefly) event-based programming/message passing
• xv6 paging
• system calls and memory protection
• page table tricks
  • allocate on demand
  • copy-on-write

• notes

• memory mapped files
  • POSIX mmap
  • /proc/$$/maps
• demand paging
• the page cache
• 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 (better)
  • clock algorithm and variants

• non-LRU replacement
  • handling scanning — readahead
  • fairness and page replacement
• device drivers and interrupts
  • “top” and “bottom” halves
  • device interface
  • devices as magic memory

• devices and device drivers continued
  • aside on I/O space
  • direct memory access
• disk interface: sectors
• FAT: linked lists on disk
• hard disks (start)

• hard disks (finish)
• SSDs
• the inode concept
• double- and triply-indirect blocks
• hard links and symbolic links
• locality: block groups

• extents
• trees on disk
• RAID
• ordering writes carefully
• fsck, etc.

• snapshots
• write-ahead logging and journaling filesystems
• (if time) log-structured filesystems
• reasons for distribution, briefly

• DNS, IP addresses, port numbers, connections
• sockets
  • getaddrinfo
  • POSIX API: socket, bind, listen, accept, connect
  • Caution: Incomplete reads and writes
• supplemental references:
  • Wikipedia’s Berkeley Sockets article
  • echo-server example, echo-client example

• FTP extremely briefly
• remote procedure calls
• network filesystems
• stateful versus stateless
• caching

• fail-stop
• two-phase commit
• briefly: distributed consensus

• access control lists
• user IDs on Unix
• /bin/login
• set-user-ID
• capabilities

• trap and emulate
• reflecting exceptions
• software support for virtualized virtual memory
• (if time) alternate OS designs (microkernels, hypervisor as OS, etc.)

• notes