• 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

• System calls in xv6 (continued)
• Other exception handling
• Context switches generally
• Context switches in xv6 (start)

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

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

• 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

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

• 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

• 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

• 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
• POSIX rwlocks

• reader/writers problem (con’t)
• deadlock
  • definition: resources and conditions
  • examples
• deadlock prevention
• deadlock detection and resource acquisition graphs

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

• notes

• 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

• page replacement algorithms (possible, con’t)
  • SEQ
  • clock algorithm and variants
• non-LRU replacement
  • handling scanning and readahead
  • fairness and page replacement
• device files

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

• FAT: linked lists on disk (con’t)
• hard disks
• SSDs
• the inode concept
• double- and triply-indirect blocks

• sparse files
• hard links and symbolic links
• locality: block groups
• extents
• trees on disk
• RAID (start)

• RAID (finish)
• ordering writes carefully
• fsck, etc.
• write-ahead logging and journaling filesystems
• snapshots

• reasons for distribution
• DNS, IP addresses, port numbers, connections
• sockets
  • getaddrinfo
  • POSIX API: socket, bind, listen, accept, connect
• supplemental references:
  • Wikipedia’s Berkeley Sockets article
  • echo-server example, echo-client example

• sockets con’t
  • Caution: Incomplete reads and writes
• remote procedure calls
• network filesystems
• stateful versus stateless
• supplemental sockets references:
  • Wikipedia’s Berkeley Sockets article
  • echo-server example, echo-client example

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

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

• sandboxing
• trap and emulate
• reflecting exceptions
• software support for virtualized virtual memory

• hardware virtual machine support
• alternate OS design case study: seL4

• notes

9AM.