處理機演算法
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、響應時間：用戶提交請求到系統首次產生響應所用的時間。在互動式系統中，周轉時間不可能是最好的評價准則，一般採用響應時間作業衡量調度演算法的重要准則之一。從用戶角度來看，調度策略應該盡量降低響應時間，使得響應時間處在用戶能接受的范圍之內。