Operating Systems: Course Website

Course Information

Lecture:
MWF 11:30am-12:20pm
BHEE 117

Instructor:
Kihong Park
park0@purdue.edu
765-494-7821
Office hours: MW 1-2pm, or by appointment (HAAS 220)

Teaching Assistants:
Hyunchai Jeong
Office hours: M 2-3pm, F 11-noon (HAAS G50)
jeong3@purdue.edu
Paul Pok Hym Ng
Office hours: T 3-4pm (HAAS G50), R 3:20-4:20pm (HAAS G72)
ng121@purdue.edu

PSOs (HAAS 257):
M 3:30-5:20pm (Ng)
T 9:30-11:20am (Ng)
W 3:30-5:20pm (Jeong)
R 1:30-3:20pm (Jeong)

Textbook:
Operating System Design – The Xinu Approach, Douglas Comer, latest edition

Announcements

The final exam has been graded. To check your score (fin.rpt), please follow the same procedure as before. The text file, fin-stats.txt, in the course directory contains relevant stats. There is no regular follow-up. You may pick up your answer sheet in the third and fourth weeks of the next semester.
The fifth lab assignment, part II, has been graded. To check your score (lab6.rpt), please follow the same procedure as before. As noted in class, due to time constraints we will have an abbreviated follow-up that ends Dec. 11.
As noted in class, I will hold an additional office hour Dec. 9, 1-2pm.
The fifth lab assignment, part I, has been graded. To check your score (lab5.rpt), please follow the same procedure as before. You have one week to follow up after Thanksgiving break. For those who are utilizing late days, your work will be graded after the break.
The final exam is scheduled on Dec. 12, 2022, 8-9:15am, in WALC 2007; exam duration is 1 hour and 15 minutes (not 2 hours); closed note/book. Scope is comprehensive but focus will be on material covered after the midterm. Sample final and solution: exam | solution
Due to scheduling issues Hyunchai Jeong's office hours/PSOs will change as follows: additional office hours Nov. 14 3-4pm, Nov. 15 2-3pm, Nov. 22 2-3pm; cancel Nov. 30 PSO, Dec. 2 office hour.
The fourth lab assignment has been graded. To check your score (lab4.rpt), please follow the same procedure as before.
The fifth lab assignment, lab5, has been released. Please note the 2-phase implementation and submission.
The third lab assignment has been graded. To check your score (lab3.rpt), please follow the same procedure as before.
Please check the specification of 3.2 and Case (i) of 3.3 in lab4 which has been updated. The reason for the modification will be noted in class on Oct. 26.
The fourth lab assignment, lab4, has been released.
The midterm has been graded. Please follow the same procedure as the lab assignments to check your score (mid.rpt). The text file, mid-stats.txt, in the course directory contains relevant stats. You may pick up your exam during my office hours. Compare your answers against the solution key. If you have any questions, please come to my office hours. You have three weeks to follow up. Copy of midterm and solution: exam | solution.
The second lab assignment has been graded. To check your score (lab2.rpt), please follow the same procedure as lab1. Due to October break, you have until Oct. 14 to follow up.
The third lab assignment, lab3, has been released.
The midterm is scheduled on October 12, 2022; in-class, closed note/book. The scope covers material discussed in class and lab assignments. Sample midterm and solution: exam | solution
The first lab assignment has been graded. To check your score, please follow the instructions in scores.txt in the course directory. It will also contain instructions on how to follow up if you have questions.
The second lab assignment, lab2, has been released.
Paul Ng will hold his office hours on Sep. 8 (Thu.) via Zoom. Please use the link in zoom-link.txt located in the course directory.
The first lab assignment, lab1, has been released.
There are no PSOs and TA office hours 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

Lecture Notes

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.

