Clock 及改进 Clock置换算法实现

操作系统课程设计报告

学 院：

学生姓名: ＿＿

学 号:

题 目： Clock 及改进 Clock置换算法实现

指 导 教 师:

1

一、 课程设计目的

操作系统课程设计是计算机专业重要的教学环节，它为学生提供了一个既动手又动脑，将课本上的理论知识和实际有机的结合起来，独立分析和解决实际问题的机会。

 进一步巩固和复习操作系统的基础知识。

 培养学生结构化程序、模块化程序设计的方法和能力。  提高学生调试程序的技巧和软件设计的能力。

 提高学生分析问题、解决问题以及综合利用 C 语言进行程序设计的能力。

二、 课程设计内容与要求：

模拟实现Clock及改进Clock置换算法，程序应按照Clock置换算法及改进Clock置换算法模拟实现页面的置换。

1．不同的功能使用不同的函数实现（模块化），对每个函数的功

能和调用接口要注释清楚。对程序其它部分也进行必要的注释。

2．对系统进行功能模块分析、画出总流程图和各模块流程图。 3．用户界面要求使用方便、简洁明了、美观大方、格式统一。所

有功能可以反复使用，最好使用菜单。

4．通过命令行相应选项能直接进入某个相应菜单选项的功能模

块。

5．所有程序需调试通过 三、 算法及关键数据结构设计

2

(1)Clock置换算法：

当采用简单Clock算法是只需为每页设置一位访问位，再将内存中的所用页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位被置1。置换算法在选择一页淘汰时，只需检查页的访问位。如果是0，就选择该页换出；若为1，则重新将他置0,暂不换出，而给该页第二次驻留内存的机会,在按照FIFO 算法检查下一个页面。当检查到队列中的最后一个页面是，若其访问位仍为1，则再返回到队首去检查第一个页面。 （2）算法流程图

（3）改进型Clock置换算法

在将一个页面换出时，如果该页已被修改过，便须将该页重新写回到磁盘上；但如果该页未被修改过，则不必将它拷回磁盘。在改进型Clock算法中，除须考虑页面的使用情况外，还须在增加一个因素，即置换代价，这样 页面换出时，既要是未使用过的页面，又要是未被修改过的页面。把同时满足这两个条件的页面作为首选淘汰的页

3

面。由访问位A和修改位M可以组合成下面四种类型的页面: 1类（A=0，M=0）：表示该页最近既未被访问，又未被修改，是最佳淘汰页。

2类（A=0，M=0）：表示该页最近未被访问，但已被修改，并不是很好的淘汰页。

3类（A=1，M=0）：表示该页最近已被访问，但未被修改，该页有可能在被访问。

4类（A=1，M=1）：表示该页最近已被访问且被修改，该页可能再被访问。，

执行过程：① 从查寻指针当前位置起扫描内存分页循环队列，选择A=0且M=0的第一个页面淘汰；若未找到，转②

② 开始第二轮扫描，选择A=0且M=1的第一个页面淘汰，同时将经过的所有页面访问位置0；若不能找到，转① 四、 程序代码分析

