实验一 进程状态转换模拟
流程图
代码
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <error.h>
#include <wait.h>
#include <unistd.h>
#define MAXSIZE 50
#define ERROR -99
#define MSIZE 100
typedef struct
{
char name; //进程名字
int msize; //占用内存大小
int time; //运行时间
int priority; //进程优先级
}process;
typedef process QElemType;
typedef struct //队列
{
QElemType data[MAXSIZE];
int front;
int rear;
int size;
}Queue;
Queue *createQ() //创建队列
{
Queue *q = (Queue*)malloc(sizeof(Queue));
q->front = -1;
q->rear = -1;
q->size = 0;
return q;
}
void addQ(Queue *q,QElemType e) //入队列
{
if(((q->rear+1)%MAXSIZE)==q->front)
{
printf("队列已满\n");
return;
}
q->rear++;
q->size++;
q->data[q->rear] = e;
int n=q->front+1;
for(int i=n;i<=q->rear;i++) //按照队列中进程的优先级顺序调整
{
for(int j =n;j<=q->rear-1-i;j++)
{
if((q->data[j]).priority > (q->data[j+1]).priority) //保证优先级低的在后面
{
process tmp;
tmp=q->data[j];
q->data[j]=q->data[j+1];
q->data[j+1]=tmp;
}
}
}
}
QElemType deleteQ(Queue *q) //出队列（队头出）
{
q->front++;
q->size--;
return q->data[q->front];
}
int isempty(Queue *q) //判断一个队列是否为空
{
if(q->size==0)
return 1;
else
return 0;
}
void deleteq(Queue *q,QElemType a) //删除队列中的某元素
{
int flag=0;
if(isempty(q)==1)
printf("此队列为空！\n");
else
{
for(int i=0;i<=q->rear;i++) //队列不为空时在其中循环查找，找到就删除该进程
{
if(q->data[i].name==a.name)
{
for(int j=i;j<q->rear;j++)
{
q->data[j]=q->data[j+1];
}
q->rear--;
q->size--;
flag=1;
break;
}
}
if(flag==0)
printf("队列中没有该进程！\n");
}
}
void printQ(Queue *q) //打印队列中的元素
{
if(isempty(q))
{
printf("空");
}
else{
int n=q->front+1;
for(int i=n;i<=q->rear;i++)
{
printf("%c ",(q->data[i]).name);
}
}
}
void Create(Queue *newq,Queue *ready,Queue *run,Queue *blocked,int &allsize) //新建一个进程
{
process p;
char n;
printf("请输入所创建进程名字（字母）：");
scanf("%c",&p.name);
printf("请输入进程占用内存大小（整数）：");
scanf("%d",&p.msize);
printf("请输入进程运行时间（整数）：");
scanf("%d",&p.time);
printf("请输入进程优先级（整数）：");
scanf("%d",&p.priority);
allsize=allsize+p.msize;
if(allsize >MSIZE) //超过内存限制需要在新建队列中等待
{
printf("\n");
printf("该进程需要等待之后才能提交\n");
printf("\n");
addQ(newq,p);
allsize=allsize-p.msize;
}
else
{
addQ(ready,p);
}
printf("转换后状态为：\n");
printf("Running: ");
printQ(run);
printf("\n");
printf("Ready: ");
printQ(ready);
printf("\n");
printf("Blocked: ");
printQ(blocked);
printf("\n");
printf("New: ");
printQ(newq);
printf("\n");
printf("\n");
}
void Timeout(Queue *newq,Queue *ready,Queue *run,Queue *blocked) //时间片超时
{
process x;
if (isempty(run)!=1) //运行队列不为空
{
x = deleteQ(run); //将运行队列中的进程移到就绪队列中
addQ(ready, x);
printf("进程%c 超时 Running->Ready\n",x.name);
}
else //运行为空
{
printf("\n");
printf("当前无运行进程！\n");
printf("\n");
}
printf("转换后状态为：\n");
printf("Running: ");
printQ(run);
printf("\n");
printf("Ready: ");
printQ(ready);
printf("\n");
printf("Blocked: ");
printQ(blocked);
printf("\n");
printf("New: ");
printQ(newq);
printf("\n");
printf("\n");
}
void EventWait(Queue *newq,Queue *ready,Queue *run,Queue *blocked) //进程阻塞
{
process x;
if (isempty(run)!=1) //运行队列不为空
{
x = deleteQ(run);
addQ(blocked, x);
printf("进程%c 被阻塞 Running->Blocked\n",x.name);
}
else //运行为空
{
printf("\n");
printf("当前无运行进程！\n");
printf("\n");
}
printf("转换后状态为：\n");
printf("Running: ");
printQ(run);
printf("\n");
printf("Ready: ");
printQ(ready);
printf("\n");
printf("Blocked: ");
printQ(blocked);
printf("\n");
printf("New: ");
printQ(newq);
printf("\n");
printf("\n");
}
void EventOccur(Queue *newq,Queue *ready,Queue *run,Queue *blocked) //唤醒进程
{
process x;
char c;
int flag=0;
if (isempty(blocked)!=1) //有进程在阻塞状态
{
printf("请输入要唤醒的进程名字：");//需不需要给出唤醒的进程
scanf("%c",&c);
for(int i=blocked->front+1;i<=blocked->rear;i++)
{
if(blocked->data[i].name==c)
{
x=blocked->data[i];
deleteq(blocked,x);
addQ(ready, x);
flag=1;
}
}
if(flag!=1)
printf("未找到该进程\n");
}
else
{
printf("\n");
printf("当前无进程在阻塞状态！\n");
printf("\n");
}
printf("转换后状态为：\n");
printf("Running: ");
printQ(run);
printf("\n");
printf("Ready: ");
printQ(ready);
printf("\n");
printf("Blocked: ");
printQ(blocked);
printf("\n");
printf("New: ");
printQ(newq);
printf("\n");
printf("\n");
}
void Release(Queue *newq,Queue *ready,Queue *run,Queue *blocked,int &allsize) //释放进程
{
process x,y;
if (isempty(run) == 0) //运行不为空
{
x=deleteQ(run);
printf("进程%c 释放\n",x.name);
allsize = allsize - x.msize;
if ((allsize < MSIZE)&&(isempty(newq) == 0)) //有足够内存且新建不为空
{
int m=newq->size;
for(int i=0;i<m;i++) //在新建队列中循环找到并调入能够满足内存条件的进程
{
y=newq->data[i];
if((allsize+y.msize)<=MSIZE)
{
deleteq(newq,y); //从新建队列中删除该进程
addQ(ready, y); //将该进程加入就绪队列
allsize = allsize+y.msize; //加上占用内存
}
}
}
}
else
{
printf("\n");
printf("当前无运行进程！");
printf("\n");
}
printf("转换后状态为：\n");
printf("Running: ");
printQ(run);
printf("\n");
printf("Ready: ");
printQ(ready);
printf("\n");
printf("Blocked: ");
printQ(blocked);
printf("\n");
printf("New: ");
printQ(newq);
printf("\n");
printf("\n");
}
void Dispatch(Queue *newq,Queue *ready,Queue *run,Queue *blocked)
{
process x;
if(isempty(ready))
{
printf("\n");
printf("无进程在就绪态\n");
printf("\n");
}
else{
if(isempty(run)) //没有进程在运行
{
x=deleteQ(ready);
addQ(run,x);
printf("\n");
printf("调度成功！进程%c Ready->Running \n",x.name);
printf("\n");
}
else //有进程在运行
{
printf("\n");
printf("有进程在运行！无法完成调度！\n");
printf("\n");
}
}
printf("转换后状态为：\n");
printf("Running: ");
printQ(run);
printf("\n");
printf("Ready: ");
printQ(ready);
printf("\n");
printf("Blocked: ");
printQ(blocked);
printf("\n");
printf("New: ");
printQ(newq);
printf("\n");
printf("\n");
}
int main()
{
int a, size_now, pnum = 9;
Queue* run = createQ(); //运行态
Queue* ready = createQ(); //就绪态
Queue* blocked = createQ(); //阻塞态
Queue* newq = createQ(); //创建新进程，若内存已满，则存入
process pro[30];
pro[0].name='A';
pro[0].msize=10;
pro[0].priority=1;
pro[0].time = 3;
pro[1].name='B';
pro[1].msize=15;
pro[1].priority=1;
pro[1].time = 5;
pro[2].name='C';
pro[2].msize=10;
pro[2].priority=1;
pro[2].time = 3;
pro[3].name='D';
pro[3].msize=15;
pro[3].priority=1;
pro[3].time = 5;
pro[4].name='E';
pro[4].msize=25;
pro[4].priority=1;
pro[4].time = 5;
pro[5].name='F';
pro[5].msize=25;
pro[5].priority=1;
pro[5].time = 5;
addQ(run, pro[0]);
addQ(ready, pro[1]);
addQ(ready, pro[2]);
addQ(ready, pro[3]);
addQ(ready, pro[4]);
addQ(ready, pro[5]);
size_now = 100;
printf("当前进程状态：\n");
printf("Running: ");
printQ(run);
printf("\n");
printf("Ready: ");
printQ(ready);
printf("\n");
printf("Blocked: ");
printQ(blocked);
printf("\n");
printf("New: ");
printQ(newq);
printf("\n");
printf("\n");
while (1) {
printf("请选择你的操作：\n");
printf("1 Create\n");
printf("2 Dispatch: Ready->Running\n");
printf("3 Timeout: Running->Ready\n");
printf("4 EventWait: Running->Blocked\n");
printf("5 EventOccurs: Blocked->Ready\n");
printf("6 Release\n");
printf("0 Exit \n");
scanf("%d", &a);
getchar();
switch (a) {
case 1:Create(newq,ready,run,blocked,size_now); pnum++; break;
case 2:Dispatch(newq,ready,run,blocked); break;
case 3:Timeout(newq,ready,run,blocked); break;
case 4:EventWait(newq,ready,run,blocked); break;
case 5:EventOccur(newq,ready,run,blocked); break;
case 6:Release(newq,ready,run,blocked, size_now); break;
case 0:exit(0);
default:printf("请输入正确操作！\n\n");
}
}
return 0;
}
运行结果
初始界面
若剩余内存不能满足创建的新进程所需，则将新进程放入New队列
若有内存释放且释放后剩余内存能满足New对列中进程所需，将进程调入Ready队列
调度进程：
时间片用完：
调度下一个进程
进程阻塞：
发生阻塞后调度新的进程
事件发生：
实验二 生产者消费者问题模拟
流程图
代码
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <error.h>
#include <wait.h>
#include <unistd.h>
#define Buffersize 8
#define MAXSIZE 100
struct Buffer{ //缓冲区
int pipe[Buffersize]; //缓冲区整形数组
int write; //写指针
int read; //读指针
}buf;
typedef struct
{
char name; //进程名
int num; //进程编号
}process;
typedef process QElemType;
typedef struct //队列
{
QElemType data[MAXSIZE];
int front;
int rear;
int size;
}Queue;
Queue *createQ() //创建队列
{
Queue *q = (Queue*)malloc(sizeof(Queue));
q->front = -1;
q->rear = -1;
q->size = 0;
return q;
}
void addQ(Queue *q,QElemType e) //入队列
{
if(((q->rear+1)%MAXSIZE)==q->front)
{
printf("full!\n");
return;
}
q->rear++;
q->size++;
q->data[q->rear] = e;
}
QElemType deleteQ(Queue *q) //出队列（队头出）
{
q->front++;
q->size--;
return q->data[q->front];
}
int isempty(Queue *q) //判断一个队列是否为空
{
if(q->size==0)
return 1;
else
return 0;
}
void printQ(Queue *q) //打印队列中的元素
{
if(isempty(q))
{
printf("empty");
}
else{
int n=q->front+1;
for(int i=n;i<=q->rear;i++)
{
printf("%c%d ",(q->data[i]).name,(q->data[i]).num);
}
}
}
int full = 0; //full信号量
int empty = Buffersize; //empty信号量
int pn=0; //生产者总数
int cn=0; //消费者总数
Queue* Waitc=createQ(); //等待的消费者队列
Queue* Waitp=createQ(); //等待的生产者队列
void producer()
{
pn++;
empty--;
if(empty<0) //缓冲区无空位
{
process p;
p.name='p';
p.num=pn;
addQ(Waitp,p); //加入生产者等待队列
printf("Buffer is full! producer%d need to wait.\n",pn);
}
else //有空位
{
if(Waitc->size!=0) //是否有等待的消费者
{
process c;
c=deleteQ(Waitc);
printf("product %d is consumed\n",pn);
empty++;
}
else //无消费者等待
{
if(buf.write<=Buffersize-1) //写指针未超
{
buf.pipe[buf.write]=pn;
buf.write++;
}
else //写指针超过了
{
buf.write=0; //重置写指针到头
buf.pipe[buf.write]=pn;
buf.write++;
}
}
full++;
}
}
void consumer()
{
cn++;
full--;
if(full<0) //缓冲区中无产品
{
process c;
c.name='c';
c.num=cn;
addQ(Waitc,c); //加入消费者者等待队列
printf("Buffer is empty! consumer%d need to wait.\n",cn);
}
else //缓冲区中有产品
{
if(buf.read<=Buffersize-1) //读指针未超
{
int x=buf.pipe[buf.read];
buf.pipe[buf.read]=0; //该产品被消费
buf.read++;
printf("product %d is consumed\n",x);
}
else if(buf.read>Buffersize-1) //读指针超过了
{
buf.read=0; //重置写指针到头
int x=buf.pipe[buf.read];
buf.pipe[buf.read]=0; //该产品被消费
buf.read++;
printf("product %d is consumed\n",x);
}
empty++;
if(Waitp->size!=0) //有空位了且有等待的生产者
{
process p;
p=deleteQ(Waitp);
if(buf.write==Buffersize) //如果写指针超过则重置
buf.write=0;
buf.pipe[buf.write]=p.num;
buf.write++;
full++;
}
}
}
void show()
{
int a;
for(a=0;a<Buffersize;a++)
{
printf("|%d",buf.pipe[a]);
}
printf("\n");
printf("wait producers:");
printQ(Waitp);
printf("\n");
printf("wait consumers:");
printQ(Waitc);
printf("\n");
printf("empty:%d",empty);
printf("\n");
printf("full:%d",full);
printf("\n");
}
int main()
{
char c;
printf("Press 'p' to run producer.\nPress 'c' to run consumer.\n");
printf("Press 'e' to exit.\n");
int a=0;
while(1)
{
scanf("%c",&c);
getchar();
if(c=='p')
{
producer();
show();
}
else if(c=='c')
{
consumer();
show();
}
else if(c=='e')
{
exit(0);
}
else
printf("error,input again!\n");
}
return 0;
}
运行结果
初始界面：
执行生产者进程：
执行消费者进程：
缓冲区为空时，消费者进程等待，生产者进程生产出产品后，消费者进程再继续执行
缓冲区满时，生产者进程等待，消费者进程消费产品后，生产者进程再继续执行
实验三 进程的管道通信
流程图
代码
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <error.h>
#include <sys/wait.h>
#include <unistd.h>
int main(){
int p1,p2,p3,fd[2];
char outpipe[40],str[40];
pipe(fd);
while((p1=fork())==-1); //子进程p1创建失败
if(p1==0){ //创建子进程p1成功
lockf(fd[1],1,0); //管道加锁
sprintf(outpipe,"Child process P1 is sending messages!\n"); //向outpipe中写入字符串
write(fd[1],outpipe,40); //将outpipe中的内容写入管道
sleep(2);
lockf(fd[1],0,0); //管道解锁
exit(0); //子进程结束
}
while((p2=fork())==-1);
if(p2==0){
lockf(fd[1],1,0);
sprintf(outpipe,"Child process P2 is sending messages!\n");
write(fd[1],outpipe,40);
sleep(2);
lockf(fd[1],0,0);
exit(0);
}
while((p3=fork())==-1);
if(p3==0){
lockf(fd[1],1,0);
sprintf(outpipe,"Child process P3 is sending messages!\n");
write(fd[1],outpipe,40);
sleep(2);
lockf(fd[1],0,0);
exit(0);
}
wait(0);
if(read(fd[0],str,40)==-1) //从管道中读出数据
printf("Can't read pipe!\n"); //读取数据失败
else printf("%s\n",str); //成功读取出则打印出来
wait(0);
if(read(fd[0],str,40)==-1)
printf("Can't read pipe!\n");
else printf("%s\n",str);
wait(0);
if(read(fd[0],str,40)==-1)
printf("Can't read pipe!\n");
else printf("%s\n",str);
exit(0); //父进程结束
}
拓展点1：
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <error.h>
#include <sys/wait.h>
#include <unistd.h>
int main(){
int p1,p2,p3,fd[2];
char str[50],buf[50];
pipe(fd);
if(pipe(fd)<0)
printf("pipe error\n");
p1=fork();
if(p1<0)
printf("p1 error\n");
else if(p1>0)
{
p2=fork(); //创建子进程p2
if(p2<0)
printf("p2 error\n");
else if(p2>0)
{
p3=fork();
if(p3<0)
printf("p3 error\n");
else if(p3>0) //p1,p2,p3均大于零，为父进程
{
lockf(fd[1],1,0); //管道上锁
sprintf(buf,"The father process is sending messages");
write(fd[1],buf,50); //父进程向管道中写入信息
lockf(fd[1],0,0); //管道解锁
}
else
{
if(read(fd[0],str,50)==-1) //从管道中读出数据
printf("p3 can't read the pipe!\n"); //读取数据失败
else
printf("p3 get the message:%s \n",str); //p3=0,p3进程读取父进程发送数据
exit(0);
}
}
else
{
if(read(fd[0],str,50)==-1) //从管道中读出数据
printf("p2 can't read the pipe!\n"); //读取数据失败
else
printf("p2 get the message:%s\n",str); //p2=0,p2进程读取父进程发送数据
exit(0);
}
}
else //p1=0 p1子进程
{
if(read(fd[0],str,50)==-1) //从管道中读出数据
printf("p1 can't read the pipe!\n"); //读取数据失败
else
printf("p1 get the message:%s\n",str); //p1=0,p1进程读取父进程发送数据
exit(0);
}
wait(0);
exit(0); //父进程结束
}
运行结果
拓展点1：
思考题
① 指出父进程与两个子进程并发执行的顺序，并说明原因。
子进程先执行，然后父进程才能够执行。父进程首先创建子进程p1，然后执行子进程p1。在执行子进程p1之后，父进程创建子进程p2，执行子进程p2。之后，父进程执行，程序结束。即先执行子进程，再执行父进程。这是进程的同步机制决定的，因为只有在子进程将信息写入管道后，父进程才能读取。否则，父进程调用wait()系统将自己阻塞，将处理机交给子进程。直到子进程将数据写入管道之后唤醒。
② 若不对管道加以互斥控制，会有什么后果？
管道互斥控制是为了防止两个子进程对管道资源进行争夺而产生信息丢失或覆盖。如果没有互斥控制，那么可能子进程写入的信息还没有来得及被父进程读出，另外的子进程又写入了新的信息，这样之前子进程写入的信息就被覆盖了，父进程也没有读到上一个子进程传递的信息，这就造成了信息丢失与覆盖。因此，进程之间的互斥表现在以下事实：当子进程写入管道时，另一个想要写入管道的子进程必须等待。
③ 说明你是如何实现父子进程之间的同步的。
进程之间的同步要求，父进程在读取之前确定管道中是否有数据，没有则会阻塞自身。这可以通过父进程中调用wait()函数来实现。当子进程完成后，再执行父进程，这样就能保证在管道中有子进程写入的数据了。子进程在进行写入之前需要确定父进程是否已读取管道中的数据，否则的话就无法写入或阻塞自身。这可以通过进程之间互斥来实现，每个子进程在执行写入之前都对管道进行加锁，这样就可以保证在同一个时刻只有一个子进程向管道中写入数据。子进程在将数据写入管道后调用sleep()，休眠一段时间，便于父进程从管道中读取数据。然后再创建执行下一个子进程，下一个子进程才能够有机会向管道中写入数据。这样就可以实现子进程在写入之前确定父进程已读取管道中的数据，否则它无法写入或阻塞自身。
实验四 页面置换算法
流程图
代码
#include<stdio.h>
#include<sys/types.h>
#include<stdlib.h>
#include<sys/stat.h>
#include<fcntl.h>
#include<error.h>
#include<wait.h>
#include<unistd.h>
#include<time.h>
struct one_frame {
int page_no; //页面号
int flag;
};
const int frame_num=6; //进程分配的最大内存页面数
int Access_series[12]; //访问序列
int diseffectF = 0; //FIFO算法的缺页次数
int diseffectL = 0; //LRU算法的缺页次数
struct one_frame M_Frame[frame_num]; //进程分配页面使用情况
int main()
{
srand((unsigned) time(NULL));
int p1, p2;
int flagF = 0; //FIFO是否找到页面标志
int flagL = 0; //LRU是否找到页面标志
float r;
for (int i = 0; i<frame_num; i++)
M_Frame[i].page_no = -1; //初始化进程分配页数为-1，表示没有页面占用
printf("Frame: ");
for (int i = 0; i<12; i++){
Access_series[i] = rand() % 12 + 1; //通过随机数产生页面访问序列
printf("%d ", Access_series[i]);
}
printf("\n\n");
while ((p1 = fork()) == -1); //创建子进程p1
if (p1 == 0) //进入p1子进程
{
int framenow=0; //现在已经分配的物理页面数
int readframe; //读取的页面号
for (int i = 0; i<12; i++)
{
for (int j = 0; j<12; j++)
printf("%d ", Access_series[j]);
printf("\n");
readframe = Access_series[i]; //读入访问页面号
printf("read the frame %d\n",readframe);
for (int j=0; j<framenow; j++) //查找该页面是否已分配
{
if (readframe != M_Frame[j].page_no)
continue;
else if(readframe == M_Frame[j].page_no)
{
printf("Have found the frame!\n"); //命中
printf("The memory:\n");
for (int k = 0; k<framenow; k++) //显示当前分配页面使用情况
printf("%d ", M_Frame[k].page_no);
printf("\n\n");
flagF = 1;
break;
}
}
if (flagF == 0)
{
diseffectF++; //出现缺页次数加1
if (framenow < frame_num) //还有剩余的内存可分配
{
M_Frame[framenow].page_no = readframe; //为该页面分配内存空间
M_Frame[framenow].flag = 1;
framenow++;
printf("Diseffect %d times, caused by frame %d\n", diseffectF,readframe);
printf("The memory:\n");
for (int j = 0; j<framenow; j++)
printf("%d ", M_Frame[j].page_no);
printf("\n\n");
}
else //分配物理页面数已满
{
printf("The memory is full, frame %d out\n", M_Frame[0].page_no); //淘汰最早进入的页面
for (int j =1; j<frame_num; j++) //后面的页面一次向前移动一位
M_Frame[j-1]=M_Frame[j];
M_Frame[frame_num-1].page_no = readframe; //让读到的页面号分配到最后
printf("Diseffect %d times, caused by frame %d\n", diseffectF,readframe);
printf("The memory:\n");
for (int j = 0; j<framenow; j++)
printf("%d ", M_Frame[j].page_no);
printf("\n\n");
}
}
flagF = 0;
}
r = diseffectF / 12.0; //计算缺页率
printf("FIFO: diseffect rate %f\n", r);
printf("FIFO: hit rate %f\n\n", 1-r);
exit(0);
}
wait(0);
for (int i = 0; i<frame_num; i++) //重置进程分配页数
M_Frame[i].page_no = -1;
while ((p2 = fork()) == -1); //创建子进程p2
if (p2 == 0)
{
int framenow=0; //现在已经分配的物理页面数
int readframe; //读取的页面号
for (int i=0; i<12; i++)
{
for (int j=0; j<12; j++)
printf("%d ", Access_series[j]);
printf("\n");
readframe = Access_series[i]; //读入访问页面号
printf("read the frame %d\n",readframe);
for (int j=0; j<framenow; j++)
{
if (readframe!= M_Frame[j].page_no) //查找该页面是否已分配
continue;
else if(readframe == M_Frame[j].page_no)
{
printf("Have found the frame!\n"); //命中
for (int k = j+1; k<framenow; k++) //进行移位，让最新被访问的在最后面
M_Frame[k-1].page_no = M_Frame[k].page_no;
M_Frame[framenow - 1].page_no = readframe;
printf("The memory:\n");
for (int k = 0; k<framenow; k++)
printf("%d ", M_Frame[k].page_no);
printf("\n\n");
flagL = 1;
break;
}
}
if (flagL == 0)
{
diseffectL++; //缺页次数加1
if (framenow<frame_num) //物理页面还没有分配完
{
M_Frame[framenow].page_no = readframe; //为该页面分配内存空间
M_Frame[framenow].flag = 1;
framenow++;
printf("Diseffect %d times, caused by frame %d\n", diseffectL,readframe);
printf("The memory:\n");
for (int k = 0; k<framenow; k++)
printf("%d ", M_Frame[k].page_no);
printf("\n\n");
}
else
{ //分配物理页面数已满
printf("The memory is full, frame %d out\n", M_Frame[0].page_no); //淘汰最近最久未使用的页面
for (int j = 1; j<frame_num; j++) //将页面进行移位
M_Frame[j - 1].page_no = M_Frame[j].page_no;
M_Frame[frame_num - 1].page_no = readframe; //最后一项放入刚读入的页面
printf("Diseffect %d times, caused by frame %d\n", diseffectL,readframe);
printf("The memory:\n");
for (int k = 0; k<framenow; k++)
printf("%d ", M_Frame[k].page_no);
printf("\n\n");
}
}
flagL = 0;
}
r = diseffectL / 12.0; //统计失效率
printf("LRU: diseffect rate %f\n", r);
printf("LRU: hit rate %f\n\n", 1-r);
exit(0);
}
wait(0);
return 0;
}
运行结果
FIFO:
缺页率和命中率：
LUR:
缺页率和命中率：
思考题
①父进程、子进程之间的并发执行过程。
父进程先创建子进程p1，再执行子进程p1。子进程p1执行结束父进程继续执行，创建子进程p2，再执行子进程p2，父进程等待子进程执行结束继续执行，程序结束。
②通过完成实验，根据你的体会，阐述虚拟存储器的原理。
虚拟存储的基本原理：在程序装入时，不必将其全部读入到内存，而只需将当前需要执行的部分页或段读入到内存，就可让程序开始执行。在程序执行过程中，如果需执行的指令或访问的数据尚未在内存（称为缺页或缺段），则由处理器通知操作系统将相应的页或段调入到内存，然后继续执行程序。另一方面，操作系统将内存中暂时不使用的页或段调出保存在外存上，从而腾出空间存放将要装入的程序以及将要调入的页或段。只需程序所需的一部分在内存就可执行。
③写出FIFO算法中出现Belady现象的内存页面访问序列。
页面访问序列：1,2,3,4,1,2,5,1,2,3,4,5
如果在内存中分配3个页面，12次访问页面时会出现9次缺页
如果在内存中分配4个页面，12次访问页面时会出现10次缺页
