操作系统英文课件：ch3b Memory Management

1、1Memory ManagementChapter 3vFetch StrategiesvPage Replacement-Optimal -FIFO -LRU -NRU -Second-chancevDesign Issues for paging systemsvImplementation IssuesvSegmentationvSummary2Paging PoliciesvFetch Strategies When should a page be brought into primary (main) memory from secondary (disk) storage. vR

2、eplacement StrategiesWhich page now in primary storage is to be removed from primary storage when some other page or segment is to be brought in and there is not enough room. vClean StrategiesWhen a page in memory is brought out? 3Demand FetchingvAlgorithm Never bring a page into primary memory unti

3、l its needed. 1.Page fault occurs.2.Check if a valid virtual memory address. Kill job if not. 3.If valid reference, check if its cached in memory already (perhaps for some other process.) If so, skip to 7. 4.Find a free page frame. 5.Map address into disk block and fetch disk block into page frame.

4、Suspend user process. 6.When disk read finished, add vm mapping for page frame. 7.If necessary, restart process. 4Prepaging vAlgorithm bring a page into primary in advance.vWhen page-fault happens, the page needed and adjacent pages will be brought into memory.Advantage: improve the I/O efficiency w

5、hen fetch page.Disadvantage: based on prediction, if the fetched page is rare referenced, low efficiency. Used when loading page.5Page Replacement1.Find location of page on disk 2.Find a free page frame If free page frame use it Otherwise, select a page frame using the page replacement algorithm Wri

6、te the selected page to the disk if necessary and update any necessary tables 3.Read the requested page from the disk. 4.Restart the user process. 6Page Replacement StrategiesvThe Principle of Optimality Replace the page that will not be used again the farthest time in the future. vRandom page repla

7、cement Choose a page randomly vFIFO - First in First Out Replace the page that has been in primary memory the longest vNRU - Not Recently Used An approximation to LRU. vLRU - Least Recently Used Replace the page that has not been used for the longest time vNFU - Not Frequently Used Replace the page

8、that is used least often vWorking Set Keep in memory those pages that the process is actively using. 7Principal of Optimality vDescription: Assume that each page can be labeled with the number of instructions that will be executed before that page is first references, i.e., we would know the future

9、reference string for a program. Then the optimal page algorithm would choose the page with the highest label to be removed from the memory. vImpractical because it needs future referencesvIf future references are knownshould not use demand fetching should use pre paging to allow paging to be overlap

10、ped with computation. vThis algorithm provides a basis for comparison with other schemes.8FIFO Page Replacement AlgorithmvMaintain a linked list of all pages in order they came into memory with the oldest page at the front of the list.vPage at beginning of list replacedvAdvantage: easy to implementv

11、Disadvantagepage in memory the longest (perhaps often used) may be evicted9Optimal Example12 references, 7 faults10FIFO 12 references, 9 faults 11Paging Behavior with IncreasingNumber of Page Frames12Beladys anomalyvBelady discovered more page frames might not always have fewer page faults. This is

12、called Beladys anomaly. vA paging system can be characterized by three items:The reference string of the executing process.The page replacement algorithm.The number of page frames available in memory.13Beladys Anomaly (for FIFO)As the number of page frames increase, so does the fault rate. 12 refere

13、nces, 10 faults 14Second Chance Page Replacement AlgorithmvInspect R bit: if R = 0 evict the page if R = 1 set R = 0 and put page at end (back) of list. The page is treated like a newly loaded page.15Second Chance Page Replacement AlgorithmvOperation of a second chancea)Pages sorted in FIFO orderb)P

14、age list if fault occurs at time 20, A has R bit set(numbers above pages are loading times)16The Clock Page Replacement AlgorithmvClock Replacement Algorithm: a different implementation of second chance17State of buffer just prior to a page replacement012345678n.Page 9use = 1Page 19use = 1Page 1use

15、= 0Page 45use = 1Page 191use = 1Page 556use = 0Page 13use = 0Page 67use = 1Page 33use = 1Page 222use = 0next frame pointer18State of buffer just afterthe next page replacement012345678n.Page 9use = 1Page 19use = 1Page 1use = 0Page 45use = 0Page 191use = 0Page 727use = 1Page 13use = 0Page 67use = 1Pa

16、ge 33use = 1Page 222use = 019Not Recently Used Page Replacement Algorithm (NRU)vEach page has Reference bit(R) and Modified bit(M).bits are set when page is referenced (read or written recently), modified (written to)when a process starts, both bits R and M are set to 0 for all pages.periodically, (

17、on each clock interval (20msec) ), the R bit is cleared. (i.e. R=0).vPages are classifiedClass 0: not referenced, not modifiedClass 1: not referenced, modifiedClass 2: referenced, not modifiedClass 3: referenced, modifiedvNRU removes page at randomfrom lowest numbered non-empty class20Least Recently

18、 Used (LRU)vAssume pages used recently will used again soonthrow out page that has been unused for longest timevSoftware Solution: Must keep a linked list of pagesmost recently used at front, least at rearupdate this list every memory reference Too expensive!vHardware solution 1: Equip hardware with

19、 a 64 bit counter. That is incrementing after each instruction. After memory reference, the counter value is stored in the page table entry of the page that was just referenced.choose page with lowest value counterperiodically zero the counter21Least Recently Used (LRU)vHardware solution 2: Maintain

20、 a matrix of n x n bits for a machine with n page frames. v When page frame K is referenced: (i) Set row K to all 1s. (ii) Set column K to all 0s.v The row whose binary value is smallest is the LRU page.22LRU using a matrix pages referenced in order 0,1,2,3,2,1,0,3,2,3LRU23Simulating LRU in Software

