7) The page table contains 2^32/2^13 entries, which is 524, 288. 524,288*100ns = 52msec therefore 
loading the page table takes 52 msec. If a process gets 100 msec, this consists of 52 msec for load-
ing the page table and 48 msec for running. Thue 52% of the time is spent loading page tables.



8) Twenty bits are used for the virtual page numbers, leaving 12 over for the offset. this yields a 
4K page. Twenty bits for the virtual page implies 2^20 pages.



9) The reference string, where I stands for an instruction reference and D for a data reference, is:

Load word 6144...	1(I), 12(D)

Push register 0 onto...	2(I), 15(D)

Call a procedure...	2(I), 15(D)

Subtract the immed...	10(I)

Compare the actual...	10(I), 15(D)

Jump if equal...	10(I)



11) The effective instruction time is 100*h + 500*(1-h), where h is the hit rate. If we equate this for-
mula with 200 and solve for h, we find that h must be at least 0.75.



14) NRU removes page 0. FIFO removes page 2. LRU removes page 1. Second chance removes 
page 0.



15) The page frames for FIFO are as follows:

FIFO: 	0 1 7 2 3 2 7 1 0 3

	x x x x x - - - x - => 6 faults

LRU: 	0 1 7 2 3 2 7 1 0 3

	x x x x x - - - x x => 7 faults

FYI: LRU list order:

F(0),F(0,1),F(0,1,7),F(0,1,7,2),F(0,1,7,2,3),(0,1,7,3,2),

(0,1,3,2,7),(0,3,2,7,1),F(3,2,7,1,0),F(2,7,1,0,3)



16) The counters are:

Page 0: 01101110

Page 1: 01001001

Page 2: 00110111

Page 3: 10001011



17) The seek plus rotational latency is 40 msec. For 2K pages, the transfer time is 1.25 msec, for a 
total of 41.25 msec. Loading 32 of these pages will take 1.32 sec. For 4K pages, the transfer time is 
doubled to 2.5 msec, so the total time per page is 42.5. Loading 16 of these pages takes 0.68 sec.



19) The text is 8 pages, the data are 5 pages, and the stack is 4 pages. The programs does not fit 
because it needs 17 4096-byte pages. With a 512-byte page, the text is 64 pages, the data are 33 
pages and the stack is 31 pages, for a total of 128 512-byte pages, which fits.



22) Internal fragmentation occurs when the last allocation unit is not full. External fragmentation 
occurs when space is wasted between 2 allocation units. In a paging system, the wasted space in 
the last page is lost to internal fragmentation. In a pure segmentation system, some space is 
invariably lost between the segments. This is due to external fragmentation.