©2020-2024 ioDraw All rights reserved
<>四种算法介绍
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<iostream> #include<assert.h> using namespace std; #define
TIME_SLICE 2 typedef struct PCB { char name[10];//此为进程id char state; //进程状态w/r
int Arrivetime;//进程到达时间 int BeginTime;//进程开始时间 int FinishTime;//进程结束时间 int
ServerTime;//进程服务时间 float wholeTime;//周转时间 float Weight_wholetime;//带权周转时间
double Average_wholeTime;//平均周转时间 double Average_weight_wholetime;//带权平均周转时间 int
RunTime;//已经占用cpu时间 int NeedTime;//还需要cpu时间 int Prio;//优先级 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
开始界面，功能选项：
算法1：
算法2：
算法3：
算法4：
OK！！！！！