操作系统实验答案

2023-04-18 来源：易榕旅网

部分实验答案

第三部分操作系统实验指导

实验3 指导

[实验内容]

1．进程的创建

〈任务〉

编写一段程序，使用系统调用fork( )创建两个子进程。当此程序运行时，在系统中有一个父进程和两个子进程活动。让每一个进程在屏幕上显示一个字符；父进程显示字符“a”，子进程分别显示字符“b”和“c”。试观察记录屏幕上的显示结果，并分析原因。

〈程序〉

#include

main()

{

int p1,p2;

if(p1=fork()) /*子进程创建成功*/

putchar('b');

else

{

if(p2=fork()) /*子进程创建成功*/

putchar('c');

else putchar('a'); /*父进程执行*/

}

<运行结果>

bca(有时会出现abc的任意的排列)

分析：从进程执行并发来看，输出abc的排列都是有可能的。

原因：fork()创建进程所需的时间虽然可能多于输出一个字符的时间，但各个进程的时间片的获得却不是一定是顺序的，所以输出abc的排列都是有可能的。

2．进程的控制

<任务>

修改已编写好的程序，将每个程序的输出由单个字符改为一句话，再观察程序执行时屏幕上出现的现象，并分析其原因。如果在程序中使用系统调用lockf()来给每个程序加锁，可以实现进程之间的互斥，观察并分析出现的现象。

〈程序1〉

#include

main()

{

int p1,p2,i;

if(p1=fork())

{

for(i=0;i<500;i++)

printf(\"parent%d\\n\

wait(0); /* 保证在子进程终止前，父进程不会终止*/

exit(0);

}

else

{

if(p2=fork())

{

for(i=0;i<500;i++)

printf(\"son %d\\n\

wait(0); /* 保证在子进程终止前，父进程不会终止*/

exit(0); /*向父进程信号0且该进程推出*/

}

else

{

for(i=0;i<500;i++)

printf(“grandchild %d\\n\

exit(0);

}

〈运行结果〉

parent….

son…

grandchild…

或grandchild

…son

…grandchild

…son

…parent

分析：由于函数printf()输出的字符串之间不会被中断，因此,每个字符串内部的字符顺序输出时不变。但是 , 由于进程并发执行时的调度顺序和父子进程的抢占处理机问题，输出字符串的顺序和先后随着执行的不同而发生变化。这与打印单字符的结果相同。

〈程序2〉

#include

main()

{

int p1,p2,i;

if(p1=fork())

{

lockf(1,1,0);

for(i=0;i<500;i++)

printf(\"parent %d\\n\

lockf(1,0,0);

wait(0); /* 保证在子进程终止前，父进程不会终止*/

exit(0);

}

else

{

if(p2=fork())

{

lockf(1,1,0);

for(i=0;i<500;i++)

printf(\"son %d\\n\

lockf(1,0,0);

wait(0); /* 保证在子进程终止前，父进程不会终止*/

exit(0);

}

else

{

lockf(1,1,0);

for(i=0;i<500;i++)

printf(\"daughter %d\\n\

lockf(1,0,0);

exit(0);

}

<运行结果〉

输出parent块,son块,grandchild块的顺序可能不同，但是每个块的输出过程不会被打断。

分析：因为上述程序执行时，lockf(1,1,0)锁定标准输出设备，lockf(1,0,0)解锁标准输出设备，在lockf(1,1,0)与lockf(1,0,0)中间的for循环输出不会被中断，加锁与不加锁效果不相同。

3．软中断通信

〈任务1〉

编制一段程序，使用系统调用fork()创建两个子进程，再用系统调用signal()让父进程捕捉键盘上来的中断信号（即按ctrl+c键），当捕捉到中断信号后，父进程用系统调用kill()向两个子进程发出信号，子进程捕捉到信号后，分别输出下列信息后终止：

child process1 is killed by parent!

child process2 is killed by parent!

父进程等待两个子进程终止后，输出以下信息后终止：

parent process is killed!

<程序流程图>

〈程序〉

#include

void waiting(),stop(),alarming();

int wait_mark;

main()

{

int p1,p2;

if(p1=fork()) /*创建子进程p1*/

{

if(p2=fork()) /*创建子进程p2*/

{

wait_mark=1;

signal(SIGINT,stop); /*接收到^c信号，转stop*/

signal(SIGALRM,alarming);/*接受SIGALRM

waiting();

kill(p1,16); /*向p1发软中断信号16*/

kill(p2,17); /*向p2发软中断信号17*/

wait(0); /*同步*/

wait(0);

printf(\"parent process is killed!\\n\");

exit(0);

}

else

{

wait_mark=1;

signal(17,stop);

signal(SIGINT,SIG_IGN); /*忽略 ^c信号*/

while (wait_mark!=0);

lockf(1,1,0);

printf(\"child process2 is killed by parent!\\n\");

lockf(1,0,0);

exit(0);

}

else

{

wait_mark=1;

signal(16,stop);

signal(SIGINT,SIG_IGN); /*忽略^c信号*/

while (wait_mark!=0)

lockf(1,1,0);

printf(\"child process1 is killed by parent!\\n\");

lockf(1,0,0);

exit(0);

}

void waiting()

{

sleep(5);

if (wait_mark!=0)

kill(getpid(),SIGALRM);

}

void alarming()

{

wait_mark=0;

}

void stop()

{

wait_mark=0;

}

<运行结果>

不做任何操作等待五秒钟父进程回在子进程县推出后退出，并打印退出的顺序；或者点击ctrl+C后程序退出并打印退出的顺序。

〈任务2〉

在上面的任务1中，增加语句signal(SIGINT,SIG_IGN)和语句signal(SIGQUIT,SIG_IGN)，观察执行结果，并分析原因。这里，signal(SIGINT,SIG_IGN)和signal(SIGQUIT,SIG_IGN)分别为忽略键信号以及忽略中断信号。

<程序>

#include

int pid1,pid2;

int EndFlag=0;

int pf1=0;

int pf2=0;

void IntDelete()

{

kill(pid1,16);

kill(pid2,17);

}

void Int1()

{

printf(\"child process 1 is killed !by parent\\n\");

exit(0);

}

void Int2()

{

printf(\"child process 2 is killed !by parent\\n\");

exit(0);

}

main()

{

int exitpid;

if(pid1=fork())

{

if(pid2=fork())

{

signal(SIGINT,IntDelete);

waitpid(-1,&exitpid,0);

printf(\"parent process is killed\\n\");

exit(0);

}

else

{

signal(SIGINT,SIG_IGN);

signal(17,Int2);

pause();

}

else

{

signal(SIGINT,SIG_IGN);

signal(16,Int1);

pause();

}

〈运行结果〉

请读者将上述程序输入计算机后，执行并观察。

3．进程的管道通信

〈任务〉

编制一段程序，实现进程的管道通信。使用系统调用pipe()建立一条管道线。两个子进程p1和p2分别向通道个写一句话：

child1 process is sending message!

child2 process is sending message!

而父进程则从管道中读出来自两个进程的信息，显示在屏幕上。

〈程序〉

#include

int pid1,pid2;

main( )

{

int fd[2];

char outpipe[100],inpipe[100];

pipe(fd); /*创建一个管道*/

while ((pid1=fork( ))==-1);

if(pid1==0)

{

lockf(fd[1],1,0);

sprintf(outpipe,\"child 1 process is sending message!\");

/*把串放入数组outpipe中*/

write(fd[1],outpipe,50); /*向管道写长为50字节的串*/

sleep(5); /*自我阻塞5秒*/

lockf(fd[1],0,0);

exit(0);

}

else

{

while((pid2=fork( ))==-1);

if(pid2==0)

{

lockf(fd[1],1,0); /*互斥*/

sprintf(outpipe,\"child 2 process is sending message!\");

write(fd[1],outpipe,50);

sleep(5);

lockf(fd[1],0,0);

exit(0);

}

else

{

wait(0); /*同步*/

read(fd[0],inpipe,50); /*从管道中读长为50字节的串*/

printf(\"%s\\n\

wait(0);

read(fd[0],inpipe,50);

printf(\"%s\\n\

exit(0);

}

〈运行结果〉

延迟5秒后显示:

child1 process is sending message!

再延迟5秒:

child2 process is sending message!

〈分析〉

请读者自行完成。

<思考>

1、程序中的sleep(5)起什么作用？

2、子进程1和2为什么也能对管道进行操作？

实验4指导

[实验内容]

1 消息的创建，发送和接收

〈任务〉

使用系统调用msgget( ), megsnd( ), msgrev( )及msgctl()编制一长度为1K的消息发送和接收的程序。

〈程序设计〉

（1）为了便于操作和观察结果，用一个程序为“引子”，先后fork( )两个子进程，SERVER和CLIENT，进行通信。

（2） SERVER端建立一个Key为75的消息队列，等待其他进程发来的消息。当遇到类型为1的消息，则作为结束信号，取消该队列，并退出SERVER 。SERVER每接收到一个消息后显示一句“(server)received”。

（3） CLIENT端使用Key为75的消息队列，先后发送类型从10到1的消息，然后退出。最后的一个消息，既是 SERVER端需要的结束信号。CLIENT每发送一条消息后显示一句“(client)sent”。

（4）父进程在 SERVER和 CLIENT均退出后结束。

〈程序〉

#include

#define MSGKEY 75 /*定义关键词MEGKEY*/

struct msgform /*消息结构*/

{

long mtype;

char mtexe[100]; /*文本长度*/

}msg;

int msgqid,i;

void CLIENT( )

{

int i;

msgqid=msgget(MSGKEY,0777|IPC_CREAT);

for(i=10;i>=1;i--)

{

msg.mtype=i;

printf(\"(client)sent\\n\");

msgsnd(msgqid,&msg,1030,0); /*发送消息msg入msgid消息队列*/

}

exit(0);

}

void SERVER( )

{

msgqid=msgget(MSGKEY,0777|IPC_CREAT); /*由关键字获得消息队列*/

{

msgrcv(msgqid,&msg,1030,0,0); /*从队列msgid接受消息msg*/

printf(\"(server)receive\\n\");

}while(msg.mtype!=1); /*消息类型为1时，释放队列*/

msgctl(msgqid, IPC_RMID,0);

}

main()

{

if(fork())

{

SERVER();

wait(0);

}

else CLIENT( );

}

<结果>

从理想的结果来说，应当是每当Client发送一个消息后，server接收该消息，Client再发送下一条。也就是说“(Client)sent”和“(server)received”的字样应该在屏幕上交替出现。实际的结果大多是，先由 Client 发送两条消息，然后Server接收一条消息。此后Client

Server交替发送和接收消息.最后一次接收两条消息. Client 和Server 分别发送和接收了10条消息,与预期设想一致

<分析>

message的传送和控制并不保证完全同步,当一个程序不再激活状态的时候,它完全可能继续睡眠,造成上面现象,在多次send message 后才 receive message.这一点有助于理解消息转送的实现机理.

2.共享存储区的创建,附接和断接

<任务>

使用系统调用shmget(),sgmat(),smgdt(),shmctl()编制一个与上述功能相同的程序.

<程序设计>

(1)为了便于操作和观察结果，用一个程序为“引子”，先后fork( )两个子进程，SERVER

和 CLIENT，进行通信。

(2)SERVER端建立一个KEY为75的共享区,并将第一个字节置为-1.作为数据空的标志.等待其他进程发来的消息.当该字节的值发生变化时,表示收到了该消息,进行处理.然后再次把它的值设为-1.如果遇到的值为0,则视为结束信号,取消该队列,并退出SERVER.SERVER每接收到一次数据后显示”(server)received”.

(3)CLIENT端建立一个为75的共享区,当共享取得第一个字节为-1时, Server端空闲,可发送

请求. CLIENT 随即填入9到0.期间等待Server端再次空闲.进行完这些操作后, CLIENT 退出.

CLIENT每发送一次数据后显示”(client)sent”.

(4)父进程在SERVER和CLIENT均退出后结束.

<程序>

#include

#define SHMKEY 75 /*定义共享区关键词*/

int shmid,i;

int *addr;

CLIENT()

{

int i;

shmid=shmget(SHMKEY,1024, 0777|IPC_CREAT); /*获取共享区，长度1024，关键词SHMKEY*/

addr=shmat(shmid,0,0); /*共享区起始地址为addr*/

for(i=9;i>=0;i--)

{

while(*addr!= -1); printf(\"(client)sent\\n\"); *addr=i; }

exit(0);

}

SERVER()

{

while(*addr = =-1);

/*打印（client）sent*/

/*把i赋给addr*/

printf(\"(server)received\\n%d\ /*服务进程使用共享区*/

if(*addr!=0)

*addr=-1;

} while(*addr);

wait(0);

shmctl(shmid,IPC_RMID,0);

}

main()

{

shmid=shmget(SHMKEY,1024,0777|IPC_CREAT); addr=shmat(shmid,0,0); *addr=-1;

if(fork())

{

/*创建共享区*/

/*共享区起始地址为addr*/

SERVER();

}

else

{

CLIENT();

}

<结果〉

运行的结果和预想的完全一样。但在运行的过程中，发现每当client发送一次数据后，server要等大约0.1秒才有响应。同样，之后client又需要等待大约0.1秒才发送下一个数据。

<分析〉

出现上述的应答延迟的现象是程序设计的问题。当client端发送了数据后，并没有任何措施通知server端数据已经发出，需要由client的查询才能感知。此时，client端并没有放弃系统的控制权，仍然占用CPU的时间片。只有当系统进行调度时，切换到了server进程，再进行应答。这个问题，也同样存在于server端到client的应答过程之中。

3 比较两种消息通信机制中的数据传输的时间

由于两种机制实现的机理和用处都不一样，难以直接进行时间上的比较。如果比较其性能，应更加全面的分析。

(1) 消息队列的建立比共享区的设立消耗的资源少.前者只是一个软件上设定的问题,后者需要

对硬件操作,实现内存的映像,当然控制起来比前者复杂.如果每次都重新进行队列或共享的建立,共享区的设立没有什么优势。

(2) 当消息队列和共享区建立好后,共享区的数据传输,受到了系统硬件的支持,不耗费多余的资

源;而消息传递,由软件进行控制和实现,需要消耗一定的CPU资源.从这个意义上讲,共享区更适合频繁和大量的数据传输.

(3) 消息的传递,自身就带有同步的控制.当等到消息的时候,进程进入睡眠状态,不再消耗CPU资

源.而共享队列如果不借助其他机制进行同步,接受数据的一方必须进行不断的查询,白白浪费了大量的CPU资源.可见消息方式的使用更加灵活.

实验5指导

[实验内容]

<任务>

设计一个虚拟存储区和内存工作区,并使用下列算法计算访问命中率.

（1）进先出的算法（FIFO）

（2）最近最少使用的算法（LRU）

（3）最佳淘汰算法(OPT)

（4）最少访问页面算法(LFU)

（5）最近最不经常使用算法(NUR)

命中率=(1-页面失效次数)/页地址流长度

<程序设计〉

本实验的程序设计基本上按照实验内容进行。即首先用srand()和rand()函数定义和产生指令序列，然后将指令序列变换成相应的页地址流，并针对不同的算法计算出相应的命中率。相关定义如下：

1 数据结构

(1)页面类型

typedef struct{

int pn,pfn,counter,time;

}pl-type;

其中pn 为页号,pfn为面号, counter为一个周期内访问该页面的次数, time为访问时间.

(2) 页面控制结构

pfc-struct{

int pn,pfn;

struct pfc_struct *next;

}

typedef struct pfc_struct pfc_type;

pfc_type pfc_struct[total_vp],*freepf_head,*busypf_head;

pfc_type *busypf_tail;

其中pfc[total_vp]定义用户进程虚页控制结构,

*freepf_head为空页面头的指针,

*busypf_head为忙页面头的指针,

*busypf_tail为忙页面尾的指针.

2．函数定义

（1）Void initialize( ):初始化函数,给每个相关的页面赋值.

（2）Void FIFO( ):计算使用FIFO算法时的命中率.

（3）Void LRU( ):计算使用LRU算法时的命中率.

（4）Void OPT( ):计算使用OPT算法时的命中率.

（5）Void LFU( ):计算使用LFU算法时的命中率.

（6）Void NUR( ):计算使用NUR算法时的命中率.

3.变量定义

(1)int a[total_instruction]: 指令流数据组.

(2)int page[total_instruction]: 每条指令所属的页号.

(3)int offset[total_instruction]: 每页装入10条指令后取模运算页号偏移值.

(4)int total_pf: 用户进程的内存页面数.

(5)int disaffect: 页面失效次数.

4.程序参考源码及结果

<程序>

#define TRUE 1

#define FALSE 0

#define INVALID -1

#define NULL 0

#define total_instruction 320 /*指令流长*/

#define total_vp 32 /*虚页长*/

#define clear_period 50 /*清0周期*/

typedef struct /*页面结构*/

{

int pn; //页号 logic number

int pfn; //页面框架号 physical frame number

int counter; //计数器

int time; //时间

}pl_type;

pl_type pl[total_vp]; /*页面线性结构---指令序列需要使用地址*/

typedef struct pfc_struct /*页面控制结构，调度算法的控制结构*/

{

int pn;

int pfn;

struct pfc_struct *next;

}pfc_type;

pfc_type pfc[total_vp], *freepf_head, *busypf_head, *busypf_tail;

int diseffect, a[total_instruction]; /* a[]为指令序列*/

int page[total_instruction], offset[total_instruction];/*地址信息*/

int initialize(int);

int FIFO(int);

int LRU(int);

int LFU(int);

int NUR(int); //not use recently

int OPT(int);

int main( )

{

int s,i,j;

srand(10*getpid()); /*由于每次运行时进程号不同，故可用来作为初始化随机数队列的“种子”*/

s=(float)319*rand( )/32767/32767/2+1; /*正态分布*/

for(i=0;i{

if(s<0||s>319)

{

printf(\"When i==%d,Error,s==%d\\n\

exit(0);

}

a[i]=s; /*任选一指令访问点m*/

a[i+1]=a[i]+1; /*顺序执行一条指令*/

a[i+2]=(float)a[i]*rand( )/32767/32767/2; /*执行前地址指令m*/

a[i+3]=a[i+2]+1; /*顺序执行一条指令*/

s=(float)(318-a[i+2])*rand( )/32767/32767/2+a[i+2]+2;

if((a[i+2]>318)||(s>319))

printf(\"a[%d+2],a number which is :%d and s==%d\\n\

}

for (i=0;i{

page[i]=a[i]/10;

offset[i]=a[i]%10;

}

for(i=4;i<=32;i++) /*用户内存工作区从4个页面到32个页面*/

{

printf(\"---%2d page frames---\\n\

FIFO(i);

LRU(i);

LFU(i);

NUR(i);

OPT(i);

}

return 0;

}

/*初始化相关数据结构 total_pf表示内存的块数 */

int initialize(int total_pf)

{

int i;

diseffect=0;

for(i=0;i{

pl[i].pfn=INVALID; /*置页面控制结构中的页号，页面为空*/

pl[i].counter=0; /*页面控制结构中的访问次数为0*/

pl[i].time=-1; /*访问的时间*/

}

for(i=0;i{

pfc[i].next=&pfc[i+1];

pfc[i].pfn=i;

}

pfc[total_pf-1].next=NULL;

pfc[total_pf-1].pfn=total_pf-1;

freepf_head=&pfc[0]; /*空页面队列的头指针为pfc[0]*/

return 0;

}

int FIFO(int total_pf) /*先进先出算法total_pf:用户进程的内存页面数*/

{

int i,j;

pfc_type *p; /*中间变量*/

initialize(total_pf); /*初始化相关页面控制用数据结构*/

busypf_head=busypf_tail=NULL; /*忙页面队列头，队列尾链接*/

for(i=0;i{

if(pl[page[i]].pfn==INVALID) /*页面失效*/

{

diseffect+=1; /*失效次数*/

if(freepf_head==NULL) /*无空闲页面*/

{

p=busypf_head->next;

pl[busypf_head->pn].pfn=INVALID;

freepf_head=busypf_head; /*释放忙页面队列的第一个页面*/

freepf_head->next=NULL; /*表明还是缺页*/

busypf_head=p;

}

p=freepf_head->next;

freepf_head->pn=page[i];

pl[page[i]].pfn=freepf_head->pfn;

freepf_head->next=NULL; /*使busy的尾为null*/

if(busypf_tail==NULL)

{

busypf_tail=busypf_head=freepf_head;

}

else

{

busypf_tail->next=freepf_head;

busypf_tail=freepf_head;

}

freepf_head=p;

}

printf(\"FIFO:%6.4f\\n\

return 0;

int LRU (int total_pf) /*最近最久未使用算法least recently used*/

{

int min,minj,i,j,present_time; /*minj为最小值下标*/

initialize(total_pf);

present_time=0;

for(i=0;i{

if(pl[page[i]].pfn==INVALID) /*页面失效*/

{

diseffect++;

if(freepf_head==NULL) /*无空闲页面*/

{

min=32767; /*设置最大值*/

for(j=0;j{

if(min>pl[j].time&&pl[j].pfn!=INVALID)

{

min=pl[j].time;

minj=j;

}

freepf_head=&pfc[pl[minj].pfn]; //腾出一个单元

pl[minj].pfn=INVALID;

pl[minj].time=0;

freepf_head->next=NULL;

}

pl[page[i]].pfn=freepf_head->pfn; //有空闲页面,改为有效

pl[page[i]].time=present_time;

freepf_head=freepf_head->next; //减少一个free 页面

}

else

{

pl[page[i]].time=present_time; //命中则增加该单元的访问次数

present_time++;

}

printf(\"LRU:%6.4f\\n\

return 0;

}

int NUR(int total_pf ) /*最近未使用算法Not Used recently count表示*/

{

int i,j,dp,cont_flag,old_dp;

pfc_type *t;

initialize(total_pf);

dp=0;

for(i=0;i{

if (pl[page[i]].pfn==INVALID) /*页面失效*/

{

diseffect++;

if(freepf_head==NULL) /*无空闲页面*/

{

cont_flag=TRUE;

old_dp=dp;

while(cont_flag)

{

if(pl[dp].counter==0&&pl[dp].pfn!=INVALID)

cont_flag=FALSE;

else

{

dp++;

if(dp==total_vp)

dp=0;

if(dp==old_dp)

for(j=0;jpl[j].counter=0;

}

freepf_head=&pfc[pl[dp].pfn];

pl[dp].pfn=INVALID;

freepf_head->next=NULL;

}

pl[page[i]].pfn=freepf_head->pfn;

freepf_head->pn=page[i];

freepf_head=freepf_head->next;

}

else

pl[page[i]].counter=1;

if(i%clear_period==0)

for(j=0;jpl[j].counter=0;

}

printf(\"NUR:%6.4f\\n\

return 0;

}

int OPT(int total_pf) /*最佳置换算法*/

{

int i,j, max,maxpage,d,dist[total_vp];

pfc_type *t;

initialize(total_pf);

for(i=0;i{

if(pl[page[i]].pfn==INVALID) {

diseffect++;

if(freepf_head==NULL) {

for(j=0;j{

if(pl[j].pfn!=INVALID)

dist[j]=32767;

/*页面失效*/

/*无空闲页面*/

else

dist[j]=0;

}

for(j=0;j{

if((pl[j].pfn!=INVALID)&&(dist[j]==32767))

{

dist[j]=j;

}

max=0;

for(j=0;jif(max{

max=dist[j];

maxpage=j;

}

freepf_head=&pfc[pl[maxpage].pfn];

freepf_head->next=NULL;

pl[maxpage].pfn=INVALID;

}

pl[page[i]].pfn=freepf_head->pfn;

freepf_head=freepf_head->next;

}

printf(\"OPT:%6.4f\\n\

return 0;

}

/*该算法时根据已知的预测未知的，least frequency Used是最不经常使用置换法*/

int LFU(int total_pf)

{

int i,j,min,minpage;

pfc_type *t;

initialize(total_pf);

for(i=0;i{

if(pl[page[i]].pfn==INVALID) {

diseffect++;

if(freepf_head==NULL) {

min=32767;

/*页面失效*/

/*无空闲页面*/

/*获取counter的使用用频率最小的内存*/

for(j=0;j{

if(min>pl[j].counter&&pl[j].pfn!=INVALID)

{

min=pl[j].counter;

minpage=j;

}

freepf_head=&pfc[pl[minpage].pfn];

pl[minpage].pfn=INVALID;

pl[minpage].counter=0;

freepf_head->next=NULL;

}

pl[page[i]].pfn=freepf_head->pfn; //有空闲页面,改为有效

pl[page[i]].counter++;

freepf_head=freepf_head->next; //减少一个free 页面

}

else

{

pl[page[i]].counter;

pl[page[i]].counter=pl[page[i]].counter+1;

}

printf(\"LFU:%6.4f\\n\

return 0;

}

<结果一：〉

4 page framesFIFO:0.2562LRU:0.2531OPT:0.3031LFU:0.2812NUR:0.2812

5 page framesFIFO:0.2969LRU:0.2906OPT:0.3500LFU:0.3219NUR:0.3094

6 page framesFIFO:0.3375LRU:0.3281OPT:0.3844LFU:0.3375NUR:0.3344

7 page framesFIFO:0.3563LRU:0.3563OPT:0.4031LFU:0.3563NUR:0.3500

8 page framesFIFO:0.3937LRU:0.3750OPT:0.4531LFU:0.3937NUR:0.3719

9 page framesFIFO:0.4219LRU:0.4094OPT:0.4844LFU:0.4156NUR:0.4062

10 page framesFIFO:0.4375LRU:0.4313OPT:0.5062LFU:0.4313NUR:0.4250

11 page framesFIFO:0.4813LRU:0.4625OPT:0.5531LFU:0.4500NUR:0.4656

12 page framesFIFO:0.5406LRU:0.4875OPT:0.5687LFU:0.4938NUR:0.4875

13 page framesFIFO:0.5500LRU:0.5188OPT:0.5969LFU:0.5062NUR:0.5437

14 page framesFIFO:0.5594LRU:0.5531OPT:0.6344LFU:0.5281NUR:0.5469

15 page framesFIFO:0.5687LRU:0.5844OPT:0.6687LFU:0.5469NUR:0.5813

16 page framesFIFO:0.5781LRU:0.5938OPT:0.6813LFU:0.5719NUR:0.5969

17 page framesFIFO:0.5906LRU:0.6156OPT:0.6969LFU:0.6156NUR:0.6156

18 page framesFIFO:0.6156LRU:0.6312OPT:0.7156LFU:0.6344NUR:0.6531

19 page framesFIFO:0.6687LRU:0.6656OPT:0.7344LFU:0.6531NUR:0.6719

20 page framesFIFO:0.6875LRU:0.6969OPT:0.7500LFU:0.6719NUR:0.6906

21 page framesFIFO:0.6906LRU:0.7094OPT:0.7688LFU:0.6969NUR:0.7188

22 page framesFIFO:0.7125LRU:0.7219OPT:0.7969LFU:0.7156NUR:0.7344

23 page framesFIFO:0.7156LRU:0.7406OPT:0.8125LFU:0.7250NUR:0.7812

24 page framesFIFO:0.7281LRU:0.7625OPT:0.8187LFU:0.7406NUR:0.7719

25 page framesFIFO:0.7469LRU:0.7750OPT:0.8344LFU:0.7594NUR:0.8000

26 page framesFIFO:0.8125LRU:0.8000OPT:0.8500LFU:0.7812NUR:0.8063

27 page framesFIFO:0.8313LRU:0.8187OPT:0.8594LFU:0.8031NUR:0.8281

28 page framesFIFO:0.8438LRU:0.8375OPT:0.8688LFU:0.8344NUR:0.8469

29 page framesFIFO:0.8688LRU:0.8531OPT:0.8750LFU:0.8562NUR:0.8562

30 page framesFIFO:0.8781LRU:0.8719OPT:0.8781LFU:0.8750NUR:0.8688

31 page framesFIFO:0.8938LRU:0.8750OPT:0.8844LFU:0.8844NUR:0.8906

32 page framesFIFO:0.9000LRU:0.9000OPT:0.9000LFU:0.9000NUR:0.9000

<分析>

从上述结果可知，在内存页面数较少（4~5页）时，五种算法的命中率差别不大，都是30%左右。在内存页面为7~18个页面之间时，5种算法的访内命中率大致在35%~60%之间变化。但是，FIFO算法与OPT算法之间的差别一般在6~10个百分点左右。在内存页面为25~32个页面时，由于用户进程的所有指令基本上都已装入内存，使命中率增加，从而算法之间的差别不大。

比较上述5种算法，以OPT算法的命中率最高，NUR算法次之，再就是LFU算法和LRU算法，其次是FIFO算法。就本问题，在15页之前，FIFO的命中率比LRU的高。

<结果二：>

4 page framesFIFO:0.2594LRU:0.2562OPT:0.2687LFU:0.2437NUR:0.2625

5 page framesFIFO:0.3000LRU:0.3000OPT:0.3000LFU:0.2969NUR:0.2875

6 page framesFIFO:0.3375LRU:0.3281OPT:0.3281LFU:0.3094NUR:0.3281

7 page framesFIFO:0.3563LRU:0.3563OPT:0.3688LFU:0.3312NUR:0.3469

8 page framesFIFO:0.4031LRU:0.4094OPT:0.3875LFU:0.3406NUR:0.3781

9 page framesFIFO:0.4156LRU:0.4281OPT:0.4156LFU:0.3656NUR:0.4125

10 page framesFIFO:0.4281LRU:0.4469OPT:0.4313LFU:0.3750NUR:0.4406

11 page framesFIFO:0.4531LRU:0.4688OPT:0.4594LFU:0.4281NUR:0.4656

12 page framesFIFO:0.4656LRU:0.4813OPT:0.4906LFU:0.4375NUR:0.4938

13 page framesFIFO:0.4750LRU:0.5000OPT:0.5219LFU:0.4625NUR:0.5312

14 page framesFIFO:0.4906LRU:0.5125OPT:0.5375LFU:0.4938NUR:0.5500

15 page framesFIFO:0.5312LRU:0.5250OPT:0.5625LFU:0.5281NUR:0.5563

16 page framesFIFO:0.5406LRU:0.5625OPT:0.5813LFU:0.5531NUR:0.5844

17 page framesFIFO:0.5906LRU:0.5813OPT:0.6188LFU:0.5750NUR:0.6031

18 page framesFIFO:0.6000LRU:0.5906OPT:0.6344LFU:0.5906NUR:0.6250

19 page framesFIFO:0.6312LRU:0.6156OPT:0.6438LFU:0.6219NUR:0.6438

20 page framesFIFO:0.6406LRU:0.6344OPT:0.6625LFU:0.6438NUR:0.6750

21 page framesFIFO:0.6969LRU:0.6594OPT:0.6875LFU:0.6656NUR:0.6937

22 page framesFIFO:0.7000LRU:0.6781OPT:0.7125LFU:0.6813NUR:0.6844

23 page framesFIFO:0.7156LRU:0.6906OPT:0.7312LFU:0.7188NUR:0.6969

24 page framesFIFO:0.7438LRU:0.7219OPT:0.7531LFU:0.7438NUR:0.7469

25 page framesFIFO:0.7594LRU:0.7562OPT:0.7656LFU:0.7656NUR:0.7719

26 page framesFIFO:0.7750LRU:0.7812OPT:0.7937LFU:0.7781NUR:0.7781

27 page framesFIFO:0.8125LRU:0.7969OPT:0.8094LFU:0.8125NUR:0.7969

28 page framesFIFO:0.8344LRU:0.8313OPT:0.8281LFU:0.8313NUR:0.8406

29 page framesFIFO:0.8406LRU:0.8594OPT:0.8531LFU:0.8375NUR:0.8406

30 page framesFIFO:0.8625LRU:0.8781OPT:0.8750LFU:0.8562NUR:0.8594

31 page framesFIFO:0.8812LRU:0.8812OPT:0.8906LFU:0.8781NUR:0.8656

32 page framesFIFO:0.9000LRU:0.9000OPT:0.9000LFU:0.9000NUR:0.9000

<分析>

从结果可以看出，FIFO的命中率竟然比OPT的还高。至于为什么，请探讨。

实验6指导

[实验内容]

<任务>

为Linux系统设计一个简单的二级文件系统。要求做到以下几点：

1.可以实现下列几条命令：

dir 列目录

create 创建文件

delete 删除文件

open 打开文件

close 关闭文件

read 读文件

write 写文件

2．列目录时要列出文件名，物理地址，保护码和文件长度

3．源文件可以进行读写保护

<程序设计>

(1)设计思想

本文件系统采用两级目录，其中第一级对应于用户账号，第二级对应于用户帐号下的文件。另外，

为了简便文件系统未考虑文件共享，文件系统安全以及管道文件与设备文件等特殊内容。对这些内容感兴趣的读者，可以在本系统的程序基础上进行扩充。

(2)主要数据结构

a) I节点

struct inode{

struct inode *i_forw;

struct inode *i_back;

char I_flag;

unsigned int i_into; /*磁盘i节点标号*/

unsigned int i_count; /*引用计数*/

unsigned short di_number; /*关联文件书，当为0时，则删除该文件*/

unsigned short di_mode; /*存取权限*/

unsigned short di_uid; /*磁盘i节点用户*/

unsigned short di_gid; /*磁盘i节点组*/

Unsigned int di_addr[NADDR]; /*物理块号*/

b) 磁盘i结点

Struct dinode

{

unsigned short di_number; unsigned short di_mode; unsigned short di_uid;

unsigned short di_gid;

unsigned long di_size; unsigned int di_addr[NADDR]; c)目录项结构

Struct direct

{

char d_name[DIRSIZ]; /*关联文件数*/

/*存取权限*/

/*文件大小*/

/*物理块号*/

/*目录名*/

unsigned int d_ino; /*目录号*/

}

d)超级块

Struct filsys

{

unsigned short s_isize; unsigned long s_fsize; unsigned int s_nfree; unsigned short s_pfree; unsigned int s_free[NICFREE]; unsigned int s_ninode; unsigned short s_pinode; unsigned int s_inode[NICINOD]; unsigned int s_rinode; /*i节点块块数*/

/*数据块块数*/

/*空闲块块数*/

/*空闲块指针*/

/*空闲块堆栈*/

/*空闲i节点数*/

/*空闲i节点指针*/

/*空闲i节点数组*/

/*铭记i节点*/

char s_fmod; /*超级块修改标志*/

};

e)用户密码

Struct pwd

{

unsigned short P_uid;

unsigned short P_gid;

char passward[PWOSIZ];

}

f) 目录

Struct dir

{

strut direct direct[DIRNUM];

int size;

}

g).查找i内存节点的hash表

Struct hinode

{

strut inode *iforw;

}

h).系统打开表

Struct file

{

char f_flag; /*文件操作标志*/

unsigned int f_count; /*引用计数*/

struct inode *f_inode; /*指向内存节点*/

unsigned long f_off; /*读/写指针*/

}

i)用户打开表

Struct user

{

unsigned short u_default_mode;

unsigned short u_uid; /*用户标志*/

unsigned short u_gid; /*用户组标志*/

unsigned short u_ofile[NOFILE]; /*用户打开表*/

}

3.主要函数

（1）i节点内容获取函数iget()（详细描述略）。

（2）节点内容释放函数iput()（详细描述略）。

（3）目录创建函数mkdir()（详细描述略）。

（4）目录搜索函数namei()（详细描述略）。

（5）磁盘块分配函数balloc()（详细描述略）。

（6）磁盘块释放函数bfree()（详细描述略）。

（7）分配i节点区函数ialloc()（详细描述略）。

（8）解释结点区函数ifree（）（详细描述略）。

（9）搜索当前目录下文件的函数iname（）（详细描述略）。

（10）访问控制函数access（）（详细描述略）。

（11）显示目录和文件函数_dir（）（详细描述略）。

（12）改变当前目录用函数chdir（）（详细描述略）。

（13）打开文件函数open（）（详细描述略）。

（14）创建文件函数create（）（详细描述略）。

（15）读文件用函数read（）（详细描述略）。

（16）读文件用函数write（）（详细描述略）。

（17）用户登陆函数login（）（详细描述略）。

（18）用户退出函数logout（）（详细描述略）。

（19）文件系统格式化函数format（）（详细描述略）。

（20）进入文件系统函数install（）（详细描述略）。

（21）关闭文件函数close（）（详细描述略）。

（22）退出文件系统函数halt（）（详细描述略）。

（23）文件删除函数delecte（）（详细描述略）。

4．主程序说明

begin

Step1 对磁盘进行格式化

Step2 调用install（），进入文件系统

Step3 调用_dir（），显示当前目录

Step4 调用login（），用户注册

Step5 调用mkdir（）和chdir（）创建目录

Step6 调用create（），创建文件0

Step7 分配缓冲区

Step8 写文件0

Step9 关闭文件0和释放缓冲

Step10 调用mkdir（）和chdir（）创建子目录

Step11 调用create（），创建文件1

Step12 Step13 Step14 Step15 Step16 Step17 Step18 Step19 Step20 Step21 Step22 分配缓冲区

写文件1

关闭文件1和释放缓冲

调用chdir将当前目录移到上一级

调用create（），创建文件2

分配缓冲区

调用write（），写文件2

关闭文件1和释放缓冲

调用delecte（），删除文件0

调用create（），创建文件1

为文件3分配缓冲区

Step23 调用write（），写文件2

Step24 关闭文件3并释放缓冲区

Step25 调用open()，打开文件2

Step26 为文件2分配缓冲

Step27 写文件3后关闭文件3

Step28 释放缓冲

Step29 用户退出（logout）

Step30 关闭（halt）

End

由上述的描述过乘可知，该文件系统实际是为用户提供一个解释执行相关命令的环境。主程序中的大部分语句都被用来执行相应的命令。

下面我们给出每个过程的相关C语言程序。读者也可以使用这些子过程，编写一个用Shell控制的文件系统界面。

<程序>

1.编写管理文件makefile

本文件系统程序用编写makefile管理工具进行管理。其内容如下：

***********************************************************************/

/*******************************************

makefile

*******************************************/

filsys:main.o iallfre.o ballfre.o name.o access.o log.o close.o creat.o delete.o dir.o

open.o rdwt.o format.o install.o halt.o cc-o filsys main.o iallfre.o ballfre.o

name.o access.o log.o close.o creat.o delete.o dir.o open.o format.o install.o halt.o

main.o:main.c filesys.h

cc-c main.c

igetput.o: igetput.c filesys.h

cc-c igetput.c

iallfre.o: iallfre.c filesys.h

cc-c iallfre.c

ballfre.o: ballfre.c filesys.h

cc-c ballfre.c

name.o:name.c filesys.h

cc-c name.c

access.o:access.c filesys.h

cc-c access.c

log.o:log.c filesys.h

cc-c log.c

close.o:close.c filesys.h

cc-c close.c

creat.c:creat.c filesys.h

cc-c creat.c

delete.o:delete.c filesys.h

cc-c delete.c

dir.o:dir.c filesys.h

cc-c dir.c

open.o:open.c filesys.h

cc-c open.c

rdwt.o:rdwt.c filesys.h

cc-c rdwt.c

format.o:format.c filesys.h

cc-c format.c

install.o: install.c filesys.h

cc-c install.c

halt.o:halt.c

cc-c halt.c

系统调用函数说明、参数值及定义

1、fork()

创建一个新进程

int fork()

其中返回int取值意义如下：

0：创建子进程，从子进程返回的id值

大于0：从父进程返回的子进程id值

-1：创建失败

2、lockf(files,function,size):

用作锁定文件的某些段或者整个文件，本函数适用的头文件为：

#include

参数定义：

int lockf(files,function,size)

int files,function;

long size;

其中：files是文件描述符：function是锁定和解锁；1表示锁定，0表示解锁。size是锁定和解锁

的字节数，若用0，表示从文件的当前位置到文件尾。

3、msgget(key,flag):

获得一个消息的描述符，该描述符指定一个消息队列以便用于其他系统调用。

该函数使用偷文件如下：

#include

参数定义

int msgget(key,flag)

key_tkey;

int flag;

语法格式：msgqid=msgget(key,flag)

其中：msgid是该系统调用返回的描述符，失败则返回-1；flag 本身由操作允许权和控制命令值相“或”得到。

如：IP_CREAT|0400 是否该队列应被创建；

IP_EXCL |0400 是否该队列的创建应是互斥的；等。

4、msgsnd(id,msgp,size,flag):

发送一消息。

该函数是用头文件如下：

#include

参数定义

int msgnd(id,msgp,size,flag)

int id,size,flag;

struct msgbuf * msgp;

其中：id是返回消息队列的描述符；msgp是指向用户存储区的一个构造体指针，size指示由msgp指向的数据结构中字符数组的长度；即消息的长度。这个数组的最大值由MSG-MAX系统可调用参数来确定。flag规定当核心用尽内部缓冲空间时应执行的动作；若在标志flag中末设置IPC_NOWAIT位，

则当该消息队列中字节数超过一最大值时，或系统范围的消息数超过某一最大值时，调用msgsnd进程睡眠。若是设置IPC_NOWAIT，则在此情况下，msgsnd立即返回。

5、msgrcv(id,msgp,size,type,flag):

接受一消息。

该函数调用使用头文件如下：

#include

参数定义

int msgrcv(id,msgp,size,type,flag)

int id,size,type,flag;

struct msgbuf * msgq;

struct sgbuf{long mtpe;chat mtext[];};

语法格式：

count=msgrcv(id,msgp,size,type,flag)

其中：id是用来存放欲接收消息的拥护数据结构的地址；size是msgp中数据数组的大小； type是用户要读的消息类型：

type为0:接收该队列的第一个消息；

type为正：接收类型type的第一个消息；

type为负：接收小于或等于type绝对值的最低类型的第一个消息。

flag规定倘若该队列无消息，核心应当做什么事，如果此时设置了IPC_NOWAIT标志，则立即返回，若在flag中设置了MSG_NOERROR，且所接收的消息大小大于size，核心截断所接受的消息。

count是返回消息正文的字节数。

6、msgctl(id,cmd,buf):

查询一个消息描述符的状态，设置它的状态及删除一个消息描述符。

调用该函数使用头文件如下：

#include

参数定义

int msgctl(id,cmd,buf)

int id,cmd;

struct msgbuf * msgq;

struct msqid_ds * buf;

其中：函数调用成功时返回0，调用不成功时返回-1。id用来识别该消息的描述符；cmd规定命令的类型。

IPC_START将与id相关联的消息队列首标读入buf。

IPC_SET为这个消息序列设置有效的用户和小组标识及操作允许权和字节的数量。

IPC_RMID删除id的消息队列。

buf是含有控制参数或查询结果的用户数据结构的地址。

附：msgid_ds结构定义如下：

struct msgid_ds

{struct ipc_perm msg_perm; /*许可权结构*/

shot padl[7]; /*由系统使用*/

ushort onsg_qnum; /*队列上消息数*/

ushort msg_qbytes; /*队列上最大字节数*/

ushort msg_lspid; /*最后发送消息的PID*/

ushort msg_lrpid; /*最后接收消息的PID*/

time_t msg__stime; /*最后发送消息的时间*/

time_t msg_rtime; /*最后接收消息的时间*/

me_t msg_ctime; /*最后更改时间*/

}；

struct ipc_perm

{ushort uid; /*当前用户id*/

ushort gid; /*当前进程组id*/

ushort cuid; /*创建用户id*/

ushort cgid

/*创建进程组id*/

ushort mode; /*存取许可权*/

{shot patl;long pad2} /*由系统使用*/

}；

7、shmget(key,size,flag):

获得一个共享存储区。

该函数使用头文件如下：

#include

语法格式：

shmid=shmaget(key,size,flag)

参数定义:

int shmaget(key,size,flag)

key_t key;

int size,flag;

其中：size是存储区的字节数，key和flag与系统调用msgget中的参数含义相同。

附：

操作允许权八进制数

用户可读 00400

用户可读 00200

小组可读 00040

小组可读 00020

其他可读 00004

其他可读 00002

控制命令值

IPC_CREAT 0001000

IPC_EXCL 0002000

如:shmid=shmget(key,size,(IPC_CREAT|0400））；

创建一个关键字为key,长度为size的共享存储区。

8、shmat(id,addr,flag):

从逻辑上将一个共享存储区附接到进程的虚拟地址空间上。

该函数调用使用头文件如下：

#include

参数定义:

char * shmat(id,addr,flag)

int id,flag;

char * addr;

语法格式：virtaddr=shmat(id,addr,flag)

其中：id是共享存储区的标识符，addr是用户要使用共享存储区附接的虚地址，若addr是0，系统是否对应用户规定的地址做舍入操作。如果flag中设置了shm_rnd即表示操作系统在必要时舍去这个地址。如果设置了shm_rdonly，即表示只允许读操作。viraddr是附接的虚地址。

9、shmdt(addr):

把一个共享存储区从指定进程的虚地址空间分开。

调用该函数使用头文件：

#include

参数定义:

int shmdt(addr)

char * addr

其中，当调用成功时，返回0值，调用不成功，返回-1，addr是系统调用shmat所返回的地址。

10、shmctl(id,cmd,buf):

对与共享存储区关联的各种参数进行操作，从而对共享存储区进行控制。

调用该函数使用头文件：

#include

参数定义:

int shmctl(id,cmd,buf)

int id,cmd;

struct shmid_ds * buf;

其中：调用成功返回0，否则返回-1。id为被共享存储区的标识符。cmd规定操作的类型。规定如下：

IPC_STAT:返回包含在指定的shmid相关数据结构中的状态信息，并且把它放置在用户存储区中的*but指针所指的数据结构中。执行此命令的进程必须有读取允许权。

IPC_SET：对于指定的shmid，为它设置有效用户和小组标识和操作存取权。

IPC_RMID：删除指定的shmid以及与它相关的共享存储区的数据结构。

SHM_LOCK：在内存中锁定指定的共享存储区，必须是超级用户才可以进行此项操作。

Buf是一个用户级数据结构地址。

附：

shmid_ds

{struct ipc_perm shm_perm; /*允许权结构*/

int shm_segsz; /*段大小*/

int padl; /*由系统使用；*/

ushort shm_lpid; /*最后操作的进程id；*/

ushort shm_cpid; /*创建者的进程id；*/

ushort shm_nattch; /*当前附界数；*/

short pad2; /*由系统使用；*/

time_t shm_atime; /*最后附接时间*/

time_t shm_dtime; /*最后段接时间*/

time_t shm_ctime; /*最后修改时间*/

}

11、signal(sig,function):

允许调用进程控制软中断信号的处理。

头文件为：

#include

参数定义:

signal(sig,function);

int sig;

void(*func)();

其中：sig的值是：

SIGHVP 挂起

SIGINT 键盘按^c键或break键

SIGQUIT 键盘按quit键

SIGILL 非法指令

SIGIOT IOT指令

SIGEMT EMT指令

SIGFPE 浮点运算溢出

SIGKILL 要求终止进程

SIGBUS 总线错

SIGSEGV 段违例

SIGSYS 系统调用参数错

SIGPIPE 向无读者管道上写

SIGALRM 闹钟

SIGTERM 软件终结

SIGUSRI 用户定义信号

SIGUSR2 第二个用户定义信号

SIGCLD 子进程死

SIGPWR 电源故障

function的解释如下：

SIG_DEL：缺省操作。对除SIGPWR和SIGCLD外所有信号的缺省操作是进程终结对信号

SIGQUIT,SIGILL,SIGTRA,SIGIOT,SIGEMT,SIGFPE,SIGBUS,SIGSEGV和SIGSYS它产生一内存映像

文件。

SIG_IGN：忽视该信号的出现。

Function:在该进程中的一个函数地址，在核心返回用户态时，它以软中断信号的序号作为参数调用该函数，对除了信号SIGILL,SIGTRAP和SIGTWR以外的信号，核心自动地重新设置软中断信号处理程序的值为SIG_DEL，一个进程不能捕获SIGKILL信号。

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文

全部栏目

操作系统实验答案