CSC213 Operating Systems and Parallel Algorithms

Fall 2012

Synopsis: This course is a bridge between the past and the future. We will learn to appreciate abstractions already provided by operating systems, which will help you become not only proficient users of modern systems (from a programming perspective), but also effective designers of your own abstractions. As extravagantly multiprocessor systems become more prevalent and more important, the principles of synchronization and parallelization will become essential knowledge for building systems that can effectively harness the ongoing developments in computing power.

"All problems in computer science can be solved by another level of indirection."

- Butler Lampson, who attributes the sentiment to David Wheeler, who continues ...

... But that usually will create another problem.

Instructor:	Jerod Weinman
Office:	Noyce 3825
Phone:	x9812
E-mail:	[`weinman`]

Lab Assistant:	Zach Butler
Assistant Hours:	7:30-8:30 Thursday

Class	MWF	8:00-8:50 am	Science 3819
Lab 1	T	9:00-9:50 am	Science 3819
Lab 2	T	1:15-2:05 pm	Science 3819

Course web page: http://www.cs.grinnell.edu/~weinman/courses/CSC213/2012F

1 Accommodations
2 Overview
3 Textbook
4 Class attendance
5 Assignments and Activities
    5.1 Reading
        5.1.1 Preparation
        5.1.2 Reading journal
    5.2 Participation
    5.3 Significant Bits
    5.4 Laboratory Work
    5.5 Exams
6 Grading
7 Academic Honesty
8 Deadlines
9 Contacting Me

1 Accommodations

If you have any disability that requires accommodations, please meet with me right away so that we can work together to find accommodations that meet your learning needs. You will also need to provide documentation of your disability to the Dean for Student Academic Support and Advising, Joyce Stern, located on the 3rd floor of the Rosenfield Center (x3702).

Please also note that I require your accommodations. The synthetic fragrances found in deodorants, lotions, after shave, body sprays, laundry products, perfume, cologne, etc. make many people who suffer with asthma, allergies, environmental sensitivities, cancer, and migraines much sicker. I am sensitive to many such chemicals you may not even notice, so please try to avoid using such scented products before coming to class and especially if you visit my office.

2 Overview

"Operating Systems" should really be called "Software Systems." This course will help you understand the abstraction from a hardware-based machine to the software-based world of the programmer. Computational complexity is one (very important) aspect of analysis, but another critical aspect is "the system." Learning about what is abstracted can help you debug your program's performance on a system.

Programs large and small will use an OS. Many growing application areas (e.g., e-commerce, social networking, information management/retrieval) and a diverse array of fields (such as biology, climatology, physics, ecology, and sociology) incorporating more computation will require large systems that effectively employ multiple CPUs, disks, network interfaces, etc. Expanding the computational frontier will require fluency in the areas of synchronization, parallelization, and distributed algorithms.

Perhaps it is you who will soon help craft a new language that makes writing parallel programs to exploit multiple CPUs as easy as it is to write a file to magnetic disk today (as opposed to the punch cards, assembly code, and device driver bit-twiddling of yore.)

Our major objectives for this course include:

Learning to identify, understand, and practice the principles of abstraction behind OS design that are supplied to the programmer
Understanding modern OS design principles that enable you to build effective large-scale, networked, or multi-threaded applications
Fluency in the elements of synchronization and concurrency along with design principles for parallel processing
Learning to evaluate and communicate designs and empirical behavior of systems

Why take it?

If you have any interest in advanced computer science study, high-performance computing, or adding a twist of computation to just about any other science, this course will be highly relevant and rewarding for you! This course fulfills the CS major's systems requirement.

What do I need to know?

This course assumes you have taken CSC 161. That means you should be reasonably adept at

the practice of programming (problem analysis, program design, debugging, etc.).
programming in the C language

If you're a little rusty on the C, you should review your earlier class material or Walker's An Introduction to C Through Annotated Examples, and keep a C reference handy. (After all, even writers who are perfectly fluent speakers of English keep a dictionary or style manual close by when practicing their craft!)

3 Textbook

Our main textbooks are:

Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau. Operating Systems: Three Easy Pieces. 2012. ISBN: 978-1-10-597912-5
Ian T. Foster. Designing and Building Parallel Programs. Addison Wesley, 1994. ISBN: 0-201-57594-9
David B. Kirk and Wen-mei W. Hwu. Programming Massively Parallel Processors. Morgan Kauffman, 2010. ISBN: 978-0-12-381472-2.

The first two are freely available online, while several copies of the third are on reserve in the Kistle Science Library.

You may also wish to acquire a good C language reference and keep it handy. You may wish to refer to the following free online (first) or trusty print (second) reference manuals.

Eric Huss, The C Library Reference Guide, University of Illinois Student Chapter, 1997.
Samuel P. Harbison and Guy L. Steel. C: A Reference Manual, Fifth Edition. Prentice Hall, 2002. ISBN: 0-13-08952-X

Occasionally our discussions will be supplemented by other texts or research papers. I will provide these and note them in the detailed class schedule.

4 Class attendance

