CS代考 COMP 2432 2021/2022 – cscodehelp代写

Operating Systems
Lecture 8 Virtual Memory

 Virtual memory

Copyright By cscodehelp代写 加微信 cscodehelp

 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.
 Notethat0f1.
 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代考 加微信: cscodehelp QQ: 2235208643 Email: kyit630461@163.com