OS161 Assignment 3

Assignment3

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 clone, and about branching and merging with git.

Step 1. Prepare

Pull some new code required for this assignment:

git remote add instructor http://dev.ece.ubc.ca/git/OS161
git fetch instructor
git merge --allow-unrelated-histories instructor/synchprobs

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

Now, push the 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

Why we need to solve this synchronization problem?

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.

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 enemy, Lord FlowerKiller, is also at work. FlowerKiller is rearranging the ropes to thwart Princess Marigold and Prince Dandelion. He will randomly switch ropes attached to two different stakes. 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 corresponds to exactly one stake, and each stake corresponds to exactly one hoop). However, while Lord FlowerKiller may break this symmetry. Say, Lord FlowerKiller decides to switch ropes connected to Stake 1 and Stake 5. Before the switch, the rope connected to Stake 1 on the ground is also connected to Hook 1 on the balloon, and the rope connected to Stake 5 on the ground is also connected to Hook 5 on the balloon. After the switch, however, one rope is connected to Stake 1 on the ground and to Hook 5 on the balloon, and vice versa.

As Marigold and Dandelion cut ropes, they must delete mappings, so that they remove all the ropes as efficiently as possible. 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.

Marigold and Dandelion must work as efficiently as possible, so one should not try to disconnect a rope that has already been disconnected. For example, if Dandelion already unhooked a rope, Marigold should see that the rope is hanging loose and not try to unook it from the stake. Similarly, Dandelion should not try to unook a rope that Marigold disconnected on the ground.

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

Due to recent advances in genetic technology, there is another unfortunate circumstance: Lord FlowerKiller figured out how to clone himself, so now there are N_LORD_FLOWERKILLER copies of of him at work (each is a separate thread)!

problems to avoid in your implementation:

Marigold randomly selects Stake 7, sees that the rope is still attached. She marks the rope as severed. Suppose that the hook corresponding to the severed rope is Hook 11. If Dandelion now randomly selects Hook 11, he must see that the rope is severed and not try to sever it again. What data structures might you use to avoid a race condition in this situation? What would you need to lock to make sure that Marigold and Dandelion don't sever the same rope twice?

Worse yet, Lord FlowerKiller might be wreaking havoc with the same ropes. For example, imagine that he decides to swap the rope attached to Stake 7 with the rope attached to Stake 4, and vice versa. How do you make sure to avoid race conditions that this situation creates?

Now consider how Lord FlowerKillers might step on each other toes. Suppose Lord FlowerKiller1 grabs Stake1 and Stake4 to swap the corresponding ropes, and Lord FlowerKiller2 grabs Stake4 and Stake1. How might this cause deadlock? What would you do to prevent it?

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.

Step 3. Understand the requirements

Your solution must satisfy these conditions:

• Avoid deadlocks and race conditions
• 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.
• Marigold must access the ropes via stakes. She does not have access to hooks. Programmatically, this means that you need to have some kind of data structure representing stakes, which Marigold indexes. Marigold can update stakes and ropes (that are connected to stakes), but she may not update hooks. Similarly, LordFlowerkillers may access ropes via stakes only. Dandelion, on the other hand, may access ropes only via hooks. He cannot see or access stakes.

What your code should print?

• 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. If he switches two ropes, which is exactly what he will do every time, he must print two statements: one for each rope.

• 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.

• To randomly select a stake to unhook (or two stakes to swap) or a hook, use random() function in OS161.

• Every time a character succeeded unhooking one rope or switching one pair of ropes, the corresponding thread must yield (call thread_yield()).

• 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 print the stake index corresponding to the severed rope, because Dandelion cannot access 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 4. Write, test and debug the code

configure the kernel:

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

Test your code by invoking sp1 from the kernel menu.

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.
4. If you need to figure out where a thread is stuck, print the address of the thread struct in your code: kprintf("%p\n", curthread);. We will call the pointer that is printed threadaddr. Then you can print the contents of the thread struct in GDB: print *(struct thread) <threadaddr>. You can also figure out which thread holds the lock by printing the lock struct in gdb, for example: print stake->lk_stake;. If you are keeping track of the lock holder inside the lock structure, that field will show the threadaddr or the holder thread.
5. If your code is stuck in a deadlock, you should be able to attach to it with the debugger using the os161-gdb command and following the instructions linked in A1. This should work even if you did not launch your sys161 with -w flag.