Class meetings will involve a mix of discussions, collaborative activities, labs, and the occasional mini-lecture. In short: You are expected to attend and actively participate in class. I am expected to make class worth attending.

Because is a collaborative, discussion-based course, your presence is integral to your learning. Thus, 1.5% will be deducted from your overall grade for each absence. I know that sometimes "things happen." Therefore, you will be granted one unexcused absence from class without penalty. However, this rebate is cancelled upon a second absence.

If you are absent, I would appreciate a written explanation (email is appropriate). If you know in advance that you will be absent for any reason, please notify me in writing (again, email is fine) at least 7 days in advance to make arrangements for considering your absence excused.

Because I do not wish you to risk harm to yourself or others, I am likely to moderate penalties in case of illness.

Our discussions benefit from your contributions. If you do miss a class, you must first talk to a classmate about any material that you may have missed. After that, you may follow up with the instructor about any further questions or concerns.

5 Assignments and Activities

Under a normal 16 credit load, I expect that you will spend at least 40 hours per week on your studies (class time, homework, and studying).¹ Thus, you should plan to spend a minimum of 10 hours/week on work for this course:

5.1 Reading

Our class meetings will be heavily discussion-based, and this will require a significant amount of preparation on your part. Most of this will consist of careful reading and reflection on the material through the use of a reading journal.

5.1.1 Preparation

You should check the class schedule for updates and read any material that has been assigned before coming to class. Reading the textbook entails the following:

Overview: You should quickly skim through the reading once to get an overview of the material to be covered, paying particular attention to subject headings and topic introductions. This first "reading" can (and should) be very quick. (Expected time: 5 to 10 minutes.)
In-Depth: Next, read the material closely. Try to understand what individual steps of algorithms or mathematical proofs are accomplishing. Not everything will make sense at this point, but hopefully many things will. (Expected time: 40 to 50 minutes.)
Final Notes: After carefully reading the material, mentally review and try making a few notes to yourself about what you think are the most important concepts being covered, as well as any questions you have. (Expected time: 5 to 10 minutes.)

Many of the readings are fairly short (about 13±6 pages, or roughly 30-40 pages per week), but can contain code and concepts that require a moderate amount of study. While I realize not everyone learns best by reading, you are asked to make your best effort and come to class with any questions you may have. Then we can proceed with discussion, examples, and exercises that enhance and clarify the material in class.

5.1.2 Reading journal

To help focus your efforts and give us a basis for discussion, you will be provided short a list of questions to answer for each day's reading. Reflecting upon your responses to the questions will help to give you a deeper understanding of the most important concepts surrounding each topic. See the accompanying "Reading Journal" document on the course web page.

Your responses are due by 10:30 p.m. the night before class. No late responses will be accepted. You will submit your responses electronically to a private journal via our PioneerWeb course page, where I will be able to give you feedback on your writing.

While these low-stakes writing assignments are technically "informal," they must reflect a certain level of engagement and evidence of thinking seriously about the material.

Responses will be graded using the following ternary scale:

PLUS	Exhibits exceptional clarity, insight and/or creativity.
CHECK	Exhibits evidence of processing and studying concepts.
MINUS	Superficial response or insufficient evidence of engagement.

Because I expect most entries will receive a check, I will comment on your journal to report a plus or minus. You should expect to discuss the issues raised in your reading journal entries during class. Because this class is somewhat larger, I may only grade 50% of your reading journal entries (which will be sampled randomly).

5.2 Participation

Because much of our work in this course involves collaboration and discussion, you will be evaluated on your participation.

Participating in class involves:

being present in class (physically and mentally)
coming to class on time
coming to class prepared
asking questions when appropriate
making positive contributions to class discussion by volunteering and when called upon
staying on task during collaborative exercises, and
working effectively with your group.

Students who regularly meet these criteria can expect to earn 90% (i.e., an A-) for their participation grade. I will reward students who regularly provide significant insights or guide discussion in productive ways with a higher participation score. Students who fail to participate regularly or who participate in counterproductive ways (e.g., by dominating the conversation or making inappropriate comments) can expect to earn a lower score.

5.3 Significant Bits

From time to time, one member of the class will present a five minute overview/preview/insight/review of a recent development in the broad area of "systems." The idea is to establish a practice of following technological developments in the popular and technical press as well as research publication venues. In doing this, you will inform your classmates, at a high level, about something that relates to the course material in principle and goal, rather than necessarily a particular topic. Your presentation should include what the development is, why it is important, a bit about how it is/was done, and perhaps something on who did it. You will asked to do just one during the semester, so find something interesting and share it with us! See the course web page for the schedule, details, evaluation rubric, and suggestions for finding topics.

5.4 Laboratory Work

We will practice using programmer-level OS elements via the UNIX system call interface and C standard library in our weekly lab sessions. Since lab time is limited, it is very important for you to come prepared by reading the assignment and any other related material beforehand. You will start your work in our weekly sessions but complete it outside of lab. Assignments may be broken into parts with multiple due dates to help you structure your time. You will typically complete these labs in pairs or groups, oftentimes assigned by me on a rotating basis, and only one lab will be submitted for the group.

