Assignment 3
In this assignment, you will implement synchronization primitives for OS/161 and learn how to use them to solve several synchronization problems. Once you have completed the written and programming exercises, you should have a fairly solid grasp of the pitfalls of concurrent programming and, more importantly, how to avoid those pitfalls in the code you will write later this semester.
To complete this assignment, you will need to be familiar with the OS/161 thread code. The thread system provides interrupts, control functions, and semaphores (which will be a useful reference when implementing locks and condition variables).
Deadlines
- Released: Tuesday, September 10
- Written Part Due: Tuesday, September 17
- Preliminary Code Due: Tuesday, September 17
- Final Code Due: Tuesday, September 24
I strongly recommend you implement at least half the code before the first deadline.
Allow time for testing. Your code may not work the first time.
Or the second time.
Or the third time.
Getting Started
As usual, you'll need to decide who you're working with for this assignment, and then accept the assignment on GitHub Classroom. You can do that by clicking the link below:
We mentioned suggestions for your group naming convention in Homework 1; you can go back and check them out if you need a reminder. But Please do not include the homework number in your group name. GitHub Classroom will automatically append the homework number to your repository name, and you don't need it twice.
Group Work Rules
The course syllabus says
When working as a pair, true shared ownership is the goal. Thus, both members of a programming pair must contribute equally to the assignment, document who wrote what, and be sure that both members of the pair understand their entire submission. You are not required to adopt a CS-70 style pair-programming methodology, however.
Thus, while the CS 70 approach of two people using the same computer works well for many people, you are allowed to coordinate in other ways. For example, you could decide on two things that need to be written, plan together, go away and write them independently, and then come back and discuss and refine the work to produce code you're both happy with.
Shared ownership is the goal. Both members of the pair put in equal effort and make equal contributions, and each of you understands and approves of all the work that's done for the assignment. Thus it should never be the case that someone asks one of you, “What does that code do?” you'd have to say, “I have no idea; I didn't write it.”
Taking a different approach from CS-70-style pair programming requires careful and deliberate communication between both members of the pair to set boundaries and responsibilities, as well as explicit time for coordination and review.
Outline
First, get things set up:
Then, come up to speed on the relevant parts of the OS/161 codebase for this assignment:
Now you get to write code. Read the entire coding component before you begin. Doing so will help you work out how much work you have to do, and give you things to be mulling in the back of your mind while you work on other parts.
Finally, submit your code:
After submission, we'll have a peer review process:
Notes & Tips
Code Quality
In this and subsequent programming assignments, you will be developing a patch to OS/161 to implement a particular feature. This patch will be voted on by the other members of the class, and assessed according to the following criteria:
- Your code should work correctly.
- Your code should be cleanly written and easy to follow (for someone else in the class).
- You should supply documentation with your patch.
- Your code should be sufficiently commented;
- Your code should match the coding style of OS/161 (not just formatting; your code should feel like it fits in with “the OS/161 way” as best you understand it).
In other words, the skills you learned in CS 70 are still needed.
Concurrent Programming with OS/161
If your code is properly synchronized, the timing of context switches and the order in which threads run should not change the behavior of your solution. Of course, your threads may print messages in different orders, but you should be able to easily verify that they follow all the constraints applied to them and that they do not deadlock.
Built-In Thread Tests
When you booted OS/161 in the first assignment, you may have seen the options to run the thread tests. The thread-test code uses the semaphore-synchronization primitive. You should trace the execution of one of these thread tests in GDB to see how the scheduler acts, how threads are created, and exactly what happens in a context switch. You should be able to step through a call to mi_switch() and see the precise point where the current thread changes.
Thread test 1 (tt1 at the prompt or tt1 on the kernel command line) prints the numbers 0 through 7 each time that each thread loops. Thread test 2 (tt2) prints only when each thread starts and exits. The latter is intended to show that the scheduler doesn't cause starvation—the threads should all start together, spin for a while, and then end together.
Debugging Concurrent Programs
thread_yield() is automatically called for you at intervals that vary randomly. While this randomness is fairly close to reality, it complicates the process of debugging your concurrent programs.
The random-number generator used to vary the time between these thread_yield() calls uses the same seed as the random device in System/161. Thus you can reproduce a specific execution sequence by using a fixed seed for the random-number generator. You can pass an explicit seed into the random device by editing the “random” line in your sys161.conf file. For example, to set the seed to 1, you would comment out the existing line that configures the random device and add a replacement line that reads as follows:
28 random seed=1
We recommend that while you are writing and debugging your solutions you pick a seed and use it consistently. Once you are confident that your threads do what they are supposed to do, set the random device back to the autoseed setting. Using different random seeds should allow you to test your solutions under varying conditions and may expose scenarios that you had not anticipated.
Share Tips
Although you may not share implementation code with other class members, you should feel free to share useful tips on topics such as using OS/161, designing a lock implementation, debugging with gdb, and so forth. The class Pizza forum is a good place to share such tips.
(When logged in, completion status appears here.)