.
CPSC 213 – 2018 Winter Term 2 Exam Review: Threads
1 [1 marks] General thread questions
1a ThreadscanbeusedtomanagetheasynchronyinherentinI/O-deviceaccess(e.g.,readingfromdisk).Care-
fully explain how threads help.
1b CarefullydescribeinplainEnglishthesequenceofstepsauser-levelthreadsystemsuchasuthreadsfollowsto switch from one thread to another. Ensure that your answer explains the role of the ready queue and explains how the hardware switches from running one thread to the other.
1c Whatistheroleofthethreadscheduler?
It determines which of the ¡±runnable¡± threads should be currently running on a CPU.
1d Explainpriority-based,round-robinscheduling.
1e ExplainwhatelseisneededtoensurethatthreadsofequalprioritygetanequalshareoftheCPU?
It comes from two factors related to IO devices. The first is that IO operations are executed on the IO controller in parallel with the execution of the CPU ¡ª and they take millions of cycles ¡ª and so the CPU can and should do something constructive during the time an application waits for a response from the IO device. The second is that IO devices interrupt the processor at unpredictable times thus causing the CPU to jump from one synchronous thread of control to another repeatedly and non-deterministically. Threads help by encapsulating both of these issues behind an abstraction that looks a CPU executing a program that does no IO and in which there are no interrupts. Threads are stopped and restarted as necessary to wait for IO events and to handle interrupts.
For every pair of threads a and b, if only one of a and b can be running on a CPU, the thread with the highest priority is running. Among threads of equal priority, the thread that has been waiting the longest on the ready queue is the next thread to run on a CPU.
Preemption is needed to force threads that have been running to long to give up the CPU so that other threads of equal priority can run. This time limit is called the thread¡¯s scheduling quantum.
.
2 [16 marks] General synchronization questions and implementation
2a Explainthedifferencebetweenbusy-waitingandblocking.Giveoneadvantageofblocking.
2b Considerthefollowingprograminwhichincanddeccanrunconcurrently.
spinlock_t s; int c; void dec() {
int success = 0; while (success==0) {
while (c==0) {} spinlock_lock (s); if (c>0) {
c = c – 1;
success = 1;
}
spinlock_unlock (s);
Busy waiting occurs when the a thread waits for a lock to be free by actively polling its value, spinning in a loop repeated reading it until it see that it is available.
Blocking waiting occurs when a thread waits for a lock by sleeping so that other threads can use the CPU. It is then the responsibility of the thread that releases the lock to wakeup the waiting thread.
} }
void inc() { spinlock_lock (s);
c = c + 1; spinlock_unlock (s);
}
mutex_t mx;
cond_t notZero;
void dec() { lock (mx);
while (c == 0)
wait (notZero)
c–;
unlock (mx);
}
void inc() { lock (mx);
c++;
signal (notZero);
unlock (mx);
}
Re-implement the program to eliminate all busy waiting using monitors and condition variables. You may make the changes in place above or re-write some or all of the code below.
2
.
2c Assumethatmonitorsareimplementedinsuchawaythatathreadinsideofamonitorispermittedtore-enter that monitor repeatedly without blocking (e.g., when bar calls zot, which calls foo, foo is permitted to enter monitor x). Indicate whether the following procedures could cause deadlock in multi-threaded program that contained them (and other procedures as well). Explain why or why not. If they could, say whether you could eliminate this deadlock by only adding additional monitors or additional monitor enter or exits (you may not remove monitors). If so, show how.
void foo () { monitor_enter (x); monitor_exit (x);
}
void bar () {
monitor_enter (x);
zot ();
monitor_exit (x);
}
void zot () {
monitor_enter (y);
foo ();
monitor_exit (y);
}
Yes it can deadlock, because if, for example, one thread calls bar and another calls zot, the first thread could be holding x while waiting for y and the other could be holding y while waiting for x, and thus the threads would be deadlocked. You can fix this by ensuring that threads always acquire locks in the same order. For example, to ensure that lock x is always acquired before lock y, add monitor_enter(x) to the beginning of zot and monitor_exit(x) to the end.
Note that in this version of the course the term monitor enter and monitor exit where used in place of lock and unlock.
3
.
3 [1 marks] Complete the code using mutexes and condition variables so that the output is always ¡±doe re me¡±.
//TODO:
uthread_mutex_t mx;
uthread_cond_t first, second, third;
int ready = 0;
void* doe() {
uthread_mutex_lock(mutex);
while (ready < 2)
uthread_cond_wait(first);
printf("doe ");
uthread_cond_signal(second);
uthread_mutex_unlock(mutex);
return NULL;
}
void* re() {
uthread_mutex_lock(mutex);
ready++;
uthread_cond_signal(first);
uthread_cond_wait(second);
printf("re ");
uthread_cond_signal(third);
uthread_mutex_unlock(mutex);
return NULL;
}
void* me() {
uthread_mutex_lock(mutex);
ready++;
uthread_cond_signal(first);
uthread_cond_wait(third);
printtf("me\n"); uthread_mutex_unlock(mutex);
return NULL;
}
int main (int argc, char** argv) {
uthread_init (3);
mx = uthread_mutex_create();
first = uthread_cond_create(mx);
second = uthread_cond_create(mx);
third = uthread_cond_create(mx);
uthread_t t1, t2, t3;
t1 = uthread_create (doe,NULL);
t2 = uthread_create (re,NULL);
t3 = uthread_create (me,NULL);
uthread_join(t1,0);
uthread_join(t2,0);
uthread_join(t3,0);
}
4
.
4 [1 marks] Complete the code using semaphores so that the output is always ¡±doe re me¡±.
//TODO:
uthread_sem_t lockab, lockbc;
void* doe() {
printf("doe ");
uthread_sem_signal(lockab);
return NULL;
}
void* re() {
uthread_sem_wait(lockab);
printf("re...");
uthread_sem_signal(lockbc);
return NULL;
}
void* me() {
uthread_sem_wait(lockbc);
printtf("me\n");
return NULL;
}
int main (int argc, char** argv) {
uthread_init (3);
lockab = uthread_sem_create (0);
lockbc = uthread_sem_create (0);
uthread_t t1, t2, t3;
t1 = uthread_create (doe,NULL);
t2 = uthread_create (re,NULL);
t3 = uthread_create (me,NULL);
uthread_join(t1,0);
uthread_join(t2,0);
uthread_join(t3,0);
}
5
.
5 [1 marks] In a science lab, people wanting to visit need to acquire three items: goggles, a coat, and gloves. The system designed to manage these items contains the following code. Note that some parts of the code that are not useful for this question have been removed. You may assume that all mutexes and all arrays have been properly initialized.
uthread_mutex_t goggles_lock;
uthread_mutex_t coat_lock;
uthread_mutex_t gloves_lock;
int goggles[NUM_ITEMS], coats[NUM_ITEMS], gloves[NUM_ITEMS];
int num_goggles = NUM_ITEMS, num_coats = NUM_ITEMS;
int num_gloves = NUM_ITEMS;
int get_goggles() {
int rval = -1;
while (rval == -1) {
uthread_mutex_lock(goggles_lock);
if (num_goggles > 0) {
rval = goggles[–num_goggles];
}
uthread_mutex_unlock(goggles_lock);
}
return rval;
}
void return_goggles(int num) {
uthread_mutex_lock(goggles_lock);
goggles[num_goggles++] = num;
uthread_mutex_unlock(goggles_lock);
}
Functions get coat() and get gloves() are implemented like the get goggles() function. Functions return coat() and return gloves() are implemented similarly to function return goggles(). A visitor will typically acquire all three items (coat, gloves, goggles), perform any relevant tasks in the lab, and then return all three items when they are finished.
5a Whyistheimplementationshownaboveinefficient?
Because it achieves its purpose using busy waiting, which wastes CPU time without making any progress.
6
.
5b Rewrite functions get goggles and return goggles to use condition variables in order to avoid the inefficiency mentioned in the previous question. You may assume that any mutex condition variable you use in your solution is properly initialized in the main function.
int get_goggles() {
int rval;
uthread_mutex_lock(goggles_lock);
while (num_googles == 0)
uthread_cond_wait(goggles_cond);
rval = goggles[–num_goggles];
uthread_mutex_unlock(goggles_lock);
return rval;
}
void return_goggles(int num) {
uthread_mutex_lock(goggles_lock);
goggles[num_goggles++] = num;
uthread_cond_signal(goggles_cond);
uthread_mutex_unlock(goggles_lock);
}
5c Rewritefunctionsget\_gogglesandreturn\_gogglestousesemaphoresinordertoavoidtheinef- ficiency mentioned in the previous question. Assume that any semaphore you create is properly initialized in the main function, but you must indicate its initial value in your answer.
// goggles_sem starts at NUM_ITEMS, mx semaphore starts at 1.
int get_goggles() {
int rval;
uthread_sem_wait(goggles_sem);
uthread_mutex_lock(goggles_lock); // or sem_wait on a mx semaphore
rval = goggles[–num_goggles];
uthread_mutex_unlock(goggles_lock); // or sem_signal on a mx semaphore
return rval;
}
void return_goggles(int num) {
uthread_mutex_lock(goggles_lock);
goggles[num_goggles++] = num;
uthread_mutex_unlock(goggles_lock);
uthread_sem_signal(goggles_sem);
}
7
.
5d Kidsliketogettheirgearinanorderdifferentthanadults.Moreprecisely,thecodeusedtoforeachvisitoris
the following (note: line breaks in the call to printf were only added to make it fit this page):
void *visit_lab(void *param) {
person_t *person = (person_t *) param;
int goggles_no, coat_no, gloves_no;
if (person->age < 12) {
goggles_no = get_goggles();
coat_no = get_coat();
gloves_no = get_gloves();
}
else {
coat_no = get_coat();
gloves_no = get_gloves();
goggles_no = get_goggles();
}
printf("Person %d got into the lab using goggles #%d,
coat #%d, gloves #%d.", person->number,
goggles_no, coat_no, gloves_no);
usleep(random() % STALL);
printf(“Person %d got out of the lab.”, person->number);
return_goggles(goggles_no);
return_coat(coat_no);
return_gloves(gloves_no);
return 0; }
Each visitor runs in a separate thread. Is this code deadlock-free? If it is, explain why. If it is not, give a sequence of operations that will result in a deadlock, and explain how to fix the problem.
No it is not deadlock free.
Consider the case where there are two people, one under the age of 12, and one over the age of twelve.
If the thread with the person under the age of twelve acquires the goggles and is then interrupted, and the person over twelve acquires the coat and gloves, the person over twelve will not be able to progress until the gloves are free, and then person under the age of twelve will not be able to progress until the coat is free. This results in a deadlock.
There are a number of possible fixes. One would be to require all people to put on their gear in the same order, another would be to to add a lock around the whole area of code where a person gets their gear, so only one person can get gear at a time.
8