nix

10.    Virtual Memory

• Virtual memory is a technique that allows the execution of processes that may not be completely in memory.
• Virtual memory abstracts main memory into an extremely large, uniform array of storage, separating logical memory as viewed by the user from physical memory.
• The entire program does not have to be in memory, because
  • Error handling codes are not frequently used.
  • Arrays, tables, large data structures are allocated memory more than necessary many parts are not used at the same time.
  • Some options and cases may be used rarely.
• Benefits
  • Program length is not restricted to real memory size. That is, virtual address size can be larger than physical address size.
  • Can run more programs because those space originally allocated for the un-loaded parts can be used by other programs.
  • Save load/swap I/O time because we do not have to load/swap a complete program.
• Virtual memory is the separation of user logical memory form physical memory.
• This permits to have extremely large virtual memory, which makes programming large systems much easier to use.
• Because pages can be shared, this further improves performance and save time.
• Virtual memory is commonly implemented with demand paging, demand segmentation or demand paging+segmentation.

• A demand-paging system is similar to a paging system with swapping.
• A lazy swapper never swaps a page into memory unless that page will be needed.
• We are now viewing a process as a sequence of pages, rather than as one large contiguous address space, a swapper manipulates entire processes, whereas a pager is concerned with the individual pages of a process.

10.2.1          Basic Concepts

• The translation from a virtual address to a physical address is the same as what a paging system does.
• However, there is an additional check. If the page is not in physical memory (i.e., the valid bit is not set), a page fault (i.e., a trap) occurs. The paging hardware, in translating the address through the page table, will notice that the invalid bit is set, causing a trap to the OS.
• If a page fault occurs, we need to do the following:
  • Find an unused page frame. If no such page frame exists, a victim must be found and evicted.
  • Write the old page out and load the new page in.
  • Update both page tables.
  • Resume the interrupted instruction.
• Details of Handling a Page Fault
  • Trap to the OS                                                                                 // a context switch occurs
  • Make sure if it is a page fault
  • If the address is not a legal one then address error, return
  • Find an unused page frame                                                        // page replacement algorithm
  • Write the page back to disk                                                          // page out
  • Load the new page form disk                                                      // page in
  • Update both page tables                                                              // two pages are involved!
  • Resume the execution of the interrupted instruction
• Pure demand paging: Never bring a page into memory until it is required.
• Hardware Support
  • Page Table Base Register, Page Table Length Register, and a Page Table.
  • Each entry of the page table must have a valid/invalid bit. Valid means that page is in physical memory. The address translation hardware must recognize this bit and generate a page fault if the valid bit is not set.
  • Secondary Memory: use a disk.
• Too Many Memory Accesses?
  • Each address reference may cause at least two memory accesses, one for page table look up and the other for accessing the item. It may be worse!

10.2.2          Performance of Demand Paging

• Let p be the probability of a page fault, the page fault rate, 0 <= p <= 1.
• The effective access time is (1-p) * memory access time + p * page fault time.
• The page fault rate p should be small, and memory access time is usually between 10 and 200 nanoseconds.
• To complete a page fault, three components are important:
  • Serve the page-fault trap
  • Read in the page, a bottleneck
  • Restart the process
• Suppose memory access time is 100 nanoseconds, paging require 25 milliseconds (software and hardware). Then, effective access time is

(1-p)*100 + p*(25 milliseconds)
= (1-p)*100 + p*25,000,000 nanoseconds
= 100 + 24,999,900*p nanoseconds

• If the page fault rate is 1/1000, the effective access time is 25,099 nanoseconds = 25 microseconds. It is 250 times slower!
• If we wish it is only 10% slower, effective access time is no more than 110 and p=0.0000004.

10.3.1          Copy-on-Write

• Process creation using the fork() system call may initially bypass the need for demand paging by using a technique similar to page sharing.
• Traditionally fork() worked by creating a copy of the parent’s address space for the child, duplicating the pages belonging to the parent.
• Copy-on-write works by allowing the parent and child processes to initially share the same pages. These shared pages are marked as copy-on-write pages, meaning that if either process writes to a shared page, a copy of the shared page is created.
• Many OSs provide a pool of free pages for such requests, zero-fill-on-demand pages have been zeroed-out before being allocated, thus erasing the previous contents of the page.
• With vfork() (virtual memory fork) the parent process is suspended and the child process uses the address space of the parent. Because vfork() does not use copy-on-write, if the child process changes any pages of the parent’s address space, the altered pages will be visible to the parent once it resumes.

10.3.2          Memory-Mapped Files

• Use virtual-memory techniques to treat file I/O as routine memory accesses. Memory mapping a file allowing a part of the virtual-address space to be logically associated with a file.
• Memory mapping a file is possible by mapping a disk block to a page (or pages) in memory. A page-sized portion of the file is read from the file system into a physical page.

• Three Important Issues in Virtual Memory
  • A page table can be very large. If an address has 32 bits and page size is 4K, then there are 2³²/2¹² = 2²⁰ = (2¹⁰)² = 1M entries in a page table per process!
  • Virtual to physical address translation must be fast. This is done with TLB.
  • Page replacement. When a page fault occurs and there is no free page frame, a victim page must be selected. If the victim is not selected properly, system degradation may be high.

