Monday Dec 9:

Final Exam is held 11:00–1:30.

Oct 29:

Reading set 3 and 4 announced.

Oct 27:

Project 5 announced.

Oct 9:

Wednesday, see class Slack for hurricane Milton news.

Oct 18:

Friday, Midterm

Sep 30:

Project 4 announced.

Sep 30:

Project 3 extended.

Sep 19:

Project 3 announced.

Sep 5:

Project 2 announced.

Aug 30:

Make sure you have joined the slack channel.

The project assignment invite is found in the channel,

and you connect to your TA's in the channel.

Aug 19:

Class begins.

TA Hours

Monday:

2:00 PM To 4:00 PM — Satyarth Arora

Tuesday:

5:00 PM To 8:00 PM — Oscar Arana

Thursday:

5:00 PM To 7:00 PM — Oscar Arana

Friday:

3:00 PM To 4:00 PM — Oscar Arana

Calendars

• Academic
• Finals

This is a course in computer operating systems. The goals of the course are,

• to present the most common mechanisms used by operating systems to implement useful behavior;
• these mechanisms include concurrency and data persistence;
• to understand the trade-offs between mechanisms given available technologies and human demands;
• C language coding, to understand computer architecture.

• Join the class slack channel csc-courses.slack.com, #csc421-251.

• Required reading:
  • The Little Book on Semaphores, by Allen Downey
  • C: A Reference Manual, by Harbison and Steele (referred to as H&S)
  • The Design of the Unix Operating System, by Maurice Bach
  • The C Programming Language by Kernighan and Ritchie. (Referred to as K&R)

• Suggested reading:
  • The Cathedral and the Bazaar, by Eric Raymond.
  • Mythical Man-Month, talking about the Waterfall.
  • Operating Systems: Principles and Practice, by Anderson and Dahlin.
  • The Design and Implementation of the FreeBSD Operating System, by McKusick and Neville-Neil
  • Windows Internals, by Russinovich, Solomon and Ionescu
  • Mac OS X Internals: A Systems Approach, by Amit Singh
  • Operating Systems: Three Easy Pieces, by Remzi H. Arpaci-Dusseau and Andrea C Arpaci-Dusseau.
  • Linux Kernel Development (3rd Edition), by Love
  • Operating System Concepts, Abraham and Silberschatz (also known as "The Dragon Book", because of the cover)
  • Lion's book. Source code for Sixth Edition Unix.

• What you will do:
  • Quizzes and presentations: There might be quizzes on particular topics, or students might present from readings or from their own code (code stand-ups).
  • Exams: a midterm and final.
  • Projects:
    1. A series projects, assigned from a Monday to the second following Monday. However, this might vary according to pace and vacation schedule.
    2. Project grading: Projects are generally scored on a 0 to 5 scale, with 5 being reserved for excellent projects. Short or longer projects have their total points adjusted.
    3. Project grades depend on completeness, correctness, and originality and sincerity of effort.
    4. Projects must make proper use of git, Makefiles, and proper folder and file names.

• Grading:
  • Lateness: Three days grace automatic on projects. Over that, one point off and an additional one point for each week late, up to some reserve number of points.
  • No lateness for quizzes or presentations.
  • No work accepted once reading days end.
  • Class grading: After normalizations, 30% each midterm and final, 40% projects.
  • If quizzes are assigned, they will be an announced percentage.

• Who will help you:
  • Our TA's are Satyarth Arora and Oscar Arana; contact them on slack.

• Honor Code:
  • Class participants read and accept the University Honor Code, available from the Dean of Students.
  • Work resulting from an integrity violation will not be graded. A no-grade arising in this way can be numerically distinct from a zero.

Part 1: Introduction and Requirements

• What is an operating system? (blog entry)
• What is Unix?
  • Unix Mini Course
  • Unix: Making Computers Easier to use (1982 Bell Labs)
• What is a kernel? (blog entry)
• Introduction to the Linux kernel (IBM developerworks reference)
  • Linux kernel and GNU operating system
  • Distro's
  • GNU Copy-left and open source
  • Linux kernel map
• Introduction to the Windows NT kernel (wikipedia)
  • WinObj
  • Process Explorer
  • Entire Sysinternals suite
