Weekly Notes for Week 17

• Due to the university lockdown we will still use Zoom for online teaching and this week also for the tutorials. The exercises are Thursday, 10am.

• In the lecture in week 17 we finish the few parts left of Chapter 11 (Mass-Storage Systems), and will then continue with Chapter 13 (File-System Interface). After next weeks lectures you will be able to work on the mandatory assignment 3 (to be published early next week latest).

Tutorial Session Week 17

See also the Weekly Notes from Week 14, as there are still important exercises from Chapter 8 to be discussed. In addition prepare the following exercises form Chapter 9 and from the first part of Chapter 10:

Chapter 9

1. (important) Name two differences between logical and physical addresses.

2. (important) Why are page sizes always powers of 2?

3. Consider a system in which a program can be separated into two parts: code and data. The CPU knows whether it wants an instruction (instruction fetch) or data (data fetch or store). Therefore, two base –limit register pairs are provided: one for instructions and one for data. The instruction base –limit register pair is automatically read-only, so programs can be shared among different users. Discuss the advantages and disadvantages of this scheme.

4. (important) Consider a logical address space of 64 pages of 1,024 words each, mapped onto a physical memory of 32 frames.
   • How many bits are there in the logical address?
   • How many bits are there in the physical address?

5. What is the effect of allowing two entries in a page table to point to the same page frame in memory? Explain how this effect could be used to decrease the amount of time needed to copy a large amount of memory from one place to another. What effect would updating some byte on one page have on the other page?

6. (important) Given six memory partitions of 300 KB, 600 KB, 350 KB, 200 KB, 750 KB, and 125 KB (in order), how would the first-fit, best-fit, and worst-fit algorithms place processes of size 115 KB, 500 KB, 358 KB, 200 KB, and 375 KB (in order)?

7. Assuming a 1-KB page size, what are the page numbers and offsets for the following address references (provided as decimal numbers):
   • 3085
   • 42095
   • 215201
   • 650000 -2000001
