Exam: Modelling Complex Software Systems (SWEN90004_2022_SM1)
Started: Jun 6 at 15:01
Quiz Instructions
Academic Integrity Declaration
Copyright By PowCoder代写 加微信 powcoder
By commencing and/or submitting this assessment I agree that I have read and understood the University¡¯s policy on academic integrity. (https://academicintegrity.unimelb.edu.au/#online-exams)
I also agree that:
1. Unless paragraph 2 applies, the work I submit will be original and solely my own work (cheating);
2. I will not seek or receive any assistance from any other person (collusion) except where the work is for a
designated collaborative task, in which case the individual contributions will be indicated; and,
3. I will not use any sources without proper acknowledgment or referencing (plagiarism).
4. Where the work I submit is a computer program or code, I will ensure that:
a. any code I have copied is clearly noted by identifying the source of that code at the start of the program or in a header file or, that comments inline identify the start and end of the copied code; and
b. any modifications to code sourced from elsewhere will be commented upon to show the nature of the modification.
Introduction – Concurrency
The first half of the exam contains questions on modelling concurrent systems. It contains:
12 multiple choice / multiple answer questions, each worth 2.5 marks (30 marks total) 3 longer questions (one with 3 parts), each worth 10 marks (30 marks total)
You should attempt all questions.
Note that where multiple questions relate to the same scenario, model or code, this will be provided at the beginning of each question for convenience.
Question 1 2.5 pts
Interleaving is an abstraction that helps us to analyse the behaviour of concurrent systems. Which of the following statements about the interleaving abstraction is not true?
Question 2 2.5 pts
Two processes each execute the following sequences of instructions, in order, before halting.
You may assume that each instruction is an atomic event.
Select all of the possible interleavings of these sequences from the following list.
pip, inc, drop, bet, set set, pip, inc, drop, bet inc, pip, bet, set, drop pip, bet, set, inc, drop
HADES : pip, bet, drop
IMP : inc, set
Question 3 2.5 pts
Debugging concurrent systems is particularly challenging because of which property?
non-determinism synchronization liveness parallelism
It ensures predictable behaviour.
It ignores real time.
It enables us prove correct behaviour.
It assumes only one event happens at a time.
Question 4 2.5 pts
Question 5 2.5 pts
A semaphore S is initialised as (6, {}) (ie, with 6 access permits).
S.wait() is executed 3 times, following which S.signal() is executed 6 times. How many access permits does S have after this?
A cargo port contains 4 container ships. Each ship requires 2 tugboats in order to dock or undock. What is the minimum number of tugboats that will prevent deadlock from occurring (ie, no container ship being able to acquire the required number of tugboats)?
Question 6 2.5 pts
Two processes P and Q share access to an Boolean variable x and a binary semaphore S:
Question 7 2.5 pts
Three concurrent processes P, Q and R each execute a critical section of code within which shared variables are accessed and modified. The processes use four binary semaphores named a, b, c and d (each initialised to 1) to control access to the critical section.
Semaphores are obtained one at a time, by executing wait().
Process P needs to obtain semaphores a, b and c to execute its critical section.
Process Q needs to obtain semaphores b, c and d to execute its critical section.
Process R needs to obtain semaphores c, d and a to execute its critical section.
After it finishes executing its respective critical section, a process releases all three semaphores, by executing signal().
In which order should each process acquire their semaphores to prevent deadlock from occurring?
P: b, a, c; Q: b, c, d; R: a, c, d P: a, b, c; Q: b, c, d; R: c, d, a P: b, a, c; Q: c, b, d; R: a, c, d P: a, b, c; Q: c, b, d; R: c, d, a
We assume a fair scheduler, such that each process will eventually finish running its code. Which of the following outputs is not possible?
Question 8 2.5 pts
In Java, monitors can be used to encapsulate data shared by multiple processes. Which of the following problems does a monitor not prevent?
race conditions
FSP Scenario A
The following three questions all relate to the same FSP model, shown below:
Note that later questions do not depend on earlier questions and can be answered independently.
interference “busy-waiting”
Question 9 2.5 pts
Consider the following four Finite State Processes:
Question: Which of the following (partial) traces can not be executed by the process DAVE?
… ¡ú eat ¡ú leave ¡ú argue ¡ú play ¡ú …
… ¡ú eat ¡ú play ¡ú argue ¡ú leave ¡ú …
… ¡ú wake ¡ú eat ¡ú play ¡ú argue ¡ú …
… ¡ú argue ¡ú leave ¡ú wake ¡ú argue ¡ú …
Question 10 2.5 pts
Consider the following four Finite State Processes:
Question: Which of the following (partial) traces can not be executed by the composite process DAVE || ROGER?
… ¡ú eat ¡ú play ¡ú rest ¡ú leave ¡ú … … ¡ú wake ¡ú argue ¡ú play ¡ú rest ¡ú … … ¡ú rest ¡ú eat ¡ú leave ¡ú wake ¡ú … … ¡ú leave ¡ú wake ¡ú eat ¡ú play ¡ú …
Question 11 2.5 pts
Consider the following four Finite State Processes:
Question: Which of the following composite processes will not deadlock?
DAVE || RICK DAVE || ROGER ROGER || RICK ROGER || NICK
Question 12 2.5 pts
Consider the following Labelled Transition System (LTS):
The composite process ||HOUSE = (ANNA || BINH || CATO).
Which of the following Finite State Process (FSP) models corresponds to the LTS above? A:
FSP Scenario B
Consider an alternative model for the Foyer of the Museum of Parallel and Concurrent Art from Assignment 1. In this model, a security guard is still responsible for ensuring that only one tour group is present in the foyer at a time. Tour groups must wait in line to enter
( joinEntryLine ) and to leave ( joinLeaveLine ) the foyer. Each line has a maximum length of two tour groups. Tour groups can only enter or leave when they are given permission by the guard.
The FSP model below describes this system. Study the model and answer the following questions. Note that later questions do not depend on earlier questions and can be answered independently.
Question 13 3 pts
(This question relates to FSP Scenario B, shown above)
The model as specified above enforces the constraint that only zero, one or two groups can be in a line at a time. However, we can imagine a more general model that would allow a larger number of groups to join a line (ie, where MaxID was greater than two). Write down a general safety property that would ensure that would ensure that there was always a valid number of groups in the entry line.
Edit View Insert Format Tools Table
0 words
12pt Paragraph
Edit View Insert Format Tools Table
Question 14 2 pts
(This question relates to FSP Scenario B, shown above)
Write down a linear temporal logic (LTL) formula that specifies that all tour groups that join the departure line will eventually leave the Museum.
Edit View Insert Format Tools Table
12pt Paragraph
Question 15 5 pts
(This question relates to FSP Scenario B, shown above)
There is a liveness problem with this version of the model.
(i) [2 marks] Briefly describe the problem.
(ii) [2 marks] Write an LTL formula that would detect this problem. (iii) [1 mark] Describe the formula you wrote in a single sentence.
Edit View Insert Format Tools Table
12pt Paragraph
0 words
0 words
Question 16 10 pts
A store sells packets of rapid antigen tests (RATs) that enable people to quickly self-test for COVID-19. The store stocks up to five packets at a time (T = 5). Three customers (C = 3) buy packets from this store. Due to shortages, customers can only buy one packet at a time.
When the store runs out of packets, the supplier restocks it up to its maximum capacity of five packets.
The manager opens and closes the store. Customers and the supplier can only visit the store while it is open. However, while the store is closed, a thief can break in and steal all the remaining packets that are in stock before escaping.
The store is initially open and fully stocked.
Write down the FSP processes required to model this system, including a composite process ||SYSTEM.
Edit View Insert Format Tools Table
12pt Paragraph
0 words
Question 17 10 pts
At a swimming pool, safety regulations require that there must always be at least one parent present for every R children who are swimming. That is, for R = 3, if no parents are present, then no children may be swimming. If one parent is present, then there may be none, one, two or three children swimming. If two parents are present, then up to six children may be swimming, and so on. Conversely, if there are one, two or three children swimming, then there must be at least one parent present, and so on.
A FSP model describing the components of this system is outlined below.
Provide a Java implementation of the POOL process (as a class Pool). Your classes should define or make use of methods corresponding to the actions in the FSP model (ie, childArrive, childDepart, parentArrive, parentDepart, etc).
Note: you only need to provide implementations for the class specified. You are not required to implement other classes or a main() method.
Edit View Insert Format Tools Table
12pt Paragraph
Introduction – Complex Systems
The second half of the exam contains questions on modelling complex systems and Petri nets. It contains:
1×10 marks longer text answer question and 2×5 marks shorter text answer question (20 marks total)
4 multiple answer questions (2×5 marks, 1×3 marks, 1×2 marks, 15 marks total)
12 multiple choice questions (11×2 marks and 1×3 marks , 25 marks total)
You should attempt all questions.
Question 18 2 pts
Mark all statements that hold true for a cellular automaton.
An automaton can represent the spatial aspects of the system.
An automaton can be Turing complete.
An automaton is suitable for analytical analysis.
An automaton uses the global environment to update the current state. The states of the constituting cells are independent.
An automaton can be three-dimensional.
p 0 words
Question 19 3 pts
A system is chaotic if it displays these properties (mark all correct answers):
The dynamic update rule can uniquely determine the next state of the system based on its current state.
The dynamic update rule uses all the history of the system evolution and stochastic mechanisms to determine the next state of the system.
The system never returns to a state it was in before.
The system can sometimes return to one of the states that it was previously in.
The number of different states the system can be in is bounded by some, potentially huge number.
At any point in time, the state of the system is drawn from some bounded range.
If the initial state of the system is changed a bit, the trajectory of its future states will be completely different.
If the dynamic update rule of the system is changed a bit, the trajectory of its future states will be completely different.
Question 20 10 pts
(a) Discuss three benefits of describing a complex system as a mathematical model. [3 Marks]
(b) Give one example of a mathematical model of a complex system that we studied in the class and discuss the parameters and rules of this model. [2 Marks]
(c) Give one example property of the system that one can study using the mathematical model you discussed in Part (b). [2 Marks]
(d) Propose one extension of the model from Part (b) to make it better reflect the corresponding real-world system. [3 Marks]
Edit View Insert Format Tools Table
12pt Paragraph
Question 21 5 pts
Explain what is a function and what is an iteration. How can one use functions and iterations to model complex systems? Discuss an example model that uses functions and iteration to describe a complex system.
p 0 words
Question 22 5 pts
Give an example of a complex system and explain how it exhibits self-organisation.
Question 23 2 pts
Which of the listed models does not resemble a model of a chaotic system?
The logistic map with parameter r = 3.84.
The Lorenz attractor of the Lorenz system of ordinary differential equations. 1D cellular automaton with the dynamic update rule number 126.
A deterministic, aperiodic, bounded, and sensitive to initial conditions system.
Question 24 2 pts
Which of the listed models of complex systems is not an example of a mathematical model, and thus cannot be solved analytically?
The Lotka-Volterra model
The logistic map
The basic SIR model
The deterministic version of the basic SIR model
Question 25 2 pts
Consider the ordinary differential equations and the parameters of the Lotka-Volterra model that describe the dynamics of the predator-prey model shown below.
Question 26 2 pts
Which statement is not correct about the phase plane of the evolution of the Lotka-Volterra model?
The phase plane represents predator and prey populations over time.
A point on the phase plane encodes predator and prey populations.
The population trajectories evolve in the counter clock direction.
The population trajectories always form a continuous curve without start or end.
What will the behaviour of the system be in the absence of rabbits?
The fox population will decay linearly.
The fox population will grow.
The fox population will decay exponentially. The fox population level will reach an attractor.
Question 27 2 pts
Question 28 2 pts
Two parameters govern the basic SIR model:
1. A probability (q) for a susceptible person becoming infectious on the next day after meeting an infectious person, and
2. A probability (p) for an infectious person to recover on the next day.
What will be the expected behaviour of the system if q is very high and p is very low?
The epidemic will most likely not happen.
The epidemic will happen and impact a large share of the population. The epidemic will most likely impact a large share of the population.
The epidemic will proceed in waves in terms of high and low numbers of simultaneously infectious people.
In the basic SIR model, which two possible events can occur to a single person?
If a person is susceptible and meets an infectious person, they may become infected. An infectious person recovers.
If a person is susceptible and meets an infectious person, they become infected. An infectious person may recover.
An infectious person can recover. If a person is susceptible and meets an infectious person, they can become infected.
A recovered person may get infectious. If a person is susceptible and meets an infectious person, they may become infected.
Question 29 2 pts
Consider the 1D cellular automaton and the update rules shown below.
Question 30 2 pts
How many possible neighbourhood states and rules for updating 1D cellular automaton exists if a cell of the automaton can be in one of eight states, and the size of neighbourhood considered for state updates is equal to three?
6561 possible neighbourhood states and approximately 2.41 x 10^462 possible update rules. 6561 possible neighbourhood states and approximately 2.47 x 10^3130 possible update rules. 512 possible neighbourhood states and approximately 2.41 x 10^462 possible update rules. 512 possible neighbourhood states and approximately 2.47 x 10^3130 possible update rules.
What will be the next state of the automaton?
1011010110001001 0011010110001000 0100101001110110 1011011110101001
Question 31 2 pts
Consider three neighbourhoods of the cell in the middle shown below. If black cells are alive and white cells are dead, according to the rules of Conway¡¯s Game of Life, what will happen to the cell in the middle in the next generation?
Question 32 2 pts
Which statement is not true about Petri net systems?
In general, two net systems that describe the same collection of distributed runs can describe
different collections of sequential runs.
In general, a place of an elementary net system can hold any number of tokens.
In general, an elementary net system can describe an infinite number of reachable markings. In general, an elementary net system can describe an infinite number of sequential runs.
(a) dies, (b) dies, and (c) comes alive
(a) survives, (b) dies, and (c) comes alive
(a) survives, (b) survives, and (c) comes alive (a) survives, (b) dies, and (c) stays dead
Question 33 5 pts
Mark all properties that do not hold for the workflow system shown below.
Option to complete Proper completion No dead transitions Soundness
Question 34 5 pts
Mark all properties that hold for the workflow system shown below.
Option to complete Proper completion
Question 35 2 pts
How many reachable markings does the net system shown below describe?
12 9 10 11
No dead transitions Soundness
Question 36 3 pts
Which marking of the net structure shown below results in a net system that describes a sequential run in which transitions occur in this order (from left to right): b, a, b, c, a, b, d, d, d?
ABEHHH BDEHHH AEGHHH ABEEHH
Saved at 15:01
Submit Quiz
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com