《操作系统》
实 验 总 结
学 号：
学生姓名：
专业班级：
1.1进程创建
UNIX中，进程既是一个独立拥有资源的基本单位，又是一个独立调度的基本单位。一个进程实体由若干个区（段）组成，包括程序区、数据区、栈区、共享存储区等。每个区又分为若干页，每个进程配置有唯一的进程控制块PCB，用于控制和管理进程。
在Linux中主要提供了fork、vfork、clone三个进程创建方法。在linux源码中这三个调用的执行过程是执行fork(),vfork(),clone()时，通过一个系统调用表映射到sys_fork(),sys_vfork(),sys_clone(),再在这三个函数中去调用do_fork()去做具体的创建进程工作。本次实验我们只使用fork。
fork创建一个进程时，子进程只是完全复制父进程的资源，复制出来的子进程有自己的task_struct结构和pid,但却复制父进程其它所有的资源。新旧进程使用同一代码段,复制数据段和堆栈段，这里的复制采用了注明的copy_on_write技术，即一旦子进程开始运行，则新旧进程的地址空间已经分开，两者运行独立。
fork（）函数不需要参数，返回一个进程ID。返回值有三种情况：
（1）对于父进程，fork函数返回新的子进程的ID。
（2）对于子进程，fork函数返回0。
（3）如果出错，fork函数返回-1。
1.2 进程控制
进程控制主要有：
1.exec( )
系统调用exec( )系列，也可用于新程序的运行。exec( )系列可以将一个可执行的二进制文件覆盖在新进程的用户级上下文的存储空间上，以更改新进程的用户级上下文。exec( )系列中的系统调用都完成相同的功能，它们把一个新程序装入内存，来改变调用进程的执行代码，从而形成新进程。如果exec( )调用成功，调用进程将被覆盖，然后从新程序的入口开始执行，这样就产生了一个新进程，新进程的进程标识符id 与调用进程相同。
2.wait( )
进程一旦调用了wait，就立即阻塞自己，由wait自动分析是否当前进程的某个子进程已经退出，如果让它找到了这样一个已经变成僵尸的子进程，wait就会收集这个子进程的信息，并把它彻底销毁后返回；如果没有找到这样一个子进程，wait就会一直阻塞在这里，直到有一个出现为止。
3.exit( )
这个系统调用是用来终止一个进程的。无论在程序中的什么位置，只要执行到exit系统调用，进程就会停止剩下的所有操作，清除包括PCB在内的各种数据结构，并终止本进程的运行。
4.getpid( )
getpid的作用很简单，就是返回当前进程的进程ID。
#include<stdio.h>
#include<unistd.h>
main( )
{
int pid;
pid=fork( ); /*创建子进程*/
switch(pid)
{
case -1: /*创建失败*/
printf("fork fail!\n");
exit(1);
case 0: /*子进程*/
execl("/bin/ls","ls","-1","-color",NULL);
printf("exec fail!\n");
exit(1);
default: /*父进程*/
wait(NULL); /*同步*/
printf("ls completed !\n");
exit(0);
}
}
进程同步是指对多个相关进程在执行次序上进行协调，以使并发执行的主进程之间有 效地共享资源和相互合作，从而使程序的执行具有可在现行。 首先程序在调用fork()机那里了一个子进程后，马上调用wait()，使父进程在子进程调用之前一直处于睡眠状态，这样就使子进程先运行，子进程运行exec()装入命令后，然后调用wait(0),使子进程和父进程并发执行，实现进程同步。
1.3 进程互斥
#include <stdio.h>
#include <unistd.h>
main( )
{
int p1,p2,i;
while((p1=fork( ))= = -1); /*创建子进程p1*/
if (p1= =0)
{
lockf(1,1,0); /*加锁，这里第一个参数为stdout（标准输出设备的描述符）*/
for(i=0;i<10;i++)
printf("daughter %d\n",i);
lockf(1,0,0); /*解锁*/
}
else
{
while((p2=fork( ))= =-1); /*创建子进程p2*/
if (p2= =0)
{
lockf(1,1,0); /*加锁*/
for(i=0;i<10;i++)
printf("son %d\n",i);
lockf(1,0,0); /*解锁*/
}
else
{
lockf(1,1,0); /*加锁*/
for(i=0;i<10;i++)
printf(" parent %d\n",i);
lockf(1,0,0); /*解锁*/
}
}
}
上述程序执行时，不同进程之间不存在共享临界资源（其中打印机的互斥性已由操作系统保证）问题，所以加锁与不加锁效果相同。
1.4 总结
进程管理相关命令：
Ps: ps命令是用来显示系统瞬间的进程信息，它可以显示出在用户输入ps命令时系统的进程及进程的相关信息。
Kill: kill命令不但能杀死进程，同时也会杀死该进程的所有子进程。
Nice: 指定程序的运行优先级。
Renice：改变一个正在运行的进程的优先级。
2．进程间通信
2.1信号机制
每个信号都对应一个正整数常量(称为signal number,即信号编号。定义在系统头文件<signal.h>中)，代表同一用户的诸进程之间传送事先约定的信息的类型，用于通知某进程发生了某异常事件。每个进程在运行时，都要通过信号机制来检查是否有信号到达。若有，便中断正在执行的程序，转向与该信号相对应的处理程序，以完成对该事件的处理；处理结束后再返回到原来的断点继续执行。实质上，信号机制是对中断机制的一种模拟，故在早期的UNIX版本中又把它称为软中断。
#include <stdio.h>
#include <signal.h>
#include <unistd.h>
void waiting( ),stop( );
int wait_mark;
main( )
{
int p1,p2,stdout;
while((p1=fork( ))= =-1); /*创建子进程p1*/
if (p1>0)
{
while((p2=fork( ))= =-1); /*创建子进程p2*/
if(p2>0)
{
wait_mark=1;
signal(SIGINT,stop); /*接收到^c信号，转stop*/
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); /*接收到软中断信号17，转stop*/
waiting( );
lockf(stdout,1,0);
printf("Child process 2 is killed by parent!\n");
lockf(stdout,0,0);
exit(0);
}
}
else
{
wait_mark=1;
signal(16,stop); /*接收到软中断信号16，转stop*/
waiting( );
lockf(stdout,1,0);
printf("Child process 1 is killed by parent!\n");
lockf(stdout,0,0);
exit(0);
}
}
void waiting( )
{
while(wait_mark!=0);
}
void stop( )
{
wait_mark=0;
}
Wait(0)作用就是把调用它的进程挂起，直到有别的进程终止它再开始执行。
每个进程退出时都用了语句exit(0),一方面要结束进程,另外向父进程返回结束标志0 。
2.2 进程管道通信
常用的进程间通信方式有这几种
A.传统的进程间通信方式
无名管道(pipe)、有名管道(fifo)和信号(signal)
B.System v IPC对象
共享内存(share memory)、消息队列(message queue)和信号灯(semaphore)
C.BSD
套接字(socket)
本次实验使用无名管道
2.3 消息发送与接收
消息（message）是一个格式化的可变长的信息单元。消息机制允许由一个进程给其它任意的进程发送一个消息。当一个进程收到多个消息时，可将它们排成一个消息队列。消息使用二种重要的数据结构：一是消息首部，其中记录了一些与消息有关的信息，如消息数据的字节数；二个消息队列头表，其每一表项是作为一个消息队列的消息头，记录了消息队列的有关信息。
1、client.c
#include <sys/types.h>
#include <sys/msg.h>
#include <sys/ipc.h>
#define MSGKEY 75
struct msgform
{ long mtype;
char mtext[1000];
}msg;
int msgqid;
void client()
{
int i;
msgqid=msgget(MSGKEY,0777); /*打开75#消息队列*/
for(i=10;i>=1;i--)
{
msg.mtype=i;
printf(“(client)sent\n”);
msgsnd(msgqid,&msg,1024,0); /*发送消息*/
}
exit(0);
}
main( )
{
client( );
}
2、server.c
#include <sys/types.h>
#include <sys/msg.h>
#include <sys/ipc.h>
#define MSGKEY 75
struct msgform
{ long mtype;
char mtext[1000];
}msg;
int msgqid;
void server( )
{
msgqid=msgget(MSGKEY,0777|IPC_CREAT); /*创建75#消息队列*/
do
{
msgrcv(msgqid,&msg,1030,0,0); /*接收消息*/
printf(“(server)received\n”);
}while(msg.mtype!=1);
msgctl(msgqid,IPC_RMID,0); /*删除消息队列，归还资源*/
exit(0);
}
main( )
{
server( );
}
message的传送和控制并不保证完全同步，当一个程序不在激活状态的时候，它完全可能继续睡眠，造成了上面的现象，在多次send message 后才recieve message。这一点有助于理解消息传送的实现机理。
2.4 共享存储区通信
共享存储区（Share Memory）是UNIX系统中通信速度最高的一种通信机制。该机制可使若干进程共享主存中的某一个区域，且使该区域出现（映射）在多个进程的虚地址空间中。另一方面，一个进程的虚地址空间中又可连接多个共享存储区，每个共享存储区都有自己的名字。当进程间欲利用共享存储区进行通信时，必须先在主存中建立一共享存储区，然后将它附接到自己的虚地址空间上。此后，进程对该区的访问操作，与对其虚地址空间的其它部分的操作完全相同。进程之间便可通过对共享存储区中数据的读、写来进行直接通信。图示列出二个进程通过共享一个共享存储区来进行通信的例子。其中，进程A将建立的共享存储区附接到自己的AA’区域，进程B将它附接到自己的BB’区域。
#include <sys/types.h>
#include <sys/shm.h>
#include <sys/ipc.h>
#define SHMKEY 75
int shmid,i; int *addr;
void client( )
{ int i;
shmid=shmget(SHMKEY,1024,0777); /*打开共享存储区*/
addr=shmat(shmid,0,0); /*获得共享存储区首地址*/
for (i=9;i>=0;i--)
{ while (*addr!=-1);
printf("(client) sent\n");
*addr=i;
}
exit(0);
}
void server( )
{
shmid=shmget(SHMKEY,1024,0777|IPC_CREAT); /*创建共享存储区*/
addr=shmat(shmid,0,0); /*获取首地址*/
do
{
*addr=-1;
while (*addr==-1);
printf("(server) received\n");
}while (*addr);
shmctl(shmid,IPC_RMID,0); /*撤消共享存储区，归还资源*/
exit(0);
}
main( )
{
while ((i=fork( ))= =-1);
if (!i) server( );
system(“ipcs -m”);
while ((i=fork( ))= =-1);
if (!i) client( );
wait(0);
wait(0);
}
由于两种机制实现的机理和用处都不一样，难以直接进行时间上的比较。如果比较其性能，应更加全面的分析。
（1）消息队列的建立比共享区的设立消耗的资源少。前者只是一个软件上设定的问题，后者需要对硬件的操作，实现内存的映像，当然控制起来比前者复杂。如果每次都重新进行队列或共享的建立，共享区的设立没有什么优势。
（2）当消息队列和共享区建立好后，共享区的数据传输，受到了系统硬件的支持，不耗费多余的资源；而消息传递，由软件进行控制和实现，需要消耗一定的cpu的资源。从这个意义上讲，共享区更适合频繁和大量的数据传输。
（3）消息的传递，自身就带有同步的控制。当等到消息的时候，进程进入睡眠状态，不再消耗cpu资源。而共享队列如果不借助其他机制进行同步，接收数据的一方必须进行不断的查询，白白浪费了大量的cpu资源。可见，消息方式的使用更加灵活。
3 存储管理
3.1常用页面置换算法模拟
设计一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率。
1、最佳淘汰算法（OPT）
2、先进先出的算法（FIFO）
3、最近最久未使用算法（LRU）
4、最不经常使用算法（LFU）
5、最近未使用算法（NUR）
命中率＝１－页面失效次数／页地址流长度
#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,pfn,counter,time;
}pl_type;
pl_type pl[total_vp]; /*页面结构数组*/
struct pfc_struct{ /*页面控制结构*/
int pn,pfn;
struct pfc_struct *next;
};
typedef struct pfc_struct pfc_type;
pfc_type pfc[total_vp],*freepf_head,*busypf_head,*busypf_tail;
int diseffect, a[total_instruction];
int page[total_instruction], offset[total_instruction];
int initialize(int);
int FIFO(int);
int LRU(int);
int LFU(int);
int NUR(int);
int OPT(int);
int main( )
{
int s,i,j;
srand(10*getpid()); /*由于每次运行时进程号不同，故可用来作为初始化随机数队列的“种子”*/
s=(float)319*rand( )/32767/32767/2+1; //
for(i=0;i<total_instruction;i+=4) /*产生指令队列*/
{
if(s<0||s>319)
{
printf("When i==%d,Error,s==%d\n",i,s);
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",i,a[i+2],s);
}
for (i=0;i<total_instruction;i++) /*将指令序列变换成页地址流*/
{
page[i]=a[i]/10;
offset[i]=a[i]%10;
}
for(i=4;i<=32;i++) /*用户内存工作区从4个页面到32个页面*/
{
printf("---%2d page frames---\n",i);
FIFO(i);
LRU(i);
LFU(i);
NUR(i);
OPT(i);
}
return 0;
}
int initialize(total_pf) /*初始化相关数据结构*/
int total_pf; /*用户进程的内存页面数*/
{int i;
diseffect=0;
for(i=0;i<total_vp;i++)
{
pl[i].pn=i;
pl[i].pfn=INVALID; /*置页面控制结构中的页号，页面为空*/
pl[i].counter=0;
pl[i].time=-1; /*页面控制结构中的访问次数为0，时间为-1*/
}
for(i=0;i<total_pf-1;i++)
{
pfc[i].next=&pfc[i+1];
pfc[i].pfn=i;
} /*建立pfc[i-1]和pfc[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(total_pf) /*先进先出算法*/
int total_pf; /*用户进程的内存页面数*/
{
int i,j;
pfc_type *p;
initialize(total_pf); /*初始化相关页面控制用数据结构*/
busypf_head=busypf_tail=NULL; /*忙页面队列头，队列尾链接*/
for(i=0;i<total_instruction;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; /*按FIFO方式调新页面入内存页面*/
freepf_head->next=NULL;
freepf_head->pn=page[i];
pl[page[i]].pfn=freepf_head->pfn;
if(busypf_tail==NULL)
busypf_head=busypf_tail=freepf_head;
else
{
busypf_tail->next=freepf_head; /*free页面减少一个*/
busypf_tail=freepf_head;
}
freepf_head=p;
}
}
printf("FIFO:%6.4f\n",1-(float)diseffect/320);
return 0;
}
int LRU (total_pf) /*最近最久未使用算法*/
int total_pf;
{
int min,minj,i,j,present_time;
initialize(total_pf);
present_time=0;
for(i=0;i<total_instruction;i++)
{
if(pl[page[i]].pfn==INVALID) /*页面失效*/
{
diseffect++;
if(freepf_head==NULL) /*无空闲页面*/
{
min=32767;
for(j=0;j<total_vp;j++) /*找出time的最小值*/
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=-1;
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",1-(float)diseffect/320);
return 0;
}
int NUR(total_pf) /*最近未使用算法*/
int total_pf;
{ int i,j,dp,cont_flag,old_dp;
pfc_type *t;
initialize(total_pf);
dp=0;
for(i=0;i<total_instruction;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;j<total_vp;j++)
pl[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=freepf_head->next;
}
else
pl[page[i]].counter=1;
if(i%clear_period==0)
for(j=0;j<total_vp;j++)
pl[j].counter=0;
}
printf("NUR:%6.4f\n",1-(float)diseffect/320);
return 0;
}
int OPT(total_pf) /*最佳置换算法*/
int total_pf;
{int i,j, max,maxpage,d,dist[total_vp];
pfc_type *t;
initialize(total_pf);
for(i=0;i<total_instruction;i++)
{ //printf("In OPT for 1,i=%d\n",i); //i=86;i=176;206;250;220,221;192,193,194;258;274,275,276,277,278;
if(pl[page[i]].pfn==INVALID) /*页面失效*/
{
diseffect++;
if(freepf_head==NULL) /*无空闲页面*/
{for(j=0;j<total_vp;j++)
if(pl[j].pfn!=INVALID) dist[j]=32767; /* 最大"距离" */
else dist[j]=0;
d=1;
for(j=i+1;j<total_instruction;j++)
{
if(pl[page[j]].pfn!=INVALID)
dist[page[j]]=d;
d++;
}
max=-1;
for(j=0;j<total_vp;j++)
if(max<dist[j])
{
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",1-(float)diseffect/320);
return 0;
}
int LFU(total_pf) /*最不经常使用置换法*/
int total_pf;
{
int i,j,min,minpage;
pfc_type *t;
initialize(total_pf);
for(i=0;i<total_instruction;i++)
{ if(pl[page[i]].pfn==INVALID) /*页面失效*/
{ diseffect++;
if(freepf_head==NULL) /*无空闲页面*/
{ min=32767;
for(j=0;j<total_vp;j++)
{if(min>pl[j].counter&&pl[j].pfn!=INVALID)
{
min=pl[j].counter;
minpage=j;
}
pl[j].counter=0;
}
freepf_head=&pfc[pl[minpage].pfn];
pl[minpage].pfn=INVALID;
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++;
}
printf("LFU:%6.4f\n",1-(float)diseffect/320);
return 0;
}
运行结果
4 page frams
FIFO: 0.7312
LRU: 0.7094
LFU: 0.5531
NUR: 0.7688
OPT: 0.9750
5 page frams
…………
OPT算法在执行过程中可能会发生错误，OPT算法本身实现就不现实，它只是一种理想算法，它是假设将来主存中的页面调度情况与过去一段时间内主存中的调度情况是相同的，这种假设并不总是正确的，因此在执行过程中会出现错误。