News and Announcements for CSC421 Operating systems.

Dec 11:

Final (Monday) — 11:00–1:30

Dec 4:

Final Notes: Review of error correcting codes

Dec 5:

Midnight — no projects accpted after midnight

Nov 17:

Midterm makeup in class. Student must contact me before that Friday.

Nov 2:

Midterm Grades

Oct 20:

Midterm

Sep 1:

Zoom link for Fridays's class Zoom!

Aug 30:

Zoom link for wednesday's class.

TA's hours are announced (see Syllabus)

Aug 28:

Zoom link for monday's class

Aug 23:

Class cancelled.

Aug 21:

Zoom link for monday's class

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

The academic calendar

Class begins.

Syllabus for CSC421 Computer Operating Systems.

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, and
• to understand the trade-offs between mechanisms given available technologies and human demands.

In addition, the student will gain experience working with "real code", that is, the code of the linux operating system kernel, as well as developer tools for working with code in a collaborative environment.

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

• 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)
  • Operating Systems: The Tiny Textbook, Burton Rosenberg,

• Suggested reading:
  • The Cathedral and the Bazaar, by Eric Raymond.
  • Mythical Man-Month, possibly the most influential software engineering/operating systems book ever.
  • 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, 20% quiz and presentations, 20% each midterm and final, 40% projects.

• Who will help you:
  • Our TA is Satyarth Arora, sxa1654@miami.edu; Tuesday 3:30–6:00 and Thursday 4.00–5.30 PM.

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

Class notes for CSC421 Computer Operating Systems.

Part 1: Introduction and Requirements

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

Part 2: Data Representation & Architecture

• Crash course in CPU architecture
• Architecture notes
• Bytes and Registers
• Stack frames
• System traps
• the context switch

Part 3: Processes and Concurrency

• 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
• Concurrency
  • Introduction
  • Concurrency in practice
    • Presented in Java
    • Presented in Go
    • Presented in Posix C
  • Concurrency Calculus, a reasoning methodology.
    • Definitions: synchronous, concurrent, timeline, safety, liveness, fairness
    • Mutex is pthreads
    • test and set, spin locking
    • Peterson's algorithm
  • Condition Variables
  • Mesa v. Hoare Monitors
    • 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
  • Semaphores and Monitors
• Scheduling
  • 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:
  • the CEL theory: Concurrency, Efficiency, and Latency .
  • Interrupts and exceptions
  • APC/DPC, (Windows)
  • SoftIRQ's, Tasklets, Work queues (Linux)
  • System class (Solaris)
  • Soft interrupts (FreeBSD)
  • Work loops (OS X)
• Canes OS
  • Process and Thread life cycle in the CanesOS operating system.
  • Scheduling in the CanesOS operating system.
  • Semaphores in the CanesOS operating system.
• References:
  • 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)

Part 4: Memory and Execution Support

• 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.
    • shared, copy on write (COW), position independent code (PIC).
  • Advanced Topics
    • Swap space, swap cache (illustration from Bovet and Cesati)
    • Swap slot management (kernel.org)
    • Page frame management
    • Page cache
    • Virtual Address Descriptors
    • shared memory and copy on write (COW)
• 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
• References: VM
  • 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)
• References: Core Services
  • 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

Part 5: Persistence and Datastores

• Disk technology
  • Block devices
  • partitions
  • RAID
    • RAID 1: Mirroring
    • RAID 5: (n-1) of n Parity
    • The failure of the disk failure model: welcome RAID 6
    • NetApp Dual parity
  • snapshots
  • Journaling
  • LVM
• Classical File Systems
  • General Observations and Comments (on wayback)
  • The 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
• 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
    • SOSP 2007
• 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

Part 6: Software Engineering, Security and Exploits

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

Quizzes for CSC421 Computer Operating Systems.

Projects for CSC421 Operating Systems.

Please read:

⇒ Project Requirements

• Project 1: Bytes and registers
  Due: Wednesday September 6.
• Project 2: BCD Integer Project. Accept the assignment by the github classroom link, posted in slack.
  Due: Wednesday September 13. Friday, September 15.
• Project 3: Pirate Programming. See the project homepage.
  Due: Friday, September 29.
• Project 4: Snail-gate. See the project homepage.
  Due: Friday, October 13.
• Project 5: Reduced FAT Filesystem. Part 1. See the project homepage.
  Due: Friday, November 17.
• Project 6: Reduced FAT Filesystem. Part 2. See the project homepage.
  Due: Monday, December 4.

References for CSC421 Computer Operating Systems.

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

• Class Recordings

  wednesday, aug 30

  recording

  monday, aug 28

  recording

• 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
• Schedulers
  • The O(1) scheduler
  • the stair step scheduler
  • CFS: the completely fair scheduler
  • BFS: the brain friendly scheduler
• 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
• 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.
• 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.