Section I: Answer two of the following questions: ( 6 marks each)

Q(1)- The table below contains a sample of logical addresses of a program memory references. Indicate which of the addresses is valid or invalid (generates memory access error) , and indicate what the physical address of the valid addresses. The relocation and limit register values are indicated below.(1 mark for each correct answer, red highlighted)

Logical address / Valid / Invalid / Physical address
600 / Valid / 8600
1300 / Invalid / Not generated
1100 / Valid / 9100
Relocation register / Limit register
8000 / 1200

------

Q(2)- Table(1) represents the page table of a certain process under execution. Table (2) represents a sequence of memory references generated by this process.

Indicate in table (2) which memory reference will generate a page fault and what is the corresponding physical address. The page size is 1024 byte.(Half mark for each correct answer, red highlighted)

Table (1) / Table(2)
Page number / Page offset / Page number / Displacement / Page fault / Physical address
7 / 3000 / 7 / 200 / NO / 3200
12 / 9000 / 11 / 800 / Yes / To be calculated
10 / 4000 / 5 / 300 / Yes / To be calculated
5 / 8000 / 4 / 900 / Yes / To be calculated
9 / 6000 / 12 / 100 / NO / 9100
1 / 2000 / 10 / 1100 / Yes / Illegal address, page size violation

------

Q(3)- A certain computer provide its users with virtual memory space of 240 bytes. The computer has a physical memory of 230 bytes. The virtual memory is implemented by paging, and the page size is 2048 bytes. A user program generates the address ( X):

a)Is this address real or physical?( In virtual memory environment all memory references generated by programs are logical addresses, hence this address is virtual) (2 Marks)

b)Explain how the system establishes the corresponding physical location.

-The page size is 2048 byte: page displacement is 11 bit ( 211=2048)

-The main memory is divided to 240/211= 2 29 page (536,870,912 pages)

-Page table has (536,870,912) entry each of (29 bit) length.

-The first (11bits) in the (X) address is the displacement within the page, while the remaining (29) bits are the page address to be referenced from page table entries.

(4 Marks: 1 mark for each of the above mentioned answer details)

------

Section I I: Answer two of the following questions: ( 8 Marks)

Q(1): Consider the following paging reference string:

1,2,3,4,5,3,4,1,6,7,8,7,8,9,7,8,9,5,4,5,4,2

-Compare the performance of the following page replacement algorithms:

a)Least Recently used (LRU).

b)Most Frequently Used (MFU).(Hint: if two or more pages have an equal and maximum (most) number of references, among them, choose the oldest page available in memory frame and replace it). When four page frames are used.

Solution:

a)- LRU: (9) page faults

4 / 5 / 3 / 4 / 1 / 6 / 7 / 8 / 7 / 8 / 9 / 7 / 8 / 9 / 5 / 4 / 5 / 4 / 2
3 / 4 / 5 / 3 / 4 / 1 / 6 / 7 / 8 / 7 / 8 / 9 / 7 / 8 / 9 / 5 / 4 / 5 / 4
2 / 3 / 4 / 5 / 3 / 4 / 1 / 6 / 6 / 6 / 7 / 8 / 9 / 7 / 8 / 9 / 9 / 9 / 5
1 / 2 / 2 / 2 / 5 / 3 / 4 / 1 / 1 / 1 / 6 / 6 / 6 / 6 / 7 / 8 / 8 / 8 / 9

b)- MFU: (11) page faults

1 / 5 / 3(2) / 3(2) / 1 / 6 / 7 / 8 / 8 / 8(2) / 9 / 7 / 8 / 8 / 5 / 4 / 4 / 4(2) / 2
2 / 4 / 5 / 5 / 5 / 1 / 6 / 7 / 7(2) / 7(2) / 8(2) / 9 / 7 / 7 / 8 / 5 / 5(2) / 5(2) / 4(2)
3 / 3 / 4 / 4(2) / 4(2) / 5 / 1 / 6 / 6 / 6 / 6 / 6 / 9 / 9(2) / 7 / 8 / 8 / 8 / 8
4 / 2 / 2 / 2 / 2 / 2 / 5 / 1 / 1 / 1 / 1 / 1 / 6 / 6 / 6 / 7 / 7 / 7 / 7

LRU performs better than MFU for this page string. ( 4 marks for each analysis)

Q(2): Consider a demand-paging system with the following time-measured utilization:

-CPU utilization 50%

-Paging disk 95%.

-Other I/O utilization 85%.

For each of the following, say whether it will ( or not) improve CPU utilization. Justify your answers: (1 Mark for each correct answer)

a)Install faster CPU. (It will not improve the utilization factor (CPU UF) as the utilization factor is already low)

b)Install bigger paging disk. (it will not improve the(CPU UF) as the low (CPU UF) is not related in this case to the size of secondary memory)

c)Increase the multiprogramming degree.( No: processes are spending significant time in paging, increasing multiprogramming degree might further reduce (CPU UF))

d)Decrease the multiprogramming degree.( Yes: this procedure might reduce the competition for free frames in memory and allow the CPU to execute more processes and further increase (CPU UF) )

e)Install more main memory.(Yes: more memory will decrease the need for page replacement. This is likely to increase (CPU UF))

f)Install multi-bus, multi-channels I/O devices.( Yes: The current (I/O) UF is high, installing faster I/O devices will provide more data to CPU and is likely to increase (CPU UF))

g)Reduce page size.(No: the (CPU UF) is already low, reducing the page size will lead the monitor to schedule more new processes, which might lead to trashing)

h)Add associative memory.(as the page level is high, most of page references are generating page fault. The main time delay is due to I/O operations. Low Associative memory access time will not significantly contribute to the improving (CPU UF))