Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due

A2: Preemptive Threads

Concurrency - A Preemptive User-Level Threads Package

You will be working with your queue.c and thread.c code that you implemented in Tutorial 1 and Assignment 1. Please be aware that full completion of assignment 1 is required before starting assignment 2. If you did not receive full marks for assignment 1, please immediately see the course instructor or a TA to help you complete your assignment 1.

Background: Timer Signals

User-level code cannot use hardware timer interrupts directly. Instead, POSIX operating systemsprovide a software mechanism called signals that can be used to simulate "interrupts" at the userlevel. These signals interrupt your program and give you a chance to handle that interrupt. For example, when you hit Ctrl-C to kill a program, that causes the OS to send the SIGINT signal toyour program. Most programs don't handle this signal, so by default, the OS kills the process. However, if you wanted to save the state of your program before it was killed (e.g., a text editor couldsave any unsaved files), you can register a handler with the OS for SIGINT. Then, when the user hitsCtrl-C, the OS calls your handler; in your handler, you could write out the state of your program andthen exit.

More generally, signals are a form of asynchronous, inter-process communication mechanism. A signal can be sent from one process to another, or from a process to itself. We will use the latter method to have the process that invokes your user-level scheduler, i.e., your thread library functions, deliver timer signals to itself.

The operating system delivers a signal to a target (recipient) process by interrupting the normal flowof execution of the process. Execution can be interrupted after any instruction. If a process hasregistered a signal handler, that handler function is invoked when the signal is delivered. After thesignal handler finishes executing, the normal flow of execution of the process is resumed. Notice thesimilarities between signals and hardware interrupts.

Because signals can be delivered after any instruction, signal handling is prone to race conditions. For example, if you increment a counter (counter = counter + 1), either during normal execution or inyour signal handler code, the increment operation may not work correctly because it is not atomic.The signal may be delivered between the instructions implementing the increment operation. To avoidthis problem, you should disable signal delivery while the counter is being updated. Note that this is essentially the old OS strategy of disabling interrupts to protect critical sections on a uniprocessor.

