Some final exam feedback
The final exam was set to make you think and reflect. It was meant to provoke you to look at the bigger picture and combine the different topics. I hope that worked for you.
Quite a few students did not read the questions carefully enough. Some attempted to answer questions with direct quotes from the lecture or elsewhere. The method of picking up keywords, look them up, and dump on us whatever you found, is a waste of everybody's time and won't result in marks obviously. The idea of an exam question is that you reflect on the material and provide a concise response.
Some specific feedback for individual questions.
**1. [15 marks] General Concurrency
(a) [9 marks] Concurrent programming languages will always provide some form of concurrent
- Their names vary widely (in Ada for instance they are called tasks), or
- may not be mentioned at all as part of the syntax. Yet in all cases, the compiler
will need to provide an implementation of those concurrent entities.
(i) [3 marks] What are the options for the compiler designer to implement the concurrent
entities of a concurrent programming language? Describe each option briefly.**
(ii) [6 marks] What are the advantages and disadvantages of each option?
- The questions are all about implementation - not language design. The question already explains that different languages may provide concurrency in different forms, so it is not about those forms, but about how to implement them on an actual machine.
- Many way to answer here. You could elaborate on the different ways to connect or ignore operating systems, or you could dive into hardware options. Either path gains you full marks.
(b) [6 marks] Which forms of hardware are supportive or required for the concurrent
execution of your code? Enumerate them and discuss their impact on the performance
of your programs briefly. Also state what needs to be done so that they can perform
- A rather easy question actually, which most of you got mostly right.
- There were again weaknesses in reading the question by some students though: The question explicitly asks what the impact on performance is for those hardware options (and how to gain that performance). So just dumping hardware options on us is not what the question is about.
2. [31 marks] Message Passing
(a) [23 marks] In an assignment, students were asked to provide a solution for a message
buffer task, which provides the following properties: The buffer task shall ...
(i) [15 marks] Evaluate all three student submissions with the form below. Tick all
properties (by writing "x") which have been successfully implemented and provide
detailed feedback for improvements if the solution falls short of expectations.
- I thought this was an easy question. Turns out it wasn't.
- You gain 15 (!) marks just for reading short code fragments and understanding what they do. My expectation was that you look into those code fragments carefully and in detail as you have been given ample time to do so (with relation to the marks gained).
- In terms of number of ticks per program, the first one gains the most! It does everything which has been asked for without unnecessary blocking or idling. The only tick missing is for the buffer size to be more than 1.
- The second option makes things worse by introducing busy waiting without any further gain.
- The last option is still stuck in busy waiting and introduces uncalled blocking at the same time. So that one will gain the least ticks - but gains a tick for the buffer size being more than 1.
- This was not hard to analyse, yet very few students took the time to look into those fragments carefully enough to evaluate them properly. This makes me think weather we are not doing enough for your skills to read programs. It could also be of course that many students, simply underestimated the question and took a guess. More often than not this is leading to a completely wrong conclusion, as programs often do very different things than what they look like on first glance.
(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
pseudo code) to implement a buffer, which fulfils all required properties, and is based
on synchronous message passing. If you find one of the student submissions already
fulfils all requirements, then nominate that one for full marks.
- Those were relatively easy 8 marks and most students gained them.
- You need to understand that the main shortcoming of the previous student fragments is that they either have a too small buffer size (so, yes, the solution will need some internal storage which is more than a scalar), and it does require concurrency (e.g. a second task which can do the sending).
- The busy waiting surely needs to be removed (so no more select-else constructs).
- While not the most efficient solution, you can also chain up the single buffer solution A into a chain of tasks passing the message along. Still gains you full marks.
(b) [8 marks] Assume that a concurrent programming language does not provide you with
a synchronous message passing, but with some form of asynchronous message passing.
This could be a synchronous queue or a maybe a completely asynchronous message
(i) [8 marks] Construct a synchronous message passing system. Use any programming
language of your choice (including pseudo code). You should provide two methods,
function, procedures, subroutines, processes, threads, or tasks (depending on
the language of your choice and your design) to provide a synchronous sending and a
synchronous receiving operation respectively. State your assumptions about the asynchronous
message passing system which you use as a foundation.
- Many ways to provide an answer.
- Both tasks need to be waiting on each other.
- Tasks can only progress once both know that the message has been transmitted.
3. [20 marks] Data Parallelism
(a) [12 marks] Some programming languages provide "implicit concurrency". While it is
good to automate things, it is also good to understand what is going on.
(i) [4 marks] Will implicit concurrency always, sometimes or never add synchronization
mechanisms (like locks) to your code? Give precise reasons for your answer.
- Branching off into concurrent threads usually means that they need to be combined again before the next sequential statement can be executed. They all produce results and the compiler needs to make sure that all those results are available before they are being read. So ... yes, this means synchronization
- There are rare exceptions of that, e.g. when code branching off into vector operations which are all guaranteed to be completed after a certain number of CPU cycles.
- So both "always" as well as "sometimes" gains full marks with the correct rationale.
(ii) [4 marks] Can or will implicit concurrency take full advantage (in terms of maximal
performance for your program) of all existing hardware? Give precise reasons for your
- Can be argued either way. Again the rationale will gain you marks, not a yes/no answer.
(iii) [4 marks] Can implicit concurrency lead to unsafe code (for example: race conditions)?
Give precise reasons for your answer. Which assumptions did you make to
answer this question?
- Also a question which doesn't have a correct yes/no answer. Some implicit concurrent languages will be restricted enough to be unable to introduce unsafe code (by means of implicit concurrency), yet some are more flexible. Chapel for instance is on the flexible side and can produce unsafe code quite easily.
- You again gain full marks with a sensible argument.
(b) [8 marks] Write a program to implement the discrete cross-correlation function (as a
discrete array) between two cyclic, discrete functions (which are themselves represented
by discrete arrays) which optimizes for performance on an 8-core CPU with vector
processing units (processing 8 16-bit integer numbers per vector operation):
- Many ways to solve that.
- Explicit solutions will require management of tasks and combining results.
- Implicit solutions will require a precise list of assumptions about the language.
- The assumption, "I call the Cross-Correlation function and the compiler does everything for me automatically and perfect" is a step too far though :)
4. [11 marks] Scheduling
(a) [11 marks] The CPU scheduler on the computer which you are using right now has
been carefully designed and optimized over decades. Let's have a closer look:
(i) [5 marks] What can your operating system know about the processes running on
**(ii) [3 marks] What information could your scheduler use to make a good decision of
what to schedule next?**
**(iii) [3 marks] What do you assume your scheduler will optimize for specifically, and
how will it do that?**
- Some students ignored the two "you", "using right now" and "your" details in the question, and a generic copy-n-paste from elsewhere does not answer this question.
- We do not expect you to know those things by heart, but we expect you to take an educated guess about what is reasonable.
- Generally, neither you nor your computer will know how long programs take for instance. You and your computer do always know however how long something took so far for instance.
5. [11 marks] Distributed Systems
(a) [11 marks] Mutual exclusion in distributed systems via Token Ring structures have
been discussed in the lectures, yet we did not provide a concrete implementation to
illustrate the method. Read the following Ada code carefully. It is syntactically correct
and will compile without warnings.
The provided code is intended to illustrates mutually exclusive access (reading and
writing) to a shared variable in an ongoing sequence of accesses from all tasks (the
program is not designed to terminate). Current_Task (from Ada.Task_Identification)
provides the Task_Id of the currently running task, i.e. the task calling Current_Task.
(i) [2 marks] Will this program provide ongoing output? Or will it crash, dead-lock, or
live-lock? Give detailed reasons for your answer.
- Most of you spotted the obvious deadlock and put their finger on it.
(ii) [3 marks] Does this code actually provide mutually exclusive access to the shared
variable while also keeping all tasks running concurrently while they are not accessing
this shared variable? Give detailed reasons for your answer.
- This one was as obvious (or so I thought), but much less student spotted the unprotected access right before the accept Token statement.
- This read access happens completely unprotected, and while some students argued that concurrent reads are fine, there is no guarantee that some other task did not already get the token and writes happily - while another task is reading. There is also not hint that Task_Id would be word sized, so arguments along those lines rest of strong assumptions.
- I was a little disappointed that your senses to press the alarm knob for any unprotected access are apparently not yet sharp enough.
(iii) [6 marks] If you find the provided code lacking in some respect, please provide
an alternative implementation below. Use any programming language of your choice
(including pseudo code), that is based on synchronous message passing. If you find the
provided implementation to be perfect, than nominate it for full marks.
- Minor corrections of the code take care of both issues.
6. [12 marks] Networks & Time
(a) [6 marks] What OSI network layer 1 (physical layer) interfaces do you find in your
computer? Enumerate them and name the network protocols which are utilizing those
interfaces (for some you cannot know the associated protocols, so leave that open).
Hint: not all of those interfaces will be accessible to you directly. We do not expect you
to actually know all of them, but we expect you to be able to take an educated guess of
what needs to be or will most likely be found in your computer.
- The question bifurcated mostly in two groups: those who couldn't imagine their computer having any interface beyond WiFi and possible Ethernet, and those students who enumerated long lists of things.
- Your computer is full to the brim with layer 1 interfaces. The job was just to reflect for a moment how much hardware there actually is and how this hardware possibly interfaces with the rest of your machine. As the question said, we do not expect you to know all the actual protocols, but we do expect you to understand that the gazillions of devices inside your computer will need to interact, i.e. there is always a physical layer and there is a protocol. ... you can tell that a student has not been reflecting when they claim to have TokenTalk or FDDI interfaces.
(b) [6 marks] Logical time (or Lamport time) is often preferred in computer applications
over wall-clock time.
(i) [3 marks] What are the advantages and disadvantages of logical time?
- Can be answered in many ways - most of you got it right.
(ii) [1 marks] What can you conclude if a process receives a message which has a logical
time stamp which is larger then the logical time of the current process?
- A few ways to answer that correctly.
- Basically, you do not conclude terribly much, but some things can be excluded.
(iii) [2 marks] What can you conclude if the logical time stamps of two events are identical?
- Pretty much everybody got that right - I just wanted to confirm this to be the case.