command do gc od executes repeatedly as the guarded command gc, while gc continues not to fail, and terminates when gc fails. (a) Assume that boolean and arithmetic expressions have no side effects and always terminate, and that the rules for their evaluation are given. Write down a collection of rules for an inductively defined evaluation relation of the form c, S ⇒ S 0 whose sense is "starting from the initial state S, the evaluation of the command c terminates at the final state S 0 ." [10 marks] (b) Give the commands in Dijkstra's guarded langcuage which simulate the standard imperative programming commands if b then c1 else c2 and while b do c respectively. You may assume that if b is a boolean expression, then so is ¬b, the negation of b. [2 marks] (c) Give an appropriate definition of semantic equivalence of commands with respect to the evaluation relation defined in (a). Prove that for any boolean expression b and any [] ¬b → skip fi [8 marks] 7 [TURN OVER CST.94.7.8 14 Concurrency Define what is meant by observational equivalence of CCS agents. [5 marks] A transmitter T, transmission medium M, and receiver R are modelled by CCS agents with the following definitions: T def = in.i.T0 T 0 def = r.i.T0 + a.T M def = i.M0 M0 def = o.M + τ.r.M R def = o.out.a.R M is an unreliable medium: having received an input message fro

c

 

m T (action i) it either outputs the message to R (action o), or loses it (represented by the τ action) and then sends a request for retransmission (action r). If R does receive the message, after broadcasting it (action out) it sends an acknowledgement directly to T (action a). Calculate the transition graph of (T|M|R) \ {i, o, r, a} and hence show that this agent is observationally equivalent to a simple buffer B with definition B def = in.out.B [10 marks] Are (T|M|R) \ {i, o, r, a} and B observationally congruent? [3 marks] Do the two agents have the same behaviour with respect to divergence, that is, the ability to perform a series of actions ending in an infinite sequence of τ -actions?

 Consider the following clauses: a(1). a(a). b(3). b(a). c(A,B) :- b(B),!,a(A). c(X,_) :- a(X),b(X). (i) List all the solutions to the query c(A,B) in order, giving any binding of variables that occurs. [2 marks] (ii) List all the solutions to the query c(X,1) in order, giving any binding of variables that occurs. [2 marks] (c) A binary tree has nodes whose values are non-empty lists. A tree node is represented using a term that takes the form Left-SomeList+Right or nil (note that parentheses can be used to enforce precedence). For example, the following term would be a valid tree: nil-[root,1,2]+(nil-[child,4]+nil) (i) Write a predicate preorder(+Tree,-ValueList) that unifies ValueList with a list containing all of the tree nodes' values from a pre-order tree walk (i.e. emit node value, then left subtree, then right subtree). The predicate should fail if any of the tree nodes' values are not of the correct form. For the above example tree, preorder/2 would unify ValueList with [[root,1,2],[child,4]]. You may assume that append/3 has been defined already. [6 marks] (ii) Now write a predicate preorderdl/2 that behaves exactly like your preorder/2 predicate, but in its implementation makes use of difference lists, instead of querying append/3. [6 marks] 8 CST.2011.3.9 9 Software Engineering (a) Describe the ks] (b) When discussing system development Fred Brooks says, "plan to throw one away - you will anyway". What disadvantages of the waterfall model is he referring to? Outline an alternative software development model that deals with these disadvantages. [7 marks] (c) You work for a large "social networking" company which has recently introduced a one-to-one chat mechanism, promising that they will never censor conversations. Users are now reporting that their friends' computers are being compromised by malicious software. When users click on links within messages sent by this malicious software, their machine is also compromised, and spreads the infection still further. A crisis meeting has decided that the chat software must be modified to block this "worm" behaviour. As manager of this project, how will you approach the development, how will you estimate how long the task will take, and how will you establish that your solution is safe to deploy

 

