实现操作系统的主要进程调度算法：先来先服务(FCFS)算法，短进程优先(SPN)算法和时间片轮转(RR)算法。
(1)先来先服务调度算法（FCFS）
该算法采用非剥夺策略，算法按照进程提交或进程变为就绪状态的先后次序，分派 CPU。当前进程占用CPU，直到执行完或阻塞，才出让CPU（非抢占方式）。在进程唤醒后（如I/O 完成），并不立即恢复执行，通常等到当前进程出让CPU。这是最简单的调度算法，比较有利于长进程，而不利于短进程，有利于CPU 繁忙的进程，而不利于I/O 繁忙的进程。
(2)短进程优先调度算法（SPN）
该算法也采用非剥夺策略，对预计执行时间短的进程优先分派处理机。通常后来的短进程不抢先正在执行的进程。相比FCFS 算法，该算法可改善平均周转时间和平均带权周转时间，缩短进程的等待时间，提高系统的吞吐量。缺点是对长进程非常不利，可能长时间得不到执行，且未能依据进程的紧迫程度来划分执行的优先级，以及难以准确估计进程的执行时间，从而影响调度性能。
(3)时间片轮转算法（RR）
该算法采用剥夺策略。让就绪进程以FCFS 的方式按时间片轮流使用CPU 的调度方式，即将系统中所有的就绪进程按照FCFS 原则，排成一个队列，每次调度时将CPU 分派给队首进程，让其执行一个时间片，时间片的长度从几个ms 到几百ms。在一个时间片结束时，发生时钟中断，调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程，进程可以未使用完一个时间片，就出让CPU（如阻塞）。时间片轮转调度算法的特点是简单易行、平均响应时间短，但不利于处理紧急作业。在时间片轮转算法中，时间片的大小对系统性能的影响很大，因此时间片的大小应选择恰当。
使用C语言实现FCFS,SPN,RR算法：
#include<stdio.h>#include<stdlib.h>//先来先服务，最短作业优先算法结构体typedef struct process_FCFS{ char name; //进程名 float arrivetime; //到达时间 float servetime; //服务时间 float finishtime; //完成时间 float roundtime; //周转时间 float daiquantime; //带权周转时间 struct process_FCFS *link;//结构体指针}FCFS; //时间片轮转算法结构体typedef struct stud{ char name; //进程名 float arrive; //进程到达时间 float run; //进程运行时间 float rest; //运行进程剩余时间 char *state; //进程状态 struct stud *next; //结构体指针}stud;FCFS *p,*q,*head=NULL;struct process_FCFS a[100];float avrRoundtime;//平均周转时间float avrDaiquantime;//平均带权周转时间FCFS initial(struct process_FCFS a[],int n);void print(struct process_FCFS a[],int n);void Fcfs(struct process_FCFS a[],int n); //FCFS算法void SPN(struct process_FCFS a[],int n); //SPN算法struct process_FCFS *sortarrivetime(struct process_FCFS a[],int n); //到达时间冒泡排序struct process_FCFS *sortservetime(struct process_FCFS a[],int n); //服务时间冒泡排序struct stud *create(int &a); //初始化创建时间片轮转算法调度队列void RR(struct stud *head, int &a); //时间片轮转RR算法//按到达时间进行冒泡排序struct process_FCFS *sortarrivetime(struct process_FCFS a[],int n){ int i,j; struct process_FCFS t; int flag; for(i=1;i<n;i++) { flag=0; for(j=0;j<n-i;j++) { if(a[j].arrivetime>a[j+1].arrivetime) //将到达时间短的交换到前边 { t=a[j]; a[j]=a[j+1]; a[j+1]=t; flag=1;//交换 } } if(flag==0)//如果一趟排序中没发生任何交换，则排序结束 { break; } } return a; //返回排序后进程数组}//按服务时间进行冒泡排序struct process_FCFS *sortservetime(struct process_FCFS a[],int n){ int i,j; struct process_FCFS t; int flag; for(i=1;i<n;i++) { flag=0; for(j=1;j<n-i;j++) { if(a[j].servetime>a[j+1].servetime) //将到达时间短的交换到前边 { t=a[j]; a[j]=a[j+1]; a[j+1]=t; flag=1;//交换 } } if(flag==0)//如果一趟排序中没发生任何交换，则排序结束 { break; } } return a; //返回排序后进程数组}//先来先服务算法void Fcfs(struct process_FCFS a[],int n,float &t1, float &t2){ int i; a[0].finishtime=a[0].arrivetime+a[0].servetime; //完成时间=到达时间-服务时间 a[0].roundtime=a[0].finishtime-a[0].arrivetime; //周转时间=完成时间-提交时间 a[0].daiquantime=a[0].roundtime/a[0].servetime; //带权时间=周转时间/服务时间 for(i=1;i<n;i++) { if(a[i].arrivetime<a[i-1].finishtime) //当前到达时间在上一个作业结束时间之前 { a[i].finishtime=a[i-1].finishtime+a[i].servetime; //完成时间=上一个完成时间+服务时间 a[i].roundtime=a[i].finishtime-a[i].arrivetime; //周转时间=完成时间-到达时间 a[i].daiquantime=a[i].roundtime/a[i].servetime; //带权时间=周转时间/服务时间 } else //当前到达时间在上一个作业结束时间之后 { a[i].finishtime=a[i].arrivetime+a[i].servetime; a[i].roundtime=a[i].finishtime-a[i].arrivetime; a[i].daiquantime=a[i].roundtime/a[i].servetime; } } for(int i=0;i<n;i++) { printf("进程名：%c",a[i].name); printf("到达时间：%f",a[i].arrivetime); printf("服务时间：%f",a[i].servetime); printf("完成时间：%f",a[i].finishtime); printf("周转时间：%f",a[i].roundtime); printf("带权周转时间：%f",a[i].daiquantime); printf("\n"); t1 += a[i].roundtime; t2 += a[i].daiquantime; }}//短作业优先算法void SPN(struct process_FCFS a[],int n,float &t1, float &t2){ int i; a[0].finishtime=a[0].arrivetime+a[0].servetime; //完成时间=到达时间-服务时间 a[0].roundtime=a[0].finishtime-a[0].arrivetime; //周转时间=完成时间-提交时间 a[0].daiquantime=a[0].roundtime/a[0].servetime; //带权时间=周转时间/服务时间 for(i=1;i<n;i++) { if(a[i].arrivetime<a[i-1].finishtime) //当前到达时间在上一个作业结束时间之前 { a[i].finishtime=a[i-1].finishtime+a[i].servetime; //完成时间=上一个完成时间+服务时间 a[i].roundtime=a[i].finishtime-a[i].arrivetime; //周转时间=完成时间-到达时间 a[i].daiquantime=a[i].roundtime/a[i].servetime; //带权时间=周转时间/服务时间 } else //当前到达时间在上一个作业结束时间之后 { a[i].finishtime=a[i].arrivetime+a[i].servetime; a[i].roundtime=a[i].finishtime-a[i].arrivetime; a[i].daiquantime=a[i].roundtime/a[i].servetime; } } for(int i=0;i<n;i++) { printf("进程名：%c",a[i].name); printf("到达时间：%f",a[i].arrivetime); printf("服务时间：%f",a[i].servetime); printf("完成时间：%f",a[i].finishtime); printf("周转时间：%f",a[i].roundtime); printf("带权周转时间：%f",a[i].daiquantime); printf("\n"); t1 += a[i].roundtime; t2 += a[i].daiquantime; }}//打印输出函数void print(struct process_FCFS a[],int n){ int i; for(i=0;i<n;i++) { printf("进程名：%c",a[i].name); printf("到达时间：%f",a[i].arrivetime); printf("服务时间：%f",a[i].servetime); printf("完成时间：%f",a[i].finishtime); printf("周转时间：%f",a[i].roundtime); printf("带权周转时间：%f",a[i].daiquantime); printf("\n"); }}//初始化创建调度队列struct stud *create(int &a){ int i; struct stud *head, *rear,*p,*q,*t; head=rear=NULL; for(i=0;i<a;i++) { p=(struct stud*)malloc(sizeof(struct stud)); printf("%d 进程名: ",i+1); scanf("%s",&p->name); printf("到达时间："); scanf("%f",&p->arrive); printf("服务时间："); scanf("%f",&p->run); p->rest = p->run; p->state = "ready"; if(rear == NULL) { head = p; p->next = NULL; rear = p; } else { t = NULL; q = head; while(q && q->arrive < p->arrive) { t = q; q = q->next; } if(q == head) { p->next = head; head = p; } else if(t == rear) { rear->next = p; p->next = NULL; rear = p; } else { t->next = p; p->next = q; } } } return head;}//时间片轮转算法void RR(struct stud *head, int &a){ struct stud *p,*t,*r; float slice = 0.0f; float temp = 0.0f; //缓存最后一个正数rest float m1 = 0.0f , m2 = 0.0f, n1 = 0.0f, n2 = 0.0f; float sum_zhouzhuan = 0.0f, sum_daiquan = 0.0f; //所有进程总周转时间，所有进程总带权周转时间 float zhouzhuan = 0.0f, daiquan = 0.0f; //周转时间，带权周转时间 float avr_zhouzhuan = 0.0f, avr_daiquan = 0.0f; printf("请输入时间块大小: "); scanf("%f",&slice); while(head != NULL) //队列非空，循环 { r = p = head; while(p != NULL) //遍历队列，结束后跳出当前循环 { t = head; m1 += slice; temp = p->rest; p->rest = p->rest - slice; //剩余时间 p->state = "running"; if(p->rest <= 0) { m1 = m1 - slice + temp; //进程完成时间 zhouzhuan = m1 - p->arrive; //进程周转时间 daiquan = zhouzhuan / (p->run); //进程带权周转时间 sum_zhouzhuan += zhouzhuan; //所有进程周转时间之和 sum_daiquan += daiquan; p->rest = 0; } printf("\n-----------------------------------------------\n"); printf("name\tarrive\trun\trest\tstate\n"); while(t != NULL) { printf("%d\t%f\t%f\t%f\t%s\n",t->name,t->arrive,t->run,t->rest,t->state); t = t->next; } if(p->rest == 0)/*判断是否删除结点*/ { //finishtime += if(p == head)/*删除头结点*/ { head = p->next; free(p); p = head; } else { r->next = p->next; p = r->next; r = p; } } else { r = p; p->state = "ready"; p = p->next; } } } printf("\n总周转时间： "); printf("%f", sum_zhouzhuan); printf("\n总带权周转时间： "); printf("%f\n", sum_daiquan); avr_zhouzhuan = sum_zhouzhuan / a; avr_daiquan = sum_daiquan / a; printf("\n平均周转时间： "); printf("%f",avr_zhouzhuan); printf("\n平均带权周转时间： "); printf("%f\n",avr_daiquan);}//主函数void main(){ float t1 = 0.0f; //总周转时间 float t2 = 0.0f; //总带权周转时间 float avr_t1 = 0.0f; //平均周转时间 float avr_t2 = 0.0f; //平均带权周转时间 int n,i; char select = ' '; //选择算法变量标识 while (select != 'e' && select != 'E') //不为退出标识，保持循环 { printf("请选择算法：\na.先来先服务算法\nb.短作业优先算法\nc.时间片轮转算法\ne.退出程序\n输入选择字符标号: "); scanf("%c",&select); if (select == 'a' || select == 'A') //先来先服务算法 { printf("\n\n=================先来先服务算法================\n\n"); printf("请输入进程数："); scanf("%d",&n); for(i=0;i<n;i++) { printf("%d 进程名: ",i+1); scanf("%s",&a[i].name); printf("到达时间："); scanf("%f",&a[i].arrivetime); printf("服务时间："); scanf("%f",&a[i].servetime); } sortarrivetime(a, n); //冒泡排序 Fcfs(a,n,t1,t2); //先来先服务算法 avr_t1 = t1 / n; avr_t2 = t2 / n; printf("\n"); printf("平均周转时间为：%f \n", avr_t1); printf("平均带权周转时间为：%f \n", avr_t2); } else if (select == 'b' || select == 'B') //短作业优先算法 { printf("\n\n=================短作业优先算法================\n\n"); printf("请输入进程数："); scanf("%d",&n); for(i=0;i<n;i++) { printf("%d 进程名: ",i+1); scanf("%s",&a[i].name); printf("到达时间："); scanf("%f",&a[i].arrivetime); printf("服务时间："); scanf("%f",&a[i].servetime); } sortservetime(a, n); //冒泡排序 SPN(a,n,t1,t2); //短作业优先算法 avr_t1 = t1 / n; avr_t2 = t2 / n; printf("\n"); printf("平均周转时间为：%f \n", avr_t1); printf("平均带权周转时间为：%f \n", avr_t2); } else if (select == 'c' || select == 'C') //时间片轮转算法 { printf("\n\n=================时间片轮转算法================\n\n"); int a; printf("请输入进程数: "); scanf("%d",&a); struct stud *head; head = create(a); RR(head, a) ; } } system("pause");}联系客服
