北京企业网站建设哪家服务好,wordpress first主题,国外服务器怎么买,舆情信息报送1.实验目标
利用标准C 语言#xff0c;编程设计与实现最佳淘汰算法、先进先出淘汰算法、最近最久未使用淘汰算法、简单 Clock 淘汰算法及改进型 Clock 淘汰算法#xff0c;并随机发生页面访问序列开展有关算法的测试及性能比较。
2.算法描述 1. 最佳淘汰算法#xff08;Op…1.实验目标
利用标准C 语言编程设计与实现最佳淘汰算法、先进先出淘汰算法、最近最久未使用淘汰算法、简单 Clock 淘汰算法及改进型 Clock 淘汰算法并随机发生页面访问序列开展有关算法的测试及性能比较。
2.算法描述 1. 最佳淘汰算法Optimal Replacement Algorithm这种算法选择将来最久不会被访问的页面进行淘汰。实现这个算法需要预知未来的页面访问请求因此在实际中无法实现但是我们可以模拟访问序列来比较实现效果。
2. 先进先出淘汰算法FIFO Replacement Algorithm这种算法总是淘汰最早进入内存的页面。实现这个算法可以使用一个队列新进入的页面放入队尾需要淘汰页面时总是淘汰队头的页面。
3. 最近最久未使用淘汰算法LRU Replacement Algorithm这种算法淘汰最长时间未被访问的页面。实现这个算法可以使用一个链表每次页面被访问时将这个页面移动到链表头需要淘汰页面时总是淘汰链表尾的页面。
4. 简单 Clock 淘汰算法Clock Replacement Algorithm这种算法将内存中的页面组织成一个环形链表有一个指针指向最早进入的页面。每次需要淘汰页面时检查指针指向的页面如果这个页面最近被访问过则将其标记清除指针向前移动否则淘汰这个页面。
5. 改进型 Clock 淘汰算法Enhanced Clock Replacement Algorithm这是 Clock 算法的改进版增加了一个修改位用于记录页面是否被修改过。在选择淘汰的页面时优先选择未被修改且最近未被访问的页面。
3.访问序列模拟
1. 初始化进程逻辑地址空间页面总数 N、各逻辑页面的读写访问方式是否支持写访问即R、RW、工作集起始页号ss∈[0, N) 、工作集中包含的页数 w工作集移动速率 v每处理 v 个页面访问就将工作集起始页号递增即 s1以及一个取值区间为[0, 1]的值 t
2. 生成取值区间为[s, min(sw, N-1)]的v 个随机数并添加保存到页面访问序列中同时为每次页面访问分别生成一个取值区间为[0, 1]的随机数若该随机数值大于 0.7 且对应所访问页面支持写访问则设定以写方式访问相应页面否则以读方式访问对应页面
3. 生成取值区间为[0, 1]的一个随机数r并比较 r 与t 的大小
4. 若r t则为s 生成一个新值s∈[0, N) 否则s (s 1) mod N
5. 如果想继续加大页面访问序列的长度返回第 2 步否则结束
4.模拟测试思路
基于相同的条件系统均采用固定分配局部置换策略、相同的进程逻辑地址空间大小、分配给进程同样多的物理块、相同的页面访问序列、均预装入前三个页面进行有关算法的测试预计执行一百轮测试以轮数为随机数种子保证结果可以复现。
5.相关数据结构
// 模拟页面
struct PAGE { int pages[MAXLEN];int usenum; // 分配的最大页框数int visitlen; // 访问序列长度
} pinfo;// 模拟页表
struct MEM { int time; // 访问记录int r; // 访问位int rw; // 修改位int pages; // 页号
} minfo;MEM pagelist[MAXLEN]; // 分配页框
#include iostream
#include thread
#include time.h
using namespace std;const int MAXLEN 1024; // 最大页面数
const int epoch 100; // 测试次数
int lossnum; // 缺页次数统计
int now; // 当前访问的页面
int replace; // 页面替换指针
int lossflag; // 是否缺页
int full; // 已使用的页框数
int rate[5][epoch];
int times[5][epoch];struct PAGE {int pages[MAXLEN];int usenum; // 分配的最大页框数int visitlen; // 访问序列长度
} pinfo;
struct MEM {int time; // 访问记录int r; // 访问位int rw; // 修改位int pages; // 页号
} minfo;
MEM pagelist[MAXLEN]; // 分配页框void pageinit() { // 初始化页面数据pinfo.usenum 3;pinfo.visitlen 256;for (int i 0; i MAXLEN; i)pinfo.pages[i] -1;
}void visitlist(int epoch) { // 随机生成访问序列int v 16, w 64, s 128; // v为每个页面访问次数w为每个页面访问的范围s为页面访问的起始位置pageinit();srand(epoch); // 随机种子int t rand() % 11; // 生成tfor(int i 0, j 0; i 10; i) {for(j i * v; j (i 1) * v; j) { // 生成v个[s, sw]的随机数if(j pinfo.visitlen) // 生成数量不能超序列长度break;pinfo.pages[j] (s (rand() % w)) % MAXLEN; // 随机数存储到访问序列中}if(rand() % 11 t) // 如果r t则为p生成一个新值s rand() % MAXLEN;elses (s 1) % MAXLEN;}
}bool randBool() { // 读写随机数生成函数if(rand() % 11 7) return true;else return false;
}bool inram(int page) { // 查找是否在内存for(int i 0; i pinfo.usenum; i) {pagelist[i].time; // 访问记录}for(int i 0; i pinfo.usenum; i) {if(pagelist[i].pages page) {lossflag 0; // 不缺页置为0pagelist[i].time 0; // 访问记录置0if(randBool()) {pagelist[i].r 1;pagelist[i].rw 1;}elsepagelist[i].r 1;return true;}}lossflag 1; // 缺页置为1return false;
}void OPT() {// 最佳淘汰算法replace 0, lossnum 0, full 0, lossflag 0;for(int i 0; i pinfo.usenum; i) // 刷新页框pagelist[i].pages -1;for(now 0; now pinfo.visitlen; now) {if(full pinfo.usenum) {if(!inram(pinfo.pages[now])) { // 不在内存则装入页面pagelist[replace].pages pinfo.pages[now];replace (replace 1) % pinfo.usenum;full, lossnum; }}else {if(!inram(pinfo.pages[now])) { // 不在内存则需置换int min, max 0 ; // min为最近访问max为最远访问for(int m 0; m pinfo.usenum ; m) {min MAXLEN;for(int n now; n pinfo.visitlen; n) {if (pinfo.pages[n] pagelist[m].pages) {min n;break;}}if(max min) {max min;replace m;}}pagelist[replace].pages pinfo.pages[now];replace (replace 1) % pinfo.usenum;lossnum;}}std::this_thread::sleep_for(10ms);}
}void FIFO(void) { // 先进先出淘汰算法replace 0, lossnum 0, full 0, lossflag 0;for(int i 0; i pinfo.usenum; i)pagelist[i].pages -1;for(now 0; now pinfo.visitlen; now) {if(full pinfo.usenum) { if(!inram(pinfo.pages[now])) {pagelist[replace].pages pinfo.pages[now];replace (replace 1) % pinfo.usenum;full, lossnum;}}else {if(!inram(pinfo.pages[now])) {pagelist[replace].pages pinfo.pages[now];replace (replace 1) % pinfo.usenum;lossnum;}}std::this_thread::sleep_for(10ms);}
}void LRU(void) { // 最近最久未使用淘汰算法replace 0, lossnum 0, full 0, lossflag 0;for(int i 0; i pinfo.usenum; i) {pagelist[i].pages -1;pagelist[i].time 0;} // 刷新页框for(now 0; now pinfo.visitlen; now) {if(full pinfo.usenum) {if(!inram(pinfo.pages[now])) {pagelist[replace].pages pinfo.pages[now];replace (replace 1) % pinfo.usenum;full, lossnum;}}else {if(!inram(pinfo.pages[now])) {int max 0; // 最久的访问记录for(int i 1; i pinfo.usenum; i) {if(pagelist[i].time pagelist[max].time) {max i;}}replace max;pagelist[replace].pages pinfo.pages[now];pagelist[replace].time 0;lossnum;}}std::this_thread::sleep_for(10ms);}
}int replace0(int num) { // 简单Clock置换for(int i 0; i pinfo.usenum; i) {if(pagelist[(i num) % pinfo.usenum].r 0 ) // 找到第一个访问位为0的页面return (i num) % pinfo.usenum;pagelist[(i num) % pinfo.usenum].r 0; // 未找到则将所有访问位置0}for(int i 0; i pinfo.usenum; i) {if(pagelist[(i num) % pinfo.usenum].r 0 )return (i num) % pinfo.usenum;}return 0;
}int replace1(int num) { // 改进的clock置换for(int i 0; i pinfo.usenum; i) {if (pagelist[(i num) % pinfo.usenum].r 0 pagelist[(i num) % pinfo.usenum].rw 0) // 先找访问位和修改位都为0的页面return (i num) % pinfo.usenum;}for(int i 0; i pinfo.usenum; i) {if (pagelist[(i num) % pinfo.usenum].r 0 pagelist[(i num) % pinfo.usenum].rw 1) // 再找访问位为0修改位为1的页面return (i num) % pinfo.usenum;pagelist[(i num) % pinfo.usenum].r 0; // 未找到则将所有访问位置0}for(int i 0; i pinfo.usenum; i) {if (pagelist[(i num) % pinfo.usenum].r 0 pagelist[(i num) % pinfo.usenum].rw 0) // 再找访问位和修改位都为0的页面return (i num) % pinfo.usenum;}for(int i 0; i pinfo.usenum; i) {if (pagelist[(i num) % pinfo.usenum].r 0 pagelist[(i num) % pinfo.usenum].rw 1) // 最后找访问位为0修改位为1的页面return (i num) % pinfo.usenum;}return 0;
}void CLOCK(int choose) {int num 0;replace 0, lossnum 0, full 0, lossflag 0;for(int i 0; i pinfo.usenum; i) {pagelist[i].pages -1;pagelist[i].rw 0;pagelist[i].r 0;pagelist[i].time 0;}for(now 0; now pinfo.visitlen; now) {if(full pinfo.usenum) {if(!inram(pinfo.pages[now])) {pagelist[replace].pages pinfo.pages[now];replace (replace 1) % pinfo.usenum;pagelist[replace].r 1;full, lossnum;}}else {if(!inram(pinfo.pages[now])) {if(choose 1)replace replace1(num); // choose1,改进clock算法else if(choose 0) // choose0,简单clock算法replace replace0(num); pagelist[replace].pages pinfo.pages[now];pagelist[replace].r 1;lossnum;}}std::this_thread::sleep_for(10ms);}
}void calculate(int i, int j, clock_t start) { // 计算缺页率和运行时间rate[i][j] (double)(lossnum) * 100 / now;times[i][j] (double)(clock() - start) / 1000;
}int main() {clock_t start;for(int i 0; i epoch; i) {visitlist(i);start clock();OPT();calculate(0, i, start);start clock();FIFO();calculate(1, i, start);start clock();LRU();calculate(2, i, start);start clock();CLOCK(0);calculate(3, i, start);start clock();CLOCK(1);calculate(4, i, start);}for(int i 0; i 5; i) {if(i 0) printf(OPT: );if(i 1) printf(FIFO: );if(i 2) printf(LRU: );if(i 3) printf(CLOCK: );if(i 4) printf(CLOCK: );int avrate 0, avtime 0;for(int j 0; j epoch; j) {avrate rate[i][j];avtime times[i][j];}printf(Average replace rate %.3lf%% , (double)(avrate) / epoch);printf(Average spend time: %.3lfs\n, (double)(avtime) / epoch);}return 0;
}7.运行结果
