Unit 4.3
Paging Replacement

Presenter Notes

本节幻灯片

Page Fault

Objectives

  • Page Fault Handling
  • Page Replacement
  • Allocation Policies

Page Fault Handling (1)

  • The hardware traps to the kernel, saving the program counter on the stack.
  • An assembly code routine is started to save the general registers and other volatile information.
  • The operating system discovers that a page fault has occurred, and tries to discover which virtual page is needed.
  • Once the virtual address that caused the fault is known, the system checks to see if this address is valid and the protection consistent with the access.
  • If the page frame selected is dirty, the page is scheduled for transfer to the disk, and a context switch takes place.

Page Fault Handling (2)

  • When page frame is clean, operating system looks up the disk address where the needed page is, schedules a disk operation to bring it in.
  • When disk interrupt indicates page has arrived, page tables updated to reflect position, frame marked as being in normal state.
  • Faulting instruction backed up to state it had when it began and program counter reset to point to that instruction.
  • Faulting process scheduled, operating system returns to the (assembly language) routine that called it.
  • This routine reloads registers and other state information and returns to user space to continue execution, as if no fault had occurred.

Presenter Notes

通过页目录项可以发现页表不需要都存在内存当中，当访问一个虚拟地址，它对应的页表或者页不存在内存中时会触发 Page Fault 异常，就可以在异常处理函数中完成页表或者页的分配，理论上开启分页只需要准备好页目录。 页表或转换后备缓冲器中数据项有标注：“脏位”（dirty bit）：表示该页是否被写过。“访问位”（accessed bit）：表示该页最后使用于何时，以便于置换算法的实现。

Page Replacement

  • The operating system tries to keep a certain amount of free memory.
  • When the amount of free memory is low, the operating system begins to "steal pages".
  • Using special page replacement algorithms, the amount of free memory is restored to an acceptable range.

Local versus Global Allocation Policies

  • Local versus global page replacement. (a) Original configuration. (b) Local page replacement. (c) Global page replacement.

Presenter Notes

Summary

  • Page Fault Handling
  • Page Replacement
  • Allocation Policies

Page Replacement Algorithms

  • Optimal page replacement algorithm
  • Not recently used page replacement
  • First-In, First-Out page replacement
  • Second chance page replacement
  • Clock page replacement
  • Least recently used page replacement
  • Working set page replacement
  • WSClock page replacement

Presenter Notes

如果发生了缺页中断，就需要从磁盘上将需要的页面调入内存。如果内存没有多余的空间，就需要在现有的页面中选择一个页面进行替换。使用不同的页面置换算法，页面更换的顺序也会各不相同。如果挑选的页面是之后很快又要被访问的页面，那么系统将很开再次产生缺页中断，因为磁盘访问速度远远内存访问速度，缺页中断的代价是非常大的。

Page Replacement Algorithms (1)

Objectives

  • Optimal page replacement algorithm
  • Not recently used page replacement
  • First-In, First-Out page replacement
  • Second chance page replacement
  • Clock page replacement

Optimal page replacement algorithm

  • Replace the page that never be used in the future, or will not be used soon.
  • Best algorithm ... but is not implementable. It is useful as a benchmark.

Not Recently Used page replacement

Use Referenced and Modified bits to decide.

 R  M  
------
 0  0 
 0  1 
 1  0 
 1  1
  • R is set to 0 periodically, especially after a clock tick.
  • R = 0 , means this page is not referenced , thus it is less important.
  • R = 1 , means this page is important, keep it.
  • M = 0 , this page is clean, no need to write to disk.
  • M = 1 , this page is dirty, write to disk before replacement.
  • Easy to implement.

First-In, First-Out page replacement

  • Always replacement the oldest pages.
  • Might throw out important pages

Second Chance Algorithm

Operation of second chance.

  • (a) Pages sorted in FIFO order.
  • (b) Page list if a page fault occurs at time 20 and A has its R bit set. The numbers above the pages are their load times.

Presenter Notes

在使用FIFO更换一个页面时，需要看一下该页面是否在最近被访问过，如果没有被访问过，则替换该页面。反之，如果最近被访问过（通过检查其访问位的取值），则不替换该页面，而是将该页面挂到链表末端，并将该页面进入内存的时间设置为当前时间，并将其访问位清零。这样，对于最近被访问过的页面来说，相当于给了它第二次机会。

The Clock Page Replacement Algorithm

Presenter Notes

将页面排成一个时钟的形状，该时钟有一个针臂，每次需要更换页面时，我们从针臂所指的页面开始检查。如果当前页面的访问位为0，即从上次检查到这次，该页面没有被访问过，将该页面替换。反之，就将其访问位清零，并顺时针移动指针到下一个页面。重复这些步骤，直到找到一个访问位为0的页面。

Summary

  • Optimal page replacement algorithm
  • Not recently used page replacement
  • First-In, First-Out page replacemen
  • Second chance page replacement
  • Clock page replacement

Page Replacement Algorithms (2)

Objectives

  • Least Recently Used page replacement
  • Not Frequently Used page replacemen
  • Aging page replacement

