Question 1
Computer Systems
(a) You are building a system that records student marks in an in-memory data struc- ture. It is important that the system works efficiently and correctly for multiple concurrent users. There are 2 classes of operation: recording a mark for a student and generating a report of a student’s marks. Whenever an operation takes place an audit record is kept of that operation. This is done by appending a record (user, date-time, operation performed) to a global string that records all of the operations that have been performed on the database. You can ignore practical issues e.g. of data persistence or memory use and can assume that reading/writing a mark is an atomic operation.
Explain what issues could arise from having multiple concurrent users of this system. You should propose a solution to these potential problems and provide an argument for why you have chosen this solution rather than other alternatives. Explain what
the implications are of implementing your proposal. (b) You have been given the following algorithm:
for i=1 to n
for j=1 to n/2
for k=1 to n/3
(i) Derive and justify its time complexity using ‘Big-O’ notation
(ii) You have been given the following execution times for a program which im- plements this algorithm. The program has two parts. The first is constant and independent of n – a fixed overhead, the second implements the algorithm above.
N 250 500 Execution time 110 msec 180 msec
Estimate and justify how long it would take to execute for n=1000
(c) You need to represent data for up to 40,000 people. For each person you need to record:
• Their name (100 bytes)
• Their date of birth (10 bytes)
• Their person id (8 bytes)
• An image (64k bytes)
• Astringwhichrecordsdetailsofanyadditionalinformation(2kbytes)
Estimate how much space you will need to allow to record this information. Express your result as the number of Mbytes. How many bits would be required to address this many bytes? Explain your working.
Question 2
(a) Translate the following Java code into MIPS assembly code. Briefly, explain each line of your code.
(i) A program makes three system calls: one to open a file; one to read a byte from it; and then one to close the file. How many times will the mode bit change from 0 to 1 during this process? Justify your answer.
(ii) How can the CPU’s registers be used to pass parameters to system calls, and why might this cause problems if system calls take many parameters? Propose an alternative method of passing parameters, that avoids this problem.
(iii) Give three examples of when a context-switch between processes is performed. What are the actions taken by a kernel during the context-switch? Explain the advantages and disadvantages of context-switching.
for (i=0;i¡10;i++) vals[i]=i*i;
(c) UsingRSA,choosep=5andq=13.Foreachofthefollowing,showeverystepof your working:
(i) Encode the first three digits (upper-case letters) of your first name by encrypt- ing each letter separately. If your first name contains less than three letters, combine it with the first letter(s) from your surname (last name) so you will have 3 digits in total. Hint: Replace each upper-case letter by its position in the alphabet, for example A=1, B=2, Z=26.
(ii) Apply the decryption algorithm to the encrypted version in (i) to recover the original plaintext message, i.e, the three digits that you have encrypted.
Question 3
(a) Consider the following workload:
Process Burst Time Priority Arrival Time
P1 60 2 0 P2 20 4 0 P3 50 1 10 P4 10 5 20 P5 20 3 50
Schedule the above processes using Shortest Remaining Time First (SRTF) and Preemptive Priority algorithms. Please note that for priority scheduling, a lower number indicates higher priority.
Compute the AWT (Average Waiting Time), Average Turnaround Time (ATAT) and Average Response Times (ART) for both of the given policies. Which one of these policies is better-suited to the given workload? [6 marks]
(b) Consider the following program:
The above software solution to the mutual exclusion problem for two processes has been suggested in the literature. Do you agree that the proposed solution is correct? If yes, explain with the help of supporting arguments and examples. If no, find a counter-example that demonstrates that this solution is incorrect and does not preserve mutual exclusion? [6 marks]
(c) Consider a computer system that runs 10,000 jobs per month with no deadlock- prevention or deadlock-avoidance scheme. Deadlocks occur about three times per
month, and the system operator must terminate and rerun about 40 jobs per dead- lock. Each job is worth about $3 (in CPU time + resources), and the manually terminated jobs tend to be about half-done when they are aborted.
A systems’ programmer has estimated that a deadlock-avoidance algorithm (like the banker’s algorithm) could be implemented in the system with an increase in the average execution time per job of about 5%. Since the machine currently has 30% idle time, all of the 10,000 jobs per month could still be run and completed on-time. Estimate the cost of running this system per month with and without any deadlock-avoidance scheme. In your calculations, also include the cost of an operator who charges $400 every time he manually intervenes and restarts the deadlocked processes. Finally, indicate which one of these two schemes would be more cost effective. Support your conclusions with appropriate calculations. [8 marks]