UCLA CS111, Section 1, Spring 2016
Operating Systems Principles

Instructor: Mark Kampe

My background is not academic. I am a professional engineer. 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

• 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, and 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

• 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 static and dynamic/sharable 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:

• much more 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):

• Principles of Computer System Design part II, by Jerome Saltzer and Frans Kaashoek
• Wikipedia articles for general overviews of areas not covered by the other texts
• numerous readings from chapter 2 (System Calls) of the Linux Programmers' Manual as detailed examples
• monograph's written specifically for this course

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 text. Most of the lecture time will be used 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.

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 me to present, you can add them to a publicly writable Discussion Topic Request List.

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 (BH 4532-B one hour before and after each class session (13:00-13:50, 16:00-16:50). When not on campus, I am generally on-line. The most reliable way to reach me is via email markk@cs.ucla.edu. 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.


• 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
  • 15% Project 2: Synchronization
  • 10% Project 3: File Systems


• 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)


• 10% one research paper or embedded systems project ... due at the end of the quarter
  The purpose of the research paper is to develop and demonstrate your ability to read, understand, and draw useful conclusions from contemporary Operating System research.
  The purpose of the embedded systems project is to demonstrate your ability to apply the principles discussed in this course to a whole-system project.


• 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 the research paper and part 2 of the final exam tend to be distributed over a much wider range.

• I do not grade on a curve, but a fixed scale. The break points generally fall within two points of 90/80/70/60
• I do look carefully at the break points to make sure that students who did similar work do not get different grades
• 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

• there are no make-ups for quizzes, but you can take a quiz before it is due.
• each student has four slip-days that can be used for any lab or research paper due date. After those have been used up, a grade is reduced by 10% for each 24 hours late the assignment is.
• if you miss an exam due to medical necessity, substantiated by an attending physician, you will have the opportunity to take a (different) make-up exam at some later date.

• I will always correct any (promptly reported) error in score computation.
• I am always willing to explain exam grading criteria.
• I am usually 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 having misunderstood the question
  • giving credit for not having 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.

Permission to Enroll:

If you need a PTE 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, you are very likely to get a PTE 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.

Academic Honesty*:

Students must follow the UCLA Student Conduct Code, which prohibits cheating, fabrication, multiple submissions, and facilitating academic dishonesty. A summary of the academic integrity material of the Student Conduct Code can be found in the Student Guide to Academic Integrity, and the Office of the Dean of Students has a workshop on academic integrity.

Students are encouraged to study together, and to discuss general problem-solving techniques that are useful on assignments; but when working on the projects students must not share work with others, and must specify the sources for all parts of their submitted work. For your research paper, you are free to quote from the paper on which your work is based. But all conclusions drawn from that paper must be your own (not from other commentaries or discussions with classmates). For any statement that is not your own, cite your source.

If you have questions about the policy, please discuss them with the instructor. 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:

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.
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.)