ANSWER ALL Consider a queue data structure, with the following interface: interface Queue { void push(Object val);
Question:
ANSWER ALL
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 these?uni- and bidirectional data transfer?have 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?.
provide answers to every question
) Explain what is meant by "instruction scheduling" in a compiler. Indicate what properties of architectures make it beneficial. Are some architectures too simple, or too complex, for it to be useful? [3 marks] (b) Sketch an algorithm that schedules instructions within a basic block for an architecture of your choice on which scheduling is useful. Indicate its time complexity O(f(n)) stating to what 'n' refers. What additional complications arise in choosing which instruction to emit first from a basic block? [5 marks] (c) Indicate how your algorithm could be modified to deal with a static multipleissue VLIW-style architecture. The input basic block contains simple instructions, but the output basic block contains wide instructions consisting of two simple instructions (either of which may be NOP). These two instructions execute in parallel. Now explain how your algorithm can schedule the following sequence of instructions to execute in parallel, or detail any adjustments necessary to permit this. st r1,r to enable a wider range of load/store pairs to be re-scheduled. [6 marks] (d) Briefly summarise a source-level approach to alias or points-to analysis, for example Andersen's algorithm. Your summary should emphasise key choices, for example any data-structures used; detailed algorithms are not required. [6 marks] 9 (TURN OVER) CST.2011.9.10 9 Principles of Communications (a) Control Theory allows us to find various useful properties of a system such as stability. Draw a picture of a generic control system, explaining the functions of feedback and the design goals for the controller. [5 marks] (b) The Transmission Control Protocol of the Internet uses a feedback controller and responds to absence or presence of congestion signals by Additive Increase Multiplicative Decrease of a sending window. (i) Describe the operation of this scheme. [10 marks] (ii) Explain qualitatively why the scheme is necessary, but perhaps not sufficient, to create a stable set of traffic flows in the Internet. [5 marks] 10 System-on-Chip Design (a) What is an instruction set simulator (ISS) and what is typically the best way for it to achieve high performance? [2 marks] (b) What performance bottleneck can typically arise when CPU-intensive software is run on a model of a complete system on chip (SoC)? How can this be avoided and at what costs to modelling accuracy? [4 marks] (c) What problems can arise when operating system device drivers are run on an ISS that has been optimised according to your answers to parts (a) and (b) above? [4 marks] (d) Two processors on a SoC have separate address spaces. What does this mean? Describe a simple hardware mechanism for sending non-trivial amounts of data between processors in separate address spaces. Interrupts should be used.
(a) The Border Gateway Protocol (BGP) uses two mechanisms to reduce the number of update messages: route-flap damping and rate-limiting. (i) Describe the rate-limiting mechanism. [3 marks] (ii) Discuss what might happen if every BGP speaking router in the Internet turned off rate-limiting. (b) Professor Bell claims that BGP could be replaced by a simple shortest paths routing protocol. Is Professor Bell correct? Explain. [4 marks] (c) Content Delivery (or Distribution) Networks (CDNs) are becoming an important component of the Internet. (i) What is a CDN? [2 marks] (ii) What impact could the growth of CDNs have on inter-domain routing? [3 marks] (d) The growth of routing tables has led to proposals to make an explicit separation between identifiers and locators. (i) Explain how this could reduce routing table size. [2 marks] (ii) Explain how tunnelling is required by this scheme. [3 marks]
Computer Architecture A Quantitative Approach
ISBN: 978-0123704900
4th edition
Authors: John L. Hennessy, David A. Patterson