HOW DO SOFTWARE

1 Data Structures and Algorithms A certain program has to maintain an array, count, of N counters which are all initialised to zero. The value of counter i can be incremented by one by the call: increment(i), and this is the only way the program changes counter values. Two variables, mincount and maxcount, must always hold the smallest and largest of the counter values whenever the point of execution is not within the function increment. You may assume that increment is called about 1000N times when the program is run and that its argument is typically uniformly randomly distributed between 1 and N, but on some runs it cycles through the numbers 1 to N in order 1000 times. (a) Describe, in detail, an efficient data structure and algorithm to use when N is expected to be about 10. [5 marks] (b) Describe, in detail, an alternative data structure and algorithm to use when N is about a million. [10 marks] (c) Suppose your algorithm for (a) above were used when N = 106 , estimate how much slower it would be compared with your algorithm for (b). [5 marks] 2 Computer Design (a) What is a data cache and why is it vital for high performance processors? [5 marks] (b) What is a cache line and how big is it likely to be? [3 marks] (c) What is a page and how big is it likely to be? [3 marks] (d) What is a snoopy cache and in what system is it likely to be used? [3 marks] (e) A computer system has the following memory parameters: memory level access time in clock cycles first level cache 1 second level cache 3 main memory 100 If the probability of a hit in the first level cache is 80%, what hit rate do we need in the second level cache if the mean access time is to be two clock cycles? For this part, use the approximation that the cache line length is just one machine word. [6 marks] 2 CST.2005.13.3 3 Digital Communication I (a) Describe on-off flow control. In what circumstances is it appropriate? [4 marks] (b) Describe the operation of window-based flow control. [4 marks] (c) What happens if window-based flow control is used on a flow passing through a highly loaded resource (e.g. router) that is not participating in the flow control protocol? [4 marks] (d) How is this addressed in the Internet? [4 marks] (e) What are the advantages and disadvantages of having Internet routers participate in window-based flow control of every TCP connection? [4 marks] 4 Distributed Systems P4 P3 P2 P1 0000 0000 0000 0000 = message delivery algorithm time --> The above diagram represents a process group that communicates by means of multicast messages. At each process-hosting node, message delivery software decides whether a given incoming message should be delivered to the process or buffered for later delivery. This is achieved by the use of vector clocks. (a) Describe, by means of the above example, the vector clock algorithm for delivery of messages in causal order. [15 marks] (b) By means of a similar example, show that total ordering of messages is not achieved by this algorithm.

How do software engineering tools change as systems scale? Discuss this question with reference to (a) a 2000-line device driver for a safety-critical sensor on board an aircraft; (b) a 100,000-line engine control unit for a diesel engine that adapts it for use in trucks, generators or irrigation pumps; (c) a 1,000,000-line social networking site such as Facebook or MySpace; (d) a 50,000,000-line operating system.

(a) The classic MIPS 5-stage pipeline is depicted below. instruction decode and execute memory write fetch register fetch access back (i) With reference to the 5-stage pipeline, what are data hazards and how can they be resolved to ensure that the programmer's model of sequential execution is always preserved whilst minimising performance impact? [6 marks] (ii) With reference to the 5-stage pipeline, what are control hazards and how can they be resolved? [4 marks] (b) If we wanted the above pipeline to mimic two processors running at half the speed, then we could have two copies (A and B) of the register state and keep the existing pipeline. The instruction-fetch stage would alternate between fetching from threads A and B on alternate clock cycles. As a consequence, if instruction fetch was from thread B, then an instruction from thread A would be in decode, B in execute, A in memory access and B in wriack. (i) For this dual-threaded processor, if branches are performed in the decode stage, does the pipeline exhibit a branch delay slot? [5 marks] (ii) How can the resolution of data hazards be simplified for this dual-threaded processor?

(a) Describe five physical properties of a communications channel. [5 marks] (b) Consider the figure below. Entities N and N0 use an ARQ system. Channel - 1 Channel Channel + 1 Entity - 1 Entity Entity + 1 Entity - 1 Entity Entity + 1 n n n N N N N' N' N' (i) Explain how the latency of channel n 1 can have a direct effect on the capacity of channel n. [6 marks] (ii) Define windowing as it relates to an ARQ system and describe how the capacity of the ARQ system may be improved through its use. [4 marks] (iii) If an ARQ system is used for an interactive session, the ARQ system can lead to many small packets, each under-full and perhaps sent with significant overhead. Design and describe an algorithm that overcomes the limitation of sending many mostly-empty packets for an interactive(a) A web server is an application that listens for incoming network connections on TCP port 80. Once a connection is established, the task of processing client requests and sending replies can be handled by an instance of a Worker class which you may assume already exists. Worker implements the java.lang.Runnable interface and has an accessible constructor that takes as argument a java.net.Socket object representing the network connection to a client. Provide the Java code for a webserver which, upon start-up, attempts to listen on TCP port 80 and starts a new Thread running a new Worker for every connection. Your program should print helpful error messages indicating the likely cause of problems when it is unable to proceed as expected. [10 marks] (b) A busy web server might expect to handle concurrent requests to read and update some shared data and could use Timestamp Ordering (TSO) to enforce isolation between concurrent transactions. (i) Explain how TSO enforces isolation. [5 marks] (ii) Is TSO appropriate for a web server application? Explain your reasoning. [5 marks] session. [5 marks]

