Assignment 8: Address Translation and Virtual Memory Quiz Answers

Philosophy and ethics12.25 KB

Assignment 8 - Address Translation & Virtual Memory

Consider the following page reference string: A, B, C, D, B, A, E, F, B, A, B, C, G, F, C, B, A, B, C, F. How many page faults would occur using the MIN replacement algorithm, assuming four frames? Remember that all frames are initially empty, so your first unique pages will cost one fault each.

  1. 9

Which of the following is a term to describe when a process spends more time paging than executing, which results in a dramatic decrease in performance?

  1. Thrashing

Consider the following page reference string: A B C D B A E F B A B C G F C B A B C F. How many page faults would occur using the FIFO replacement algorithm, assuming seven frames?

  1. 7

True or False

Consider a demand-paged computer system where the degree of multiprogramming is currently fixed at four. The system was recently measured with CPU utilization of 13 percent and paging disk utilization of 97 percent. In this case, thrashing is occurring, leading to an increase in the degree of multiprogramming but a decrease in the CPU utilization.

  1. True

True or False

Suppose that you want to use a page replacement algorithm that requires a reference bit (such as second-chance replacement or working-set model), but the hardware does not provide one. If so, the valid/invalid bit supported in hardware can be used to simulate the reference bit. Initially set the bit to invalid. On first reference, a trap to the operating system is generated. The operating system will set a software bit to 1 and reset the valid/invalid bit to valid.

  1. True

True or False

Some systems automatically delete all user files when a user logs off or a job terminates, unless the user explicitly requests that they be kept. Other systems keep all files unless the user explicitly deletes them. Is it true or false that the following describes the relative merits of each approach? Deleting all files not specifically saved by the user has the advantage of minimizing the file space needed for each user by not saving unwanted or unnecessary files. Saving all files unless specifically deleted is more secure for the user in that the user cannot lose files inadvertently by forgetting to save them.

  1. True

A page fault occurs when:

  1. A process tries to access a page that is not loaded into memory

If memory access time is 250 nanoseconds and average page fault service time is 10 milliseconds, which of the following is the maximum probability of a page fault if it is required to keep the performance degradation less than 20%?

  1. 0.000005

Which of the following is terminology that describes the case that allows the parent and child processes to initially share the same pages, but when either process modifies a page, a copy of the shared page is created?

  1. Copy-on-write

Suppose we have the following page accesses: A B C D B C D A B A A C A D. And that there are three frames within our system. Using the LRU replacement algorithm, what is the number of page faults for the given reference string?

  1. 8

Consider a text editor that saves a file whenever you click a Save button. Suppose that when you press the button, the editor simply (1) animates the button "down" event (e.g., by coloring the button grey), (2) uses the write() system call to write your text to your file, and then (3) animates the button "up" event (e.g., by coloring the button white).

Which of the following could be a result if a user edits a file, saves it, and then turns off her machine by flipping the power switch (rather than shutting the machine down cleanly)?

  1. When the user turns the machine on and looks at the file, she may see the old version of the file, a mix of the old and new versions, or the new version. The result generally depends on the file system implementation.

  2. write() only guarantees that the updates are in the kernel's memory; it does not guarantee that the updates are flushed to stable storage.

True or False

When a process references pages according to a Zipf distribution (e.g., a web server with its memory consisting of cached web pages), the likelihood of a reference depends on its popularity rank, not whether it has been recently used or not. Recently referenced objects are more likely (than random chance) to be popular, and so LRU will do better than random. But a replacement algorithm that measures frequency of use will likely outperform both.

  1. True

Consider two programs, one that exhibits spatial and temporal locality, and the other that exhibits neither. To make the comparison fair, they both use the same total amount of virtual memory: that is, they both touch N distinct virtual pages, among a much larger number of total references. Select which of the following is a true description of the behavior of the program assuming clock page replacement algorithm and the two programs run at the same time on the machine.

  1. Since the performance of the program with no locality is basically the speed of the page fault handler and disk access, its performance will be cut in half when the locality program is competing for disk (when there is too little memory for either). At higher loads, the locality program will not be using the disk, but it will steal pages, making it appear as if the program has only a few pages even as the system approaches N.

  2. The program with no locality will steal pages away from the program that has locality. When they are both below the working set, this will worsen performance (of the locality program) somewhat. Above the working set, however, the program without locality will still take frequent page faults. Since that program is spending most of its time in the page fault handler, it will not be setting the reference bit on its pages. So the clock algorithm will tend to discard those pages, preferentially keeping the pages of the program with locality. So the performance will converge on the performance the program with locality would have had if it was running on its own.

