先来先服务算法实验报告

1、程序中使用的数据结构及符号说明

(1)设置一个队首指针head ，用来指出最先进入系统中的进程，各就绪进程通过链接指针链成一个队列。 struct process *head；

head=(struct process *)malloc(L); /*头结点的创建与定义*/ (2)每个进程由进程控制块（PCB）来标识，进程控制块的内容如下： 进程名 struct process{

链接指针 要求运行时间 到达时间 进程状态 char name; /* 进程名 */

char status; /* 进程状态 */ int num; /* 进程号*/ int t1; /* 到达时间 */ int t2; /* 要求运行时间 */

struct process *next; /* 链接指针 */

};

(3)#define L sizeof(struct process) /* 宏定义 */

struct process *creat(struct process *h,struct process *pro) /*创建进程*/ int counter; /*全局变量counter用于计算链表中节点的个数*/ int N; /*全局变量N代表需要运行的总进程数*/

2、程序实现概述：

(1)creat()函数:即创建进程，定义一个头结点h，开始队列为空，将第一个进程直接插

入队列的队尾，如果只有一个节点，则进程创建完毕，进行下一步操作；如果有多个进程，插入时按照各进程的到达时间由大到小排序，排序的方法是：首先定义三个指针p0,p1，p2，令p1指向队列的第一个元素，p0指向待插入的节点，如果p1->next!=NULL并且p1->t1<=p0->t1，则令p2=p1,

p1=p1->next，直到p1->next=NULL或者是p1->t1>p0->t1,此时判断p1->t1与p0->t1的大小，如果p1->t1<=p0->t1，则把p0插到p1的后面，如果p1->t1>p0->t1，则把p0插到p1的前面，当所有的进程都创建完毕时，队列中的进程就是按照到达时间依次减小的。返回队首指针h。进行下一步操作。

(2)print()函数：定义一个指针p，令p指向队列的的第一个节点，输出p的所有内容，

p->t1减1,再输出p的所有内容，当p2->t1=0时，令p->status=’C’，即将进 程的状态置为完成，输出p的所有内容，p指针后移，即p=p->next,重复上述 步骤，输出队列中所有就绪进程的执行情况。

(3)main()函数：创建头结点，定义一个头指针head,调用creat()函数，创建进程，再调

用print()函数输出各进程的运行情况。

3、程序主要代码： #include #include

1

(1)创建进程主要代码如下：

struct process *creat(struct process *h,struct while(p1->t2!=0)/*进程的要求运行时间不等于0*/ { p1->t2--;

if(p1->t2==0)/*进程的要求运行时间不等于0*/ process *pro) /*创建进程*/ {struct process *p0,*p1,*p2; int a,b; int j=1,i=1;

char name,status;int t1,t2,num;

while(counterp1=pro=(struct process *)malloc(L); scanf(\"%s %d\

t1=i++; /*由程序指定进程的到达时间*/ if(j>=5) {j=1;} /*进程要求运行时间小于5*/ t2=j++; t2+=1;/*由程序指定进程的到达时间*/ pro->name=name;pro->status='R'; pro->t1=t1; pro->t2=t2; pro->num=num;

printf(\"task number:%d,name:%c,status:%c,

arrivaltime:%d,servicetime:%d\\n\pro->name,pro->status,pro->t1,pro->t2); p1=h; /*p1指向第一个节点*/ p0=pro; /*p0指向待插入节点*/ if(counter==1) /*没有结点*/

{h=p0;p0->next=NULL; /*把节点插入队尾*/} else

{while(p0->t1>p1->t1&&p1->next!=NULL) {p2=p1;

p1=p1->next; /*p1指针后移*/} }

if(p0->t1<=p1->t1) {if(h==p1) h=p0; else p2->next=p1;

p0->next=p1; } /*把节点插到p1前面*/ else

{ p1->next=p0;p0->next=NULL; } /*把节点插到p1后面*/} return(h);}

(2)输出进程运行情况函数代码如下： void print(struct process *Q) {int j=1;

struct process *p1; p1=Q; if(Q!=NULL) do{

4、实验结果

{p1->status=’C’;

printf(\"%d %d %c %c%d\\n\

p1->name,,p1->status,p1->t2); /*完成状态为C*/} else

printf(\"%d %d %c %c%d\\n\p1->name,,p1->status,p1->t2); j++;} p1=p1->next;}while(p1!=NULL);}

(3)主函数代码如下： main()/*主函数*/ { int i;

struct process *head,*p,*q; /* 队首指针head ，用来指出最先进入系统中的进程 */

head=(struct process *)malloc(L); /*创建头结点*/ head=NULL;p=NULL;printf(\"\\n\"); printf(\"******************FCFS scheduling arithmetic status*****************\\n\\n\"); printf(\"input the total number of the task:\"); scanf(\"%d\输入总进程数*/printf(\"\\n\"); printf(\"please input the following information:\"); printf(\"process name,process number\\n\\n\"); q=creat(head,p);/*调用creat函数*/ printf(\"\\nAll the task is ready!\"); printf(\"Press Enter to continue.\"); getch();clrscr();printf(\"\\n\");

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

printf(\"* present process process process leaving*\\n\");

printf(\" * running service*\\n\"); printf(\" * ime\\number\\name\\status\\time *\\n\");

printf(\"********************************\\n\"); printf(\" -----------------------------------------------\\n\"); print(q); /*调用print函数*/

printf(\"********************************\\n\"); printf(\"--------------------------------------------------\"); free(head); /*释放内存空间*/ free(p); free(q);getch(); }

2

以系统中有五个进程为例，进程名和进程号如下所示: 进程号 进程名 1 A 2 C 3 E 4 F 5 S

运行环境为Win-TC，运行结果如下：

3