Week Monday Wednesday Friday (or Lab Th/Fr)
1 September 23
1. Welcome to CS110 / Intro to Filesystems
presentation:small Slides, [PDF], Screencast
document:small Handout: CS110 Course Information

document:small Handout: CS110 Course Syllabus

book_1:small Reading: Skim S & K Chapter 2

Introductions, course administration and expectations. We will introduce Unix file systesms today, as well.

September 25
2. File Systems, APIs, and System Calls
presentation:small Slides, [PDF]
code:small Code (lambdas)
code:small Code (file systems)
notepad:small Assignment 1 released

We need to invest some time learning about some C and some UNIX/Linux libraries that offer us programmatic access to the file system. There are a few data structures and a collection of Linux library functions that allow us to crawl over the tree of files and directories, and there are even more functions that grant us raw, low-level access to the file contents. We'll invest some time discussing these functions and data structures—enough that we can implement a collection of obvious and not-so-obvious programs that emulate some of the terminal/shell builtins you've been using your entire UNIX lives.

September 27
3. (Lecture) More on Filesystems APIs
presentation:small Slides, [PDF], Screencast
book_1:small Reading: S & K Chapter 2
We'll work through a few more UNIX Filesystem API examples before advancing on to a discussion of how the raw hardware of a disk is leveraged to look like the filesystem you've taken for granted for the entirety of your UNIX and programming careers. My hope is that by the end of the day you'll have gained a familiarity with the filesystem APIs and begin to understand how filesystems work under the hood.
2 September 30
4. Filesystems Data Structures and System Calls
presentation:small Slides
book_1:small Reading: Begin Bryant & O'Hallaron, Chapters 2 and 1 (in that order). Chapters 2 and 1 correspond to Chapters 10 and 8 of the full textbook.
code:small Code
We need to work through the rest of our discussion of how a filesystem is layered over raw hardware. We started to explain how basic files—be they text files, audio files, executable images, etc— are segmented into blocked and distributed across free sectors of the hardware. We need to advance that discussion to be clear how filesystem supplorts the notion of a directory, and how an absolute path name like /usr/class/cs110/WWW/index.html can be parsed and translated to an inode number, which is the location within the inode table that stores metainformation about that file and where all of its payload blocks live.

We'll then discuss a few things as a way of transitioning to multiprocessing: how open file sessions are maintained by the OS on a per-process basis, and how system calls differ from traditional function calls. And time permitting, we'll introduce a new system call that's used to spawn new processes.

October 2
5. Understanding execvp
presentation:small Slides, [PDF], Screencast
book_1:small Reading: Begin: Bryant & O'Hallaron, Chapters 2 and 1 (in that order). Chapters 2 and 1 correspond to Chapters 10 and 8 of the full textbook.
code:small Code
notepad:small Assignment 2 released

This past Monday we introduced fork in the final minutes of lecture. Today we need to work through a collection of etudes so that we master the nuances of how fork works. We'll then introduce related functions, waitpid and execvp, which are used to synchronize multiple processes and transform processes to run a new executable instead of the one it inherited as part of the fork call.

October 3/4
Lab / Discussion 01. File System Experimentation
notepad:small Lab 01: File Systems and System Calls
(solution)

Your first lab will have you discuss the various ways you can exploit a file system design to implement other functions. You'll also get a chance to play with the stat command line utility and learn some new valgrind tricks.

3 October 7
6. execvp, Pipes, Interprocess Communication
presentation:small Slides, [PDF], Screencast
book_1:small Reading: Continue Reading: Bryant & O'Hallaron, Chapters 2 and 1 (in that order). Chapters 2 and 1 correspond to Chapters 10 and 8 of the full textbook.
code:small Code
Last time, we introduced execvp as the one system call that reboots a process to execute the main function of a new executable. We need to advance that discussion today by working through the implementation of a tiny shell, much like the one you're using whenever you'll using Unix. We'll then introduce the notion of a pipe as a way to set up communication channels between multiple processes.
October 9
7. Signals, Signal Handlers, and Signal Blocks
presentation:small Slides, [PDF], Screencast
book_1:small Reading: Begin: Bryant & O'Hallaron, Chapters 2 and 1 (in that order). Chapters 2 and 1 correspond to Chapters 10 and 8 of the full textbook.
code:small Code
We need to discuss signal masks, signal blocking, and how they can be used properly to avoid concurrency issues. We'll start with a contrived example where code is technically capable of executing in an order we don't intend, and we'll use signal masks and blocking to fix the problem. We'll then advance to work through a series of improvements to the simplesh program that we wrote last time.
October 10/11
notepad:small (Thursday) Assignment 3 released (Overview Video)

Lab / Discussion 02: Multiprocessing Experimentation
notepad:small Lab 02: Multiprocessing Experimentation

notepad:small Lab 02 Solution

This week we'll investigate the use of fork, execvp, and waitpid to build a command line utility called exargs. We'll then blend in some file descriptor and multiprocessing work to better understand how the two work together, and time permitting, we'll work through some short answer questions to prompt you to think more holistically about how fork and multiprocessing work.

