[SOLVED] CS COMP2310/6310 2021 S2 Final Exam

type Waiting_Process is range 0..2;
Gate1, Gate2 : Waiting_Process := 0;

task body P1 is
Put_Line (P1 in NCS);
Gate1 := 1;
if Gate2 = 0 then
Gate2 := 1;
exit when Gate1 = 1 and Gate2 = 1;
Put_Line (P1 in CS);
critical_section_1
Gate2 := 0;

task body P2 is
Put_Line (P2 in NCS);
Gate1 := 2;
if Gate2 = 0 then
Gate2 := 2;
exit when Gate1 = 2 and Gate2 = 2;
Put_Line (P2 in CS);
critical_section_1
Gate2 := 0;

### Q1.e [7 marks]

This semester you have gained significant experience programming in the Ada language.
If you had to design a concurrent programming language from scratch, describe at least three features of Adas support for concurrency that you would or would not include. For Ada features that you would not include, propose an alternative. Provide a design justification for each feature.

## Question 2: Message Passing [30 marks]

### Q2.a [22 marks]

In an assignment, students were asked to provide a solution for a *mailbox* task, which provides the following properties:

The mailbox task shall

1. provide the following entries to put messages into the mailbox and take messages out of the mailbox:
type Message is range 1 .. 20;
task Mailbox is
entry Put (Msg : Message);
entry Take (Msg : out Message);
end Mailbox;
2. allow the `Take` entry to be called by multiple receiver tasks of the following type:
task type Receiver;
3. deliver messages in the same order in which they have been received.
4. be able to store more than one message.
5. allow a sending task (the task calling `Put`) to send messages as long as the mailbox still has storage capacity, even if the `Receiver` is currently not available.
6. if the mailbox has no free storage capacity, block any call to `Put` until the mailbox has free capacity.
7. when `Take` is called and there is a message in the mailbox, return the message immediately.
8. when there is no message in the mailbox, block any call to `Take` until a message arrives.

Three submissions from different students are shown below. All three submissions compile without warnings.

Student A:

task body Mailbox is
Contents : Message;
accept Put (Msg : Message) do
Contents := Msg;
accept Take (Msg : out Message) do
Msg := Contents;
end Mailbox;

Student B:

task body Mailbox is
Contents : Message := MessageInvalid_Value;
when ContentsValid =>
accept Take (Msg : out Message) do
Msg := Contents;
Contents := MessageInvalid_Value;
accept Put (Msg : Message) do
Contents := Msg;
end select;
end Mailbox;

Student C:

task body Mailbox is
package Storage is new Queue_Pack_Generic (Message);
use Storage;
Store : Protected_Queue;
when not Store.Is_Full =>
accept Put (Msg : Message)do
Store.Enqueue (Msg);
accept Take (Msg : out Message)do
Store.Dequeue (Msg);
end select;
end Mailbox;