10.4.1          Basic Scheme

• Basic scheme
  • Find the desired page on the disk
  • Find a free page frame in physical memory
    • If there is a free page frame, use it
    • If there is no free page frame, use a page-replacement algorithm to find a victim page
    • Write this victim page back to disk and change the page table and page frame table
  • Write this victim page back to disk and change the page table and page frame table
  • Restart the interrupted instruction
• If there is no free page frame, two page transfers (i.e., page-in and page-out) are required.
• A modify bit (or dirty bit) may be added to a page table entry. The modify bit is set if that page has been modified (i.e., storing info into it). It is initialized to 0 when a page is brought into memory.
• Thus, if a page is not modified (i.e., modify bit = 0), it does not have to be written back to disk.
• Some systems may also have a reference bit. When a page is referenced (i.e., reading or writing), its reference bit is set. It is initialized to 0 when a page is brought in.
• Both bits are set by hardware automatically.
• Frame-allocation algorithm: If we have multiple processes in memory, we must decide how many frames to allocate to each process.
• The fewer number of page faults an algorithm generates, the better the algorithm it is.
• Page replacement algorithms work on page numbers. A string of such page numbers is referred to as a page reference string.

10.4.2          FIFO Page Replacement

• The FIFO algorithm always selects the “oldest” page to be the victim.

• Belady Anomaly
  • Intuitively, increasing the number of page frames should reduce page faults.
  • However, some page replacement algorithms do not satisfy this “intuition”. The FIFO algorithm is an example.
  • Belady Anomaly: Page faults increase as the number of page frames increases.
  • FIFO was used in DEC VAX-78xx series because it is easy to implement: append the new page to the tail and select the head to be victim!

10.4.3          Optimal Page Replacement

• The optimal algorithm always selects the page that will not be used for the longest period of time.

• The optimal algorithm always delivers the fewest page faults, if it can be implemented. It also satisfies the inclusion property (i.e., no Belady anomaly).

10.4.4          LRU Page Replacement

• The LRU algorithm always selects the page that has not been used for the longest period of time.

• The memory content of 3-frames is a subset of the memory content of 4-frames. This is the inclusion property. With this property, Belady anomaly never occurs.

10.4.5          LRU Approximation Page Replacement

• FIFO has Belady anomaly, the optimal algorithm requires the knowledge in the future, and the LRU algorithm requires accurate info of the past.
• The optimal and LRU algorithms are difficult to implement, especially the optimal algorithm. Thus, LRU approximation algorithms are needed.

10.4.5.1       Additional-Reference-Bits Algorithm

• The OS shifts the reference bit for each page into the high-order bit of its 8-bit byte, shifting the other bits right 1 bit, discarding the low-order bit.

10.4.5.2       Second-Chance Algorithm

• The second chance algorithm is basically a FIFO algorithm. It uses the reference bit of each page.
• When a page frame is needed, check the oldest one:
  • If its reference bit is 0, take this one
  • Otherwise, clear the reference bit, move it to the tail, and (perhaps) set the current time. This gives it a second chance.
• Repeat this procedure until a 0 reference bit page is found. Do page-out and page-in if necessary, and move it to the tail.
• Problem: Page frames are moved too frequently.

10.4.5.3       Enhanced Second-Chance Algorithm

• We have four page lists based on their reference-modify bits (r, c):
  • Q00 – pages were not referenced and not modified. The best candidates!
  • Q01 – pages were changed but not recently referenced. Need a page-out.
  • Q10 – pages were recently used but clean.
  • Q11 – pages were recently used and modified. Need a page-out.
• We still need a “next” pointer.
• When a page frame is needed:
  • Does the “next” frame have 00 combinations? If yes, victim is found. Otherwise, reset the reference bit and move this page to the corresponding list.
  • If Q00 becomes empty, check Q01. If there is a frame with 01 combination, it is the victim. Otherwise, reset the reference bit and move the frame to the corresponding list.
  • If Q01 becomes empty, move Q10 to Q00 and Q11 to Q01. Restart the scanning process.

• The major difference between this algorithm and the simpler clock algorithm is that here we give preference to those pages that have been modified to reduce the number of I/Os required.

10.4.5.4       Clock Algorithm

• If the second chance algorithm is implemented with a circular list, we have the clock algorithm.
• We need a “next” pointer.
• When a page frame is needed, we examine the page under the “next” pointer:
  • If its reference bit is 0, take it
  • Otherwise, clear the reference bit and advance the “next” pointer.
• Repeat this until a 0 reference bit frame is found.
• Do page-in and page-out, if necessary.

10.4.6          Counting-Based Page Replacement
10.4.7          Page-Buffering Algorithm

10.5.1          Minimum Number of Frames

• The minimum number of frames per process is defined by the instruction-set architecture, whereas the maximum number is defined by the amount of available physical memory.
• When a page fault occurs before an executing instruction is complete, the instruction must be restarted.
• We must place a limit on the levels of indirection.

10.5.2          Allocation Algorithms

