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]