Computer Science 521 Homepage

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 in the context of 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.

Reading
- Required reading:
  - Linux Kernel Development (3rd Edition), by Love
  - C: A reference manual, by Harbison and Steele
  - Lions' Commentary on Unix by John Lions
  - The Little Book on Semaphores by Allen Downey
  - Operating Systems: the tiny textbook, Burton Rosenberg,
- Recommended reading:
  - 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
- Suggested reading:
  - How to be become a hacker, by Eric Raymond.
  - Operating System Concepts, Abraham and Silberschatz
  - The Design of the Unix Operating System by Maurice Bach
Work:
- Quizzes: Generally one per week. Out on Monday after class, due the next Wednesday by the end of class.
- Projects: A series projects, assigned from a Monday to the second following Monday. However, this might vary according to pace and vacation schedule.
- Project grading: Projects are generally scored on a 0 to 5 scale, with 5 being reserved for excellent projects. Grade depends on completeness, correctness, and presentation. Use of Subversion, Makefiles and file and folder names as requested are a must.
- Lateness: One week grace automatic on projects. Over one week late, one point off for each week late. No lateness for quizzes.
- Last day of class is Tuesday, December 10-th. All work to be done by that date.
- Class grading: After normalizations, 60% projects, 40% quizzes.
Computers:
- We will be working in various modes. I recommend strongly that you have your own computer to work on. We will install Virtual Box and work on virtual machines hosted by Virtual Box.
- If you do not have a computer of sufficient power to work comfortably with Virtual Box, please we will discuss options.
- We will make extensive use of subversion, a source code control system. You will turn in your assignments using subversion, and if you use subversion, I and the TA can help you by examining and correcting your code, at any time and from any location, when we are on-line.
New media:
- There is a CSC521 topic on my blog. It includes both my posts and as a sub-category the grader's posts.
- You follow twitter.com/cs521. I will keep it super-low traffic for the courtesy of those who want to enable SMS.
Contact:
- Office hours: We have to work this out. People often need help with C and Linux.
Writing credit:
- Writing credit is offered. The student submits three essays of length 1500 words each (not counting references section, if any) on a subject related to computer operating systems, technical, historical, or even market-business.
- New: Recommended:
  - Mythical Man-Month, possibly the most influential software engineering/operating systems book ever.
  - A second recommendation is E. Raymonds' Cathedral and Bizaar.
Grants/Sponsorship:
- Thanks to the Faculty Learning Community for grant to help develop course delivery.
- Thanks to Amazon: for a grant under their AWS for Education program, to explore cloud computing, and integrate cloud computing concepts into the course.

These class notes have been most supplanted by the tiny textbook that is on line. Additional gloss on classroom material.

Introduction
- What is an operating system? (blog entry)
- Demo: Subversion.
- Demo: Virtual box; Building the linux kernel.
Kernels
- What is a kernel? (blog entry)
  - Introduction to the Linux kernel (IBM developerworks reference)
  - Introduction to the Windows NT kernel (wikipedia)
  - Introduction to the XNU kernel
- Microkernels and hypervisors (IBM Developerworks reference)
- System traps and the kernel API
  - Trapping to kernel, basic memory layout, stacks.
  - Stacks and stack frames (notes)
  - More about stack frames (notes)
  - Syscalls, specifically Linux syscalls (notes)
  - x86 architecture calling conventions (unixwiz reference)
  - Linux system calls (IBM developerworks reference)
History
- Unix:
  - Unix history (Bell Labs web site)
  - Unix mini-course (mini-course notes)
  - Bell Systems Journal articles
  - Version 6 man pages
- Microsoft
  - DOS, Windows for Workgroups
  - Little windows
  - Windows NT/VMS
- OS X Amit Singh's What is OSX?
  - Xerox
  - Mach, Darwin and XNU
  - system services
Processes
- General remarks: (blog entry)
  - Multiprocessing and the context switch (blog entry)
  - The process life cycle (experiment)
  - Process context, kernel threads, kernel preemption and SMP
  - some code examples
- Scheduling (blog entry)
  - Interactive, batch, real-time.
  - Preemption, time-slice (quanta)
  - Priority (multi-level feedback)
  - The O(1) scheduler
  - the stair step scheduler
  - CFS: the completely fair scheduler
