处理机算法
1. 进程调度算法1——FCFS、SJF、HNNR
进程的调度方式有两种： 非剥夺调度方式（非抢占式）和剥夺调度方式（抢占方式）。
非抢占式：只允许进程主动放弃处理机。如进程运行结束、异常结束或主动请求I/O阻塞。在运行的过程中即使有更紧迫的任务到达，当前进程依然会继续使用处理机，直到该进程终止或主动要求进入阻塞态。
抢占式：当一个进程正在处理机上执行时，如果有一个更重要更紧迫的进程需要处理机，则立即暂停正在执行的进程，将处理机分配给更重要更紧迫的那个进程。
下面介绍适用于早期操作系统几种进程调度的算法
先来先服务（FCFS）：按照到达的先后顺序调度，事实上就是等待时间越久的越优先得到服务。
下面表示按照先来先服务算法的执行顺序
计算进程的几个衡量指标：
短作业优先算法是非抢占式的算法，但是也有抢占式的版本—— 最短剩余时间优先算法（STRN,Shortest Remaining Time Next） 。
用于进程的调度算法称为短进程优先调度算法（SPF,Shortest Process First）。
短作业/进程优先调度算法：每次调度时选择当前已到达且运行时间最短的作业/进程.。
因为进程1最先达到，此时没有其他线程，所以进程1先被服务。当进程1运行完后，进程2和3已经到达，此时进程3需要的运行时间比进程2少，所以进程3先被服务…
计算进程的几个衡量指标：
最短剩余时间优先算法：每当有进程 加入就绪队列改变时就需要调度 ，如果新到达的进程的所需的运行时间比当前运行的进程剩余时间更短，则由新进程抢占处理机，当前运行进程重新回到就绪队列。此外，当一个 进程完成时也需要调度 。
通过比较上面三组的平均周转时间、平均带权周转时间和平均等待时间可以看出，短作业优先算法可以减少进程的等待时间，对短作业有利。
高响应比优先算法： 非抢占式的调度算法 ，只有当前运行的进程主动放弃CPU时（正常/异常完成、或主动阻塞），才需要进行调度，调度时计算所有就绪进程的相应比，选响应比最高的进程上处理机。
响应比 = （等待时间 + 运行时间）/ 运行时间
上面的三种调度算法一般适用于 早期的批处理系统 ，没有考虑响应时间也不区分任务的紧急程度。因此对用户来说交互性差。
如发现错误，请指正！！！
2. 处理机调度和进程调度
在多道程序系统中，进程的数量往往多于处理机的个数，这样不可能同时并行地处理各个进程。处理机的调度就是 从就绪队列中按照一定的算法选择一个进程并将处理机分配给它运行 ，以实现进程的并发执行。
调度的方式： 高级调度、中级调度、低级调度。
由于内存空间有限，有时无法将用户提交的作业全部放入内存中，因此需要确定某种规则来决定作业调入内存的顺序。
高级调度（作业调度） ：按照一定的原则从外存上处于后备队列的作业中挑选一个或多个作业，给他们分配内存等必要资源，并建立相应的进程（ 建立PCB ），以使它（们） 获得竞争处理机的权利。
高级调度是外存与内存之间的调度。 每个作业只调入一次，调出一次。作业调入时会建立相应的PCB，作业调出时才撤销PCB。高级调度主要是指调入的问题，因为只有调入的时机需要操作系统来确定，但调出的时机必然是作业运行结束才调出。
在引入虚拟存储技术之后，可以将暂时不能运行的进程调至外存等待，等它重新具备了运行条件且内存又稍有空间时，再重新调入内存。
这样做是为了提高内存利用率和系统吞吐量。
暂时调到外存等待的进程状态为 挂起状态 ，但是进程的PCB不会一起调到外存，而是会 常驻内存 。PCB中会记录进程数据在外存中的存放位置，进程状态等信息，操作系统通过内存的PCB来保持对各个进程的监控、管理。被挂起的进程PCB会被放到挂起队列中。
中级调度（内存调度） ，就是按照某种规则，从挂起队列中选择合适的进程将其数据重新调回内存。
一个进程可能会被多次调出、调入内存。因此中级调度发生的频率比高级调度更高
低级调度（进程调度） ：其主要任务是按照某种方法和策略从就绪队列中选取一个进程，将处理机分配给它。
进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度。
进程调度的频率很高，一般几十毫秒一次。这样才能保证多进程在宏观是同时进行的。
需要进行进程调度与切换的情况：
不能进行进程调度与切换的情况：
非剥夺调度方式，又称非抢占式。 即只允许进程主动放弃处理机，在运行过程中即使有更紧急的任务到达，当前进程依然会继续使用处理机，直到该进程终止或要求进入阻塞态。
实现简单，系统开销小但是无法及时处理紧急任务，适合早期批处理操作系统。
剥夺调度方式，又称抢占式。 当一个进程正在处理机上执行时，如果有一个更重要更紧急进程要使用处理机，即立即暂停正在执行的进程，将处理机分配给更重要更紧急的那个进程。
可以优先处理更紧急的进程。也可以实现各进程按时间片轮流执行的功能（通过时钟中断）。适合分时操作系统、实时操作系统。
由此可见， 进程的切换是有代价的 ，因此如果进程切换调度过于频繁的话，必然会使整个系统的开销过大，效率降低。因为系统大部分时间都花在进程切换上，真正用于执行进程的时间少。
评价指标： CPU利用率、系统吞吐量、周转时间、等待时间、响应时间。
CPU利用率：指CPU忙碌的时间占总时间的比例。
CPU利用率 = 忙碌时间 / 总时间。
如某计算机只支持单道程序，某个作业刚开始需要在CPU上运行5s，再用打印机打印输出5s，之后再执行5s，在此过程中：
CPU利用率=(5 + 5) / 15 = 66.67%.
打印机利用率=5 / 15 = 33.33%.
系统吞吐量：单位时间内完成作业的数量。
系统吞吐量=总共完成了多少道作业/总共花了多少时间
周转时间：指从作业被提交给操作系统开始，到作业完成为止的这段时间间隔。
包括四个部分：作业在外存设备队列上等待作业调度（高级调度）的时间、进程在就绪队列上等待进程调度（低级调度）的时间、进程在CPU上执行的时间、进程等待I/O操作完成的时间。
作业周转时间= 作业完成时间 – 作业提交时间
平均周转时间 = 各作业周转时间之和 / 作业数
带权周转时间 = 作业周转时间 / 作业实际运行时间
平均带权周转时间 = 各作业带权周转时间之和 / 作业数
等待时间：指进程或作业处于等待处理机状态时间之和。
平均等待时间：各个进程/作业等待时间的平均值。
对进程来说，等待时间就是指进程建立后等待被服务的时间之和。
对于作业来说，不仅要考虑建立进程后等待的时间（进程建立时作业已经进入了内存），还要加上作业在外部存后备队列中等待的时间。
响应时间：指从用户提交请求到首次产生相应所用的时间。
本文完
如发现错误，请指正！！！
3. 急求 程序代码 c/c++ 操作系统中的 处理机调度算法
#include <iostream>
#include <stdio.h>
#include <string>
//#include <windows.h>
using namespace std;
//hyugtyftydrtdtrdrrtrdrt
struct Node
{
string name;//进程（作业）名称
int arriveTime;//到达时间
int ServerTime;//服务时间
int leftTime;//the left time
Node *link;//指向下一个节点的指针
};
class CProcess
{
public:
CProcess();//构造函数
~CProcess();//析构函数
const CProcess &operator =(const CProcess& p);//重载赋值操作符
void insertNode(string &na,int& at,int& st);//插入新元素（at由小到大）到链表合适的位置
void sort();//按照服务时间由大到小排序
bool isEmpty();//判断是否为空
void destroy();//销毁
int length();//求出链表长度
void print();//打印出元素
void FCFS();//先到先服务
void SJF();//短进程(作业)优先
void RR(int& q);//时间片轮转
void priority();//优先权调度
protected:
Node *first;
Node *last;
};
const CProcess& CProcess::operator=(const CProcess& p)
{
Node *newNode;
Node *Current;
if(this!=&p)//避免自己给自己赋值
{
if(first!=NULL)//如果链表不为空
destroy();
if(p.first==NULL)
{//如果要拷贝的对象为空
this->first = NULL;
this->last = NULL;
}
else
{
Current = p.first;
first= new Node;
first->name=Current->name;//
first->arriveTime=Current->arriveTime;
first->ServerTime=Current->ServerTime;
first->link =NULL;
last =first;
Current = Current->link;
while(Current!=NULL)
{
newNode = new Node;
newNode->name=Current->name;
newNode->arriveTime=Current->arriveTime;
newNode->ServerTime=Current->ServerTime;
newNode->link=NULL;
last->link=newNode;
last=newNode;
Current = Current->link;
}
}
}
return *this;
}
CProcess::CProcess()
{//构造函数
first=NULL;
last=NULL;
}
CProcess::~CProcess()
{
Node *temp;
while(first!=NULL)
{
temp=first;
first=first->link;
delete temp;
}
last=NULL;
}
void CProcess::insertNode(string &na,int& at,int& st)
{//按照到达时间升序排序
Node *Current;
Node *trailCurrent;//指向Current的前一个节点
Node *newNode;
bool found;
newNode = new Node;//建立一个新节点
newNode->name=na;
newNode->arriveTime=at;
newNode->ServerTime=st;
newNode->link=NULL;//
if(first==NULL)//如果第一个节点为空（如果是第一次插入元素）
first=newNode;//将新节点赋给第一个节点
else
{//如果不是第一次
Current =first;
found = false;
while(Current!=NULL && !found)
{
if(Current->arriveTime >= at)
found = true;
else
{
trailCurrent = Current;
Current = Current->link;
}
}
if(Current==first)
{
newNode->link = first;
first = newNode;
}
else
{
trailCurrent->link = newNode;
newNode->link = Current;
}
}
}
int CProcess::length()
{
int count =0;//声明变量，并初始化为0（用来记录长度）
Node *Current;
Current = first;
while(Current!=NULL)//当前节点不为空，记录值自加，一直向后遍历,
{
count++;
Current = Current->link;
}
return count;//返回长度
}
void CProcess::sort()//按照服务时间，升序排列
{//冒泡排序
string sname;
int at;
int st;
Node *Current;//指向当前节点
Node *trailCurrent;//指向当前节点的前一个节点
for(trailCurrent=first->link;trailCurrent!=NULL;trailCurrent=trailCurrent->link)//控制条件有问题
{
for(Current=trailCurrent->link;Current!=NULL;Current=Current->link)//控制条件有问题
{
if(trailCurrent->ServerTime > Current->ServerTime)
{
sname=trailCurrent->name;
at=trailCurrent->arriveTime;
st=trailCurrent->ServerTime;
trailCurrent->name=Current->name;
trailCurrent->arriveTime=Current->arriveTime;
trailCurrent->ServerTime=Current->ServerTime;
Current->name=sname;
Current->arriveTime=at;
Current->ServerTime=st;
}
}
}
}
bool CProcess::isEmpty()//判断是否为空
{
return (first==NULL);//如果第一个节点为空，返回值
}
void CProcess::print()
{
Node *Current;
Current = first->link;//头节点赋给当前节点
while(Current!=NULL)//当前节点不为空，一直向后遍历打印
{
cout<<Current->name<<" ";
cout<<Current->arriveTime<<" ";
cout<<Current->ServerTime<<"\n";
Current = Current->link;
}
}
void CProcess::destroy()
{
Node *temp;//定义一个临时指针变量
while(first!=NULL)
{
temp=first;
first=first->link;
delete temp;
}
last=NULL;
}
void CProcess::FCFS()//先到先服务
{
Node *Current;
int T0=0;//完成时间
int T1=0;//周转时间
Current = first->link;//头节点赋给当前节点
while(Current!=NULL)
{
if(T0 < Current->arriveTime)
{
T0=Current->arriveTime+Current->ServerTime;
T1=T0-Current->arriveTime;
cout<<Current->name<<"\t";//打印出进程名
cout<<T0<<"\t";//打印出完成时间
cout<<T1<<"\n";//打印出周转时间
Current = Current->link;
}
else
{
T0=Current->ServerTime+T0;
T1=T0-Current->arriveTime;//周转时间等于，完成时间 - 到达时间
cout<<Current->name<<"\t";//打印出进程名
cout<<T0<<"\t";//打印出完成时间
cout<<T1<<"\n";//打印出周转时间
Current = Current->link;
}
}
}
void CProcess::SJF()//短进程(作业)优先
{
//首先执行第一个到达的作业
Node *Current;
int T0=0;//完成时间
int T1=0;//周转时间
T0=first->link->ServerTime+T0;
T1=T0-first->link->arriveTime;
cout<<first->link->name<<"\t";
cout<<T0<<"\t";//打印出完成时间
cout<<T1<<"\n";//打印出周转时间
first->link=first->link->link;//删除
//执行剩下的
sort();//对剩下的排序
Current = first->link;//头节点赋给当前节点
while(Current!=NULL)
{
if(T0 < Current->arriveTime)
{
T0=Current->arriveTime+Current->ServerTime;
T1=T0-Current->arriveTime;
cout<<Current->name<<"\t";//打印出进程名
cout<<T0<<"\t";//打印出完成时间
cout<<T1<<"\n";//打印出周转时间
Current = Current->link;
}
else
{
T0=Current->ServerTime+T0;
T1=T0-Current->arriveTime;//周转时间等于，完成时间 - 到达时间
cout<<Current->name<<"\t";//打印出进程名
cout<<T0<<"\t";//打印出完成时间
cout<<T1<<"\n";//打印出周转时间
Current = Current->link;
}
}
}
void CProcess::RR(int& q)//时间片轮转
{
cout<<"时间片轮转操作完成！\n";
}
void CProcess::priority()//优先权调度
{
cout<<"优先权操作完成！\n";
}
void main()
{
CProcess p0,p1,p2,p3,p4;
int at,st;
string na;
int judge=1;//控制退出程序
int choice;//控制选择操作
while(judge)
{
cout<<"********************************************************\n";
cout<<"****** 说明：本程序适用于单道进程（作业） ******\n";
cout<<"******** 请选择您的操作 ***************\n";
cout<<"*********输入相应的数字，按下（Enter）键！**************\n";
cout<<"************* 5.录入信息 ************\n";
cout<<"************* 1.先到先服务 ************\n";
cout<<"************* 2.短进程（作业）优先 ************\n";
cout<<"************* 3.时间片轮转 ************\n";
cout<<"************* 4.优先权(静态)调度 ************\n";
cout<<"************* 0.退出程序 ************\n";
cout<<"********************************************************\n";
cin>>choice;
switch(choice)
{
case 0:
judge=0;
break;
case 5:
cout<<"请输入信息以“end”结束输入！\n";
cout<<"进程名 到达时间 服务时间"<<endl;
while(na.compare("end"))//如果相等则会返回0
{
p0.insertNode(na,at,st);
cin>>na>>at>>st;
}
cout<<"录入成功，目前的信息为：\n";
cout<<"进程名 到达时间 服务时间"<<endl;
p0.print();
break;
case 1://先到先服务
p1=p0;//拷贝一份
if(p1.isEmpty())
{
cout<<"请先录入信息\n";
break;
}
else
{
cout<<"先到先服务\n";
cout<<"进程名 完成时间 周转时间\n";
p1.FCFS();
break;
}
case 2://短作业优先
p2=p0;//拷贝一份
//p2.sort();
//p2.print();
if(p2.isEmpty())
{
cout<<"请先录入信息\n";
break;
}
else
{
cout<<"短作业优先\n";
cout<<"进程名 完成时间 周转时间\n";
p2.SJF();
break;
}
case 3://时间片轮转
p3=p0;//拷贝一份
int q;
if(p3.isEmpty())
{
cout<<"请先录入信息\n";
break;
}
else
{
cout<<"请输入时间片大小";
cin>>q;
cout<<"时间片轮转\n";
cout<<"进程名 完成时间 周转时间\n";
p3.RR(q);
break;
}
case 4://优先权
p4=p0;//拷贝一份
if(p4.isEmpty())
{
cout<<"请先录入信息\n";
break;
}
else
{
cout<<"时间片轮转\n";
cout<<"进程名 完成时间 周转时间\n";
p4.priority();
break;
}
default:
cout<<"请选择目录中的选项！\n";
break;
}
}
return;
}
4. 处理机调度算法的共同目标是什么批处理
作系统常用的批处理作业调度算法 1．先来先服务调度算法 先来先服务(FCFS)调度算法是一
5. 处理机调度的算法的实现
程序设计思路：
自定义结构体PCB表（进程名name，进程优先数priority，进程执行时间time）以及进程就绪队列Queue_Process（data[MAXSIZE]数组存放PCB，front，rear队首队尾指针），通过每次对进程就绪队列进行进程优先数从大到小排序来确定进程执行的选择，并且是采用动态优先数调度算法（每次优先数减1，执行时间减1），每次输出进程执行情况时只需要将队首PCB调出执行，其他进程都处于动态就绪状态，等进程执行结束后重新对进程就绪队列排序。
程序中，采用结构体、队列等数据结构，其中对队列每次排序是采用冒泡排序算法实现。 #include<iostream>#include<string>usingnamespacestd;#defineMAXSIZE10structPCB{intname;//进程名intpriority;//进程优先数inttime;//进程执行时间};structQueue_Process{PCBdata[MAXSIZE];//PCB队列intfront;//队首intrear;//队尾};voidInitQueue(Queue_Process*Q){Q->front=Q->rear=0;}boolIsQueueEmpty(Queue_ProcessQ)//队空判断函数{return(Q.front==Q.rear)?true:false;}boolIsQueueFull(Queue_ProcessQ)//队满判断函数{return(Q.front==(Q.rear+1)%MAXSIZE)?true:false;}voidEnQueue(Queue_Process*Q,PCBx)//入队函数{if(IsQueueFull(*Q))//判断队列是否为满{cout<<队满，入队操作失败！<<endl;exit(0);}//队列非满，将PCB入队，将其中信息填入Q->data[Q->rear].name=x.name;Q->data[Q->rear].priority=x.priority;Q->data[Q->rear].time=x.time;Q->rear=(Q->rear+1)%MAXSIZE;//队列队尾指针后移}voidDeleQueue(Queue_Process*Q){if(IsQueueEmpty(*Q))//判断队列是否为空{cout<<队空，出队操作失败！<<endl;exit(0);}Q->front=(Q->front+1)%MAXSIZE;//将队列首指针后移}voidSortPCB(PCB*pcb,intn)//PCB优先数大小从大到小排列函数{PCBtemp;boolexchange=true;//交换标志for(inti=n-1;i>0&&exchange;i--)//冒泡排序算法排序{exchange=false;for(intj=0;j<i;j++){if(pcb[j].priority<pcb[j+1].priority)//交换PCB中的数据{temp.name=pcb[j].name;temp.priority=pcb[j].priority;temp.time=pcb[j].time;pcb[j].name=pcb[j+1].name;pcb[j].priority=pcb[j+1].priority;pcb[j].time=pcb[j+1].time;pcb[j+1].name=temp.name;pcb[j+1].priority=temp.priority;pcb[j+1].time=temp.time;exchange=true;}}}}voidInput(PCB*pcb,intn)//进程信息输入函数{cout<<请输入每个进程的优先数和执行时间：<<endl;intp,t;for(inti=0;i<n;i++)//输入每个进程的优先数和执行时间{cin>>p>>t;pcb[i].name=i;pcb[i].priority=p;pcb[i].time=t;}}voidDisplay(Queue_Process*queue)//输出每个时刻的进程运行情况函数{cout<<进程名 <<优先数 <<执行时间 <<进程状态<<endl;do{if(queue->data[queue->front].time>1){cout<<<<queue->data[queue->front].name<< <<<<queue->data[queue->front].priority<< <<<<queue->data[queue->front].time<< <<执行中...<<endl;queue->data[queue->front].priority-=1;queue->data[queue->front].time-=1;for(inti=1;i<queue->rear-queue->front;i++)cout<<<<queue->data[queue->front+i].name<< <<<<queue->data[queue->front+i].priority<< <<<<queue->data[queue->front+i].time<< <<等待中...<<endl;cout<<endl<<endl;}else{cout<<<<queue->data[queue->front].name<< <<<<queue->data[queue->front].priority<< <<<<queue->data[queue->front].time<< <<执行中...<<endl;for(inti=1;i<queue->rear-queue->front;i++)cout<<<<queue->data[queue->front+i].name<< <<<<queue->data[queue->front+i].priority<< <<<<queue->data[queue->front+i].time<< <<等待中...<<endl;cout<<进程<<queue->data[queue->front].name<<执行完毕！<<endl<<endl<<endl;DeleQueue(queue);}SortPCB(queue->data,queue->rear-queue->front);//对队列中的优先数进程重新排序}while(!IsQueueEmpty(*queue));}voidmain(){PCBprocess[MAXSIZE-1];//进程数组Queue_Processqueue;//进程队列intnum;//要输入的进程数cout<<请输入进程同步数num：<<endl;cin>>num;InitQueue(&queue);//初始化队列Input(process,num);for(inti=0;i<num;i++)//通过循环使每个进程入队{EnQueue(&queue,process[i]);}SortPCB(queue.data,queue.rear-queue.front);//对进程按优先数从大到小排列cout<<endl<< 进程执行情况：<<endl;Display(&queue);//进程运行函数}
6. 电脑CPU 是怎么分配的
在系统当中，这叫处理机的分配算法；具体说来，要看是什么系统了：分时系统按时间片，采用优先级算法、先来先服务算法等进行分配；实时系统则具有高可靠性和快速响应的特点，严格按照高优先级算法进行处理机的分配。。。。。等
7. 处理机调度模拟程序:选择一个调度算法,实现处理机调度.
处理机调度主要有：先到先服务、短作业优先、优先权调度、轮转法调度、多级队列调度、多级反馈队列。
在实现时：
1、创建三个状态（队列）：运行（队长为1）、就绪、阻塞。
2、创建一个数据结构代表进程，里面有一些进程特征标记（根据我上面说的调度算法）。
3、写算法，读进程的数据结构进行入队、出队。
8. 第三章 处理机的调度与死锁
在多道程序系统中，调度的实质是一种资源分配，处理机调度是对处理机资源进行分配。处理机调度算法是指根据处理机分配策略所规定的处理机分配算法。
在多道程序系统中，进程的数量远远多于处理机的个数，因此进程争用处理机的情况在所难免。处理机调度是对处理机进行分配，即从就绪队列中按照一定的算法（公平、高效）选择一个进程并将处理机分配给它运行，以实现进程的并发执行。
高级调度又称 长程调度 或 作业调度 ，它调度的对象是 作业 。其主要功能是根据某种算法，决定将外存上处于后备队列中的哪几个作业调入内存，为它们创建进程、分配必要的资源，并将其放入就绪队列。
高级调度主要用于多道批处理系统中，在分时系统和实时系统中不设置高级调度。高级调度的执行频率较低，通常为几分钟一次。
低级调度又称为 进程调度 或 短程调度 ，其所调度的对象是 进程 或 内核级线程 。其主要功能是根据某种算法决定就绪队列中哪个进程应获得处理机，并由分派程序将处理机分配给被选中的进程。
进程调度是最基本的一种调度，在多道批处理、分时系统和实时系统三种类型的OS中都必须设置这种调度。进程调度的频率很高，一般几十毫秒一次。
中级调度又称 内存调度 。引入中级调度的目的主要是提高内存的吞吐率和系统吞吐量。为此应把那些暂时不能运行的进程调至外存等待，此时进程的状态称为 就绪驻外存状态（或挂起状态） 。当它们已具备运行条件且内存又稍有空闲时，由中级调度来决定把外存上那些已具备运行条件的就绪进程再重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待。中级调度实际上就是存储器管理中的对换功能。
为了管理和调度作业，在多道批处理系统中，为每个作业设置一个作业控制块JCB，它是作业在系统中存在的标志，其中保存了系统对作业进行管理和调度所需的全部信息，例如 作业标识 、 用户名称 、 用户账号 、 作业类型（CPU繁忙型、I/O繁忙型、批量型、终端型） 、 作业状态 、 调度信息（优先级、作业运行时间） 、 资源需求（预计运行时间、要求内存大小等） 、 资源使用情况 等。
每当一个作业进入系统时，由“作业注册”程序为该作业建立一个JCB，再根据作业类型放到相应的后备队列中等待调度。调度程序根据一定的调度算法来调度它们，被调度的作业将被装入内存。在作业运行期间，系统根据JCB中的信息和作业说明书对作业进行控制。当一个作业执行完毕后，系统负责回收分配给它的资源，并撤销该JCB。
作业调度的主要任务是 根据JCB中的信息，检查系统中的资源是否满足作业对资源的需求，以及按照一定的调度算法，从外存的后备队列中选取某些作业调入内存，并为它们创建进程、分配必要的资源，然后将新创建的进程排在就绪队列上等待调度 。因此也把作业调度称为“接纳调度”。在每次执行作业调度时，都需要决定 接纳多少个作业 和 接纳哪些作业 。
进程调度和切换的程序是操作系统的内核程序。请求调度的事件发生后，才可能运行进程调度程序，调度了新的就绪进程后，才会进行进程间的切换。在实际设计中，操作系统的内核程序运行时，若发生了引起进程调度的因素，也不一定能够马上进行进程调度与切换。
不能进行进程调度与切换的原因有：
若上述过程中发生了引起调度的条件，不能马上进行进程的调度与切换，应置系统的请求调度标志，直到上述过程结束后再进行相应的调度与切换。
应该进行进程的调度与切换的情况如下：
进程切换往往在调度完成后立刻发生。
进程调度方式是指 某个进程正在处理机上执行时，若有某个更为重要或紧迫的进程需要处理，即有更高优先权的进程进入就绪队列，此时应该如何分配处理机。
进程调度通常有 非剥夺调度方式 和 剥夺调度方式 两种方式。
又称 非抢占方式 ，是指当一个进程正在处理机上执行时，即使有某个更为重要或紧迫的进程进入就绪队列，仍然让正在执行的进程继续执行，直到该进程完成或发生某种事件而进入阻塞状态时，才把处理机分配给更为重要或紧迫的进程。在非剥夺调度方式下，一旦把CPU分配给一个进程，该进程就会保持CPU直到终止或转换到等待态。
非剥夺调度方式适合大多数的批处理系统，但不能用于分时系统和大多数的实时系统。
又称 抢占方式 ，是指当一个进程在处理机上执行时，若有某个更为重要或紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给这个更为重要或紧迫的进程。
采用剥夺调度方式，对提高系统吞吐率和响应效率都有明显的好处，但“剥夺”必须遵循一定的原则，主要有优先权、短进程优先、时间片原则等。
FCFS调度算法既可以用于作业调度，又可以用于进程调度。在作业调度中， 算法每次从后备队列中选择最先进入该队列的一个或几个作业，将它们调入内存，分配必要的资源，创建进程并放入就绪队列。
在进程调度中，FCFS调度算法每次从就绪队列中选择最先进入该队列的进程，将处理机分配给它，直到进程完成或因某种原因而阻塞才释放处理机。
FCFS调度算法属于不可剥夺算法。若一个长作业先到达系统，就会使后面许多短作业等待很长时间，因此它不能作为分时系统和实时系统的主要调度策略。但它常被结合在其它调度策略中使用，如在使用优先级作为调度策略的系统中，往往对多个具有相同优先级的进程按FCFS处理。
特点：
短作业优先调度算法是对短作业优先调度的算法。短作业优先算法从后备队列中选择一个或若干估计运行时间最短的进程，将它们调入内存执行；短进程优先算法从就绪队列中选择一个估计运行时间最短的进程，将处理机分配给它，直到完成或发生某事件而阻塞时，才释放处理机。
特点：
优先级调度算法又可称为优先权调度算法，既可以用于作业调度，又可以用于进程调度。该算法中的优先级用于描述作业的紧迫程度。在作业调度中，优先级调度算法每次从后备作业队列中选择优先级最高的一个或几个作业，将它们调入内存，分配必要的资源，创建进程并放入就绪队列。在进程调度中，优先级调度算法每次从就绪队列中选择优先级最高的进程，将处理机分配给它。
该算法按照更高优先级的进程是否抢占正在执行的进程可分为两种：
根据进程的优先级是否改变，可将进程的优先级分为以下两种：
一般来说，进程优先级的设置可以参照以下原则：
高响应比优先调度算法主要用于作业调度，是对FCFS调度算法和SJF调度算法的一种综合平衡，同时考虑了每个作业的等待事件和估计的运行时间。在每次进行作业调度时，先计算后备队列中每个作业的响应比，从中选出响应比最高的作业投入运行。
响应比的计算公式为： 响应比Rp = （等待时间 + 要求服务时间）/ 要求服务时间
特征：
时间片轮转调度算法主要用于分时系统。系统将所有就绪进程按到达时间的先后次序排成一个队列，进程调度程序总是选择就绪队列中的第一个进程执行，即先来先服务原则，但仅能运行一个时间片（如100ms）。在使用完一个时间片后，即使进程未完成其运行，它也必须释放处理机给下一个就绪的进程，而被剥夺处理机的进程返回就绪队列的末尾重新排队，等候再次运行。
时间片的大小对性能影响很大。若时间片足够大以至于所有进程都能在一个时间片内执行完毕，则该算法就退化为先来先服务调度算法；若时间片很小，则处理机将在进程间过于频繁地切换，使处理机的开销增大，而真正用于运行用户进程的时间将减少。
时间片的长短通常由以下因素确定：
多级反馈队列调度算法是时间片轮转调度算法和优先级调度算法的综合与发展。多级反馈队列调度算法可以兼顾多方面的系统目标，如为提高系统吞吐量和缩短平均周转时间而照顾短进程；为获得较好的I/O设备利用率和缩短响应时间而照顾I/O型进程；不必事先估计进程的执行时间。
该算法的实现思想如下：
优点：
死锁是指多个进程因竞争资源而造成的一种僵局（互相等待），若无外力作用，这些进程都将无法向前推进。
为使系统不发生死锁，必须破坏死锁的四个必要条件之一，或允许死锁产生，但当死锁发生时能检测出死锁，并有能力实现恢复。
设置某些限制条件，破坏产生死锁的四个必要条件中的一个或几个，以防止发生死锁。
在资源的动态分配过程中，用某种方法防止系统进入不安全状态，从而避免死锁。
无需采取任何限制性措施，允许进程在运行的过程中发生死锁，通过系统的检测机构及时地检测出死锁的发生，然后采取某种措施解除死锁。
死锁的预防和避免都属于事先预防策略，预防死锁的限制条件比较严格，实现起来较为简单，但往往导致系统的效率低，资源利用率低；避免死锁的限制条件比较宽松，资源分配后需要通过算法来判断是否进入不安全状态，实现起来比较复杂。
死锁的几种处理策略如下：
防止死锁的发生只需要破坏死锁产生的4个必要条件的其中之一即可。
特点：把只能互斥使用的资源改造成允许共享使用，则系统就不会进入死锁状态。如操作系统使用SPOOLing技术把独占设备在逻辑上改造成共享设备。
缺点：并不是所有的资源都可以改造成可以共享使用的资源，并且为了系统安全，很多地方还必须保持这种互斥性。因此，很多时候都无法破坏这种互斥条件。
特点：
缺点：
特点：可采用静态分配方法，即进程运行之前一次申请完它所需要的全部资源，在它的资源尚未得到满足前，不把它投入运行。一旦投入运行，这些资源就一直归它所有，不再提出申请其他资源的请求。这种方法实现起来简单。
缺点：有些资源可能只需要使用很短的时间，因此如果进程的整个运行期间都一直保持着所有资源，就会造成严重的资源浪费，资源利用率极低。另外，该策略也有可能导致某些进程饥饿。
特点：采用顺序资源分配法，首先给系统中的资源编号，规定每个进程都必须按照编号递增的顺序请求资源，同类资源一次申请完。也就是说，只要进程提出申请分配资源Ri，则该进程在以后的资源申请中就只能申请编号大于Ri的资源（一个进程只有已占有我号的资源时，才有资格申请更大编号的资源）。按此规则，已持有更大编号资源的进程不可能逆向地申请我号的资源，从而就不会产生循环等待现象。
缺点：
所谓安全序列，就是指如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要找出一个安全序列，系统就是安全状态。安全序列可能有多个。
如果分配了资源之后，系统找不到安全序列，则系统就进入了不安全状态。这就意味着之后可能所有进程都无法顺利执行下去。当然，如果有进程提前归还了一些资源，那系统也有可能提前回到安全状态。
如果系统处于安全状态，那么就一定不会发生死锁；如果系统进入不安全状态，就可能发生死锁（处于不安全状态未必就发生了死锁，但发生死锁时系统一定处于不安全状态）。因此可以在资源分配前预先判断这次分配是否会导致系统进入不安全状态，以此决定是否答应资源分配请求。
设Requesti是进程Pi的请求向量，Requesti[j] = K表示进程Pi需要j类资源K个。当Pi发出资源请求后，系统按照如下步骤进行检查：
安全性算法描述如下：
若系统在为进程分配资源时不采取任何措施，则应该提供死锁检测与解除的手段。
系统死锁可用资源分配图描述。如下图所示，圆圈代表一个进程，框代表一类资源，由于一种资源可能有多个，所以用框中的一个圆代表一类资源中的一个资源。从进程到资源的有向边称为请求边，表示该进程申请一个单位的该类资源；从资源到进程的边称为分配边，表示该类资源已经有一个资源分配给了该进程。
通过简化资源分配图可以检测系统状态S是否为死锁状态。简化方法如下：
9. 处理机调度算法的实现 用C语言
网络答案，经过验证：
#include "stdio.h"
#include <stdlib.h>
#include <conio.h>
#define getpch(type) (type*)malloc(sizeof(type))
#define NULL 0
struct pcb { /* 定义进程控制块PCB */
char name[10];
char state;
int super;
int ntime;
int rtime;
struct pcb* link;
}*ready=NULL,*p;
typedef struct pcb PCB;
void sort() /* 建立对进程进行优先级排列函数*/
{
PCB *first, *second;
int insert=0;
if((ready==NULL)||((p->super)>(ready->super))) /*优先级最大者,插入队首*/
{
p->link=ready;
ready=p;
}
else /* 进程比较优先级,插入适当的位置中*/
{
first=ready;
second=first->link;
while(second!=NULL)
{
if((p->super)>(second->super)) /*若插入进程比当前进程优先数大,*/
{ /*插入到当前进程前面*/
p->link=second;
first->link=p;
second=NULL;
insert=1;
}
else /* 插入进程优先数最低,则插入到队尾*/
{
first=first->link;
second=second->link;
}
}
if(insert==0) first->link=p;
}
}
void input() /* 建立进程控制块函数*/
{
int i,num;
system("cls"); /*清屏*/
printf("\n 请输入进程数: ");
scanf("%d",&num);
for(i=1;i<=num;i++)
{
printf("\n 进程号No.%d:\n",i);
p=getpch(PCB);
printf("\n 输入进程名:");
scanf("%s",p->name);
printf("\n 输入进程优先数:");
scanf("%d",&p->super);
printf("\n 输入进程运行时间:");
scanf("%d",&p->ntime);
printf("\n");
p->rtime=0;p->state='W';
p->link=NULL;
sort(); /* 调用sort函数*/
}
}
int space()
{
int l=0;
PCB* pr=ready;
while(pr!=NULL)
{
l++;
pr=pr->link;
}
return(l);
}
void disp(PCB * pr) /*建立进程显示函数,用于显示当前进程*/
{
printf("\n 进程名\t 状态\t 优先数\t 需要运行时间\t 已经运行时间\n");
printf("|%s\t",pr->name);
printf("|%c\t",pr->state);
printf("|%d\t",pr->super);
printf("|%d\t\t",pr->ntime);
printf("|%d\t",pr->rtime);
printf("\n");
}
void check() /* 建立进程查看函数 */
{
PCB* pr;
printf("\n **** 当前正在运行的进程是:\n"); /*显示当前运行进程*/
disp(p);
pr=ready;
printf("\n **** 当前就绪队列状态为:\n"); /*显示就绪队列状态*/
while(pr!=NULL)
{
disp(pr);
pr=pr->link;
}
}
void destroy() /*建立进程撤消函数(进程运行结束,撤消进程)*/
{
printf("\n 进程 [%s] 已完成.\n",p->name);
free(p);
}
void running() /* 建立进程就绪函数(进程运行时间到,置就绪状态*/
{
(p->rtime)++;
if(p->rtime==p->ntime)
destroy(); /* 调用destroy函数*/
else
{
(p->super)--;
p->state='W';
sort(); /*调用sort函数*/
}
}
void main() /*主函数*/
{
int len,h=0;
char ch;
input();
len=space();
while((len!=0)&&(ready!=NULL))
{
ch=getchar()();
h++;
printf("-----------------------------------------------------");
printf("\n 现在是第%d次运行： \n",h);
p=ready;
ready=p->link;
p->link=NULL;
p->state='R';
check();
running();
printf("\n 按任意键继续......\n");
}
printf("\n\n 进程已经完成.\n");
}
10. 进程调度有哪几种方式有哪几种评价方式
进程调度的几种方式：
1、非剥夺（非抢占）调度方式：当一个进程正在处理机上执行时，即使有某个更为重要或者紧迫的进程进入就绪队列，仍然让正在执行的进程继续执行，知道该进程完成或发生某种事件而进入阻塞态时，才把处理机分配给更为重要或紧迫（优先级更高）的进程。其优点是实现简单，系统开销小，适用于大多数批处理系统，但它不能用于分时系统和大多数实时系统。
2、剥夺（抢占）调度方式：当一个进程正在处理机上执行时，若有某个更为重要或紧迫的进程（优先级更高）的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给这个更重要的进程。这种方式对提高系统吞吐率和响应效率都有明显的好处。但抢占也要遵循一定原则。
(10)处理机算法扩展阅读：
为了比较处理机调度算法的性能，人们提出了很多评价准则，主要有一下几种：
1、CPU利用率：CPU是计算机系统中最重要和最昂贵的资源之一，所以应该尽可能使得CPU保持忙的状态，资源利用率尽可能高。
2、系统吞吐量：单位时间内CPU完成的作业数量。长作业需要消耗较长的处理机时间，会降低系统的吞吐量。对于短作业，他们所需消耗的处理机时间较短，因此能提高系统吞吐量。调度算法和方式不同，也会对系统的吞吐量产生较大影响。
3、周转时间：周转时间是指从作业提交到作业完成所经历的时间，是作业等待、在就绪队列中排队，在处理机上运行及输入输出操作所花费的时间的总和。
4、等待时间：进程处于等处理机状态的时间之和。等待时间越长，用户满意度越低。实际上，处理机调度算法实际上并不影响作业执行或输入输出操作的时间，只影响作业在就绪队列中等待所花的时间。因此，衡量一个调度算法的优劣，常常只需简单地考察等待时间。
5、响应时间：用户提交请求到系统首次产生响应所用的时间。在交互式系统中，周转时间不可能是最好的评价准则，一般采用响应时间作业衡量调度算法的重要准则之一。从用户角度来看，调度策略应该尽量降低响应时间，使得响应时间处在用户能接受的范围之内。