(6) The following picture given by the textbook shows the format of a virtual address with paging.

a)   What is the page size with this address format? __________

b)   What is the maximum number of pages a program can have? __________

(7) An TLB improves address translation performance. Which of the following are necessary (true or false).

a)    The user program is CPU bound.    (T/F)

b)   The user program exhibits locality. (T/F)

c)    The TLB memory is faster than the main memory. (T/F)

(8) Say whether the following statements are true or false.

a)   A virtual memory system can have segmentation and without paging. (T/F)

b)   It can have paging and without segmentation. (T/F)

c)    It can have paging and segmentation. (T/F)

(9) Give one advantage and one disadvantage of paging as compared to segmentation.

a)   Advantage ______________________________________________

b)   Disadvantage ____________________________________________

(10)A page table entry contains only the physical frame number (PFN). An TLB entry contains both the virtual page number and the PFN. Why?

_________________________________________________________________

_________________________________________________________________

(11)(6 points) The following are the five original rules of the MLFQ policy. R1: If priority(A) > priority(B), A runs

R2: If priority (A) = priority(B), A, B runs in RR

R3: New job at highest priority

R4: Once a job uses up its time allotment R, its priority is reduced R4a: If a job uses up all time slice T, its priority is reduced

R4b: If a job gives up the CPU before its time slice T, it stays at the same priority

R5: After some time S, move all the jobs to the topmost queue               a)   Which of these rules allow us to conclude that a job is CPU bound?

____________________________________________________________

b)   Which of these rules allow us to avoid starvation?

___________________________________________________________

c)   R in rule R4 should be greater than T in R4a and R4b. Is that true? Why?

___________________________________________________________

(12)(4 points) Suppose that the time to execute job(i) is t(i). Write a formula that gives the average turnaround time of n jobs. Why it is true that the SJF scheduling algorithm will give the minimum average turnaround time?

(13)(12 points) For a 32 bit microprocessor with 4KB pages.

a)    (4 points) The maximum virtual address space will be 4GB. Why?

___________________________________________________________

b)   What is the maximum number of entries in the page table? ____________

c)   How many pages will be needed to store the page table? ____________

d)   (4 points) Suggest one method to reduce the size of the page table.

Part 2: Longer questions

(14)(12 points) Fill in the following table to show what will happen from the time when the user process A calls read(), the operating system chooses user process B to execute, till user process B begins execution.

(15)(12 points) The following code segment describes the control flow in converting a virtual address to a physical address via a TLB. Suppose that the TLB lookup time is 10 nano second and memory lookup time is 100 nano second. (a) What is the average lookup time, for hit ratios of 60%, 50% and 40% if the TLB lookups (line 2) and memory lookups (line 12) are done one after another? (b) What if they are done in parallel? (c) Compare and discuss the results of (a) and (b).

(16)(12 points) The following is a code fragment intended to handle the sequence execution operator “;” of a shell in programming assignment  1. Point out three errors in the code and correct them.

void

runcmd (struct cmd *cmd)

{    …

(17)(12 points) Give four test cases (command strings) that you used in programming assignment 1, give their expected output and the reasons that you used them (best if illustrated with your equivalence partitioning). Discuss how do you know that the & operator is correctly implemented.