(a) Consider packet switching and circuit switching. In simple terms, packet
switching may allow more users to use the network.
We have N users sharing a 1 Mbit/s link. Each user consumes 100 kbit/s when
transmitting but only transmits for 10% of the time, on average.
(i) How many users would a circuit-switching system support? State your
assumptions. [1 mark]
(ii) For N = 40 users, the probability that more than 10 users are active at the
same time is approximately 0.0015.
Show how to compute this probability. You are not required to calculate
the actual figures. [6 marks]
(iii) State two assumptions that you made in Part (a)(ii) about the network
users. In each case describe why the assumption may fail for current
Internet traffic. [4 marks]
(b) The formulae below are used in TCP implementations to compute a value for
the retransmission time-out T. R is an estimate of the round-trip time (RTT),
D is an estimate of variance, M is the most recently measured round-trip
measurement, α = 0.875 and h = 0.25.
D ← D + h(|M − R| − D)
R ← αR + (1 − α)M
T = R + 4D
(i) Give an example of how the retransmission time-out T is used within TCP.
[1 mark]
(ii) Describe why the computation of the retransmission time-out T incorporates a correction for deviation in the estimate of the RTT. [2 marks]
(iii) For each assumption you stated in Part (a)(iii), describe the impact on the
estimate of the retransmission time-out T. [3 marks each]
7 (TURN OVER)
CST.2016.5.8
7 Concurrent and Distributed Systems
This question is with respect to an operating system that supports multi-threaded
processes using the POSIX threads (pthreads) API. Assume that each call to printf
prints its output atomically, that thread scheduling is non-deterministic, and that
threads are allocated unique and sequential integer IDs starting with 0.
(a) Some program state is per-process, and some is per-thread. How many instances
of each of the following will a 2-thread process have: virtual address space,
executable program, register file, scheduling state (e.g., RUN, SLEEP), and stack?
[5 marks]
(b) A programmer adds printfs to a concurrent program to debug a race condition,
but the symptoms vanish. Explain why this might have happened. [2 marks]
(c) thrprint accepts as arguments the current thread's unique ID and a debug
message to print. If each thread calls thrprint exactly once on start, how
many possible interleavings are there with n threads? [2 marks]
void thrprint(int threadid, char *message) {
printf("Thread %d: %s\n", threadid, message);
}
(d) ordered thrprint attempts to print debug messages ordered by thread ID.
Describe three ways in which the synchronisation in this implementation is
incorrect, and provide a corrected pseudocode implementation. [6 marks]
int next_thread_id = 0; // Next ID to print
pthread_mtx_t ordering_mtx; // Lock protecting next ID
pthread_cond_t ordering_cv; // next_thread_id has changed
void ordered_thrprint(int thread_id, char *message) {
pthread_mtx_lock(ordering_mtx);
if (thread_id != next_thread_id) {
pthread_cond_wait(ordering_cv, ordering_mtx);
}
next_thread_id = next_thread_id + 1;
pthread_mtx_unlock(ordering_mtx);
printf("Thread %d: %s\n", thread_id, message);
}
(e) This approach to implementing ordered thrprint suffers a substantial performance problem: if lower-numbered threads are slow in starting, then
higher-numbered threads will also be delayed. Describe an alternative strategy,
paying particular attention to synchronisation, that maintains ordered output
while allowing greater concurrency. [5 marks]
8
CST.2016.5.9
8 Concurrent and Distributed Systems
History graphs record dependencies between individual atomic operations within
sequences of events associated with specific schedules of more complex transactions.
(a) (i) What do edges in a history graph represent? [1 mark]
(ii) What graph property holds if a bad schedule is present? [1 mark]
(iii) Which ACID properties may be violated by a bad schedule? [2 marks]
(iv) Define serial and serialisable executions. Explain whether (and if so, how)
one is a superset of the other. [3 marks]
(b) Two transactions, T1 and T2, consist of operations on two objects, A and B:
T1: { T2 (v): {
a = A.getbalance(); A.debit(v);
b = B.getbalance(); B.credit(v);
return (a + b); }
}
(i) Explain how a dirty read might be experienced through concurrent
executions of T1 and T2. [2 marks]
(ii) Draw and label a history graph illustrating this bad schedule. [2 marks]
(c) A programmer designs a transaction system that uses history graphs to detect
bad schedules. After an operation is performed, and before its containing
transaction is allowed to commit, the history graph is updated and a graph
analysis is run. If a bad schedule is detected, affected transactions will be aborted
and rolled back.
(i) Will this scheme always make progress? Explain your answer. [2 marks]
(ii) Time Stamp Ordering (TSO) will sometimes reject good schedules, which
could lead to unnecessary transaction aborts. Does the scheme described
here accept or reject more schedules than TSO? Explain why. [3 marks]
(iii) Explain one way in which this scheme may perform better than TSO.
Explain one way in which it may perform worse. [4 marks]
9 (TURN OVER)
CST.2016.5.10
9 Concurrent and Distributed Systems
Remote Procedure Call (RPC) allows procedures (functions, methods) to be
forwarded over the network, and is a fundamental building block of distributed
systems such as the Network File System (NFS).
(a) Explain, with respect to a client, what it means for an RPC call to be:
(i) Synchronous [1 mark]
(ii) Asynchronous [1 mark]
(iii) Idempotent [1 mark]
(b) Distributed-filesystem clients utilize different tradeoffs between performance and
consistency for operations on the directory namespace (e.g., file or directory
creation) versus those on file data itself. The following program creates and
opens a file foo, writes some data to it, and closes it, via NFSv3:
fd = open("foo", O_CREAT | O_RDWR, 0755);
// POINT A
write(fd, data, sizeof(data));
// POINT B
close(fd);
// POINT C
For each of points A, B, and C in the program, discuss whether or not another
NFSv3 client is guaranteed to be able to see the results of each of open and (if
it has been called) write.

