Assignments‎ > ‎

Assignment 3

In this assignment you will solve a synchronization problem using the synchronization primitives in OS161, two of which you have implemented in the previous assignment. You will also learn about having multiple remotes configured for your git cone, and about branching and merging with git. 

Step 1. Prepare

Make sure you have a working implementations of locks and condition variables

Before you begin working on this assignment, you must have a working implementation of the synchronization primitives that you completed in Assignment 2. If your implementation is not working, you are welcome to use the solution code that we distributed to you separately. It is entirely up to you how you want to integrate the solution code into your tree. One option is to simply copy over the affected files. There is probably only two of them at this point: synch.h and sync.c. Another option is to use the git reset command to discard your commits and apply the patch to your tree, then commit and push the changes to git. Regardless of what you decide to do, make sure that your working tree compiles, runs and passes all the synchronization tests in the kernel menu (sy2, sy3 and sy4). If you need help, talk to your TAs during the lab session.

Pull some new code required for this assignment

We have created stubs and driver code for the synchronization problem you will be solving in this assignment. Follow these steps to integrate the code into your repository.  

First, you need to add another remote to your git clone. The new remote is for the git repository set up by your instructor to share with you certain bits of the OS161 codebase. It is the same repository that you used to create your original master repository a couple of weeks ago. Go into the directory where you have the clone of your master repo (probably ~/os161/src) and type the following:

git remote add instructor

Next, examine the remotes your repository knows about by typing:
git remote -v

You will see the output that looks something like this:

instructor (fetch)
instructor (push)
origin (fetch)
origin (push)

As you can see, the new remote was added under the name "instructor". There is nothing magic about the name "instructor". It is simply the name we chose to use; you could give it any other name you wish. Now, if you want to fetch from that repository, you will refer to it by its name: 'instructor', in this case. (As a side note, if you use git commands without providing the name of the remote, git automatically defaults to the name "origin", which is the name assigned to your own master repository). 

Now, fetch data from the new remote:

git fetch instructor

You will see that this command resulted in fetching of the two branches: master and synchprobs. Next, you need to integrate the code from synchprobs into your current tree. You will do this by merging the branch instructor/synchprobs into your master branch. (More information on git merging can be found here.)

git merge instructor/synchprobs

At this point, git will probably complain about merge conflicts. Follow this tutorial to resolve them before proceeding. 

If you now examine your source tree, you will see that there is a couple of new files that have been added, such as kern/conf/SYNCHPROBS and kern/synchprobs/airballoon.c. The first one is the configuration file that you will use for your assignment. The second one is the stub code for the synchronization problem you will solve. Make sure these files were successfully added to your source tree.

Now, push that new code into your master repository and tag your tree to indicate that you are beginning to work on Assignment 3:

git push
git tag asst3-start
git push --tags

Step 2. Understand the problem

Here is the synchronization problem you will have to solve. This is a well-known and a very serious known as AirBalloon. 

After a war erupts in their kingdom, Princess Marigold must help Prince Dandelion (her younger brother) escape from danger. Marigold places Dandelion in a hot air balloon, which is connected to the ground by NROPES ropes -- each rope is connected to a hook on the balloon as well as a stake in the ground. Marigold and Dandelion must work together to sever all of these ropes so that Dandelion can escape. Marigold unties the ropes from the ground stakes while Dandelion unhooks the ropes from the balloon. To free a rope it must be either severed from the ground or unhooked from the balloon: not both.

Unfortunately, one of Princess Marigold and Prince Dandelion's enemies, Lord FlowerKiller, is also at work. FlowerKiller is rearranging the ropes to thwart Princess Marigold and Prince Dandelion. He will randomly unhook a rope from one stake and move it to another stake. This leads to chaos!

Without Lord FlowerKiller's dastardly, behavior, there would be a simple 1:1 correspondence between balloon_hooks and ground_stakes (each hook in balloon_hooks has exactly one corresponding entry in ground_stakes, and each stake in ground_stakes has exactly one corresponding entry in balloon_hooks). However, while Lord FlowerKiller is around, this perfect 1:1 correspondence may not exist.