Course overview.
Basic organization of kernels as reactive systems: system calls (upper half) and interrupts (lower half); scheduler situated in-between.
Steps of XINU boot loading and initialization on Galileo backends.
Isolation/protection: motivation, hardware and software support.
x86-specific features for supporting trapped system calls and interrupt handling using kernel mode/user mode switching.
Process management: process models.
XINU mechanics of scheduling and context-switching.
Isolation/protection and context-switching: transitioning to run new and old processes in user mode.
User stack, per-process kernel stack, and interrupt stack switching.
Time-share (TS) scheduling: framework, issues, implementation, overhead.
Constant enqueue/dequeue overhead of multilevel feedback queue.
Examples: UNIX Solaris, Windows NT, Linux O(1) scheduler.
Solaris UNIX Dispatch Table: TS
Heuristic scheduling and starvation prevention.
Weighted fair scheduling of TS processes: meaning of fairness under time-varying load, benefits and drawbacks, implementation in Linux CFS.
Real-time scheduling: motivation, multimedia streaming and periodic tasks with hard deadlines.
Compressed video example (pdf).
RMS and EDF: schedulability and admission control, scheduling algorithm, optimality.

Journal of the ACM

Note: Papers serve as auxiliary reference for those interested in learning additional details above and beyond what is discussed in class. They fall outside the regular scope of the course and do not need to be read.

Implementation issues: estimation of computation time, time-varying computation time, kernel design and overhead, timer accuracy.
Multiprocessor scheduling: load balancing (CPU and priority), process migration overhead, process lifetime.

Proc. ACM SIGMETRICS

Applications of process coordination/synchronization.
Mutual exclusion in uniprocessor and multiprocessor systems: hardware and software support, pros/cons.
Use of semaphores to implement preemptible upper half.
Asynchronous IPC with callback function, its implementation while preserving isolation/protection.
Deadlocks: detection overhead, prevention, Ostrich approach to kernel response.
Zero-copy I/O: reduced copy cost and system call overhead, Linux sendfile() example.
Motivation for virtual to physical address translation and memory management with hardware support: external fragmentation, virtualization of memory to facilitate simple programming model, memory protection.
Hierarchical memory: multi-level instruction/data caching, virtual vs. physical address referencing and VIPT, multi-level TLB and address translation; main memory, disk, and demand paging.
Page faults and TLB misses: boundary between kernel vs. hardware responsibility.
Memory footprint of real-world processes (mice | elephants) and multi-level page tables.
Example: 2-level paging structure in 32-bit x86 with 4 KB pages; 4-level paging in 64-bit x86 with 48-bit addressing.
Expansion of process context, content and TLB cache flushing, overhead of context-switching (lightweight/heavyweight process, multicore scheduling).
Page replacement: optimal, LRU, global clock, their relationship.
Memory thrashing: cause, symptoms and performance effect.
Example: Linux VM performance. (pdf)
Driver architecture: upper half and lower half, shared kernel buffer, and input/output synchronization.
Reuse of IPC synchronization primitives for device I/O: upper and lower half are executed by processes.
Example: Windows device I/O using IRP for video streaming. (pdf)
Refinement of lower half: top half and bottom half division.
Bottom half implementation: context borrowing vs. kernel thread implementation, trade-offs.
Essential role of DMA for high-speed I/O, its control by top half.
Example: video streaming using isochronous mode with DMA hardware support - Linux vs. Windows. (pdf)
Types of hardware clocks, their features, use in kernels: time of day clock, system timer, high resolution counter.
Example: x86 hardware clocks and their roles.
Maintaining timer events and overhead, clock synchronization and drift mitigation.
Tickful vs. tickless kernels, trade-offs.
Kernel abstraction of disk I/O: sectors, blocks, kernel-level indexing.
XINU FS, relationship to FAT file systems, linear indexing overhead, practical use in devices such as memory sticks.
File size distribution: mice and elephants (90/10 rule), influence on design and performance.
Log-structured file system: low hard disk throughput, operation and relationship to journaling, performance benefits and drawbacks.

Proc. ACM SOSP '07

SSD file systems: idiosyncracies of flash memory, wear leveling and flash translation layer, connection to LFS.
Operating system virtualization: full virtualization, trap and emulation, overhead.

Communications of the ACM

Example: x86 specific issues and dynamic binary translation.

Prerequisites