Most modern computer systems choose a page size of 4KB. Which of the following can be reasons why doubling the page size might increase performance?

For convenience, let us term the two sub-pages of the new page as I and I+1. Whenever I is in memory, I+1 will be in memory automatically (and vice versa).

  1. If the program exhibits spatial locality (at the new page granularity), then both I and I+1 are needed at the same time, reducing page faults.

  2. Fewer pages implies fewer use/modified bits to keep track of.

  3. Fewer pages implies less space taken up by page tables, leaving more room for useful pages, decreasing page faults.

  4. Increasing the page size increases the range of addresses that can be translated by a fixed number of entries in the TLB.

Most modern computer systems choose a page size of 4KB. Which of the following can be reasons why doubling the page size might decrease performance?

For convenience, let us term the two sub-pages of the new page as I and I+1. Whenever I is in memory, I+1 will be in memory automatically (and vice versa).

  1. Disk access time is increased slightly, as both pages need to be written/read from disk, even when only one is needed.

  2. If the program exhibits no spatial locality (at the new page granularity), there will be less room for useful pages, increasing page faults.

  3. Internal fragmentation if application memory regions are small compared to the new page size.

  4. Likewise, whenever any part of I is referenced, both subpages are marked as recently used, even if the other half is not being used.

Quiz 5 - Hwk #8 + File System, Storage Devices, and Files and Directories

Consider a demand-paging system with a paging disk that has an average access and transfer time of 6 milliseconds for a single page. Addresses are translated through a page table in main memory, with an access time of 100 nanoseconds per memory access. Thus, each memory reference through the page table takes two accesses. The system has a 48-entry TLB to speed up memory accesses. Assume the TLB access time is negligible. Assume also that 99% of memory accesses result in a TLB hit, and of the remaining 1%, 5 percent of them cause page faults. What is the effective memory access time?

Hint: With TLB hit, access time is only 1 memory access; with TLB miss (no page fault), access time is 2 memory accesses (1 page table and 1 memory access); and finally with TLB miss (page fault), access time is I/O transfer plus 3 memory access (1 for page table but entry invalid, 1 page table again when entry revalidated after I/O transfer, 1 for memory access).

  1. 3101.05 ns

Which of the following can be a reason explaining why mobile devices generally do not support swapping?

  1. Limited space constraints of flash memory.

  2. Poor throughput between main memory and flash memory.

Suppose an application is assigned 4 pages of physical memory and the memory is initially empty. It then references pages in the following sequence:

A C B D B A E F B F A G E F A

How many fault pages will result into the four frames of physical memory, using the Clock replacement policy?

  1. 9

Suppose an application is assigned 4 pages of physical memory and the memory is initially empty. It then references pages in the following sequence:

A C B D B A E F B F A G E F A

How many fault pages will result into the four frames of physical memory, using the MIN (Optimal) replacement policy?

  1. 7

Suppose an application is assigned 4 pages of physical memory and the memory is initially empty. It then references pages in the following sequence:

A C B D B A E F B F A G E F A

How many fault pages will result into the four frames of physical memory, using the LRU replacement policy?

  1. 8

A system can perform only at the speed of its slowest bottleneck. Disks or disk controllers are frequently the bottlenecks in modern systems, as their individual performance cannot keep up with that of the CPU and system bus. When I/O is balanced among disks and controllers, neither an individual disk nor a controller is overwhelmed, so that bottleneck is avoided.

  1. True

Which of the following represents an approximation of a program's locality?

  1. Working set

True or False

Consider a demand-paged computer system where the degree of multiprogramming is currently fixed at four. The system was recently measured with CPU utilization of 13 percent and paging disk utilization of 97 percent. In this case, thrashing is occurring, leading to an increase in the degree of multiprogramming but a decrease in the CPU utilization.

  1. True

Download

PDF Word HTML