Arduino Leonardo

News and Announcements for CSC421 Operating systems.

Friday, Oct 17:

Midterm.

Monday, Sep 22:

Project 3 released.

Monday, Sep 8:

Project 2 released.

Wednesday, Aug 27:

Project 1 released.

Tuesday, Aug 19:

CSC 421-E/ECE 421-E has been moved to Mahoney Pearson 116

Monday, Aug 18:

Class begins.

TA Hours

TBA:

Dewan Tauhid Rahman

Also by arrangement on Slack.

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

• 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 is Dewan Tauhid Rahman. Please arrange time either slack, zoom or in Ungar 310T.

• 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

• 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
  • FUSE
• 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: Processes and Concurrency

• Tasks and Threads: Process Context and Execution
  • Simple, Simon and Sage Chat about Processes
  • The process abstraction
  • The Process Life Cycle
  • Signals and simple interprocess communication
• Syscalls and Context Switch
  • Stack frames
  • Automatic (stack) variables are not initialized.
  • Suggested chat with ChatGPT prompt: "What is the difference between CISC and RISC architectures?"
  • System traps
  • the context switch
  • ELF Sections New, for a look at BSS data.
• Scheduling
  • Overview and examples
    • Classes: e.g. interactive, batch, or real-time.
    • Preemption, time-slice (quanta)
    • Priority (multi-level feedback)
    • Priority inversion, priority boosting
  • The CEL Theory: Concurrency, Efficiency, and Latency
  • 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
  • concurrent, causal or synchronous, mutual exclusion
  • safety, liveness, fairness
  • Thread-count.c, a concurrency experiment.
  • The spin lock: Test and set
  • PV Semaphores and monitors
    • Mesa v. Hoare Monitors
    • Condition Variables
  • Concurrency in practice
    • Nag.c: how to wait for events.
    • Java example
    • Accumulate in Java, Go and V
    • 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
    • References:
      • Presented in Java
      • Presented in Go
      • Presented in Posix C
  • Reasoning about concurrency
    • deadlock
    • Concurrency Calculus, a reasoning methodology.
    • A Rendez-Vous with correctness argument.
    • Peterson's Algorithm

This is last semesters's. Will be updated

Part 3: 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.
    • 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
• 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

Part 4: Persistence and Datastores

• 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

Part Ar: Computer Architecture

• Review of Architecture
  • The story of the Intel 4004 (movie)
  • Crash course in CPU architecture
  • Architecture notes
  • Bytes and Registers

Part Se: 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)

Readings for CSC421 Computer Operating Systems.

• Readings 1:
  • The Unix Time Sharing System by Ritche and Thompson.
  • The Design of the UNIX Operating System, by Bach chapters 1 and 2.
• Readings 2: About processes.
  • In Bach: Chapters 6, 7 and 8.

ChatGPT chats for understanding

Here are a list of prompts to discuss with ChatGPT. These are issues that came up in class that will enrich the discussion, but not enough in the curriculum to devote class time.

1. "What is the difference between CISC and RISC architectures?"
2. "In the context of concurrency, discuss the properties of: safety, liveness, fairness?""

Projects for CSC421 Operating Systems.

• Project 0: The Preparations Project
  1. Read the Project Requirements,
  2. Make a github account.
  3. Learn AWS concepts
  4. SSH will be needed. See Brew for mac and WSL for windows.
  5. Start and and configure your EC2 instance.
• Project 1: The RingBuffer Project
  Due: Friday, 5 September
• Explanation: Simple, Simon and Sage Chat about Make (the code)
• Project 2: The Signal Ping Pong Project
  Due: Friday, 19 September
• Project 3: The SnailGate Project.
  Due: Friday, 3 October

References for CSC421 Computer Operating Systems.

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.