(For definition of `Queue_Pack_Generic`, see https://gitlab.cecs.anu.edu.au/comp2310/comp2310-lectures/-/blob/master/queue-implementations/queues-concurrent/src/queue_pack_generic.ads)

#### Q2.a.i [14 marks]

Evaluate all three student submissions and provide feedback.

For each submission, indicate which properties have *not* been successfully implemented. For properties that have not been successfully implemented, explain why it fails and briefly suggest an improvement. (If you do not provide feedback for a given property, that means you believe it has been successfully implemented.)

#### Q2.a.ii [8 marks]

If you find all three student submissions lacking in some regard, provide your own solution below.
Use any programming language of your choice (including pseudocode) to implement a buffer, which fulfils all required properties, and is based on synchronous message passing.
If you believe one of the student submissions already fulfils all requirements, then explain why.

### Q2.b[8 marks]

Assume that a concurrent programming language does not support asynchronous message passing but does provide some form of synchronous message passing.

Construct an asynchronous message-passing system using any programming language of your choice (including pseudocode).
You should provide methods, functions, procedures, subroutines, processes, threads, or tasks (depending on the language of your choice and your design) to provide the following operations:

asynchronous send
asynchronous receive
wait for completion of send
wait for completion of receive

State your assumptions about the synchronous message-passing system which you use as a foundation.

## Question 3: Data Parallelism [14 marks]

### Q3.a [3 marks]

How does a `forall` statement in Chapel differ from a `for` statement in Java or C? Be as precise as you can.

### Q3.b [11 marks]

Read this syntactically correct Chapel expression and then answer the questions below:

sqrt((+ reduce (Vector (+ reduce Vector)/n)**2)/n)

where you may assume the following declarations:
config const n = 1000;
const Index = {1 .. n};
var Vector : [Index] real;

#### Q3.b.i [1 mark]

What is the type of the expression?

#### Q3.b.ii [6 marks]

Identify and explain the potentially data-parallel operations which are implemented by this Chapel expression. For each operation, state the degree of potential data parallelism in terms of the maximum number of processing elements that could be used to execute the operation.

#### Q3.b.iii [4 marks]

Assume an infinite number of available computing cores. How does the processing time complexity of the above expression scale with `n` (in terms of overall time passed, rather than in terms of the cost of all executed machine instructions)?

## Question 4: Scheduling [11 marks]

### Q4.a[11 marks]

In answering the following questions, consider the scheduler in an operating system for a desktop computer (for example, the computer you are using right now!).

#### Q4.a.i [5 marks]

What properties of the processes running on the computer can be observed by the operating system?

#### Q4.a.ii [2 marks]

What performance goals do you assume the scheduler is designed to achieve?

#### Q4.a.iii [4 marks]

What information is available to the scheduler to optimize for those goals, and how might it choose which process to schedule next?

## Question 5: Distributed Systems [13 marks]

### Q5.a [13 marks]

Read the following Ada program carefully. The program is syntactically correct and will compile without warnings.

with Ada.Text_IO; use Ada.Text_IO;
procedure Distributed_System is
type Workers_Range is range 1 .. 3;
type Clients_Range is range 1 .. 6;
task Server is
entry Service;
entry Report (w : Workers_Range);
entry Hold;
entry Forward;
end Server;
task type Worker is
entry Identify (Id : Workers_Range);
entry Service;
end Worker;
Workers : array (Workers_Range) of Worker;
task body Server is
type State is (Available, Busy);
type States is array (Workers_Range) of State;
All_Workers_Busy : constant States := (others => Busy);
Workers_State: States:= All_Workers_Busy;
accept Report (w : Workers_Range) do
Workers_State (w) := Available;
end Report;
or when ForwardCount = 0 =>
accept Service do
if (for some w of Workers_State => w = Available) then
requeue Forward;
requeue Hold;
end Service;
or when ForwardCount = 0
and then Workers_State /= All_Workers_Busy =>
accept Hold do
requeue Forward;
accept Forward do
for i in Workers_Range loop
if Workers_State (i) = Available then
Workers_State (i) := Busy;
requeue Workers (i).Service;
end Forward;
terminate;
end select;
end Server;
task body Worker is
Worker_Id : Workers_Range;
accept Identify (Id : Workers_Range) do
Worker_Id := Id;
end Identify;
Server.Report (Worker_Id);
accept Service do
Put ( W & Workers_RangeImage (Worker_Id) & );
delay 1.0; pretend to work
Server.Report (Worker_Id);
end Service;
terminate;
end select;
end Worker;
task type Client;
task body Client is
Server.Service;
end Client;
Clients : array (Clients_Range) of Client;
for w in Workers_Range loop
Workers (w).Identify (Id => w);
end Distributed_System;

#### Q5.a.i [2 marks]

What are the different types of concurrent entities that are implemented in this program, and how many are there of each?

#### Q5.a.ii [2 marks]

How many task queues are implemented in this program? Identify them.

#### Q5.a.iii [4 marks]

Which of the entries in this program might block for an extended period? Assume that the underlying hardware supports running all concurrent entities in the program in parallel.

#### Q5.a.iv [5 marks]

What are the sources of non-determinism in this program? How does non-determinism affect the overall program behaviour, including the output? Will the program sometimes or always terminate, livelock or deadlock? Provide reasons for your conclusions.

## Question 6: Networks and Time [12 marks]

### Q6.a [6 marks]

At a minimum, a network router must implement the first three layers of the OSI network model. Why is this the case? What would be the advantages and disadvantages of implementing services from additional layers? Consider from the point of view of network providers, application providers, and application users.

### Q6.b [6 marks]

The following three questions refer to logical time (or Lamport time).

### Q6.b.i [3 marks]

What are the advantages and disadvantages of logical time in comparison to wall-clock time?

### Q6.b.ii [1 mark]

What can you conclude if a process receives a message with a logical timestamp that is greater than the logical time of the current process? Please explain any symbols or connectives you use in your answer.

### Q6.b.iii [2 marks]

Process X sends a message with timestamp *C(a)* to Process A, followed by a message with timestamp *C(b)* to Process B.
After receiving these messages, both Processes A and B send reply messages to Process X.
Process X first receives the reply from Process A with timestamp *C(c)*, and then receives the reply from Process B with timestamp *C(d)*.

What can you conclude about the timestamps *C(a)*, *C(b)*, *C(c)*, and *C(d)*?

**This is the end of the exam.**

CS : assignmentchef QQ: 1823890830 Email: [email protected]