The following variables are used in an implementation of the algorithm: ar is the count of active
Question:
The following variables are used in an implementation of the algorithm: ar is the count of active readers rr is the count of reading readers aw is the count of active writers ww is the count of writing writers (who write one-at-a-time) (a) In a semaphore implementation: SemWrite is for writers to wait on, in order to write one-at-a-time. For condition synchronisation: SemOKtoRead is for readers to wait until all writers have finished. SemOKtoWrite is for writers to wait until currently reading readers have finished. Discuss the following pseudocode for an attempted implementation of startread: procedure startread ( ) wait(SemCountGuard); ar := ar + 1; if aw > 0 then wait(SemOKtoRead); rr := rr + 1; signal(SemCountGuard) return [6 marks] (b) Using the above example, comment on the ease of monitor programming and implementation, compared with semaphore programming. Assume a monitor ReadersWriters defines condition variables OKtoRead andOKtoWrite. [6 marks] (c) Describe and comment on the Java approach to supporting mutual exclusion and condition synchronisation. [4 marks] (d) Explain how active objects and guarded commands avoid some of the issues arising in the above programs.
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.
Consider the programming language with terms e having abstract syntax: e ::= x | c | x.e | e1e2 | let x = e1 in e2 where x ranges over a set of identifiers and c over a set of integer constants. For the rest of the question, your answers can be illustrated by reference to the program p: z.let id = x.x in id id 7 State how to label terms in p uniquely so that a subterm occurring repeatedly in a term has different labels. [4 marks] Show how such terms may be seen as a family of flowgraphs, one for each (you may find it useful to consider the above labelling as providing a unique function name for anonymous -abstractions). [4 marks] Define the call graph of such a family of flowgraphs, stating clearly how indirect calls are treated. [4 marks] Describe how to associate a flow-variable with each labelled node of a term such as p and to derive equations which can improve the above treatment of indirect calls to get a better approximation of the edges in the call graph. [8 marks] [Hint: you may find it useful to recall the shorthand of ( 7 ) as representing the compound constraint that whenever (xj .ek ) i we have j k where r is the flow variable associated with the node labelled r.] 5 [TURN OVER CST.98.9.6 8 Neural Computing When using a feed-forward network to solve a classification problem we can interpret the network's outputs as posterior probabilities of class membership, and then subsequently use these probabilities to make classification decisions. Alternatively, we can treat the network as a discriminant function which is used to make the classification decision directly. Discuss the relative merits of these two approaches. [7 marks] Explain the concept of a likelihood function, and the principle of maximum likelihood. [3 marks] Consider a feed-forward network which implements a function y(x, w) in which y is the output variable, x is the vector of input variables, and w is the vector of weight parameters. We wish to use this network to solve a classification problem involving two classes A and B. The value of y, when the network is presented with an input vector x, is to be interpreted as the posterior probability P(t = 1|x) in which t = 1 denotes class A and t = 0 denotes class B. Write down the probability distribution of t given y. Use the principle of maximum likelihood to derive an expression for the corresponding error function defined over a set of training data comprising input vectors xn and targets tn, where n = 1, . . . , N. Write down a suitable form for the output unit activation function y = g(a). Hence evaluate the derivative of ln P(t|y) with respect to a. [10 marks] 6 CST.98.9.7 9 Security Describe those provisions of the following Acts of Parliament that are relevant to computer security: The Civil Evidence Act of 1968 The Police and Criminal Evidence Act of 1984 The Data Protection Act of 1984 The Computer Misuse Act of 1990 [12 marks] A software house incorporates a time-lock which causes their product to stop working if it is not supplied with a suitable password every 6 months. What risks are they running? [4 marks] A hospital de-identifies patient records by removing names and addresses, leaving only the patient's postcode and date of birth as an identifier. These records are then sold to researchers and drug companies. What risk is the hospital running?
State, with justification, whether each of the following statements is true or false. (a) The set of natural numbers, N = {0, 1, 2, . . .}, equipped with the usual less-than-or-equal relation, 6, is a domain. [3 marks] (b) The set of all subsets of N, equipped with the relation of subset inclusion, is a domain.
(a) When distributed systems are designed and engineered, certain fundamental characteristics have to be taken into account, including: 1. Concurrent execution of components. 2. Independent failure modes. 3. Communication delay. 4. No global time. In the light of these characteristics, discuss the monitoring of a widely distributed industrial process with the following properties: Distributed monitoring computers analyse regions of the process. Each region contains a number of sensors at identified locations and with the ability to generate timestamps. Some sensors monitor temperature, others monitor pressure. If both temperature and pressure are found by a monitoring computer to be above their defined thresholds in a given locality within its region it sends an alarm signal to the process control centre, indicating the time and place of the occurrence. The control centre initiates action to bring the values under control. [10 marks] (b) The diagram below represents a process group that communicates by means of multicast messages. P4 (0000) P3 (0000) P2 (0000) P1 (0000) = message delivery software time --> At each process-hosting node, message delivery software decides whether an incoming message should be delivered to the process or buffered for later delivery. This is achieved by the use of vector clocks. With reference to the example shown in the diagram, describe the vector clock algorithm for delivery of messages in causal order. [10 marks] 6 CST.2010.5.7 7 Digital Communication I When Skype establishes an audio channel for telephony calls, it can do so in three ways: Direct connection, using UDP. Indirect connection, using UDP relayed via a Supernode. Indirect connection, using TCP to reach a Supernode, then UDP from there to the destination. (a) Why does Skype provide these three modes? [2 + 2 + 2 marks] (b) Describe the different audio problems you might encounter when the first and last modes are used. [8 marks] (c) Which mode will normally provide the best audio experience? Why? [2 marks] (d) Suggest two further techniques that an Internet telephony application such as Skype can use to minimise the effects of packet loss. Discuss their relative merits.
(a) The diagram below shows an abstraction of the modules involved in processing an incoming packet on an Internet host. IP header TCP header Payload Incoming Packet IP Module UDP Module TCP Module Process A Process B Process C Process D Explain how these modules process the header fields in the incoming packet so that the data is delivered to the correct process. [6 marks] (b) The Transmission Control Protocol (TCP) utilises a 3-way handshake at the start of a connection. Explain, with reference to sequence numbers, how this operates and the purpose of the third packet in this exchange. [8 marks] (c) What is meant by a TCP port? Make reference to how ports are used at client and server when a web browser opens a TCP connection of a web server.
Write program that reads a list of integers ending with a negative, and that then outputs that list in reverse. After the negative that ends the list, a character indicates what character should separate the output integers. a full C++ program that reads an integer, a list of words, and a character. The integer signifies how many words are in the list. The output of the program is every word in the list that contains the character at least once
Consider the following client program extract: 1 Socket s = new Socket("localhost",10000); 2 ObjectInputStream ois = new ObjectInputStream(s.getInputStream()); 3 Object o = ois.readObject(); 4 Class c = o.getClass(); 5 for(Field f : c.getDeclaredFields()) 6 System.out.println(f.get(o)); 7 c.getMethod("run").invoke(o); (a) Describe the execution of this extract, assuming that no exceptions are thrown. [5 marks] (b) Identify five distinct exceptions that may occur during execution of the client program extract. Your answers should include the line number at which the exception would be thrown and a brief description of the problem which would cause it. General virtual machine errors such as OutOfMemoryError or StackOverflowError should not be included in your answer. [2 marks each] (c) Write a server program extract that is capable of communicating successfully with the client extract shown above. You should assume the existence of an Object variable called sendMe which contains the object to be sent to the client. You do not need to write any error handling code.
(a) Given a positive reset signal, how is an asynchronous reset described in Verilog? [2 marks] (b) For each of the following six always blocks, what sequence or error will be produced? You should assume that registers are reset to zero at the start (as they are for FPGAs) and that clk is a clock. [3 marks each] reg [2:0] counterA, counterB, counterC, counterD, counterE, counterF; always @(posedge clk) begin counterA <= counterA+1; if(counterA==5) counterA <= 1; end always @(posedge clk) begin if(counterB==5) counterB <= 1; counterB <= counterB+1; end always @(posedge clk) begin if(counterC==5) counterC = 1; counterC = counterC+1; end always @(*) counterD <= counterE+1; always @(posedge clk) counterE <= (counterD==5) ? 1 : counterD; always @(*) begin if(counterF==5) counterF <= 1; counterF <= counterF+1; end 2 CST.2010.5.3 2 Computer Design Gordon Moore's "law" was originally an observation about transistor density improving exponentially and the implications for the semiconductor industry. (a) Does Moore's law still apply to transistor density? Justify your answer. [4 marks] (b) Can Moore's law be applied to processor performance? Justify your answer. [4 marks] (c) Communication to peripherals, including disks, now uses serial rather than parallel communication techniques. (i) What are the electrical reasons for this change? [4 marks] (ii) What are the economic reasons for this change? [4 marks] (d) Why did EDSAC perform calculations in a bit-serial manner and yet modern processors compute bit-parallel? [4 marks] 3 Computer Design (a) Pipelining is used to improve processor performance and yet it increases instruction execution latency. How does pipelining improve performance? [4 marks] (b) Is the pipelining technique scalable to ever more pipeline stages? Justify your answer. [6 marks] (c) Flynn's original taxonomy of parallel architectures identifies four classes of parallelism: SISD, SIMD, MISD, MIMD. What do these acronyms mean? [4 marks] (d) Today's commercial desktop processors are often said to be "many-core". How would you classify them using Flynn's taxonomy? Do they exhibit other forms of parallelism?