My Solution

Use the synchronization primitives(lock, CV, semaphore) implemented in A2 to solve this synchronization problem. Specifically, I choose to use a lock for each object in the problem(stake, rope, hook) and use condition variables for some threads to wait for other threads to exit.

Why and How I represent each object(stake, rope, hook) in the problem?

Object-oriented programming makes this problem easier. Plus, there needs to be some kind of separation between stakes and hooks as they can only operate on their own side of the rope. Use a lock for each object to avoid big lock.

Also, we need to protect shared global variables if they exist.

/* Data structures for rope mappings */

/* rope structure */
typedef struct
{
    bool is_cut;
    int rope_number;
    struct lock *lock;
} rope;

/* stake structure, containing the connected rope */
typedef struct
{
    rope *connected_rope;
    struct lock *lock;
} stake;

/* hook structure, containing the connected rope */
typedef struct
{
    rope *connected_rope;
} hook;

/* represent each rope, stake and hook */
static rope ropes[NROPES];
static stake stakes[NROPES];
static hook hooks[NROPES];

/* Synchronization primitives */
// protect global variable ropes_left
static struct lock *ropes_left_lock; 

How to have some threads to wait for other threads to exit?

Specifically, I use a condition variable for balloon thread waiting for all dandelion, marigold and flowerkiller threads to exit. I use another cv for main thread waiting for balloon thread to exit.

/* CV for balloon thread waiting for all dandelion, marigold and flowerkiller threads done */
static struct cv *all_threads_done_cv;
static struct lock *threads_exit_lock;
static int threads_exited = 0;

/* CV for main thread waiting for balloon thread finished. */
static struct cv *balloon_thread_done_cv;
static struct lock *balloon_exit_lock;
static bool balloon_finished = false;

Let's go into the core of the problem. What is my design and locking protocols that must be maintained? How do all threads know when they are done?

Use three structures: rope, stake and hook.

Each rope and stake has its own lock. Actually we don't need a lock for hooks as they always maintain 1:1 correspondence to the ropes. Dandelion accesses each rope only from its hook, required to lock the rope before severing it. Marigold should lock the stake first before accessing the rope from its stake, and lock the rope before severing it. Flowerkiller should lock both stakes first before accessing the ropes from them, and lock the corresponding ropes(in particular order) before swaping them.

Dandelion and marigold threads should exit when global variable ropes_left = 0. Flowerkiller threads should exit when global variable ropes_left < 2. Balloon thread should wait for all dandelion, marigold and flowerkillers threads to exit before exiting. Airballoon(main) thread should wait for balloon thread to exit before exiting.

// Threads

/* Dandelion severs ropes from hooks. */
static void dandelion(void *p, unsigned long arg)
{
	(void)p;
	(void)arg;

	kprintf("Dandelion thread starting\n");

	/* Implement this function */

	/* Loop until all the ropes have been severed. */
	while (true)
	{
		/* Check if all the ropes are severed. If so, break and exit. */
		lock_acquire(ropes_left_lock);
		if (ropes_left == 0)
		{
			lock_release(ropes_left_lock);
			break;
		}
		lock_release(ropes_left_lock);

		/* Randomly select a hook and get its connected rope. */
		int hook = random() % NROPES;
		rope *current_rope = hooks[hook].connected_rope;

		/* If the rope has already been severed by himself, abort. */
		if (current_rope == NULL)
		{
			continue;
		}

		/* lock the rope before trying to sever it */
		lock_acquire(current_rope->lock);
		/* If the rope is not severed, sever it from the hook. */
		if (!current_rope->is_cut)
		{
			current_rope->is_cut = true;
			hooks[hook].connected_rope = NULL;

			lock_acquire(ropes_left_lock);
			ropes_left--;
			kprintf("Dandelion severed rope %d\n", hook);
			lock_release(ropes_left_lock);
		}
		lock_release(current_rope->lock);
		/* give up the cpu and switch to another thread. */
		thread_yield();
	}

	kprintf("Dandelion thread done\n");
	notify_thread_exit();
	thread_exit();
}