• Introduction to the XNU kernel
  • Apple Mach/Darwin
  • OSX Book
  • OSX Internals by Amit Singh
• Microkernels and hypervisors

• Review of Architecture
  • The story of the Intel 4004 (movie)
  • Crash course in CPU architecture
  • Architecture notes
  • Bytes and Registers
• Syscalls and Context Switch
  • Stack frames
  • System traps
  • the context switch
  • ELF Sections New, for a look at BSS data.
• Virtual memory system
  • Concepts:
    1. The mongo introduction virtual memory
    2. Overview;
    3. Pages and page frames;
    4. Demand paging and eviction;
    5. Frame management and the swap cache.
  • Theory:
    • TLB and content addressable memory
    • Working sets and locality of reference (a principle)
    • Demand paging aand Page replacement: MIN and LRU (mechanisms)
    • Viewpoint: backing stores and the memory hierarchy.
    • copy on write (COW)
  • Advanced Topics
    • Swap space, swap cache (illustration from Bovet and Cesati)
    • Swap slot management (kernel.org)
    • Page frame management
    • Page cache
    • Virtual Address Descriptors
    • position independent code (PIC) and shared memory

• Tasks and Threads: Process Context and Execution
  • The process abstraction
  • The Process Life Cycle
  • Signals and simple interprocess communication
  • Pipes, unix piping.
  • Kernel context, kernel threads, user context in kernel threads
  • Copy on Write
• Scheduling
  • the CEL theory: Concurrency, Efficiency, and Latency
  • Overview and examples
    • Classes: e.g. interactive, batch, or real-time.
    • Preemption, time-slice (quanta)
    • Priority (multi-level feedback)
    • Priority inversion, priority boosting
  • Scheduling in Linux
    • The O(1) scheduler
    • the stair step scheduler
    • CFS: the completely fair scheduler
  • SMP and NUMA, processor affinity and migration
• Other dispatched entities:
  • Interrupts and exceptions
  • APC/DPC, (Windows)
  • SoftIRQ's, Tasklets, Work queues (Linux)
  • System class (Solaris)
  • Soft interrupts (FreeBSD)
  • Work loops (OS X)
• Concurrency
  • Introduction
  • Definitions: synchronous (or causal), concurrent, timeline, safety, liveness, fairness
    • concurrent: a ∥ b
    • mutual exclusion: a ∦ b
    • causal: a < b
  • Test and set, spin lock, poll, "give up"
  • PV Semaphores and friends
  • Semaphores and Monitors
    • Mesa v. Hoare Monitors
    • Condition Variables
    • Mesa Monitors are Java threads
    • Pthreads are almost Hoare Monitors except,
      • The signaling thread does not automatically vacate the lock
      • The signaled thread contends as if it were relocking
  • A Rendez-Vous with correctness argument.
  • Concurrency in practice
    • Presented in Java
    • Presented in Go
    • Presented in Posix C
  • Peterson's Alogrithm
  • Concurrency Calculus, a reasoning methodology.
  • Reader–Writer Locks

• Linking and loading
  • Purpose (blog entry)
  • Example (blog entry)
  • Dynamic linking–loading (blog entry)
• Memory management
  • Buddy System and contiguous page frames
  • Slab
  • sbrk, malloc and the heap

• Classical File Systems
  • General Observations and Comments (on wayback)
  • Digression: IMAP/Folders versus Gmail/Labels
  • VFS: review the
  • The Linux kernel map
  • FAT file system (Marc McDonald, Microsoft, 1978)
    • FAT32 Filesystem Specification, Microsoft
    • FAT Layout visual
  • The Unix filesystem (Ken Thompson, ATT, 1969)
    • The Unix file system
    • The Unix file system, part 2
    • The Unix file system extension
  • Windows file system: NTFS
    • Helen Custer, Inside the Windows NT File System
  • NFS: the network file system for Unix
    • Design and Implementation of the Sun Network Filesystem, Sandberg et at.
    • draft-leach-cifs-v1-spec-01.txt by Paul Leach. The standard before the Samba people reversed engineered it.
  • File locking and consistency
• Disk technology
  • Block devices
  • partitions
  • RAID
    • Patterson, Gibson and Katz, the original paper.
    • RAID at the Computer History Museum.
    • RAID 1, 5 and 6.
    • NetApp Dual parity
  • snapshots
  • Journaling
  • LVM
