• Logistics
• What is an operating system
• Dual-mode operation; protection; exceptions
• process VMs
• Process = thread + address space
• xv6 generally (12:30pm)

• xv6 generally (3:30pm)
• 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(), exec(), wait()

(add deadline)

• Shells, generally, and the shell assignment
• Unix: everything is a file, stdio, stdout
• POSIX file API: open(), dup2(), close()
• POSIX file API: read(), write()
• POSIX API: pipe()
• pipes and pipelines (start)

• pipe and pipelines (finish)

• partial read()s and write()s

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

• scheduling metrics: fairness, response time, throughput (finish)
• FCFS, RR
• priority scheduling
• proportional share scheduling
  • lottery scheduling (start)

• lottery scheduling (finish)
• SJF, SRTF
• approximating SRTF: multi-level feedback scheduling
• (briefly) Linux’s Completely Fair Scheduler (start)

• (briefly) Linux’s Completely Fair Scheduler (finish)

• 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
• locks with interrupt disabling
• cache coherency and false sharing
• atomic operations and spinlocks

• avoiding busy waits: mutexes
• producer/consumer idea
• monitors
  • producer/consumer with monitors
• intuition for using monitors

(drop deadline)

• monitor exercises
• counting semaphores
• producer/consumer with counting semaphores

• reader/writers problem
  • reader or writer priority
• deadlock
  • definition: resources and conditions
  • examples
• deadlock prevention through ordering

• review(?) of virtual memory
• xv6 paging

• xv6 paging (finish)
  • walkpgdir, mappages

(withdraw deadline)

due to technical difficulties the 12:30pm screen capture may not reflect what was shown to the class. (I recommend using the 3:30pm one)

• xv6 paging misc
  • what if page fault
  • setting page table base register
• 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)
  • ideal: Belady’s MIN

• page replacement algorithms (possible)
  • LRU
  • second chance
• non-LRU-friendly patterns

• virtual memory: being proactive / 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
• (briefly) extents
• write-ahead logging and journaling filesystems (start)

• write-ahead logging and journaling filesystems (finish)

• reasons for distribution
• (briefly) sockets (high-level POSIX API)
• DNS, IP addresses, port numbers, connections

• remote procedure calls (start)

• supplemental references:
  • Wikipedia’s Berkeley Sockets article
  • echo-server example, echo-client example

• remote procedure calls (finish)
• network failures and acknowledgments
• fail-stop model
• distributed transactions

• how naive distributed transactions don’t work
• two-phase commit
• two-phase commit examples

• two-phase commit (finish)
• two-phase assignment

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

notes: 12:30pm 3:30pm

Via quiz system.

Released 7pm 11 May.

Due 5pm 13 May.

24 hour time limit (from when you open the exam; time expires earlier if you open the exam less than 24 from the due time).