友情提示:教材p183没有把“工作集”的概念讲解清楚,图5-11所示的工作集是错误的。

工作集

工作集是个动态的概念,但也是个经常被忽视的出题点。很多书上就寥寥几句话带过,根本不足以解决像2016年408的一道真题。在后面解释这个问题。

首先为了讲清楚工作集,需要先明白几个替换算法。


局部最佳页面替换算法

类似于全局最佳替换算法,需要事先知道页面的引用串,再根据进程行为改变页面数量。
思想:进程在t时刻访问某页面,如果该页面不在内存中,导致一次缺页。则把该页面装入一个空闲页框。无论是否发生缺页,算法在每一步需要考虑引用串,如果页面再时间间隔(t,t+τ)内未被再次引用,那么就移出内存页面,否则该页被保留到进程的驻留集中,直到再次被引用。τ是一个系统常量,间隔(t,t+τ)内称作滑动窗口。在任意时刻t,驻留集包含这个窗口中可见的那些页面,即:当前引用的页面,未来τ次内存访问引用的页面。实际窗口大小是τ+1.

这就像我们说的最佳置换算法,是看未来时。实际上无法实现,但可以作为衡量其他替换算法是否优良的标准。


工作集模型和工作集替换算法

工作集替换算法是可实现的算法,只不过不是往前看,而是往后看。驻留集未规定用多少页框,而是动态增长的,当然在实际系统中肯定设置了上限,比如Windows中大概32MB或者其他。对于一个进程来说,不用考虑那么远,看当下如何替换即可。工作集窗口大小是一个时间概念,不是说动态集合分配的页框数。而是过去k次(不含当前)访问的页面记号。比如工作集窗口大小是3,那么一个访问串为:0,2,3,2,1,4

则当访问页面4时,往前看3个,1,2,3在被窗口覆盖,因此驻留集中页面是3,2,1,当然现在4也要加入驻留集,什么时候被踢出去,要看窗口滑动。形象说来就是用一个挖了k个洞的尺子,紧跟在你当前要访问的页面屁股后面,当前的页面并未加入到驻留集,所以窗口还不含当前页面。在窗口内能看到的页面就是当前驻留集的内容。可以是看到2,2,2,2这样重复的,也就是一直访问的是同一个页面,因为驻留集要动态更新,窗口里就只能看到一个页面了,这个情况是OK的。

理解到这里,问题将非常容易解决。

这篇文章的主要出发点就是下面这个题目。

(2016.29)某进程访问页面的序列如下:
…,1,3,4,5,6,0,3,2,3,2,→t时刻←,0,4,0,3,2,9,1,…

若工作集窗口大小是6,则在t时刻的工作集为:A

A. {6,0,3,2}
B. {2,3,0,4}
C. {0,4,3,2,9}
D. {4,5,6,0,3,2}

分析:由上面的理论储备,这题就是简单的小学题了。在t时刻往后看6个,页号是:6,0,3,2,3,2

看到的就是这6个页号,即:6,0,3,2这四个页。那么驻留集就是这四个页。

我想很多很多人会往前数6个不一样的,然后开心的选择D,实际这题就只考察了一个简单的概念:工作集窗口。
 

“工作集” 有 0 条回应

发表评论

*