Lab reports will typically be due the following Friday and/or Monday after the Tuesday meeting. See the course webpage and the particular lab for submission guidelines and formats.

Instructions regarding collaboration will be given with each assignment. While you are welcome to discuss course concepts with others, solutions and any work you do and submit should be that of you and your group alone. (See Academic honesty, section 7 below.)

Most work is required to be done with partners, which will often be assigned. Working with a partner will help ensure you can take some advantage of the principle that "Given enough eyeballs, all bugs are shallow."² Working with an assigned partner will increase the chances of being exposed to different ways of thinking and problem-solving as well as help you practice the skills you'll need in the real world, where you typically do not get to choose your coworkers.

Working collaboratively means everyone whose name appears on a submission has contributed to and understands all parts of the work. I reserve the right to briefly interview you to ask questions about your work. The kinds of questions I would ask will be easy for anyone who contributed to and understands their submission.

You are highly encouraged to use the PioneerWeb Discussion Board for questions related to the course. If a post is related to an assignment, it must adhere to the standards of collaboration for that particular assignment.

5.5 Exams

As opportunities for you to demonstrate your design prowess and grasp of OS abstraction principles, there will be two hour exams as well as a cumulative final exam.

Hour Exam 1	Friday, October 5
Hour Exam 2	Friday, November 16
Final Exam	Friday, December 21 (2 PM)

Do not make airline reservations that will conflict with your final exam schedule.

6 Grading

My goal is for everyone taking this course to be able to demonstrate familiarity and fluency with the course concepts. I would be very happy if you all met the goals above and received "A"s. The following weighting will provide a basis for evalution,

Laboratory Work	45%
Reading Journal	15%
Discussion & Participation	5%
Hour Exams	20%
Final Exam	15%

with the caveat that you must pass the final exam to pass the course.

7 Academic Honesty

As students, you are members of the academic community. Both the College and I expect the highest standards of academic honesty. (See the Grinnell College Student Handbook, e.g.,
http://www.grinnell.edu/offices/studentaffairs/shb/academicpolicies/academichonesty). Among other things, this means clearly distinguishing between work and ideas that are your own, and those that should be attributed to others. It is expected that the collaboration policies given in this syllabus and on particular assignments will be followed. In particular:

When you explicitly work as part of a group or team, you need not identify the work of each individual (unless I specify otherwise).
You may discuss concepts (algorithms, ideas, approaches, etc.) described in the readings, during class, or explained in the lab assignments with anyone.
You may only discuss homework assignments (algorithms, solutions, write-ups, code, debugging, etc.) with your group members, the class mentor, or the instructor.
All the work submitted (code, experimental data, write-ups, etc.) must be your own. Code or documentation provided by the instructor should be attributed, but no other code or written work (from any source) may be shared with others or copied for your own use.
All non-syntax consultations (including the textbook and language references) require formal citation within the related program or write-up.
Any conceptual contributions by others (not in your group) must be acknowledged and attributed in your report. That is you must give specific attribution for any assistance you receive. The suggested acknowledgment format is

"[Person X] helped me to do [thing Y] by [explaining Z]."
Any program results or output must be faithfully recorded, not forged. (A thoughtful explanation of unexpected behavior can often be a worthwhile submission and is much better than the alternative.)
You are responsible for safeguarding your work from being copied by others. This requires you to take reasonable precautions with hard copy printouts as well as file system permissions.

As an instructor, I will meet my obligation to bring any work suspected to be in violation of the College's Academic Honesty Policy to the attention of the Committee on Academic Standing, after which there is no recourse with me.

8 Deadlines

Assignments are due at the specified time and date. Assignments due on days for which you have a prior excused absence must still be submitted by the deadline.

A late penalty of one letter grade will be deducted in each subsequent twenty-four hour period after the deadline.

Exception: Deadlines for MathLAN computer-based assignments will automatically be extended by at least one twenty-four hour period if MathLAN is down for an unscheduled period of three or more hours during the week preceding the assignment due date.

9 Contacting Me

Please come by during my office hours to discuss the course content, get any extra assistance, or just talk about how the course is going. Note that if multiple students have similar questions or issues, we may work together as a group. If you cannot attend a scheduled office hour, you may also email me to schedule an appointment; please include 3-4 possible meeting times so that I can pick one that works for me.

I enjoy getting to know my students, but I prefer to reserve office hours for academic matters. If you would like to have a more informal conversation, I would be delighted to accept an invitation to eat lunch with you at the Marketplace.

Email is also a reliable way to contact me, but please allow 24 hours for a response (except on weekends, when I do not regularly read email). You may also call me in my office (x9812) for more urgent matters (e.g., you will be missing a lab due to illness).

With thanks to Janet Davis for the "Reading Suggestions" and other key policies.

Footnotes:

¹This is a minimum recommendation for achieving "satisfactory" (i.e., C-level) results. "Good" or "excellent" results may require a greater investment.

²This principle is dubbed Linus's Law by Eric S. Raymond in The Cathedral and the Bazaar, O'Reilly Media, 1999, p. 30.