• Weaker consistency, stronger availability
  • Brewer's CAP theorem
  • Strong consistency: ACID
  • Case study in Strong consistency: Relational databases
  • Eventual consistency: Vogel's Blog Post
  • Case study in highly availabile eventually consistent: DNS
• Three Distributed Datastores
  • BitCask, LevelDB and Bigtable (blog)
  • Bitcask (pdf)
  • Bigtable:
    • OSSI 2006
    • Google App Engine.
  • Case study: Amazion Dynamo
    • Blog notes
    • Dynamo: Amazon's Highly Available Key-value Store, Vogels et. al., SOSP 2007.
    • Time, Clocks, and the Ordering of Events ..., Lamport
• Cloud computing
  • Above the Clouds: A Berkeley View of Cloud Computing.
  • Replication, Sharding
  • Distributed consistent hashing
  • Merkle trees and anti-entropy
  • Gossip
  • Resolution: quorum, last write, eventual consistency
  • Lamport event clocks
  • Vector clocks
  • Consenus: Paxos

• The Cathedral and the Bazaar
• Open source and proprietary
• Release engineering
• Updates and security
• Exploits
  • Stack: The classic text by Aleph One
  • Heap: Slapper virus (SSL buffer overrun causes free() to patch the GOT to run shellcode)

• Readings 1:
  • The Unix Time Sharing System by Ritche and Thompson.
  • The Design of the UNIX Operating System, by Bach chapters 1 and 2.
  • The Linux Kernel
• Readings 2: About processes.
  • In Bach:Chapters 6, 7 and 8.
• Readings 3: About files.
  • In Bach: Chapters 3, 4, 5, 10.
• Readings 4: Memory, IPC
  • In Bach: Chapters 9, 11.

#include<stdio.h>

int f(int i) { return 3+i ; }
int g(int i) { return i*i ; }
int h(int i) { return 5*i ; }
int z(int i) { return 0 ; }

int main(int argc, char * argv[]) {
        int i, j = 1; 
        int (*fcts[3])(int) = {z,z,z};
        for (i=0;i<3;i++) j = fcts[i](j) ;
        printf("%d\n",j) ;
        return 0 ;
}

Final Review

• Block devices
  • LBA: Logical Block Addresses
  • Disk partitions
  • RAID 1: Mirroring
  • RAID 5: Parity
  • LVM
  • Snapshots
  • Journaling
• VFS the virtual file system
  • stat
  • open, fileid
  • read and write
  • seeking
  • directory access and modification
  • permission system in unix
• FAT File system
  • FAT Table
  • Clusters
  • Directory Structure
• Unix File system
  • Inode and the Inode table
  • tree structure for clusters
  • bitmap for free clusters
  • mount points
  • block devices
  • character devices
  • directory data structure
  • link count
  • in-core inode reference count
• consistency
  • ACID and BASE
  • The CAP theorem
  • Eventual Consistency
  • DNS TTL, caching and replication
  • Read Your Writes consistency
• The LevelDB file system
  • Log structured key-value store
  • SST: sorted string tables
  • Tombstones
• dynamo
  • Distributed consistent hashing (DCH)
  • data sharding
  • data replication with DCH
  • adding and removing nodes in dynamo
  • Merkel trees
  • vector clocks
  • most recent write resolution
  • R and W confirmations
  • quorum systems (R+W>N)
• Cryptographic hashing
  • Polynomial time deterministic
  • Pre-image resistance
  • Collision resistance
• Coding
  • call out tables
  • memory mapped I/O

Midterm Histogram

• Midterm Histogram

Midterm Review

• Definition of an Operating system: variations
• Architecture and definition of the kernel
• Getting service from the kernel
• CPU Architecture: elements of the CPU
• Registers in a CPU
• interrupts
• stack use
• Purposes of Virtual memory
• Page tables and their use
• Demand Paged
• 32 bit two level page tables
• Sections in physical memory
• time share
• context switch
• process lifecycle
• round robin and priority scheduling
• Latency and efficiency
• priority classes
• starvation
• interactive and computation type tasks
• definition of concurrency
• definition of and need for thread safety
• the definitions of safe, live and fair
• the definition of deadlock
• spin locks
• PV Semaphores
• mutex and condition variables
• Monitors
• Petersons Algorithm
• Rendez-Vous
• C language programing
  • General syntax
  • structs
  • mallocs
  • pointers
  • casts
  • simple algorithms
