2. Consider a paging system with the page table stored in memory.

a. If a memory reference takes 110 nanoseconds, how long does a paged memory reference take?

b. If we add associative registers, and 80 percent of all page-table references are found in the associative registers(TLB), what is the effective memory reference time? (Assume that finding a page-table entry in the associativeregisters takes 15 ns, if the entry is there.)

3. Consider the following reference string:

a. How many page faults would this string produce under the FIFO page replacement strategy with three frames?

3	1	4	3	1	5	2	3	4	5	2	1	3	2	1

b. How many page faults would this string produce under the OPT replacement strategy with three frames?

3	1	4	3	1	5	2	3	4	5	2	1	3	2	1

c. How many page faults would this string produce under the LRU replacement strategy with three frames?

3	1	4	3	1	5	2	3	4	5	2	1	3	2	1

4. Briefly discuss the reason systems do not implement the Optimal page replacement algorithm

5. Briefly describe the enhanced second chance algorithm and compare it to FIFO and LRU.

6. What is the cause of thrashing? How does the system detect thrashing? Once it detects thrashing, what can the system do to eliminate this problem?

7. The CPU has a logical address format with 4 bits for the page number and 2 bits for the offset. The page table for aprocess is:Page frame

Page	Frame
0	4	I
1	7	I
2	1	I
3	5	I
4	3	V
5	1	I
6	6	I
7	0	V
8	7	V
9	2	I
10	1	V
11	4	V
12	5	V
13	6	V
14	2	V

15 6 I

Map the following logical addresses to physical addresses: (8 frames 3 bits for frame #) Logical Address Physical Address

1000 11 0011 11 1111 01

0110 10 0100 11

0010 10 1110 11

8. Consider a demand paging virtual memory system with 24 bit virtual address space, page size is (8KB or 2^13) andthe system has 8 MB of main memory. Assume the page table is single level and stored in memory.

a. When we split a logical address into page number and offset within the page, how many bits are used for the

page number, and how many bits are used for the offset?

b. Assuming page table entries are 4 bytes each and a single level page table is used, how many bytes are requiredto store a page table?

c. If the OS reserves 1 MB (128 frames) of physical memory for kernel code, buffers, etc., how many physicalframes are left for demand paging?

d. Suppose at some point in time our TLB contains the entries:

Page #	Frame #	Valid?
5	3	V
4	2	V
6	4	V

The user attempts to access the logical address 0000 0000 1000 1011 0011 0100. Is this a TLB miss? Briefly explain.

e. What is the physical address?

9. Suppose that a disk drive has 2000 cylinders, numbered 0 to 1999. The drive is currently serving a request at cylinder130, and the previous request was at cylinder 124. The queue of pending requests, in order, is

84, 1110, 30, 825, 200, 120, 980, 515, 33, 300

Starting from the current head position, what is the access sequence and the total distance (in cylinders) that the diskarm moves to satisfy all the pending requests, for each of the following disk-scheduling algorithms?

a. FCFS

b. SSTF

c. SCAN

d. LOOK

e. C-SCAN

f. C-LOOK