As Marigold and Dandelion cut ropes, they must delete mappings, so that they remove all the ropes as efficiently as possible (that is, once Marigold has severed a rope, she wants to communicate that information to Dandelion, so that he can work on severing different ropes). Each character is represented by a thread. Dandelion selects ropes to sever by generating a random balloon hook index, and Marigold selects ropes by generating a random ground stake index.

Lord FlowerKiller is on the ground, so like Marigold, he selects ropes by their ground stake index.

Consider this example:
Marigold randomly selects the rope attached to stake 7 to sever. She consults the mapping for the corresponding rope, sees that it is still mapped, and sees that the other end of the rope attaches to balloon hook 11. To cut the rope, she must free the mappings in both stake 7 and balloon hook 11. Imagine that Dandelion randomly selects balloon hook index 11 to delete. He determines that it is still mapped, finds that the corresponding ground stake index is 7. He will want to free the mappings in balloon hook 11 and ground stake 7. It's important that Dandelion and Marigold don't get in each other's way. What data structures might you use to avoid a deadlock in this situation? What locking protocol? (We do not assume that you will use data structures implied in the given example!) Worse yet, Lord FlowerKiller might be wreaking havoc with the same ropes. For example, imagine that he decides to swap ground stake 7 with ground stake 4 at the same time. Now, all of a sudden, balloon hook 11 is no longer associated with ground stake 7 but with ground stake 4.

Without proper synchronization and proper choice of data structures, Marigold and Dandelion can encounter:
  • a race condition, where multiple threads attempt to sever the same rope at the same time (e.g., Marigold and Dandelion threads attempt to sever the same rope).
  • a deadlock, where two threads select the same rope, but accessing it from different directions (e.g., Dandelion gets at the rope from balloon hook 11 while Marigold gets at the rope from ground stake 7).
In addition to our character threads, there is also a Balloon thread that does not do much. It gets started in the beginning of the program, at the same time as the other threads, and just sits there and waits until all the ropes have been severed. Then it announces that Prince Dandelion escaped and exits. 

Side note: You may be wondering why you have to solve a synchronization problem that seems to be completely unrelated to the code in the OS kernel. Here is why. As you will realize in the future programming assignments, which all directly involve programming kernel services, proper synchronization among threads is essential. You will not get far if you are unable to properly synchronize the code in the scheduler, virtual memory system and the file system. This exercise lets you practice concurrent programming and the use of synchronization primitives in a less challenging environment. This exercise will prepare you for more challenging exercises that follow. 

Step 3. Understand the requirements

Your solution must satisfy these conditions:
  • Avoid deadlocks and race conditions
  • Stick to the API provided in the driver code. You may write any other code you want, but do not change or go around the code already provided to you. If unsure, as your TA!
  • You may use semaphores, locks and condition variables available in OS161, but do not use spinlocks, wchans, or atomic primitives directly, and don't turn on/off the interrupts. 
  • Permit Marigold, Dandelion and Lord FlowerKiller threads to operate concurrently (no "big lock" solutions)
  • The Balloon thread exits after all ropes have been severed
  • The Main thread (the one that starts all other threads) exits after all threads are done.
  • You must deallocate all the memory allocated by your code before all threads exit. If you don't, there will be a memory leak! We will run your program multiple times to make sure your kernel does not leak.
