Virtual Memory Concepts

• Chapter 10 discusses virtual memory concepts
• Virtual memory separates user logical memory from physical memory allowing programs to be partially loaded into memory

Virtual Memory Benefits

• Enables execution of programs not entirely in memory
• Allows logical address space to exceed physical address space
• Facilitates address space sharing among processes
• Supports more efficient process creation and enables concurrent execution of programs
• Reduces I/O for process loading/swapping

Virtual Address Space

• Represents the logical view of how a process is stored in memory, typically starting at address 0
• Physical memory is organized into page frames
• MMU maps logical to physical addresses
• Implemented via demand paging or demand segmentation

Demand Paging

• Pages are brought into memory only when referenced
• Reduces I/O and memory needs
• Allows faster response
• Supports more users
• A "lazy swapper" (pager) only swaps pages when needed
• "Not-in-memory" pages trigger fetching/load into memory

Basic Concepts of Demand Paging

• Pager brings in specific pages, not guessed pages like in swapping
• New MMU functionality required for demand paging
• Memory-resident pages involve no difference from non-demand paging
• Non-memory-resident pages must be detected and loaded without altering program behavior or requiring programmer changes

Valid-Invalid Bit

• Each page table entry has a valid-invalid bit to indicate if a page is in memory (v) or not (i)
• Initially, set to i on all entries
• MMU checks this bit during address translation, triggering a page fault if it is i

Handling a Page Fault

• Reference to a page results in a trap to the OS as “Page fault”
• OS checks another table; if invalids abort, if valid but not in memory go to next state
• Find a free frame
• Swap the page into frame via scheduled disk operation
• Reset tables to indicate page is now in memory, and set validation bit to v
• Restart instruction that caused the page fault

Aspects of Demand Paging

• Extreme case is "pure demand paging," which starts processes with no pages in memory
• Locality of reference decreases access pain
• Hardware is needed, such as page table with valid/invalid bit, swap space, and instruction restart
• The Operating system sets the instruction pointer to the first instruction of process, resulting in a non-memory-resident leading to page fault

Free-Frame List

• OS brings desired pages into main memory from secondary storage when a page fault occurs
• Most OS maintain a "free-frame list," that is a pool of free frames, when such requests occur
• System typically allocates free frames to a technique known as a zero-fill-on-demand
• When a system starts up, all available memory is placed on the free-frame list

Demand Paging Stages

• Trapping to the OS
• Saving the user register and process state
• Determining that the interrupt was a page fault
• Checking the page reference legality and location of the page on the disk
• Issue a read from the disk to a free frame
• Wait in queue to device
• Wait for device seek and/or latency time
• Transfer page to a free frame
• Allocate the CPU to another user while waiting
• Recieve an interrupt from the I/O subsystem
• Save the registers and process state for the user
• Determine the interrupt came from the Disk
• Correct page and other tables to show the page is in memory
• Wait for the CPU to allocate to this process again
• Restore user registers, process state and new page table
• Resume interrupted instruction

Performance of Demand Paging

• Consists of servicing the interrupt, reading the page and restarting the process
• Page Fault Rate (p) has a range from 0 (no faults) to 1 (every reference is a fault)
• Effective Access Time (EAT) = (1 – p) x memory access + p (page fault overhead + swap page out + swap page in)

Instruction Restart

• Involves an instruction that could access several locations
• Auto-increment/decrement location
• Requires restart of the whole operation
• Handles overlapping source and destination

Demand Paging Optimizations

• Swap space I/O is faster than file system I/O
• Copy entire process image to swap space at process load time
• Demand page from program binary on disk and discard when freeing frame
• Still need to write to swap space such as pages that are non-file associated (anonymous memory) and pages modified but not yet written back
• Mobile systems
• Typically don't support swapping
• Demand page from the file system such as code and reclaim read-only pages

Copy-on-Write (COW)

• Allows parent and child processes to share pages initially in memory
• If either process modifies a page, only then is the page copied
• Pool needs free frames for demand page execution
• Variation call vfork()has the parent suspend and child using the copy-on-write for address space

Page Replacement

• Used to reduce memory allocation
• A modify (dirty) bit is used to reduce page transfer overhead
• Completes the logical memory and physical memory by providing large virtual memory over smaller physical memory

Basic Page Replacement

• Find the location of the desired page on disk
• Find a free frame
• If free use it
• if not select a victim frame using a page replacement algorithm
• Write victim frame to the disk if dirty
• Bring the desired page into the freed up page and update tables
• Restart instruction that caused the trap
• Note this potentially increases EAT due to page transfer for page fault

Frame-Allocation and Page Replacement Algorithms

• Frame-allocation algorithm determines how many frames given to each process and which frames can be replaced
• Page-replacement algorithm, want to minimize page-fault with lowest rate on both first access and re-access
• Evaluate algorithm by running it on memory references (reference string)

