# COMP2310/6310 2021 S2 Final Exam
This file contains the questions for the 2021 Final Exam.
Copyright By PowCoder代写 加微信 powcoder
There are six questions worth different marks, for a total of 100 marks.
Please make a local clone of this repository to work on.
Answer each question by editing the markdown file provided for that question.
When you have completed a question, commit and push the file to GitLab.
You have **3 hours and 30 minutes** to complete the exam.
This exam is open-book, meaning you may refer to books, notes, and online references as you complete the exam.
All answers that you submit for this exam must be your own original work.
If you need to include material that is not your original work, it must be appropriately acknowledged and referenced.
You **must not** communicate with any person other than the examiners at any time during the exam.
Chat, text, email and all other such forms of communications must be turned off before the exam and must remain off for the duration of the exam.
**The penalties for cheating in an exam at ANU are severe.**
**Note**: this repository, including this README file, will be updated prior to the commencement of the exam. You should make a local clone of the repository now; at the start of the exam, you should pull the updates from GitLab. **Please do not make any changes to this repository prior to the exam**, as it may lead to Git merge problems that will waste valuable time. If this occurs, you will not receive additional time to complete the exam.
For all questions, you must clearly state all relevant assumptions on which your answer relies.
## Question 1: General Concurrency [20 marks]
### Q1.a [3 marks]
Compare and contrast Ada tasks and Unix processes. What are their similarities and differences?
### Q1.b [3 marks]
How do Dijkstra’s guarded commands differ from `switch` statements as in Java or C? Describe at least two differences.
### Q1.c [2 marks]
Suppose you define a boolean expression that must be true when all your concurrent processes are terminated. Could such an expression be regarded as a safety property or a liveness property? Must all concurrent programs fulfil such a termination condition? Give precise reasons for both answers.
### Q1.d [5 marks]
Does the following pseudocode provide an effective solution to the critical section problem? Give precise reasons.
type Waiting_Process is range 0..2; |
task body P1 is |
task body P2 is ### Q1.e [7 marks] This semester you have gained significant experience programming in the Ada language. ## 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: Three submissions from different students are shown below. All three submissions compile without warnings. Student A: task body Mailbox is Student B: task body Mailbox is Student C: task body Mailbox is (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. ### 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). – asynchronous send 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: #### 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; #### 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. What can you conclude about the timestamps *C(a)*, *C(b)*, *C(c)*, and *C(d)*? **This is the end of the exam.** 程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com |