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

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 forum to suggest questions and topics to be discussed during the lecture sessions.
• asking questions during the lecture sessions.

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.

Quizzes

Years of experience have consistently taught me that the greatest single predictor of how much a student will get from a lecture is how well they understood the material before the start of the lecture. I have found (and student surveys regularly confirm) that giving daily quizzes on the assigned reading gets students to do the reading before the lecture, and greatly enhances learning. A secondary purpose of the quizzes is to enable me to assess what concepts you are having trouble with, so that I can give them greater emphasis in future lectures.



I attempt to choose quiz questions, based on key concepts, that few people could answer from common sense or general knolwedge, but should not be too difficult to answer the day after a single reading. Each quiz will have four or five questions, typically asking

• definitions of or distinctions between key terms
• descriptions or examples of key concepts
• applicability, efficacies and issues with techniques
• key results from studies
Most of these questions will be based on the associated learning objectives, so you may find it helpful to review the list of learning objectives for the next lecture before starting the reading.

Most quiz questions can be answered with a single sentence (or even a few words). Since the quizzes are timed, short answers are pretty clearly the best.

It is important that you review the feedback you receive on your quiz answers ...

1. to improve your understanding.
2. to help me identify bad questions or grading errors.
3. because quiz questions where people have trouble often reappear on exams.

Exams

There are two exams: a mid-term, and a two-part final. These are closed book exams. The purpose of these exams is to determine whether or not you understand the key concepts that have been discussed in the preceding lectures and chapters.

The mid-term, and part-one of the final will be comprised of roughly 10-12 multi-part questions, covering (respectively) the first, and second halves of the course. Some may ask for definitions and examples, but most will ask you to describe how or why something works, to contrast related concepts, to explain which principles are applicable, or to predict what would happen in some situation. The vast majority of these questions will pertain to designated key concepts, and in most cases the answers will have been presented in the text, the lectures or both. Most exam questions have brief (2-4 sentence or a simple diagram) answers. Typical types of questions might be:

• simple "do you remember" questions, comparable in nature and difficulty to quiz questions.
• moderate "can you describe/contrast/apply" questions, comparable in nature and difficulty to in-class discussions.
• moderate "list and briefly describe the steps" question, for processes covered in the reading and lectures.
• moderate "consider this" questions, asking you to find answers not specifically discussed in class.
• a philosophical extra credit question, related to key concepts, but un-related to any reading or in-class discussion.

Part-two of the final exam will be a set (6-8) more difficult (analyze this situation, propose a solution) questions spanning the entire course. You can choose any four of these that you want to answer.

Different study techniques are more effective for different people. This is a general suggestion for review, that is meant only to guide your own study efforts:

• Start by reviewing the key learning objectives.
• If there is a concept, issue or technique that you don't think you could talk about for five minutes, go back and review the lecture notes.
• If anything in the lecture notes (including the discussion points) is not completely obvious, go back and review the related reading.

Exam (and quiz) questions are almost entirely based on the key concepts list. You are encouraged to pose questions and continue discussions of these key concepts in the on-line forum.

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, cost just about the same amount of money you would have otherwise spent on an Operating Systems text. We also have a few of these systems available for checkout ... but, if you are taking this course, the odds are that you will find many other uses for such embedded development systems after this course is over.

Student Presentations

Students will form two-person teams, choose a lecture, and research and prepare a related presentation and discussion (beyond the material covered by the assigned reading and prepared lecture slides). Suggested topics are recent problems, solutions, issues, or incidents ... but what I am looking for is good research and interesting discussions of relevant topics.

Activity Objectives:
• To develop and demonstrate the ability to do research into current OS-related topics.
• To develop and demonstrate the ability to prepare and deliver Transfer-of-Information presentations.
• To develop additional depth and explore interesting issues beyond the planned course syllabus.

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.

• 10% student presentations and discussions.

  Presenters will be graded on relevance of topic, depth of research, and quality of preparation/presentation.



• 40% 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
  • 5% 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

Late and make-up policy

• there are no make-ups for quizzes, but you can take a quiz before it is due, and I will drop one or two of your lowest quiz scores in computing your final grade.
• each student has 5 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.

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 Academic Honesty Standards of both Harvey Mudd and the Computer Science Department which prohibit 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.)