操作系统进程调度算法 先来先服务 短作业优先 时间片轮转 优先级

资源内容介绍

操作系统是管理计算机硬件资源并为用户程序提供服务的核心软件，其中进程调度是其核心功能之一。本文将深入探讨四种常见的进程调度算法：先来先服务（FCFS）、短作业优先（SJF）、时间片轮转（RR）以及优先级调度。1. **先来先服务（FCFS）调度算法**： FCFS是最简单的调度算法，它按照进程到达的顺序进行服务。当一个进程被创建并进入就绪队列，它会等待前面的进程执行完毕才能获得CPU。这种算法易于实现，但可能导致长进程等待时间过长，即饥饿现象，不利于系统效率。2. **短作业优先（SJF）调度算法**： SJF旨在减少平均周转时间和平均等待时间，它优先选择预计运行时间最短的进程。短进程能更快完成，从而提高系统效率。然而，SJF可能导致长进程长时间等待，同样可能产生饥饿问题。另外，SJF在实际应用中需考虑进程预知其执行时间的困难，常采用静态或动态预测。3. **时间片轮转（RR）调度算法**： RR通过为每个进程分配固定时间片来实现调度，当时间片用尽，进程被强制切换到就绪队列末尾。这种方法可以确保所有进程在一定时间内得到执行，适合多用户交互环境。时间片大小对系统性能有很大影响，过大可能导致上下文切换开销增大，过小则频繁切换影响效率。4. **优先级调度算法**： 优先级调度根据进程的优先级决定执行顺序。优先级高的进程优先获取CPU，可以是抢占式（高优先级进程到来时可中断低优先级进程）或非抢占式。该算法灵活，适用于不同场景，但同样可能出现优先级反转和优先级继承等问题，需要适当策略调整。这些调度算法各有优缺点，实际操作系统往往结合多种策略，例如Linux中的混合调度器，既包含时间片轮转，也采用优先级调度，以平衡响应速度和系统效率。了解和掌握这些基本调度算法，有助于理解和优化操作系统性能，提升用户体验。在实际操作中，可以根据系统需求和工作负载情况选择合适的调度策略。