- Other dispatched entities:
  - Interrupts and exceptions
  - APC/DPC, (Windows)
  - Tasklets, Work queues (Linux)
  - System class (Solaris)
  - Soft interrupts (FreeBSD)
  - Work loops (OS X)
  - Priority inversion, priority boosting
- Synchronization
  - A morality tale
  - Class notes:
  - The little book of Semaphores by Allen Downey (PDF)
  - References:
    - 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)
- Signals, time and timers.
- Interprocess Communication
Memory
- Virtual memory system
  - Class notes on virtual memory
  - Blog entries on VM:
    1. Part 1;
    2. Part 2;
    3. Part 3;
    4. Part 4.
  - From the intel IA-32/e manual, volume 3.
  - Concepts:
    - Demand paging
    - Page replacement: MIN and LRU
    - Working sets
    - Swap space, swap cache (illustration from Bovet and Cesati)
    - Page frame management
    - Page cache
- Kernel memory management
  - Buddy System and contiguous page frames
  - Slab
- User memory management
  - Virtual Address Descriptors
  - sbrk, malloc and the heap
- Linking and loading
  - Linking and loading, Part 1 (blog entry)
  - Linking and loading, Part 2 (blog entry)
  - Linking and loading, Part 3 (blog entry)
- References
  - Linking and loading by John Levine
  - i386 paging details
  - Mel Gorman
  - Linux Memory Management
  - Itanium architecture, Eranian and Mosberger.
  - x86-64 architecture, Andi Kleen
  - Position independent code versus DLL's, and "well known DLL's", leading to DLL Hell
  - Elf and elf tools (man pages for nm, ar, objdump)
  - LP64 model is not harmful
  - 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)
  - Old class notes on linking and loading
File systems
- Blog posts:
- Disk technology
  - partitions
  - 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.
--- topics in green we did not get to
Graphical Systems
- X windows
- Window managers
- OSX and compositors
- MS windowing, VNC and RDP
- Android windowing systems
- fonts and colors
Cloud computing and virtual machines
Software engineering
- Open source and proprietary
- Release engineering
- Updates and security

Each week there is a pop-quiz. These are assigned at the end of Monday class and due by the end of Wednesday class. They are distributed and collected through the class subversion repository.

Pop quiz 1: Due: Wed 11 September, before end of class.
Copy [repo]/class/quiz/quiz1.txt to your quiz subdirectory and edit with your answers.
Pop quiz 2: Due: Wed 18 September, before end of class.
Copy [repo]/class/quiz/quiz2.txt to your quiz subdirectory and edit with your answers.
Pop quiz 3: Due: Wed 25 September, before end of class.
Copy [repo]/class/quiz/quiz3.txt and [repo]/class/quiz/quiz3_a.c to your quiz subdirectory and edit quiz3.txt with your answers.
Pop quiz 4: Due: Wed Oct 9 before end of class.
Copy [repo]/class/quiz/quiz4.txt to your quiz subdirectory and edit with your answers.
Pop quiz 5: Due: Wed Oct 16 before end of class.
Copy [repo]/class/quiz/quiz5.txt to your quiz subdirectory and edit with your answers.
Pop quiz 6: Due: Wed Nov 13 before end of class.
Copy [repo]/class/quiz/quiz6.txt to your quiz subdirectory and edit with your answers.
Pop quiz 7: Due: Wed Nov 20 before end of class.
Copy [repo]/class/quiz/quiz7.txt to your quiz subdirectory and edit with your answers.

The world renowned csc521 operating system projects.

Project 1: Due Monday, Sept 9.
- learn unix
- learn subversion
- install linux on virtual box and build its kernel
- To turn in: Put the output of the uname -a and uname -r commands in the file [your-repo]/proj1/uname.out. Don't forget to svn add, svn commit to upload the file.
  Hint: "uname -a > uname.out ; uname -r >> uname.out"
