Computer Systems Sample Examination Paper January 2021
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-Mbps WiFi connection and it can
Question 3
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]
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.
b. Consider the block cypher shown in the figure below:
[6 Marks]
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]