(a) Consider unspecified behaviour in C.
(i) Define what unspecified behaviour means in the C standard and give two
examples of such behaviour. [3 marks]
(ii) Briefly explain why it is important to have unspecified behaviour in the
definition of the C language. [1 mark]
(b) Compare and contrast the struct and union keywords in C, supplying an
example of a situation where it would be more appropriate to use a union
rather than a struct. [4 marks]
(c) Explain the following C or C++ language concepts. You may find it helpful to
use short code fragments or diagrams to illustrate your answer.
(i) The virtual keyword used to qualify a C++ member function and its
impact on generated code. [4 marks]
(ii) The role of the C preprocessor in the source-code compilation cycle, and
why it is a useful tool for debugging. [4 marks]
(iii) Templated functions in C++, giving one benefit and one drawback of using
them compared with using a void* function in C. [4 marks]
3 (TURN OVER)
CST.2016.3.4
3 Compiler Construction
Programming answers should be written in some notation approximating SML or
OCaml.
(a) Describe what is meant by tail recursion. [4 marks]
(b) Eliminate tail recursion from foldl given below. Explain your answer.
(*
foldl : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a
*)
let rec foldl f accu l =
match l with
[] -> accu
| a::l -> foldl f (f accu a) l
[8 marks]
(c) Eliminate tail recursion from the following mutually tail-recursive functions.
Explain your answer.
let rec is_even n =
if n = 0
then true
else is_odd (n - 1)
and is_odd n =
if n = 0
then false
else is_even(n - 1)
[8 marks]
4
CST.2016.3.5
4 Compiler Construction
Consider writing a compiler for a simple language of expressions given by the following
grammar,
e ::= n (integer)
| ? (read integer input from user)
| e + e (addition)
| e − e (subtraction)
| e ∗ e (multiplication)
| (e, e) (pair)
| fst e (first projection)
| snd e (second projection)
(a) Describe the tasks that should be carried in implementing a front end for this
language and any difficulties that might be encountered. [5 marks]
(b) Suppose that the target virtual machine is stack-oriented and that the stack
elements are integer values, and addresses can be stored as integers. Explain
which other features are required in such a virtual machine. Invent a simple
language of instructions for such a machine and show how it would be used to
implement each of the expressions. [10 marks]
(c) Suppose that the following rules are proposed as possible optimizations to be
implemented in your compiler.
expression simplifies to expression
(fst e, snd e) → e
fst (e1, e2) → e1
snd (e1, e2) → e2
Describe how you could implement these rules so that the simpli
CST.2016.3.6fications are
made only when the program's semantics is correctly preserved.

 

 

a C++ program to sort the elements of the array in ascending
order.
a C++ program using for-loop to print the following output, 105 205 305 405 505 605.

2. Write  C++ program using do-while to take a number less than 100 as input from keyboard.

(a) Explain what is meant by a monad in a programming language, giving the two
fundamental operations of a monad along with their types. [3 marks]
(b) Consider the use of a monad for input-output. For the purposes of this question,
take the IO monad as including two operations readint and writeint which
respectively read integers from stdin and write integers to stdout. Give the types
of these operators. [2 marks]
(c) Assume MLreadint and MLwriteint are primitives with side effects for inputoutput and consider the ML expression add1 of type int:
                      let val x = MLreadint() in MLwriteint(x+1); x end
(i) Give an equivalent expression which uses the IO monad instead of
side-effects, and state its type. [3 marks]
(ii) Give a function run2diff which can be applied to your answer to
part (c)(i). When so applied it should give a value in the IO monad which
corresponds to ML code that runs add1 twice and returns the difference
between the values read. [4 marks]
(d) State what happens when attempting to compile and execute the following Java
fragment (explaining the origin of any error messages or exceptions which might
arise).
Object n = new Integer(42), o = new String("Whoops");
Object [] v;
Integer [] w = new Integer[10];
v = w;
v[4] = n;
v[5] = o; [4 marks]
(e) Consider the Java code:
Object n = new Integer(42);
ArrayList v1;
ArrayList