Weekly Notes for Week 16

Please note: Intentionally a superset of the exercises to be covered in the tutorial section is listed. The intention is to make you aware of what you should be able to solve with enough time and the slides/book/video lecture available, and to give you material for the preparation of the exam (some of the questions indeed introduce new content, but that is usually not the case). Several of the exercises have now attributes, if they are, e.g., deemed to be very important.
In the lectures in week 16 we finish the few parts left of Chapter 10 and the discuss Chapters 13 (File-System Interface) and Chapter 14 (File-System Implementation), and if time allows Chapter 15 (File-System Internals). We will cover the missing Chapter 12 after this.

Tutorial Session Week 16

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

Chapter 10

Assume that a program has just referenced an address in virtual memory. Describe a scenario in which each of the following can occur. (If no such scenario can occur, explain why.)
- TLB miss with no page fault
- TLB miss with page fault
- TLB hit with no page fault
- TLB hit with page fault
Important Consider a system that uses pure demand paging.
- When a process first starts execution, how would you characterize the page-fault rate?
- Once the working set for a process is loaded into memory, how would you characterize the page-fault rate?
- Assume that a process changes its locality and the size of the new working set is too large to be stored in available free memory. Identify some options system designers could choose from to handle this situation.
repetition The following is a page table for a system with 12-bit virtual and physical addresses and 256-byte pages. Free page frames are to be allocated in the order 9, F, D. A dash for a page frame indicates that the page is not in memory.

Convert the following virtual addresses to their equivalent physical addresses in hexadecimal. All numbers are given in hexadecimal. In the case of a page fault, you must use one of the free frames to update the page table and resolve the logical address to its corresponding physical address.
Consider the page table for a system with 16-bit virtual and physical addresses and 4,096-byte pages.

The reference bit for a page is set to 1 when the page has been referenced. Periodically, a thread zeroes out all values of the reference bit. A dash for a page frame indicates that the page is not in memory. The page-replacement algorithm is localized LRU, and all numbers are provided in decimal.
- Convert the following virtual addresses (in hexadecimal) to the equivalent physical addresses. You may provide answers in either hexadecimal or decimal. Also set the reference bit for the appropriate entry in the page table.
  - 0x621C
  - 0xF0A3
  - 0xBC1A
  - 0x5BAA
  - 0x0BA1
- Using the above addresses as a guide, provide an example of a logical address (in hexadecimal) that results in a page fault.
- From what set of page frames will the LRU page-replacement algorithm choose in resolving a page fault?
(repetition) Apply the (1) FIFO, (2) LRU, and (3) optimal (OPT) replacement algorithms for the following paGe-reference strings:
- 2, 6, 9, 2, 4, 2, 1, 7, 3, 0, 5, 2, 1, 2, 9, 5, 7, 3, 8, 5
- 0, 6, 3, 0, 2, 6, 3, 5, 2, 4, 1, 3, 0, 6, 1, 4, 2, 3, 5, 7
- 3, 1, 4, 2, 5, 4, 1, 3, 5, 2, 0, 1, 1, 0, 2, 3, 4, 5, 0, 1
- 4, 2, 1, 7, 9, 8, 3, 5, 2, 6, 8, 1, 0, 7, 2, 4, 1, 3, 5, 8
- 0, 1, 2, 3, 4, 4, 3, 2, 1, 0, 0, 1, 2, 3, 4, 4, 3, 2, 1, 0
Discuss situations in which the least frequently used (LFU) page-replacement algorithm generates fewer page faults than the least recently used (LRU) page-replacement algorithm. Also discuss under what circumstances the opposite holds.
The KHIE (pronounced “k-hi”) operating system uses a FIFO replacement algorithm for resident pages and a free-frame pool of recently used pages. Assume that the free-frame pool is managed using the LRU replacement policy. Answer the following questions:
- If a page fault occurs and the page does not exist in the free-frame pool, how is free space generated for the newly requested page?
- If a page fault occurs and the page exists in the free-frame pool, how are the resident page set and the free-frame pool managed to make space for the requested page?
- To what does the system degenerate if the number of resident pages is set to one?
- To what does the system degenerate if the number of pages in the free-frame pool is zero?
Explain why compressed memory is used in operating systems for mobile devices.
Suppose that your replacement policy (in a paged system) is to examine each page regularly and to discard that page if it has not been used since the last examination. What would you gain and what would you lose by using this policy rather than LRU or second-chance replacement?
(important) Is it possible for a process to have two working sets, one representing data and another representing code? Explain.
(important) In a 1,024-KB segment, memory is allocated using the buddy system. Which allocations are made (you could draw a tree illustrating the allocations) after the following memory requests are allocated:
- Request 5-KB
- Request 135 KB.
- Request 14 KB.
- Request 3 KB.
- Request 12 KB.
Next, modify the tree/allocations for the following releases of memory. Perform coalescing whenever possible:
- Release 3 KB.
- Release 5 KB.
- Release 14 KB.
- Release 12 KB.
(interesting) The slab-allocation algorithm uses a separate cache for each different object type. Assuming there is one cache per object type, explain why this scheme doesn’t scale well with multiple CPUs. What could be done to address this scalability issue?