• Make
  • targets
  • dependencies
  • recipes

• Project 0: The Preparations Project
  • Read the Project Requirements,
  • Learn AWS and how to start and EC2 instance.
  • SSH will be needed. See Brew for mac and WSL for windows.
  • Learn git and make a github account.
• Project 1: The RingBuffer Project
  Due: Friday, 6 September, 2024.
• Project 2: The Virtual Memory Project
  Due: Friday, 20 September, 2024.
• Project 3: The Unix Processes Exercise.
  Due: Friday, 4 October, 2024.
• Project 4: The SnailGate Project.
  Due: Wednesday, 16 October, 2024.
• Project 5: The Hello Fuse Project.
  Due: Monday, 4 November
• Project 6: The LevelDB Project.
  Due: Monday, 25 November

References of use in this course; some are referred to in the class notes.

• Unix
  • The Unix Time-sharing System, 1978 BSTJ update of the 1974 C. ACM article, Denis Ritchie and Ken Thompson (PDF)
  • The Evolution of the Unix Time-sharing System, by D. Ritchie (PDF)
  • The UNIX Time-sharing System, Dennis Ritchie and Ken Thomson, C. ACM 17 No. 7 (July 1974). (Brewer's annotated version) (see also archive.org for the BSTJ Vol 57 version.)
  • Ken Thompson, Unix Implementation, AT&T Bell Laboratories Technical Journal Vol. 57 No. 6, July-August 1978. (see also archive.org)
  • Dennis Ritchie, The Evolution of the Unix Time-Sharing System, (AT&T Bell Laboratories Technical Journal 63 No. 6 Part 2, October 1984) (see also A Retrospective)
  • The Bourne shell, by Bourne.
  • Unix history from Bell Labs website.
  • The Unix-Haters Handbook
  • The Unix Philosophy
  • Worse is better
• The Free Software movement
  • The GNU Project by Richard Stallman
  • Linux and GNU by Richard Stallman
  • Stallman at NYU.
  • Cathedral and Bizaar by Eric Raymond, on First Monday
• Windows and Apple
  • Twenty Years of Windows
  • History of Microsoft Windows
  • Windows NT and VMS: The Rest of the Story by Mark Russinovich
  • History of OSX by Amit Singh
  • OSX Internals by Amit Singh
  • XNU kernel
• Operating system design philosophies
  • Platform death march by Daniel Eran
  • In the Beginning ... by Neal Stephenson.
  • Mythical Man-Month
  • Hints for Computer System Design, Butler Lampson (1983) (citeseer)
  • outer space OS
• Chip architectures: CPU's and beyond
  • Intel IA-32 Manual Vol 1: Basic Concepts
  • ARM Architecture Reference Manual
• Scheduling and Concurency
  • The O(1) scheduler
  • the stair step scheduler
  • CFS: the completely fair scheduler
  • BFS: the brain friendly scheduler
  • notes to a new theory
  • notes on life cycles
  • The little book of Semaphores by Allen Downey (PDF)
  • Intel 64 and IA-32 Architectures Software Developer's Manual: (Cover page) XCHG operation
    • Vol 1
    • Vol 2a
  • Kai Li at Princeton (notes)
  • Concurrent sequential processes, by Tony Hoare. (PDF)
  • Experience with Processes and Monitors in Mesa, by Butler Lampson and David Redall (PDF)
  • Mutual Exclusion
  • From semaphores to locks
• Linking and loading
  • Position Independent Code, Wikipedia
  • The Hardworking Elf, Peter Seebach, IBM Developer Works.
  • Shared Objects, Ashish Bansal, IBM Developer Works.
  • Introduction to Mach-O Programming Topics from Apple Developer
  • How To Write Shared Libraries by Ulrich Drepper.
  • Dissecting shared libraries by Peter Seebach at IBM.
  • Computer Science from the Bottom Up, Ian Wienand, see chapters 8 and 9.
  • PE Files, Wikipedia
  • ELF Format, PDF file.
  • C Lang FAQ
  • C++ Frequently Questioned Answers
  • My explanation of stack frames
  • Someone else's explanation of stack frames
  • Linking and loading by John Levine
  • Position independent code versus DLL's, and "well known DLL's", leading to DLL Hell
  • Eli Bendersky's explanation
  • Elf and elf tools (man pages for nm, ar, objdump)
  • LP64 model is not harmful
  • Old class notes on linking and loading
• Virtual Memory
  • Porting Linux to x86064 by Andi Kleen
  • x86-64 Wikipedia
  • Page sizes on 32 and 64 Fedora distro's.
  • Understanding Virtual Memory at Red Hat.
  • Virtual Memory, WinNT
  • Linux MM Wiki
  • Rik van Riel interview at KernelTrap
  • Page table dump from one of my linux systems.
  • Physical Address Extension, another way to skin a cat.
  • From the intel IA-32/e manual, volume 3.
  • Figures 3-1: Segmentation and paging
  • Table 4-1: Properties of different paging modes
  • Figures 4-2 and 4-3: IA-32 paging modes
  • Figure 4-4: CR3, PDE's and PTE's for IA-32
  • Figures 4-5 and 4-6: IA-32 PAE paging modes
  • Figures 4-8, 4-9, and 4-10: IA-32e (64 bit) paging modes
  • Figures 5-1 and 5-2: segment descriptors
  • i386 paging details
  • Mel Gorman
  • Linux Memory Management
  • Itanium architecture, Eranian and Mosberger.
  • x86-64 architecture, Andi Kleen
  • Additional notes on virtual memory
  • Emery Berger of UMass Amherst, slides.
  • Chrobak and Noga, LRU is better than FIFO. (PDF)
  • Tarjan and Sleator, Amortized efficiency of list update and paging rules. (PDF)
  • Memory management for the ARM architecture (as in, Apple M1)
• File systems
  • EXT3, Journaling Filesystem by Dr. S. Tweedie
  • ext3 Journaling File Sytems (ppt) Chadd Williams
  • Linux NTFS
  • FAT Layout visual
  • Journaling the Linux ext2fs Filesystem, Stephen Tweedie
  • How NTFS Works Microsoft Technet.
  • Implementing CIFS by Christopher Hertel
  • CIFS by Paul Leach and Dan Perry at MSDN.
  • draft-leach-cifs-v1-spec-01.txt by Paul Leach. The standard before the Samba people reversed engineered it.
  • Op Locks in SMB from MSDN.
  • Common Internet File Systems Technical Reference from Storage Networking Industry Association.
  • Understanding NFS Michael Lucas at O'Reilly books.
  • 8.3 Filename, and LFN to SFN algorithm, and directory layout (as of 15 Oct 08) Wikipedia.
  • Design and Implementation of the Sun Network Filesystem, Sandberg et at.
  • Use of NFS Considered Harmful, Shane Kerr.
  • FreeBSD fs technologies: softupdates, snapshots, and comparision to logging.
  • Eventually consistent
  • Mongo DB
  • Proof of CAP by Lynch and Gilbert, 2002. (download from Gilbert's biblio page)
  • Disk failures in the real world by Bianc Schroeder and Garth A. Gibson.
  • Fail trends in a large disk drive population by Pinheiro, Web and Barroso.
  • Riak
• Protection
  • Windows NT Security by Mark Russinovich. Part 2
  • Access Control (Windows) at MSDN dot com.
  • ACL's (Linux), Andreas Grunbacher
  • Protection Butler Lampson.
  • Unix Protection Demystifing Suid Wagner, et al.
  • The Melissa Virus, and others
  • Stack smashing, see also Smashing The Stack For Fun And Profit, Aleph One.
  • PaX
  • ASLR, Address space layout randomization
  • Stack cookies and friends.
  • Non-execute bit
• Graphical systems
  • Pango
  • Sub pixel rendering, especially typefaces.
  • Sub pixel, more to look at.
• Cloud computing and virtual machines
  • Above the clouds, a report by Berkeley computer science department.
  • The clock and clock interrupts
  • software and hardware techniques
  • AMD MMD hacks
  • Intel MMD hacks
  • Eventually consistent
  • comments on E.C.
• Canes OS
  • Process and Thread life cycle in the CanesOS operating system.
  • Scheduling in the CanesOS operating system.
  • Semaphores in the CanesOS operating system.