College of Science – Computer Science CS-210 – Concurrency Release Time: 09:20 Tuesday 02/06/2020 (Time Zone: BST) Deadline: 17:20 Tuesday 02/06/2020 (Time Zone: BST) Alternative Assessment Information • This is an open-book assessment. This means you may consult your notes, textbooks, and other resources, including calculators, as you see fit. • You must submit before the deadline. Allow some spare time for technical submission issues. • This assessment is designed to take 2 hours to complete (maybe a little longer to account for typing speed). The deadline has been set to give you a longer window than necessary to allow you time to deal with technical issues, provide some flexibility of starting times, and to help students with disability access plans that require rest breaks and extra time. • It is suggested that you use Microsoft Word (or any other editor of your choice) to type your answers, then save as PDF when you are ready to submit. All submitted text must be word- processed, but you may include images (or photos of hand drawn images) as part of the document. • This is an individual assessment. Under no circumstances are you to discuss any aspect of this assessment with anyone; nor are you allowed to share this document, ideas or solutions with others using email, social media, instant messaging, websites, or any other means. Your attempts at these questions must be entirely your own work. Those found to have collaborated with others will receive a mark of 0. Special Instructions Answer all questions. Submission Instructions • Please submit a single PDF file named as your student number (e.g. 123456.pdf) via the submission link located on the module page in Blackboard/Canvas. By submitting, electronically and/or hardcopy, you state that you fully understand and are complying with the university’s policy on Academic Integrity and Academic Misconduct. The policy can be found at https://myuni.swansea.ac.uk/academic-life/academic-misconduct. Originator(s): Dr Alma Rahat In case of queries email both: [email protected] [email protected] CS-210: Page 1 of 8 1. Please provide the term used to describe the following concepts: (a) How do you refer to a passive process that controls access to shared resources? [2 marks] (b) How do you refer to a property that states that “something good eventually happens”, i.e. progress is made despite potential concurrency issues? [2 marks] 2. Using Amdahl’s law, answer the following. (a) A particular (parallelised) program spends 55% of its time in its parallel part. Compute the bound on speedup possible with 16 cores. [2 marks] (b) In addition to improving performance in the parallel part, if the serial part is also optimised by a factor of 2, what is the combined bound of speedup in this case? [2 marks] (c) You are given the choice to either perform the optimisations above or to make the serial part five times faster without any speedup in the parallel part. What option would you go for? [3 marks] 3. (a) Consider the following scenario: A computer has two USB disk drives, and two processes that can cut and paste data between the drives and erase the origin. Now, if we use locking mechanism for writing and mutual exclusion, in the light of the necessary and sufficient (or Coffman) conditions, discuss how the above system may lead to deadlock. [4 marks] (b) Briefly propose a solution (keeping the locking mechanism) that would fix the above problem by breaking one of the Coffman conditions. You are not required to provide code. [2 marks] (c) Below we have provided you with a sample code for the UsbDrive class. Using the multiverse library, modify the code below to provide a software transactional memory (STM) solution to the deadlock problem. You are required to provide necessary Java code here. [6 marks] 1 import java.util.Date; 2 public class UsbDrive extends HardDrive{ 3 private Date lastUpdate; 4 private void updateDate (){ 5 lastUpdate = new Date(); 6 } 7 /* 8 * This is a simple method that reads from a UsbDrive 9 * object , and then copies the contents from a given 10 * address to the other UsbDrive object at a given 11 * address. It finally erases the origin. 12 * @param other The destination instance of UsbDrive. 13 * @param originAddress The address of the data in this instance of UsbDrive. 14 * @param destAddress The address of the data in destination. 15 */ 16 public void cutAndPaste(UsbDrive other , 17 int originAddress , 18 int destAddress){ 19 // read , write and erase methods are defined in superclass CS-210: Page 2 of 8 20 // they do not have any mechanism to ensure atomicity 21 byte[] data = read(originAddress); 22 boolean success = other.write(data , destAddress); 23 if (success){ 24 erase(originAddress); 25 updateDate (); 26 } 27 else{ 28 throw new java.lang.RuntimeException(“Write failed!”); 29 } 30 } 31 } 4. You are given the following class diagram of a Switch class. (a) Provide Java code for an implementation of the Switch class that implements the Runnable interface adhering to the class diagram and the following specifications: [3 marks] • The toggle method prints a message on the console showing the contents of name and isOn attributes, and if isOn is false then sets it to true, and vice versa. • The run method implements an infinite while loop within which it allows the thread to sleep for 500ms, and then call the toggle method. (b) Provide Java implementation of a main method with the following specifications: [3 marks] • It should have two instances of the Switch class named switch1 and switch2. • It should create two instances of Thread called thread1 and thread2, taking switch1 and switch2 as parameters respectively. • It should then start the two threads, and go to sleep for 5s. • It should then interrupt both threads, and wait for them to finish before exiting the program. CS-210: Page 3 of 8 5. (a) Using the resource allocation graph, discuss whether the system below will lead to deadlock or not. [4 marks] P1 P4 P2 P3 R2 R4 R1 R3 P5 R6R5 P6 (b) Below you are given a resource allocation graph for a system that is deadlocked. Referring to the processes, describe one method to recover from the deadlock. [2 marks] P1 P2R1 R2 P3R3 6. In a highly specialised lab, there are five computers. The lab Controller registers a student with a photographic ID, and allows the student to enter if there is at least one space left. Access is blocked if a student does not have an ID or the lab is full. A student in the lab can leave at any point in time. Given this scenario, answer the following questions. (a) Write the Finite State Process (FSP) code that models the system. [5 marks] (b) Specify a safety property in FSP that ensures that there are at most five users in the lab at any point in time, and check the Lab system. [5 marks] (c) Provide Java code for the monitor in this problem. [5 marks] CS-210: Page 4 of 8 Appendix A FSP Quick Reference A.1 Processes A process is defined by a one or more local processes separated by commas. The definition is terminated by a full stop. STOP and ERROR are primitive local processes. Example Process = (a -> Local), Local = (b -> STOP). Action Prefix -> If x is an action and P a process then (x->P) describes a process that initially engages in the action x and then behaves exactly as described by P. Choice | If x and y are actions then (x->P|y->Q) describes a process which initially engages in either of the actions x or y. After the first action has occurred, the subsequent behavior is described by P if the first action was x and Q if the first action was y. Guarded Action when The choice (when B x -> P | y -> Q) means that when the guard B is true then the actions x and y are both eligible to be chosen, otherwise if B is false then the action x cannot be chosen. Alphabet Extension + The alphabet of a process is the set of actions in which it can engage. P + S extends the alphabet of the process P with the actions in the set S. Table A.1 – Process operators A.2 Composite Processes A composite process is the parallel composition of
one or more processes. The definition of a composite process is preceded by ||. Example ||Composite = (P || Q). Parallel Composition || If P and Q are processes then (P||Q) represents the concurrent execution of P and Q. Replicator forall forall [i:1..N] P(i) is the parallel composition (P(1) || … || P(N)) Process Labeling : a:P prefixes each label in the alphabet of P with a. Process {a 1 ,..,a x }::P replaces every label n in the alphabet of CS-210: Page 5 of 8 Sharing :: P with the labels a 1 .n,…,ax.n. Further, every transition (n->Q) in the definition of P is replaced with the transitions ({a 1 .n,…,ax.n}->Q). Priority High << ||C =(P||Q)<1 ,…,a n } specifies a composition in which the actions a 1 ,…,a n have higher priority than any other action in the alphabet of P||Q including the silent action tau. In any choice in this system which has one or more of the actions a 1 ,…,a n labeling a transition, the transitions labeled with lower priority actions are discarded. Priority Low >> ||C=(P||Q)>>{a 1 ,…,a n } specifies a composition in which the actions a 1 ,…,a n have lower priority than any other action in the alphabet of P||Q including the silent action tau. In any choice in this system which has one or more transitions not labeled by a 1 ,…,a n , the transitions labeled by a 1 ,…,a n are discarded. Table A.2 – Composite Process Operators A.3 Common Operators The operators in Table A.3 may be used in the definition of both processes and composite processes. Conditional if then else The process if B then P else Q behaves as the process P if the condition B is true otherwise it behaves as Q. If the else Q is omitted and B is false, then the process behaves as STOP. Re-labeling / Re-labeling is applied to a process to change the names of action labels. The general form of re-labeling is: /{newlabel_1/oldlabel_1,… newlabel_n/oldlabel_n}. Hiding \ When applied to a process P, the hiding operator \ {a 1 ..ax} removes the action names a1..ax from the alphabet of P and makes these concealed actions “silent”. These silent actions are labeled tau. Silent actions in different processes are not shared. Interface @ When applied to a process P, the interface operator @{a 1 ..ax} hides all actions in the alphabet of P not labeled in the set a 1 ..ax. Table A.3 – Common Process Operators A.4 Properties Safety property A safety property P defines a deterministic process that asserts that any trace including actions in the alphabet of P, is accepted by P. Progress progress progress P = {a 1 ,a 2 ..a n } defines a progress property P which asserts that in an infinite execution of a target system, at least one of the actions a 1 ,a 2 ..a n will be executed infinitely often. CS-210: Page 6 of 8 Table A.4 – Safety and Progress Properties A.5 FLTL – Fluent Linear Temporal Logic Fluent fluent fluent FL = 1 ,…s n }, {e 1 ..e n }> initially B defines a fluent FL that is initially true if the expression B is true and initially false if the expression B is false. FL becomes true immediately any of the initiating actions {s 1 ,…s n }occur and false immediately any of the terminating actions {e 1 ..e n } occur. If the term initially B is omitted then FL is initially false. Assertion assert assert PF = FLTL_Expression defines an FLTL property. && conjunction (and) || disjunction (or) ! negation (not) -> implication ((A->B)º (!A || B)) equivalence ((AB) º(A->B)&&(B->A)) next time X F iff F holds in the next instant. always []F iff F holds now and always in the future. eventually <>F iff F holds at some point in the future. until P U Q iff Q holds at some point in the future and P holds until then. weak until P W Q iff P holds indefinitely or P U Q forall forall [i:R] FL(i) conjunction of FL(i) exists exists [i:R] FL(i) disjunction of FL(i) Table A.5 – Fluent Linear Temporal Logic CS-210: Page 7 of 8 End of Paper CS-210: Page 8 of 8
