ASST1: Synchronization

After completing ASST1 you should:

ASST1 is your first chance to write real kernel code. Here are the guidelines for how to work with other students and work with your partner (if you have one):

Note that commenting, while potentially useful, does not make up for poor coding conventions. In many cases, well-structured code with good choices of variables and function names needs comments only in cases where something unusual must be pointed out.

For example, try to determine what the following (intentionally obfuscated) code on the left does. The click on the right side for the much better solution. Note that with appropriately named variables no commentary is needed for this very familiar piece of code.

Here are some general tips for writing better code:

You and your partner will probably find it useful to agree on a coding style. For instance, you might want to agree on how variables and functions will be named (my_function, myFunction, MyFunction, mYfUnCtIoN, or ymayUnctionFay) since your code will have to interoperate and be jointly readable. Note that OS/161 uses the my_function convention, so you may want to too.

When you boot OS/161 you should see options to run various 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 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—​or tt1 at the kernel menu or on the 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. It’s a good idea to familiarize yourself with the other thread tests as well.

One of the frustrations of debugging concurrent programs is that timing effects will cause them them to do something different each time. The end result should not be different—​that would be a race condition. But the ordering of threads and how they are scheduled may change. Our test drivers in the kern/test directory will frequently have threads spin or yield unpredictably when starting tests to create more randomness. However, for the purposes of testing you may want to create more determinism.

The random number generator used by OS/161 is seeded by the random device provided by System/161. This means that you can reproduce a specific execution sequence by using a fixed seed for the random device. You can pass an explicit seed into random device by editing the random line in your sys161.conf file. This may be help you create more reproducible behavior, at least when you are running the exact same series of tests.

While these code reading questions are ungraded, it is strongly recommended that you complete them with you partner.

Implement locks for OS/161. The interface for the lock structure is defined in kern/include/synch.h. Stub code is provided in kern/threads/synch.c. When you are done you should repeatedly pass the provided lt{1,2,3} lock tests.

Note that you will not be able to run any of these tests an unlimited number of times. Due to limitations in the current virtual memory system used by your kernel, appropriately called dumbvm, your kernel is leaking a lot of memory. However, your synchronization primitives themselves should not leak memory, and you can inspect the kernel heap stats to ensure that they do not. (We will.)

You may wonder why, if the kernel is leaking memory, the kernel heap stats don’t change between runs of sy1, for example, indicating that the semaphore implementation allocates and frees memory properly. The reason is that the kernel malloc implementation we have provided is not broken, and it will correctly allocate, free and reallocate small items inside of the memory made available to it by the kernel. What does leak are larger allocations like, for example, the 4K thread kernel stacks, and it is these large items that eventually cause the kernel to run out of memory and panic. Look at kern/arch/mips/vm/dumbvm.c for more details about what’s broken and why.

Implement condition variables with Mesa—​or non-blocking—​semantics for OS/161. The interface for the condition variable structure is also defined in synch.h and stub code is provided in synch.c.

We have not discussed the differences between condition variable semantics. Two different varieties exist: Hoare, or blocking, and Mesa, or non-blocking. The difference is in how cv_signal is handled:

Please implement Mesa semantics. When you are done you should repeatedly pass the provided cvt{1,2,3,4} condition variable tests.

Implement reader-writer locks for OS/161. A reader-writer lock is a lock that threads can acquire in one of two ways: read mode or write mode. Read mode does not conflict with read mode, but read mode conflicts with write mode and write mode conflicts with write mode. The result is that many threads can acquire the lock in read mode, or one thread can acquire the lock in write mode.

Your solution must also ensure that no thread waits to acquire the lock indefinitely, called starvation. Your implementation must solve many readers, one writer problem and ensure that no writers are starved even in the presence of many readers. Build something you will be comfortable using later. Implement your interface in synch.h and your code in synch.c, conforming to the interface that we have provided.

Unlike locks and condition variables, where we have provided you with a test suite, we are leaving it to you to develop a test that exercises your reader-writer locks. You will want to edit kern/main/menu.c to allow yourself to run your test as rwt1 from the kernel menu or command line. We have our own reader-writer test that we will use to test and grade your implementation.

Does this depart from our normal practice of providing you with the tools necessary to evaluate your assignment? Yes. And for a very good reason: writing tests is a critical development practice. You will write a lot of OS/161 code this semester, and particularly for ASST2 and ASST3 our tests are designed to tell if everything is working at a very high level. They are comprehensive tests, not unit tests, which target a particular piece of functionality. Writing good unit tests is extremely important to building large pieces of software—​some even claim that you should write the unit test first and then the implementation that passes it. So we are using this opportunity to force you to write a unit test in the hopes that you will continue this practice later.

You have been hired by the New England Aquarium’s research division to help find a way to increase the whale population. Because there are not enough of them, the whales are having synchronization problems in finding a mate. The trick is that in order to have children, three whales are needed; one male, one female, and one to play matchmaker—​literally, to push the other two whales together 2.

Your job is to write the three procedures male(), female(), and matchmaker(). Each whale is represented by a separate thread. A male whale calls male(), which waits until there is a waiting female and matchmaker; similarly, a female whale must wait until a male whale and matchmaker are present. Once all three are present, the magic happens and then all three return.

Each whale thread should call the appropriate {male,female,matchmaker}_start() function when it begins mating or matchmaking and the appropriate {male,female,matchmaker}_end() function when mating or matchmaking completes. These functions are part of the problem driver in synchprobs.c and you are welcome to change them, but again we will install and use our own versions for testing. We have provided stub code for the whale mating problem that you should use in whalemating.c.

The test driver in synchprobs.c forks thirty threads, and has ten of them invoke male(), ten of them invoke female(), and ten of them invoke matchmaker(). Stub routines, which do nothing but call the appropriate _start() and _end() functions, are provided for these three functions. Your job will be to re-implement these functions so that they solve the synchronization problem described above.

When you are finished, you should be able to examine the output from running sp1 and convince yourself that your solution satisfies the constraints outlined above.

If you drive in Buffalo you know two things very well:

In general, four-way stops are so tricky that they’ve even been known to flummox the otherwise unflummoxable Google self-driving car, which both knows and is programmed to follow the rules.

Given that robot cars are the future anyway, we can rethink the entire idea of a four-way stop. Let’s model the intersection as shown below. We consider the intersection as composed of four quadrants, numbered 0–3. Cars approach the intersection from one of four directions, also numbered 0–3. Note that we have numbered the quadrants so that a car approaching from direction X enters the intersection in quadrant X.

Given our model of the intersection, your job is to use synchronization primitives to implement a solution meeting the following requirements:

Here is a brief description of each of the five tests we will use to evaluate your reader-writer lock implementation:

Note that, unlike the lock tests, our reader-writer lock tests do not require you to track ownership: that is, if a thread tries to release a reader-writer lock that it does not hold that does not have to immediately panic. That said, it is possible and a good idea to do this both for readers and writers: take a look at kern/include/array.h for some help. We just don’t test it.