Computer Systems
Consider the following formula: (r1 ×(M1 +r2))−(r2 ×M2). Here r1 and r2 are
two registers, and M1 and M2 represent the contents of two memory addresses.
(a) Write an assembly program for computing the result of the formula into
register r3. Try to make the programme as short as possible.
[10 marks]
(b) Consider the instructions in the ISA in the appendix. Determine for each
instruction its type, i.e., whether it does one or a combination of the
following: (1) data transfer, (2) data processing, (3) control.
[10 marks]
Question 2 (Assembly code execution and analysis)
Consider the following assembly programme, where M1, M2, M3 and M4 denote
memory addresses, and r1, r2, r3 denote registers:
I1: LOAD r1, M1
I2: LOAD r2, M2
I3: MUL r1, r1, r2
I4: LOAD r2, M3
I5: LOAD r3, M4
I6: MUL r2, r2, r3
I7: ADD r1, r1, r2
Answer the following questions:
(a) Show the execution of the programme on the architecture described in the
appendix. Assume that the fetched and decoded instructions are stored in
an instruction window IW with unlimited capacity (and so you can store
2
any number of instructions in the IW). Explain where and why delay
slots appear. Assume that the processor can do out-of-order execution to
speed up the completion of the program. Assume that there is only one
bus, and that the fetching of instructions uses this bus. So the fetching of
an instruction can conflict with a stage where another instruction accesses
memory.
(b) Show all the dependencies (both true and false) in the code.
(c) Apply register renaming to remove the false dependencies.
[15 marks]
[10 marks]
[10 marks]
Subtotal: [35 marks]
Question 3 (Banker’s algorithm)
Consider the following situation concerning processes and resources assigned to
them: There are three processes p1, p2, p3, and four types of resources R1, R2,
R3, R4. The existence vector for the resources is E = (5, 5, 5, 5). The claim
matrix is as follows:
R1 R2 R3 R4
p1 5 3 0 4
p2 4 2 3 0
p3 4 2 2 1
The current situation for each process is:
• p1 holds 4 units of R1, 2 units of R2, 3 units of R4.
• p2 holds 3 units of R3.
• p3 holds 2 units of R2.
For the described situation, answer the following questions:
(a) Compute the request matrix and the availability vector.
[5 marks]
(b) Suppose that p2 requests 1 unit of R2 and that this request is granted.
Use the Banker’s algorithm to determine if the resulting state is a safe
state or not. Show each step of the algorithm.
[10 marks]
Subtotal: [15 marks]
3
Question 4 (Page allocation for virtual memory)
Consider the following string of page references 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2.
Complete a table showing the frame allocation assuming 4 page frames and
calculate the hit rate for the following scheduling algorithms:
(a) Least Recently Used
(b) FIFO
[5 marks]
[5 marks]
Subtotal: [10 marks]
Question 5 (Page tables)
A computer uses virtual memory implemented by paging. The TLB lookup
takes 50 ns and the update takes 100 ns. The PT lookup takes 2 µs and the
update takes 1 µs. Loading a word from main memory onto the CPU takes 5 µs
and loading a page from the disk into main memory takes 15 ms. The TLB hit
ratio is 0.5 and the main memory hit ratio is 0.2.
We define access time as the total time it takes to (1) find the referenced
word, (2) load it into the CPU, and (3) update the TLB and page tables if that
is necessary.
Answer the following questions:
(a) What is the average access time in the case of a TLB hit?
[5 marks]
(b) What is the average access time in the case of a TLB miss and PT hit?
[5 marks]
(c) What is the average access time if the case of a TLB miss and a PT miss?
[5 marks]
(d) What is the average access time in general?
[5 marks]
Subtotal: [20 marks]
