In this assignment you finally get to write your own code in OS161! By the end of this assignment you will
Have a good understanding of the implementation of spinlocks and semaphores in OS161
Implement locks
Implement condition variables.
Step 1. Prepare
Make sure you don't have any uncommitted updates in your repo. Now, tag your repository as shown here:
git tag asst2-start
Now push that new tag:
git push --tags
Make a directory submit/asst2 in your os161 tree. You will put your file with the answers to code reading questions in that directory.
Command line arguments to OS161
Your solutions to ASST2 will be tested by running OS161 with command line arguments that correspond to the menu options in the OS161 boot menu. Please DO NOT change any existing menu option strings, since we will be using them to automate testing.
Physical memory and CPUs
In order to execute the tests in this assignment, you may need more than the 512 KB of memory configured into System/161 by default. We suggest that you allocate at least 2MB of RAM to System/161. This configuration option is passed to the mainboard device with the ramsize parameter in your sys161.conf file. Furthermore, having many CPUs will enhance the rigour of your testing. Make sure the mainboard device line looks like the following:
31 mainboard ramsize=2097152 cpus=4
Concurrent programming with OS161
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 of the constraints applied to them and that they do not deadlock.
Built-in thread tests
When you booted OS161 in ASST0, you may have seen the options to run the thread tests (type ? at the menu for a list of commands). 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 what exactly happens in a context switch. You should be able to step through a call to thread_switch() and see exactly 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 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 awhile, 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. This means that you can reproduce a specific execution sequence by using a fixed seed for the random number generator. You can pass an explicit seed into random device by editing the "random" line in your sys161.conf file. For example, to set the seed to 1, you would edit the line to look like:
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 done with initial debugging/testing, remember to set the random device back to autoseed. This should allow you to test your solutions under varying conditions and may expose scenarios that you had not anticipated, which is central to effective testing.
Step 2. Code reading exercises
Please answer the following questions and submit them with your assignment. Place the answers in a file called asst2-answers.txt in your submit directory.
What happens to a thread when it exits (i.e., calls thread_exit())? What about when it sleeps?
What function(s) handle(s) a context switch?
What does it mean for a thread to be in each of the possible thread states?
What does it mean to turn interrupts off? How is this accomplished? Why is it important to turn off interrupts in the thread subsystem code?
What happens when a thread wakes up another thread? How does a sleeping thread get to run again?
What function(s) choose(s) the next thread to run?
How does it (do they) pick the next thread?
What role does the hardware timer play in scheduling? What hardware independent function is called on a timer interrupt?
Describe how wchan_sleep() and wchan_wakeone() are used to implement semaphores.
How does the implementation of wchan ensure that a thread never misses a wakeup signal: that another thread cannot attempt to awaken the first thread just as it is preparing to sleep, but before it is actually placed into the sleep queue?
Step 3. Implement locks for OS161
The interface for the lock struct is defined in kern/include/synch.h. Stub code is provided in kern/thread/synch.c.
Requirements:
Comply to the interface. Take a look at the stub code provided in kern/thread/synch.c. Your implementation must conform to this API. Please don't change it, as this will break the tests that we will use to test your assignment.
Mutual exclusion. It's probably a no-brainer that your locks must provide mutual exclusion. You are going to implement the simplest semantics of locks: only one thread can hold a lock at any given time.
No busy-waiting. If you carefully read the OS161 code, you noticed that there is an implementation of spinlocks. Spinlocks derive their name from the method that they use to wait until the lock becomes available: they spin, or busy-wait, hogging the CPU and checking if the lock became available. While this is perfectly fine for short critical section and only on a multiprocessor system (why?), a general implementation of locks must be more universal. We must be able to use them on a system with a single CPU and for long critical sections, e.g., those involving I/O operations, where it makes no sense to busy-wait on the CPU. Therefore, your locks implementation must not busy-wait on a taken lock. It must give up the CPU until the lock becomes available.
You are allowed to use any other functions already available in OS161. It's your kernel! We will test your code by running the lock test available in the OS161 menu (sy2). Make sure that your kernel passes the test before submitting your code. And don't forget to bmake install your kernel before running it!
Step 4. Implement condition variables for OS161
Implement condition variables with Mesa semantics for OS/161. The interface for the cv struct is also defined in synch.h and stub code is provided in synch.c. If you are still unsure what condition variables are, take a look at this document. Mesa semantics are explained here.
Requirements:
Just like with locks, your solution must:
Comply to the existing interface.
Implement proper cv semantics as explained here.
Not use busy-waiting to wait on cv.
Again, you are allowed to use any functions available in OS161, including, of course, the lock that you implemented in the previous step.
We will test your code by running synchronization tests sy3 and sy4. Make sure your kernel passes them before you submit.
Step 5. Submit your assignment
Now follow the familiar steps for submitting your assignment.
Save your asst2-answers.txt and tell git about it.
git add ~/os161/src/submit/asst2/asst2-answers.txt
You also need to tell git about any other files you might have added, but for this assignment chances are you didn't need to add any others.
Now, commit the files you have modified.
git commit -a -m "Solution set for assignment 2".
Now push the changes to your master repository.
git push
Finally, tag your repository and push the tags:
git tag asst2-submit
git push --tags
If and ONLY if your GitHub URL is not the same as the one used for Assignment 1, submit to us the URL of your Git Repo.
Go to Canvas, navigate to Assignment 2 submission.
Get the SSH URL of your repo by going to GitHub, navigating to your repo, clicking on the green "Code" button at the top right. Make sure that the white box that appears says "Clone with SSH"; if it does not, click on the "Use SSH" link at the top right of the box.
Copy the Git URL that appears in the text box within the pop-up box. It will look something like: git@github.com:YourUserName/os161.git
Paste the Git URL into the submission box, and Submit!
Congratulations! You are done with Assignment 2!
For each question:
0 - absent
1 - partial answer
2 - complete good answer
We will run tests sy2, sy3 and sy4 from the OS161 kernel test menu. We award points as follows:
0 - doesn't compile or run
2 - passes sy2
1 - passes sy3
1 - passes sy4
(Add points for each test passed)
0 - non-existent or incomprehensible
1 - kind-of sort-of
2 - basically ok
3 - dholland kind code
This document describes the principles of writing good C code. Please read it and follow the guidelines to obtain high code-quality marks.
Basically, we give 3 points if we see the code at the same level as in the base OS161: well documented, but not excessively so. Consistent formatting, reasonable and readable variable naming conventions. We can easily read the code and understand what it does.
We give 1 point if the code is a mess, we don’t understand what it’s doing, seems like a bunch of copy-paste, there is lots of commented-out code.
We give 2 for something in-between.
The teaching staff takes care to calibrate and discuss code quality marks to make sure that all students are evaluate consistently and fairly.
We compute the points for the tests and for the implementation (out of maximum 7) and multiply that by 15. Then add the code reading points to it.
So the maximum is 105+20=125 points. Code reading accounts for roughly 16% out of the total.