FIFO,LRU算法-操作系统代码

FIFO算法

实验代码：

#include

#define M 4 //物理页数

#define N 17 //需要调入的页数

typedef struct page

{

int num;

int time;

}Page; //物理页项，包括调入的页号和时间

Page b[M]; //4个物理页

int queue1[20],queue2[20],queue3[20]; //记录置换的页

int K=0,S=0,T=0; //置换页数组的标识

int pos=0;//记录存在最长时间项

void INIT(){

int i;

for(i=0;ib[i].num =-1;

b[i].time =0;

}

}

//取得内存中存在时间最久的位置

int GetMax(){

int max=-1;

int i;

for(i=0;iif(b[i].time > max){

max=b[i].time ;

pos=i;

}

}

return pos;

}

//检查物理内存是否已满,-1表满，其他不满

int Check(){

int i;

for(i=0;iif(b[i].num == -1)

return i;

}

return -1;

}

int Equation(int fold,Page *b)

{

int i;

for(i=0;i{

if(fold==b[i].num)

return i;

return -1;

}

}

//先进先出

void FIFO(int fold){

int i;

int a,b,c;

a=Equation(fold,b);

//页已存在

if(a != -1){}

//页不存在

else{

b=Check();

//内存还有空闲

if(b != -1){

b[b].num = fold;

}

//内存已满，需要置换

else {

c=GetMax();

b[c].num = fold;

b[c].time = 0;

}

queue1[K++]=fold;

}

for(i=0;iif(b[i].num != -1){

b[i].time ++;

}

}

}

void main()

{

int A[N];

int i;

INIT();

a[N]={1,0,1,0,2,4,1,0,0,8,7,5,4,3,2,3,4}

for(i=0;iFIFO( a[i],b);

}

printf(\"FIFO的\");

printf(\"调入队列为：\");

for(i=0;iprintf(\"%3d\

printf(\"\\n缺页次数为：%6d\\n缺页率：%16.6f\\n\\n\

}

时间片轮转算法

#include

#include

#include

#include

typedef struct node /**/

{

char name[10]; /*进程标识符*/

int prio; /*进程优先数*/

int round; /*进程时间轮转时间片*/

int cputime; /*进程占用CPU时间*/

int needtime; /*进程到完成还需要的时间*/

int count; /*计数器*/

char state; /*进程的状态*/

struct node *next; /*链指针*/

}PCB;

PCB *finish,*ready,*tail,*run; /*队列指针*/

int N; /*进程数*/

/*将就绪队列中的第一个进程投入运行*/

firstin()

{

run=ready; /*就绪队列头指针赋值给运行头指针*/

run->state='R'; /*进程状态变为运行态*/

ready=ready->next; /*就绪队列头指针后移到下一进程*/

}

/*标题输出函数*/

void prt1( )

{

/*输出标题*/

printf(\"name cputime needtime count round state\\n\");

}

/*进程PCB的输出*/

void prt2(PCB *q)

{

/*轮转法的输出*/

printf(\"%-8s%-8d%-8d%-6d%-5d %-c\\n\

q->cputime,q->needtime,q->count,q->round,q->state);

}

/*输出函数*/

void prt()

{

PCB *p;

if(run!=NULL) /*如果运行指针不空*/

prt2(run); /*输出当前正在运行的PCB*/

p=ready; /*输出就绪队列的PCB*/

while(p!=NULL)

{

prt2(p);

p=p->next;

}

p=finish; /*输出就完成队列的PCB*/

while(p!=NULL)

{

prt2(p);

p=p->next;

}

printf(\"Press any key to continue...\\n\");

_getch(); /*按任意键继续*/

prt1();

}

insert(PCB *p2) /*轮转法插入函数*/

{

tail->next=p2;

tail=p2;

p2->next=NULL;

}

void creat() /*轮转法创建进程PCB*/

{

PCB *p;

int i,time;

char na[10];

ready=NULL; /*就绪队列头指针*/

finish=NULL; /*完成队列头指针*/

run=NULL; /*运行队列指针*/

printf(\"Enter name and time of round process \\n\");

for(i=1;i<=N;i++)

{

p=malloc(sizeof(PCB));

scanf(\"%s\

scanf(\"%d\

strcpy(p->name,na);

p->cputime=0;

p->needtime=time;

p->count=0; /*计数器*/

p->state='w';

p->round=2; /*时间片*/

if(ready!=NULL)

insert(p);

else

{

p->next=ready;

ready=p;

tail=p;

}

}

printf(\" output of round\\n\");

printf(\"****************************************\\n\");

prt1();

prt(); /*输出进程PCB信息*/

run=ready; /*将就绪队列的第一个进程投入运行*/

ready=ready->next;

run->state='R';

}

roundrun() /*时间片轮转法*/

{

while(run!=NULL)

{

run->cputime=run->cputime+1;

run->needtime=run->needtime-1;

run->count=run->count+1;

/*运行完将其变为完成态，插入完成队列*/

if(run->needtime==0)

{

run->next=finish;

finish=run;

run->state='F';

run=NULL;

if(ready!=NULL)

/*就绪队列不空，将第一个进程投入进行*/

firstin();

}

else

if(run->count==run->round) /*如果时间片到*/

{

run->count=0; /*计数器置0*/

if(ready!=NULL) /*如果就绪队列不空

*/

{

/*将进程插入到就绪队列

中等待轮转*/

run->state='W';

insert(run);

/*将就绪队列的第一个进

程投入运行*/

firstin();

}

}

prt(); /*输出进程信息*/

}

}

/*主函数*/

main()

{

printf(\"Enter process number\\n\");

scanf(\"%d\ /*输入进程数*/

creat(); /*轮转法*/

roundrun();

}