Operating Systems Principles

Instructor: Mark Kampe

My background is not academic, but in Operating Systems development. I have spent over 40 years designing, building, and guiding operating systems, operating systems related projects, and system software development teams. Much of my work has focused on high performance and highly available multi-processor and distributed systems. I teach for fun, and to help develop the next generation of engineers. My goal in this course is to identify the most valuable concepts and techniques, and to make them interesting and clear.

Course Objectives

Operating Systems has been considered a core computer science course for a very long time. This is a new syllabus, developed by Paul Eggert, Mark Kampe, and Peter Reiher. While the list of covered topics is quite similar to most other Operating Systems courses, the detailed learning objectives have been updated to reflect the needs of a new generation of computer science students:

• provide all students with OS related concepts and exploitation skills that they (a) will all likely need and (b) are unlikely to get in other courses.
• provide Computer Science majors with an introduction to key concepts and principles that have emerged from (or been best articulated in) operating systems.
• provide all students with a conceptual foundation that will enable them to read well written introductory level OS-related papers, engage in intelligent discussions of those topics, and participate in entry-level OS-related projects.
• non-objectives ... things often taught in other OS courses:
• prepare students to write or work with kernel code. Very few of our students will ever have need to do this, and the pendulum now appears to be swinging away from kernel-mode implementations (even for file systems and other performance-critical data-paths).
• understanding of the issues and techniques associated with device drivers and low level platform support code in operating systems. This may be crucial background for hardware system designers and embedded software developers, but this course seeks to provide a more general introduction for a much broader audience.

The reading, lectures, projects, and exams are all designed around a large set of detailed learning objectives. In addition to giving students a detailed overview of the material to be covered in this course, this list is an excellent starting point for exam study.

Assumed Student Background

• abiliy to design, write, build, and debug C software
• familiarity with basic computer architecture (registers, memory, instruction pointer, processor status word) and instruction sets (load, store, test, branch, logical/arithmetic operations).
• familiarity with the stack model of program execution (parameter passing, saving/restoring registers, local variables, return values).
• familiarity with the software generation tool chain (compilers, assemblers, object modules, linkage editors, load modules).
• familiarity with the use of libraries.

Primary Text

This course introduces an extremely wide range of new concepts, and so involves a great deal of reading. Most of the readings for this course will come from Remzi Arpaci-Dusseau's Operating Systems in Three Easy Pieces. This text was selected, after evaluating numerous alternatives, for several reasons:

• a good introduction to an appropriate range of topics.
• a practical treatment with numerous code examples that students can run for themselves.
• highly readable.
• presentations are based on readily available (Linux) systems.
• numerous quantitative analyses of performance implications.
• excellent explorations of important performance issues in synchronization and file systems.
• avoidance of gratuitous formalisms, ancient history, and low-value tangents.
• it is an Open Source effort ... a movement for which many of us have tremendous respect. A very practical implication of this decision is that students are not required to purchase a text book.

The primary weaknesses of this text seem to be:

• focused on mechanisms than principles
• subjects and examples are limited to those found in the Linux kernel

Hence, there will be a few areas that must be covered from alternative readings (all available on-line):

• numerous monographs written specifically for this course
• numerous readings from chapter 2 (System Calls) of the Linux Programmers' Manual as detailed examples
• Wikipedia articles for general overviews of areas not covered by the other readings

Projects

Viewed in terms of problem domains, the projects are C programming problems in several key operating systems areas:

• processes and threads
• file I/O and Inter-Process Communication
• synchronization, and contention
• file systems
• Internet-of-Things (IOT) and embedded system security

But they also span a wide range of software development skills:

• developing software to specifications
• learning and mastering complex APIs
• performance analysis
• consistency analysis of complex data structures
• developing and debugging parallel, distributed, and embedded applications

The projects in this course will require you to have:

• Access to a Linux system on which you can build and test C programs. If you are taking this course, there is a better-than-even chance that you already have a Linux system, but if you don't there are several options:
  • Install Linux on your own laptop or desktop.
  • Install Linux in a virtual machine inside your own laptop or desktop.
  • Do your project work on CS department Linux servers.
  • Get a free (low powered) Linux virtual machine from Amazon Web Services.
  For most of the projects any Linux system will do, but ...
  • Project 2 (synchronization and contention) will require you to have access to a multi-core CPU (departmental servers will do).
  • Parts of Project 4 (Embedded System) will require you to be able to connect your embedded system directly (via USB) to another computer.
• An embedded development system, including:
  • an BeagleBone Green ... a small, low-power, system on a chip with numerous general purpose I/O pins
  • a Grove Starter Kit ... a collection of sensors, actuators, and display devices for embedded system hobby projects
  • a suitable micro-USB power supply for the embedded board
  All of these parts are widely avaiable and, ironically, they will cost you just about the same amount of money you would have otherwise spent on an Operating Systems text. But, if you are taking this course, the odds are that you will find many other uses for your embedded development system after this course is over.

Lecture, Reading, Lab and Exam Schedule

Lecture, Reading, Lab, and Exam Schedule

