COMP2310 2015 Final

1. General Concurrency

a. Give three examples of hardware components that support concurrency.

1. CPU
2. Computer Network
3. Distributed OS

b. What will be the output (or the possible outputs) of the following concurrent program? Give precise reasons for your answer. If you need to make assumptions about the underlying operating system, runtime environment or hardware then state those assumptions as well.

with Ada.Text_IO; use Ada.Text_IO;
procedure x_Value is
    x : Positive := 1;
    task One;
    task body One is
    begin
        x := x + x;
    end One;

    task Two;
    task body Two is
    begin
        x := x + x;
        end Two;
begin
    Put (Positive’Image (x));
end x_Value;

c. How does a block of Dijktra’s guarded commands differ from a switch statement as you find it in Java or C? Name at least two essential differences.

With Java/C, select statements work downwards. The difference occurs because Dijktra's guarded commands choose an option nondeterministically as opposed to Java/C which select the first statement that meets the criteria.

The other difference is the option to include do, and if-else logic within the guarded commands. Java/C select statements only select based on the boolean evaluating expression provided in the statement.

d. How does a forall statement (as in Chapel) differ from a for statement as you find it in Java or C? Be as precise as you can.

forall in Chapel runs the commands in parallel by design. This is contrasted with Java or C where doing a for (List x : element y) will work through the list sequentially. As such using forall will lead to faster evaluation/computation times compared to Java or C.

e. If you define a boolean expression which is true when all your concurrent processes are terminated could such an expression be regarded as a safety or a liveness property? Do all concurrent programs have to fulfil such a termination condition? Give precise reasons for both answers.

If a boolean is defined after all concurrent processes are terminated, it would be regarded as a liveness property as it is asserting something good (true value) eventually happens. However, all concurrent programs would not have to fulfil such a termination condition because the process has already terminated and the boolean expression occurs after it not during.

2. Synchronization and Communication

a. Can synchronous message passing systems emulate asynchronous message passing? Can asynchronous message passing systems emulate synchronous message passing? For both questions provide either a reason why this is not possible or a diagram which is depicting how it could work. If it is only possible under certain assumptions then also state those assumptions.

Yes, synchronous message passing systems can be emulated using asynchronous message passing. This is because both processes could suspend themselves until the interaction is completed. Because no direct/immediate communication between the two occurs, they are never synchronized. The sender would know when the interaction is completed, but not the reciever.

For asynchronous message passing systems, the introduction of an intermediate processes can emulate the sense of synchronisation. This is because the intermediate message will be accepting messages at all times (+ messages sent out on request). While the sender and reciever would be blocked in the sense of sycnhronous message passing they are not delayed because the intermediate is always ready.

b. Define a general semaphore (as offered by an operating system) precisely. Only the defining characteristics are asked for here – not the additional convenience functions which might be offered as well by an operating system.

n/a

c. Can you program a semaphore if your programming language does not provide one? If you need to make assumptions to answer this question then explain them here as well.

n/a

d. Which problematic issues with semaphores are resolved by monitors? Which issues are not? Explain at least one resolved and one unresolved issue.

https://www.geeksforgeeks.org/monitor-vs-semaphore/

Mutual exclusion with monitors is automatically done as opposed to needing to be manually implemented explicitly in a semaphore. Monitors can also overcome any timing errors as they do not need to flip variables around to allow/block. A sempahore must also be shared globally, but monitors can be hidden to all other processes.

Semaphores however are more independent and not machine dependent as checks are implemented via kernel services. They are also more resource efficient and can prevent sources of busy waiting.

4. Selective Concurrency

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

i. Explain the usage and the meaning of the initialization values of the individual semaphores. What minimum and maximum values can each Semaphore reach?

The initialisation value can reach a minimum of 0 (positive type) and can reach $2^31 - 1$ as the max positive value.

ii. Can any data be accessed in an unsynchronized way? If so, point out where this can happen and how you would prevent this.

No, no data can be accessed in an unsynchronized way as there is a semaphore operation before any such data operation. The semaphore would prevent any such unsynchronized data operations from occuring.

iii. Are there any possibilities for deadlocks in the operations Push, Pop, Is_Empty or Is_Full? If so, point out where this could happen and how you would prevent this.

No, there are no possibilities for deadlocks in the operations as it would not be possible for a task to be stuck inside of any of those operations waiting. This is because the semaphore operation is the first to be done for each step and as such no amount of interleaving would be possible to cause the operations to be interleaved in such a way to allow one operation to wait on another while accessing two different bits of data because only the first (fastest) operation would reach and accept the semaphore, stopping the others.

5. Data Parallelism

a.