操作系统|操作系统四种进程调度算法C/c++语言(先来先服务（FCFS）短作业优先算法（SJF）优先级调度算法（PSA）时间片轮转算法（RR）) c#|操作系统|c++

四种算法介绍 1. 先来先服务算法（FCFS）
FCFS是最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，系统将按照作业到达的先后次序来进行调度，或者说它是优先考虑在系统中等待时间最长的作业，而不管该作业所需执行时间的长短，从后备作业队列中选择几个最先进入该队列的作业，将它们调入内存，为它们分配资源和创建进程。然后把它放入就绪队列。当在进程调度中采用FCFS算法时，每次调度是从就绪的进程队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后，进程调度程序才将处理机分配给其它进程。顺便说明，FCFS算法在单处理机系统中已很少作为主调度算法，但经常把它与其它调度算法相结合使用，形成- -种更为有效的调度算法。例如，可以在系统中按进程的优先级
设置多个队列，每个优先级- -个队列，其中每一个队列的调度都基于FCFS算法。
2. 短作业优先调度算法（SJF）：
由于在实际情况中，短作业(进程)占有很大比例，为了能使它们能比长作业优先执行，而产生了短作业优先调度算法。
(1)短作业优先算法SJF算法是以作业的长短来计算优先级，作业越短，其优先级越高。作业的长短是以作业所要求的运行时间来衡量的。SJF 算法可以分别用于作业调度和进程调度。在把短作业优先调度算法用于作业调度时，它将从外存的作业后备队列中选择若干个估计运行时间最短的作业，优先将它们调入内存运行。
(2)短作业优先算法的缺点:
SJF调度算法较之FCFS算法有了明显的改进，但仍然存在不容忽视的缺点:
(1)必须预知作业的运行时间。在采用这种算法时，要先知道每个作业的运行时间。即使是程序员也很难准确估计作业的运行时间，如果估计过低，系统就可能按估计的时间终止作业的运行，但此时作业并未完成，故一般都会偏长估计。
(2)对长作业非常不利，长作业的周转时间会明显地增长。更严重的是，该算法完全忽视作业的等待时间，可能使作业等待时间过长，出现饥饿现象。
(3)在采用FCFS算法时，人----机无法实现交互。
(4)该调度算法完全未考虑作业的紧迫程度，故不能保证紧迫性作业能得到及时处理。
3. 时间片轮转调度算法(RR)
在轮转(RR)法中，系统将所有的就绪进程按FCFS策略排成-一个就绪队列。系统可设置每隔一定时间(如30 ms)便产生一次中断，去激活进程调度程序进行调度，把CPU分配给队首进程，并令其执行一个时间片。当它运行完毕后，又把处理机分配给就绪队列中新的队首进程，也让它执行-一个时间片。这样，就可以保证就绪队列中的所有进程在确定的时间段内，都能获得一个时间片的处理机时间。
4. 优先级调度算法(非抢占式)
我们可以这样来看作业的优先级，对于先来先服务调度算法，作业的等待时间就是作业的优先级，等待时间越长，其优先级越高。对于短作业优先调度算法，作业的长短就是作业的优先级，作业所需运行的时间越短，其优先级越高。但上述两种优先级都不能反映作业的紧迫程度。而在优先级调度算法中，则是基于作业的紧迫程度，由外部赋予作业相应的优先级，调度算法是根据该优先级进行调度的。这样就可以保证紧迫性作业优先运行。优先级调度算法可作为作业调度算法，也可作为进程调度算法。当把该算法用于作业调度时，系统是从后备队列中选择若千个优先级最高的作业装入内存。
直接代码（实验原因封装在一块）
VS2019运行