（1） Clock置换算法代码实现 void CLOCK(int num){ int j;

if(isInside(num)){ cout<<\"命中\"<cout<<\"物理块\"<4

} else

if(count == A){ lost++;

for(j=0; j < A; ){ if(state[j] == 0){ break; } else{

state[j] = 0; } j++; j = j %3; }

Inside[j] = Page[num]; state[j] = 1;

for(int i=0 ; i cout<<\"物理块\"<Inside[count] = Page[num];

5

count++;

for(int i=0 ; i cout<<\"物理块\"<（2） 改进Clock置换算法实现 void LCLOCK(int num){ int j;

if(isInside2(num)){ cout<<\"命中\"<cout<<\"物理块\"<if(count == A){ lost++; j =whichpage(); Inside[j] = Page[num]; state2[j][0] = 1; for(int i=0 ; i 6

cout<<\"物理块\"<else{

Inside[count] = Page[num]; count++;

for(int i=0 ; i cout<<\"物理块\"<五．程序截图 运行截图：

7

8

六．程序代码

#include #include

using namespace std; #define M 2

int const A = 4;//内存中存放的页面数 int count = 0; int Inside[A];

int const PageCount =10;//总的页面数 int Page[PageCount];

int insert = 0;//先到先出置换算法fcfo中表示 当内存满的时候，新进入的页号放的位置

9

int suiji = 0; //随机置换算法randchange 当内存满的时候，新进入的页号放的位置

int state[A];//clock置换算法中，内存中的每个页面号对应的状态 int state2[A][M];// 二维数组，第一行第一列为访问位，第一行的第二列为修改位

double lost = 0.0;

//检测页号是否在内存中 bool isInside(int num){ for(int i = 0; i < A; i++){ }

return false; }

//判断页面是否已经被修改 bool change(){

if((rand()%2+1) == 1 ){

if(Inside[i] == Page[num]){ }

state[i] = 1; return true;

cout<<\"该页面被修改\"<10

}

return true;

else }

//用于改进型clock置换算法，检测页号是否在内存中并把访问位和修改位置1

bool isInside2(int num){ for(int i = 0; i < A; i++){ }

return false;

11

return false;

if(Inside[i] == Page[num]){ }

if(change()){ } else{ }

return true; state2[i][0] = 1; state2[i][0] = 1; state2[i][1] = 1;

}

//用于改进型clock置换算法，判断内存中第几个需要被置换 int whichpage(){ int j;

for(j=0; j < A;j++){

if(state2[j][0] == 0&&state2[j][1] == 0){ }

for(j=0; j < A;j++ ){

if(state2[j][0] == 0&&state2[j][1] == 1){ }

for(j=0; j < A;j++ ){ }

return whichpage(); }

12

}

return j;

}

return j;

state2[j][0] = 0 ;

state2[j][0] = 0 ;

//简单Clock置换算法 void CLOCK(int num){ int j;

if(isInside(num)){

cout<<\"命中\"<cout<<\"物理块\"<if(count == A){

lost++; for(j=0; j < A; ){

if(state[j] == 0){ } else{ } j++;

13

break;

state[j] = 0;

}

j = j %3;

Inside[j] = Page[num]; state[j] = 1; for(int i=0 ; i cout<<\"物理块\"<} else{

Inside[count] = Page[num]; count++;

for(int i=0 ; i cout<<\"物理块\"<//改进型clock置换算法 void LCLOCK(int num){ int j;

if(isInside2(num)){

}

cout<<\"命中\"<14

cout<<\"物理块\"<if(count == A){

lost++; j =whichpage(); Inside[j] = Page[num]; state2[j][0] = 1; for(int i=0 ; i cout<<\"物理块\"<15

}

else{ }

Inside[count] = Page[num]; count++;

for(int i=0 ; i cout<<\"物理块\"<int main(){ char ch ;

cout<<\"默认的页号为\"<cout<cout<<\"------------1.Clock置换算法（CLOCK）-----\"<>ch; switch(ch){ case '1':{ lost = 0;

cout<count = 0;

for(int m = 0; m < A; m++){

state[m] = 0; }

16

for(int j = 0; j < A; j++){ }

for(int i = 0; i < PageCount; i++){

读

入

Inside[j] = 0;

cout<<\"Page[\"<CLOCK(i); }

cout<<\"\\n页面访问次数\"<}break; case '2':{ lost = 0;

count = 0;

for(int m = 0; m < A; m++){

for(int n = 0; n < 2;n++)

}

for(int j = 0; j < A; j++){ state2[m][n] = 0;

Inside[j] = 0;

}

for(int i = 0; i < PageCount; i++){

17

cout<<\"读入Page[\"<cout<<\"\\n页面访问次数\"<}break; case '0':{ } } return 0; }

exit(0);

}break;

18