Due: Thu Apr 30 11:59 pm
Late submissions accepted until Sat May 2 11:59 pm
Assignment by David Mazières and John Ousterhout, with modifications by Nick Troccoli.
In this assignment you will extend your work in Assignment 3 by adding locks and condition variables. In addition, you will begin to think about ethical issues related to trust.
Learning Goals
The learning goals for this assignment:
- Learn how locks and condition variables can be implemented in a singe-core system.
- Learn about techniques for establishing trust.
Getting Started
To get started on the assignment, clone the starter project using the command
git clone /afs/ir/class/cs111/repos/assign4/$USER assign4
This line creates a new folder called assign4 in your current working directory containing a copy of the starter code.
This assignment builds on Assignment 3, so once you've
cloned the starter repo, cd into the assign4 directory and invoke the
following command:
make copy_thread_sources
This will copy your code from Assignment 3 into the assign4 directory
so that you can use it for this assignment.
The command assumes that your work for Assignment 3 is in a directory
named assign3 with the same parent directory as assign4. If this isn't
the case, the command above will fail; ask for help on Ed if that happens.
The files sync.hh and sync.cc contain a skeleton for all of the
code you need to write. You will complete the declarations
of Mutex and Condition in sync.hh
and fill in the bodies of the methods in sync.cc.
If you didn't get Assignment 3 fully working, you may need to keep working on it in order to complete this assignment (if this is the case, the course staff is happy to give you lots of help to finish Assignment 3).
The directory also contains a Makefile; if you type make, it
will compile your code for both problems together with
a test program test.cc, producing an executable file
test. You can invoke ./test with an argument giving the
name of a test to run (invoke it with no arguments to see a list
of available tests).
You can also invoke the command tools/sanitycheck to run a series of basic
tests on your solution.
Try this now: the starter code should compile but almost all the tests will
fail.
Additionally, this project builds on our use of C++ classes, methods and instance variables, and uses some additional C++ features, some of which you may have used before, and others that might be new. The resources in our C/C++ guide, including the C++ classes review video, may be helpful in reviewing details of classes in C++. Also check out this C++ guide/refresher to get up to speed on static!
Important note: one of the new C++ features mentioned in the guide above is static class variables. When deciding whether to make something static, carefully consider how many copies of that field you need; do you need one per object, or one shared across all objects? Making something static when it shouldn't be can be the source of many a gnarly bug, since it will subtly share one copy instead of keeping separate copies!
Additionally, make sure to distinguish between using this and using Thread::current(). this refers to the current object in a non-static method; e.g. within Mutex::lock, it will refer to the current Mutex.
1. Mutex
Your task is to implement something you're familiar with as a client - but now you have the tools (specifically your dispatcher from part 1!) to build one yourself. The Mutex class is extremely similar to the standard C++ mutex, with the addition of a mine method. Check out sync.hh for the list of public methods on the Mutex class that you will implement - the documentation in the header file provides more information about each method's behavior.
Complete the declaration of the Mutex class in sync.hh, and
fill in the bodies of the Mutex constructor and the methods
lock, unlock, and mine.
You may assume that your code will only run on single-core systems, so disabling interrupts ensures that no other thread will run. Your solution should look similar to the uniprocessor implementation described in lecture, but must also keep track of its owner thread.
As part of this assignment, you will need to use the public methods you
implemented in the Thread class. For example, a thread can block
itself by calling Thread::redispatch (with interrupts disabled,
of course). Later on, some other thread can wake it up by invoking
the schedule method on the blocked thread. Carefully consider
how some of those methods will come in handy to perform the thread
operations you want to perform.
Make sure to properly enable and disable interrupts as needed to avoid race conditions.
At this point the tests mutex_basic, many_threads and mine should
pass!
2. Condition
Your final task is to implement something else you're familiar with as a client - a condition variable. Now that you have both a dispatcher and a mutex implementation, you have the tools to build one yourself. The Condition class is extremely similar to the standard C++ condition_variable_any. Check out sync.hh for the list of public methods on the Condition class that you will implement - the documentation in the header file provides more information about each method's behavior.
Before you start coding, think a bit about what sort of information you'll need to keep in Condition structures. There are some similarities with the Mutex implementation to consider.
Like with Mutex, the thread operations (blocking a thread, etc.) will require using the public methods from your Thread dispatcher. Carefully consider how some of those methods will come in handy to perform the thread operations you want to perform. Your implementation will also use the public methods of your Mutex class.
There should be no need for any of the Condition methods
to access the private fields of a Mutex object, or vice versa.
Complete the declaration of the Condition class in sync.hh, and
fill in the bodies of the Condition constructor and the methods
wait, notify_one, and notify_all.
You may assume that your code will only run on single-core systems, so disabling interrupts is sufficient to ensure that no other thread will run.
Make sure to properly enable and disable interrupts as needed to avoid race conditions.
At this point the remaining tests (cond_basic, two_conds, notify_all, and lock_vs_notify) should pass!
Reflecting on and Communicating Trust
As you may know, the Computer Science Department has begun adding short units on ethics to many of its classes. For CS 111 the ethics topic is trust. The overall goal of this topic is to raise your awareness of a variety of issues relating to trust. For this assignment you will consider techniques for establishing trust in a system.
We will use part of the lecture on Friday, April 24, to introduce the
issues around trust. After you have listened to that material, answer
the following questions in questions.txt:
Question 2: suppose you needed to convince another student in CS 111 that they can trust your code for Assignment 3 and 4; how would you go about that? Note: for someone else to trust your code, you may want to consider how you can increase the legitimacy of either the code itself or the creator of the code.
Question 3: suppose that you wanted to have a higher level of trust in your solutions to Assignments 3 and 4 than sanitycheck provides. What additional steps could you take to increase your level of trust that the code will perform as expected?
Software bugs are examples of situations where systems are less
trustworthy than we think or would like.
They are to difficult to test for, yet
they can have significant real-world impact. In 2020, Natalie Silvanovich
of Google Project Zero discovered a race condition with Google’s video
calling service, Duo. Please read this document,
which describes the problem, and then apply Nguyen’s framework of trust
discussed in lecture to a real world race condition by answering
the questions below in questions.txt:
Question 4: describe the race condition in Google Duo and its impact.
Question 5: in 1-3 sentences, describe one way developers of the Google Duo bug exhibit over-trust.
Question 6: In 1–3 sentences, describe one concern a user might have because of this Google Duo race condition. Consider the issue from the user’s perspective and discuss a concrete harm that could result.
Question 7: in 1-3 sentences, identify two ways a mobile phone user could infer trust in Google Duo.
Question 8: in 1-3 sentences, identify two way a mobile phone user could substitute the need to trust Google Duo.
Submitting
Once you are finished working and have saved all your changes, submit by running the submit tool in the tools folder: ./tools/submit. We recommend you do a trial submit in advance of the deadline to allow time to work through any snags. You may submit as many times as you would like; we will grade the latest submission. Submitting a stable but unpolished/unfinished is like an insurance policy. If the unexpected happens and you miss the deadline to submit your final version, this previous submit will earn points. Without a submission, we cannot grade your work. You can confirm the timestamp of your latest submission in your course gradebook.
Grading
Here is a recap of the work that will be graded on this assignment:
questions.txt: answer the questions, including the question about queues in the implementation of Mutex and Condition as well as the questions about trust.sync.hhandsync.cc: flesh out theMutexandConditionclasses.
We will grade your code using the provided sanity check tests and possible additional autograder tests. We will also review your code for other possible errors and for style. Check out our course style guide for tips and guidelines for writing code with good style!