LRU Page Replacement Algorithm

  • Replace the longest unused page.
  • Excellent but difficult to implement exactly.
  • Might need special hardware.

Presenter Notes

LRU算法不仅考虑最近是否用过，还要考虑最近使用的频率。这里是基于过去的数据预测未来：如果一个页面被访问的频率低，那么以后很可能也用不到。LRU算法虽然很好，但是实现成本高（需要分辨出不同页面中哪个页面时最近最少使用的），并且时间代价大（每次页面访问发生时都需要更新记录）

Using a matrix to simulate LRU

  • LRU using a matrix when pages are referenced in the order
    0, 1, 2, 3, 2, 1, 0, 3, 2, 3.

Not Frequently Used page replacement

  • Record R bit in every clock ticks to a counter for each page.
  • NFU never forgets.
  • So new coming pages are always less important.

Simulating LRU in Software

  • The aging algorithm simulates LRU in software. Shown are six pages for five clock ticks. The five clock ticks are represented by (a) to (e).

Presenter Notes

LRU算法的实现必须以某种方式记录每个页面被访问的次数，这是个相当大的工作量。最简单的方式就是在页表的记录项里增加一个计数域，一个页面被访问一次，这个计数器的值就增加1。于是，当需要更换页面时，只需要找到计数域值最小的页面替换即可，该页面即是最近最少使用的页面。

Summary

  • Least Recently Used page replacement
  • Not Frequently Used page replacement
  • Aging page replacement

Page Replacement Algorithms (3)

Objectives

  • Working Set Page Replacement
  • WSClock Page Replacement

Working Set Page Replacement

  • The working set is the set of pages used by the k most recent memory references.
  • The function w(k, t) is the size of the working set at time t.

Presenter Notes

工作集概念来源于程序访问的时空局限性，即在一段时间内，程序访问的页面将局限在一组页面集合上。例如，最近k次访问均发生在某m个页面上，那么m就是参数为k时的工作集。我们用w(k,t)来表示在时间t时k次访问所涉及的页面数量。

Working Set Page Replacement

Presenter Notes

如果一个程序在内存里面的页面数与其工作集大小相等或者超过工作集，则该程序可在一段时间内不会发生缺页中断。如果其在内存的页面数小于工作集，则发生缺页中断的频率将增加，甚至发生内存抖动。因此，工作计算法的目标就是维持当前的工作集的页面在物理内存里面。每次页面更换时，寻找一个不属于当前工作集的页面替换即可。

WSClock Page Replacement

When the hand comes all the way around to its starting point there are two cases to consider:

  • At least one write has been scheduled.
  • No writes have been scheduled.

Presenter Notes

使用工作集算法的原理，但是将页面的扫描顺序按照时钟的形式组织起来。这样每次需要替换页面时，从指针指向的页面开始扫描，从而达到更加公平的状态。而且，按时钟组织的页面只是在内存里面的页面，在内存外的页面不放在时钟圈里，从而提高实现效率。

WSClock Page Replacement

  • Operation of the WSClock algorithm. (a) and (b) give an example of what happens when R = 1. (c) and (d) give an example of R = 0.

Presenter Notes

鉴于其时间与空间上的优势，工作集时钟算法被大多商业操作系统所采纳。

Summary

  • Working Set Page Replacement
  • WSClock Page Replacement

Page Replacement Algorithms (4)

Objectives

  • Summary of Page Replacement Algorithms
  • Page fault rate versus page frames
  • Belady anomaly

Page Replacement Algorithms

Presenter Notes

页面置换时挑选页面的目标主要在于降低随后发生缺页中断的次数或概率。

Page fault rate versus page frames

  • Page fault rate as a function of the number of page frames assigned.

Presenter Notes

因为磁盘访问速度远远内存访问速度，缺页中断的代价是非常大的。

Belady anomaly

Bélády's anomaly is the phenomenon in which increasing the number of page frames results in an increase in the number of page faults for certain memory access patterns.
This phenomenon is commonly experienced when using the first-in first-out (FIFO) page replacement algorithm.

Page requests    3    2    1    0    3    2    4    3    2    1    0    4
Newest page        3*    2*    1*    0*    3*    2*    4*    4    4    1*    0*    0
                    3    2    1    0    3    2    2    2    4    1    1
Oldest page                 3    2    1    0    3    3    3    2    4    4

Page requests    3    2    1    0    3    2    4    3    2    1    0    4
Newest page        3*    2*    1*    0*    0    0    4*    3*    2*    1*    0*    4*
                    3    2    1    1    1    0    4    3    2    1    0
                        3    2    2    2    1    0    4    3    2    1
Oldest page                       3    3    3    2    1    0    4    3    2

An example of Bélády's anomaly. Using three page frames, nine page faults occur. Increasing to four page frames causes 10 page faults to occur. Page faults are in asterisk(*).

Presenter Notes

Summary

  • Summary of Page Replacement Algorithms
  • Page fault rate versus page frames
  • Belady anomaly

Reference

  • Chapter 3: Memory management, Modern Operating Systems . Forth Edition, Andrew S. Tanenbaum

results matching ""

    No results matching ""