Why are TLBs always much smaller than caches? [4 marks] (d) Which of the lookup mechanisms in part (b) is usually used for a TLB and why aren't the other mechanisms usually used? [6 marks] 2 ECAD Consider the following mysterious Verilog module. module mystery(c,r,a,s); input c,r,a; output [2:0] s; reg [2:0] s; always @(posedge c or posedge r) if(r) s<=30; else begin if(a && (s<37)) s<=s+31; else if(!a && (s>0)) s<=s-1; end endmodule (a) A software module controls a car park of known capacity. () and exit() are triggered when cars enter and leave via the barriers. Give pseudocode for the enter and exit procedures (i) if the module is a monitor [8 marks] (ii) if the programming language in which the module is written provides only semaphores [4 marks] (b) Outline the implementation of (i) semaphores [4 marks] (ii) monitors [4 marks]

In a proposed, next-generation banking system a number of transactions are to be scheduled to run concurrently: Debit (D) transactions to make payments from customer accounts to a credit card company. Interest (I) transactions to add daily interest to customer account balances. Transfer (T) transactions which first check whether the source account contains sufficient funds then either abort or continue the transfer from source to destination accounts. Customer x is running a T to transfer 1000 from A to B. Customer y is running a T to transfer 200 from B to A. (a) Discuss the potential for interference between any of these transactions. [7 marks] (b) Demonstrate the effect of concurrency control based on strict two-phase locking in relation to the discussion in (a). [8 marks] (c) Comment on the scope of concurrency control in relation to the discussion in (a). [5 marks] [Hint: you may assume that operations on bank account objects, such as debit, credit and add-interest are atomic.]

You are asked to write Prolog program to work with binary trees. Your code should not rely on any library predicates and you should assume that the interpreter is running without occurs checking. (a) Describe a data representation scheme for such trees in Prolog and demonstrate it by encoding the tree shown above. [3 marks] (b) Implement a Prolog predicate bfs/32 which effects a breadth-first traversal of a tree passed as the first argument and unifies the resulting list with its second argument. For example, when given the tree shown above as the first argument the predicate should unify the second argument with the list [3,2,7,4,2,5]. [4 marks] (c) Explain why the bfs/2 predicate might benefit from being converted to use difference lists. [2 marks] (d) Implement a new predicate diffbfs/2 which makes use of a difference list to exploit the benefit you identified in part (c). Your predicate should take the same arguments as bfs/22. [6 marks] (e) A friend observes that a clause in diffbfs/22 will need to contain an empty difference list and proposes two possible ways of representing it, either []-[] or A-A. Consider your implementation of diffbfs/2. For each use of an empty difference list, justify your choice and explain what can go wrong using the alternative form. [2 marks... Suppose that R(SA, B, CS) is a relational schema with functional dependencies F = {SA, B C, SC B}. (i) Is this schema in 3NF? Explain. [2 marks] (ii) Is this schema in BCNF? Explain. [2 marks] (b) Decomposition plays an important role in database design. (i) Define what is meant by a lossless-join decomposition. [2 marks] (ii) Define what is meant by a dependency preserving decomposition. [2 marks] (c) Let R(DA, B, FC, DD, E) be a relational schema with the following functional dependencies i) What is the closure of {A, B}? [2 marks] (ii) What is the closure of {B, E}? [2 marks] (iii) Decompose the schema to BCNF in two different ways. In each case, are all dependencies preserved? Explain. [4 + 4 marks]

For a transaction model based on objects and object operation time-stamps: (a) (i) Define how conflict may be specified in terms of object operation semantics. (ii) Give an example of conflicting operations. (iii) Give an example of non-conflicting operations that would be defined as conflicting under read-write semantics. [3 marks] (b) Define the necessary and sufficient condition for two transactions to be serialisable. Give an example of a non-serialisable execution of a pair of transactions. [3 marks] (c) Define the necessary and sufficient condition for any number of transactions to be serialisable. [1 mark] (d) Discuss how the following methods of providing concurrency control in database systems enforce the properties defined above. (i) Strict two-phase locking. [4 marks] (ii) Strict timestamp ordering. [4 marks] (iii) Optimistic concurrency control. [5 marks]

) In the context of virtual memory management: implemented? [4 marks] (ii) What is meant by temporal locality of reference? [2 marks] (iii) How does the assumption of temporal locality of reference influence page replacement decisions? Illustrate your answer by briefly describing an appropriate page replacement algorithm or algorithms. [3 marks] (iv) What is meant by spatial locality of reference? [2 marks] (v) In what ways does the assumption of spatial locality of reference influence the design of the virtual memory system? [3 marks] (b) Buses are used to connect devices to the processor. (i) Describe with the aid of a diagram the operation of a synchronous bus. [4 marks] (ii) In what ways does an asynchronous bus differ? [2 marks

Consider an operating system that uses hardware support for paging to provide virtual memory to applications. (a) (i) Explain how the hardware and operating system support for paging combine to prevent one process from accessing another's memory. [3 marks] (ii) Explain how space and time overheads arise from use of paging, and how the Translation Lookaside Buffer (TLB) mitigates the time overheads. [3 marks]