CSE 421/521 Spring 2017

This web page serves as the syllabus for the course.

1. Overview

This course is an introduction to operating system design and implementation. We study operating systems because they are examples of mature and elegant solutions to a difficult design problem: how to safely and efficiently share system resources and provide abstractions useful to applications.

For the processor, memory, and disks, we discuss how the operating system allocates each resource and explore the design and implementation of related abstractions. We also establish techniques for testing and improving system performance and introduce the idea of hardware virtualization. Programming assignments provide hands-on experience with implementing core operating system components in a realistic development environment.

2. Calendar

We suggest that you add our shared calendar to your calendaring program. If you are not using a calendaring program, we suggest that you start using a calendaring program.

3. Information

3.1. Course Staff

  1. Instructor: Geoffrey Challen. I go by "Geoff", "Geoffrey", or "GWA"—not "Dr", "Professor, or "Sir". Please use [email protected] to aid my email filtering. However, you should rarely contact me directly. Instead, 99% of the time use the Discourse forum or 1% of the time contact the entire staff at [email protected].

  2. Teaching Assistants: Ali Ben Ali, Carl Nuessle, and Vicky Zheng, are your fantastic and hard-working teaching assistants this semester. They will be teaching recitation, holding office hours, and grading exams. Please do not email them directly—​instead, use the Discourse forum.

  3. Ninjas: In addition to the official TAs, we have a number of volunteers we call ninjas. Some are members of my research group. Others are 421/521 students from previous years. This year’s 17 ninjas are Adhish Chugh, Ben Rueda, Brijesh Rakholia, Grant Wrazen, Guru Prasad, James Droste, Jinghao Shi, Matthew McGovern, Rob Rymarczyk, Scott Haseley, Sriram Shantharam, Steve Bass, Timothy Eilinger, William Burgin, Yousuf Zubairi, and Zach Wieand. Ninjas will hold office hours but do not do any grading.

3.2. Times and Locations

The online calendar contains up-to-date information about all course meetings and activities. Please check it regularly—​changes do happen.

  1. Lecture: MWF 2:00—​2:50PM, Cooke 121 1.

  2. Recitations: T 4:00–3:50PM, Knox 110; W 3:00–3:50PM, Fronczak 454; and F 8:00—​8:50AM, NSC 210. Ali, Carl, and Vicky will rotate recitation responsibilities. Attendance is not mandatory, and you can none, one, or many depending on what fits your schedule. We will videotape recitations and add them to the recitation playlist. Graduate students may only attend recitations if there is space. However, both Knox 110 and NSC 210 are quite large rooms, so there will probably be space.

3.3. Exams

A 50-minute midterm will be given in class on Friday 3/31/2017. A 3-hour final exam will be Monday 5/15/2017 from 3:30—​6:30PM in Cooke 121. All dates are on the Calendar. Please contact the course staff as soon as possible if you cannot attend a scheduled exam for any reason.

3.4. Undergraduate Prerequisites

CSE 250: Data Structures.

=== Other Important Dates

(Also on the Calendar.)

  • Last Day to Drop Add: 2/6/2017

  • Last Day to Resign: 4/21/2017

  • Last Day of Class: 5/12/2017

4. Description

Operating systems are the masterworks of the programming world: beautiful and sophisticated solutions to difficult design problems that have emerged from years of effort by thousands of skilled programmers. Like budding artists study the works of the great masters for inspiration, programmers study operating systems. While most of you will never contribute a single line of code to a production operating system, we hope that by the end of the course you will have learned something from their elegance and maturity.

Understanding operating system design will make you a better software engineer. Struggling with operating system programming will make you a better programmer. This course gives you a chance to do both. We establish a conceptual track through lectures and exams, where we discuss the concepts and design principles of modern operating systems and how hardware devices such as the CPU, memory, and disks are multiplexed and abstracted. Equally important, however, is the programming track which proceeds through four assignments that give you the chance to implement core operating system functionality in a simplified development environment. After studying synchronization, you will implement synchronization primitives. After studying the system call interface, you will implement it. After studying virtual memory and address translation, you will design and implement a virtual memory subsystem.

Designing and implementing operating system concepts is not easy, and neither is this course. But we are here to help and committed to providing you with the support you need to succeed. Our online grading tools provide helpful feedback and allow you to repeatedly test and submit your assignments until you earn the grade you desire. Our TAs are experienced and will be available for many hours each week to provide individual help. And a number of successful previous students will return as volunteers to offer even more help. We expect that you will find this course difficult, but we hope you will also learn a large amount, have fun, and develop a passion for computer systems.

4.1. Learning Objectives

4.1.1. Conceptual Objectives

When you finish this course, you will be able to:

Outcome Assessment

Understand the abstractions supported by modern operating systems.

Class and recitation participation, midterm, final exam. 70% correctly identified marks outcome achieved.

Describe how operating systems safely and efficiently multiplex hardware resources through effective policies and mechanisms.

