the belw

(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. (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. (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.

(a) For a processor pipeline, what is the difference between control and data dependencies? [4 marks] (b) For a superscalar processor, under what conditions can instructions from the same thread be executed in parallel? [4 marks] (c) What does it mean to have coherent shared memory and in this context what do the terms write propagation and write serialisation mean? [8 marks] (d) If a simultaneous multithreading processor core supports two hardware threads (or Hyperthreads), under what conditions might performance be decreased by scheduling two jobs in parallel rather than running them sequentially? [4 marks] 3 Computer Design (a) Why do modern processors need caches and what statistical properties do they exploit to improve processor performance? [5 marks] (b) How are cache tags used in direct-mapped and fully-associative caches? [5 marks] (c) A translation look-aside buffer (TLB) is a form of cache, but what does it store and how are TLB misses handled? [5 marks] (d) A processor architect proposes the use of a large direct-mapped TLB rather than the traditional small fully-associative TLB. What might the performance implications be? [5 marks] 4 Computer Networking The popular press suggest that the Internet is a great success. Based on the range of topics covered in the Computer Networking course, critique the technological success and failure of the Internet. Assertions alone will not constitute an answer to the question: please supply evidence by examples.

Consider two physically-separated entities A and B. B has been supplied messages that will be sent to A following these conventions: A gets a request from the layer above to retrieve the next data (D) message from B. A must send a request (R) message to B on the A-to-B channel. Upon receipt of an R, B will send D back to A on the B-to-A channel. A should deliver exactly one copy of each D message to the layer above. R messages may be lost (but will not be corrupted) in the A-to-B channel. D messages are always delivered correctly (no loss or corruption). The delay along each channel is unknown and variable. Give the FSM describing a protocol employed by A and B. This FSM must compensate for the loss-prone channel between A and B, as well as implementing message passing to the layer above at entity A. Your FSM must not use more mechanisms than is necessary. [20 marks] 5 (TURN OVER) CST.2011.5.6 6 Computer Networking (a) The diagram below shows a TCP connection between Hosts HA and HB passing through networks with different values of Maximum Transmission Unit (MTU) shown. Version 4 of the Internet Protocol (IPv4) is in use. MTU 4000 bytes MTU 1500 bytes MTU 4000 bytes Router 1 Router 2 HA HB HA chooses a TCP segment size of 3000 bytes of data (TCP and IP headers are each 20 bytes in size). (i) Describe the way in which fragmentation takes place as HA sends data to HB. Include the arithmetic used to calculate fragment sizes. Explain the saving that may be made by HA choosing an optimal TCP segment size when sending 60KBytes of data. [8 marks] (ii) Briefly explain how the situation described in part (i) would be handled if Internet Protocol version 6 (IPv6) were used. [2 marks] (b) The formulae below are used in TCP implementations to compute a value for the retransmission time-out (R). R is an estimate of the round-trip time, M is the most recently measured round-trip measurement, = 0.875 and h = 0.25. D D + h(|M R| D) R R + (a )M R = R + 4D (i) How is M measured? [2 marks] (ii) Explain the principles behind the design of these formulae and the values h, and D. [8 marks] 6 CST.2011.5.7 7 Concurrent and Distributed Systems Database concurrency control enables multiple transactions to proceed simultaneously against a shared database. (a) Give an example each of conflicting and non-conflicting operations on objects in a database. [2 marks] (b) Explain how timestamp ordering (TSO) works, and how it responds to conflicts between transactions. [4 marks] (c) Explain cascading aborts, and use an example to show how they can occur with TSO. [4 marks] (d) Why is TSO not subject to deadlock? [2 marks] (e) Explain why TSO distributes well, compared with two-phase locking. [4 marks] (f ) Construct a workload that performs badly under TSO, and explain why it does so. What could you do to improve its performance? [4 marks] 7 (TURN OVER) CST.2011.5.8 8 Concurrent and Distributed Systems (a) Consider a queue data structure, with the following interface: interface Queue { void push(Object val); Object pop(); }; (i) Write pseudocode for a semaphore-based implementation of Queue. Your implementation should allow concurrent push and pop when it is safe to do so, but not when it is unsafe. The queued data should be stored in an array of fixed length n. [6 marks] (ii) Explain the specific circumstances under which concurrent push and pop is unsafe. Explain how your solution in part (i) addresses these. [2 + 2 marks] (b) You decide to use this data structure to manage a service, where people around the world push jobs of work to be done, and others pop jobs and do them. (This is a description of Amazon's Mechanical Turk.) This could be implemented as a centralised service, offered through ObjectOriented Middleware. (i) How can the Object-Oriented Middleware maximise the utilisation of this service? [2 marks] (ii) Object-Oriented Middleware makes the calls to push and pop look local. Name two things that this hides from the programmer using the service and say why each is a problem. [4 marks] (iii) What aspects, that are not part of the middleware, might hinder scalability in terms of the number of potential pushers and poppers? [4 marks] 8 CST.2011.5.9 9 Concurrent and Distributed Systems (a) We have considered four types of middleware: remote procedure call, object-oriented middleware, message-oriented middleware, and event-based middleware. (i) Each middleware has a core action, such as a remote procedure call or a remote method invocation. This entails data transfer that is either unidirectional (out of or into the calling context) or bidirectional (in and out). State which is used by each of the four types of middleware. [4 marks] (ii) Does each of theseuni- and bidirectional data transferhave sufficient expressive power for programming? Explain your answer. [2 marks] (iii) One of the characteristics of distributed systems is that they lack global time. Given your answers above, what effect might this have on middleware use? [4 marks] (b) (i) What are causal and totally ordered message delivery? [2 marks] (ii) Which does vector clocks provide? [1 mark] (iii) The vector clock algorithm is a way of sharing state, ensuring that every process knows what it needs to about how far the others have progressed. Why is it critical that messages having vector timestamps are never lost? [2 marks] (c) (i) Storage services can be stateful or stateless. Give one advantage and one disadvantage of each. [2 marks] (ii) If you were designing a service to support film production, which would you use and why?

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 simplifications are made only when the program's semantics is correctly preserved. [5 marks] 5 (TURN OVER) CST.2016.3.6 5 Concepts in Programming Languages (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