Course Information
MWF 11:30am-12:20pm
Beering Hall 1245
Instructor:
Kihong Park
email: park@cs.purdue.edu
phone: 494-7821
office hours: M 12:30am-1:30pm, W 10:30am-11:30am; LWSN 1211
Teaching Assistants:
Satish Kumar Eerpini
seerpini@purdue.edu,
496-9431 (LWSN B116E)
M 2:30pm-3:30pm, R 12pm-1pm
Wei-Chiu Chuang
chuangw@purdue.edu,
496-9444 (LWSN B132 #11)
T 1:30pm-3:30pm
PSOs:
M 3:30pm-5:20pm
F 1:30pm-3:20am (HAAS 257)
Textbook:
Operating System Design – The Xinu Approach, Linksys Version
Announcements
- Final exam and QCE: 05/01/2012 (Tue.), 1-3pm, BRNG B222, closed note/book
- Please check the TA notes for lab3 related info on paging API used in testing/evaluation.
- The group project description has been posted.
-
Midterm: 03/21/2012 (Wed.), in-class, closed note/book
Sample exams: fall 09 | spring 09 | spring 08 - Revised due date for lab2/hw2: 03/11/2012 (Sun.)
- Please check the TA notes link for instructions on accessing the lab/hw scores and TA feedback.
- The location of the MWF lecture classroom has changed from HAAS G066 to Beering Hall (BRNG) 1245.
- No PSOs in the first week of class. Although not required, it is strongly recommended that students attend the PSOs where lab assignments are discussed and TA assistance is provided.
Labs/Assignments
- lab0 | hw0
- lab1 | hw1
- lab2 | hw2
- lab3 | group project
- lab4 (Part 2 of VM lab)
- TA notes (last update: 04/24/2012)
- XINU setup (last update: 01/23/2012)
- Hardware and software documents
Lecture Notes
Please follow instructions given in class for accessing lecture slides (pdf).
The topics listed below which contain material not covered in the lecture slides should be referenced from class notes:- Evolution of computing hardware, their operating systems, and real-world requirements
- Isolation/protection: hardware support, kernel support
- Virtualization: full, para, and hardware assisted; x86-specific idiosyncrasies
- Process/thread models: user space, kernel space, hardware threads; their pros/cons
- General-purpose process scheduling: I/O- vs. CPU-bound process behavior, multilevel feedback queues, structure of Solaris scheduler (esp. TS), Linux process scheduling, fair scheduling
- Solaris Dispatch Table Example: TS [dispadmin -c TS -g]
- Real-time process scheduling: RMS, EDF -- motivation, algorithm, admission control, optimality, kernel implementation issues
- M. Harchol-Balter and A. Downey. "Exploiting process lifetime distributions for dynamic load balancing," in Proc. ACM SIGMETRICS '96, 1996.
- W. Leland and T. Ott. "Load-balancing heuristics and process behavior," in Proc. ACM SIGMETRICS '86, 1986.
- Process synchronization: deadlock detection, resolution, prevention, kernel implementation issues
- Windows IRP example (pdf)
- Synchronous/asynchronous I/O, blocking/nonblocking I/O: architecture of asynchronous nonblocking I/O with callback function, overlapped I/O, zero-copy I/O -- performance benefits
- Multi-processor/multi-core kernel design issues
- Memory fragmentation: internal, external, solutions/trade-offs
- Role of garbage collection in modern computing systems
- Logical/virtual vs. physical memory: motivation/benefits, hardware assisted address translation, multi-level caching (L1, TLB, L2, RAM, flash memory, disk), hardware/kernel boundary, tasks performed by kernel intervention
- Multi-level page tables, inverted page tables (frame-to-page bookkeeping, 64-bit architecture use with hashing), Belady's anomaly, relationship between optimal, LRU, and global clock page replacement, thrashing -- cause and impact
- Linux VM performance (pdf)
- Relationship between upper/lower half kernel synchronization and IPC synchronization
- Lower half architecture: top half and bottom half, passive/active (kernel thread) implementation of bottom half, pros/cons
- Bottom half design/implementation in Linux, Solaris, and Windows
- Kernel, interrupt and DMA controller coordination
- FireWire-DMA DV I/O: Linux | Windows I | Windows II
- Message queues: multiple writer/reader atomicity issue
- Types of clocks: functional classification, x86-specific hardware resources (RTC, PIT, local APIC, TSC, HPET) and their uses
- Tick configuration: accuracy vs. overhead, tickless kernel design and pros/cons
- Asymmetries in lower half kernel implementation: input vs. output, urgent I/O interrupt handling vs. software interrupt handling (incl. signal handlers/callback function invocation)
- Real-world file size distribution (cf. G. Irlam's UNIX file system data), 90/10 rule, implication on file system design/performance
- Journaling file system: reliability issue of write vs. read, checkpointing technique borrowed from DB for fast recovery
- Log-structured file system: motivation -- performance of write operations (many mice, few elephants) in disk file systems, append -- taking journaling to the extreme, performance benefits and drawbacks, segmentation and garbage collection to mitigate fragmentation
- M. Rosenblum and J. Ousterhout. "The design and implementation of a log-structured file system," in Proc. ACM SOSP '91, 1991.
- M. Jambor, T. Hruby, J. Taus, K. Krchak and V. Holub. "Implementation of a Linux log-structured file system with a garbage collector," in Proc. ACM SOSP '07, 2007.
- Flash memory and log-structured file system (LFS): NAND/NOR based technologies, wear leveling, write amplification, write gathering, tasks of flash translation layer, SSD (solid state drive) firmware, and relationship to LFS
Prerequisites:
Graduate standing in Computer Science, previous operating system class at the undergraduate level (CS 354 or equivalent), ability to read and understand a large non-trivial system written in C, ability to program extensively in C, and command of system development tools.
Grading Policy:
The grade will be determined by a midterm, final, lab assignments, and a group project toward the end of the semester. Their relative weights are:
| Midterm | 20% |
| Final | 20% |
| Lab assignments | 50% |
| Group project | 10% |
QCE:
For those planning to take the CS503 Qual 1 examination, the format is the regular final exam plus additional questions. Please contact the instructor for further information and details.
Labs and Policies:
We will use the XINU operating system for the lab assignments. The XINU lab is located in the HAAS Building Room 257.
Getting your CS account.
Students can get their CS account information on-line. Go to CS homepage, use the ITaP login and password in the upper right-hand corner. This will take you to a page where you agree to the access and usage policies, and then get your CS login and initial password. You also use the same site for doing mid-semester reviews, evaluations, etc. If you have signed up but don't have an account, please contact the accounts@cs.purdue.edu alias.
Late Policy
The due date of lab assignments is a hard deadline. No late submissions are accepted.
Academic Dishonesty
We wish to foster an open and collegial class environment. At the same time, we are vigorously opposed to academic dishonesty because it seriously detracts from the education of honest students. Because of this, we have the following standard policy on academic honesty, consistent with Purdue University's official policy.
It is permissible to discuss a general method of solution with other students, or to make use of reference materials in the library or online. If you do this, you will be expected to clearly disclose with whom you discussed the method of solution, or to cite the references used. Failure to do so will be considered cheating or plagiarism. The use of "method of solution" means a general discussion of technique or algorithm, such as one would reasonably expect to occur standing in front of a whiteboard, and precludes the detailed discussion of code. Specifically, looking at another student's code on his/her computer monitor is NOT allowed.
Unless otherwise explicitly specified, all code that is submitted is to be entirely each student’s own work. Using any code or copying any assignment from others is strictly prohibited without advance prior permission from the instructor. This includes the use of code others have submitted in the past.
All students work is their own. Students who do share their work with others are as responsible for academic dishonesty as the student receiving the material. Students are not to show work to other students, in the class or not. Students are responsible for the security of their work and should ensure that printed copies are not left in accessible places, and that file/directory permissions are set to be unreadable to others (e.g. use "chmod -R 700 *" from your home directory). If you need assistance protecting your work, please contact the TA or the instructor.
Students who encourage others to cheat or plagiarize, or students who are aware of plagiarism or cheating and do not report it are also participating in academically dishonest behavior.
Be aware that we will use a software tool called MOSS to check for copying among submitted assignments. Additionally, the instructor and TA will be inspecting all submitted material to ensure honesty.
Any case of academic dishonesty will be dealt with by a severe grade penalty in the overall class grade and referral to the office of the Dean of Students.
Campus Emergencies:
In the event of a major campus emergency, course requirements, deadlines, and grading percentages are subject to changes that may be necessitated by a revised semester calendar. If such unusual circumstances arise, students may determine any such changes by contacting their instructors via email or phone, and checking the course web page for updates.
Emergencies and campus closings will be announced on local media and on the main Purdue University WWW site http://www.purdue.edu. Individuals may subscribe to an SMS text announcement service. Other details are on the Purdue emergency preparedness site.
Course Content:
This is a graduate introductory course in operating systems that examines how modern operating systems are architected and implemented. Extensive implementation experience is gained by coding, testing, and benchmarking key components of the Xinu operating system on x86/Linksys hardware. A by-product of programming hardware-dependent kernel features in assembly is achieving significant familiarity with x86 hardware, a dominant platform of commodity computing systems.
The topics covered in the course include: evolution of operating systems and computer architectures, process management, memory manangement, virtual memory, file systems, I/O subsystems and device management, virtualization and security. In addition to implementing key kernel features in Xinu, we will examine case studies in Linux, UNIX (Solaris and BSD), and Windows that differ from Xinu and each other in significant ways. One important example is how I/O subsystems are architected to handle a range of heterogenous devices and their interrupts, including high-speed USB and wired/wireless network interfaces, that characterize many of today's computing systems. Kernel dependence on changing hardware features and support is an important theme throughout the course that will help familiarize with recent developments such as non-traditional file systems for flash RAM secondary memory prevalent in mobile systems.