Final Examination Solution

Instructions

General

    1. This is a take-home exam and should be treated as such. You are expected to do the exam independently and may not collaborate with other people (classmates or otherwise).

    2. This is an open-book exam, so you can consult your notes, the lecture materials, Google, Stack Overflow, man pages, etc.

    3. If you take code from a source on the internet, make sure you cite it with a comment including the URL where you found it.

    4. Questions will not be answered on Piazza or via e-mail; if you need to state an assumption, do so.

    5. Submit your PDF with the written questions to the written question dropbox, and a zip file with your code to the code question dropbox.

    6. Be sure to submit your files on time.


Written Questions

    1. You can create your PDF using whatever software you like.

    2. Answer the questions in the order of the exam, but also make it clear to the reader what question is being answered.

    3. Use the amount of marks associated with a question as your guide for how much you should write; keeping it brief is preferred.

Programming Questions

    1. You are allowed to modify the code and the makefiles as you need, except you cannot change the output formats (for marking consistency).

    2. Your code needs to run on eceubuntu machines.

    3. You can use the compiler, code analysis tools, debuggers, etc.

    4. If you are having technical issues with the ECE Servers, please e-mail praetzel@uwaterloo.ca (course staff are not admins on the machines).

    5. If something is wrong with the remote server, please contact jzarnett@uwaterloo.ca (I run that one!)

    6. As with the assignments, your local machine setup cannot be supported.

    7. Please try to distribute your work across servers; if a server is heavily loaded, use a different one.

    8. Please respect the directions to use a maximum of 4 threads in any question that requires threads; this helps reduce the server load to allow multiple people to work at once.





























1
    • Short Answer Questions [25 marks]

Answer the following questions by either completing the code or writing 1-3 sentences; 2.5 marks each.


    1. Some implementations of select change the struct timeval. That usually means it needs to be reset on each iteration of the loop, but can getting the remaining time value back be useful somehow? Explain.

    2. Amid the pandemic, gyms may require bookings for time slots. So if the gym has a 1 hour time slot and a maximum occupancy of 10 people, members must book in advance to get one of those spaces. In this scenario, does a lock-modify-unlock model or a copy-modify-merge model make sense? Explain.

    3. Give an example of something that could go wrong if you used malloc() in a signal handler.

    4. You have a program where the parallel part is known to be 15%. Calculate the maximum possible speedup for this program, reported to three decimal places. Show your work.

    5. You have a function save() that should not be interrupted by the SIGINT signal. Show how you would block this signal before calling save() and then unblock it afterwards.

    6. Consider the following changes to the Dining Philosophers Problem, in which we have 5 philosophers and 5 chopsticks. Does the change prevent deadlock from occurring? Explain your answer.

        (a) Remove one philosopher and one chopstick from the group.

        (b) Philosophers are assigned to either the left-handed team (50% chance) or the right-handed team (50% chance) when they enter the room and will always try to pick up chopsticks in the correct order for their team.

    7. Could you improve the performance of your program by cancelling threads? Explain.

    8. Why is this code wrong? Explain how you would fix it.
int main(int argc, char * argv[]) {    void * run (void * arg) {
pthread_t threads[10];    // do something correct with parameters
for( int i = 0; i < 10; ++i ) {    }

struct params p;

p.x = 0;

p.y = 0;

p.z = 0;
pthread_create(&threads[i], NULL, run, &p);
pthread_detach(t1);
}
pthread_exit( 0 );
}

    9. Describe a scenario where the lost-wakeups problem can occur, but does not affect the outcome of execution.

    10. Speculate as to why message queues require different message types specified as a field in the message, rather than requiring different types of message to be in different queues.

    • Synchronization Problems [11 marks total]

2.1    Battle of Hoth [5 marks]

Recall from lectures that the Rebel Alliance wanted to escape from the ice planet Hoth before Darth Vader and the Imperial troops could capture them. They are evacuating transports with a fighter escort, but the problem description left out an important aspect of the Rebels’ success: the Ion Cannon. If hit by Ion Cannon fire, a capital ship (e.g., a Star Destroyer) will be disabled and open a gap for the transports and fighters to escape.

The Ion Cannon has to execute the functions ready(), aim() and fire(). Obviously, it must be ready before aiming, and aim before firing. Fighters and Transports cannot launch until the Ion Cannon has aimed. As soon as the Transport launches, the Ion Cannon should fire.

Reproduced here is the solution from the lectures, with a new column for the Ion Cannon. Complete the Ion Cannon column and make modifications, if any are needed, to the pseudocode of the Fighters and/or Transports to implement the described behaviour.

Initial values: mutex = 1 and fighter_queue = 0 and transport_queue = 0.

Fighters    Transport    Ion Cannon

wait( mutex )    wait( mutex )

if transports > 0    if fighters > 0

transports--    fighters--
post( transport_queue )    post( fighter_queue )
else    else