/* Marigold severs ropes from stakes. */
static void marigold(void *p, unsigned long arg)
{
	(void)p;
	(void)arg;

	kprintf("Marigold thread starting\n");

	/* Implement this function */

	/* Loop until all the ropes have been severed. */
	while (true)
	{
		/* Check if all the ropes are severed. If so, break and exit. */
		lock_acquire(ropes_left_lock);
		if (ropes_left == 0)
		{
			lock_release(ropes_left_lock);
			break;
		}
		lock_release(ropes_left_lock);

		/* Randomly select a stake and get its connected rope, protected by its lock. */
		int stake = random() % NROPES;
		lock_acquire(stakes[stake].lock);
		rope *current_rope = stakes[stake].connected_rope;

		/* If the rope has already been severed by herself, abort. */
		if (current_rope == NULL)
		{
			lock_release(stakes[stake].lock);
			continue;
		}

		/* lock the rope before trying to sever it */
		lock_acquire(current_rope->lock);
		/* If the rope is not severed, sever it from the stake. */
		if (!current_rope->is_cut)
		{
			current_rope->is_cut = true;
			stakes[stake].connected_rope = NULL;

			lock_acquire(ropes_left_lock);
			ropes_left--;
			kprintf("Marigold severed rope %d from stake %d\n", current_rope->rope_number, stake);
			lock_release(ropes_left_lock);
		}
		/* release the lock in reverse order, avoiding deadlock */
		lock_release(current_rope->lock);
		lock_release(stakes[stake].lock);
		/* give up the cpu and switch to another thread. */
		thread_yield();
	}

	kprintf("Marigold thread done\n");
	notify_thread_exit();
	thread_exit();
}

static void flowerkiller(void *p, unsigned long arg)
{
	(void)p;
	(void)arg;

	kprintf("Lord FlowerKiller thread starting\n");

	/* Implement this function */

	/* Loop until all the ropes have been severed. */
	while (true)
	{
		/* Check if there are at least two ropes left. If not, break and exit. */
		lock_acquire(ropes_left_lock);
		if (ropes_left < 2)
		{
			lock_release(ropes_left_lock);
			break;
		}
		lock_release(ropes_left_lock);

		/* Randomly select two different stakes to swap. */
		int stake1, stake2;
		do
		{
			stake1 = random() % NROPES;
			stake2 = random() % NROPES;
		} while (stake1 == stake2);

		/* get the smaller stake and bigger stake by their number */
		int first_stake = (stake1 < stake2) ? stake1 : stake2;
		int second_stake = (stake1 < stake2) ? stake2 : stake1;

		/* lock the smaller stake first, then lock the bigger stake, avoiding deadlock, before getting the connected ropes */
		lock_acquire(stakes[first_stake].lock);
		lock_acquire(stakes[second_stake].lock);
		rope *rope1 = stakes[stake1].connected_rope;
		rope *rope2 = stakes[stake2].connected_rope;

		/* If either rope has already been severed from its stake, abort. */
		if (rope1 == NULL || rope2 == NULL)
		{
			lock_release(stakes[second_stake].lock);
			lock_release(stakes[first_stake].lock);
			continue;
		}
        
		/* get the smaller rope and bigger rope by their number */
		rope *first_rope = (rope1->rope_number < rope2->rope_number) ? rope1 : rope2;
		rope *second_rope = (rope1->rope_number < rope2->rope_number) ? rope2 : rope1;

        /* lock the smaller rope first, then lock the bigger rope, avoiding deadlock, before trying to swap them. */
		lock_acquire(first_rope->lock);
		lock_acquire(second_rope->lock);
		/* If neither rope is severed, swap them from their stakes */
		if (!rope1->is_cut && !rope2->is_cut)
		{
			stakes[stake1].connected_rope = rope2;
			stakes[stake2].connected_rope = rope1;

			kprintf("Lord FlowerKiller switched rope %d from stake %d to stake %d\n", rope1->rope_number, stake1, stake2);
			kprintf("Lord FlowerKiller switched rope %d from stake %d to stake %d\n", rope2->rope_number, stake2, stake1);
		}
		/* release the lock in reverse order, avoiding deadlock */
		lock_release(second_rope->lock);
		lock_release(first_rope->lock);
		lock_release(stakes[second_stake].lock);
		lock_release(stakes[first_stake].lock);
		/* give up the cpu and switch to another thread. */
		thread_yield();
	}

	kprintf("Lord FlowerKiller thread done\n");
	notify_thread_exit();
	thread_exit();
}

