㈠ 基於優先數的時間片輪轉調度演算法調度處理器
沒有完全符合的,但是差不多的,你自己改改吧!
#include<iostream.h>
#include<stdlib.h>
#include<string.h>
typedef struct PCBA
{
char name[30];
int round;
int prio;
int cputime;
int needtime;
char state;
struct PCBA *next;
} PCB,*CurrentRunPCB,*LinkQueue;
CurrentRunPCB SelMosHeiPrio(LinkQueue *Q);//從Q鏈表中選擇一個優先順序最大的進程
void InitQueue(LinkQueue *Q);//初始化鏈表Q，如果鏈表沒有頭指針，可以省略；
void InsertQueue(LinkQueue * Q,PCB* run);
{
}//將Run結點插入鏈表Q中，表示就緒隊列里多了一個進程
void Priosch(LinkQueue Wait_Queue,LinkQueue Finish_Queue)//優先法運行，從就緒隊列Wait_Queue中選擇進程執行，（選擇隊列中優先順序最高的進程），執行結束的進程放入完成隊列中；
{ while (WaitQueue!=NULL)
{
CurrentRunPCB run=SelMosHeiPrio(&WaitQueue); //run為就緒隊列中優先順序最高的進程
run->cputime+=2;//時間片為2
run->needtime-=2;
run->prio=50-run->needtime;//動態優先順序，但是優先順序隨著運行時間的增加，優先順序增加，所以誰優先順序高會一直佔用CPU
run->state='r';
if(run->needtime>0)
{ run->state='w';
InsertQueue(&WaitQueue,run) ;
}
else
{cout<<"當前運行進稱為："<<run->name<<"運行結束後就緒隊列情況："<<'\n';
run->state='F';
run->needtime=0;
InsertQueue(&FinishQueue,run) ;
Print(&WaitQueue);
}
//當然可以採用不看進程運行過程，直接將優先順序高的運行完，插入完成隊列
/*
CurrentRunPCB run=SelMosHeiPrio(&WaitQueue);
cout<<"當前運行進稱為："<<run->name<<"運行結束後就緒隊列情況："<<'\n';
Print(&WaitQueue);
run->cputime=run->needtime;
run->needtime=0;
run->prio=50;//動態優先順序，但是優先順序隨著運行時間的增加，優先順序增加，所以誰優先順序高會一直佔用CPU
run->state='F';
InsertQueue(&FinishQueue,run) ;*/
}
void Print(LinkQueue*Q)//將隊列的元素顯示輸出，輸出包含進程名，進程CPUTIME,NEEDTIME,狀態，優先順序
{LinkQueue p=*Q;
cout<<"name cputime needtime state prio'"<<'\n';
while (p!=NULL)
{ cout<<p->name<<'\t'<<p->cputime<<'\t'<<p->needtime<<'\t'<<p->state<<'\t'<<p->prio<<'\n';
p=p->next;
}
}
CurrentRunPCB DeQueue(LinkQueue*Q)//從就緒隊列中取出一個進程
{LinkQueue p=*Q;
*Q=(*Q)->next;
p->next=NULL;
return p;
}
void Roundsch(LinkQueue WaitQueue,LinkQueue FinishQueue)//輪轉法運行，從就緒隊列Wait_Queue中選擇進程執行一個時間片，執行結束的進程放入完成隊列中；若一個時間片未能執行完的進程再插入到就緒隊列
{ while (WaitQueue!=NULL)
{
CurrentRunPCB run=DeQueue(&WaitQueue);
cout<<"當前運行進稱為："<<run->name<<"運行結束後就緒隊列情況："<<'\n';
run->cputime+=2;//時間片為2
run->needtime-=2;
run->prio=50- run->cputime;
run->state='r';
if(run->needtime>0)
{InsertQueue(&WaitQueue,run) ;
run->state='w';
}
else
{run->state='F';
run->needtime=0;
InsertQueue(&FinishQueue,run) ;
}
Print(&WaitQueue);
}
cout<<"完成隊列情況："<<'\n';
Print(&FinishQueue);
}
void SetAllpro(LinkQueue*Q)//設置優先順序函數50-p->needtime
{int max=0;
LinkQueue p,t;
t=NULL;
p=*Q;
if (p!=NULL)
{
max=p->prio;
p=p->next;
while(p)
{
if (max<p->prio) max=p->prio;
p=p->next;
}
p=*Q;
t=*Q;
if (t==p&&max==t->prio)
{*Q=(*Q)->next;
t->next=NULL;
return t;}
else{
t=t->next;
while(t)
{
if (max==t->prio)
{
p->next=t->next;
t->next=NULL;
return t;
}
else{p=t;
t=t->next;
}
}
}
}
return t;
}
void main()
{
PCBA *pcb0,*pcb1,*pcb2,*pcb3,*pcb4; //five processes 五個進程
LinkQueue Wait_Queue,Finish_Queue; //兩個隊列 等待和完成
Wait_Queue=NULL; //給隊列賦初值，如果帶有頭指針的鏈表，可以用函數；
Finish_Queue=NULL;
//InitQueue(&Wait_Queue);
//InitQueue(&Finish_Queue);
char ch;
//給各個進程設置初值
pcb0= new PCBA();
pcb1= new PCBA();
pcb2= new PCBA();
pcb3= new PCBA();
pcb4= new PCBA();
//example
strcpy(pcb0->name,"process1");
pcb0->round=2;
pcb0->prio=0;
pcb0->cputime=0;
pcb0->needtime=5;
pcb0->state='W';
pcb0->next=NULL;
strcpy(pcb1->name,"process2");
pcb1->round=2;
pcb1->prio=0;
pcb1->cputime=0;
pcb1->needtime=7;
pcb1->state='W';
pcb1->next=NULL;
strcpy(pcb2->name,"process3");
pcb2->round=2;
pcb2->prio=0;
pcb2->cputime=0;
pcb2->needtime=3;
pcb2->state='W';
pcb2->next=NULL;
strcpy(pcb3->name,"process4");
pcb3->round=2;
pcb3->prio=0;
pcb3->cputime=0;
pcb3->needtime=11;
pcb3->state='W';
pcb3->next=NULL;
strcpy(pcb4->name,"process5");
pcb4->round=2;
pcb4->prio=0;
pcb4->cputime=0;
pcb4->needtime=8;
pcb4->state='W';
pcb4->next=NULL;
//將各個進程插入就緒隊列中
InsertQueue(&Wait_Queue,pcb0);
InsertQueue(&Wait_Queue,pcb1);
InsertQueue(&Wait_Queue,pcb2);
InsertQueue(&Wait_Queue,pcb3);
InsertQueue(&Wait_Queue,pcb4);
//利用此演算法實現Wait_Queue中prio=50-needtime;
SetAllpro(&Wait_Queue);
cout<<"請輸入選擇的調度演算法(1 or 2 or anykey exit!)："<<endl;
cin>>ch;
switch(ch)
{
case '1':
Print(&Wait_Queue);
Roundsch(Wait_Queue,Finish_Queue);
break;
case '2':
Print(&Wait_Queue);
Priosch(Wait_Queue,Finish_Queue);
break;
default :
cout<<"你選擇了退出!"<<endl;
system("pause");
return;
}
return;
}
㈡ 操作系統實驗 使用C++完成處理器調度
在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;
sort() /* 建立對進程進行優先順序排列函數*/
{
PCB *first, *second;
int insert=0;
if(ready==NULL)
{
p->link=ready;
ready=p;
}
else /* 進程比較優先順序,插入適當的位置中*/
{
first=ready;
second=first->link;
while(second!=NULL)
{
first=first->link;
second=second->link;/*插尾*/
}
if(insert==0) first->link=p;
}
}
input() /* 建立進程式控制制塊函數*/
{'
int i,num;
system("cls"); /*清屏*/
printf("\n 請輸入進程號?");
scanf("%d",&num);
for(i=0;i<num;i++)
{
printf("\n 進程號No.%d:\n",i);
p=getpch(PCB);
printf("\n 輸入進程名:");
scanf("%s",p->name);
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);
}
disp(PCB * pr) /*建立進程顯示函數,用於顯示當前進程*/
{
printf("\n qname \t state \t super \t ndtime \t runtime \n");
printf("|%s\t",pr->name);
printf("|%c\t",pr->state);
printf("|%d\t",pr->super);
printf("|%d\t",pr->ntime);
printf("|%d\t",pr->rtime);
printf("\n");
}
check() /* 建立進程查看函數 */
{
PCB* pr;
printf("\n **** 當前正在運行的進程是:%s",p->name); /*顯示當前運行進程*/
disp(p);
pr=ready;
printf("\n ****當前就緒隊列狀態為:\n"); /*顯示就緒隊列狀態*/
while(pr!=NULL)
{
disp(pr);
pr=pr->link;
}
}
destroy() /*建立進程撤消函數(進程運行結束,撤消進程)*/
{
printf("\n 進程 [%s] 已完成.\n",p->name);
free(p);
}
running() /* 建立進程就緒函數(進程運行時間到,置就緒狀態*/
{
(p->rtime)++;
if(p->rtime==p->ntime)
destroy(); /* 調用destroy函數*/
else
{
p->state='w';
sort(); /*調用sort函數*/
}
}
main() /*主函數*/
{
int len,h=0;
char ch;
input();
len=space();
while((len!=0)&&(ready!=NULL))
{
ch=getchar();
h++;
printf("\n The execute number:%d \n",h);
p=ready;
ready=p->link;
p->link=NULL;
p->state='R';
check();
running();
printf("\n 按任一鍵繼續......");
ch=getchar();
}
printf("\n\n 進程已經完成.\n");
ch=getchar();
}
㈢ 設計一個按優先數調度演算法實現處理器調度的程序。
#include "stdio.h"
#include "malloc.h"
#include "string.h"
typedef struct node{
int time;
int name;
char statement;
int num;
struct node *next;
}node,*L;
void createL(L &l,int n){
l=(L)malloc(sizeof(node));
if(!l)
printf("error!");
else
l->next=NULL;
L p,q;
q=l;
for(int i=0;i<n;i++){
p=(L)malloc(sizeof(node));
printf("請輸入進程的名字name:\n");
scanf("%d",&p->name);
getchar();
printf("請輸入該進程的運行時間time:\n");
scanf("%d",&p->time);
printf("請輸入其優先順序數num:\n");
scanf("%d",&p->num);
getchar();
printf("請輸入其狀態:\n");
p->statement=getchar();
p->next=q->next;
q->next=p;
q=p;
getchar();
}
}
void traL(L &l){
L p;
p=l->next;
printf("進程名\t運行時間\t優先數\t狀態\n");
while(p){
printf(" %d\t%5d\t%11d\t %c",p->name,p->time,p->num,p->statement);
printf("\n");
p=p->next;
}
}
void Sort(L &l)
{
L tail=NULL;
while(tail!= l->next)
{
L pre = l;
L cur = pre->next;
while(cur != tail && cur->next != tail)
{
if( cur->num < cur->next->num )
{
pre->next = cur->next;
cur->next = cur->next->next;
pre->next->next = cur;
}
pre = pre->next;
cur = pre->next;
}
tail = cur;
}
}
void run(L &l){
Sort(l);
L p,r,q;
q=l;
if(l->next!=NULL)
p=l->next;
int j=0;
printf("第k次運行\t進程名\t運行時間\t優先數\t狀態\n");
while(p!=NULL){
j++;
printf("%5d\t %d\t%5d\t%11d\t %c",j,p->name,p->time,p->num,p->statement);
printf("\n");
p->num--;
p->time--;
if(p->time==0){
p->statement='E';
r=p;
if(p->next!=NULL)
{
l->next=p->next;
free(r);
p=l->next;
}
else
break;
}
else{
Sort(l);
if(l->next!=NULL)
p=l->next;
else
break;
}
}
}
void main(){
L l;
int n;
printf("請輸入進程的數目n:\n");
scanf("%d",&n);
createL(l,n);
traL(l);
run(l);
}
//這是運行過的，應該符合你的要求！
㈣ 2018-06-09
一、常見的批處理作業調度演算法
1.先來先服務調度演算法（FCFS）:就是按照各個作業進入系統的自然次序來調度作業。這種調度演算法的優點是實現簡單，公平。其缺點是沒有考慮到系統中各種資源的綜合使用情況，往往使短作業的用戶不滿意，因為短作業等待處理的時間可能比實際運行時間長得多。
2.短作業優先調度演算法(SPF): 就是優先調度並處理短作業，所謂短是指作業的運行時間短。而在作業未投入運行時，並不能知道它實際的運行時間的長短，因此需要用戶在提交作業時同時提交作業運行時間的估計值。
3.最高響應比優先演算法(HRN)：FCFS可能造成短作業用戶不滿，SPF可能使得長作業用戶不滿，於是提出HRN，選擇響應比最高的作業運行。響應比=1+作業等待時間/作業處理時間。
4. 基於優先數調度演算法(HPF)：每一個作業規定一個表示該作業優先順序別的整數，當需要將新的作業由輸入井調入內存處理時，優先選擇優先數最高的作業。
5.均衡調度演算法，即多級隊列調度演算法
基本概念：
作業周轉時間（Ti）＝完成時間(Tei)－提交時間(Tsi)
作業平均周轉時間(T)＝周轉時間/作業個數
作業帶權周轉時間（Wi）＝周轉時間/運行時間
響應比＝（等待時間＋運行時間）/運行時間
二、進程調度演算法
1.先進先出演算法(FIFO)：按照進程進入就緒隊列的先後次序來選擇。即每當進入進程調度，總是把就緒隊列的隊首進程投入運行。
2. 時間片輪轉演算法(RR)：分時系統的一種調度演算法。輪轉的基本思想是，將CPU的處理時間劃分成一個個的時間片，就緒隊列中的進程輪流運行一個時間片。當時間片結束時，就強迫進程讓出CPU，該進程進入就緒隊列，等待下一次調度，同時，進程調度又去選擇就緒隊列中的一個進程，分配給它一個時間片，以投入運行。
3. 最高優先順序演算法(HPF)：進程調度每次將處理機分配給具有最高優先順序的就緒進程。最高優先順序演算法可與不同的CPU方式結合形成可搶占式最高優先順序演算法和不可搶占式最高優先順序演算法。
4. 多級隊列反饋法：幾種調度演算法的結合形式多級隊列方式。
三、空閑分區分配演算法
\1. 首先適應演算法：當接到內存申請時，查找分區說明表，找到第一個滿足申請長度的空閑區，將其分割並分配。此演算法簡單，可以快速做出分配決定。
2. 最佳適應演算法：當接到內存申請時，查找分區說明表，找到第一個能滿足申請長度的最小空閑區，將其進行分割並分配。此演算法最節約空間，因為它盡量不分割到大的空閑區，其缺點是可能會形成很多很小的空閑分區，稱為「碎片」。
3. 最壞適應演算法：當接到內存申請時，查找分區說明表，找到能滿足申請要求的最大的空閑區。該演算法的優點是避免形成碎片，而缺點是分割了大的空閑區後，在遇到較大的程序申請內存時，無法滿足的可能性較大。
四、虛擬頁式存儲管理中的頁面置換演算法
1.理想頁面置換演算法(OPT)：這是一種理想的演算法，在實際中不可能實現。該演算法的思想是：發生缺頁時，選擇以後永不使用或在最長時間內不再被訪問的內存頁面予以淘汰。
2.先進先出頁面置換演算法(FIFO)：選擇最先進入內存的頁面予以淘汰。
3. 最近最久未使用演算法（LRU）：選擇在最近一段時間內最久沒有使用過的頁，把它淘汰。
4.最少使用演算法（LFU）：選擇到當前時間為止被訪問次數最少的頁轉換。
三、磁碟調度
1.先來先服務（FCFS）：是按請求訪問者的先後次序啟動磁碟驅動器，而不考慮它們要訪問的物理位置
2.最短尋道時間優先（SSTF）：讓離當前磁軌最近的請求訪問者啟動磁碟驅動器，即是讓查找時間最短的那個作業先執行，而不考慮請求訪問者到來的先後次序，這樣就克服了先來先服務調度演算法中磁臂移動過大的問題
3.掃描演算法（SCAN）或電梯調度演算法：總是從磁臂當前位置開始，沿磁臂的移動方向去選擇離當前磁臂最近的那個柱面的訪問者。如果沿磁臂的方向無請求訪問時，就改變磁臂的移動方向。在這種調度方法下磁臂的移動類似於電梯的調度，所以它也稱為電梯調度演算法。
4.循環掃描演算法（CSCAN）：循環掃描調度演算法是在掃描演算法的基礎上改進的。磁臂改為單項移動，由外向里。當前位置開始沿磁臂的移動方向去選擇離當前磁臂最近的哪個柱面的訪問者。如果沿磁臂的方向無請求訪問時，再回到最外，訪問柱面號最小的作業請求。
對一個進程來說,一個重要的指標是它執行所需要的時間. 從進程提交到進程完成的時間間隔為周轉時間.也就是等待進入內存的時間,在就緒隊列中等待的時間,在 CPU中執行的時間和I/O操作的時間的總和.
例1.設一個系統中有5個進程，它們的到達時間和服務時間如下，A的到達時間為0，服務時間為3；B的到達時間為2，服務時間為6；C的到達時間為4，服務時間為4；D的到達時間為6，服務時間為5；E的 到達時間為8，服務時間為2，忽略1/0以及其他開銷時間，若分別按先來先服務（fFCFS）進行CPU調度，其平均周轉時間為？
10.2
6.4
8.6
4.5
先來先服務調度演算法
進程名 到達時間 服務時間 開始執行時間 完成時間 周轉時間
A 0 3 0 3 3
B 2 6 3 9 7
C 4 4 9 13 9
D 6 5 13 18 12
E 8 2 18 20 12
周轉時間 = 完成時間 - 到達時間
平均周轉時間 = 所有進程周轉時間 / 進程數 = （3+7+9+12+12）/ 5 = 8.6
單道批處理系統中有4個作業，J1的提交時間8.0，運行時間為2.0；J2的提交時間8.6，運行時間為0.6；J3提交時間8.8，運行時間為0.2；J4的提交時間9.0，運行時間為0.5。在採用響應比高者優先調度演算法時，其平均周轉時間為T為（）小時？
2.5
1.8
1.975
2.675
周轉時間=作業完成時間-作業提交時間
響應比=（作業等待時間+作業執行時間）/作業執行時間
當提交J1時，只有J1作業，執行J1，J1的周轉時間為2，此時時間為10.
J2、J3、J4提交時，由於正在執行J1，因此等待。
當J1執行完畢（此時時間為10），J2、J3、J4的等待時間分別為：1.4,1.2,1，
其響應比分別為：1.4/0.6+1=3.33 1.2/0.2+1=7 1/0.5+1=3，因此執行J3，J3的周轉時間為1.2+0.2=1.4
當J3執行完畢（此時時間為10.2），J2和J4的等待時間分別為1.6,1.2，
其響應比分別為：1.6/0.6+1=3.66 1.2/0.5+1=3.4，因此執行J2，J2的周轉時間為1.6+0.6=2.2
執行J2完畢後時間為10.8，接下來執行J4，執行完後時時間為11.3，J4的周轉時間為2.3
於是平均周轉時間為（2+1.4+2.2+2.3）/4=1.975
如果系統作業幾乎同時到達，則使系統平均作業周轉時間最短的演算法是短作業優先。
例3、
現有4個同時到達的作業J1,J2,J3和J4,它們的執行時間分別是3小時,5小時,7小時,9小時系統按單道方式運行且採用短作業優先演算法,則平均周轉時間是()小時
12.5
24
19
6
作業到達時間執行時間開始時間完成時間周轉時間
J103033
J20 5388
J30781515
J409152424
平均周轉時間（3+8+15+24）/4=12.5
有4個進程A,B,C,D,設它們依次進入就緒隊列，因相差時間很短可視為同時到達。4個進程按輪轉法分別運行11,7,2,和4個時間單位，設時間片為1。四個進程的平均周轉時間為 （）？
15.25
16.25
16.75
17.25
17.75
18.25
A:1 4 4 3 3 2 2 2 1 1 1 共24
B:2 4 4 3 3 2 2 共20
C:3 4 共7
D:4 4 3 3 共14
字母後面的數字為等待的時間加運行時間
平均周轉時間為（24+20+7+14）/4=16.25
例5、假設系統按單值方式運行且採用最短作業優先演算法，有J1,J2,J3,J4共4個作業同時到達，則以下哪幾種情況下的平均周轉時間為10分鍾?
執行時間J1:1分鍾 J2:5分鍾 J3:9分鍾 J4:13分鍾
執行時間J1:1分鍾 J2:4分鍾 J3:7分鍾 J4:10分鍾
執行時間J1:2分鍾 J2:4分鍾 J3:6分鍾 J4:8分鍾
執行時間J1:3分鍾 J2:6分鍾 J3:9分鍾 J4:12分鍾
首先，短作業優先則短時間的作業利用資源，其餘的作業等待
根據平均周轉時間概念，將所有作業"等待時間"加上"運行時間"除以"作業數量"即可得到平均周轉時間
A： (J1執行1分鍾 + J2等待1分鍾 + J2執行5分鍾 + J3等待6分鍾 + J3執行9分鍾 + J4等待15分鍾 + J4執行13分鍾) / 4 = 50/4 = 12.5
B： (J1執行1分鍾 + J2等待1分鍾 + J2執行4分鍾 + J3等待5分鍾 + J3執行7分鍾 + J4等待12分鍾 + J4執行10分鍾) / 4 = 40/4 = 10
C： (J1執行2分鍾 + J2等待2分鍾 + J2執行4分鍾 + J3等待6分鍾 + J3執行6分鍾 + J4等待12分鍾 + J4執行8分鍾) / 4 = 40/4 = 10
D： (J1執行3分鍾 + J2等待3分鍾 + J2執行6分鍾 + J3等待9分鍾 + J3執行9分鍾 + J4等待18分鍾 + J4執行12分鍾) / 4 = 50/4 = 12.5
例6、假設系統中有5個進程，它們的到達時間和服務時間見下表1，忽略I/O以及其他開銷時間，若按先來先服務（FCFS）、非搶占的短作業優先和搶占的短作業優先三種調度演算法進行CPU調度，請給出各個進程的完成時間、周轉時間、帶權周轉時間、平均周轉時間和平均帶權周轉時間，完成表2。 表1 進程到達和需要服務時間 進程 到達時間 服務時間 A 0 3 B 2 6 C 4 4 D 6 5 E 8 2
表2 進程的完成時間和周轉時間
進程 A B C D E 平均
FCFS 完成時間 3 9 13 18 20
周轉時間 3 7 9 12 12 8.6
帶權周轉時間 1.00 1.17 2.25 2.40 6.00 2.56
SPF(非搶占) 完成時間 3 9 15 20 11
周轉時間 3 7 11 14 3 7.6
帶權周轉時間 1.00 1.17 1.75 2.80 1.50 1.84
SPF(搶占) 完成時間 3 15 8 20 10
周轉時間 3 13 4 14 2 7.2
帶權周轉時間 1.00 2.16 1.00 2.80 1.00 1.59
例7、假定在單道批處理環境下有5個作業，各作業進入系統的時間和估計運行時間如下表所示： 作業 進入系統時間 估計運行時間/分鍾 1 8:00 40 2 8:20 30 3 8:30 12 4 9:00 18
5 9:10 5
如果應用先來先服務和應用最短作業優先的作業調度演算法，試將下面表格填寫完整。
(1) 如果應用先來先服務的作業調度演算法，試將下面表格填寫完整。
作業 進入系統時間 估計運行時間/分鍾 開始時間 結束時間 周轉時間/分鍾
1 8:00 40 8：00 8：40 40
2 8:20 30 8：40 9：10 50
3 8:30 12 9：10 9：22 52
4 9:00 18 9：22 9：40 40
5 9:10 5 9：40 9：45 35
作業平均周轉時間T= 43.4 217
2）如果應用最短作業優先的作業調度演算法，試將下面表格填寫完整。 作業 進入系統時間 估計運行時間/分鍾 開始時間 結束時間 周轉時間/分鍾 1 8:00 40 8：00 8：40 40 2 8:20 30 8：52 9：22 62 3 8:30 12 8：40 8：52 22 4 9:00 18 9：27 9：45 45 5 9:10 5 9：22 9：27 17作業平均周轉時間T= 37.2 186
CPU和兩台輸入/輸出設備(I1,I2)多道程序設計環境下,同時有三個作業J1,J2,J3進行,這三個作業
使用CPU和輸入/輸出設備的順序和時間如下所示:
J1:I2(35ms);CPU(15ms);I1(35ms);CPU(15ms);I2(25ms)
J2:I1(25ms);CPU(30ms);I2(35ms)
J3:CPU(30ms);I1(25ms);CPU(15ms);I1(15ms);
假定CPU,I1,I2都能並行工作,J1的優先順序最高,J2次之,J3優先順序最低,優先順序高的作業可以搶占優先順序低的作業的CPU,但不能搶佔I1,I2,作業從J3開始到完成需要多少時間?
㈤ 設計一個按優先數調度演算法實現處理器調度的程序。 高手幫忙!!
#include <stdio.h>
#include <stdlib.h> //提供atoi()函數
#include <conio.c> //提供clrscr()函數
#define M 10 //字元串大小常量
#define N 3 //進程數常量
#define SLOT 2
typedef struct node{
char name[M];
int prio; //優先順序
int round; //時間片長度
int cputime; //已經使用的cpu時間
int needtime;//需要多少cpu時間
int count; //計數器
char state; //進程的當前狀態
struct node *next; //指向下一個進程
}PCB;
PCB *finish,*ready,*tail,*run;
void ShowHead(char *s1,char *s2);
int Menu_Select();
void Creat(int select);
void InsertPriority(PCB *q);
void InsertSlot(PCB *q);
void PrintOneProcess(int select,PCB *q);
void PrintAllProcess(int select);
void FirstIn();
void FIFODo(int select);
void PriorityDo(int select);
void SlotDo(int select);
void Quit();
main()
{
while(1)
{
clrscr();
switch(Menu_Select())
{
case 1:
Creat(1);
FIFODo(1);
printf("\n\n\t\t按回車鍵返回菜單...");
getchar();
getchar();
break;
case 2:
Creat(2);
PriorityDo(2);
printf("\n\n\t\t按回車鍵返回菜單...");
getchar();
getchar();
break;
case 3:
Creat(3);
SlotDo(3);
printf("\n\n\t\t按回車鍵返回菜單...");
getchar();
getchar();
break;
case 0:
Quit();
break;
}
}
}
/*列印每個界面的開頭顯示*/
void ShowHead(char *s1,char *s2)
{
printf("\t ==================%s========================\n\n",s1);
printf("\t\t\t\t%s\n\n",s2);
printf("\t ========================================================\n\n");
}
/*主菜單*/
int Menu_Select()
{
int choose;
char s[2];
clrscr();
printf("====================進程調度演算法模擬程序=====================\n\n");
printf("\t\t 1.先進先出調度策略\n");
printf("\t\t 2.優先數調度策略\n");
printf("\t\t 3.時間片輪轉調度策略\n");
printf("\t\t 0.退出系統\n\n");
printf("=============================================================\n\n");
do
{
printf("\n請輸入你的選擇(0-3):");
scanf("%s",s);
choose=atoi(s);
}while(choose<0 || choose>3);
return choose;
}
/*創建調度演算法的鏈表*/
void Creat(int select)
{
PCB *p,*q; //q為就緒隊列的最後一個結點
int i,time,rounds;
char na[M];
ready=NULL;
finish=NULL;
run=NULL;
if(select==1) //先進先出調度創建
{
printf("\nEnter name and time of process:\n");
for(i=1;i<=N;i++)
{
p=(PCB *)malloc(sizeof(PCB));
scanf("%s",na);
scanf("%d",&time);
strcpy(p->name,na);
p->cputime=0;
p->needtime=time;
p->state='W';
p->next=NULL;
if(ready!=NULL) //就緒隊列不為空
{
q->next=p;
q=p;
}
else //就緒隊列為空
{
p->next=ready;
ready=p;
q=ready;
}
}
clrscr();
ShowHead("先進先出調度策略","FIFO dispatching algorithm ");
printf("\t\t name cputime needtime state\n");
PrintAllProcess(select); //列印出初始狀態的信息
}
else if(select==2) //優先數調度創建
{
printf("\nEnter name and time of process:\n");
for(i=1;i<=N;i++)
{
p=(PCB *)malloc(sizeof(PCB));
scanf("%s",na);
scanf("%d",&time);
strcpy(p->name,na);
p->cputime=0;
p->needtime=time;
p->state='W';
p->prio=50-time;
if(ready!=NULL) //就緒隊列不為空的時候
InsertPriority(p);
else //就緒隊列為空
{
p->next=ready;
ready=p;
}
}//end of for()
clrscr();
ShowHead("優先順序調度策略","Priority dispatching algorithm ");
printf("\t\t name cputime needtime prio state\n");
PrintAllProcess(select); //列印出初始狀態的信息
}//end of else if()
else if(select==3) //時間片輪轉調度創建
{
printf("\nEnter name and the time of process:\n");
for(i=1;i<=N;i++)
{
p=(PCB *)malloc(sizeof(PCB));
scanf("%s",na);
scanf("%d",&time);
strcpy(p->name,na);
p->cputime=0;
p->needtime=time;
p->count=0; //計數器
p->round=SLOT;
p->state='W';
if(ready!=NULL)
InsertSlot(p);
else
{
p->next=ready;
ready=p;
}
}
clrscr();
ShowHead("時間片輪轉調度策略","Time slot dispatching algorithm ");
printf("\n\t\t name cputime needtime count slot state\n");
PrintAllProcess(select); //列印出初始狀態的信息
}
run=ready; //從就緒隊列取一個進程，使其運行，同時就緒隊列的頭指針後移
run->state='R';
ready=ready->next;
}
/*優先調度：把進程插入到合適的位置，就緒隊列按優先順序由高到低的順序排列*/
void InsertPriority(PCB *q)
{
PCB *pre,*p;
int flag=1;
pre=NULL;
p=ready;
while(p!=NULL && flag)
{
if(p->prio>q->prio)
{
pre=p;
p=p->next;
}
else
flag=0;
}
if(pre==NULL)
{
q->next=ready;
ready=q;
}
else
{
pre->next=q;
q->next=p;
}
}
/*時間片輪轉：把結點插入到就緒隊列的末尾*/
void InsertSlot(PCB *q)
{
PCB *pre,*p;
pre=NULL;
p=ready;
while(p!=NULL)
{
pre=p;
p=p->next;
}
pre->next=q;
q->next=NULL; /*由於插入到隊列的末尾，所以必須要使其的下一個結點為空值*/
}
/*列印一個信息*/
void PrintOneProcess(int select,PCB *q)
{
if(select==1)
printf("\t\t %-10s%-10d%-10d%c\n",q->name,q->cputime,q->needtime,q->state);
else if(select==2)
printf("\t\t %-10s%-10d%-10d%-10d%c\n",q->name,q->cputime,q->needtime,q->prio,q->state);
else if(select==3)
printf("\t\t %-10s%-10d%-10d%-10d%-10d%c\n",q->name,q->cputime,q->needtime,q->count,q->round,q->state);
}
/*將所有的進程列印出來，按運行，就緒，完成順序列印*/
void PrintAllProcess(int select)
{
PCB *p;
if(run!=NULL)
PrintOneProcess(select,run);
p=ready;
while(p!=NULL)
{
PrintOneProcess(select,p);
p=p->next;
}
p=finish;
while(p!=NULL)
{
PrintOneProcess(select,p);
p=p->next;
}
}
/*把就緒隊列的第一個進程調入運行*/
void FirstIn()
{
run=ready;
ready=ready->next;
run->state='R';
}
/*先進先出調度策略*/
void FIFODo(int select)
{
while(run!=NULL)
{
run->cputime=run->cputime+1;
run->needtime=run->needtime-1;
if(run->needtime==0) //進程執行結束
{
printf("\n\t\t name cputime needtime state\n");
run->next=finish;
finish=run;
run->state='F';
run=NULL;
if(ready!=NULL)
FirstIn();
PrintAllProcess(1);
}
}
}
/*優先順序演算法*/
void PriorityDo(int select)
{
while(run!=NULL)
{
printf("\n\t\t name cputime needtime prio state\n");
run->cputime=run->cputime+1;
run->needtime=run->needtime-1;
run->prio=run->prio-3;
if(run->needtime==0)
{
run->next=finish;
finish=run;
run->state='F';
run=NULL;
if(ready!=NULL)
FirstIn();
}
else if((ready!=NULL) && (run->prio < ready->prio))
{
run->state='W';
InsertPriority(run);
FirstIn();
}
PrintAllProcess(select);
}
}
/*時間片輪轉演算法*/
void SlotDo(int select)
{
while(run!=NULL)
{
printf("\n\t\t name cputime needtime count slot state\n");
run->count=run->count+1;
run->cputime=run->cputime+1;
run->needtime=run->needtime-1;
if(run->needtime==0) /*運行完成時*/
{
run->next=finish;
finish=run;
run->state='F';
run=NULL;
if(ready!=NULL)
FirstIn(); //就緒隊列不為空，將就緒隊列的第一個進程投入運行
}
else if(run->count==run->round) /*時間片已經到了，還未運行完成*/
{
run->count=0; //時間片
if(ready!=NULL)
{
run->state='W';
InsertSlot(run);
FirstIn();
}
}
PrintAllProcess(select); //列印本次的所有記錄
}
}
void Quit()
{
char ch;
clrscr();
gotoxy(10,5);
printf("==========================================================\n\n");
printf(" Thank you for you using\n\n");
gotoxy(10,9);
printf("==========================================================\n\n");
gotoxy(13,15);
getchar();
printf("\n\t\tDo you really want to quit(y/Y or n/N):");
scanf("%c",&ch);
if(ch=='y' || ch=='Y')
{
printf("\n\t\t按任意鍵退出系統...");
getchar();
exit(0);
}
}
㈥ 進程調度方案設計 實現一個基本動態優先順序的調度演算法
前兩天做操作系統作業的時候學習了一下幾種進程調度演算法，在思考和討論後，有了一些自己的想法，現在就寫出來，跟大家討論下。，或者說只有有限的CPU資源，當系統中有多個進程處於就緒狀態，要競爭CPU資源時，操作系統就要負責完成如何分配資源的任務。在操作系統中，由調度程序來完成這一選擇分配的工作，調度程序所使用的演算法即是調度演算法。調度演算法需要考慮的指標主要有盡量保證CPU資源分配的公平性；按照一定策略強制執行演算法調度；平衡整個計算機系統，盡量保持各個部分都處於忙碌狀態。而根據系統各自不同的特點和要求，調度演算法又有一些側重點和目標不同，因此，演算法按照系統差異主要分為三大類：批處理系統中的調度演算法，代表調度演算法有：先來先服務、最短作業優先、最短剩餘時間優先。互動式系統中的調度演算法，代表調度演算法有：輪轉調度、優先順序調度、多級隊列、最短進程優先、保證調度、彩票調度、公平分享調度。實時系統中的調度演算法，代表調度演算法有：速率單調調度、最早最終時限優先調度。下面就上述提到的調度演算法中挑出幾個進行重點分析：保證調度保證調度是指利用演算法向用戶做出明確的性能保證，然後盡力按照此保證實現CPU的資源分配。利用這種演算法，就是定一個進程佔用CPU的時間的標准，然後按照這個標准去比較實際佔用CPU的時間，調度進程每次使離此標准最遠的進程得到資源，不斷滿足離所保證的標准最遠的進程，從而平衡資源分配滿足這個標準的要求。保證調度演算法的優點是：能很好的保證進程公平的CPU份額，當系統的特點是：進程的優先順序沒有太大懸殊，所制定的保證標准差異不大，各個進程對CPU的要求較為接近時，比如說系統要求n個進程中的每個進程都只佔用1/n的CPU資源，利用保證調度可以很容易的實現穩定的CPU分配要求。但缺點是，這種情況太過理想，當系統的各個進程對CPU要求的緊急程度不同，所制定的保證較為復雜的時候，這個演算法實現起來比較困難。彩票調度彩票調度這種演算法的大意是指向進程提供各種系統資源如CPU資源的彩票，當系統需要做出調度決策時，隨機抽出一張彩票，由此彩票的擁有者獲得資源。在彩票調度系統中，如果有一個新的進程出現並得到一些彩票，那麼在下一次的抽獎中，該進程會有同它持有彩票數量成正比例的機會贏得獎勵。進程持有的彩票數量越多，則被抽中的可能性就越大。調度程序可以通過控制進程的彩票持有數量來進行調度。彩票調度有很多優點：首先，它很靈活，系統增加分給某個進程的彩票數量，就會大大增加它佔用資源的可能性，可以說，彩票調度的反應是迅速的，而快速響應需求正是互動式系統的一個重要要求。其次，彩票調度演算法中，進程可以交換彩票，這個特點可以更好的保證系統的平衡性，使其各個部分都盡可能的處於忙碌狀態。而且利用彩票調度還可以解決許多別的演算法很難解決的問題，例如可以根據特定的需要大致成比例的劃分CPU的使用。速率單調調度速率單調調度演算法是一種可適用於可搶占的周期性進程的經典靜態實時調度演算法。當實時系統中的進程滿足：每個周期性進程必須在其周期內完成，且進程之間沒有相互依賴的關系，每個進程在一次突發中需要相同的CPU時間量，非周期的進程都沒有最終時限四個條件時，並且為了建模方便，我們假設進程搶占即刻發生沒有系統開銷，可以考慮利用速率單調演算法。速率單調調度演算法是將進程的速率（按照進程周期所算出的每秒響應的次數）賦為優先順序，則保證了優先順序與進程速率成線性關系，這即是我們所說的速率單調。調度程序每次運行優先順序最高的，只要優先順序較高的程序需要運行，則立即搶占優先順序低的進程，而優先順序較低的進程必須等所有優先順序高於它的進程結束後才能運行。速率單調調度演算法可以保證系統中最關鍵的任務總是得到調度，但是缺點是其作為一種靜態演算法，靈活性不夠好，當進程數變多，系統調度變得復雜時，可能不能較好的保證進程在周期內運行。最早最終時限優先調度最早最終時限優先調度演算法是一個動態演算法，不要求進程是周期性的，只要一個進程需要CPU時間，它就宣布它的到來時間和最終時限。調度程序維持一個可運行的進程列表，按最終時限排序，每次調度一個最終時限最早的進程得到CPU 。當新進程就緒時，系統檢查其最終時限是否在當前運行的進程結束之前，如果是，則搶占當前進程。由於是動態演算法，最早最終優先調度的優點就是靈活，當進程數不超過負載時，資源分配更優，但也同樣由於它的動態屬性，進程的優先順序都是在不斷變化中的，所以也沒有哪個進程是一定可以保證滿足調度的，當進程數超過負載時，資源分配合理度會急速下降，所以不太穩定。
㈦ 動態高優先權優先調度演算法
動態高優先權優先調度演算法：
動態優先權是指，在創建進程時所賦予的優先權，是可以隨進程的推進或隨其等待時間的增加而改變的，以便獲得更好的調度性能。例如，我們可以規定，在就緒隊列中的進程，隨其等待時間的增長，其優先權以速率a提高。若所有的進程都具有相同的優先權初值，則顯然是最先進入就緒隊列的進程，將因其動態優先權變得最高而優先獲得處理機，此即FCFS演算法。若所有的就緒進程具有各不相同的優先權初值，那麼，對於優先權初值低的進程，在等待了足夠的時間後，其優先權便可能升為最高，從而可以獲得處理機。當採用搶占式優先權調度演算法時，如果再規定當前進程的優先權以速率b下降，則可防止一個長作業長期地壟斷處理機。
演算法代碼模擬實現：
#include<stdio.h>
#include<stdlib.h>
#defineN6
//待插入就緒隊列的進程數據
intid[N]={0,1,
2,3,4,
5};
intpriority[N]={9,38,17,
2,7,18};
intcpuTime[N]={0,
0,0,0,
0,0};
intallTime[N]={3,
2,3,6,
1,3};
//********************************
//
//模擬進程/PCB數據結構
//
//********************************
//
枚舉進程的狀態：就緒、執行、阻塞、完成
enumSTATE{Ready,Run,Block,Finish
};
//建立PCB結構體
structPCB{
intid;//標志數
intpriority;//優先數
intcpuTime;//
已佔CPU時間
intallTime;//
還需佔CPU時間
intblockTime;//已被阻塞的時間
STATEstate;//
進程狀態
PCB*pre;//
PCB的前指針
PCB*nxt;//
PCB的後指針
};
//********************************
//
//模擬進程隊列
//
//********************************
//進程入列
voidqueQush(PCB*process,PCB
*queHead)
{
process->pre=NULL;
process->nxt=
queHead->nxt;
if(queHead->nxt!=NULL){
//非第一個入列
queHead->nxt->pre=
process;
}
queHead->nxt=process;
}
//進程出列
voidquePop(PCB*process,PCB
*queHead)
{
if(process->pre!=NULL){
//不是頭節點
process->pre->nxt=
process->nxt;
}
else{
queHead->nxt=
process->nxt;
}
if(process->nxt!=NULL){
//不是尾節點
process->nxt->pre=
process->pre;
}
//
清空進程指針
process->pre=process->nxt=
NULL;
}
//查看隊列里進程的信息
voidqueWalk(PCB*queHead)
{
PCB*pro=queHead->nxt;
if(pro==NULL){
printf("(無進程) ");
return;
}
while(pro!=NULL)
{
printf("id:%d,
pri:%d,alltime:%d ",
pro->id,
pro->priority,
pro->allTime);
pro=
pro->nxt;
}
}
//********************************
//
//模擬就緒隊列
//
//********************************
intreadyQueNum;//就緒隊列的進程數量
PCBreadyQueHead;//
就緒隊列的頭部
PCB*readyMaxProcess;//就緒隊列中優先順序最高的進程
//進程插入到就緒隊列
voidreadyQueQush(PCB
*process)
{
readyQueNum++;
process->state=Ready;
queQush(process,&readyQueHead);
}
//優先順序最高的進程出列
PCB*readyQuePop()
{
readyQueNum--;
quePop(readyMaxProcess,
&readyQueHead);
returnreadyMaxProcess;
}
//每個時間片，更新就緒隊列里進程的信息
voidreadyQueUpdate()
{
intmaxPriority=-1;
PCB*pro=readyQueHead.nxt;
if(pro==NULL){
//就緒隊列沒有進程
readyMaxProcess=
NULL;
return;
}
while(pro!=NULL)
{
pro->priority
++;
if(pro->priority>maxPriority)
{
maxPriority=
pro->priority;
readyMaxProcess=pro;
}
pro=
pro->nxt;
}
}
//返回就緒隊列最高優先順序的值
intreadyMaxPriority()
{
returnreadyMaxProcess->priority;
}
//查看就緒隊列里進程的信息
voidreadyQueWalk()
{
printf("就緒隊列里的進程信息為： ");
queWalk(&readyQueHead);
}
//********************************
//
//模擬阻塞隊列
//
//********************************
#defineEndBlockTime3
//進程最長被阻塞時間
intblockQueNum;//阻塞隊列的進程數量
PCBblockQueHead;//
阻塞隊列的頭部
PCB*blockMaxProcess;//阻塞隊列中優先順序最高的進程
//進程插入到阻塞隊列
voidblockQueQush(PCB
*process)
{
blockQueNum++;
process->blockTime=0;
process->state=Block;
queQush(process,&blockQueHead);
}
//優先順序最高的進程出列
PCB*blockQuePop()
{
blockQueNum--;
quePop(blockMaxProcess,
&blockQueHead);
returnblockMaxProcess;
}
//每個時間片，更新阻塞隊列里進程的信息
voidblockQueUpdate()
{
intmaxPriority=-1;
PCB*pro=blockQueHead.nxt;
while(pro!=NULL)
{
pro->blockTime
++;
if(pro->blockTime>=EndBlockTime)
{
PCB*process=pro;
pro=pro->nxt;
//阻塞時間到，調入就緒隊列
blockQueNum--;
quePop(process,
&blockQueHead);
readyQueQush(process);
}else
if(pro->priority>maxPriority)
{
//更新阻塞隊列里優先順序最高的進程指針
maxPriority=
pro->priority;
blockMaxProcess=pro;
pro=pro->nxt;
}
}
}
//查看阻塞隊列里進程的信息
voidblockQueWalk()
{
printf("阻塞隊列里的進程信息為： ");
queWalk(&blockQueHead);
}
//********************************
//
//模擬動態優先權的進程調度
//
//********************************
//初始化數據
voidinitData()
{
//
初始化就緒隊列和阻塞隊列
readyQueNum=blockQueNum=0;
readyMaxProcess=blockMaxProcess=NULL;
readyQueHead.pre=readyQueHead.nxt=NULL;
blockQueHead.pre=blockQueHead.nxt=NULL;
//
初始化進程進入就緒隊列
inti,maxPriority=-1;
for(i=0;i<N;i
++)
{
//分配一個PCB的內存空間
PCB*pro=(PCB
*)malloc(sizeof(PCB));
//給當前的PCB賦值
pro->id
=id[i];
pro->priority
=priority[i];
pro->cpuTime
=cpuTime[i];
pro->allTime
=allTime[i];
pro->blockTime
=0;
if(pro->allTime>0){
//插入到就緒隊列中
readyQueQush(pro);
//更新就緒隊列優先順序最高的進程指針
if(pro->priority>
maxPriority){
maxPriority=pro->priority;
readyMaxProcess=pro;
}
}
}
}
//模擬cpu執行1個時間片的操作
voidcpuWord(PCB
*cpuProcess)
{
cpuProcess->priority-=3;
if(cpuProcess->priority<0)
{
cpuProcess->priority=0;
}
cpuProcess->cpuTime++;
cpuProcess->allTime--;
//
顯示正執行進程的信息：
printf("CPU正執行的進程信息為： ");
printf("id:M,pri:M,
alltime:M ",
cpuProcess->id,
cpuProcess->priority,
cpuProcess->allTime);
}
intmain()
{
inttimeSlice=0;//
模擬時間片
intcpuBusy=0;
//模擬cpu狀態
PCB*cpuProcess=NULL;//當前在cpu執行的進程
//
初始化數據
initData();
//
模擬進程調度
while(1)
{
if(readyQueNum==0
&&blockQueNum==0
&&cpuBusy==0){
//就緒隊列、阻塞隊列和cpu無進程，退出
break;
}
//printf(" %d%d",
readyQueNum,blockQueNum);
if(cpuBusy==0)
{
//cpu空閑，選擇一個進程進入cpu
if(readyQueNum>0)
{
//
選擇緒隊列優先順序最高的進程
cpuProcess
=readyQuePop();
}else{
//
就緒隊列沒有進程，改為選擇阻塞隊列優先順序最高的進程
cpuProcess
=blockQuePop();
}
cpuProcess->cpuTime=
0;
cpuProcess->state=
Run;
cpuBusy=1;
}
timeSlice++;
printf(" 第%d個時間片後： ",
timeSlice);
//
模擬cpu執行1個時間片的操作
cpuWord(cpuProcess);
if(cpuProcess->allTime==0){
cpuProcess->state=
Finish;
//釋放已完成進程的PCB
free(cpuProcess);
cpuBusy=0;
}
//
更新就緒隊列和阻塞隊列里的進程信息
blockQueUpdate();
readyQueUpdate();
//
查看就緒隊列和阻塞隊列的進程信息
readyQueWalk();
blockQueWalk();
if(cpuBusy==1
&&readyQueNum>0
&&
cpuProcess->priority
<readyMaxPriority()){
//需搶佔cpu，當前執行的進程調入阻塞隊列
blockQueQush(cpuProcess);
cpuProcess=readyQuePop();
}
}
printf(" 模擬進程調度演算法結束 ");
return0;
}