Operating System Memory

1. Exercise 9.28 on page 449 (9.10 on textpage 398 for version 7). Consider a demand-paging system with the following time-measured utilizatoins

CPU utilization 20%
Paging disk 97.7%
Other I/O devices 5%

For each of the following, say whether it will (or is likely to) improve CPU utilization. Explain your answers.

• Install a Faster CPU
• Install a bigger paging disk
• Increase the degree of multiprogramming
• Decrease the degree of multiprogramming
• Install more main memory
• Install a faster hard disk or multiple controllers with multiple hard disks
• Add prepaging to the page-fetch algorithms
• Increase the page size.

2. Exercise 9.31 on page 450 (9.13 on page 399 for version 7). Give the detailed steps for questions b) and c).

9.31 A page-replacement algorithm should minimize the number of page faults. We can achieve this minimization by distributing heavily used pages evenly over all of memory, rather than having them compete for a small number of page frames. We can associate with each page frame a counter of the number of pages associated with that frame. Then, to replace a page, we can search for the page frame with the smallest counter.

a. Define a page-replacement algorithm using this basic idea. Specifically address these problems:

• What is the initial value of the counters?
• When are counters increased?
• When are counters decreased?
• How is the page to be replaced selected?

b. How many page faults occur for your algorithm for the following reference string with four page frames?

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

3. 10.15 on page 498 (10.6 on textpage 440 for version 7). If the operating system were to know that a certain application is going to access the file data in a sequential manner, how could it exploit this information to improve performance?

4. 11.14 on page 541 (11.6 on textpage 480 for version 7). Consider a file system on a disk that has both logical and physical block sizes of 512 bytes. Assume that the information about each file is already in memory. For each of the three allocation strategies (contiguous, linked, and indexed), answer these questions :

• How is the logical-to-physical address mapping accomplished in this system (for the indexed allocation, assume that a file is always less than 512 blocks long.)
• If we are currently at logical block 10 (the last block accessed was block 10) and want to access logical block 4, how many physical blocks must be read from the disk?