Two independent threads are run on different processors in a chip-multiprocessor. Each thread simply increments a private counter one million times. The two counters are stored in consecutive memory locations. It is discovered that running the threads sequentially is faster than running them in parallel. What may cause this type of behaviour? [5 marks] (b) Cache coherence protocols are classified as either invalidate or update protocols. What are the potential advantages and disadvantages of adopting an update rather than an invalidate protocol? [5 marks] (c) Sequential consistency offers a simple and intuitive memory consistency model. Why is sequential consistency rarely supported by modern chip-multiprocessor designs? [5 marks] (d) What information does the directory provide in a directory-based coherence protocol? [5 marks] 4 CST.2012.8.5 4 Computer Systems Modelling (a) Let U be a uniform random variable on the interval (0, 1). Show that for any continuous distribution function F(x) the random variable X defined by X = F 1 (U) has the probability distribution function F(x). [4 marks] (b) Use your result in part (a) together with a random variable U distributed according to a uniform distribution on the interval (0, 1) to construct random variables for the following two distributions: (i) the uniform distribution on the interval (a, b) where a and b are real numbers such that a < b

no half work answer all

A company has fired one of its senior staff after an incident that they claimed was an accident, but where the directors suspected malice. The company's auditors have suggested a review of the company's systems to mitigate 'the insider threat', and your advice has been sought. The directors want to be able to assure the shareholders that they are taking all reasonable steps to limit the damage that staff could do to affect the company's share price, whether accidentally or otherwise. (a) Describe a multilevel security policy briefly, explaining what sort of harms it seeks to prevent, and how. [5 marks] (b) Describe a separation-of-duty security policy briefly, explaining what sort of harms it seeks to prevent, and how. [5 marks] (c) Describe one approach to minimising the risk of user error that is based primarily on psychology. [5 marks] (d) Introducing architectural changes to the company's information systems will take time, while changes to user interfaces and workflows are often simple to implement. Which psychological approaches might be adopted more quickly, and what might you expect to go wrong? [5 marks] 6 Software and Security Engineering A university has decided to implement a student monitoring system to enforce social distancing during the coronavirus pandemic. It is located in a country that does not expect to vaccinate all its residents until 2023, and the students will be about the last in line. As the budget is limited, the Vice-Chancellor plans to turn on event logging in its existing WiFi access points located in each lecture hall, lab and residence building to monitor that occupant numbers do not exceed notified limits. You may assume that access points can be configured to log network addresses, user logons or both. (a) What performance, security and privacy issues might you expect? [7 marks] (b) What policies might the Vice-Chancellor enact to manage the associated risks? [7 marks] (c) Could you suggest any alternative strategies to the Vice-Chancellor?

(a) To switch between processes, an operating system must save the context of the current executing process and restore the context of that being resumed. (i) By what mechanism is the point of execution of a process preserved and restored? [2 marks] (ii) Describe two methods by which the contents of a process address space are preserved and restored. [8 marks] (iii) Give two other elements of process context. [2 marks] (b) The diagram below is a simplified state transition diagram for a process in a generic operating system. k j a b kernel ready interrupted waiting h g e f c running i l For each of the following, describe the transitions taken by the process and say whether or not it is necessary for the process scheduler to run: (i) A running process is interrupted by a timer. The timer interrupt service routine determines that the time slice given to the process has not yet expired. [2 marks] (ii) As in (b)(i) but the time slice given to the process has expired. [2 marks] (iii) A running process makes a system call which can be serviced immediately by the kernel. [2 marks] (iv) A running process makes a system call which requires an I/O operation to be initiated. [2 marks] 4 CST.2012.2.5 4 Operating Systems Consider the following scheme for structuring a file from a set of disk blocks. A disk block contains 4096 bytes and a block address is 32 bits. The first block of the file contains the following information: control information: 1024 bytes direct block pointers: 1024 bytes indirect block pointer: 4 bytes double indirect block pointer: 4 bytes immediate data: 2040 bytes The data bytes of the file start at the beginning of the immediate data. After the immediate data, the file data is found on the block addressed by the first direct block pointer and then carries on in a fashion similar to the structure defined by a Unix inode. We consider the first byte of the file to be byte 0, then byte 1, etc. (a) For each of the following describe the actions taken to fetch the indicated byte of a file, and state how many disk blocks may need to be read: (i) byte 70 of the file [1 mark] (ii) byte 220 + 2044 [1 mark] (b) How large can a file be if it is to be guaranteed that only three disk blocks need to be read in order to access any given byte of the file? [4 marks] (c) Information about a file can be stored in a directory that references the file or in the control part of the first block of the file (i.e. inode in Unix). Which of these is used in the Unix file system to store the following information and why? (i) time of creation [3 marks] (ii) file name [3 marks] (iii) file access rights [3 marks] (d) Another way to structure files on a disk is to use physically contiguous blocks (with contiguous addresses), so that if the first block of a file is block b, then the next block of the file is b + 1. Suppose we use this method, retain the control information on the first block, but include the first 3 KBytes of the file in the first block. Comment on the performance of such a system, considering reading, writing, and creating files.

(a) What are the main criteria to be considered in the design of a line drawing algorithm for a raster graphics display? [2 marks] (b) Describe an algorithm to fill a series of pixels running from (x0, y0) to (x1, y1) that meets these criteria, explaining why it does so. Answers should consist of more than a fragment of pseudo-code. [6 marks] (c) A new volumetric display stores an image as a three-dimensional array of volume elements or voxels. Reformulate the design and implementation of the line-drawing algorithm to fill a series of voxels running from (x0, y0, z0) to (x1, y1, z1). [6 marks] (d) How would this line-drawing algorithm be used to draw Bezier curves in three dimensions? [6 marks] 4 CST.2012.4.5 4 Computer Graphics and Image Processing (a) Describe how transform coding can be used to compress image data. [4 marks] (b) Explain the Walsh-Hadamard transform on a one-dimensional array of 4 greyscale values. [4 marks] (c) Extend this to the Walsh transform for a two-dimensional array of 22 greyscale values. [4 marks] (d) Develop an analogous transform for a three-dimensional array of 2 2 2 greyscale values.

Consider the host mine.ja.net, with a local DNS server dns1.ja.net. [Note: dns1.ja.net is configured to use recursive DNS by default.] (i) Host mine.ja.net asks server dns1.ja.net to resolve the hostname yours.foobar.com. Assume there are no cached entries relevant to this request. Write down the steps taken to resolve yours.foobar.com and respond to mine.ja.net. [4 marks] (ii) Describe the differences between this solution and one achieved using iterative DNS. [2 marks] (iii) Compare and contrast DNS with ARP. [4 marks] (b) An office has an (Internet) access link rated at 10 Mbps full-duplex. Each user requires 1 Mbps when transmitting and each user is active 10% of the time. (i) Initially a static allocation of bandwidth is made for each user. How many users can the access link support? [1 mark] (ii) The office opts for a pure packet-switched access link. What is the probability that a given user is transmitting? [1 mark] (iii) The office supports 35 users on the packet-switched access link. What is the probability that exactly n users are transmitting simultaneously? [2 marks] (iv) Find the probability that there are 11 or more users transmitting simultaneously. [3 marks] (v) Describe an assumption about the nature of the traffic that underlies the answer to part (b)(iv) and give two examples of network traffic where this assumption is not valid