|
|
#include <stdio.h>
|
|
|
#include <stdlib.h>
|
|
|
#include <time.h>
|
|
|
#include <string.h>
|
|
|
|
|
|
#define maxn 320 // 序列个数
|
|
|
#define max (maxn + 20) // 数组大小
|
|
|
#define maxp (max / 10) // 最大页数
|
|
|
|
|
|
int inst[max]; // 指令序列
|
|
|
int page[max]; // 页地址流
|
|
|
int size; // 内存能容纳的页数
|
|
|
|
|
|
int in[maxp]; // 该页是否在内存里，提高效率
|
|
|
int pin[maxp]; // 现在在内存里的页
|
|
|
|
|
|
void welcome()
|
|
|
{
|
|
|
printf("******************************************\n");
|
|
|
printf("** 操作系统模拟实验\t\t**\n");
|
|
|
printf("** 页式存储管理\t\t**\n");
|
|
|
printf("******************************************\n\n");
|
|
|
}
|
|
|
|
|
|
void input_hint()
|
|
|
{
|
|
|
printf("\n1--创建新指令序列 2--设置内存页数(4到32)\n");
|
|
|
printf("3--使用FIFO算法求解 4--使用LRU算法求解\n");
|
|
|
printf("5--使用OPT算法求解 0--退出\n");
|
|
|
printf("*********请输入您的选择: ");
|
|
|
}
|
|
|
|
|
|
/*通过随机数产生一个指令序列，共320条指令*/
|
|
|
void produce_inst()
|
|
|
{
|
|
|
int m, n;
|
|
|
int num = 0;
|
|
|
|
|
|
while (num < maxn)
|
|
|
{
|
|
|
m = rand() % maxn;
|
|
|
inst[num++] = (m + 1) % maxn;
|
|
|
if (num == maxn)
|
|
|
break;
|
|
|
|
|
|
m = (m + 2) % maxn;
|
|
|
if (m == 0)
|
|
|
m = 160;
|
|
|
n = rand() % m;
|
|
|
inst[num++] = (n + 1) % maxn;
|
|
|
if (num == maxn)
|
|
|
break;
|
|
|
|
|
|
n = (n + 2) % maxn;
|
|
|
m = maxn - n;
|
|
|
if (m == 0)
|
|
|
m = 160;
|
|
|
m = rand() % m + n;
|
|
|
inst[num++] = m;
|
|
|
}
|
|
|
}
|
|
|
|
|
|
/*将指令序列变换成为页地址流*/
|
|
|
void turn_page_address()
|
|
|
{
|
|
|
for (int i = 0; i < maxn; i++)
|
|
|
{
|
|
|
page[i] = inst[i] / 10;
|
|
|
}
|
|
|
}
|
|
|
|
|
|
void FIFO_solve()
|
|
|
{
|
|
|
memset(in, 0, sizeof(in));
|
|
|
int fault_n = 0; // 缺页次数
|
|
|
int ptr, i;
|
|
|
|
|
|
// 预调页填满空间
|
|
|
ptr = 0; // 下一个要放的位置
|
|
|
for (i = 0; i < maxn && ptr < size; i++)
|
|
|
if (!in[page[i]])
|
|
|
{
|
|
|
pin[ptr++] = page[i];
|
|
|
in[page[i]] = 1;
|
|
|
fault_n++;
|
|
|
}
|
|
|
|
|
|
// 继续执行剩下的指令
|
|
|
ptr = 0; // 队列里最先进来的位置，即下一个要被替换的位置
|
|
|
for (; i < maxn; i++)
|
|
|
if (!in[page[i]])
|
|
|
{
|
|
|
/*--------------*/
|
|
|
// 请补全该部分
|
|
|
in[pin[ptr]] = 0;
|
|
|
in[page[i]] = 1;
|
|
|
pin[ptr] = page[i];
|
|
|
fault_n++;
|
|
|
ptr = (ptr + 1) % size;
|
|
|
/*--------------*/
|
|
|
}
|
|
|
|
|
|
printf("\n使用FIFO算法，缺页次数为: %d\n", fault_n);
|
|
|
printf(" 命中率为: %.2lf\n", (1 - (fault_n + 0.0) / 320.0));
|
|
|
}
|
|
|
|
|
|
void LRU_solve()
|
|
|
{
|
|
|
int ltu[maxp]; // 最后使用时间 (last_time_use)
|
|
|
int ti = 1; // 模拟时间
|
|
|
int fault_n = 0;
|
|
|
memset(ltu, 0, sizeof(ltu));
|
|
|
memset(in, 0, sizeof(in));
|
|
|
memset(pin, -1, sizeof(pin));
|
|
|
|
|
|
int min, ptr, i, j;
|
|
|
for (i = 0; i < maxn; i++)
|
|
|
{
|
|
|
if (!in[page[i]])
|
|
|
{
|
|
|
// 寻找LRU页面
|
|
|
min = 1000000;
|
|
|
ptr = 0;
|
|
|
for (j = 0; j < size; j++)
|
|
|
{
|
|
|
if (ltu[j] < min)
|
|
|
{
|
|
|
/*--------------*/
|
|
|
// 请补全该部分
|
|
|
min = ltu[j];
|
|
|
ptr = j;
|
|
|
/*--------------*/
|
|
|
}
|
|
|
}
|
|
|
// 替换或写入
|
|
|
/*--------------*/
|
|
|
// 请补全该部分
|
|
|
in[pin[ptr]] = 0;
|
|
|
pin[ptr] = page[i];
|
|
|
in[page[i]] = 1;
|
|
|
/*--------------*/
|
|
|
fault_n++;
|
|
|
ltu[ptr] = ti++;
|
|
|
}
|
|
|
else // 已经在内存里则只需修改最近使用时间
|
|
|
{
|
|
|
for (j = 0; j < size; j++)
|
|
|
if (pin[j] == page[i])
|
|
|
{
|
|
|
ltu[j] = ti++;
|
|
|
break;
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
|
|
|
printf("\n使用LRU算法，缺页次数为: %d\n", fault_n);
|
|
|
printf(" 命中率为: %.2lf\n", (1 - (fault_n + 0.0) / 320.0));
|
|
|
}
|
|
|
|
|
|
void OPT_solve()
|
|
|
{
|
|
|
int ntu[maxp]; // 下次使用时间 (next_time_use)
|
|
|
int fault_n = 0;
|
|
|
int i, j;
|
|
|
memset(in, 0, sizeof(in));
|
|
|
memset(ntu, -1, sizeof(ntu));
|
|
|
|
|
|
// 预调页填满
|
|
|
int ptr = 0;
|
|
|
for (i = 0; i < maxn && fault_n < size; i++)
|
|
|
{
|
|
|
if (!in[page[i]])
|
|
|
{
|
|
|
in[page[i]] = 1;
|
|
|
pin[ptr] = page[i];
|
|
|
fault_n++;
|
|
|
ptr++;
|
|
|
}
|
|
|
}
|
|
|
|
|
|
// 初始化ntu数组
|
|
|
ptr = 0;
|
|
|
for (j = i; j < maxn && ptr < 32; j++)
|
|
|
{
|
|
|
if (ntu[page[j]] == -1)
|
|
|
{
|
|
|
/*--------------*/
|
|
|
// 请补全该部分
|
|
|
ntu[page[j]] = j;
|
|
|
/*--------------*/
|
|
|
}
|
|
|
}
|
|
|
|
|
|
int temp;
|
|
|
for (; i < maxn; i++)
|
|
|
{
|
|
|
if (!in[page[i]])
|
|
|
{
|
|
|
temp = 0;
|
|
|
ptr = 0;
|
|
|
for (j = 0; j < size; j++)
|
|
|
{
|
|
|
if (ntu[pin[j]] == -1)
|
|
|
{
|
|
|
ptr = j;
|
|
|
break;
|
|
|
}
|
|
|
if (ntu[pin[j]] > temp)
|
|
|
{
|
|
|
/*--------------*/
|
|
|
// 请补全该部分
|
|
|
temp = ntu[pin[j]];
|
|
|
ptr = j;
|
|
|
/*--------------*/
|
|
|
}
|
|
|
}
|
|
|
in[pin[ptr]] = 0;
|
|
|
in[page[i]] = 1;
|
|
|
pin[ptr] = page[i];
|
|
|
fault_n++;
|
|
|
}
|
|
|
|
|
|
ntu[page[i]] = -1;
|
|
|
for (j = i + 1; j < maxn; j++)
|
|
|
if (page[j] == page[i])
|
|
|
{
|
|
|
ntu[page[i]] = j;
|
|
|
break;
|
|
|
}
|
|
|
}
|
|
|
|
|
|
printf("\n使用OPT算法，缺页次数为: %d\n", fault_n);
|
|
|
printf(" 命中率为: %.2lf\n", (1 - (fault_n + 0.0) / 320.0));
|
|
|
}
|
|
|
|
|
|
int main()
|
|
|
{
|
|
|
srand(100);
|
|
|
welcome();
|
|
|
|
|
|
int choice;
|
|
|
while (1)
|
|
|
{
|
|
|
input_hint();
|
|
|
scanf("%d", &choice);
|
|
|
printf("\n");
|
|
|
|
|
|
if (choice == 0)
|
|
|
{
|
|
|
printf("再见!!!\n");
|
|
|
break;
|
|
|
}
|
|
|
if (choice == 1)
|
|
|
{
|
|
|
produce_inst();
|
|
|
turn_page_address();
|
|
|
printf("新页地址序列设置成功!!!\n");
|
|
|
}
|
|
|
else if (choice == 2)
|
|
|
{
|
|
|
printf("请输入内存页数: ");
|
|
|
scanf("%d", &size);
|
|
|
}
|
|
|
else if (choice == 3)
|
|
|
FIFO_solve();
|
|
|
else if (choice == 4)
|
|
|
LRU_solve();
|
|
|
else if (choice == 5)
|
|
|
OPT_solve();
|
|
|
else
|
|
|
printf("输入错误 !!! \n");
|
|
|
}
|
|
|
|
|
|
return 0;
|
|
|
} |