#if 1#include #include using namespace std; #define TIME_SLICE 2typedef struct PCB { char name[10]; //此为进程id char state; //进程状态w/r int Arrivetime; //进程到达时间 int BeginTime; //进程开始时间 int FinishTime; //进程结束时间 intServerTime; //进程服务时间 float wholeTime; //周转时间 float Weight_wholetime; //带权周转时间 double Average_wholeTime; //平均周转时间 double Average_weight_wholetime; //带权平均周转时间 intRunTime; //已经占用cpu时间 intNeedTime; //还需要cpu时间 intPrio; //优先级 struct PCB* next; }pcb, * Pcb; int Proc_Num = 0; //进程数目void head_Show(Pcb proc)//输入打印 { assert(proc != NULL); printf("PCB_ID优先级数到达时间服务时间\n"); while (proc != NULL) { printf("%6s%6d%6d%6d\n", proc->name, proc->Prio, proc->Arrivetime, proc->ServerTime); proc = proc->next; } } void Show(Pcb proc) { assert(proc != NULL); double sum_wholeTime = 0; double sum_weight_wholetime = 0; pcb* p = proc; while (p != NULL) { sum_wholeTime += p->wholeTime; sum_weight_wholetime += p->Weight_wholetime; p = p->next; } double Average_wholeTim = sum_wholeTime / Proc_Num; double Average_weight_wholetime = sum_weight_wholetime / Proc_Num; printf("PCB_ID到达时间开始时间服务时间完成时间周转时间带权周转时间\n"); while (proc != NULL) { printf("%6s%6d%6d%6d%6d%8.1f%8.2f\n", proc->name, proc->Arrivetime, proc->BeginTime, proc->ServerTime, proc->FinishTime, proc->wholeTime, proc->Weight_wholetime); proc = proc->next; } printf("平均周转时间平均带权周转时间\n"); printf("%10.2f%10.2f\n", Average_wholeTim, Average_weight_wholetime); } Pcb PCB_Create()//创建输入链表 { cout << "请输入进程个数:"; cin >> Proc_Num; pcb* _head = NULL; pcb* _tail = NULL; if (Proc_Num > 6000) { return NULL; } cout << "请输入PCB名称、优先级、到达时间、服务时间" << endl; for (int i = 1; i <= Proc_Num; i++) { pcb* new_proc = (pcb*)malloc(sizeof(pcb)); assert(NULL != new_proc); cin >> new_proc->name >> new_proc->Prio >> new_proc->Arrivetime >> new_proc->ServerTime; new_proc->next = NULL; if (NULL == _head) { _tail = new_proc; _head = new_proc; } else { _tail->next = new_proc; _tail = new_proc; } } return _head; } Pcb Sort_Arrivetime(Pcb list)//时间先后顺序排序 { assert(NULL != list); pcb* new_head = (pcb*)malloc(sizeof(pcb)); assert(NULL != new_head); new_head->Arrivetime = 0; new_head->ServerTime = 0; new_head->next = NULL; pcb* head = NULL; while (list != NULL) { pcb* cur = list; list = list->next; cur->next = NULL; if (new_head->next == NULL) { new_head->next = cur; } else { pcb* ptr = new_head; for (ptr; ptr->next != nullptr; ptr = ptr->next); if (cur->Arrivetime >= ptr->Arrivetime) { ptr->next = cur; } else { pcb* p = new_head; while (cur->Arrivetime > p->next->Arrivetime) { p = p->next; } cur->next = p->next; p->next = cur; } } } return new_head->next; } Pcb Sort_Shortjob(Pcb list)//短作业排序链表 { assert(NULL != list); pcb* new_head = (pcb*)malloc(sizeof(pcb)); assert(NULL != new_head); new_head->Arrivetime = 0; new_head->ServerTime = 0; new_head->next = NULL; pcb* head = NULL; while (list != NULL) { pcb* cur = list; list = list->next; cur->next = NULL; if (new_head->next == NULL) { new_head->next = cur; } else { pcb* ptr = new_head; for (ptr; ptr->next != nullptr; ptr = ptr->next); if (cur->ServerTime >= ptr->ServerTime) { ptr->next = cur; } else { pcb* p = new_head; while (cur->ServerTime > p->next->ServerTime) { p = p->next; } cur->next = p->next; p->next = cur; } } } return new_head; } void RR_runprocces(PCB* proc)//时间片轮转 { int _time = proc->Arrivetime; int flag = 0; pcb* p = proc; for (p; p != NULL; p = p->next) { flag++; } pcb* p1 = proc; for (p1; p1->next != NULL; p1 = p1->next); p1->next = proc; pcb* ptr = proc; while (flag != 0) { if (ptr->Arrivetime <= _time) {if (ptr->state == 'W') { cout << "时刻" << _time << "开始执行" << ptr->name << endl; _time += TIME_SLICE; ptr->RunTime += TIME_SLICE; ptr->NeedTime = ptr->ServerTime - ptr->RunTime; if (ptr->NeedTime >= -1) {cout << "时刻" << _time << "挂起作业" << ptr->name; cout << "已运行" << ptr->RunTime << "还需要执行" << ptr->NeedTime << endl; cout << endl; if (ptr->NeedTime <= 0) { cout << "时刻" << _time << "作业消失" << ptr->name << endl; cout << endl; flag--; ptr->state = 'P'; } ptr = ptr->next; } else { cout << "时刻" << _time << "作业消失" << ptr->name << endl; cout << endl; flag--; ptr->state = 'P'; ptr = ptr->next; } } } else { ptr = ptr->next; } }Pcb End_list(Pcb plist)//最终链表 { assert(NULL != plist); int begin_time = plist->Arrivetime; plist->BeginTime = begin_time; int end_time = begin_time + plist->ServerTime; plist->FinishTime = end_time; plist->wholeTime = (float)(plist->FinishTime - plist->Arrivetime); plist->Weight_wholetime = (float)(plist->wholeTime / plist->ServerTime); plist->state = 'W'; plist->RunTime = 0; pcb* ptr = plist->next; while (ptr != NULL) { ptr->BeginTime = end_time; ptr->FinishTime = end_time + ptr->ServerTime; end_time += ptr->ServerTime; ptr->wholeTime = (float)(ptr->FinishTime - ptr->Arrivetime); ptr->Weight_wholetime = (float)(ptr->wholeTime / ptr->ServerTime); ptr->state = 'W'; ptr->RunTime = 0; ptr = ptr->next; } return plist; } Pcb Sort_SJFjob(Pcb list, int time) { assert(NULL != list); pcb* ptr_head = Sort_Shortjob(list); pcb* head_node = (pcb*)malloc(sizeof(pcb)); assert(head_node != NULL); head_node->Arrivetime = 0; head_node->ServerTime = 0; head_node->Prio = 0; head_node->next = NULL; while (ptr_head->next!= NULL) { pcb* a = ptr_head->next; if (a->next == NULL) { pcb* tail = head_node; for (tail; tail->next != NULL; tail = tail->next); tail->next = a; ptr_head->next = NULL; } else { while (a->Arrivetime > time&&a->next!=NULL) { a = a->next; } if (a->next == NULL&&a->Arrivetime>time) { pcb* e = ptr_head->next; ptr_head->next = NULL; pcb* d = Sort_Arrivetime(e); pcb* s = d->next; d->next = NULL; time = time + d->ServerTime; pcb* tail = head_node; for (tail; tail->next != NULL; tail = tail->next); tail->next = d; pcb* l = Sort_Shortjob(s); pcb* j = l->next; l->next = NULL; ptr_head->next = j; } else { pcb* c = ptr_head; while (c->next != a) { c = c->next; } c->next = a->next; a->next = NULL; time = time + a->ServerTime; pcb* tail = head_node; for (tail; tail->next != NULL; tail = tail->next); tail->next = a; } } } pcb* back_head = head_node->next; head_node->next = NULL; free(head_node); head_node = NULL; return back_head; } Pcb Sort_SJF(Pcb list) { assert(list != NULL); pcb* head = Sort_Arrivetime(list); int _time = head->Arrivetime + head->ServerTime; if (head->next != NULL) { pcb* ptr = head->next; head->next = NULL; pcb* _head = Sort_SJFjob(ptr,_time); head->next = _head; } return head; } Pcb Sort_PRC(Pcb list) { assert(NULL != list); pcb* new_head = (pcb*)malloc(sizeof(pcb)); assert(NULL != new_head); new_head->Arrivetime = 0; new_head->ServerTime = 0; new_head->Prio = 0; new_head->next = NULL; pcb* head = NULL; while (list != NULL) { pcb* cur = list; list = list->next; cur->next = NULL; if (new_head->next == NULL) { new_head->next = cur; } else { pcb* ptr = new_head; for (ptr; ptr->next != nullptr; ptr = ptr->next); if (ptr->Prio >= cur->Prio) { ptr->next = cur; } else { pcb* p = new_head; while (p->next->Prio > cur->Prio) { p = p->next; } cur->next = p->next; p->next = cur; } } } return new_head; } Pcb Sort_Prcjob(Pcb list, int time) { assert(NULL != list); pcb* ptr_head = Sort_PRC(list); pcb* head_node = (pcb*)malloc(sizeof(pcb)); assert(head_node != NULL); head_node->Arrivetime = 0; head_node->ServerTime = 0; head_node->Prio = 0; head_node->next = NULL; while (ptr_head->next != NULL) { pcb* a = ptr_head->next; if (a->next == NULL) { pcb* tail = head_node; for (tail; tail->next != NULL; tail = tail->next); tail->next = a; ptr_head->next = NULL; } else { while (a->Arrivetime > time && a->next != NULL) { a = a->next; } if (a->next == NULL && a->Arrivetime > time) { pcb* b = ptr_head->next; ptr_head->next = b->next; b->next = NULL; time = time + b->ServerTime; pcb* tail = head_node; for (tail; tail->next != NULL; tail = tail->next); tail->next = b; } else { pcb* c = ptr_head; while (c->next != a) { c = c->next; } c->next = a->next; a->next = NULL; time = time + a->ServerTime; pcb* tail = head_node; for (tail; tail->next != NULL; tail = tail->next); tail->next = a; } } } pcb* back_head = head_node->next; head_node->next = NULL; free(head_node); head_node = NULL; return back_head; } Pcb Sort_Prc(Pcb list) { assert(list != NULL); pcb* head = Sort_Arrivetime(list); int _time = head->Arrivetime + head->ServerTime; if (head->next != NULL) { pcb* ptr = head->next; head->next = NULL; pcb* _head = Sort_Prcjob(ptr, _time); head->next = _head; } return head; } void FCFS()//先来先服务 { pcb* head = PCB_Create(); printf("\t\t算法调度前如下:\n"); head_Show(head); putchar('\n'); printf("\t\t\t\t算法调度后如下:\n"); pcb* end_head = Sort_Arrivetime(head); struct PCB* list = End_list(end_head); Show(list); } void SJF() { pcb* head = PCB_Create(); printf("\t\t算法调度前如下:\n"); head_Show(head); putchar('\n'); printf("\t\t\t\t算法调度后如下:\n"); pcb* end = Sort_SJF(head); pcb* list = End_list(end); Show(list); } void PrioCreate() { pcb* head = PCB_Create(); printf("\t\t算法调度前如下:\n"); head_Show(head); putchar('\n'); printf("\t\t\t\t算法调度后如下:\n"); pcb* end = Sort_Prc(head); pcb* list = End_list(end); Show(list); } void RR()//时间片轮转算法 { pcb* head = PCB_Create(); printf("\t\t算法调度前如下:\n"); head_Show(head); putchar('\n'); printf("\t\t\t\t算法调度后如下:\n"); pcb* end_head = Sort_Arrivetime(head); struct PCB* list = End_list(end_head); RR_runprocces(list); } int main() { int select = 1; while (select) { cout << "******************************************\n"; cout << "*****1.******* 先来先服务算法 ************\n"; cout << "*****2.********短作业优先************\n"; cout << "*****3.********时间片轮转************\n"; cout << "*****4.****响应比高者优先调度*********\n"; cout << "*****0.**********退出*********************\n"; cout << "请选择:> "; cin >> select; switch (select) { case 1:FCFS(); break; case 2: SJF(); break; case 3: RR(); break; case 4: PrioCreate(); break; default: break; } } return 0; } #endif

第一次写不太好见谅
测试用例以：
A 10 4 3
B 2 5 8
C 9 6 5
D 6 9 2
开始界面，功能选项：