Sorry, no recordings due to technical difficulties. Last semester’s first lecture is similar.

• 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 (review)
• Other exception handling
• Context switches generally
• Context switches in xv6 (start)

• Context switches in xv6 (finish)
• Process control blocks
• POSIX versus Unix
• Process creation and management: fork(), exec*(), wait()

Due to a technical issue, the last 20 minutes of audio are missing from the recording. Similar material was covered in the last 5 minutes of last semester’s 24 January lecture and the first section of last semester’s 29 January lecture (up to the slide 11), for which full audio/video is available.

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

(add deadline)

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

Some example solutions for the monitor exercise I got to at the very end of lecture (but didn’t really finish explaining) are at the end of the slides.

• barriers
• monitors
  • producer/consumer with monitors
• intuition for using monitors
• monitor exercises (just started)

• monitor exercises (continued)
• counting semaphores
  • producer/consumer with counting semaphores
• 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 (start)

(drop deadline)

• xv6 paging (con’t)
• page table tricks
  • allocate on demand
  • copy-on-write
• (if time) demand paging
• (if time) the page cache, high-level

• notes

(withdraw deadline)

• memory mapped files, POSIX mmap
  • /proc/$$/maps
• demand paging
• the page cache
• Linux process memory map data structures
• page replacement algorithms (ideal)
  • ideal: Belady’s MIN
  • ideal possible: LRU
• working set model
• accessed bits and simulating them
• dirty bits and simulating them

• accessed bits
• page replacement algorithms (possible)
  • second chance
  • SEQ
  • clock algorithm and variants
• non-LRU replacement
  • handling scanning and readahead
  • (if time) fairness and page replacement
• start device files

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

• the inode concept (con’t)
• double- and triply-indirect blocks
• sparse files
• hard links and symbolic links
• locality: block groups
• extents
• trees on disk

• ordering writes carefully
• fsck, etc.
• write-ahead logging and journaling filesystems
• mirroring
• snapshots

• mounting filesystems
• 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

• remote procedure calls
• fail-stop
• two-phase commit (start)

• two-phase commit
• two-phase assignment
• very briefly: distributed consensus
• network filesystems
• stateful versus stateless
• caching in network filesystems
  • open-to-close consistency
  • callbacks

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

• trap and emulate
• reflecting exceptions
• software support for virtualized virtual memory
• (if time) hardware virtualization support

notes drawing

9AM.