CS262a is the first semester of a year-long sequence on computer systems research, including operating systems, database systems, and internet infrastructure systems. The goal of the course is to cover a broad array of research topics in computer systems, and to engage you in top-flight systems research. The first semester is devoted to basic thematic issues and underlying techniques in computer systems, while the second semester goes deeper into topics related to scalable, parallel and distributed systems. The class is based on a discussion of important research papers, and a research project.
Prerequisites: The historical prerequisite was to pass an entrance exam in class, which covered undergraduate operating systems material (similar to UCB's CS162). However, this year we are trying it without an exam. However, if you have not already taken a decent undergrad OS class, you should talk with us before taking this class. The exam also had the benefit of "paging in" the undergrad material, which may have been its primary value (since the pass rate was high).There will be one midterm exam (albeit near the end), and no final exam.
Research projects are a critical aspect of the course. Your goal
is to do some quality systems research; that is, to add to our understanding
of how to build systems. Research projects must be written up in
a term paper, and will be presented in a poster in a departmental mini-conference.
Suggested project ideas will be provided by the instructors, but you are
strongly encouraged to come up with your own project ideas. Potential
projects include implementation or analysis of some piece of an OS, a DBMS,
or an internet service; extending one of these systems with new functionality;
or measurement and analysis of existing systems with the goal of better
understanding issues in system design.
We will read and discuss 2-4 papers per week. Most of the
papers for the class will be available either on-line, or as handouts in
a previous class. An additional suggested text is Gray and Reuter's Transaction Processing: Concepts and Techniques
|
Part 1: Basics and Classics |
|
| Tu 1/22 Week 1 |
The UNIX Time-Sharing System
Dennis M. Richie and Ken Thompson (New electronic version) |
| Th 1/24 | A History and
Evaluation of System R [in the Red Book] Donald D. Chamberlin, Morton A. Astrahan, Michael W. Blasgen, James N. Gray, W. Frank King, Bruce G. Lindsay, Raymond Lorie, James W. Mehl, Thomas G. Price, Franco Putzolu, Patricia Griffiths Selinger, Mario Schkolnick, Donald R. Slutz, Irving L. Traiger, Bradford W. Wade and Robert A. Yost Optional Reading 1: Architecture of a Database System [also in textbook] |
|
Part 2: Persistent Storage |
|
| Tu 1/27 Week 2 |
A Fast File System for UNIX
McKusick, Joy, Leffler and Fabry Analysis and Evolution of Journaling File Systems Optional reading: The Design and Implementation of a Log-Structured File System Rosenblum and Ousterhout (229K) |
| Th 1/31 |
The HP AutoRAID Hierarchical Storage System
[My temporary local copy,\
2-up version] Wilkes, Golding, Staelin and Sullivan |
| Tu 2/5 Week 3 |
ARIES: A Transaction Recovery Method
Supporting Fine-Granularity Locking and Partial Rollbacks
Using Write-ahead Logging,
2-up version C. Mohan et al. (in Red Book) |
|
Part 3: Concurrency |
|
| Th 2/7 | Experience with Processes
and Monitors in Mesa Butler Lampson and David Redell |
| Tu 2/12 Week 4 |
Lightweight Recoverable Virtual Memory M. Satyanarayanan, Henry H. Mashburn, Puneet Kumar, David C. Steere, and James J. Kistler |
| Th 2/14 |
Granularity of Locks and
Degrees of Consistency in a Shared Database Gray et al. (Also in the Red Book) On Optimistic Methods for Concurrency Control Kung and Robinson Optional reading: Generalized Isolation Levels Atul Adya, Barbara Liskov, Patrick O'Neil |
| Tu 2/19 Week 5 |
Concurrency Control Performance
Modeling: Alternatives and Implications Agrawal et al. |
| Th 2/21 |
Lottery Scheduling: Flexible Proportional-Share Resource Management
Waldspurger and Weihl |
| Tu 2/26 Week 6 |
SEDA: AnArchitecture for Well-Conditioned,
Scalable Internet Services
Matt Welsh, David Culler, and Eric Brewer Capriccio: Scalable Threads for Internet Services Rob von Behren, Jeremy Condit, Feng Zhou, George C. Necula, and Eric Brewer |
|
Part 4: Query Processing |
|
| Th 2/28 |
Access Path Selection in a Relational Database Management System
[all new version!] [in Red Book] Selinger, Astrahan, Chamberlain, Lorie & Price Optional reading: Grammar-like Functional Rules for Representing Query Optimization Alternatives G. Lohman [in Red Book] |
| Tu 3/4 Week 7 |
Parallel Database Systems:
The Future of High Performance Database Systems Dave DeWitt and Jim Gray MapReduce: Simplified Data Processing on Large Clusters Dean and Ghemawat |
| Th 3/6 | |
| Tu 3/11 Week 8 |
|
| Th 3/13 | |
| Tu 3/18 Week 9 |
|
| Th 3/20 | |
| Tu 3/25 Th 3/27 |
Spring Break |
| Tu 4/1 Week 10 |
|
| Th 4/3 | |
| Tu 4/8 Week 11 |
|
| Th 4/10 | |
| Tu 4/15 Week 12 |
|
| Th 4/17 | |
| Tu 4/22 Week 13 |
|
| Th 4/24 | |
| Tu 4/29 Week 14 |
|
| Th 5/1 | |
| Tu 5/6 Week 16 |
|
| Th 5/8 | Final Lecture |
| An architect's first work is apt to be spare and clean. He
knows he doesn't know what he's doing, so he does it carefully and with great
restraint
As he designs the first work, frill after frill and embellishment after embellishment occur to him. These get stored away to be used "next time." Sooner or later the first system is finished, and the architect, with firm confidence and a demonstrated mastery of that class of systems, is ready to build a second system. This second is the most dangerous system a man ever designs. When he does his third and later ones, his prior experiences will confirm each other as to the general characteristics of such systems, and their differences will identify those parts of his experience that are particular and not generalizable. The general tendency is to over-design the second system, using all the ideas and frills that were cautiously sidetracked on the first one. The result, as Ovid says, is a "big pile." -- Frederick P. Brooks, Jr. The Mythical Man-Month |