Operating Systems
Lecture 8 Virtual Memory
Virtual memory
Copyright By PowCoder代写 加微信 powcoder
Demand paging and page faults Page replacement mechanism
Page replacement algorithms
Other issues
COMP 2432 2021/2022
Memory Management
A program should be in main memory to be executed.
Loaded into memory in contiguous storage.
Brokendownintopiecesandstoredinnon-contiguousmemory.
Memory management unit (MMU) translates the logical address into physical address.
OS often implements paging and segmentation algorithms for non-contiguous memory allocation.
Do we really need the whole program in memory in order to execute it?
Could we execute a program of size 100K on a 64K Apple II computer?
Solution:
COMP 2432 2021/2022
Overlay: break a program into stages and load the next stage when the current stage finishes (e.g. divide into readGrade, adjustGrade and computeGPA).
Virtual memory: store the process on disk in a way similar to memory and load the needed part only when that part is executed.
When there are too many processes in memory, everybody will not have sufficient memory to run. So some of them should be moved out of the memory to free up the space for others.
overlay and virtual memory management.
COMP 2432 2021/2022
This is called swapping.
A process can be swapped out of memory to backing store,
and then brought back into memory for continued execution.
Backing store is normally a fast disk large enough to hold copies of memory images for users and provide direct access to these memory images.
Processes can be swapped out in full (whole process) or in part (segment or page).
Since I/O is relatively slow, it will take quite some time to swap a full process out and then swap it in later.
Ability to swap part of a process forms the basis for
COMP 2432 2021/2022
Swapping is done to different phases of program execution.
User program with storage requirement larger than available portion of main storage
Operating system
Portion of user code and data that must
remain in main storage b during the execution
initialization
processing
Overlay area
COMP 2432 2021/2022
1. Load initialization code at b and run
2. Then load processing code at b and run 3. Finally load output code at b and run
Virtual Memory
Virtual memory separates user logical memory (not just logical address) from physical main memory.
Only the currently executing part of the process needs to be in memory for execution.
Possible implementations:
Paging: break into pages.
Segmentation: break into segments. COMP 2432 2021/2022
View the disk to be extension of physical memory (RAM).
Logical address space can therefore be much larger than
physical address space.
Consider the logical address space to be stored on the disk,
as an extension of the real physical memory.
This technique is called Virtual Address eXtension and this is
the name of a very famous computer in 80’s: VAX.
Allow address space to be shared by several processes.
Less I/O since unused part of process/data is never loaded.
Virtual Memory
Virtual memory is mapped to physical memory.
Some parts are stored in real memory.
Some parts are stored on disk only.
Move in needed part to memory (swap in) and move out unneeded part from memory (swap out).
Memory map in virtual memory means the page table in paging.
COMP 2432 2021/2022
Virtual Memory
Keeping only one copy of shared library.
COMP 2432 2021/20
Lecture822
Virtual Memory
Physical memory is smaller than virtual memory.
We could not store all needed pages in memory.
A page should be in memory when its contents are needed (containing the current instruction or data to be accessed).
Anticipatory paging: predict what pages a process would need in near future and to bring them in before hand.
No need to wait for a page to be loaded, faster response time. Prediction of future could be wrong and I/O would be wasted.
Most systems implement demand paging, since it is simple and effective. COMP 2432 2021/2022
When to bring a page from disk into memory?
Demand paging: bring a page into memory only when it is
Avoid loading pages that are not used (effective use of I/O
resource).
To load a needed page, process must wait for I/O to complete. You might only do homework when the deadline is closing in.
Demand Paging
A page is needed when there is a reference to it.
A reference is a need indicated by PC or MAR.
If the reference is invalid, process is accessing outside its space, then generate a trap.
If the page is not in physical memory, load it from disk into memory.
Demand paging is implemented by a lazy process swapper .
It never swaps a part of a process into memory unless the part is needed.
A swapper that swaps pages is called a pager.
Advantages of demand paging. Less I/O needed.
Less physical memory needed.
Relatively good response.
Can support more users. COMP 2432 2021/2022
page number
page offset
Demand Paging
In paging, a virtual or logical address is divided into page number and page offset.
Page number is used as an index into the page table. A frame number is found.
For virtual memory, not all pages need to be stored in memory.
A valid-invalid bit is used to indicate whether a page is in memory.
A valid entry means that the page is in memory and the frame number could be used.
Initially, valid-invalid bit is set to invalid for all entries.
COMP 2432 2021/2022
An invalid entry means that the page is not in memory.
Hardware will detect the invalid bit and triggers a trap, called
the page fault.
The page fault handler (a kind of interrupt handler) will ask the
pager to help swapping the page into memory.
Demand Paging
A process is divided
All 8 pages can be found on disk.
Only 3 pages (A,C,F) are currently in main memory.
Valid-invalid bits indicate which are in memory.
Only pages that are in memory could be accessed by the CPU.
Memory pages are called frames.
page number
frame number
page offset
into 8 pages.
COMP 2432 2021/2022
Page Fault
If there is an access to the address within a page, this is called a reference to the page.
If the reference is to an invalid page, it will generate a trap to OS. This trap is similar to an access beyond segment limit of a process.
Get an empty frame from the free frame list.
Schedule I/O to load the page on disk into the free frame.
Update the page table to point to the loaded frame.
Set the valid-invalid bit to be valid.
Restart the instruction that caused the page fault. COMP 2432 2021/2022
This is the page fault (a fault or an error on a page access). The page fault handler in OS checks with the address limit
stored in PCB of the process for the nature of the trap.
If the reference is beyond the process logical address, print out
segmentation fault error and terminate the program.
If the page is just not in memory, continue with page fault
handling to bring it into the memory. Servicingapagefault:
Page Fault
2 2021/2022
Demand Paging Performance
Let the page fault rate be f.
If f = 0, there is no page fault.
If f = 1, every reference generates a page fault.
Notethat0f1.
Effective Access Time (EAT) is the expected time to access to memory, in the presence of virtual memory.
COMP 2432 2021/2022
EAT = (1 – f) x memory access time + f x page fault service time.
Page fault service time = page fault overhead + time to swap the page in + restart overhead.
Demand Paging Performance
Memory access time = 0.2 s.
Linux context switching time on 2GHz Xeon = 4 s.
Average disk access time = 8 ms (5 seek+3 rotation).
Average page fault service time ~ 8000 s.
EAT = (1 – f) x 0.2 + f x 8000 = 0.2 + 7999.8f
If there are 0.1% of page faults (f = 0.001), EAT = 8.2 s.
Compared with the normal memory access time of 0.2 s (200 ns), there is a factor of 40 times slowing down!
Question
Is 0.1% page fault rate reasonable?
Does it matter with a slow down of 40 times?
COMP 2432 2021/2022
Page Replacement
Recall that to handle a page fault, a free frame is needed to hold the page to be swapped from disk into memory.
Sooner or later, the system runs out of free frames. Unused frame in memory should be freed.
If all frames are still in use, try to find some frame that is probably not used and remove it.
This action of finding a frame in memory to be removed to free up the space in order to admit a newly needed page is called page replacement.
Which page is unlikely to be used and can be thrown away?
Could a process throw away pages of another process?
Should the removed page be saved back to the disk (some data have been modified)? COMP 2432 2021/2022
Page Replacement
Example: executing
All6pages,3 for each user, are used up already.
Weneedto remove a page to free a frame to hold page M.
COMP 2432 2021/2022
instruction in page 1 (i.e. K) of user 1.
Instruction needs to access page 3 (i.e. M), which is not in memory.
Page Replacement
Modify page fault handler to include page replacement mechanism.
It is more effective to remove a page that has not been changed or modified, since that page does not need to be written back on the disk.
Program text represents read-only pages that require no saving.
Sometimes some data pages may not be modified at the moment of page replacement.
Use a modify or dirty bit to indicate whether a page has been modified.
Use of page replacement mechanism completes the puzzle that allows for separation between logical memory and physical memory.
physical memory. COMP 2432 2021/2022
Now, there can be a very large virtual memory for a program, but that can be supported upon a much smaller
Page Replacement
Steps in page fault handling with page replacement.
Find the location of the desired page on disk.
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.
Write victim frame to disk if modified.
Bring the desired page into the (new) free frame.
Update the page table and frame information for both the victim and the new page.
Return from page fault handler and resume the
user process generating the page fault.
COMP 2432 2021/2022
Page Replacement
was valid was invalid
Lecture 8 COMP 2432 2021/2022
Page Replacement
Replacing a page is an expensive I/O operation.
Our example of 0.1% page fault causes 40 times slow down.
Goal is to generate smallest number of page-faults.
If we know the future perfectly, we can determine the best page to be replaced for each page fault. This is called the optimal replacement algorithm.
There are a number of common page replacement algorithms.
Look into the past, and replace the page that has not been
used for the longest time. COMP 2432 2021/2022
First In First Out (FIFO)
If a page comes in earlier than another page, the earlier page
will be replaced before the later page.
Look into the future, and replace the page that will not be
needed in the furthest future. Do you have the oracle? Least Recently Used (LRU)
Page Replacement
The performance of a page replacement algorithm is often evaluated by running it on a list of memory references and computing the number of page faults.
This list of memory references is abstracted into a reference string, showing only the page number.
If we trace a process in execution, we might see a sequence of addresses generated:
0100, 0432, 0102, 0612, 0104, 0106, 0102, 0611, 0104, 0106, 0108, 0102, 0610, 0104, 0106, 0108, 0102, 0609, 0104, 0110.
It looks like a loop referencing some data.
Assuming that a page contains 100 bytes for simplicity, the reference string of page numbers generated is 1,4,1,6,1,1,1,6,1,1,1,1,6,1,1,1,1,6,1,1.
This is equivalent to 1,4,1,6,1,6,1,6,1,6,1, since consecutive accesses to the same page will not cause further page fault.
COMP 2432 2021/2022
Page Replacement
It is quite intuitive that if we have more free frames, then the number of page faults will be smaller.
COMP 2432 20
Lecture821/2022
Page Replacement
If we have more free frames, then the number of page faults will be smaller – not necessarily true!
Belady’s anomaly
Lecture 8 COMP 2432 2021/2022
FIFO Page Replacement
When there is no free frame, the page that has resided in the memory for the longest (the earliest page admitted) will be replaced.
There is a simple implementation using a circular queue with a pointer pointing to the oldest page.
In this example, there are 15 page faults.
COMP 2432 2021/2022
Optimal Page Replacement
Replace the page that will not be used for the longest period of time in future.
It is clear that this will generate the smallest number of page faults. But how could you know the future?
Used as a benchmark to evaluate other algorithms. In this example, there are only 9 page faults.
COMP 2432 2021/2022
LRU Page Replacement
Replace the page that has not been used for the longest period of time.
LRU is very similar to using a mirror to look into the past to reflect what the future would look like. The behavior at time now+t can be reflected as now-t.
In this example, there are 12 page faults.
COMP 2432 2021/2022
LRU Page Replacement
LRU is performing well in practical cases.
Experience shows that the trick of using the past for the
future turns out to be good.
Motto: learn from the history.
LRU is the most popular algorithm used in real systems.
How could we implement LRU? Counter implementation
Stack implementation
Approximation implementations Reference bit algorithm
Additional reference bit algorithm Second chance (clock) algorithm
COMP 2432 2021/2022
1 1 1 4 4 4 4 8 8 8 11 11 11 14 14 14 17 17 17 2 2 2 5 5 7 7 7 10 10 12 12 12 12 16 16 16 19 3 3 3 6 6 6 9 9 9 9 13 13 15 15 15 18 18
LRU Page Replacement
Counter implementation
Every page entry has a counter.
Whenever a page is referenced through this entry, copy the clock value into the counter.
When a page needs to be replaced, look at the counters to determine the page with the smallest value to be replaced.
Example: red page would be replaced.
COMP 2432 2021/2022
LRU Page Replacement
Stack implementation
Use stack of pages in double linked list with head/tail pointers.
When a page is referenced, move it to the top of stack.
When you have a pile of books, the top one will be the most
recently used and the bottom one will be least recently used. Replace the page at the bottom of the stack.
Example: replace red page at bottom.
70120304230321201701 7012030423032120170 Lecture 8 7 0 1 2 2 3 0 4 2 2 0 3 3 CO1MP 22432 2021/210227
LRU Page Replacement
Counter implementation has a storage overhead of a clock value with each page entry.
Clock value would increase in size.
A search is needed to find the entry with the smallest clock
Stack implementation needs up to 6 updates to the pointers to move a stack entry to the top on each reference.
Cost of pointers to double linked list could be expensive.
Approximation algorithms
Use hardware to help to make page selection faster.
Each page is associated with a reference bit, initially zero.
When a page is referenced, the reference bit is set to one by hardware.
Basic algorithm: replace a page with a reference bit value of
zero. COMP 2432 2021/2022
value to replace.
pages) if there are several pages with the same smallest value.
LRU Page Replacement
Keep several bits or a byte with each page, initially 0.
Additional reference bit algorithm
At regular time interval, e.g. 100 ms, shift the reference bit
into the high order bit position of the few bits or the byte.
Now, these bits or the byte will contain an approximate time for the use of the page entry.
If a page is never referenced in the past 8 periods, it has a value of 0.
A page that is used once in each period has a value of 255 (11111111).
A page used in only past 4 periods (11110000) will have a value larger than a page used in only the last fifth to eighth periods (00001111).
A page with smallest value is probably the least recently used.
Replace a page with the smallest value.
Use FIFO or random algorithm to replace a page (or all those
COMP 2432 2021/2022
LRU Page Replacement
Make use of the hardware reference bit.
If a page is to be replaced, look at the entry at the current pointer of the queue.
If its reference bit is zero, replace the page and advance the queue pointer.
If the reference bit is one, then reset the reference bit to zero and advance the queue pointer to next entry, until a page with a reference bit of zero is found for replacement.
Pages are replaced according to the circular queue order and the advancement of the queue pointer looks like the hand of a clock (thus called the clock algorithm).
A selected victim page with reference bit of one will be given a second chance.
Both Unix and Linux use a variant of clock algorithm, but a few pages will be paged out together. COMP 2432 2021/2022
Second chance algorithm
Consider the list of pages like a simple circular queue
(instead of a double linked stack).
LRU Page Replacement
2 Reset to 0
4 Reset to 0
To be replaced
COMP 2432 2021/2022
Allocation of Frames
In page replacement algorithms, we would assume that we know the number of frames for each process and look for a page to be replaced.
If a system has F free frames, how are they allocated to a set of n processes?
Fixed allocation
Equal allocation: each process gets an equal number of
frames F/n.
Proportional allocation: each process gets a number of frames in proportion to its size, more frames for larger processes.
Variable allocation
Allow the number of frames allocated to each process to
Processes that suffer from too many page faults should have more frames and vice versa. COMP 2432 2021/2022
vary over time.
Allocation of Frames
Page replacement is also related to frame allocation. Local page replacement
A process will only seek for page replacement within its own set of frames.
COMP 2432 2021/2022
Global page replacement
A process will seek for page replacement within all frames of all
processes.
A process may take away a frame from another process.
Only local page replacement can be used for fixed frame allocation.
Both global and local page replacement can be used for variable frame allocation.
How should OS respond if there is a change in process memory need?
COMP 2432 2021/2022
If a process does not have enough frames allocated for it, it will generate many page faults.
The process spends a lot of time waiting for page I/O.
CPU utilization will be low.
OS thinks that it needs to increase degree of multiprogramming so as to increase CPU utilization and admits another process.
Competition for frames will become more serious with more processes, especially if global page replacement is employed.
Processes are waiting for I/O further, with even lower CPU utilization, and OS brings in yet more processes.
This is called thrashing.
Processesarebusy.
But they are just b
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com