Analyze the designs and features of historical, current, and emerging operating systems.

4.1.2. Programming Objectives

When you finish this course, you will be able to:

Outcome Assessment

Design and implement working systems software.

Office hours attendance, homework and programming assignments. 70% correctly identified marks outcome achieved.

Identify and correct bugs in complex, multithreaded systems.

Formulate and test performance hypotheses.

4.2. ABET Outcomes

The Accreditation Board for Engineering and Technology (ABET) helps guide curriculum by defining common outcomes that coursework should help students achieve by the time they graduate. This course should assist you in four of the nine University at Buffalo outcomes:

  1. (c) An ability to design, implement and evaluate a computer-based system, process, component, or program to meet desired needs.

  2. (d) An ability to function effectively on teams to accomplish a common goal.

  3. (f) An ability to communicate effectively with a range of audiences.

  4. (i) An ability to use current techniques, skills, and tools necessary for computing practice.

  5. (k) An ability to apply design and development principles in the construction of software systems of varying complexity.

The table below describes how each outcome above is incorporated into this course:

ABET a—​k Description

c

All four assignments challenge your ability to "design, implement, and evaluate" components of an operating system.

d

All four programming assignments are performed in pairs, helping you "function effectively on teams to accomplish a common goal".

f

Preparing design documents is an integral part of the two large assignments, providing practice at effective technical communication, part of the ability to "communicate effectively with a range of audiences".

i

This course requires students to develop in a virtual machine, use Git for collaborative development, and use modern debugging and code editing tools, all preparing you to "use current techniques, skills, and tools necessary for computing practice".

k

The course assignments increase in complexity as the semester goes on, allowing students to "apply design and development principles in the construction of software systems of varying complexity".

4.3. Outline