It is not my intention to use the lectures to review topics that are well presented in the reading. I hope to use the lecture time to:
• discuss student questions arising from the reading.
• expand on key results that should be drawn from reading.
• work through and discuss important but non-trivial examples from the reading.
• discuss perspectives, implications, and applications not covered by the reading.

You can help to enrich the quality of the lecture sessions by:

• using the on-line Piazza forum to suggest questions and topics to be discussed during the lecture sessions.
• asking questions during the lecture sessions.

To ensure that students have done the reading, and come to class prepared to engage in deeper exploration of the topics, an on-line quiz (based on the assigned reading) will be due before the start of each lecture. Nobody likes these quizzes, but experience has shown that (a) quizzes force students to do the reading before the lectures, and (b) students who have done the reading get more out of the lectures, and develop a better understanding of the material.

All lecture slides will be available on-line before the start of each lecture. This should simplify your own note-taking and give you a starting point for exam preparation. It will also give you the opportunity to see what topics I am planning to discuss in each lecture. If you find (after reading or a lecture) that there are additional topics you would like to discuss, please post them to the course discussion forum.

Office Hours

I am not regular faculty, and am only on campus on the days I teach this course. I will try to be in my office one hour before and after each class session. If those times do not work for you, it may be possible to schedule an appointment at some other time. When not on campus, I am generally on-line. The most reliable way to reach me is via email or google-talk Mark.Kampe@gmail.com.

Assignments and Grades

Grades in this course are based on:

• 10% daily quizzes on the assigned reading.

  These must be completed, on-line, prior to each lecture. Each quiz is a one digit number of short-answer questions. The purpose of the quizzes is to ensure that you have you have done the reading, and come to each lecture prepared for a more in-depth discussion of the topic.

• 50% lab projects

  The labs are programming exercises in which you will use the mechanisms and techniques that have been discussed in the reading and lecture. The dual purpose of the labs is to:

  1. consolidate your understanding of non-trivial concepts
  2. develop the ability to apply new techniques
  Breakdown of points among the individual projects:
  • 5% Project 0: warm-up exercise
  • 10% Project 1: I/O and signals
  • 10% Project 2: Synchronization
  • 10% Project 3: File Systems
  • 15% Project 4: Embedded System/Internet of Things


• 40% exams

  All the exams are closed-book, multi-question, with each part of each question requiring a brief (e.g. 1-3 sentence) answer. The purpose of the mid-term and part 1 of the final exam is to assess your familiarity with, and ability to apply the concepts, principles, and techniques listed in the course learning objectives. The purpose of (the more difficult) part 2 of the final exam is to assess your ability to apply these lessons to the understanding and solution of new and non-trivial problems.

  Breakdown of points among the exams:
  • 15% midterm (concepts)
  • 15% final exam - part 1 (concepts)
  • 10% final exam - part 2 (applications)

Students with good programming backgrounds generally do very well on the lab projects. Quiz scores tend to be well corellated with scores on the mid-term and part 1 of the final. Scores for part 2 of the final exam (problem solving vs. memory/understanding) tend to be distributed over a much wider range.

Letter Grading Scale:

• I do not grade on a curve, but a fixed scale. I am not trying to assign students to performance percentiles, but rather to assess their mastery of the course learning objectives.
• I do look carefully at the break points to try to ensure that students who did similar work do not get different grades, but the major break points generally fall within a point or two of 88/78/68/58.
• if I make a mistake in a problem that makes it significantly more difficult than intended, I will adjust the scale to compensate for my mistake

When classes had only 40-50 students, quiz questions were short-answer, I graded them personally, and returned them the next day. With classes of 120-160 students this is no longer possible, and I have been forced to move to automated moodle quizzes, administered on the CCLE website.

It is very difficult to do short-answer questions in moodle, as even minor variations in punctuation result in answers being scorred as incorrect. As a result, virtually all quiz questions are multiple-choice or matching. In order to keep these questions from being trivial, it is necessary to include options that sound reasonable, but are wrong in some detail. I (along with most students) dislike this format ... but despite these irritations, experience shows that quiz scores are well corellated with (and a little bit better than) exam scores. Most A-students seem to earn quiz scores in the 90s.



While I feel locked into the format, I am concerned about ensuring the fairness of questions and the relevance of the topics they cover. If you have suggestions for how to improve quiz questions, I am interested ... and you can earn (quiz) extra credit if I adopt your suggestions.

• there are no make-ups for quizzes, but you can take a quiz before it is due.
• each student has five slip-days that can be used for any lab due date (before the end of the quarter). After those have been used up, a grade is reduced by 10% for each 24 hours late the assignment is.
• if you are unable to make an exam, it may be possible (with prior notice) to arrange to take a (different) make-up exam at some later date.

• I will always correct any (promptly reported) error in score computation or recording. You are encouraged to check the on-line grade book regularly to ensure that all of your assignement grades have been properly recorded.
• I am always willing to explain the correct answers and exam grading criteria.
• I am always willing to regrade an exam problem if I misunderstood a clearly correct answer ... but this does not extend to
  • reinterpreting vague or poorly written answers
  • giving credit for not having properly or fully understood problem
