#include<stdio.h>
void Print(int bc[],int blockCount)
{
for(int i=0i<blockCounti++)
{
printf("%d ",bc[i])
}
printf("\n")
}
bool Travel(int bc[],int blockCount,int x)
{
bool is_found=false
int i
for(i=0i<blockCounti++)
{
if(bc[i]==x)
{
is_found=true
break
}
}
return is_found
}
void FIFO(int pc[],int bc[],int pageCount,int blockCount)
{
printf("0：FIFO置换算法\n")
int i
if(pageCount<=blockCount)
{
printf("缺页次数为0\n")
printf("缺页率为0\n")
}
else
{
int noPage=0
int p=0
for(i=0i<pageCounti++)
{
//printf("引用页：%d\n",pc[i])
if(!Travel(bc,blockCount,pc[i]))
{
if(i<blockCount)
{
bc[i]=pc[i]
}
else
{
if(p==blockCount)
{
p=0
}
bc[p]=pc[i]
p++
}
noPage++
//printf("物理块情况：\n")
//Print(bc,blockCount)
}
//printf("\n")
}
printf("FIFO缺页次数为:%d\n",noPage)
printf("FIFO缺页率为:%.2f%%\n",(float)noPage/pageCount*100)
}
}
int FoundMaxNum(int a[],int n)
{
int k,j
k=a[0]
j=0
for (int i=0i<ni++)
{
if(a[i]>=k)
{
k=a[i]
j=i
}
}
return j
}
void LRU(int pc[],int bc[],int pageCount,int blockCount)
{
printf("1：LRU置换算法\n")
if(pageCount<=blockCount)
{
printf("缺页次数为0\n")
printf("缺页率为0\n")
}
else
{
int noPage=0
int i,j,m
int bc1[100]
for(i=0i<blockCounti++)
{
bc1[i]=0
}
for(i=0i<pageCounti++)
{
// printf("引用页：%d\n",pc[i])
if(!Travel(bc,blockCount,pc[i]))
{
if(i<blockCount)
{
bc[i]=pc[i]
for(int p=0p<=ip++)
{
bc1[p]++
}
}
else
{
for(j=0j<blockCountj++)
{
bc1[j]++
}
int k=FoundMaxNum(bc1,blockCount)
bc[k]=pc[i]
bc1[k]=1
}
noPage++
//printf("物理快情况：\n")
//Print(bc,blockCount)
}
else if(Travel(bc,blockCount,pc[i]))
{
if(i<blockCount)
{
for(j=0j<=ij++)
{
bc1[j]++
}
for(m=0m<=im++)
{
if(bc[m]==pc[i])
{
break
}
}
bc1[m]=1
bc[m]=pc[i]
}
else
{
for(j=0j<blockCountj++)
{
bc1[j]++
}
for(m=0m<blockCountm++)
{
if(bc[m]==pc[i])
{
break
}
}
bc1[m]=1
bc[m]=pc[i]
}
}
//printf("\n")
}
printf("LRU缺页次数为:%d\n",noPage)
printf("LRU缺页率为:%.2f%%\n",(float)noPage/pageCount*100)
}
}
void Optiomal(int pc[],int bc[],int pageCount,int blockCount)
{
printf("2：最佳置换算法\n")
if(pageCount<=blockCount)
{
printf("缺页次数为0\n")
printf("缺页率为0\n")
}
else
{
int noPage=0
int i,j,k
for(i=0i<pageCounti++)
{
// printf("引用页：%d\n",pc[i])
if(!Travel(bc,blockCount,pc[i]))
{
if(i<blockCount)
{
bc[i]=pc[i]
}
else
{
int max=0
int blockIndex
for(j=0j<blockCountj++)
{
for(k=ik<pageCountk++)
{
if(bc[j]==pc[k])
{
break
}
}
if(k>=max)
{
max=k
blockIndex=j
}
}
bc[blockIndex]=pc[i]
}
noPage++
//printf("物理快情况：\n")
//Print(bc,blockCount)
}
//printf("\n")
}
printf("OPT缺页次数为:%d\n",noPage)
printf("OPT缺页率为:%.2f%%\n",(float)noPage/pageCount*100)
}
}
int main()
{
int pageCount,blockCount,i,pc[100]
printf("输入页面数\n")
scanf("%d",&pageCount)
printf("输入页面走向\n")
for(i=0i<pageCounti++)
{
scanf("%d",&pc[i])
}
blockCount=3//物理块数
int bc1[100]
printf("\n")
FIFO(pc,bc1,pageCount,blockCount)
int bc2[100]
printf("\n")
LRU(pc,bc2,pageCount,blockCount)
int bc3[100]
printf("\n")
Optiomal(pc,bc3,pageCount,blockCount)
return 0
}
/*最优置换算法（OPT）是指，其所选择的被淘汰页面，将是以后永不使用的，或许是在最长(未来)时间内不再拍拍被访问的页面。
采用最佳置换算法，通常可保证获得最低的缺页率。
但由于人们目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，
因而该算法是无法实现的，但可以利用该算法去评价其它算法。
*/
#include<stdio.h>
#include<stdlib.h>
#define M 4
#define N 17
typedef struct page
{
int num //记录页面号
int time//记录调入内存时间
}Page
Page b[M]//物理块个数
int c[M][N] //保存内存状态
int queue[50]//记录调入队列
int times//计数
void init(Page *b, int c[M][N])//内存初始化
{
int i, j
for (i = 0 i<N i++)
{
b[i].num = -1
b[i].time = N - i - 1
}
for (i = 0 i<M i++)
{
for (j = 0 j<N j++)
{
c[i][j] = -1
}
}
}
int GetOpt(int a[N], Page *b, int e)//取最近最久未使用的页面
{
int i, j
int opt = -1
int tag = 0
for (i = 0 i<M i++)
{
for (j = e j<N j++)
{
if (b[i].num == a[j])
{
b[i].time = j
break
}
else if (j == N - 1)
{
b[i].time = j
}
}
if (b[i].time>opt)
{
opt = b[i].time
tag = i
}
}
return tag
}
int judge(int num, Page *b)//判断页面是否已在内存中
{
int i
for (i = 0 i<M i++)
{
if (num == b[i].num)
{
return i
}
}
return -1
}
void OPT(int num, int a[N], Page *b, int e)
{
int i, v
v = judge(num, b)
if (v >= 0)
{
b[v].time = 0
for (i = 0 i<M i++)
{
if (i != v)
b[i].time++
}
}
else
{
queue[++times] = num
v = GetOpt(a, b, e)
b[v].num = num
b[v].time = 0
for (i = 0 i<M i++)
{
if (i != v) b[i].time++
}
}
}
int main()
{
int 袭让羡a[N] = { 1,2,3,4,1,2,5,1,2,3,4,5 }
int i, j
times = -1
init(b, c)
for (i = 0 i<N i++)
{
OPT(a[i], a, b, i)
c[0][i] = a[i]
//记录当前的内存单元中的页面
for (j = 滑顷0 j<M j++)
c[j][i] = b[j].num
}
for (j = 0 j<N j++)
printf("%2d", a[j])
printf("\n")
for (i = 0 i<M i++)
{
for (j = 0 j<N j++)
{
if (c[i][j] == -1) printf("%2c", 32)
else printf("%2d", c[i][j])
}
printf("\n")
}
printf("\n调入队列为：")
for (i = 0 i<times i++)
printf("%3d", queue[i])
printf("\n缺页次数为:%6d\n缺页率为:%16.6f\n", times + 1, (float)(times + 1) / N)
}
我替你修改了几个地方，你自己对比一下代码吧。
你的代码基本正确，只是有两处小错误。
另外，queue的单词拼写不正确，我也替你改了。
程序运行结果如图:
#include "stdio.h"#include "malloc.h"
#define OK 1
#define ERROR 0
#define NULL 0
#define status int
typedef int Elemtype
/*这个定义的是队列的元素的数据结构*/
typedef struct tailDATA{
Elemtype data/*这个存放的是队列元素的值*/
struct tailDATA *next//指向下一个元素
}datatail,*map
/*以下定义的是队列头的数据结构*/
typedef struct Tail{
/*说明:对队列进行 *** 作的时候,插入的时候是对front *** 作,删除模肆尘*/
Elemtype data/*这个记载的是队列的元素的个数*/
map front/*这个是队列的头*/
map rear/*这个是队列的尾*/
}tail,*mappath
/*以下定义的就是 *** 作了,初始话的 *** 作就不想做了,直接写个插入和删除等的一些的算法就可以了*/
status inserttail(mappath &T,map P)
{/*这个函数的功能是将一个个已知的元素插入雹指队列中*/
if(T==NULL)
{
T=(mappath)malloc(sizeof(tail))
T->data=0
T->front=NULL
T->rear=NULL
}
if(!P) return OK
T->rear->next=P
T->rear=P
if(!(T->front)) T->front=P
return OK
}
status insertdatatail(mappath &T,int a)
{/*这个函数将一个元素插入队列中,其旦禅实这个函数是没有必要的,但是为了方便起见,还是写了个*/
if(T==NULL)
{
T=(mappath)malloc(sizeof(tail))
T->data=0
T->front=NULL
T->rear=NULL
map linshi=(map)malloc(sizeof(datatail))
linshi->data=a
linshi->next=NULL
T->front=linshi
T->rear=linshi
T->data=1
return OK
}
map linshi=(map)malloc(sizeof(datatail))
linshi->data=a
linshi->next=NULL
T->rear->next=linshi
T->rear=linshi
if(!(T->front)) T->front=linshi
T->data++
return OK
}
status deltail(mappath &T)
{/*因为对队列进行删除 *** 作的时候,基本上是没有什么条件,就是对front做一些相应的 *** 作就可以了
,所以他的函数列表也就比较少了*/
if(!T) return ERROR/*如果队列本来就是空的,那么就返回一个错误的信息*/
if(T->front==T->rear)
{/*如果队列只有一个元素,就执行下面的 *** 作,防止出现了错误*/
map linshi=T->front
free(linshi)
T->data=0
T->front=NULL
T->rear=NULL
return OK
}
map linshi=T->front
T->front=T->front->next
T->data--
free(linshi)
return OK
}
status puttail(mappath T)
{/*这个是对一个已经存在的队列进行输出*/
if(!T) return ERROR
printf("the tail'count is %d\n",T->data)
int count=T->datamap q=T->front
for(int i=0i<counti++)
{
printf("%d",q->data)
q=q->next
}
return OK
}
int main()
{
printf("hello,world!\n")
mappath q=NULLint count1=0int dataa=0
printf("please input a number to the count of tail\n")
scanf("%d",&count1)
for(int i=0i<count1i++)
{
printf("please input a number to tail\n")
scanf("%d",&dataa)
insertdatatail(q,dataa)
}
puttail(q)
deltail(q)
puttail(q)
return 0
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）