8. ((*important**) The BTV operating system has a 21-bit virtual address, yet on certain embedded devices, it has only a 16-bit physical address. It also has a 2-KB page size. How many entries are there in each of the following?
   • A conventional, single-level page table
   • An inverted page table What is the maximum amount of physical memory in the BTV operating system?
9. (important) Consider a logical address space of 256 pages with a 4-KB page size, mapped onto a physical memory of 64 frames.
   • How many bits are required in the logical address?
   • How many bits are required in the physical address?
10. (important) Consider a computer system with a 32-bit logical address and 4-KB page size. The system supports up to 512 MB of physical memory. How many entries are there in each of the following?
    • A conventional, single-level page table
    • An inverted page table

11. (important) Explain the difference between internal and external fragmentation.

12. Given six memory partitions of 100 MB, 170 MB, 40 MB, 205 MB, 300 MB, and 185 MB (in order), how would the first-fit, best-fit, and worst-fit algorithms place processes of size 200 MB, 15 MB, 185 MB, 75 MB, 175 MB, and 80 MB (in order)? Indicate which—if any—requests cannot be satisfied. Comment on how efficiently each of the algorithms manages memory.

13. (important) Most systems allow a program to allocate more memory to its address space during execution. Allocation of data in the heap segments of programs is an example of such allocated memory. What is required to support dynamic memory allocation in the following schemes?
    • Contiguous memory allocation
    • Paging

14. Explain why mobile operating systems such as iOS and Android do not support swapping.

15. (should be very easy) Assuming a 1-KB page size, what are the page numbers and offsets for the following address references (provided as decimal numbers)?
    • 21205
    • 164250
    • 121357
    • 16479315
    • 27253187
16. (hopefully easy, but important) Consider a logical address space of 2,048 pages with a 4-KB page size, mapped onto a physical memory of 512 frames.
    • How many bits are required in the logical address?
    • How many bits are required in the physical address?
17. (only for repetiition now) Consider a computer system with a 32-bit logical address and 8-KB page size. The system supports up to 1 GB of physical memory. How many entries are there in each of the following?
    • A conventional, single-level page table
    • An inverted page table
18. (for specific architecture, only) Consider the IA-32 address-translation scheme shown in Figure 9.22 or on the lecture slides.
    • Describe all the steps taken by the IA-32 in translating a logical address into a physical address.
    • What are the advantages to the operating system of hardware that provides such complicated memory translation?
    • Are there any disadvantages to this address-translation system? If so, what are they? If not, why is this scheme not used by every manufacturer?

Chapter 10

1. (very important) Under what circumstances do page faults occur? Describe the actions taken by the operating system when a page fault occurs.

2. Assume that you have a page-reference string for a process with m frames (initially all empty). The page-reference string has length p, and n distinct page numbers occur in it. Answer these questions for any page-replacement algorithms:
   • What is a lower bound on the number of page faults?
   • What is an upper bound on the number of page faults?
3. (important) Consider the following page-replacement algorithms. Rank these algorithms on a five-point scale from “bad” to “perfect” according to their page-fault rate. Separate those algorithms that suffer from Belady’s anomaly from those that do not.
   • LRU replacement
   • FIFO replacement
   • Optimal replacement
   • Second-chance replacement
4. An operating system supports a paged virtual memory. The central processor has a cycle time of 1 microsecond. It costs an additional 1 microsecond to access a page other than the current one. Pages have 1,000 words, and the paging device is a drum that rotates at 3,000 revolutions per minute and transfers 1 million words per second. The following statistical measurements were obtained from the system:
   • One percent of all instructions executed accessed a page other than the current page.
   • Of the instructions that accessed another page, 80 percent accessed a page already in memory.
   • When a new page was required, the replaced page was modified 50 percent of the time.

Calculate the effective instruction time on this system, assuming that the system is running one process only and that the processor is idle during drum transfers.

1. (important) Consider the page table for a system with 12-bit virtual and physical addresses and 256-byte pages.

   The list of free page frames is D, E, F (that is, D is at the head of the list, E is second, and F is last). A dash for a page frame indicates that the page is not in memory. Convert the following virtual addresses to their equivalent physical

   • 9EF
   • 111
   • 700
   • 0FF

2. Discuss the hardware functions required to support demand paging.

3. (important) Consider the two-dimensional array A: int A[][] = new int[100][100]; where A[0][0] is at location 200 in a paged memory system with pages of size 200. A small process that manipulates the matrix resides in page 0 (locations 0 to 199). Thus, every instruction fetch will be from page 0. For three page frames, how many page faults are generated by the following array-initialization loops? Use LRU replacement, and assume that page frame 1 contains the process and the other two are initially empty.

   • for (int j = 0; j < 100; j++)
       for (int i = 0; i < 100; i++)
           A[i][j] = 0;
     

   • for (int i = 0; i < 100; i++)
       for (int j = 0; j < 100; j++)
           A[i][j] = 0;
     

4. (important) Consider the following page reference string: 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6. How many page faults would occur for the following replacement algorithms, assuming one, two, three, four, five, six, and seven frames? Remember that all frames are initially empty, so your first unique pages will cost one fault each.
   • LRU replacement
   • FIFO replacement
   • Optimal replacement
5. Consider the following page reference string: 7, 2, 3, 1, 2, 5, 3, 4, 6, 7, 7, 1, 0, 5, 4, 6, 2, 3, 0 , 1. Assuming demand paging with three frames, how many page faults would occur for the following replacement algorithms?
   • LRU replacement
   • FIFO replacement
   • Optimal replacement

6. Suppose that you want to use a paging algorithm that requires a reference bit (such as second-chance replacement or working-set model), but the hardware does not provide one. Sketch how you could simulate a reference bit even if one were not provided by the hardware, or explain why it is not possible to do so. If it is possible, calculate what the cost would be.

7. (important) You have devised a new page-replacement algorithm that you think may be optimal. In some contorted test cases, Belady’s anomaly occurs. Is the new algorithm optimal? Explain your answer.

8. Segmentation is similar to paging but uses variable-sized “pages.” Define two segment-replacement algorithms, one based on the FIFO page-replacement scheme and the other on the LRU page-replacement scheme. Remember that since segments are not the same size, the segment that is chosen for replacement may be too small to leave enough consecutive locations for the needed segment. Consider strategies for systems where segments cannot be relocated and strategies for systems where they can.

9. (important) Consider a demand-paged computer system where the degree of multiprogramming is currently fixed at four. The system was recently measured to determine utilization of the CPU and the paging disk. Three alternative results are shown below. For each case, what is happening? Can the degree of multiprogramming be increased to increase the CPU utilization? Is the paging helping?
   • CPU utilization 13 percent; disk utilization 97 percent
   • CPU utilization 87 percent; disk utilization 3 percent
   • CPU utilization 13 percent; disk utilization 3 percent
10. We have an operating system for a machine that uses base and limit registers, but we have modified the machine to provide a page table. Can the page table be set up to simulate base and limit registers? How can it be, or why can it not be?