实现操作系统的主要进程调度算法：先来先服务(FCFS)算法，短进程优先(SPN)算法和时间片轮转(RR)算法。


(1)先来先服务调度算法（FCFS）

该算法采用非剥夺策略，算法按照进程提交或进程变为就绪状态的先后次序，分派 CPU。当前进程占用CPU，直到执行完或阻塞，才出让CPU（非抢占方式）。在进程唤醒后（如I/O 完成），并不立即恢复执行，通常等到当前进程出让CPU。这是最简单的调度算法，比较有利于长进程，而不利于短进程，有利于CPU 繁忙的进程，而不利于I/O 繁忙的进程。


【算法与数据结构|进程调度--FCFS,SPN,RR算法的实现】(2)短进程优先调度算法（SPN）
该算法也采用非剥夺策略，对预计执行时间短的进程优先分派处理机。通常后来的短进程不抢先正在执行的进程。相比FCFS 算法，该算法可改善平均周转时间和平均带权周转时间，缩短进程的等待时间，提高系统的吞吐量。缺点是对长进程非常不利，可能长时间得不到执行，且未能依据进程的紧迫程度来划分执行的优先级，以及难以准确估计进程的执行时间，从而影响调度性能。


(3)时间片轮转算法（RR）
该算法采用剥夺策略。让就绪进程以FCFS 的方式按时间片轮流使用CPU 的调度方式，即将系统中所有的就绪进程按照FCFS 原则，排成一个队列，每次调度时将CPU 分派给队首进程，让其执行一个时间片，时间片的长度从几个ms 到几百ms。在一个时间片结束时，发生时钟中断，调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程，进程可以未使用完一个时间片，就出让CPU（如阻塞）。时间片轮转调度算法的特点是简单易行、平均响应时间短，但不利于处理紧急作业。在时间片轮转算法中，时间片的大小对系统性能的影响很大，因此时间片的大小应选择恰当。


使用C语言实现FCFS,SPN,RR算法：

#include #include//先来先服务，最短作业优先算法结构体 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; ia[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; ia[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; iarrive); 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