网站职业技能培训班,怎么做网站的seo优化,棋牌游戏网站建设,全网营销型推广网站建设目录
一、定义
二、分类
1、最佳置换算法 / 最远置换算法#xff08;OPT#xff0c;Optimal):
1.1、定义#xff1a;
1.2、例子#xff1a;
2、先进先出置换算法(FIFO#xff09;:
2.1、定义#xff1a;
2.2、实现方法#xff1a;
2.3、例子#xff1a;
3、最…目录
一、定义
二、分类
1、最佳置换算法 / 最远置换算法OPTOptimal):
1.1、定义
1.2、例子
2、先进先出置换算法(FIFO:
2.1、定义
2.2、实现方法
2.3、例子
3、最近最久未使用置换算法LRUleast recently used):
3.1、定义
3.2、实现方法
3.3、例子
4、时钟置换算法是一种性能和开销较均衡的算法又称CLOCK算法或最近未用算法NRUNotRecently Used)
4.1、简单的CLOCK算法实现方法:
4.2、例子
5、改进型的时钟置换算法
5.1、实现方式
三、总结 一、定义
页面置换算法是指在操作系统中当需要调入一个页面时若所有的物理页面已被占用则需要选择一个页面进行置换。页面置换算法是解决内存不足的问题从而实现更多程序同时运行的重要手段之一。
二、分类
1、最佳置换算法 / 最远置换算法OPTOptimal):
1.1、定义
每次选择淘汰的页面将是以后永不使用或者在最长时间内不再被访问的页面这样可以保证最低的缺页率。
1.2、例子 1在上例中首先依次访问页面并将页面放入内存块中直到内存块装满。
2装满后接下来要访问的是2号页面
3根据OPT算法规则我们依次往后查看要访问的页面发现在017三个页面中页面7是最远会被访问的。
4所以我们就会将内存块中的7页面淘汰替换为页面2装入。
5依此类推整个过程缺页中断发生了9次页面置换发生了6次.前3次没有发生页面置换
缺页率缺页次数 / 总的访问次数 注意缺页时未必发生页面置换。若还有可用的空闲内存块就不用进行页面置换。 2、先进先出置换算法(FIFO:
2.1、定义
每次选择淘汰的页面是最早进入内存的页面
2.2、实现方法
把调入内存的页面根据调入的先后顺序排成一个队列需要换出页面时选择队头页面即可。
队列的最大长度取决于系统为进程分配了多少个内存块。
2.3、例子 1在上例中首先依次访问页面并将页面放入内存块中直到内存块装满。
2下一个访问的是页面0此时就要把最早进来的页面3淘汰。
3替换为页面0. 3、最近最久未使用置换算法LRUleast recently used):
3.1、定义
每次淘汰的页面是最近最久未使用的页面
3.2、实现方法
赋予每个页面对应的页表项中用访问字段记录该页面自上次被访问以来所经历的时间t。
当需要淘汰一个页面时选择现有页面中t值最大的即最近最久未使用的页面。
3.3、例子 1在上例中首先依次访问页面并将页面放入内存块中直到内存块装满。
2一直访问直到访问到页面3时。
3在此之前我们依次访问过了7218所以7是最久没有被访问的。
4所以将7替换为3. 4、时钟置换算法是一种性能和开销较均衡的算法又称CLOCK算法或最近未用算法NRUNotRecently Used)
4.1、简单的CLOCK算法实现方法:
为每个页面设置一个访问位再将内存中的页面都通过链接指针链接成一个循环队列。当某页被访问时其访问位置为1。当需要淘汰一个页面时只需检查页的访问位。如果是0就选择该页换出;如果是1则将它置为0暂不换出继续检查下一个页面若第一轮扫描中所有页面都是1则将这些页面的访问位依次置为O后再进行第二轮扫描第二轮扫描中一定会有访问位为0的页面因此简单的CLOCK算法选择一个淘汰页面最多会经过两轮扫描)
4.2、例子 1若我们有如上例子且有5个内存块在依次访问了13425后我们会得到如下视图 2此时这几个内存块都被访问过所以它们的访问位都为1.
3我们从1号页面依次扫描而且要将经过的访问位为1的页面的访问位改为0并且找到访问位为0的页面。
4在上图中我们找了一圈也没有找到访问位为0的页面而且我们将它全部重置为0了。 5然后我们进行第二次扫描发现1号页为0所以淘汰它并且替换为6号页 6接下来访问347
因为有3号页了所以指针不动只是将3号页的访问位改为1
4号页同样如此。 7然后访问7此时转动指针将34的访问位改为0而且找到了2号页的访问位为0所以将7号页存到下方。 5、改进型的时钟置换算法 5.1、实现方式
1和简单时钟置换算法相似其实就是将找0改为了找00
2只不过第一轮并不会相简单的那样将1改为0
3而是如果第一轮没有找到00就会将01看作00进行淘汰。
4在第二轮的查找中会将访问位重置为0 5找到为00的页淘汰
6若是如下例子 7第一轮扫描00发现都不是。
8第二轮扫描01且被扫描过的页面的访问位都会被置为0 9第三轮扫描00没找到不改变什么
10第四轮扫描将01当作00淘汰 三、总结
