office hours: T 3-4pm, R 11am-noon, or by appointment (LWSN 1211)
James (Jim) Lembke
office hours: W 11am-1pm (YONG 557, 765-494-6149)
office hours: M 9:30-11:30am (LWSN B132, #12; 765-496-9444)
office hours: F 2:30-4:30pm (HAAS 254, #2; 765-494-0361)
PSOs (HAAS 257):
M 3:30-5:20pm (Rajas)
T 9:30-11:20am (Bo)
W 1:30-3:20pm (Jim)
F 11:30-1:20pm (Bo)
Operating System Design – The Xinu Approach, Douglas Comer, latest edition
- lab5 and final exam scores have been posted. Please follow the same protocol as before. The course grade is available through Purdue's web system.
- lab4 has been graded. Please follow the same protocol as before to access scores and address any questions.
- Final exam and QCE: 05/04/2015 (Mon.), 8-10am, WANG 2599; closed note/book
- lab3 has been graded. Please follow the same protocol as before to access scores and address any questions.
- The midterm has been graded. Please use the same method as lab scores to access mid.rpt as indicated in the TA notes. A copy of the midterm and solution. The solutions are expanded for clarity. Your answers can be more compact while receiving full credit.
- lab2 has been graded. To access the points received, please check the TA notes for instructions. If there are any questions, please send email to all three TAs and they will assist you.
Midterm: 03/12/2015 (Thu.), in-class, closed note/book
Sample exams: fall 13 | fall 12 | spring 12
- As discussed in class, please make sure to replace XINU's linear time ready list in lab2-b with the constant time multi-level feedback queue.
- lab1/hw1 has been graded. To access the points received, please check the TA notes for instructions. If there are any questions, please send email to all three TAs and they will assist you.
- Please note office hour/PSO changes by Bo and Rajas starting the week of Feb. 16, 2015.
- On-line students: To interact with the TAs during PSOs and office hours, please send email or call and they will provide you with further contact information (e.g., Skype).
- The midterm is scheduled on March 12 (Thu), 2015; in-class, closed note/book. Sample exams will be posted a couple of weeks prior to the exam.
- No PSO on Jan. 20 (Tue), 2015.
- 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 further TA assistance is provided.
- Go to the XINU lab (HAAS 257) and login to one of the frontend machines xinu01.cs.purdue.edu, xinu02.cs.purdue.edu, ..., xinu21.cs.purdue.edu which are Linux PCs. Your accounts should have already been set up. If you cannot login, please contact email@example.com.
- On-line students: Please use secure shell to remotely access one of the frontend machines and verify that your account has been set up.
Please follow instructions given in class for accessing lecture slides (pdf).The topics listed below include material not covered in the pdf lecture slides. They should be referenced from class notes and additional pdf slides.
- Isolation/protection: motivation, hardware support features, x86 specific implementation, how Linux and XINU neutralize x86 segmentation-based addressing, overhead of system calls, meaning of XINU system calls
- Full virtualization: architecture, relation to isolation/protection, overhead issues; sensitive instructions in x86 and resultant complications, solutions (binary translation, paravirtualization, hardware assisted virtualization)
- Time-share (TS) process scheduling: fairness, CPU- versus I/O-intensive process classification
- Multi-level feedback queue and constant scheduling overhead
- Solaris UNIX Dispatch Table Example: TS [dispadmin -c TS -g]
- Fair scheduling, implementation issues, logarithmic complexity of the Linux completely fair scheduler (CFS)
- Real-time scheduling: motivation, periodic multimedia apps with hard deadlines
- RMS and EDF: admission control, scheduling algorithm, optimality, performance trade-off, system overhead and implementation issues
- Compressed video trace of Terminator movie (pdf), variable CPU requirements that is dependent on compressed frame size; important role of copy cost as part of system overhead
- Multithreading support: user space, kernel support, hardware support; technical issues and pros/cons
- Deadlock detection, prevention, overhead, Ostrich approach adopted by kernels and its rationale
- Relationship between IPC and device I/O, synchronous blocking/nonblocking system call semantics, asynchronous IPC (or I/O) with callback function and isolation/protection
- Zero-copy I/O: motivation, design, and overhead reduction
- Fragmentation in basic memory management, difficulties associated with mitigating external fragmentation
- Rationale for memory management unit (MMU) hardware support: external fragmentation, simple programming abstraction, hierarchical memory, memory protection for isolation/protection
- Design of modern memory management support: CPU (including multicores), L1 cache, translation lookaside buffer (TLB), L2 cache, RAM, disk and flash RAM (solid state memories)
- Locality of reference, caching, address translation, average- v. worst-case performance
- Boundary between virtual and physical memory referencing, interface between hardware and kernel (page fault interrupt and, in some architectures, TLB miss interrupts)
- Motivation for multi-level page tables and memory savings (few elephants | many mice), 2-level page table in x86 kernels
- Relationship between optimal, LRU, and global clock page replacement
- Thrashing: cause, performance impact, and control mechanisms
- Linux VM performance (pdf)
- Kernel architecture: upper half and lower half, shared kernel buffer and input/output synchronization
- Lower half architecture: top half and bottom half division, motivation and design
- Bottom half architecture: passive vs. active (kernel thread) implementation, trade-offs
- Implementation in Linux, Solaris, and Windows
- Kernel, interrupt and DMA controller coordination
- Video streaming over USB 2.0, FireWire 400 (IEEE 1394a) isochronous mode with DMA hardware support
- FireWire-DMA DV I/O for streaming video example: Linux | Windows I | Windows II
- Types of clocks (system timer, battery powered time-of-day clock, high-resolution counter) and their function, x86 specific hardware clocks
- Event queues and chores performed by clock interrupt handlers
- Delta list event queues and clock interrupt handling overhead, timeliness/accuracy of event queue processing, challenges to providing real-time guarantees
- Tickful kernels: small v. large tick trade-off, pros/cons of tickless kernel design
- Real-world file size distribution (cf. G. Irlam's UNIX file system data), "90/10 rule" or "mice and elephants", implication on file system design/performance
- Journaling file system: fault-tolerance, checkpointing for faster 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. [The two papers are for reference in case you are interested in learning more about log-structured FS.]
- 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/SSD file systems: technology features, pros (random access, persistent, non-mechanical, power consumption), and cons (block device, high write cost, limited number of writes)
- Popular SSD file systems: traditional FS + wear leveling (flash translation layer)
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.
The grade will be determined by a midterm, final, and lab assignments. Their relative weights are:
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.
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. The lab is comprised of frontend machines xinu01.cs.purdue.edu, xinu02.cs.purdue.edu, ..., xinu21.cs.purdue.edu which are Linux PCs. You will use the frontend machines for operating system code development (coding and compiling/linking) and to access one of the backend machines galileo101.cs.purdue.edu, galileo102.cs.purdue.edu, ..., galileo196.cs.purdue.edu. The fronend machines can be remotely accessed via secure shell. They can be used by multiple users concurrently to develop and test code. The backend machines are x86-compatible Intel Galileo boards equipped with Quark X1000 processors that are dedicated to running your implementation of XINU. Thus you are loading/running your own OS binary developed on the frontends on dedicated backend hardware. The specifics of developing and testing code in the XINU Lab will be covered in lab1.
Getting your CS account
Students registered in the course should have an account automatically set up. Please check by going to HAAS 257 and logging in to one of the frontend machines (Linux PCs). If you have registered but don't have an account, please contact firstname.lastname@example.org.
To help manage unexpected scheduling demands, you are given a budget of 3 late days in total that may be used for late submissions of lab assignments. For example, you may submit 1 day late on three lab assignments, or 3 days late on one lab assignment. Any combination is valid as long as the total days delayed does not exceed 3. There will be a total of 5-6 lab assignments. Late days not utilized at the end of the semester will be converted to 30 bonus point each (maximum of 90).Due to the low-level systems nature of the lab assignments, coding and evaluating parts of an operating system running on hardware is time intensive. To encourage proactive handling of assignments, all submissions turned in 2 days prior to its deadline will be given a 10% bonus credit (as a fraction of the points received).
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.
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.
Emergency preparedness procedures: pdf
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 dedicated x86-compatible hardware. A by-product of programming hardware-dependent kernel features in assembly is achieving significant familiarity with x86 hardware, a popular 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.