FIFO (First-In-First-Out) Algorithm

• Replace pages using a FIFO queue data structure
• Can be varying by reference string
• Causes Belady's Anomaly can cause more faults; a condition where adding more frames can cause more faults!

Optimal Algorithm

• Replace pages that will not be used for longest period of time
• Cannot be read due the inability to read the future
• Used for measuring the algorithms performance

LRU (Least Recently Used) Algorithm

• Replace page that needs the most of time
• Associates time of last use with each page
• Better than FIFO, but worse than OPT
• Generally used due the good algorithm

LRU (Least Recently Used) Algorithm Implementation

• Every entry has a counter, that copies the clock into each page the is referenced through copy each page
• Stack Implementation keeps stack of page #s in double linked list, allows each top to be moved
• But needs more pointers and is each update is more expensive with less searching

LRU and OPT

• Are cases of the stack algorithm that doesn't have Belady's Anomaly
• Stack records the most recent page references

LRU Approximation Algorithms

• LRU is expensive with its hardware
• Each page associates a bit by a = 0 initially
• Page switches, then switches = 1
• Reference will then equal 0

Second-Chance Algorithms

• Provides FIFO, with a hardware reference bit through clock replacement
• If a page has to be replaced
• Reference bit = 0 > replacement
• Reference bit = 1, then the statement will leave page in memory and replace it

Enhanced Second Chance Algorithms

• Algorithm improves by using its reference bit and modifying it in available concert
• Take reference, modify and the relationship
• Replace page in the lowest non-empty class, need to circular queue several times

Counting Algorithms

• Keeps the counter of each number of references made to a page
• This is not common
• Replaces the page with the smallest count
• The most frequent argument that the with the smallest count has just been brought in

Page-Buffering Algorithms

• Keep a of free frames, available when needed, evicting to the victim from the pool
• Possibly keep the list od modified pages
• When backing store, write pages and set non-dirty

Applications and Page Replacement

• Different all the OS algorithms are guess about the OS access each OS guesses
• Some apps have better knowledge, especially on the database
• Memory-intensive has double buffering
• System gives direct the disk from apps and will by-pass buffering

Allocation of Frames to processes

• Each process has to meet a standard number of frames
• Allocate frames to each process (fixed allocation)
• Allocate based on the size of process (proportional allocation)
• Dynamic has to deal with multiprogramming

Global vs Local Allocation

• Global allows the ability to another the process or set of allocation
• Local each process selects it with allocates and utilized memory

Reclaiming Pages

• Is policy of for the global pace
• Memory satisfied from free-frame list, before the is begin to select
• A strategy made to trigger when list drops, making there is always free space

Nun-Uniform Memory Access

• Assumed all access memory is equal
• Varying speeds of accessed memory
• Boards containing CPUs memory, connected through system bus

NUCA cont.

• Optimize with memory located "close to" threads
• And modifying, will make threads to connect with low-latency groups
• Allocates all the process thread and all the memory inside of the Igroup

Thrashing

• Low CPU is cause, and makes system think degree needs multiprogramming
• Other processes have to be in system
• If process doesn't have "enough" high and rate is very high
• Replace its frame back
• It to page will and the existing frame

Demand Paging and Thrashing

• Why work, process from One with either crossing
• Process, and if smaller than program means will thrashing

Working Set

• Working rate, fixes and example instructions Working sets change over time Peaks and valleys over time.
• Working list, helps suspend with a list of process

Keeping Track of Working Set

• Accurate with timer + is timer goes on for page
• While has 2 bits for page, copy and set from 1
• Why not completely accurate?
• If can't use timer, bits and increase timer

Page-Fault Frequency

• With direct approach through local process
• It page loses, is low and gains if high

Allocating Kernel Memory

• Treated well is to use a free memory
• Needs of memory are contagious and a certain size
• Through I/O devices

Other considerations-Prepaging

• Reduce the amount of of large pages that happen when the process starts
• All processes go through some needs before reference
• Assume some of the pages have wasted resources
• Is the code to save correct and the amount of wrong processes?
• Near 0, processes will lose

Page size

• OS have for built systems
• must have
  • The correct table size
  • TLB size for affectively
  • I/O for overhead
• Number of pages to show
• 2 numbers from -to
• On, avg growing over time

TLB Reach

• From amount to the TLB with both sizing
• Set a work table for both process the TLB
• Will degree to add to faults
• Page sizes may, increase and require large increases
• Multiple to use page sides for an advantage with less fragmentation

Program Structure

• Structure data, through out Each section store on page
• Program 1 needs 128 data page
• Program 2 runs all the needed programs

//O Interlock

• Pages must be locked into the memory space from to time
• device must be locked from being selected by a
• page replacement algorithm
• Pinning of pages to locked into the memory

Priority Allocation

• Assign to numbers in and a size
• Assigns to the generate and the processes
• assign with lower programs
• assign with lower names