To grade your code, we may both read it and use an automated script to check the correctness of the output. Please read this section very carefully to understand what your code should print. Be sure to follow these rules. Otherwise our script may report your solution as incorrect even if it is correct internally. 
  • Every time Marigold severs the rope, the Marigold thread prints: "Marigold severed rope N from stake K", where N is the index of the severed rope, which can range from 0 to NROPES - 1, and K is the index of the stake to which the rope was attached. K also ranges from 0 to NROPES-1. Be sure to print the statement exactly as shown, with no extra characters. The print statement must appear on its own line. 
  • Every time Dandelion severs the rope, the Dandelion thread prints: "Dandelion severed rope N", where N is the index of the severed rope, which can range from 0 to NROPES - 1. Be sure to print the statement exactly as shown, with no extra characters. The print statement must appear on its own line. 
  • Lord FlowerKiller prints the following statement every time he switches a rope: "Lord FlowerKiller switched rope N from stake K to stake P". N, K and P are corresponding rope and stake indices. 
  • There must be a print statement for every rope indicating that it was severed by either Dandelion or Marigold.
  • Each rope must be severed exactly one: only one "severed" print statement for each rope. 
  • Marigold's print statements must indicate that she is severing the ropes from correct stakes. For example, if there is a print statement from Lord FlowerKiller saying "Lord FlowerKiller switched rope 4 from stake 4 to stake 2", then Marigold's statement about severing rope 2 must say: "Marigold severed rope 4 from stake 2". (Dandelion's print statements do not inform us about the stake to which the rope he severed was attached, because from the height of the balloon he does not necessarily see the ground stakes.)
  • When all ropes have been severed (after the "severed" print statements for all NROPES ropes were displayed), the Balloon thread must print "Balloon freed and Prince Dandelion escapes!" and exit. 
  • Each thread, except the main one, must print the "thread starting" message just as it begins running. I.e.:
    • "Dandelion thread starting"
    • "Marigold thread starting"
    • "Lord FlowerKiller thread starting"
    • "Balloon thread starting"
  • Each thread, including the main one, must print the "thread done" message just before it exits. I.e.:
    • "Dandelion thread done"
    • "Marigold thread done"
    • "Lord FlowerKiller thread done"
    • "Balloon thread done"
    • "Main thread done"
  • The main thread must print only after all other threads have printed their departing statements. That is, the "Main thread done" statement must be the last one to appear before your kernel returns to the main menu. 
  • The print statements must be atomic: characters from one print statement must not interleave with another.
  • The print statements from different actors must interleave: for instance you can't have all Dandelion print statements appear together first, and then all Marigold statements appear together.  You will accomplish it by using fine-grained locks (no one big lock) and by calling thread_yield() every time after Dandelion or Marigold sever the rope or after Lord FlowerKiller switches the ropes.

Step 5. Plan your time 

You will be given partial credit if you implement the solution to the problem assuming that there is no Lord FlowerKiller and no Balloon threads (just don't start the corresponding threads). So if you are struggling, complete the solution involving Marigold and Dandelion only first. You will be given more points if you add the Balloon thread and even more points if you add the Lord FlowerKiller thread.

Step 6. Write, test and debug the code

Put all your code into kern/synchprobs/airballoon.c. To make sure that the new files get compiled, configure the kernel as shown below, and don't forget to bmake depend:

cd kern/conf
cd ../compile/SYNCHPROBS
bmake depend
bmake install

Test your code by invoking sp1 from the kernel menu. And don't forget what you learned about debugging with gdb in Assignment 1! Also, check that your sys161.conf file uses at least four CPUs. We will test your code with four CPUs!

Debugging tips:
  1. Get one type of thread working first, e.g., Marigold or Dandelion. Make sure it does not deadlock with itself and otherwise works as you expect. Then add other thread types. 
  2. Deadlocks are easier to debug than race conditions. If you are struggling, put one big lock around the critical sections that are causing you trouble. Make sure your code is working. Then gradually reduce the size of the critical section, making your big lock cover a smaller and smaller area of the code, until your code breaks. This way you will narrow down the few lines of code where the error is occurring. 
  3. If you encounter assertions in the VM system (e.g., in the kmalloc.c file), chances are you are freeing a pointer that you did not allocate or are doing something else funky with the memory. If your kernel panics on a TLB fault, you are probably accessing a pointer that you did not allocate or a null pointer. 

Step 7. Submit the assignment

Submit the assignment as usual:

git commit -a -m "Solution to Assignment 3"
git push
git tag asst3-submit
git push --tags

Congratulations! You are done with Assignment 3.