Untitled

• Chapter 9 is about Virtual Memory

Background

• Code must be in memory to run effectively but not all code is used
• Entire program code doesn't have to be in the system memory
• Programs are no longer limited by physical storage
• Programs use less memory while running, more programs can run at one time
• Throughput and CPU utilization is increased when running in real time
• Less I/O is needed, that helps user programs run faster
• Virtual memory is a user's logical memory split from physical memory
• Only part of the program needs to be in memory to run it.
• Logical address space can be bigger compared to physical address space
• Allows for more efficient processes creation
• More programs can run at once when implementing virtual memory
• Less I/O load or swap processes when implementing virtual memory
• Virtual memory uses two approaches: demand paging and demand segmentation.
• Demand segmentation will not be covered

Demand Paging, Overview

• Jobs run with less main memory in segmented memory allocation
• There is an almost infinite appearance of physical memory
• Increased overhead caused by tables and page interrupts
• High-speed direct access storage device is required

Benefits of Virtual Memory

• Bring a page into memory only when needed by a user
• Less I/O and memory is ideal for more users and faster response times

Lazy Swapper

• Never swaps a page into memory until the specific page will be used
• A swapper deals with pages

Basic Demand Paging

• Guess what pages will be used before being swapped out
• A pager can bring “guessed” pages into memory alone versus the whole process
• New Memory Management Unit functionality is needed to implement demand paging
• Needed is understanding that page is in memory and located on the disk
• The valid-invalid scheme is for valid protection (see next slide).
• Pages that are needed, and happen to be memory resident don't change from demand paging
• For pages that are needed, and are not memory resident need to find and load its storage
• Should perform processes without changing programmer code or behavior
• Page table entries use valid-invalid bits
• "v" means in-memory, while "i" means not-in-memory
• Valid-invalid bit is initialized to "i"

Invalid Pages

• Invalid pages are non-valid and are not in the logical address space
• Invalid pages that are valid are currently on disk

Page Faults

• A page fault occurs when a page is marked invalid
• A trap page fault occurs from the operating system
• When a page fault occurs, the operating system uses another table
• An invalid reference will abort in most cases
• If valid and not in memory, the system will find a free frame location
• Swap that page via disk operation and reset the table to show page location and validation
• Restart the instruction when swapping is complete

Handling a Page fault

• In the event there are no free frames, select a victim to replace

Page Replacement

• Page replacement occurs when there are no free frames available
• When there are no free frames, a page fault occurs, and action to implement replacement begins.
• Page replacement finds the proper page in memory, then puts it out
• Decision to clear a frame is dependent on the desired algorithm
• Key point is to minimize number of page faults
• Pages may be moved to memory numerous times

Basic Page Replacement

• Find the desired location of the page disk
• Find a free frame: utilize algorithm to replace if there aren't any
• If free, write a victim to disk if it's dirty and restart the process that caused the fault
• When a process asks for a page, page replacement occurs if a page fault occurs.
• A page fault exists if there are no free frames

Issues of Page Replacement

• Overhead problems occur if there are no free frames, resulting in 2 page transfers
• This doubles page-fault time & increases access time
• To resolve, use "modify" or "dirty" bits to lower transfers
• Only modded pages written back on the disk
• Page replacement separates the logical memory from the physical memory.
• Resulting in a large virtual memory on a smaller physical memory

Algorithms to use

• Frame allocation algorithms determine: frames per process, and which frames to replace
• Choose page-replace algorithms that give minimum page faults
• Page replacement algorithms are tested by memory references
• Algorithm testing can be completed by checking faults and string
• Strings are simply page numbers, not full addresses
• Repeated access to the same page does not cause a page fault
• Results heavily depend of provided frame amounts

Page String

• If CPU has the following addresses, and page size is 100 bytes, reference string will be
• Example - the addresses 0100, 0432, 0101, 0612 etc: the reference string will equal to 1, 4, 1, 6

FIFO, First-In-First-Out

• This involves removing in memory pages with longest time stamps
• The page is in memory for the longest period
• Best page to remove is one that is not in memory for long
• More memory does not equal better performance in FIFO
• Efficiency measures a ratio to the number of page interrupts to number of requests

OPT, Optimal Page Replacement (OPR)

• OPT replaces pages not accessed for a period of time in the future
• Only provides measurements of how well a algorithm performs when comparing
• It replaces the page that will not be used for the longest time
• One is not able to read the future

LRU, Least Recently Used

• LRU utilizes past info instead of future
• Replaces pages that have not been used for an extended passage of time
• Time stamp of last use is saved

LRU Implementation

• To get an order of frames for a time of last use
• You can use different methods to implement LRU algorithms
• Methods include a counter, in which page table entries have one
• The clock content is copied into the counter as reference
• Replacement occurs to smallest time value searches

LRU Stack

• Maintain a page number stack in a double link form
• (Header pointer & Tail pointer)
• Page is moved at the top and used as a reference
• Page found on top, is most recently used
• No search for replacement
• LRU uses special hardware and slow
• LRU and OPT are stack algorithms so they don't have Belady's anomaly

Summary

• Processes can execute with logical address space larger than actual physical address space
• Virtual memory runs very large processes, raises multiprogramming, and increases CPU
• Programs run when stored entirely in memory via virtual memory
• Job size is not restricted when using virtual memory
• Demand paging lowers the number of frames per process
• Total memory replacement is greater than physical then replace the pages from memory to make place.
• Page replacement algorithms are used for all of these actions
• FIFO is easy to program but can suffer from Belady's anomaly
• OPT needs future knowledge, which is impossible
• LRU, the Least Recently Used algorithm, best approximates the OPT, although difficult to implement