1.Suppose you have a machine whose hardware supports paging but not segmentation. Is it possible to implement an OS for this machine that would support segmentation eciently? Assume there is no translation look-aside buer. Explain and take into account the eect of having the look-aside buer.

2. Suppose pages were referenced in the following order: A,B,C,D,A,B,E(w),A(w),B,C,D,E, where (w) means that the corresponding page was written to. Assume that initially the main memory was empty and that it contains just 3 frames. How many page transfers there will be under these page replacement strategies: (a) FIFO (b) LRU

3. For the previous problem and the FIFO page replacement algorithm, assume that the hardware uses an inverted page table. Draw pictures that show the evolution of the inverted page table as pages are swapped in or out. Include dirty bits and whatever is necessary.

4.Consider hardware that is based on inverted page tables. Does the format of page table entries require the valid/invalid bit? Explain.

5.An instruction takes 2 time units to execute. Processing a pagefault takes an additional n time units (just the cpu time, I/O is asynchronous). Page faults happen every k instructions. Give a formula for the eective instruction time (i.e., the average number of time units CPU needs to execute an instruction). Explain.

6. Similar to the previous problem, but now we have a fast cache where memory pages are kept (note: memory pages themselves are kept in the cachenot the page table entries). The times are as follows: Referencing a word of a page in the cache: c Referencing a word in main memory: m to load page in cache, then restart the reference using cache. Referencing a word on disk: d to bring page from disk to main memory, then copy page to cache, then restart reference. The cache hit ratio is 0.9 The main memory hit ration is 0.6 Ignoring the overhead of accessing page tables, compute the average time required for memory access in such a system?