COMP2310 2017 Final

General Concurrency

a. Which of the following hardware architectures require or are supportive for concurrent programming?

Pipelines, Vector Processors, Hyper-threading

https://en.wikipedia.org/wiki/Pipeline_(computing)

Vector processors allow things to be applied to many different objects/items in parallel via efficient execution of fractions of a complex task on multiple processing units. Hyper-threading, which divides up physical cores into virtual cores is supportive of concurrent programming because it has to split up the cpu so that it can have double the amount of threads or virtual cores. Thus it must support concurrency. Pipelines, which can be thought of as an assembly line of tasks allows for the execution of many tasks in parallel or time sliced fashion due to its design. As such they too are supportive for concurrent programming.

b. Explain the functionality of a network router. Which layers of the OSI model are implemented? Give reasons why a specific OSI layer needs to be implemented in a network router.

A network router works primarily in the Network layer. The network layer is where routing of internet packets occurs where a router must decide whether to forward a packet or not. Routers must also be aware of any network protocols avaliable in-order to properly address and route the packets. Other important features which must be done by the router include switching of packets and congestion control to ensure packets arrive on time.

c. Which layer(s) of the OSI model are specified by IEEE 802.3 (commonly known as Ethernet). Give reasons why a specific OSI layer needs to be specified.

IEEE 802.3 or Ethernet relies on the Data Link Layer in order to transfer data across a network and through the internet. The protocols in layer 2 are concerned with transferring data across nodes through the physical layer. The data link layer also has the important job of detection and correction of transfer/transmission errors that occured while the sent data was travelling through the physical layer.

d. If you could design a programming languages which would lend itself to any form of concurrent systems while also providing high level of abstraction, what would be the core language feature(s) which you would include?

https://learn.adacore.com/courses/intro-to-ada/chapters/tasking.html

A programming language that could lend itself to any form of concurrent systems must include:

1. Protected objects and entries. Essential for mutual exclusion and for the prevention of race conditions.
2. Tasks. Tasks are essential as many tasks can be run at the same time in a multithreading sense where tasks can run concurrently with many other tasks to perform certain operations.
3. Synchronization. This is essential to ensure tasks are able to execute one after another. It controls access to any shared resources needed by multiple tasks. Without it, tasks could modify shared/global variables while another thread is still using it, leading to race conditions and potential deadlocks.
4. Rendezvous. When synchronous and asynchronous message passing is combined, it leads to a very robust and set form of concurrent programming.

2. Synchronization and Communication

a. In the context of concurrent programming explain what is meant by a race condition? Include in your answer 20 lines or less of pseudo code that shows a race condition.

https://sworthodoxy.blogspot.com/2020/01/ada-concurrency-avoiding-race-conditions.html

A race condition occurs where the behaviour of a system/environment is completely dependent on the sequence, timing, or scheduling of other events/tasks. A race condition that leads to undesirable, incorrect or dangerous results is dangerous and all efforts should be made to ensure that no race conditions can occur. This is usually done through mutual exclusion and the inclusion of critical and non-critical sections.

procedure race_condition is
    Variable : Natural := 0;

    procedure Increase is
    begin
        Variable := Variable + 1;
    end Increase;

    task type Looper;

    task body Looper is
    begin
        for I in 1 .. 1000 loop
            Increase;
        end loop;
    end Looper;

begin
    declare
        Task1 : Looper;
        Task2 : Looper;
        Task3 : Looper;
    begin
        null;
    end;
end race_condition;

In the code above, it can be seen that a single global variable is added to by 3 individual tasks, the resulting mess is a set of non-deterministic sums which do not resemble the actual, correct answer.

b. Emulate asynchronous message passing by means of synchronous message passing. Identify the limitations of your design (if there are any). You can provide your answer in any programming language of your choice (including pseudo-code). You can also add a diagram.

https://www.cse.chalmers.se/edu/course/TDA384_LP1/lectures/ https://www.cse.chalmers.se/edu/course/TDA384_LP1/files/lectures/Lecture12-models_languages.pdf https://www.cl.cam.ac.uk/teaching/1011/CDSysI/05-IPC.pdf https://www.adaic.org/resources/add_content/standards/95rat/rat95html/rat95-p2-9.html

Ada style pseudocode

procedure Main is
declare
    Queue : Queue_Type;

    procedure send_message (Message: Message_Type) is
    begin
        Message.Destination.accept_message(Message);
    end send_message;

    procedure accept_message (Message: Message_Type) is
    begin
        
        if Message.Destination = this.Destination then
            this.recieve_message(Message);
        else
            Queue.Add(Message);
        end if;

        if Queue.Has_Element then
            Queue.Top.Destination.closest_neighbour.send_message(Queue.Top);
        end if;

    end accept_message;

    procedure recieve_message (Message: Message_Type) is
    begin
        Message.consume;
    end recieve_message;

    

begin
    ... Creation of lots of tasks and sending, accepting and reciving of messages as described above.
end Main;

3. Selective Synchronization

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

There are two task queues. Worker and Server. These are queues as they allow for accepting and/or requeuing of tasks.

ii. Considering the program structure, which of the entries in this program would you consider to be potentially blocking for a non-trivial amount of time? Assume that your underlying hardware supports running all concurrent entities in this program in parallel.

The Service entry would be potentially blocking for a non-trivial amount of time. The reason is that as it is selecting a worker in Workers'Range, there could be a Workers (i).Ready that isn't ready, as such it would not continue and requeue the Worker (i).Service but would lock waiting for the Worker to be ready.

iii. Will this program never / sometimes / always terminate? Explain your answer.

4. Safety and Liveness

a. Does the exclusive usage of synchronous message passing prevent deadlocks? Give precise reasons why it would be free of deadlocks or a counter-example if you can construct a deadlock situation using only synchronous message passing.