Project 2: Due Monday, Sept 23.
- Read the class notes about traps, stack frames and call gates. In particular Stack Memory notes.
- Read chapter 6 from the IA-32 Vol 1: Basic Concepts (for the intrepid!)
- See _repo_/class/proj2 for a sample program, Makefile, and the file test.out, desired output of the program when finished. Follow the directions.
- Submit your own annotated test.out as the file test.out-annotated, along with your finished program, make, etc. (The make file will have a make test traget that will recreate the test.out file.)
- Never submit binaries! Or other unnecessary, large data clods. Once in a repository they never go away (delete doesn't do it) and it slows down our backups. Thank you in advance from the management.
Read Love's book, chapters 1 through 5.
Project 3: Due Monday, October 7.
- Write the hellokernel system call that uses printk to write "hello kernel".
- Files to modify: [L]/kernel/sched.c and the callout table [L]/arch/x86/kernel/syscall_table_32.S. ([L] is /usr/src/linux-source-3.2.0 and so on)
- Use syscall number 35.
- Read "man syscall"
- Create a test file called hellokernel.c that uses syscall to test the syscall.
- Read "man getpid".
- Create the mygetpid system call that does what getpid does.
- Use next available sys_ni_syscall for the syscall number of mygetpid.
- To submit work, please provide diffs of all modified files in the kernel. Name them filename.diff (example: sched.c.diff) to show your edits. (Best to create a target in your Makefile called diff to create the diffs.)
- Submit a relevant clip from the /var/log/syslog file in file named syslog.test.
Read Love's book, chapters 6 through 11.
Project 4: Due Monday, October 28.
- Write a monitor. See project description
Read Love's book, chapters 12, 15 and 16.
Project 5: Due Wednesday, November 13.
- Create mymalloc and myfree.
- Use a linked-list of free memory segments, and thread the in-user segments with length and next pointers prepended to malloc'ed segment.
- Compile this as a library (.a); test it as a library.
- Compile this as a shared library (.so); test it as a shared library.
- How to prove it works: Use nm to check on symbols; use ldd to check on library dependences; to check that the coalesce works, you might need to write a special call that describes the free list.
Read Love's book, all remaining chapters.
Final Project: Due last day of class, no late point penalty until final date.
- Implement mini fat fuse
- the FAT specifications: FAT Functional Specs
- Fuse on sourceforge.
- IBM Article concerning FUSE. Warning: all documentation about FUSE is wrong.
- FUSE documentation from another source. Possibly no worse than any other source of misinformation.
- Harvey Mudd
- See class/proj7 for a sample fuse program

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

Inside the Mac OS X Chaos club
Linux Boot
Operating Systems (wikipedia)
Improvements from Linux 2.4 to 2.6, at IBM Developerworks.
LinuxChix: hacking for grrls (sic).
VBoxManage manual
GDB manual
Make manual
Historical Perspective
- General
- Platform death march by Daniel Eran
- In the Beginning ... by Neal Stephenson.
- Unix
- Unix history from Bell Labs website.
- The Unix-Haters Handbook
- The UNIX Time-sharing System, Dennis Ritchie and Ken Thomson (1974). (citeseer)
- Dennis Ritche's home page
- GNU and the Free Software movement
- The GNU Project by Richard Stallman
- Linux and GNU by Richard Stallman
- Stallman at NYU.
- Not Unix
- 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
- XNU kernel
Operating system design philosopies and software engineering
- The Unix Philosophy
- The Art of Unix Programming by Eric Raymond.
- Worse is better
- Mythical Man-Month
- Hints for Computer System Design, Butler Lampson (1983) (citeseer)
- Cathedral and Bizaar by Eric Raymond, on First Monday
- 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)
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 16, visually, clark@hushmail
- 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.
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

CSC521-E: Operating Systems

Prof. B. Rosenberg
Fall Semester, 2014 (141)
MWF 12:20–1:10 PM
Whitten Learning Center 160

Email: burt at cs miami edu

News Syllabus Textbook Notes Quizzes Projects Links

CSC521-E: Operating Systems

Prof. B. Rosenberg Fall Semester, 2014 (141) MWF 12:20–1:10 PM Whitten Learning Center 160 Email: burt at cs miami edu

News Syllabus Textbook Notes Quizzes Projects Links

Prof. B. Rosenberg
Fall Semester, 2014 (141)
MWF 12:20–1:10 PM
Whitten Learning Center 160

Email: burt at cs miami edu