• Equal allocation, proportional allocation (proportion to program size, priority…).

10.5.3          Global Versus Local Allocation

• Global replacement allows a process to select a victim from the set of all page frames, even if the page frame is currently allocated to another process.
• Local replacement requires that each process selects a victim from its own set of allocated frames.
• With a global replacement, the number of frames allocated to a process may change over time. With a local replacement algorithm, it is likely a constant.
• With a global replacement algorithm, a process cannot control its own page fault rate, because the behavior of a process depends on the behavior of other processes. The same process running on a different system may have a totally different behavior.
• With a local replacement algorithm, the set of pages of a process in memory is affected by the paging behavior of that process only. A process does not have the opportunity of using other less used frames. Performance may be lower.
• With a global strategy, throughput is usually higher, and is commonly used.

• A high paging activity is called thrashing. This means a process is spending more time paging than executing (i.e., low CPU utilization).
• If the number of frames allocated to a low-priority process falls below the minimum number required by the computer architecture, we must suspend that process’ execution.
• If CPU utilization is too low, the medium-term scheduler is invoked to swap in one or more swapped-out processes or bring in one or more new jobs. The number of processes in memory if referred to as the degree of multiprogramming.

10.6.1          Cause of Thrashing

• We cannot increase the degree of multiprogramming arbitrarily as throughput will drop at certain point and thrashing occurs.
• Therefore, the medium-term scheduler must maintain the optimal degree of multiprogramming.

• Suppose we use a global strategy and the CPU utilization is low. The medium-term scheduler will add a new process.
• Suppose this new process requires more pages. It starts to have more page faults and page frames of other will be taken by this process.
• Other processes also need these page frames. Thus, they start to have more page faults.
• Because pages must be paged-in and out, these processes must wait, and number of processes in the ready queue drops. CPU utilization is lower.
• Consequently, the medium-term scheduler brings in more processes into memory. These new processes also need page frames to run, causing more page faults.
• Thus, CPU utilization drops further, causing the medium-term scheduler to bring in even more processes.
• If this cycle continues, the page fault rate increases dramatically, and the effective memory access time increases. Eventually, the system is paralyzed because the processes are spending almost all time to do paging!
• Locality of Reference, locality model: looking at how many frames a process is actually using. As a process executes, it moves locality to locality. During any phrase of execution, the process references only a relatively small fraction of pages. Programs tend to have locality of reference.
• Temporal, spatial locality.
• A locality is a set of pages that are actively used together.

10.6.2          Working-Set Model

• The working set of a process at virtual time t, written as W (t, θ), is the set of pages that were referenced in the interval [t-θ, t], where θ is the window size.
• Θ = 3. The result is identical to that of LRU:

• However, the result of θ = 4 is different from that of LRU.

• The Working Set Policy: Find a good θ, and keep W (t, θ) in memory for every t (Find suitable frame numbers).
• What is the best value of θ? This is a system tuning issue. This value can change as needed from time to time.

• Unfortunately, like LRU, the working set policy cannot be implemented directly, and an approximation is necessary.
• A commonly used algorithm is the Working Set Clock algorithm, WSClock. This is a good and efficient approximation.

10.6.3          Page-Fault Frequency

• Since thrashing is due to high page-fault rate, we can control thrashing by controlling page-fault rate (page-fault frequency, PFF).
• If the page-fault rate of a process is too high, this process needs more page frames. On the other hand, if the page-fault rate is too low, this process may have too many page frames.
• Therefore, if we can always maintain the page-fault rate of a process to certain level, we control the number of page frames that process can have.
• We establish an upper bound and a lower bound, and monitor the page-fault rate periodically.
• If the rate is higher (resp., lower) than the upper (resp., lower) bound, a new (resp., existing) page is allocated to (resp., removed from) this process.

10.7.1          Window NT
10.7.2          Solaris 2

• Pages belonging to libraries that are being shared by several processes.

10.8.1          Prepaging

• An obvious property of a pure demand-paging system is the large number of page faults that occur when a process is started.
• Prepaging is an attempt to prevent this high level of initial paging. The strategy is to bring into memory at one time all the pages that will be needed.

10.8.2          Page Size

• Page sizes are invariably powers of 2, generally raging from 4096 (2¹²) to 4194304 (2²²) bytes.
• Transfer time is proportional to the amount transferred (that is, the page size), but the latency and seek time normally dwarf transfer time, thus, a desire to minimize I/O time argues for a larger page size.
• With a smaller page size, however, total I/O should be reduced, since locality will be improved.

10.8.3          TLB Reach

• The TLB reach refers to the amount of memory accessible from the TLB and is simply the number of entries multiplied by the page size.

10.8.4          Inverted Page Table
10.8.5          Program Structure

• Careful selection of data structures and programming structures can increase locality and hence lower the page-fault rate and the number of pages in the working set.
• Routines that call each other many times can be packed into the same page. This packaging is a variant of the bin-packing problem of operations research: Try to pack the variable-sized load segments into the fixed-sized pages so that interpage reference is minimized.

10.8.6          I/O Interlock
10.8.7          Real-Time Processing