21、vLRU hardware is not usually available. NRU: evict a page that is NOT recently used;LRU: evict a page that is LEAST recently used;vNFU (Not Frequently Used) is implemented in software.At each clock interrupt, the R bit is added to the counter associated with each page. When a page fault occurs, the

22、page with the lowest counter is replaced.Problem: NFU never forgets, so a page referenced frequency long ago may have the highest counter.vModified NFU = NFU with Aging - at each clock interrupt:the counters are shifted right one bit, andthe R bits are added to the leftmost bit.In this way, we can g

23、ive higher priority to recent R values.24Simulating LRU in SoftwarevThe aging algorithm simulates LRU in softwarevNote 6 pages for 5 clock ticks, (a)(e)25LRU12 references, 10 faults26LRU and AnomaliesAnomalies cannot occur. 12 references, 8 faults 27The Working Set Page Replacement Algorithm (1)vThe

24、 working set is the set of pages used by the k most recent memory referencesvw(k,t) is the size of the working set at time, tExample: 26157775162341234443434441327 | |t1 | |t2 ws(t1)=1,2,5,6,7 ws(t2)=3,428D工作集大小过渡阶段时间稳定阶段进程开始执行后，随着访问新页面逐步建立较稳定的工作集。当内存访问的局部性区域的位置大致稳定时，工作集大小也大致稳定；局部性区域的位置改变时，工作集快速扩张和收

25、缩过渡到下一个稳定值。29The Working Set Page Replacement Algorithm (2)The working set algorithm30The WSClock Page Replacement AlgorithmOperation of the WSClock algorithm. (a) and (b) give an example of what happens when R = 1.31The WSClock Page Replacement AlgorithmOperation of the WSClock algorithm. (c) and (

26、d) give an example of R = 0.32Review of Page Replacement Algorithms33Design Issues for Paging SystemsLocal versus Global Allocation Policies (1)a)Original configurationb)Local page replacementc)Global page replacement34Load ControlvDespite good designs, system may still thrashvSome processes need mo

27、re memory but no processes need lessvSolution :Reduce a number of processes competing for memoryswap one or more to disk, divide up pages they heldreconsider degree of multiprogramming35Page Size (1)Small page sizevAdvantagesless internal fragmentation less unused program in memoryvDisadvantagesprog

28、rams need many pages, larger page tables36Page Size (2)vOverhead due to page table and internal fragmentationvWheres = average process size in bytesp = page size in bytese = page entry size in bytes2s epoverheadppage table spaceinternal fragmentationOptimized when2pseS=1MB, e=8, p=4KB37Separate Inst

29、ruction and Data SpacesvOne address spacevSeparate I and D spaces38Shared PagesTwo processes sharing same program sharing its page tableSeparate instruction and data space, easy to share39Cleaning PolicyvNeed for a background process, paging daemonperiodically inspects state of memoryvWhen too few f

30、rames are freeselects pages to evict using a replacement algorithmvIt can use same circular list (clock) as regular page replacement algorithm but with diff ptr (front hand & back hand)40Implementation IssuesOperating System Involvement with PagingFour times when OS involved with paging1.Process

31、 creation-determine program size-create page table2.Process execution-MMU reset for new process-TLB flushed3.Page fault time-determine virtual address causing fault-swap target page out, needed page in4.Process termination time-release page table, pages41Page Fault Handling (1)1.Hardware traps to ke

32、rnel, saving the PC on the stack2.General registers saved3.OS determines which virtual page needed4.OS checks validity of address, seeks page frame5.If selected frame is dirty, write it to disk, suspend the process42Page Fault Handling (2)6.OS brings schedules new page in from disk. While page loadi

33、ng, process still suspend7.Disk interrupts, page tables updated8.Faulting instruction backed up to when it began 9.Faulting process scheduled10.Registers restored11.Program continues43SegmentationvThe virtual memory solution so far is paging (one-dimensional)vFor some applications, having two or mor

34、e virtual address spaces may be much better than having only one.For example, a compiler has many tables that are built up as compilation proceeds, such as source text, symbol table, constant table, parse tree and stack.44Segmentation (1)vOne-dimensional address space with growing tablesvOne table m

35、ay bump into another45Segmentation (2)Allows each table to grow or shrink, independently46Segmentation (3)vSegmentation is a memory-management scheme that supports user view of memory.vPages are fixed in size, segments are variable sized.vA program is a collection of segments. A segment is a logical

36、 unit such as:Main programProcedureFunctionSymbol tableStack47Segmentation (4)Users view of a program48Segmentation (5)Logical view of segment49Segmentation Architecture (1)vLogical address consists of two parts:vSegment table: maps two-dimensional user-defined addresses into one-dimensional physica

37、l addresses; each table entry has:Base: contains the starting physical address where the segments reside in memoryLimit: specifies the length of the segmentvSegment-table base register (STBR) points to the segment tables location in memory50Address Translation51Example of Segmentation52Segmentation

38、Architecture (2)vProtectionWith each entry in segment table associatev validation bit = 0 illegal segmentv read/write/execute privilegesvProtection bits associated with segments; code sharing occurs at segment levelvSince segments vary in length, memory allocation is a dynamic storage-allocation pro

39、blem53Implementation of Pure Segmentation(a)-(d) Development of checkerboarding(e) Removal of the checkerboarding by compaction54Paging vs. SegmentationComparison of paging and segmentation55Advantage of SegmentationvMay be possible to shrink/grow segmentsvEach segment can be given its own protectio

40、n information.this is a much easier protection scheme than trying to protect each page of memoryvLinking programs is a trivial taskvCode can be shared between processes easily. Just load the code segment once. Copies of the same program access the same segment.56Disadvantage of SegmentationvProgrammer mus