Computer Science 343 Final Examination

Instructions




The final exam duration is 3 hours including download of the exam and uploading/submitting the programs.




Your time begins at the exam download and is compared with the date-stamps on the files you submit.




The final consists of 5 complete running programs, which will be tested after the exam.




You are given the following files:




Makefile

MPRNG.h

AutomaticSignal.h

BarrierTime.cc

BarrierTimeAdmin.cc




Answer each question in the appropriate file using the given program main, Worker and Timer tasks, and starter code specific for each question. Do NOT subdivide a program into separate .h and .cc files. Use the Makefile to help simplify compilation, when a question has multiple implementations. Enter “make” in the given directory to see how the programs compile.




After writing and testing the 5 programs, submit all the files on the undergraduate environment using the submit command:




$ submit cs343 final directory-name




As a precaution, submit often, not just at the end of the final.




The following aids are allowed:




computer to write, compile, and test the final programs.



course notes



course textbook



your previous assignments



µC++ Annotated Reference Manual



man pages



cppreference.com / cplusplus.com to look up C++ syntax



The following aids are NOT allowed:




any answers from prior final exams because you did not create them



any web searching, like stack overflow or Wikipedia



any interaction with another person



any use of another person’s documents or programs



Basically, you are to complete the final by yourself using only course-related material or work you have created versus the work of others.




There is no way for us to fairly answer questions over the 24 hours of the exam, so state any assumptions with a comment in the program and press on.




Do not post on Piazza during the 24-hour exam period. If necessary, do a private post.

 Final Exam – CS 343 (F21)
3






Monitors




A barrier lock performs synchronization on a group of N threads so they all proceed at the same time. A barrier is accessed by any number of threads. The barrier makes the first N − 1 threads wait until an N th thread arrives at the barrier and then all N threads continue. After a group of N threads continue, the barrier resets and begins synchronization for the next group of N threads. A barrier is used in the following way by client tasks:




Barrier b; // global declaration or passed to the client

. . .

b.block(); // each client synchronizes, possibly multiple times




A time-barrier has a timeout member to flush waiting tasks. That is, if less than N tasks have arrived at time T , the group of tasks (< N ) is unblocked to make progress. If a timeout call occurs when no tasks are waiting in the barrier, the call does nothing. Hence, timeout needs to trick waiting tasks that called block to unblock by modifying variables and/or start unblocking. Finally, timeout ensures no quorum-failure deadlock because waiting tasks eventually unblock.




Using µC++ monitors, implement a time-barrier lock in file BarrierTime.cc using the given interface (you may add a public destructor and private members):



_Monitor Barrier {

const unsigned int N; // group size

unsigned int count = 0, // blocked tasks (< N)

total = 0, // value sum

groupno = 0; // group number




VARIABLES FOR EACH IMPLEMENTATION public:



struct Result { unsigned int total, groupno; }; Barrier( unsigned int N ) : N( N ) {

INITIALIZATION FOR EACH IMPLEMENTATION
}

void timeout() {

WRITE THIS MEMBER FOR EACH IMPLEMENTATION
PRINT TIMEOUT AND GROUP MESSAGE
}

Result block( unsigned int value ) {

WRITE THIS MEMBER FOR EACH IMPLEMENTATION
PRINT GROUP MESSAGE
}

};




The group size, N, is passed to the constructor. Each task calling block passes a value (>0). The sum of these values for all the tasks in a group and the group number are returned in Result to each task. For a timeout, the total returned is 0, so a task knows if its group timed out. A timeout with no waiting tasks does not advance the group number.




Implement the time-barrier monitor in the following ways, where the solutions must prevent staleness and freshness.




10 marks external scheduling



13 marks internal scheduling
 Final Exam – CS 343 (F21)
4






17 marks internal scheduling with a Java-style monitor using a single condition variable and the



2 given routines:

  
 
            
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 



ADDITIONAL VARIABLES public:



Barrier( unsigned int N ) : N( N ) {

ADDITIONAL INITIALIZATION
}

void timeout() {

WRITE THIS MEMBER
}

Fresult block( unsigned int value ) {

// WRITE THIS MEMBER

}

private:

void main() {

WRITE THIS MEMBER
PRINT TIMEOUT AND GROUP MESSAGE
}

};




The group size, N, is passed to the constructor. Each task calling block passes a value (>0). The sum of these values for all the tasks in a group and the group number are returned to each task in Result. For a timeout, the total returned is 0, so a task knows if its group timed out. A timeout with no waiting tasks does not advance the group number.




Use the given Makefile, which generates an executable called barrieradm, to compile and test the time-barrier administrator using commands:




make barrieradm
barrieradm . . .



The program main, shell interface, and output are the same as for the monitors in question 1.