CSCE 313 Quiz 4
Question 1 [10 pts]: The following is the Producer(.) function in a BoundedBuffer implementation. What is the purpose of the mutex in the following? Can we do without the mutex? In what circumstances?
Producer(item) {
emptySlots.P();
mutex.P();
Enqueue(item);
mutex.V();
fullSlots.V();
}
The purpose of the mutex is to prevent race conditions among the multiple producers who get past he first line, because there are empty slots.
The mutex is not need when there is just 1 producer.
Question 2 [10 pts]: The following is the Producer(.) function in a BoundedBuffer implementation. Can we change the order of the first 2 lines? Why or why not?
Producer(item) {
emptySlots.P();
mutex.P();
Enqueue(item);
mutex.V();
fullSlots.V();
}
We cannot. Because that would cause the Producer() to get stuck if there is no emptySlots. But note that the producer is stuck with the mutex locked. So, the consumer cannot consume either. Therefore there is no chance in the future that some empty slot will open up, which the producer is waiting on, AKA deadlock
|
Question 3 [10 pts]: If we run 5 instances of ThreadA() and 1 instance of ThreadB(), what can be the maximum number of threads active simultaneously in the Critical Section? The mutex is initially unlocked. Note that ThreadB() is buggy and mistakenly unlocks the mutex first instead of locking first. Explain your answer.
|
The max is 3. First ThreadA() in CS causes mutex=0, ThreadB() in CS causes mutex = 1, which allows another ThreadA() to be in CS. After that, no more ThreadA() can get in because mutex=0. There is no more ThreadB() because we only ran 1 instance of ThreadB()
Question 4 [10 pts]: Is there any race condition if we run the following function from multiple threads? Why or why not? What is the range of values (minimum and maximum) x can have after running ThreadFunction() from 10 threads. Explain using machine level assembly language.
int x=0;
void ThreadFunction(){
x++;
}
Lw $r, x
addi $r, 1
sw $r, x
IF there is a context switch between line 1 and 2, or 2 and 3, then the effect of a 2nd thread is lost. In this way, you can come up with an interleaving that erases everything except 1 thread, making the min = 1. On the other hand, it is possible that all threads ran 1 after another without interleaving (because it all depends on the wish of the scheduler) leading to max = 10.
Question 5 [25 pts]: Consider a Producer-Consumer problem where M Producer threads run simultaneously (no locking necessary among the producer threads) to fill up a buffer. Then several (i.e., 1 or more) Consumer threads will run simultaneously to take all the data out from the buffer. An example of such scenario is a file is striped into m different sites and the downloader is putting the data in a single buffer. This buffer is then processed using some Consumer threads.
Now regarding the Consumer threads form a group. They will keep consuming as they can arrive while there are other consumer threads. However, the first one coming in have to wait for the producers to finish, and the last one going out has to wake up the Producers. There can be any number (i.e., at least one) of Consumer threads piggybacking one after another. Assume that there are 100s of Producer and Consumer threads available and they are trying to run constantly. You are one controlling their numbers.
Idea: A fixed M producers must produce. Then, the consumers will form a “caravan” where 1 or more will run as long as they arrive before the previous consumer is done.
{`///////////// Given Code Sketch ///////////////`}
Producer(){
while (true){
PWait(); // define this
ProduceOperation(); //does not matter what is inside
PDone(); // define this
}
}
Consumer(){
while (true){
CWait(); // define this
ConsumeOperation(); //does not matter what is inside
CDone(); // define this
}
}
{`/////////////// Solution //////////////////////////`}
Semaphore full (0), empty(M);
int pcount = 0, ccount = 0; // number of producers/consumers done so far
Mutex pcm, ccm; // mutexes to protect the above counts
PWait(){
empty.P(); // wait for an empty slot
}
PDone(){
pcm.Lock();
pcount ++; // safely inc # of prods that are done
if (pcount == M){
pcount = 0; // reset counter
full.V(); // unleash the consumers
}
pcm.Unlock();
}
CWait(){
ccm.Lock();
ccount ++;
if (ccount == 1){ //the first in a caravan
full.P(); // only this one needs the full, others piggyback
}
ccm.Unlock();
}
CDone(){
ccm.Lock();
ccount --;
if (ccount == 0){ //the last one in a caravan, this needs to wake up all M prods
for (int i=0; i<M; i++)
empty.V(); // this will unleast exactly M producers
}
ccm.Unlock();
}
Question 6 [15 pts]: There are 3 sets of threads A, B, C. First 1 instance of A has to run, then 2 instances of B and then 1 instance of C, then the cycle repeats. This emulates a chain of producer-consumer relationship that we learned in class, but between multiple pairs of threads. Write code to run these set of threads.
Assumptions and Instructions: There are 100s of A, B, C threads trying to run. Write only the thread functions with proper wait and signal operation in terms of semaphores. You are allowed to use the necessary number of semaphores as long as you declare them in global and initialize them properly with correct values. The actual operations done by A, B and C does not really matter.
Sempahore adone(0), bdone(0), cdone(1);
int bcount = 0;
mutex bmutex;
ThreadA(){
while (1){
cdone.P();
{`// do stuff`}
adone.V();
adone.V();
}
}
ThreadB(){
while (1){
adone.P();
{`// do stuff`}
bmutex.Lock();
bcount ++;
if (bcount == 2){
bdone.V();
bcount = 0;
}
bmutex.Unlock();
}
}
ThreadC(){
bdone.P();
{`// do stuff`}
cdone.V();
}
Question 7 [20 pts]: For the program below:
- Draw the Descriptor table (DT) and File Table (FT) after executing EACH of lines 3, 5, 8. (no need for the v-node table). In each diagram, make sure to draw arrows from DT to FT for only STDOUT and fd. Also show reference counts and file cursor in your diagrams.
- What does the file contain at the end? What is printed in the STDOUT?
1 char c='C';
2 int fd = open ("file", O_WRONLY|O_CREAT, S_IRWXU);{`// write mode`}
3 dup2 (fd,1); {`// draw tables`}
4 if(!fork ())
5 cout <<“Hello”; {`// draw tables`}
6 else{
7 wait (0);
8 write (fd,&c,1);{`// draw tables`}
9 }