#include <stdio.h>#include <malloc.h>#include <stdlib.h>#include <assert.h>#include <windows.h>#include <string.h>struct pcb{int come_time;int run_time;int VIP;char name[10];struct pcb *next;};typedef struct pcb PCB;void *creat(int n);void Firstcome_Firstserve(PCB *head);void Menue(PCB *head,int n);void*My_Copy(PCB *head);void Print( PCB *head,int len);void Shortwork_Firstserve(PCB *head);void TimeTurn_Firstserve(PCB *head,int timeturn,int n);void VIP_Firstserve(PCB *head);/************************************************************************//* *创建进程链表* *//************************************************************************/ //2010_10_24void *creat(int n){PCB *head,*p,*q;assert (head=(PCB*)malloc(sizeof(PCB))); p=head;p->next=NULL;while(n--){p=head;if( ( q=(PCB*)malloc(sizeof(PCB))) == NULL){printf("ERROR!\n");exit(0);}puts("进程名:"); getchar(); gets(q->name);puts("进程开始时间"); scanf("%d",&q->come_time);puts("进程运行时间"); scanf("%d",&q->run_time);puts("优先级");scanf("%d",&q->VIP); if(p->next==NULL) //在插入节点时排序{q->next=NULL;p->next=q;}else{while (p->next!=NULL && q->come_time >p->next->come_time ){p=p->next;}q->next=p->next;p->next=q;} //在插入节点时排序}return head;}/************************************************************************//************************************************************************/void *My_Copy(PCB *head1){PCB *head2=NULL;//新链表头结点PCB *p2=NULL;//PCB *p1=head1->next;PCB *node=NULL;assert(head2=(PCB*)malloc(sizeof(PCB)));p2=head2;while(p1!=NULL){assert(node = (PCB*)malloc(sizeof(PCB)));strcpy(node->name,p1->name); //拷贝进程node->come_time=p1->come_time;node->run_time=p1->run_time;node->VIP=p1->VIP;//拷贝进程node->next=NULL; p2->next=node;p2=p2->next;//指针后移p1=p1->next;}return head2;}/********************************打印输出*****************************************/void Print( PCB *head,int len){int i=0;head=head->next;puts("进程名 到达时间 运行时间 优先级");for(i=0;i<len;i++,head=head->next){printf("%5s %10d %10d %10d\n",head->name,head->come_time,head->run_time,head->VIP);}}/************************************************************************//* *先来先服务* *//************************************************************************/ //2010_10_28void Firstcome_Firstserve(PCB *head){PCB *Head=My_Copy(head);int counter=1;PCB *h=Head->next;PCB *p;int time; //进程结束时间,int time2;while(h!=NULL){if(h==Head->next){puts("");printf("进程:%-5s正在运行，到达时间:%-5d,运行时间:%-5d,优先级:%-5d\n",h->name,h->come_time,h->run_time,h->VIP);}else{time=p->run_time+p->come_time ;if(time < h->come_time) //p结束但是h还未到达 h的开始时间就是到达时间{puts("");//Sleep(p->run_time*1000); 2010_06修改 ：优化while(p->run_time){printf("正在执行 %d \r",p->run_time); p->run_time--;Sleep(1000);}printf("执行结束！\n");time2=h->come_time-time;printf("等待下一个进程");while(time2>0){printf(". ");Sleep(1000);time2--;}puts("");printf("进程:%-5s正在运行，到达时间:%-5d,运行时间:%-5d,优先级:%d\n",h->name,h->come_time,h->run_time,h->VIP);}elseif(time == h->come_time)//p结束而且h刚好到达{//Sleep(p->run_time*1000);2010_06修改 ：优化while(p->run_time){printf("正在执行 %d \r",p->run_time); p->run_time--;Sleep(1000);}printf("执行结束！\n");puts("");printf("进程:%-5s正在运行，到达时间:%-5d,运行时间:%-5d,优先级:%d\n",h->name,h->come_time,h->run_time,h->VIP);}elseif(time > h->come_time)//p结束前h已到达{puts("");time2=p->run_time-(time-h->come_time); //p从到来至h进程等待钱执行时间while(time2){printf("正在执行 %d \r",time2--); Sleep(1000);}printf("进程:%-5s等待\n",h->name);time2=time-h->come_time;while(time2) //p从h等待到完成市时间{printf("正在执行 %d \r",time2--); Sleep(1000);}printf("进程:%-5s正在运行，到达时间:%-5d,运行时间:%-5d,优先级:%d\n",h->name,h->come_time,h->run_time,h->VIP);}}counter++;p=h;h=h->next;}}/************************************************************************//* *短作业优先* *//************************************************************************/void Shortwork_Firstserve(PCB *head) //非抢占式{PCB *Head=My_Copy(head);PCB *Head_Link;//建新队列PCB *Link,*node;//建节点，在新队列中会用到。PCB *flg;//标记指针的位置PCB *p,*q;static int flag0;int time_over; //进程结束时间int time1;p = Head;q = p->next;assert(Head_Link = (PCB*)malloc(sizeof(PCB))); //新队列的头结点的创建Head_Link->next = NULL; while(q->next != NULL)///////////|| Head_Link ->next != NULL 2010_15 { //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////if(q==Head->next){if(flag0==0){printf("进程:%-5s正在运行，到达时间:%-5d,运行时间:%-5d,优先级:%d\n",q->name,q->come_time,q->run_time,q->VIP);time_over=q->run_time;while(time_over) { printf("正在执行 %d \r",time_over--); Sleep(1000);}puts("执行完毕！"); flag0++;}// end of if(flag0==0) else if(flag0==1){if(q->next->come_time > q->run_time) //等待下一个进程{time1 = q->next->come_time - q->run_time; //等待时间puts("Wait!");while(time1){printf(". ");time1--;Sleep(1000);}printf("进程:%-5s正在运行，到达时间:%-5d,运行时间:%-5d,优先级:%d\n",q->next->name,q->next->come_time,q->next->run_time,q->next->VIP);time_over = q->next->run_time;while(time_over){printf("正在执行 %d \r",time_over); time_over--;Sleep(1000);}puts("执行完毕！");p = q;q = q->next;} //end of if (q->next->come_time > q->run_time) else if(q->next->come_time <= q->run_time) //将 在q进程执行完之前，就进入的进程入队。{time_over = q->run_time;while((q->next != NULL) && (q->next->come_time < time_over)){assert(node=(PCB*)malloc(sizeof(PCB))); //建节点node->come_time=q->next->come_time;//拷贝节点strcpy(node->name,q->next->name);//拷贝节点node->run_time=q->next->run_time;//拷贝节点node->VIP=q->next->VIP;//拷贝节点//插入 法按短作业升序 插入节点，if(Head_Link->next == NULL) {flg = q;//标记node->next = NULL;Head_Link->next = node;}else {if(node->run_time < Head_Link->next->run_time){flg = q;node->next = Head_Link->next;Head_Link->next = node;}else {Link = Head_Link->next;//while((Link->next != NULL) && (node->run_time > Link->next->run_time)) 2010_11_15修改while((Link->next != NULL) && (node->run_time > Link->next->run_time)){