I reserve the right to alter this rough outline as needed to the keep the class current, and our completion of the material will depend on the pace that we are able to establish and your understanding of the material.

  1. Processes and the system call interface

  2. Abstracting and multiplexing the CPU

    1. Interrupts.

    2. Context switches.

    3. The thread abstraction.

    4. Synchronization.

      1. Atomicity and concurrency.

      2. Critical sections.

      3. Synchronization primitives: locks, semaphores, and condition variables.

      4. Solving synchronization problems.

    5. Thread scheduling.

  3. Abstracting and multiplexing memory

    1. The address space abstraction.

    2. Virtual addresses.

    3. Efficient address translation.

    4. Segmentation and paging.

    5. Swapping.

    6. Page replacement policies.

  4. Abstracting and multiplexing disks

    1. Basics of disk operation.

    2. The file abstraction.

    3. File system basics.

    4. File system structures.

    5. File system operations.

    6. File system caching.

    7. The Berkeley Fast File Systems (FFS).

    8. Log-structured file systems.

  5. Operating system structure: micro, macro, exo and multikernels.

  6. Performance improvement.

    1. Measurement.

    2. Benchmarking.

    3. Analysis.

    4. Improvement and Amdahl’s Law.

  7. Hardware virtualization.

    1. Intro to virtualization.

    2. Types of virtualization.

    3. Full hardware virtualization.

    4. Binary translation and paravirtualization.

  8. Special topics (time permitting.

4.4. Programming Assignments

The course includes four programming assignments of increasing difficulty. The assignments themselves are hosted on this website. You also use the website to submit your answers and view your grades. Assignments are graded automatically and you may submit them as often as you like, using the autograder output to improve your submission.

All programming assignments are done in pairs. Both students in each pair receive the same grade for each programming assignment. Each programming assignment also has specific collaboration guidelines that you must indicate you have followed each time you submit.

A description of each assignment along with due dates are listed below. This year we expect these to be firm and no extensions will be given.

4.4.1. ASST0: Introduction to OS/161

Introduces you to the programming environment you will be working in this semester: the OS/161 operating system, the sys161 simulator, the GNU debugger (GDB), and the Git revision control system. Consists of code reading questions and a very simple implementation task.

4.4.2. ASST1: Synchronization

Deadline: Friday 2/17/2017 @ 5PM.

Your first real taste of kernel programming. After completing a set of code reading questions, you implement locks, condition variables and reader-writer locks. Next, you use them to solve a few simple toy synchronization problems.

4.4.3. ASST2: System Calls and Process Support

The first big and complex assignment. Start by completing a design that indicates you understand all of the moving pieces and what to do. Next, implement the system call interface. When you are finished, your kernel should be able to run user programs.

We split the ASST2 deadlines into two parts:

  1. ASST2.1: Setup and first steps. Deadline: Friday 2/24/2017 @ 5PM.

  2. ASST2.2: Finish the job: implement the file system system calls (open(), close(), read(), write(), lseek(), dup2(), chdir(), and getcwd()) and the process-related system calls (fork(), execv(), waitpid(), \_exit()). Deadline: Friday 3/17/2017 @ 5PM.

4.4.4. ASST3: Virtual Memory

The mountain top. A large amount of code to implement and many internal interfaces to design. As always, start with a careful design. Then implement virtual memory, including address translation, TLB management, page replacement and swapping. When you are finished, your kernel should be able to run forever without running out of memory, and you will have completed the course.

We split the ASST3 deadlines into three parts:

  1. ASST3.1: working core map. Deadline: Friday 4/7/2017 @ 5PM.

  2. ASST3.2: user paging. Deadline: Friday 4/21/2017 @ 5PM.

  3. ASST3.3: swapping. Deadline: Friday 5/5/2017 @ 5PM.

4.5. Textbook

There is no required textbook for this course. You can consider Modern Operating Systems to be a supplemental reference for those interested in learning more. The C Programming Language by Kernighan and Ritchie may be a helpful reference when completing the assignments, particularly if you are new to C.

5. Policies

5.1. Grading

Grading is evenly divided between conceptual material and programming assignments.

  • 50% Conceptual

    • 15% Midterm Exam, 35% Final Exam

  • 50% Programming

5.1.1. Extra credit

This year we will provide up to 5% extra credit to students that help us improve our course materials. All the assignments and lecture slides, as well as other resources including our Vagrant virtual machine configuration and the test161 OS/161 testing tool, are online at our ops-class.org GitHub repository. The amount of extra credit that will be provided will be commensurate with your contribution and entirely at the discretion of the course staff.

To take advantage of this offer you must also present your updates to the course staff in a way that makes them straightforward to incorporate. Do not email us, or post in the forum. Clone our repository, fix the problem, and send us a pull request. If you are curious about how much credit a particular change will earn you, post it as an issue on GitHub first and we’ll discuss.

5.2. Incomplete Grades

Please refer to the undergraduate or graduate incomplete policy as appropriate. Of particular importance is this language from the undergraduate incomplete policy (the graduate language is similar):

Students may only be given an I grade if they have a passing average in coursework that has been completed and have well-defined parameters to complete the course requirements that could result in a grade better than the default grade. An I grade may not be assigned to a student who did not attend the course.

Note that for graduate students, "the default grade accompanying an interim grade of I shall be U and will be displayed on the UB record as IU."

5.3. Academic Integrity

Please review the CSE Department academic integrity policy and the UB undergraduate or graduate academic integrity policy as appropriate to familiarize yourself with the relevant academic integrity policies and procedures. In general, the rule of thumb is that talking about code in English is OK, but talking in or exchanging code is cheating. Each assignment has specific guidelines about what types of collaboration are encouraged, discouraged, and forbidden. We will use automated plagiarism detection software to check every submission against solutions submitted in prior years as well as all publicly-available solutions online.

Students that submit plagiarized work will receive a grade of F for the course.

5.4. Disabilities

Please register and coordinate with the Office of Disability Services. Let the course staff know when accommodations need to be made. We are committed to helping you learn.

6. Getting Help

The operating systems programming assignments are difficult and most students require a fair amount of help during the semester. Here’s how to—​and how not to—​get help.

6.1. Great Ways to Get Help

  • Use the the forum. This is by far your best resource because it allows you to get help from anyone—​not just a TA or Ninja—​at any time—​not just during office hours. Please use and contribute to this valuable shared resource.

  • Come to office hours. We don’t hold them for our health and the staff gets bored when there isn’t anyone to help! So please don’t hesitate to come in. Office hours are also a great time to work on your assignments, since if (when) you get stuck help is already nearby.

6.2. Bad Ways to Get Help

  • Emailing any staff member using their @buffalo.edu email address. I instruct the staff to ignore these emails and I will as well.

  • Emailing [email protected]. This address is only for administrative uses, not for getting help on assignments.

  • Emailing [email protected]. This address is only for highly-sensitive administrative uses, not for getting help on assignments.

7. Online Resources

This website is the source for all information about the class: the syllabus (which you are reading) lecture slides, assignments, previous exams, lecture videos, and other useful information.

7.1. Videos

We try to tape all lectures, and recitations. A playlist of the music played before class is also available. Finally, we are experimenting with screencasts which are embedded into the assignments and also available in a playlist.

Previous years have also been recorded:

7.2. Forum

We are using a Discourse forum this semester for all class-related communications. Please update your profile on it and use it for all lecture- and assignment-related Q&A.

Before we got tired of it and it’s strange approach to pedagogy we used Piazza in past years. Unfortunately, there seems to be no way to make the previous forums contents public 2.

7.3. Mailing List

All enrolled students will be added to a mailing list which we will use for course communication. You are responsible for email messages sent to this list. If you are not enrolled and would like to be added to the list, you can sign up here.

8. Videos

Lectures

Recitations

Created 2/17/2017
Updated 9/18/2020
Commit 4eceaab // History // View
Built 9/18/2020 @ 11:03 EDT