• Logistics
• What is an operating system
• Dual-mode operation; protection; exceptions
• process VMs
• Process = thread + address space

• xv6 generally
• System calls in xv6
• Other exception handling
• Context switches generally

• Context switches in xv6
• Process control blocks
• POSIX versus Unix
  • reference: POSIX.1-2017
• Process creation and management: fork()

• Process creation and management: fork() [finish], exec(), wait()
• Shells, generally
• Shell assignment
• Unix: everything is a file, stdio, stdout
• POSIX file API: open(), dup2() [start]

(add deadline)

• POSIX file API: dup2() [finish], close(), read(), write()
• POSIX API: pipe()
• pipes and pipelines

• 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
• proportional share scheduling
  • lottery scheduling
• SJF

• SRTF
• approximating SRTF: multi-level feedback scheduling
• (briefly) Linux’s Completely Fair Scheduler

• 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
• barriers
• aside: standard container rules
• disabling interrupts for locks

• load/store reordering
• spinlocks
• atomic operations: test-and-set
• false sharing
• avoiding busy waits: mutexes
• producer/consumer idea
• (start) monitors

• monitors
  • producer/consumer with monitors
• intuition for using monitors
• monitor exercises
• counting semaphores

• producer/consumer with counting semaphores
• reader/writers problem
  • reader or writer priority
• deadlock (start)

• deadlock
  • definition: resources and conditions
  • examples
• deadlock prevention through ordering
• review(?) of virtual memory
• xv6 paging

• xv6 paging (con’t)

• xv6 paging (finish)
• page table tricks
  • allocate on demand
  • copy-on-write
• memory mapped files, POSIX mmap

• /proc/$$/maps
• demand paging
• the page cache
• page replacement
• page replacement algorithms (ideal) (start)
  • ideal: Belady’s MIN

• page replacement algorithms (ideal) (finish)
  • ideal possible: LRU
• accessed bits and simulating them
• dirty bits
• page replacement algorithms (possible)
  • second chance
  • (briefly) “CLOCK” algorithms
• (briefly) readahead

• 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
• the inode concept
• double- and triply-indirect blocks (start)

• double- and triply-indirect blocks (finish)
• (briefly) extents

• write-ahead logging and journaling filesystems

• reasons for distribution
• DNS, IP addresses, port numbers, connections
• supplemental references:
  • Wikipedia’s Berkeley Sockets article
  • echo-server example, echo-client example

• (briefly) sockets (high-level POSIX API)
• remote procedure calls
• fail-stop

• distributed transactions
• two-phase commit
• two-phase assignment

• two-phase commit examples

• two-phase commit assignment Q&A

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

• TOCTTOU

• capabilities

• trap and emulate

• notes