CS计算机代考程序代写 scheme algorithm Computer Systems

Computer Systems

Sample Examination Paper

January 2022

Answer all questions

Question 1

a. The diagram below shows roads connecting towns near to Rochdale. The numbers

on each arc represent the time, in minutes, required to travel along each road. Peter

is delivering books from his base at Rochdale to Stockport. Use Dijkstra’s algorithm

to find the minimum time for Peter’s journey.

[8 Marks]

b. Consider an environment in which there is a one-to-one mapping between user-

level threads and kernel-level threads that allows one or more threads within a

process to issue blocking system calls while other threads continue to run. Explain

why this model can make multithreaded programs run faster than their single-

threaded counterparts on a uniprocessor computer.

[6 Marks]

c. An interactive system using round-robin scheduling and swapping tries to give

guaranteed response to trivial requests as follows:

After completing a round-robin cycle among all ready processes, the system

determines the time slice to allocate to each ready process for the next cycle by

dividing a maximum response time by the number of processes requiring service.

Is this a reasonable policy? Explain and justify your argument, using examples if

necessary.

[6 Marks]

Question 2

a. Consider that you live in a small town where only dial-up access is available, with a

maximum possible speed of 300-Kbps (using V.44 modems). You are interested in

uploading a large video file of 2 gigabytes to a server on the Internet.

A bus visits your town every day from the closest city, which is located at 210km

away, and stops in front of your house for 5 minutes max (but it can leave as soon

you indicate you are done). The bus has a 100- Fi connection and it can

collect data from users in rural areas and transfer them to the Internet through a 2-

Gbps link once it gets back to the city.

Suppose the average speed of the bus is 70 km/h. What is the fastest way the user

can transfer the data to the server?

[8 Marks]

b. Convert the decimal number -92.882812710 to the equivalent 16-bit fixed point

notation. Use 1 sign bit, 7 bits for the real part and 8 bits for the fractional part.

Show clearly how you have performed the conversion and clearly state any

assumptions that you have made.

[6 Marks]

c. Your friend Jane needs to run a simulation for her thesis and her adviser wants her

to run it for a fixed problem size. Jane can make 80% of the program parallel, with

20% of it being sequential.

i) What speedup can Jane expect on 5 processors?

ii) What would the maximum theoretical speedup be on an infinite number of

processors?

[6 Marks]

Question 3

a. You are designing a network for a multinational corporation with offices in 50

different countries. Each office is required to be on a different subnet and the

corporation has obtained a Class B network address of 150.32.0.0.

Design subnets for all of the site offices and indicate how many hosts (usable ones)

can be assigned to each site office. Also, indicate if there is any room for expansion

to 10 more countries, using the same network IP address and subnetting scheme.

You are not required to list all subnets, however, you can mention the subnet

addresses, subnet masks and host address ranges for the first three and last subnet.

[6 Marks]

b. Consider the block cypher shown in the figure below:

Suppose that each block cipher Ti simply reverses the order of the eight input bits

(so that, for example, 11110000 becomes 00001111).

Further suppose that the 64-bit scrambler does not modify any bits (so that the

output value of the mth bit is equal to the input value of the mth bit).

i) With n = 3 and the original 64-bit input equal to 10100000 repeated eight

times, what is the value of the output?

ii) Repeat part i) but now change the last bit of the original 64-bit input from a

0 to a 1.

iii) Repeat parts i) and ii), but now suppose that the 64-bit scrambler inverses

the order of the 64 bits.

[8 Marks]

c. In this example you should assume that the function binarySearch is O(log n)

numberFound = 0
for i = 0..(n-1)
for j = 0..(n-1)
if binarySearch(A[i,j])
numberFound = numberFound + 1

i) Use the Big-O notation to express the time complexity of this algorithm

ii) If this algorithm takes 10 seconds to execute when n=2000, estimate how long it

will take when n=8000.

[6 Marks]