fighters++    transports++

post( mutex )    post( mutex )
wait( fighter_queue )    wait( transport_queue )
end if    end if

launch()    launch()

post( mutex )

2
2.2    Pineapple? On MY Pizza? It’s more likely than you think. [6 marks]

In this scenario, we’ll use the version of the pizza makers pseudocode where the contestants have a helper and the host places ingredients only when there is a post( host ) call.

As you know, pineapple is a divisive ingredient when it comes to pizza. Some people like it, and some really do not. In this version of the game, the host will sometimes (but not always) signal to a contestant who is ready to make their pizza that they should add the controversial ingredient. Since the contestants are not going to eat the pizza, it does not matter how they feel about it and will add it if directed.

Consider the pseudocode below for the contestants. It does to work as expected. What goes wrong and why? Explain also how you would fix it.

Contestant A

wait( contestantA )
get_sauce()
get_cheese()
wait( pineapple )
add_pineapple()
make_pizza( )
post( host )

Contestant B

wait( contestantB )
get_dough()
get_cheese()
wait( pineapple )
add_pineapple()
make_pizza( )
post( host )

Contestant C

wait( contestantC )
get_sauce()
get_dough()
wait( pineapple )
add_pineapple()
make_pizza( )
post( host )



    • Election Day [23 marks]

Before elections, professional polling companies ask eligible voters whom they will vote for in the upcoming elec-tion. Sophisticated companies apply an adjustment based on how likely a person is to actually vote, because not everyone who is eligible will vote. Even though they should.

Our simplified simulation will involve an election where a voter’s choices are A and B. We have data about 100 000 voters. A voter is represented by three numbers in the provided CSV file. The code to parse a line into a voter structure is provided, but you will want to put it into a collection so you can run the simulations.

To get good data, you need to do 100 000 runs. Each run involves generating a random number for each voter, using the random_number() function. That function returns a random value P (between 0 and 1). Using that value for P, the current voter v: (1) votes for A if P < v.x, they vote for B if v.x <= P < (v.x + v.y) and they vote for nobody if P >= (v.x + v.y). v.z is just used to numerically represent the chance that they do not vote. Each voter’s values of x, y, z sum up to 1.0. At the end of the simulation, you compare the tally of votes for each candidate and determine who won (or if there was a tie).

Repeat the simulation procedure for each of the 100 000 runs. At the end of all the simulations, your program will output to standard out the percentage chances for each candidate to win and the percentage of time that they tie, using the provided function print_results().

It’s possible to parallelize this problem, so your solution should use four (4) threads to carry out the simulations.

Complete the provided code to implement the functionality required.

    • Distribute the Work... [16 marks]

Periodically, the department (and faculty) need to prepare data in a very large and very long report for accred-itation purposes. Accreditation is what allows your undergraduate degree to count as the engineering education requirement when applying for an engineering license.

You have been hired as a co-op by the ECE department to assist Professor Wright in compiling the data. You will write a client that connects to a remote server to get units of work to do. The server will send you a file, you do some work, and send back the answer.

The client connects to the server at the IP 54.209.48.141 on port 2525. The server first sends you the size of the data file (as an integer). Send the text GET to the server when you are ready for the file. If something is wrong, the server will close the connection. Otherwise, the server will send you the file.

The provided data file is in in a comma-separated format; that is, each line is a row in the file and columns are separated by commas. There are two columns in each file: the first is UUID (a unique identifier that represents a student, but in an anonymous way so that students working on the data cannot identify any other student) and of course the grade, a value between 0 and 100 that requires no further explanation.

Call the provided function to calculate the arithmetic mean (rounded to the nearest integer). Print to the console as a form of logging in the form Computed average: 99 (where 99 is replaced with the average you calculated). Send the mean as a 32-bit integer to the server. The server will respond OK if correct and INVALID if something is wrong. Print the answer the server sent to the console in the form Answer: OK or Answer: INVALID.

Complete the provided starter code to implement the functionality described above.





3
    • Proconsumer [25 marks]

The producer/consumer problem had fixed roles where a thread/process was only a producer or only a consumer. In modern frameworks, a thread/process does one step of the work and then passes it on to another thread/process that will do the next step. Having multiple consumer/producers allows for plug-and-play combinations that are easier to read and more portable across applications.

For this question, you will implement three stages: the producer thread creates items and puts them in the input queue. The proconsumer thread takes an item from its input queue, does some work on it with do_work, and then places the modified item in the output queue. The consumer thread takes items out of the output queue and does something with them.

You should use the datatype queue, which is created with a maximum size (capacity) and can perform the actions push() and pop(). These three queue functions are not thread-safe. Also, you should not call push() when there is not enough space, and not call pop() when there are no items in the queue.

Complete the provided starter code to implement the desired behaviour. The starter code contains some comments to guide you through what is supposed to happen, so pay attention to those.





































































4