develop
main
nba
${ noResults }
2 Commits (main)
| Author | SHA1 | Message | Date |
|---|---|---|---|
 Pullaway11
|
61c72e1182 |
#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;
}
|
2 months ago |
|
pul9za2jp
|
6e08174610 |
Initial commit
|
2 months ago |