Operating System Design - Virtual Memory

Background of Virtual Memory

 

Code needs to be in memory to execute, but entire program rarely used

Entire program code not needed at same time

Each program takes less memory while running => more programs run at the same time

Increased CPU utilization and throughput with no increase in response time or turnaround time

Less I/O needed to load or swap programs into memory => program runs faster

 

Virtual Memory

 

Virtual memory : separation of user logical memory from physical memory

Logical address space can be much larger than physical address space

Allow address space to be shared by several processes

Allow for more efficient process creation

More program running concurrently

Less I/O needed to load or swap processes

 

Virtual address space : logical view of how process is stored in memory

System libraries shared via mapping into virtual address space

Shared memory by mapping pages read-write into virtual address space

 

 

Demand Paging

 

With swapping, pager guesses which pages will be used before swapping out again

Pager brings in only necessary pages into memory

 

Pages needed are already memory resident (valid-invalid bit : v) => Non demand-paging

Page needed are not memory resident (valid-invalid bit : i (page fault)) => Detect and load the page into memory from storage

 

Page Fault Handling

 

1. If there is a reference to a page, first reference to that page will trap to Operating System (Page fault)

2. OS looks at another table to decide

Invalid reference => abort(program stop)

Just not in memory => next

3. Find free frame

4. Swap page into frame via scheduled disk operation

5. Reset tables to indicate page now in memory, set validation bit = v

6. Restart the instruction that caused the page fault

 

Dmand paging in Worse case

 

1. Trap to the Operating System

2. Save the user register and process state

3. Determine that the interrupt was a page fault

4. Check that the page reference was legal and determine the location of the pae on the disk

5. Issue a read from the disk to a free frame :

   1. Wait in a queue for this device until the read request is serviced

   2. Wait for the device seek and/or latency time

   3. Begin the transfer of the page to a free frame

6. While waitingm allocate the CPU to some other user

7. Receive an interrupt from the disk I/O subsystem (I/O completed)

8. Save the register and process state for the othor user

9. Determine that the interrupt was from the disk

10. Correct the page table and other tables to show page is now in memory

11. Wait for the CPU to be allocated to this process again

12. Restore the user register, process state, and new page table, and then resume the interrupted instruction

 

Performance of demand paging

1. Service the interrupt 

2. Read the page : lost of time

3. Restart the process : again just a small amount of time

 

Copy-on-Write

 

Allows both parent and child processes to initially share the same pages in memory

More efficient process creation as only modified pages are copied

 

Page Replacement

 

Prevent over-allocation of memory by modifying page-fault service routine to include page replacement

Use modify(dirty) bit to reduce overhead of page transfers (only modified pages are written to disk)

 

1. Find the location of the desired page on disk

2. Find a free frame : 

If there is a free frame, use it

If there is no free frame, use a page replacement algorithm to select a victim frame

Swap out victim page => Change valid-invalid bit of unused page to invalid => Swap desired page in => Reset page table for new page (change valid-invalid bit of newly swaped page to valid)

3. Bring the desired page into the (newly) free frame, update the page and frame tables

4. Continue the process by restarting the instruction that caused the trap

 

Repalcement Algorithms

 

First-in-First-out(FIFO) Algorithm : 

Select the frame which is entered into memory at first among the existing frames as a victim frame

Adding more frames can caouse more page fault(Belady's Anomaly)

 

Optimal Algorithm : 

Replace page that will not be used for longest period of time

In reality, the future reference string is unknown so, this cannot be applied

No Belady's Anomaly

 

Least Recently Used Algorithm : 

Replace page that has not been used in the most amount of time

Better than FIFO but worse than OPT

No Belady's Anomaly

Counter implementation (Every page entry has a counter. everyt time page is referenced through this entry, copy the clock into the counter. When a page needs to be changed, look at the counters to find smallest value

Stack implementation (When the page is referenced, remove it from the stack and place it on top)

 

LRU Approximation Algorithm : 

 

Use reference bit (With each page associated a bit, initially = 0. When page is referenced, bit set to 1. Replace any with reference bit = 0)

 

Second-chance algorithm :

 

Generally FIFO, plus hardware provided reference bit (reference bit 0 => replace it, reference bit 1 => set reference bit, leave page in memory, replace next page)

 

Enhanced Second-chance algorithm : 

 

Take ordered pair (reference, modify)

 

Counting Algorithm

 

Keep a counter of the number of references

Least Frequently used(LFU) (smallest counter page replacement)

Most Frequently used(MFU)

 

Page-Buffering Algorithm

 

Keep a pool of free frames, always

When backing store otherwise idle, write pages there and set to non-dirty

 

Allocation of frames

 

Each process needs minimum number of frames

 

Fixed allocation : equal allocation, proportional allocation(allocate according to the size of process)

Priority allocation

 

Global replacement : process select a replacement frame from the set of all frames

Local replacement : each process selects from only its own set of allocated frames

 

Reclamining pages :

A strateegy to implement global page-replacement policy

All memory requests are satisfied from the free-frame list

Page replacement is triggered when the list falls below a certain threshold

 

Thrashing

 

If a process does not have enough pages, the page-fault rate is very high => low CPU utilization

A process is busy is busy swapping pages in and out

 

Thrashing occur when total sum of size of locality > total memory size

Handle thrashing problem => Working-set model, Page-fault frequency

 

Working-set model : 

 

Δ = working-set window = a fixed number of page references

WSSi (working set of Process Pi ) = total number of pages referenced in the most recent Δ (varies in time)

if Δ too small => will not encompass entire locality

if Δ too large => will encompass several localities

if Δ = ∞ => will encompass entire program

D = total sum of  WSSi = total demand frames

D > m => Thrashing

 

Page-fault frequency : 

 

The page fault rate must be maintained between the upper bound and the lower bound

 

Buddy System

 

Allocates memory from fixed-size segment consisting of physically-contiguous pages

Memory allocated using power-of-2 allocator

Advantage : quickly coalesce unused chunks into larger chunk

Disadvantage : fragmentation

 

Slab Allocator

 

Slab : one or more physiccally contiguous pages

Cache : consists of one or more slabs

Single cache for each unique kernel data structure

Each cache filled with objects (instantiation of the data structure)

If no empty slabs, enw slab allocated

Advantage : no fragmentation, fast memory request satisfaction