时钟置换算法CLOCK.doc

时钟置换算法（CLOCK）例题：

一个作业的物理块数为3，此作业的页面走向为：3,4,2,6,4,3,7,4,3,6,3,4,8,4,6
内存及控制信息
输入串
指针移动情况及帧替换信息
是否缺页？
内存
访问位
指针
3
内存中没有3，需要找到一个帧放入3，
指针所指的位置恰好有访问位为0的，
于是就淘汰这个帧，指针下移
√

0
←

0

0

内存
访问位
指针
4
内存中没有4，需要找到一个帧放入4，
指针所指的位置恰好有访问位为0的，
于是就淘汰这个帧，指针下移
√
3
1

0
←

0

内存
访问位
指针
2
内存中没有2，需要找到一个帧放入2，
指针所指的位置恰好有访问位为0的，
于是就淘汰这个帧，指针下移
√
3
1

4
1

0
←
内存
访问位
指针
6
内存中没有6，需要找到一个帧放入6，
指针所指的位置的访问位为1，
将其变成0，再下移
√
3
1
←
4
1

2
1

内存
访问位
指针
指针所指的位置的访问位仍为1，
将其变成0，再下移
3
0

4
1
←

2
1

内存
访问位
指针
指针所指的位置的访问位仍为1，
将其变成0，再下移（回到开头）
3
0

4
0

2
1
←
内存
访问位
指针
指针所指的位置恰好有访问位为0的，
于是就淘汰这个帧，指针下移
3
0
←
4
0

2
0

内存
访问位
指针
4
内存中有4，于是4所在帧的访问位变为1，
指针下移
×
6
1

4
0
←
2
0

内存
访问位
指针
3
内存中没有3，需要找到一个帧放入3，
指针所指的位置恰好有访问位为0的，
于是就淘汰这个帧，指针下移
√
6
1

4
1

2
0
←
内存
访问位
指针
7
内存中没有7，需要找到一个帧放入7，
指针所指的位置的访问位为1，
将其变成0，再下移
√
6
1
←
4
1

3
1

内存
访问位
指针

指针所指的位置的访问位仍为1，
将其变成0，再下移

6
0

4
1
←
3
1

内存
访问位
指针
指针所指的位置的访问位仍为1，
将其变成0，再下移（回到开头）
6
0

4
0

3
1
←
内存
访问位
指针
指针所指的位置恰好有访问位为0的，
于是就淘汰这个帧，指针下移
6
0
←
4
0

3
0

内存
访问位
指针
4
内存中有4，于是4所在帧的访问位变为1，
指针下移
×
7
1

4
0
←
3
0

内存
访问位
指针
3
内存中有3，于是3所在帧的访问位变为1，
指针下移（回到开头）
×
7
1

4
1

3
0
←
内存
访问位
指针
6
内存中没有6，需要找到一个帧放入6，
指针所指的位置的访问位为1，
将其变成0，再下移
√

7
1
←

4
1

3
1

内存
访问位
指针
指针所指的位置的访问位仍为1，
将其变成0，再下移
7
0

4
1
←
3
1

内存
访问位
指针
指针所指的位置的访问位仍为1，
将其变成0，再下移（回到开头）
7
0

4
0

3
1
←
内存
访问位
指针
指针所指的位置恰好有访问位为0的，
于是就淘汰这个帧，指针下移
7
0
←
4
0

3
0

内存
访问位
指针
3
内存中有3，于是3所在帧的访问位变为1，
指针下移
×
6
1

4
0
←
3
0

内存
访问位
指针
4
内存中有4，于是4所在帧的访问位变为1，
指针下移
×
6
1
←
4
0

3
1

内存
访问位
指针
8
内存中没有8，需要找到一个帧放入8，
指针所指的位置的访问位为1，
将其变成0，再下移（回到开头）
√
6
1

4
1

3
1
←
内存
访问位
指针
指针所指的位置的访问位仍为1，
将其变成0，再下移
6
1
←
4
1

3
0

内存
访问位
指针
指针所指的位置的访问位仍为1，
将其变成0，再下移
6
0

4
1
←
3
0

内存
访问位
指针
指针所指的位置恰好有访问位为0的，
于是就淘汰这个帧，指针下移（回到开头）
6
0

4
0

3
0
←
内存
访问位
指针
4
内存中有4，于是4所在帧的访问位变为1，
指针下移
×
6
0
←
4
0

8
1

内存
访问位
指针
6
内存中有6，于是6所在帧的访问位变为1，
指针下移
×

6
0

4
1

8
1
←
内存
访问位
指针
结束
完成
缺页8次
6
1

4
1
←
8
1

（注：专业文档是经验性极强的领域，无法思考和涵盖全面，素材和资料部分来自网络，供参考。可复制、编制，期待你的好评与关注）