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:
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)<<{a
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 = <{s
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 ((A<->B) º(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