• I will correct a quiz score if the auto-grader was unable to accept a correct answer.
• I never raise grades in response to excuses or hardship stories.
• I never assign makeup projects. The only opportunity to improve a grade is before the assignment is submitted.

If you believe that your answer was clearly correct and was simply mis-read or mis-graded, submit a re-grade request from within Gradescope.
If your answer did not agree with the posted solution or clear statements in the reading/lectures, but you believe it was more correct than reflected by the awarded points:

1. carefully review the posted solution, the relevant reading, and the relevant lecture notes.
2. write a brief (600 words or less) essay in which you:
   1. enumerate the respects in which your answer did not respond to the question, or failed to demonstrate the required insight into the problem.
   2. demonstrate why, despite these, Your answer included sufficiently clear and and key responses that it deserves more credit. You cannot receive credit for words you thought, but did not write.
   3. justify the additional credit you want by showing its proportionality to the fraction of the required insight that was captured by your submission.
3. submit your essay as part of a Gradescope regrade request.

• This is not timed, and you are able to research your position and consider your arguments; I will evaluate your arguments as a university level essay that clearly demonstrates your undertstanding of the subject and a compelling argument for the correctness of the answer you submitted.
• Do not bother explaining how you misunderstood the question (I was at the exam answering questions), or the correct answer that you meant to (but did not) write.
• If your (open-book, un-timed) essay demonstrates that (even after reviewing the reading, lecture notes, and posted solution) you still do not understand the question and its solution, your score may be further lowered.
• Attempts to defend incorrect answers are more likely to lose points than to gain them.

Permission to Enroll:

If you need a Permit to Enroll to get in the most likely reasons are:

• The class is full. If you are a graduating senior, please fill out the SEAS enrolment request form. If you attend the lectures and do well on the quizzes and first project, you are very likely to get one at the end of the second week.
• You are a graduate student. Undergraduates have piority, but if the class is not yet full, I generally issue PTEs (to students who have done well on all quizzes) at the end of the second week. Please fill out and submit the standard graduate request form.

I give out PTEs at the end of the second week, to students who have done well on all quizzes and the first project. Until you are enrolled, you will not be able to take electronic quizzes or submit projects on CCLE:

• You can take quizzes, on paper, in my office in the hour before class.
• You can take quizzes, on paper, in the classroom immediately before class.
• You can submit your project, by email, to the TA of the lab section you want to get in to.

Academic Honesty:

The most valuable thing you will get from this course is a mastery of concepts and techiques that will serve you throughout your career. Your grade in this course gives testimony to that mastery. But those benefits will only accrue, and the grade will only be meaningful if it is honestly earned. Students must follow the Student Conduct Code, which prohibits cheating, fabrication, multiple submissions, and facilitating academic dishonesty.

Students are encouraged to study together, and to discuss general problem-solving techniques that are useful on assignments; but all exams are to be completed individually without assistance or references; when working on the projects students must not share work with others, and must specify the sources for all parts of their submitted work.

If you have questions about the policy, please discuss them with me. Be warned that I take Academic Honesty deadly seriously. I use a variety of tools and techniques to detect plagiarism, I report all suspected cases to the Dean's office, and I seek full prosecution of every case I report.

Please, do not test me on this matter.

General Warnings:

You will find the material in this course to be exteremely useful. But, this is widely held to be one of the most difficult courses in the undergraduate Computer Science catalog, due to:
• the amount of reading
• the number of new and subtle concepts to be mastered
• the complexity of the principles that must be applied
• the amount of work involved in the projects

People who have had little difficulty with previous Computer Science courses are often surprised by the work load in this course.

Keeping up in this course requires considerable work and discipline.
In particular, projects must be started as soon as possible. All (but the first) involve difficulties, and students wind up losing many more points due to late submission than to functionality deficiencies.
Catching up after falling behind is extremely difficult.

Related Curriculum Standards*:

Related Computer Science Curricula 2013 knowledge areas:

• OS/Overview of Operating Systems
• OS/Operating System Principles
• OS/Concurrency
• OS/Scheduling and Dispatch
• OS/Memory Management
• OS/Security and Protection
• OS/Virtual Machines
• OS/Device Management
• OS/File Systems
• OS/System Performance Evaluation
• PD/Communication and Coordination
• PD/Distributed Systems
• IAS/Foundational Concepts in Security
• IAS/Threats and Attacks
• NC/Networked Applications
• SF/Cross-Layer Communications
• SF/Resource Allocation and Scheduling
• SF/Virtualization and Isolation
• SF/Reliability through Redundancy

Related IEEE/ACM Software Engineering 2004 (SE2004) bodies of knowledge:

• CMP.cf.4. Abstraction – use and support for (encapsulation, hierarchy, etc.)
• CMP.cf.10. Operating system basics
• CMP.cf.12. Network communication basics
• CMP.ct.1. API design and use
• CMP.ct.2. Code reuse and libraries
• CMP.ct.10. Concurrency primitives (e.g., semaphores, monitors, etc.)
• CMP.ct.14. Performance analysis and tuning
• CMP.ct.15. Platform standards (POSIX etc.)
• FND.ef.4. Systems development (e.g., security, safety, performance, effects of scaling, feature interaction, etc.)