The first portion of this workshop consists of modules:

• w7 (supplied)
• CovidCollection

Enclose all your source code within the sdds namespace and include the necessary guards in each header file.

In the specs below, functions marked with DO NOT USE MANUAL LOOPS should not use for or while in the implementation; these functions should use STL Algorithms. The STL Algorithms you choose should use lambda expressions to process the collection; the lambdas should capture the necessary variables from context only by value (the stream object is the only one allowed to be captured by reference). Check course notes to identify which algorithm is appropriate in each situation. Using manual loops will lead to rejection of the workshop or severe penalties (at the discretion of your professor).

CovidCollection Module

This modules defines a simple structure called Covid, capable of storing the following information about a covid details for a particular City:

• country
• city
• variant
• number of cases
• year
• number of deaths

No need to add any member functions to this structure. Choose appropriate types for each attribute.

Also, define a class called CovidCollection that manages a collection of objects of type Covid.

Public Members for CovidCollection

a custom constructor that receives as a parameter the name of the file containing the information about the covid details of various cities to be added to the collection. This function should load into the attributes all the covid details in the file.

If the filename is incorrect, this constructor should throw an exception.

Each line from the file contains covid information about a single city in the following format:

COUNTRY CITY VARIANT YEAR CASES DEATHS 

The fields are not separated by delimiters; each field has a fixed size: COUNTRY, CITY and VARIANT have exactly 25 characters; while YEAR, CASES and DEATHS have exactly 5 characters.

Any blank space at the begining/end of a token is not part of the token and should be removed.

void CovidCollection::display(std::ostream& out) const: print the content of the collection into the parameter (one city details / line). Use the insertion operator (see below). DO NOT USE MANUAL LOOPS!

Free Helpers

std::ostream& operator<<(std::ostream& out, const Covid& theCovid): inserts one Covid into the first parameter, using the following format (the width of each field is specified in brackets):

| COUNTRY(20) | CITY(15) | VARIANT(20) | YEAR(6) | CASES | DEATHS | 

Look in the sample output to see how the numbers should be formatted and the alignment of each field.

Add any other member that is required by your design!

w7 Module (supplied)

The tester module for the first portion has been supplied. Do not modify the existing code!

When doing the workshop, you are encouraged t tests, focusing on a single implemented feature at the time, until you get all functionality in place.

Sample Output

When the program is started with the command (the file covids.txt is provided):

ws covids.txt 

the output should look like the one from the sample_output.txt file

Design a bell system for a quiz with the use of memory elements and logic gates.

The system should have the following functions: There are a total of three buttons in the system, one button for each competitor and then a special button for the judge. If either competitor presses their own button, the appropriate light should come on (see exclamation mark) and the light stays on until the judge presses its button, which restarts the system and all lights go out. The light of the first competitor to light up and if the second competitor pushes his own switch after that the status doesn't change (the status remains unchanged until the judge restarts the system) You need to decide what to do if both competitors press the button exactly the same time. Competitors and the judge use a switch that gives 1 when pressed. The inputs are: A (competitor switch A). B (competitor B switch). S (controller switch). The outputs: Z1 (light for competitor A) Z2 (light for competitor B)

1. Use D-flip-flops with reset (R) input (R = 0 reset flip-flop).

Example of D-flip-flop :

Irue or false 2/. Java compiler does not ignore wnite spaces such as spaces, tabs, or blank lines in a Java program. 28. The same variable name(s) can be declared and used within different methods. 29. In Java, 3*b'+1 is a valid expression. 30. In Java x++ is equivalent to X=X+1. 31. In Java, int x-2.5; is a valid statement. 32. The data type of the Java expression (int) 2.5 is double. 33. A method in Java can return more than one value. 34. A method can take more than one parameter. 35. In Java, 3+*abc"+2*3 is a valid statement. 36. Method A can call another method B which in turn calls the method A again in Java 37. More than two for loops can be nested within each other 38. In Java, if a=4, b6, then statements a=b; and b=a; will produce the result that a-6 and b=4. 39. Identifier_$ is valid in Java. 40. Java bytecode for the same program is different for different platform.

Please answer all the questions