Choose the best definition for each term.
Race Condition
Mutual Exclusion
Busy Waiting
Critical Section
Block Waiting
In a system with multiple threads in which any thread can call swap() or sum(), and assuming that lock and unlock are correct lock implementations, is the following code properly synchronized?
int* a;
int n;
/**
* swap array elements a[i] and a[j]
*/
void swap(int i, j){
int t;
t = a[i];
a[i] = a[j];
a[j] = t;
}
/**
* return the sum of the elements in array a (a[0] .. a[n-1])
*/
int sum(){
int s = 0;
lock(l);
for (int i=0; i<n; i++)
s += a[i];
unlock(l);
return s;
}
Consider these three procedures that are allowed to run concurrently in different threads. Assume all mutexes are initialized correctly, and all locks are non-reentrant locks.
void one() {
lock (a);
lock (b);
...
unlock (b);
unlock (a);
}
void two() {
lock (c);
lock (a);
...
unlock (a);
unlock (c);
}
void three() {
lock (b);
...
unlock (b);
lock (a);
lock (b);
...
unlock (b);
unlock (a);
}
Will all the threads deadlock?
Which of the following statements is true about this code?
ld $lock, r0
L0: ld (r0), r1
beq r1, L1
br L0
L1: ld $1, r1
st r1, (r0)
Consider the following snippets of C code that uses mutexes and condition variables. Both procedures are called from concurrent threads (i.e., one thread calls procX and the other calls procY). Note that initialization code is omitted for brevity; you should assume that all global variables were initialized correctly.
For the below snippet, indicate whether or not the code will always deadlock, sometimes, or never deadlock. Note that if it is only one procedure that does not finish, it is not considered a deadlock.
void procX() {
lock (mx);
for (int i=0; i<100; i++) {
wait (condY);
signal (condX);
}
unlock (mx);
}
void procY() {
lock (mx);
for (int i=0; i<100; i++) {
signal (condY);
wait (condX);
}
unlock (mx);
}
Suppose I have two threads that perform a few operations, a mutex mx and a condition variable cond, as follows:
Thread 1:{
o();
lock(mx);
m();
wait(cond);
unlock(mx);
s();
}
Thread 2:{
lock(mx);
f();
signal(cond);
x();
unlock(mx);
}
Which of the following orderings are possible? Select ALL correct answers (The notation "a→b" means that the call to a() "happens before" the call to b().)
Select all possible options that apply.
Suppose I have two threads that perform a few operations, a mutex mx and condition variables cond1, and cond2 as follows:
Thread 1:{
lock(mx);
g();
signal(cond2);
wait(cond1);
k();
unlock(mx);
}
Thread 2:{
lock(mx);
r();
wait(cond2);
o();
signal(cond1);
unlock(mx);
}
Which of the following orderings are possible? Select ALL correct answers (The notation "a→b" means that the call to a() "happens before" the call to b().)
Select all possible options that apply.
During the COVID-19 pandemic, stores often had to limit the number of clients inside their stores, typically with a staff member that controlled when clients entered or exited the store. In this question, you will implement two functions that emulate the behaviour of this staff member:
enter_store is called when a client intends to enter the store. It blocks if the store's capacity has been reached, and only returns when the client is able to actually enter the store.leave_store is called when a client leaves the store. If there is a client waiting to enter the store, that client is let in.A naïve implementation is presented below.
int num_clients = 0;
void enter_store(void) {
while (num_clients >= STORE_LIMIT) uthread_yield();
num_clients++;
}
void leave_store(void) {
num_clients--;
}
The code above is subject to race conditions. It also does not properly block the current thread, causing the loop in enter_store to potentially waste CPU cycles. Using a mutex and a condition variable, change the code above to ensure the code is properly synchronized: free of race conditions and properly blocked when unable to proceed. The global variable num_clients must also be reliably updated by your function based on the description and example above.
Assume the mutex mx and the condition variable cond have already been created and initialized appropriately. You are not required to ensure that clients enter the store in any particular order (i.e., it is ok to submit code that allows queue jumping).
Moreover, assume STORE_LIMIT is already defined and initialized, i.e., do not define it again.
For reference, here are the function signatures for mutex and condition variable functions in the uthread library. You may only call the functions below.
void uthread_mutex_lock(uthread_mutex_t);
void uthread_mutex_unlock(uthread_mutex_t);
void uthread_cond_wait(uthread_cond_t);
void uthread_cond_signal(uthread_cond_t);
void uthread_cond_broadcast(uthread_cond_t);
#include "uthread_mutex_cond.h"
int num_clients = 0;
uthread_mutex_t mx;
uthread_cond_t cond;
void enter_store(void) {
uthread_mutex_lock(mx);
while (num_clients >= STORE_LIMIT) {
uthread_cond_wait(cond);
}
num_clients += 1;
uthread_mutex_unlock(mx);
}
void leave_store(void) {
uthread_mutex_lock(mx);
num_clients -= 1;
uthread_cond_signal(cond);
uthread_mutex_unlock(mx);
}