操作系统四种进程调度算法Cc++语⾔（先来先服务（FCFS）短作业优先算法
（SJF）优先级。。。
四种算法介绍
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<asrt.h>
using namespace std;
#define TIME_SLICE 2
typedef struct PCB
{
char name[10];//此为进程id
char state;//进程状态w/r
int Arrivetime;//进程到达时间
天机经
int BeginTime;//进程开始时间
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)//输⼊打印
{
asrt(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)
{
asrt(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;
return NULL;
}
cout <<"请输⼊PCB名称、优先级、到达时间、服务时间"<< endl;
for(int i =1; i <= Proc_Num; i++)
{
pcb* new_proc =(pcb*)malloc(sizeof(pcb));
asrt(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;
}
el
{
_tail->next = new_proc;
_tail = new_proc;
}
}
return _head;
}
Pcb Sort_Arrivetime(Pcb list)//时间先后顺序排序
{
asrt(NULL!= list);
pcb* new_head =(pcb*)malloc(sizeof(pcb));
asrt(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;
}
el
{
pcb* ptr = new_head;
for(ptr; ptr->next != nullptr; ptr = ptr->next);
if(cur->Arrivetime >= ptr->Arrivetime)
{战狼2结局
ptr->next = cur;
}
el
{卧薪尝胆的典故
pcb* p = new_head;酸碱盐的化学性质
while(cur->Arrivetime > p->next->Arrivetime)
{
p = p->next;
}
cur->next = p->next;
p->next = cur;
}
}
}
return new_head->next;
赵孟頫书法
return new_head->next;
}
Pcb Sort_Shortjob(Pcb list)//短作业排序链表
{
asrt(NULL!= list);
pcb* new_head =(pcb*)malloc(sizeof(pcb)); asrt(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;
}
el
{
pcb* ptr = new_head;
吉他怎么学
for(ptr; ptr->next != nullptr; ptr = ptr->next);
if(cur->ServerTime >= ptr->ServerTime)
{
ptr->next = cur;
}
el
{
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;
}
el
{
cout <<"时刻"<< _time <<"作业消失"<< ptr->name << endl;
cout << endl;
flag--;
ptr->state ='P';
ptr = ptr->next;
}
}
}
el
{
ptr = ptr->next;
}
}
Pcb End_list(Pcb plist)//最终链表
{
asrt(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)
{
asrt(NULL!= list);