Graduate standing in Computer Science, previous operating system class at the undergraduate level (CS 354 or equivalent), ability to program at a low level in C, familiarity of system development tools.

Grading Policy

The grade will be determined by a midterm, final, and lab assignments. Their relative weights are:

Midterm	25%
Final	30%
Lab assignments	45%

Lab assignments will have opportunities to earn bonus points. These points serve to more easily reach the maximum achievable points in the lab assignment component. The points do not carry over and are capped at 45%. The same goes for the midterm and final exams which are capped at 25% and 30%, respectively. The course grade is not curved. Approximately, a total weighted score in the 90s maps to an A-range grade (includes +/- grades), mid-70s to 80s to B-range, low-70s and less to C-range and below.

Labs and Policies

XINU Lab

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 ScienceHelp@purdue.edu.

Late Policy

To help manage unexpected scheduling demands, you are given a budget of 4 late days in total that may be used for late submissions of lab assignments. For example, you may submit 1 day late on four lab assignments, or 4 days late on one lab assignment. Any combination is valid as long as the total days delayed does not exceed 4. There will be a total of 5-6 lab assignments. Late days not utilized at the end of the semester will be converted to 15 bonus point each (maximum of 60).

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 5% bonus points as a fraction of the points received.

Academic Integrity

We aim 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 integrity, consistent with Purdue University's official policy.

All CS503 assignments are individual efforts unless otherwise indicated, and collaboration is not allowed. This includes discussing solutions and sharing of code. Students who share their work with others are as responsible for academic dishonesty as the student benefiting from the material. You are responsible for securing your work. Students who are aware of cheating or plagiarism and do not report it are also participating in academically dishonest behavior. We will use a software tool, MOSS, to check for copying among submitted assignments. Additionally, we will inspect all submitted material to detect academic integrity violation.

If you have any assignment related questions, please utilize the PSOs and office hours. The main difference between getting help from the instructor and TAs versus a fellow student is that we will provide assistance to help you tackle a problem on your own without revealing the solution.

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.

Emergencies

In the event of an 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. In the event of a family emergency, please contact the instructor to set accommodations following university rules.

Campus emergencies and closings will be announced on local media and on the main Purdue University WWW site http://www.purdue.edu. Please consult the Purdue emergency preparedness resources web site for detailed information and relevant resources. Consult the Protect Purdue Plan for COVID-19 specific information.

In the event of health issues, please contact the Protect Purdue Health Center (PPHC) or your health care provider to receive support and medical attention. Reach out to your Academic Case Manager acmq@purdue.edu to receive additional assistance. In case of hospitalization and other urgency care, please contact the Office of the Dean of Students (ODOS) who will document and notify the instructor. Please check MEAPS for additional details.

Purdue University is committed to advancing the mental health and well-being of its students. If you or someone you know is feeling overwhelmed, depressed, and/or in need of mental health support, services are available. For help, contact Counseling and Psychological Services (CAPS) at 765-494-6995 during and after hours, on weekends and holidays, or by going to the CAPS office on the second floor of the Purdue University Student Health Center (PUSH) during business hours.

Nondiscrimination

Purdue University is committed to maintaining a community which recognizes and values the inherent worth and dignity of every person; fosters tolerance, sensitivity, understanding, and mutual respect among its members; and encourages each individual to strive to reach his or her potential. In pursuit of its goal of academic excellence, the University seeks to develop and nurture diversity. The University believes that diversity among its many members strengthens the institution, stimulates creativity, promotes the exchange of ideas, and enriches campus life. A hyperlink to Purdue's full Nondiscrimination Policy Statement is included in Brightspace under University Policies.

Accessibility

Purdue University is committed to making learning experiences accessible. If you anticipate or experience physical or academic barriers based on disability, you are welcome to let me know so that we can discuss options. You are also encouraged to contact the Disability Resource Center at: drc@purdue.edu or by phone: 765-494-1247.

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 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 dependence on hardware support, protection and virtualization, process management and real-time scheduling, memory manangement and paging, file systems, I/O subsystems and device management. 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.

CS503: Operating Systems (Fall 2022)