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.

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.

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.

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.

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.

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.

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

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.

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.

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.

(No labs this week)

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.

We need to finish up the final implementation of the myth-buster example from this past Monday before moving on to one huge multithreaded simulation that brings in every single concurrency pattern and relies on virtually every concurrency directive we're learned. This final example is so large, that it comes with its very own handout.

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.

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.

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.

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.

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.

We will re-start our discussion of the MapReduce algorithm, and then discuss your final assignment, which is to implement MapReduce.

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!

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.