static void balloon(void *p, unsigned long arg)
{
	(void)p;
	(void)arg;

	kprintf("Balloon thread starting\n");

	/* Implement this function */

    /* wait until all dandelion, marigold and flowerkiller threads are done */
	lock_acquire(threads_exit_lock);
	while (threads_exited != N_LORD_FLOWERKILLER + 2)
	{
		cv_wait(all_threads_done_cv, threads_exit_lock);
	}
	lock_release(threads_exit_lock);

    /* print the messages */
	kprintf("Balloon freed and Prince Dandelion escapes!\n");
	kprintf("Balloon thread done\n");

	/* wake up the airballoon(main) thread */
	lock_acquire(balloon_exit_lock);
	balloon_finished = true;
	cv_signal(balloon_thread_done_cv, balloon_exit_lock);
	lock_release(balloon_exit_lock);

	/* then exit */
	thread_exit();
}

// Change this function as necessary
int airballoon(int nargs, char **args)
{
	int err = 0, i;

	(void)nargs;
	(void)args;
	(void)ropes_left;
    
    /* Initialize global variables. */
	main_thread_init();

    /* Initialize rope mappings and synchronization primitives. */
	initialize_mappings();
	initialize_synchronization();

	err = thread_fork("Marigold Thread",
					  NULL, marigold, NULL, 0);
	if (err)
		goto panic;

	err = thread_fork("Dandelion Thread",
					  NULL, dandelion, NULL, 0);
	if (err)
		goto panic;

	for (i = 0; i < N_LORD_FLOWERKILLER; i++)
	{
		err = thread_fork("Lord FlowerKiller Thread",
						  NULL, flowerkiller, NULL, 0);
		if (err)
			goto panic;
	}

	err = thread_fork("Air Balloon",
					  NULL, balloon, NULL, 0);
	if (err)
		goto panic;

	goto done;
panic:
	panic("airballoon: thread_fork failed: %s)\n",
		  strerror(err));

done:
    /* wait until balloon thread is done */
	wait_for_balloon();
	kprintf("Main thread done\n");
	cleanup_synchronization();
	
	return 0;
}

As shown in the code, I encapsulate some operations into helper functions in order to clarify the main logic.

// Helper functions

/* This function initializes the main thread global variables. */
static void main_thread_init() {
	ropes_left = NROPES;
	threads_exited = 0;
    balloon_finished = false;
}

/* Initialize rope mappings. */
static void initialize_mappings()
{
	for (int i = 0; i < NROPES; ++i)
	{
		ropes[i].is_cut = false;
		ropes[i].rope_number = i;
		ropes[i].lock = lock_create("rope lock");

		stakes[i].connected_rope = &ropes[i];
		stakes[i].lock = lock_create("stake lock");

		hooks[i].connected_rope = &ropes[i];
	}
}

/* Initialize sychronization primitives */
static void initialize_synchronization()
{
	ropes_left_lock = lock_create("ropes_left lock");
	all_threads_done_cv = cv_create("all threads done cv");
	threads_exit_lock = lock_create("threads exit lock");
	balloon_thread_done_cv = cv_create("balloon thread done cv");
	balloon_exit_lock = lock_create("balloon exit lock");
}

/* Clean up synchronization primitives */
static void cleanup_synchronization()
{
	lock_destroy(ropes_left_lock);
	cv_destroy(all_threads_done_cv);
	lock_destroy(threads_exit_lock);
	cv_destroy(balloon_thread_done_cv);
	lock_destroy(balloon_exit_lock);
	for (int i = 0; i < NROPES; ++i)
	{
		lock_destroy(ropes[i].lock);
		lock_destroy(stakes[i].lock);
	}
}

/*
 * Dandelion, marigold and all flowerkiller threads should call this right before exiting,
 * notifying their exit and waking up balloon thread when all of them have exited.
 */
static void notify_thread_exit()
{
	lock_acquire(threads_exit_lock);
	threads_exited++;
	if (threads_exited == N_LORD_FLOWERKILLER + 2)
	{
		cv_signal(all_threads_done_cv, threads_exit_lock);
	}
	lock_release(threads_exit_lock);
}

/* Airballoon(main) thread should call this before exiting, waiting for balloon thread to exit. */
static void wait_for_balloon()
{
	lock_acquire(balloon_exit_lock);
	while (!balloon_finished)
	{
		cv_wait(balloon_thread_done_cv, balloon_exit_lock);
	}
	lock_release(balloon_exit_lock);
}

Test sp1 passes!

We have finished Assignment3!😊