Please read a short introduction to signals(http://en.wikipedia.org/wiki/Unix_signal) to understand how they work in more detail. Make sure to read the "Risks" section or else you may not be able to answer some questions below.

Now go over the code in the files interrupt.h and interrupt.c . (This is the same code we provide for Tutorial 5). You do not need to understand all the code, but it will be helpful to know how these functions should be used. We will use the terms "interrupts" and "signals" interchangeably below. 

void interrupt_init(bool verbose):

This function uninstalls the timer signal handler.

bool interrupt_set(bool enable):

Why does this function return the previous signal state? The reason is that it allows "nesting" calls to this function. The typical usage of this function is as follows:

The first call to interrupt_set disables signals. The second call restores the signal state to its previous state, i.e., the signal state before the first call to interrupt_set , rather than unconditionally enabling signals. This is useful because the caller of the function fn may be expecting signals to remain disabled after the function fn finishes executing. For example:

Notice how signal disabling and enabling are performed in "stack" order, so that the signal state remains disabled after fn returns.

bool interrupt_enabled():

To help you understand how this code works, you should work through Tutorial 5 (https:// q.utoronto.ca/courses/380124/assignments/1438310) .

Setup

Task 1: Preemptive Threading

5. Is the signal state enabled or disabled when the function in thread.c above is invoked? If the signal is enabled, could it cause problems? If the signal is disabled, what code will enable them? Hint: look for sa_mask in interrupt.c .

6. What does unintr_printf do? Why is it needed? Will you need other similar functions? Reread a short introduction to signals (http://en.wikipedia.org/wiki/Unix_signal) to find out.

A simple way to ensure mutual exclusion is to disable signals when you enter procedures of the thread library and restore the signal state when you leave.

Hint: think carefully about the invariants you want to maintain in your thread functions about when signals are enabled and when they are disabled. Make sure to use the interrupts_enabled function to check your assumptions.

It will be helpful to go over the manual pages (http://linux.die.net/man/2/setcontext) of the context save and restore calls again.

After you implement preemptive threading, you can test your code by running the test/preemptive program.

Task 2: Sleep and Wakeup

In real operating systems, similar mechanisms are used to suspend threads waiting for I/O operations with slow devices (e.g., disks, networks). Your implementation will ensure that threads waiting for conditions such as a mutex becoming available or a network packet arriving can be put to sleep and later awakened efficiently.

Tid thread_sleep(fifo_queue_t *queue): Suspends the calling thread and schedules another thread to run. The calling thread is placed in the specified wait queue and remains blocked until awakened.

Wakes up one or more threads from the specified wait queue, moving them to the ready queue. If all is 0, wake up a single thread in FIFO order. If all is 1, wake up all threads in the wait queue . Any other value of all will result in undefined behaviours.

All the thought that you put into ensuring that thread preemption works correctly previously will apply to these functions as well. In particular, these functions access shared data structures (which ones?), so be sure to enforce mutual exclusion.

So far, you only have to handle the case wherethread_kill is invoked on a runnable thread. 

For this assignment, if thread_kill is called on a sleeping thread, the thread must be immediately removed from its wait queue and transitioned to a runnable state. This ensures that the thread can again be scheduled, so that eventually, it would be able to properly exit.

Task 3: Waiting for Threads to Exit

The thread_wait function is summarized below:

For mutual exclusion, you will implement blocking (sleeping) locks. Your code should associate a wait  with the lock so that threads that need to acquire the lock can wait in this queue. In addition, you need a way to track the condition variables that are associated with this lock (see next section), so that we can detect premature freeing of the lock.

The API for the condition variable functions are described below: struct cv *cv_create(struct lock *lock): Create a condition variable and associate it with lock .

Suspend the calling thread on the condition variable cv . Be sure to check that the calling thread had acquired lock when this call is made. You will need to release the lock before waiting, and reacquire it before returning from this function. Return 0 on success. Otherwise, return the error code provided by

returns an error, the associated lock will no longer be held.

Wake up one thread that is waiting on the condition variable cv .

Wake up all threads that are waiting on the condition variable cv .

Hint: all five functions above access shared data structures (which ones?), so be sure to enforce mutual exclusion.

After you implement these functions, you can test your code by running the test/signal , test/ broadcast , and test/crash program.

Task 5: Deadlock Detection

Deadlock occurs when a set of threads are blocked indefinitely, waiting for resources held by each other. In your threading library, we would like to prevent threads from becoming permanently blocked by gracefully returning an error code ( THREAD_DEADLOCK ) when deadlock would have happened as a result of making an API call, i.e., thread_wait , lock_acquire , and cv_wait .

In this assignment, deadlock detection can be implemented by checking for cyclic dependencies in the wait queues. Specifically, when a thread attempts to sleep on a queue, you should verify whether doing so would create a circular wait condition.

Your first step should be to complete the implementation for these two functions, so that an owner can be associated with each queue object. Note that the two functions below work with void pointers. This is intentional so that you have the freedom to decide how an owner should be represented.

However, we also have an suggested approach for each function.

void * queue_get_owner(fifo_queue_t * queue):

Return the owner thread of a given queue. You are suggested to implement this by returning a pointer to a TCB, i.e., the actual return type should be

struct thread *.

Set the owner thread of a given queue. You are suggested to implement this by passing in a double pointer to a TCB. In other word, you should pass in the address of a pointer to a TCB, e.g., struct thread * owner = ...; queue_set_owner(q, &owner);

You will need to update struct _fifo_queue to complete the above functions.

Next, you need to find locations in your code to insert queue_set_owner , so that each wait queue has an associated owner. It is possible that some wait queues will not always have an owner, for example, a lock only has an owner when it is held by a thread. Otherwise, it has no owner.

Think time: who would be the owner of a condition variable? Does a condition variable always have an owner?

Last, add deadlock detection logic to thread_sleep(queue) , so that it returns THREAD_DEADLOCK if circular waiting is detected. The basic approach is to start from queue , and get its owner using queue_get_owner . If the owner exists, check whether it is blocked inside a queue, and get the owner of that queue, etc. Eventually, you will come across an owner thread that is either runnable, or it is the current thread. In the latter case, a deadlock will occur if we allow it to go to sleep.

Once you completed the above steps, check any functions that call thread_sleep to make sure you propagate the error codes correctly, e.g., so that thread_wait is also able to return THREAD_DEADLOCK . Finally, you can test your code by running the test/deadlock program.

Hints and Advice

You are encouraged to reuse your own code that you might have developed in the first assignment or in previous courses for common data structures and operations such as queues, sorting, etc. Make sure to document the sources of anything you did not write specifically for this course.

You may not use code that subsumes the heart of this project, e.g., you should not base your solution on wrappers of or code taken from the POSIX thread library. If in doubt, ask.

This assignment does not require you to write a lot of code, but it does demand careful thought about the code you write. Before diving into coding, take the time to plan and fully understand what you need to implement. If you think through the problem thoroughly from start to finish, this assignment will not be too difficult. However, if you try to hack your way through without a clear plan, you may end up spending many frustrating hours debugging and reworking your solution. The main challenge of this assignment lies in conceptualizing the solution. Once you overcome that hurdle, you’ll likely find the implementation itself to be surprisingly straightforward!

All the general hints and advice (https://q.utoronto.ca/courses/380124/pages/a2-faq) from Assignment 1 apply here as well.

Frequently Asked Questions

Testing Your Code

You can test your entire code by running the programs in the test folder. One week before the duedate, the MarkUs autotester will become available. There will be no hidden test cases and you will receive exactly what you see after running the public test for the assignment.

Fortest/crash and test/deadlock, each test case forks a new process so that failing an earlier testdoes not result in failing the entire test suite. However, this introduces complexity when it comes todebugging a specific test case, since GDB is not able to debug multiple processes, e.g., you can't debug both the parent and child processes at the same time. Hence, these two tests also take a command line argument -- the test number. When you specify a test number, only that test case is run, and no forking happens, so that you can debug it without issue. For example:

Using Git and Submitting Your Assignment

You should only modify the following files in this assignment.

thread.c thread.h queue.c

Note that you are allowed to make changes to other files for your own testing, however, the only fileswe will use during marking are the ones listed above.

You can find the files you have modified by running the git status command.

You can commit your modified files to your local repository as follows:

git add fcfs.c queue.c thread.c thread.h

Note that fcfs.c does not need to be modified for A2, but you do need to copy it over from your A1 repository and commit/push it.

We suggest committing your changes frequently by rerunning the commands above (with differentmeaningful messages to the commit command), so that you can go back to see the changes youhave made over time, if needed.

Once you have tested your code, and committed it (check that by running git status ), you can push the assignment to MarkUs.

We suggest pushing your code back to MarkUs frequently, as you complete each part of the assignment.

Grace tokens are used automatically based on the time the last push to MarkUs within the grace period.