MSc EXAMINATION
Department of Computer Science and Information Systems
COMPUTER SYSTEMS (COIY060H7)
CREDIT VALUE: 15 credits
Date of examination: [[DAY]], [[MONTH]] 2022
Duration of paper: 10:00–13:00
1. (a) Explain the importance of efficient input/output (I/O) management in the con- text of operating systems. (4 marks)
Marking scheme: Any reasonable explanation will suffice. Marks will be deducted for incorrectly describing I/O.
(b) Explain how RAID schemas help improve disk I/O. (6 marks)
Marking scheme: Any reasonable explanation will suffice. Marks will be deducted for incorrectly describing RAIDs respectively.
(c) A hard disk spins at 6000 rpm (revolutions per minute), and it takes 65 μs (on average) for the head to traverse one track. Consider the following sequence of disk track requests: 175, 155, 195, 10, 111, 21, 69, 62, 96. Assume that initially the head is at track 100 and is moving in the direction of increasing track number. Compute the time it takes to serve the requests using
• FIFO, (3 marks)
• SSF (shortest seek first), (4 marks)
• SCAN (elevator) algorithms, (3 marks)
Marking scheme: Marks will be deducted for flaws in the computations and one mark will be deducted for each arithmetic mistake.
2. Consider the following attempt to solve the dining philosophers problem for five philosophers.
semaphore fork[5] = 1
semaphore s = 1
int i
void philosopher(int i)
{
while(true){
think();
wait(s);
wait(fork[i]);
wait(fork[i + 1] mod 5);
signal(s);
eat();
wait(s);
signal(fork[i]);
signal(fork[i + 1] mod 5);
signal(s);
}
}
(a) Explain what semaphores are and the effect of the wait and signal operations. Describe how semaphores can be used for concurrent programming. (6 marks)
Marking scheme: Any reasonable explanation will suffice, marks will be de- ducted if semaphores are incorrectly defined.
(b) Explain whether this code avoids deadlock. (6 marks)
Marking scheme: +3 for identifying if it avoids deadlock, +3 points for identi- fying if it enforces mutual exclusion. If correctly identified if it avoids deadlock, but the reason is incorrect, 3 points max.
(c) Explain whether this code avoids starvation. (4 marks)
Marking scheme: +2 for correctly identifying if it avoids starvation, +2 points for giving a correct reason why. If correctly identified if it prevents starvation, but the reason is wrong, 2 points max.
(d) Modify the code so that it provides a satisfactory solution to the dining philoso- phers problem. Justify your answer. (4 marks)
Marking scheme: +2 marks for a correct modification and +2 marks for the justification. 2 marks total if justification is incorrect.
3. This question consists of the following subquestions:
(a) Consider the following list of words/expressions:
• memory buffer,
• control,
• addressing,
• write back,
• read,
• memory,
• register,
• CPU,
• execute,
• operand.
Replace the numbers [n] in the text by an appropriate word or expression from this list.
The following text describes the execution of a LOAD instruction:
The instruction has to be fetched and then to be decoded by the [1] unit of the CPU so that the [2] mode used to identify the [3] of the instruction is understood. If the instruction uses [4] addressing, then the next stage is [4] read, however, if [5] addressing is used then this stage can be skipped. In the latter case, data transfer between main memory and the [6] happens during the [7] stage: the CPU sends a [8] signal to main memory together with the address of the [3], the data is transferred via the bus and arrives into the [9] register. Finally, during the [10] stage the operand is copied into the target register. (10 marks)
Marking scheme: +1 mark for each correct replacement
(b) Consider the following scenario. There are five processes A, B, C, D and E with the following arrival times (in seconds), and run times (in seconds).
|
|
A
|
B
|
C
|
D
|
E
|
|
arrival time
|
|
0
|
2
|
5
|
6
|
10
|
|
run time
|
|
3
|
4
|
2
|
2
|
3
|
Compute the average turnaround time for the five processes A to E using each of the following short-term scheduling algorithms:
i. first-come-first-served (4 marks)
Marking scheme: Full marks for a correct answer and -1 mark for each process in the wrong order.
ii. round-robin with quantum being equal to 1 (i.e. q=1). (6 marks)
Marking scheme: Full marks for a correct answer -1 mark for each process in the wrong order
4. Consider the computation (m1 + [r1]) * (m2 * r2) where m1, m2 denote the contents of memory locations, [r1] denotes the content of a memory location whose address is in the register and r2 denotes the content of the register.
(a) Write assembly code for this computation. Use at most two operands for each instruction (Use the 2 argument ISA supplied with your exam) and use at most three registers altogether. (8 marks)
Marking scheme: 4 Marks will allocated according to whether the code com- pute the formula correctly. 4 marks deducted if more than 3 registers are used.
(b) Identify the dependencies (both true and false) in your code. (4 marks)
Marking scheme: Full marks for a correct solution, 1 Mark for will be de- ducted for each incorrect dependency.
(c) List the various addressing modes in your code. (4 marks)
Marking scheme: Full marks for a correct solution, 1 Mark for will be de- ducted for each incorrect addressing mode.
(d) Describe an addressing mode suitable for supporting VM (virtual memory). (4 marks)
Marking scheme: Any reasonable answer will suffice, marks will be deducted if the method would not be suitable for VM.
5. Consider a superscalar processor with two functional units for each of the five pipeline stages: fetch, decode, register read, execute, write back. In this pipeline data move- ment happens in the execute stage and you have an instruction window of unlimited size to store decoded instructions.
(a) Show the pipeline activity when your code for the previous question is executed using the in-order-issue/in-order-completion policy. State explicitly any addi- tional assumptions you made about processing the instructions. (10 marks)
Marking scheme: Marks will be deducted for missing required pipeline stages or using unnecessary stages.
(b) Remove the false dependencies from your code by using the register renaming technique. (4 marks)
Marking scheme: Full marks for a correct solution, 1 Mark for will be de- ducted for each dependency that is not removed.
(c) Show the pipeline activity when the modified code is executed by using the out-of-order issue/out-of-order completion policy. (6 marks)
Marking scheme: Marks will be deducted for missing required pipeline stages or using unnecessary stages, violating data dependencies and missing opportu- nities for out-of-order execution.