The lab handout includes a collection of laptop exercises to elevate your gdb and valgrind acumen, though my guess is that the CA who leads your discussion section will opt to focus on the whiteboard problems and leave the laptop experimentation to you.

4 October 14
8. Race Conditions, Deadlock, and Data Integrity
presentation:small Slides, [PDF]
book_1:small Reading: Begin: Bryant & O'Hallaron, Chapters 2 and 1 (in that order). Chapters 2 and 1 correspond to Chapters 10 and 8 of the full textbook.
code:small Code
We will discuss some subtle yet interesting race conditions that can lead to a state called deadlock, where a process seemingly freezes. We will also talk about how to properly use signal handlers to clean up all children.
October 16
9. Introduction to Threads
presentation:small Slides, [PDF], Screencast
book_1:small Reading: Continue reading: Bryant & O'Hallaron, Chapters 4, skipping section 4.2. Chapter 4 refers to Chapter 12 of the full textbook.
code:small Code
We will spend some time explaining the various OS components that allow multiple processes to be (seemingly) running at the same time, even when there's just one CPU. I also want to discuss how each process can operate as if it owns all of memory, even though it clearly doesn't. We'll be discussing virtual memory and the process scheduler to advance our understanding of how these things might work.

We'll then move on to our discussion of mutlithreading and begin to work through the lecture examples I've provided today.

October 17/18
Lab / Discussion 03: Parallel Programming
notepad:small Lab 03: Parallel Programming

notepad:small Lab 03 Solution

We'd like you to spend the 80 minutes studying a parallel implementation of mergesort so you understand its architecture and ultimately believe that it works. Time permitting, I'd like you to work through a collection of short answer questions to solidify your understanding of virtual memory and process scheduling.

5 October 21
10. From C Threads to C++ Threads
Midterm Information
presentation:small Slides, [PDF]
book_1:small Reading: Continue reading: Bryant & O'Hallaron, Chapters 4, skipping section 4.2. Chapter 4 refers to Chapter 12 of the full textbook.
code:small Code
notepad:small Assignment 4 released

We started in on threading last time, and we need to continue talking about it by working through a collection of introductory examples that illustrate how threads work and the types of concurrency issues that sometimes present themselves because multiple threads are running within a process at the same time.

We'll do precisely this by working through a collection of examples in C, and then transition over to C++, which in my opinion provides much better support for threading and concurrency than pure C does.

October 23
11. Threads, Condition Variables, Semaphores
presentation:small Slides, [PDF], Screencast
book_1:small Reading: Continue reading: Bryant & O'Hallaron, Chapters 4, skipping section 4.2. Chapter 4 refers to Chapter 12 of the full textbook.
code:small Code
We need to finish up the ticket agents example from this past Monday and understand how the mutex can be used to mark the boundaries of critical regions so that at most one thread is within it at any one moment.

We'll then move on to a new example—the dining philosophers simulation—to illustrate how a system can arrive at deadlock and forever starve all threads of from CPU time. That'll be our opportunity to introduce the condition variable and the semaphore as a means of preventing deadlock from ever happening.

October 24
No labs this week -- study for midterm and work on assignment 4!
6 October 28
Midterm Exam, In class

October 30
12. More on Multithreading, CVs, and Semaphores (and some Networking)
presentation:small Slides, [PDF], Screencast
book_1:small Reading: Finish Reading: Bryant & O'Hallaron, Chapters 4, skipping section 4.2. Chapter 4 refers to Chapter 12 of the full textbook.
code:small Code
notepad:small Multithreading and Synchronization Redux

We'll continue our discussion of the semaphore by re-implementing it, and then using it to implement our final version of the dining philosophers simulation. I'll then move on to a new collection of examples that relies on the mutex and the semaphore to support a few different inter-thread communication patterns you've not seen prior.

Oct 31 / Nov 1
Lab / Discussion 04: assign3 Redux, Threads
notepad:small Assignment 5 released (Nov 1)

notepad:small Lab 04: assign3 Redux, Threads

notepad:small Lab 04 Solution:

We'd like to spend this week's lab reviewing everything about Assignment 3 that made it challenging. By now, you're well aware how difficult multiprocessing and concurrency can be, but it's not unusual for students to arrive at working Assignment 3 solutions even though they didn't quite understand everything they wrote. Problem 1 has you revisit those programs and work through why they needed to be written the way they were.

The remaining three questions all deal with multithreading. We think all three questions are instructive, but it's probably more important to work through the short answer questions of Problems 3 and 4. Problem 2 is a coding question, and that can be managed independently, outside of lab time.

7 November 4
14. Virtualization and Caching
presentation:small Slides, [PDF], Screencast
book_1:small Reading: Finish Reading: Bryant & O'Hallaron, Chapters 4, skipping section 4.2. Chapter 4 refers to Chapter 12 of the full textbook.
Today we will talk about caching, which is an important part of ensuring that programs run efficiently.
November 6
15. Introduction to Networking
presentation:small Slides, [PDF], Screencast
book_1:small Reading: Continue Reading: Bryant & O'Hallaron, Chapter 3 and Section 4.2. Chapter 3 of the reader corresponds to Chapter 11 of the full textbook.
code:small Code
After a bit of multithreading wrapup, we'll move on to formally introduce networking, the client-server idiom, request-response, and argue why a network connection is little more than a bidirectional pipe between processes on different machines.
November 7/8
notepad:small Assignment 6 released (Friday)

