CS 563 – Spring 2020
Midterm Exam Part I – Written Questions March 23, 2020
Name: ______________________ Student ID: __________________
• This is an open book exam.
Copyright By PowCoder代写 加微信 powcoder
• Time: 8:00am-11:59pm on March 23, 2020.
• This exam consists two parts. This is Part I: written questions
• Answer all questions. You can create your own file using any editor you
• Keep your answers as brief as possible
• Submit your answers to Blackboard in PDF format by the above noted
CS 563 Midterm Exam (Mar. 23, 2020)
I-1. (4 pts) Actor model has a fundamentally different design comparing to other message passing models, e.g., CSP and MPI. One major difference is that the Actor model uses asynchronous message passing, while CSP and MPI both use synchronous message passing. What are the pros and cons of using asynchronous message passing in a model of concurrency?
I-2. (4 pts) Are the following statements true or false? Give a brief explanation
a) To solve a critical section problem, the two required protocols CSenter and CSexit must appear in pairs.
b) Mutual exclusion is the only reason why you need synchronization.
CS 563 Midterm Exam (Mar. 23, 2020)
I-3. (6 pts) Suppose we have a shared channel that is declared as: chan bag(int) Assume that some process has initialized the bag by sending n values to it.
The problem is to use M workers to compute and print the sum of all the elements in bag. Each can compute only one sum at a time. Someone suggests the following program:
process Worker[i = 1 to M] { declarations of local variables;
while (true) {
receive two elements from the bag; compute their sum;
if (empty(bag))
{ print the sum; break; } else
send bag(sum);
(a) This program will work some of the time but not always. Explain when it will work and when not.
CS 563 Midterm Exam (Mar. 23, 2020)
(b) Explain how to fix the program so that it always computes the sum and prints the result once. It is OK if some workers are blocked when the program terminates. You can add fields to the messages stored in bag, add additional channels, and/or add a manager process. You do not need to develop detailed code. It is sufficient to give a good explanation and/or high-level pseudo-code.
CS 563 Midterm Exam (Mar. 23, 2020)
I-4. (6 pts) Read the following program and answer the questions.
int x=0, y=10; cowhile(x!=y) x=x+1;
//while(x!=y) y=y-1;
(a) Does this satisfy the at-most-once property? Explain.
(b) Will the program terminate? Explain.
CS 563 Midterm Exam (Mar. 23, 2020)
I-5. (6 pts) Read the following program and develop a proof to show the final values of x and y. (a) Proof
int x=0, y=0;
co
//
(b) How many histories are there?
CS 563 Midterm Exam (Mar. 23, 2020)
I-6. (6 pts) Read the code and answer the questions.
int x=10, c=true;
co
(a) Will the program terminate if scheduling is weakly fair? Explain.
(b) Will the program terminate if scheduling is strongly fair? Explain.
(c) Add the following as a third arm of the co statement. Repeat (a) and (b) for this three-process program.
//while(c){if(x<0)
CS 563 Midterm Exam (Mar. 23, 2020)
I-7. (8 pts) Below, a monitor implementation of a read/write lock is given. Readers call lock(false) before reading and writers call lock(true) before writing. When done, both readers and writers call unlock(). The implementation ensures fairness by handling lock calls in strictly first-come-first- served (FCFS) order. This is accomplished by using one condition queue, head, to hold the first waiting lock call and another condition queue, tail, to hold the subsequent calls in FIFO order.
monitor FairRWLock
int r = 0;
int w = 0;
boolean heading = false; cond head, tail;
procedure lock(write: boolean) { if (heading) wait(tail);
while ((w>0) || (write && r>0)) { if (write) w=w+1
else r=r+1;
if (empty(tail)) heading = false else signal(tail);
procedure unlock(){
if (w>0) w = w-1
else r = r-1;
if (r=0) signal(head); }
The read/write lock is now to be implemented on a server using rendezvous. The server module is specified by:
module RWLock
op lock(boolean write); op unlock();
(a) Write a server process for the module which serves the operations in such a way that it functions like a basic read/write lock. The calls of lock may be served in any feasible order, and the solution does not have to be fair.
(b) Writeanalternativeserverprocessforthemodulesothatthemodulefunctionslikethegiven monitor FairRWlock. In particular, calls of lock should be served in FCFS order. (If your solution to (a) already fulfils this requirement, you may just refer to that.)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com