Lab / Discussion 05: rwlocks and Hello Servers
notepad:small Lab 05: rwlocks and Hello Servers

notepad:small Lab 05 Solution

We'll work through the implementation of a rwlock class, which is like a traditional mutex, except that it allows multiple threads to be in a critical region, provided none of them need to change any shared data structures.

Once we work through those, we'll tinker with a simple server and exploit the fact that server sockets and client sockets are internally managed as descriptors.

8 November 11
15b. API Servers
presentation:small Slides, [PDF], Screencast
book_1:small Reading: Continue Reading: Bryant & O'Hallaron, Chapter 3 and Section 4.2. Chapter 3 of the reader corresponds to Chapter 11 of the full textbook.
code:small Code
We are going to spend some time on to building an API server using threads and processes. We will then dig deeper into some network system calls.
November 13
16. Network System Calls
presentation:small Slides, [PDF], Screencast
book_1:small Reading: Finish Reading: Bryant & O'Hallaron, Chapter 3 and Section 4.2. Chapter 3 of the reader corresponds to Chapter 11 of the full textbook.
code:small Code
notepad:small Assignment 7 released

We will provide an overview of networking and explain why it's really just a distributed form of function call and return. And in spite of the fact that function calls across the internet are inherently slow, there are many software engineering advantages to hosting the implementation of some core service on a remote server.

We'll then speak a bit about HTTP to the extent we need it for Assignment 7, which goes out today. And once I do that, I'll advance on to discuss the various data structures, system calls, and Linux library functions needed to implement createClientSocket and createServerSocket.

November 14/15
Lab / Discussion 06: ThreadPool and Networking
notepad:small Lab 06: ThreadPool and Networking

notepad:small Lab 06 Solution:

This week's lab will invest some time understanding some nuances of any operational ThreadPool implementation. And then we'll work together to implement a collection of simple servers.

9 November 18
17. HTTP Web Proxy Discussion, and Overview of MapReduce
presentation:small Slides, [PDF], Screencast
book_1:small Reading: Finish Reading: Bryant & O'Hallaron, Chapter 3 and Section 4.2. Chapter 3 of the reader corresponds to Chapter 11 of the full textbook.
code:small Code
We will start class by talking about your next assignment, HTTP Web Proxy and Cache. The assignment has many moving parts, and we will delve into some of those parts before you get to coding it up.

Once we do that, we'll pivot in a short overview of how MapReduce works. We do so because it's an easily described distributed system that relies on every major topic we've relied on this quarter, and it's a huge victory to fully understand how something you've almost certainly heard of before can be implemented using everything you've learned in CS110. MapReduce is your final assignment, and we want you to be prepared to tackle it, as well.

November 20
18. Principles of System Design
presentation:small Slides, [PDF], Screencast-->
Today we'll embark on a recap of all of the general systems design principles we've been exposed to over the course of the quarter and try to make it clear that a system's design is often more intellectually captivating than its implementation.
November 21/22
Lab / Discussion 07: proxy Redux
notepad:small Lab 07: proxy Redux

notepad:small Assignment 8 released

notepad:small Lab 07 Solution:

This should be a short discussion section. We want to use the time to have you fill out a survey that will help an educational research project move forward. After we do that, we'll spend about 30 minutes talking aspects of the HTTP proxy you build for us this past week, and how things could have been implemented differently.

This is the last week of section!

-- November 25
No class -- Thanksgiving break
November 27
No class -- Thanksgiving break
November 28/29
No class -- Thanksgiving break
10 December 2
19. Non-blocking I/O
presentation:small Slides, [PDF], Screencast
book_1:small Reading:
code:small Code
Today, we'll introduce the idea of I/O event-driven programming and how it can be used to complement nonblocking I/O techniques. Linux provides I/O event detection facilities via its epoll (short for event polling) library. We'll spend today's lecture discussing three key epoll functions and the various ways they can be combined with nonblocking descriptors to build singly-threaded web servers that can handle tens of thousands of connections. We will discuss the pros and cons of non-blocking I/O while comparing it to blocking I/O approaches relying on multithreading and multiprocessing. We will finish up non-blocking I/O with two examples: expensive-server.cc and efficient-server.cc. Both methods use a single thread to support a server able to quickly respond to multiple client requests, though the efficient server does so using the epoll system calls to leverage the OS's ability to support waiting for changes to file descriptors.

notepad:small CS110 Practice Final Exams

December 4
20. Systems Today and Wrap-up
presentation:small Slides, [PDF], Screencast
notepad:small CS110 Practice Final Exams

-- December 13
Final Exam
calendar_ok:small Fri. December 13th
alarm:small 8:30am-11:30am
map:small Location: TBA


Website design based on a design by Chris Piech
Icons by Piotr Kwiatkowski