????????前言：本文旨在分享如何使用c語言對操作系統(tǒng)中的部分進(jìn)程調(diào)度算法進(jìn)行模擬實(shí)現(xiàn)，以及算法描述的講解，完整代碼放在文章末尾，歡迎大家自行拷貝調(diào)用
目錄
常見的調(diào)度算法
數(shù)據(jù)結(jié)構(gòu)
先來先服務(wù)調(diào)度算法
算法模擬思路：
算法模擬：?
最短作業(yè)優(yōu)先調(diào)度算法
算法模擬思路：
算法模擬：
?最高優(yōu)先級調(diào)度算法
算法模擬思路：
算法模擬：
?時(shí)間片輪轉(zhuǎn)調(diào)度算法
算法模擬思路：
算法模擬：?
完整代碼：
?course.h：?
course.cpp：
test.cpp：?
常見的調(diào)度算法
- 先來先服務(wù)調(diào)度算法
- 最短作業(yè)優(yōu)先調(diào)度算法
- 高響應(yīng)比優(yōu)先調(diào)度算法
- 最高優(yōu)先級調(diào)度算法
- 時(shí)間片輪轉(zhuǎn)調(diào)度算法
- 多級反饋隊(duì)列調(diào)度算法
- ... ...
數(shù)據(jù)結(jié)構(gòu)
typedef struct program
{
char name[20];
int running_time;
int enter_time;
int priority;
int done_time; //用于時(shí)間片輪轉(zhuǎn)
int copyRunning_time; //用于時(shí)間片輪轉(zhuǎn)
int start_time;
program* next;
} Program;
typedef struct programQueue
{
program* firstProg;
program* LastProg;
int size;
} programQueue;先來先服務(wù)調(diào)度算法
????????顧名思義，先來后到，每次從就緒隊(duì)列選擇最先進(jìn)入隊(duì)列的進(jìn)程，然后一直運(yùn)行，直到進(jìn)程退出或被阻塞，才會繼續(xù)從隊(duì)列中選擇第一個(gè)進(jìn)程接著運(yùn)行。但是當(dāng)一個(gè)長作業(yè)先運(yùn)行了，那么后面的短作業(yè)等待的時(shí)間就會很長，不利于短作業(yè)。FCFS 對長作業(yè)有利，適用于 CPU 繁忙型作業(yè)的系統(tǒng)，而不適用于 I/O 繁忙型作業(yè)的系統(tǒng)。
算法模擬思路：
- 首先將輸入的進(jìn)程放入一個(gè)進(jìn)程數(shù)組中，然后根據(jù)進(jìn)程的到達(dá)時(shí)間進(jìn)行排序，將最先到達(dá)的進(jìn)程放入進(jìn)程就緒隊(duì)列中。
- 當(dāng)隊(duì)列不空時(shí)，從隊(duì)頭取出一個(gè)進(jìn)程來執(zhí)行，直至此進(jìn)程執(zhí)行完，并將在此進(jìn)程執(zhí)行期間到達(dá)的進(jìn)程依次加入進(jìn)程就緒隊(duì)列。
- 如果隊(duì)列為空，但進(jìn)程數(shù)組中仍存在未到達(dá)的進(jìn)程，這時(shí)將要到達(dá)進(jìn)程加入進(jìn)程就緒隊(duì)列。
算法模擬：?
//FCFS先來先服務(wù)算法
void FCFS(program pro[], int num)
{
printf("進(jìn)程 到達(dá)時(shí)間 服務(wù)時(shí)間 開始時(shí)間 完成時(shí)間 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間\n");
sortWithEnterTime(pro, num); //按照進(jìn)入順序排序
programQueue* queue = (programQueue*)malloc(sizeof(programQueue));
Queueinit(queue);
EnterQueue(queue, &pro[0]);
int time = pro[0].enter_time;
int pronum = 1; //記錄當(dāng)前的進(jìn)程
float sum_T_time = 0, sum_QT_time = 0;
while (queue->size > 0)
{
program* curpro = poll(queue); //從進(jìn)程隊(duì)列中取出進(jìn)程
if (time < curpro->enter_time)
time = curpro->enter_time;
int done_time = time + curpro->running_time;
int T_time = done_time - curpro->enter_time;
sum_T_time += T_time;
float QT_time = T_time / (curpro->running_time + 0.0);
sum_QT_time += QT_time;
for (int tt = time; tt <= done_time && pronum < num; tt++)
{
//模擬進(jìn)程的執(zhí)行過程
if (tt >= pro[pronum].enter_time)
{
EnterQueue(queue, &pro[pronum]);
pronum++;
}
}
printf("%s\t%d\t%d\t%d\t%d\t%d\t%.2f\n", curpro->name, curpro->enter_time, curpro->running_time, time, done_time, T_time, QT_time);
time += curpro->running_time;
if (queue->size == 0 && pronum < num)
{
//防止出現(xiàn)前一個(gè)進(jìn)程執(zhí)行完到下一個(gè)進(jìn)程到達(dá)之間無進(jìn)程進(jìn)入
EnterQueue(queue, &pro[pronum]);
pronum++;
}
}
printf("平均周轉(zhuǎn)時(shí)間為%.2f\t平均帶權(quán)周轉(zhuǎn)時(shí)間為%.2f\n", sum_T_time / (num + 0.0), sum_QT_time / (num + 0.0));
}最短作業(yè)優(yōu)先調(diào)度算法
????????最短作業(yè)優(yōu)先調(diào)度算法會優(yōu)先選擇運(yùn)行時(shí)間最短的進(jìn)程來運(yùn)行，這有助于提高系統(tǒng)的吞吐量。這顯然對長作業(yè)不利，很容易造成一種極端現(xiàn)象。比如，一個(gè)長作業(yè)在就緒隊(duì)列等待運(yùn)行，而這個(gè)就緒隊(duì)列有非常多的短作業(yè)，那么就會使得長作業(yè)不斷的往后推，周轉(zhuǎn)時(shí)間變長，致使長作業(yè)長期不會被運(yùn)行。
算法模擬思路：
- 首先也是按進(jìn)程的到達(dá)時(shí)間進(jìn)行排序。讓最先到達(dá)的進(jìn)程入隊(duì)。
- 當(dāng)隊(duì)列不空時(shí)，從隊(duì)頭取出一個(gè)進(jìn)程來執(zhí)行，直至此進(jìn)程執(zhí)行完，設(shè)置一個(gè)變量記錄此進(jìn)程執(zhí)行過程中所有到達(dá)的進(jìn)程。
- 將這些到達(dá)的進(jìn)程進(jìn)行排序，按照進(jìn)程服務(wù)時(shí)間的大小。然后將排序好的進(jìn)程數(shù)組中的進(jìn)程依次加入進(jìn)程隊(duì)列。（只排當(dāng)前進(jìn)程執(zhí)行期間到達(dá)的進(jìn)程）
- 此時(shí)也要考慮如果隊(duì)列為空，但進(jìn)程數(shù)組中仍存在未到達(dá)的進(jìn)程，這時(shí)將要到達(dá)進(jìn)程加入進(jìn)程就緒隊(duì)列。
算法模擬：
//短作業(yè)優(yōu)先算法
void SJF(program pro[], int num)
{
printf("進(jìn)程 到達(dá)時(shí)間 服務(wù)時(shí)間 開始時(shí)間 完成時(shí)間 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間\n");
sortWithEnterTime(pro, num);
programQueue* queue = (programQueue*)malloc(sizeof(programQueue));
Queueinit(queue);
EnterQueue(queue, &pro[0]);
int time = pro[0].enter_time;
int pronum = 1; //記錄當(dāng)前的進(jìn)程
float sum_T_time = 0, sum_QT_time = 0;
while (queue->size > 0)
{
program* curpro = poll(queue); //從進(jìn)程隊(duì)列中取出進(jìn)程
if (time < curpro->enter_time)
time = curpro->enter_time;
int done_time = time + curpro->running_time;
int T_time = done_time - curpro->enter_time;
float QT_time = T_time / (curpro->running_time + 0.0);
sum_T_time += T_time;
sum_QT_time += QT_time;
int pre = pronum;
for (int tt = time; tt <= done_time && pronum < num; tt++)
{
//模擬進(jìn)程的執(zhí)行過程
if (tt >= pro[pronum].enter_time)
{
// 統(tǒng)計(jì)從此任務(wù)開始到結(jié)束之間有幾個(gè)進(jìn)程到達(dá)
pronum++;
}
}
sortWithLongth(pro, pre, pronum);//將到達(dá)的進(jìn)程按照服務(wù)時(shí)間排序
for (int i = pre; i < pronum; i++)
{
//將進(jìn)程鏈入隊(duì)列
EnterQueue(queue, &pro[i]);
}
pre = pronum;
printf("%s\t%d\t%d\t%d\t%d\t%d\t%.2f\n", curpro->name, curpro->enter_time, curpro->running_time, time, done_time, T_time, QT_time);
time += curpro->running_time;
if (queue->size == 0 && pronum < num)
{
//防止出現(xiàn)前一個(gè)進(jìn)程執(zhí)行完到下一個(gè)進(jìn)程到達(dá)之間無進(jìn)程進(jìn)入
EnterQueue(queue, &pro[pronum]);
pronum++;
}
}
printf("平均周轉(zhuǎn)時(shí)間為%.2f\t平均帶權(quán)周轉(zhuǎn)時(shí)間為%.2f\n", sum_T_time / (num + 0.0), sum_QT_time / num);
}?最高優(yōu)先級調(diào)度算法
進(jìn)程的優(yōu)先級可以分為，靜態(tài)優(yōu)先級或動態(tài)優(yōu)先級：
- 靜態(tài)優(yōu)先級：創(chuàng)建進(jìn)程時(shí)候，就已經(jīng)確定了優(yōu)先級了，然后整個(gè)運(yùn)行時(shí)間優(yōu)先級都不會變化；
- 動態(tài)優(yōu)先級：根據(jù)進(jìn)程的動態(tài)變化調(diào)整優(yōu)先級，比如如果進(jìn)程運(yùn)行時(shí)間增加，則降低其優(yōu)先級，如果進(jìn)程等待時(shí)間（就緒隊(duì)列的等待時(shí)間）增加，則升高其優(yōu)先級，也就是隨著時(shí)間的推移增加等待進(jìn)程的優(yōu)先級。
該算法也有兩種處理優(yōu)先級高的方法，非搶占式和搶占式：
- 非搶占式：當(dāng)就緒隊(duì)列中出現(xiàn)優(yōu)先級高的進(jìn)程，運(yùn)行完當(dāng)前進(jìn)程，再選擇優(yōu)先級高的進(jìn)程。
- 搶占式：當(dāng)就緒隊(duì)列中出現(xiàn)優(yōu)先級高的進(jìn)程，當(dāng)前進(jìn)程掛起，調(diào)度優(yōu)先級高的進(jìn)程運(yùn)行。
但是依然有缺點(diǎn)，可能會導(dǎo)致低優(yōu)先級的進(jìn)程永遠(yuǎn)不會運(yùn)行
算法模擬思路：
- 首先也是按進(jìn)程的到達(dá)時(shí)間進(jìn)行排序。讓最先到達(dá)的進(jìn)程入隊(duì)。
- 當(dāng)隊(duì)列不空時(shí)，從隊(duì)頭取出一個(gè)進(jìn)程來執(zhí)行，直至此進(jìn)程執(zhí)行完，設(shè)置一個(gè)變量記錄此進(jìn)程執(zhí)行過程中所有到達(dá)的進(jìn)程。
- 將這些到達(dá)的進(jìn)程進(jìn)行排序，按照進(jìn)程優(yōu)先權(quán)排序（權(quán)值小的先入）。然后將排序好的進(jìn)程數(shù)組中的進(jìn)程依次加入進(jìn)程隊(duì)列。（只排當(dāng)前進(jìn)程執(zhí)行期間到達(dá)的進(jìn)程）
- 此時(shí)也要考慮如果隊(duì)列為空，但進(jìn)程數(shù)組中仍存在未到達(dá)的進(jìn)程，這時(shí)將要到達(dá)進(jìn)程加入進(jìn)程就緒隊(duì)列。
算法模擬：
//優(yōu)先權(quán)高者優(yōu)先（HPF）
void HPF(program pro[], int num)
{
printf("進(jìn)程 到達(dá)時(shí)間 服務(wù)時(shí)間 開始時(shí)間 完成時(shí)間 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間\n");
sortWithEnterTime(pro, num);
programQueue* queue = (programQueue*)malloc(sizeof(programQueue));
Queueinit(queue);
EnterQueue(queue, &pro[0]);
int time = pro[0].enter_time;
int pronum = 1; //記錄當(dāng)前的進(jìn)程
float sum_T_time = 0, sum_QT_time = 0;
while (queue->size > 0)
{
program* curpro = poll(queue); //從進(jìn)程隊(duì)列中取出進(jìn)程
if (time < curpro->enter_time)
time = curpro->enter_time;
int done_time = time + curpro->running_time;
int T_time = done_time - curpro->enter_time;
float QT_time = T_time / (curpro->running_time + 0.0);
sum_T_time += T_time;
sum_QT_time += QT_time;
int pre = pronum;
for (int tt = time; tt <= done_time && pronum < num; tt++)
{
//模擬進(jìn)程的執(zhí)行過程
if (tt >= pro[pronum].enter_time)
{
// 統(tǒng)計(jì)從此任務(wù)開始到結(jié)束之間有幾個(gè)進(jìn)程到達(dá)
pronum++;
}
}
sortWithPriority(pro, pre, pronum);//將到達(dá)的進(jìn)程按照服務(wù)時(shí)間排序
for (int i = pre; i < pronum; i++)
{
//將進(jìn)程鏈入隊(duì)列
EnterQueue(queue, &pro[i]);
}
pre = pronum;
printf("%s\t%d\t%d\t%d\t%d\t%d\t%.2f\n", curpro->name, curpro->enter_time, curpro->running_time, time, done_time, T_time, QT_time);
time += curpro->running_time;
if (queue->size == 0 && pronum < num)
{
//防止出現(xiàn)前一個(gè)進(jìn)程執(zhí)行完到下一個(gè)進(jìn)程到達(dá)之間無進(jìn)程進(jìn)入
EnterQueue(queue, &pro[pronum]);
pronum++;
}
}
printf("平均周轉(zhuǎn)時(shí)間為%.2f\t平均帶權(quán)周轉(zhuǎn)時(shí)間為%.2f\n", sum_T_time / (num + 0.0), sum_QT_time / (num + 0.0));
}?時(shí)間片輪轉(zhuǎn)調(diào)度算法
????????每個(gè)進(jìn)程被分配一個(gè)時(shí)間段，稱為時(shí)間片，即允許該進(jìn)程在該時(shí)間段中運(yùn)行。如果時(shí)間片用完，進(jìn)程還在運(yùn)行，那么將會把此進(jìn)程從 CPU 釋放出來，并把 CPU 分配另外一個(gè)進(jìn)程；如果該進(jìn)程在時(shí)間片結(jié)束前阻塞或結(jié)束，則 CPU 立即進(jìn)行切換；如果時(shí)間片設(shè)得太短會導(dǎo)致過多的進(jìn)程上下文切換，降低了 CPU 效率；如果設(shè)得太長又可能引起對短作業(yè)進(jìn)程的響應(yīng)時(shí)間變長。
算法模擬思路：
- 首先也是按進(jìn)程的到達(dá)時(shí)間進(jìn)行排序。讓最先到達(dá)的進(jìn)程入隊(duì)。
- 當(dāng)隊(duì)列不空時(shí)，從隊(duì)頭取出一個(gè)進(jìn)程來執(zhí)行。此時(shí)分兩種情況：①如果當(dāng)前進(jìn)程的剩余服務(wù)時(shí)間不大于時(shí)間片大小，說明此次將會將這個(gè)進(jìn)程執(zhí) 行完畢，在此進(jìn)程執(zhí)行過程中到達(dá)的進(jìn)程需要添加到進(jìn)程就緒隊(duì)列中，這時(shí)就可以輸出 此進(jìn)程執(zhí)行完畢②如果當(dāng)前進(jìn)程的剩余服務(wù)時(shí)間大于時(shí)間片大小，還需將此進(jìn)程執(zhí)行過程中到達(dá) 的進(jìn)程需要添加到進(jìn)程就緒隊(duì)列中，然后此進(jìn)程的剩余服務(wù)時(shí)間減少時(shí)間片大小，此進(jìn) 程重新進(jìn)入進(jìn)程就緒隊(duì)列
- 此時(shí)也要考慮如果隊(duì)列為空，但進(jìn)程數(shù)組中仍存在未到達(dá)的進(jìn)程，這時(shí)將要到達(dá)進(jìn)程加入進(jìn)程就緒隊(duì)列
算法模擬：?
//時(shí)間片輪轉(zhuǎn)（RR）
void RR(program pro[], int num)
{
printf("請輸入時(shí)間片大小");
int timeslice; scanf("%d", ×lice);
printf("進(jìn)程 到達(dá)時(shí)間 服務(wù)時(shí)間 進(jìn)入時(shí)間 完成時(shí)間 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間\n");
sortWithEnterTime(pro, num);
programQueue* queue = (programQueue*)malloc(sizeof(programQueue));
Queueinit(queue);
pro[0].start_time = pro[0].enter_time;
EnterQueue(queue, &pro[0]);
int time = 0;
int pronum = 1;
float sum_T_time = 0, sum_QT_time = 0;
while (queue->size > 0)
{
program* curpro = poll(queue); // 從隊(duì)列中取出頭節(jié)點(diǎn)
if (time < curpro->enter_time)
time = curpro->enter_time;
if (timeslice >= curpro->running_time)
{
// 如果剩余時(shí)間小于時(shí)間片 則此任務(wù)完成
for (int tt = time; tt <= time + curpro->running_time && pronum < num; tt++)
{
// 模擬進(jìn)程的執(zhí)行過程
if (tt >= pro[pronum].enter_time)
{
// 統(tǒng)計(jì)從此任務(wù)開始到結(jié)束之間有幾個(gè)進(jìn)程到達(dá)
pro[pronum].start_time = tt;
EnterQueue(queue, &pro[pronum]);
pronum++;
}
}
time += curpro->running_time;
curpro->running_time = 0;
curpro->done_time = time;
int T_time = curpro->done_time - curpro->start_time;
float QT_time = T_time / (curpro->copyRunning_time + 0.0);
sum_T_time += T_time;
sum_QT_time += QT_time;
printf("%s\t%d\t%d\t %d\t %d\t %d\t %.2f\n", curpro->name, curpro->enter_time, curpro->copyRunning_time,
curpro->start_time, curpro->done_time, T_time, QT_time);
if (queue->size == 0 && pronum < num)
{
//防止出現(xiàn)前一個(gè)進(jìn)程執(zhí)行完到下一個(gè)進(jìn)程到達(dá)之間無進(jìn)程進(jìn)入
pro[pronum].start_time = pro[pronum].enter_time;
EnterQueue(queue, &pro[pronum]);
pronum++;
}
continue;
}
for (int tt = time; tt <= time + timeslice && pronum < num; tt++)
{
//模擬進(jìn)程的執(zhí)行過程
if (tt >= pro[pronum].enter_time)
{
// 統(tǒng)計(jì)從此任務(wù)開始到結(jié)束之間有幾個(gè)進(jìn)程到達(dá)
pro[pronum].start_time = tt;
EnterQueue(queue, &pro[pronum]);
pronum++;
}
}
time += timeslice;
curpro->running_time -= timeslice;
EnterQueue(queue, curpro); //當(dāng)前程序未完成 繼續(xù)添加到隊(duì)列中
if (queue->size == 0 && pronum < num)
{
//防止出現(xiàn)前一個(gè)進(jìn)程執(zhí)行完到下一個(gè)進(jìn)程到達(dá)之間無進(jìn)程進(jìn)入
pro[pronum].start_time = pro[pronum].enter_time;
EnterQueue(queue, &pro[pronum]);
pronum++;
}
}
printf("平均周轉(zhuǎn)時(shí)間為%.2f\t平均帶權(quán)周轉(zhuǎn)時(shí)間為%.2f\n\n", sum_T_time / (num + 0.0), sum_QT_time / (num + 0.0));
}完整代碼：
我們分三個(gè)文件進(jìn)行操作，當(dāng)然大家也可以把三個(gè)文件按順序放在一個(gè)文件里面進(jìn)行操作
course.h：? ? ? 結(jié)構(gòu)體的包含以及函數(shù)的聲明
course.cpp：? 函數(shù)的具體實(shí)現(xiàn)
test.cpp：? ? ? ?主函數(shù)用于調(diào)用其余文件函數(shù)
文章來源：http://www.zghlxwxcb.cn/news/detail-735279.html
?course.h：?
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<malloc.h>
#include<string.h>
#include<stdlib.h>
typedef struct program
{
char name[20];
int running_time;
int enter_time;
int priority;
int done_time; //用于時(shí)間片輪轉(zhuǎn)
int copyRunning_time; //用于時(shí)間片輪轉(zhuǎn)
int start_time;
program* next;
} Program;
typedef struct programQueue
{
program* firstProg;
program* LastProg;
int size;
} programQueue;
//初始化
void Queueinit(programQueue* queue);
//打印
void print(program pro[], int num);
//打印隊(duì)列
void printQueue(programQueue* queue);
//加入進(jìn)程隊(duì)列
void EnterQueue(programQueue* queue, program* pro);
//查詢
program* poll(programQueue* queue);
//輸入
void inputProgram(program pro[], int num);
//根據(jù)時(shí)間排序
void sortWithEnterTime(program pro[], int num);
//FCFS先來先服務(wù)算法
void FCFS(program pro[], int num);
//根據(jù)長度排序
void sortWithLongth(program pro[], int start, int end);
//短作業(yè)優(yōu)先算法
void SJF(program pro[], int num);
//根據(jù)優(yōu)先級排列
void sortWithPriority(program pro[], int start, int end);
//優(yōu)先權(quán)高者優(yōu)先（HPF）
void HPF(program pro[], int num);
//時(shí)間片輪轉(zhuǎn)（RR）
void RR(program pro[], int num);
//選擇菜單
void choiceMenu();
course.cpp：
#define _CRT_SECURE_NO_WARNINGS 1
#include "course.h"
//初始化
void Queueinit(programQueue* queue)
{
if (queue == NULL)
{
return;
}
queue->size = 0;
queue->LastProg = (program*)malloc(sizeof(program));
queue->firstProg = queue->LastProg;
}
//打印
void print(program pro[], int num)
{
for (int i = 0; i < num; i++)
{
printf("%d ", pro[i].enter_time);
}
}
//打印輸出隊(duì)列
void printQueue(programQueue* queue)
{
program* p = queue->firstProg->next;
while (p != NULL)
{
printf("%s ", p->name);
p = p->next;
}
printf("\n");
}
//加入進(jìn)程隊(duì)列
void EnterQueue(programQueue* queue, program* pro)
{
queue->LastProg->next = (program*)malloc(sizeof(program));
queue->LastProg = queue->LastProg->next;
queue->LastProg->enter_time = pro->enter_time;
memcpy(queue->LastProg->name, pro->name, sizeof(pro->name));
queue->LastProg->priority = pro->priority;
queue->LastProg->running_time = pro->running_time;
queue->LastProg->copyRunning_time = pro->copyRunning_time;
queue->LastProg->start_time = pro->start_time;
queue->size++;
}
//查詢
program* poll(programQueue* queue)
{
program* temp = queue->firstProg->next;
if (temp == queue->LastProg)
{
queue->LastProg = queue->firstProg;
queue->size--;
return temp;
}
queue->firstProg->next = queue->firstProg->next->next;
queue->size--;
return temp;
}
//輸入
void inputProgram(program pro[], int num)
{
for (int i = 0; i < num; i++)
{
program prog;
printf("請輸入第%d個(gè)進(jìn)程的名字，到達(dá)時(shí)間，服務(wù)時(shí)間，優(yōu)先級\n", i + 1);
scanf("%s", prog.name);
scanf("%d", &prog.enter_time);
scanf("%d", &prog.running_time);
prog.copyRunning_time = prog.running_time;
scanf("%d", &prog.priority);
pro[i] = prog;
}
}
//根據(jù)時(shí)間排序
void sortWithEnterTime(program pro[], int num)
{
for (int i = 1; i < num; i++)
{
for (int j = 0; j < num - i; j++)
{
if (pro[j].enter_time > pro[j + 1].enter_time)
{
program temp = pro[j];
pro[j] = pro[j + 1];
pro[j + 1] = temp;
}
}
}
}
//FCFS先來先服務(wù)算法
void FCFS(program pro[], int num)
{
printf("進(jìn)程 到達(dá)時(shí)間 服務(wù)時(shí)間 開始時(shí)間 完成時(shí)間 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間\n");
sortWithEnterTime(pro, num); //按照進(jìn)入順序排序
programQueue* queue = (programQueue*)malloc(sizeof(programQueue));
Queueinit(queue);
EnterQueue(queue, &pro[0]);
int time = pro[0].enter_time;
int pronum = 1; //記錄當(dāng)前的進(jìn)程
float sum_T_time = 0, sum_QT_time = 0;
while (queue->size > 0)
{
program* curpro = poll(queue); //從進(jìn)程隊(duì)列中取出進(jìn)程
if (time < curpro->enter_time)
time = curpro->enter_time;
int done_time = time + curpro->running_time;
int T_time = done_time - curpro->enter_time;
sum_T_time += T_time;
float QT_time = T_time / (curpro->running_time + 0.0);
sum_QT_time += QT_time;
for (int tt = time; tt <= done_time && pronum < num; tt++)
{
//模擬進(jìn)程的執(zhí)行過程
if (tt >= pro[pronum].enter_time)
{
EnterQueue(queue, &pro[pronum]);
pronum++;
}
}
printf("%s\t%d\t%d\t%d\t%d\t%d\t%.2f\n", curpro->name, curpro->enter_time, curpro->running_time, time, done_time, T_time, QT_time);
time += curpro->running_time;
if (queue->size == 0 && pronum < num)
{
//防止出現(xiàn)前一個(gè)進(jìn)程執(zhí)行完到下一個(gè)進(jìn)程到達(dá)之間無進(jìn)程進(jìn)入
EnterQueue(queue, &pro[pronum]);
pronum++;
}
}
printf("平均周轉(zhuǎn)時(shí)間為%.2f\t平均帶權(quán)周轉(zhuǎn)時(shí)間為%.2f\n", sum_T_time / (num + 0.0), sum_QT_time / (num + 0.0));
}
//根據(jù)長度排序
void sortWithLongth(program pro[], int start, int end)
{
int len = end - start;
if (len == 1) return;
for (int i = 1; i < len; i++) {
for (int j = start; j < end - i; j++)
{
if (pro[j].running_time > pro[j + 1].running_time)
{
program temp = pro[j];
pro[j] = pro[j + 1];
pro[j + 1] = temp;
}
}
}
}
//短作業(yè)優(yōu)先算法
void SJF(program pro[], int num)
{
printf("進(jìn)程 到達(dá)時(shí)間 服務(wù)時(shí)間 開始時(shí)間 完成時(shí)間 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間\n");
sortWithEnterTime(pro, num);
programQueue* queue = (programQueue*)malloc(sizeof(programQueue));
Queueinit(queue);
EnterQueue(queue, &pro[0]);
int time = pro[0].enter_time;
int pronum = 1; //記錄當(dāng)前的進(jìn)程
float sum_T_time = 0, sum_QT_time = 0;
while (queue->size > 0)
{
program* curpro = poll(queue); //從進(jìn)程隊(duì)列中取出進(jìn)程
if (time < curpro->enter_time)
time = curpro->enter_time;
int done_time = time + curpro->running_time;
int T_time = done_time - curpro->enter_time;
float QT_time = T_time / (curpro->running_time + 0.0);
sum_T_time += T_time;
sum_QT_time += QT_time;
int pre = pronum;
for (int tt = time; tt <= done_time && pronum < num; tt++)
{
//模擬進(jìn)程的執(zhí)行過程
if (tt >= pro[pronum].enter_time)
{
// 統(tǒng)計(jì)從此任務(wù)開始到結(jié)束之間有幾個(gè)進(jìn)程到達(dá)
pronum++;
}
}
sortWithLongth(pro, pre, pronum);//將到達(dá)的進(jìn)程按照服務(wù)時(shí)間排序
for (int i = pre; i < pronum; i++)
{
//將進(jìn)程鏈入隊(duì)列
EnterQueue(queue, &pro[i]);
}
pre = pronum;
printf("%s\t%d\t%d\t%d\t%d\t%d\t%.2f\n", curpro->name, curpro->enter_time, curpro->running_time, time, done_time, T_time, QT_time);
time += curpro->running_time;
if (queue->size == 0 && pronum < num)
{
//防止出現(xiàn)前一個(gè)進(jìn)程執(zhí)行完到下一個(gè)進(jìn)程到達(dá)之間無進(jìn)程進(jìn)入
EnterQueue(queue, &pro[pronum]);
pronum++;
}
}
printf("平均周轉(zhuǎn)時(shí)間為%.2f\t平均帶權(quán)周轉(zhuǎn)時(shí)間為%.2f\n", sum_T_time / (num + 0.0), sum_QT_time / num);
}
//根據(jù)優(yōu)先級排列
void sortWithPriority(program pro[], int start, int end)
{
int len = end - start;
if (len == 1) return;
for (int i = 1; i < len; i++)
{
for (int j = start; j < end - i; j++)
{
if (pro[j].priority > pro[j + 1].priority)
{
program temp = pro[j];
pro[j] = pro[j + 1];
pro[j + 1] = temp;
}
}
}
}
//優(yōu)先權(quán)高者優(yōu)先（HPF）
void HPF(program pro[], int num)
{
printf("進(jìn)程 到達(dá)時(shí)間 服務(wù)時(shí)間 開始時(shí)間 完成時(shí)間 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間\n");
sortWithEnterTime(pro, num);
programQueue* queue = (programQueue*)malloc(sizeof(programQueue));
Queueinit(queue);
EnterQueue(queue, &pro[0]);
int time = pro[0].enter_time;
int pronum = 1; //記錄當(dāng)前的進(jìn)程
float sum_T_time = 0, sum_QT_time = 0;
while (queue->size > 0)
{
program* curpro = poll(queue); //從進(jìn)程隊(duì)列中取出進(jìn)程
if (time < curpro->enter_time)
time = curpro->enter_time;
int done_time = time + curpro->running_time;
int T_time = done_time - curpro->enter_time;
float QT_time = T_time / (curpro->running_time + 0.0);
sum_T_time += T_time;
sum_QT_time += QT_time;
int pre = pronum;
for (int tt = time; tt <= done_time && pronum < num; tt++)
{
//模擬進(jìn)程的執(zhí)行過程
if (tt >= pro[pronum].enter_time)
{
// 統(tǒng)計(jì)從此任務(wù)開始到結(jié)束之間有幾個(gè)進(jìn)程到達(dá)
pronum++;
}
}
sortWithPriority(pro, pre, pronum);//將到達(dá)的進(jìn)程按照服務(wù)時(shí)間排序
for (int i = pre; i < pronum; i++)
{
//將進(jìn)程鏈入隊(duì)列
EnterQueue(queue, &pro[i]);
}
pre = pronum;
printf("%s\t%d\t%d\t%d\t%d\t%d\t%.2f\n", curpro->name, curpro->enter_time, curpro->running_time, time, done_time, T_time, QT_time);
time += curpro->running_time;
if (queue->size == 0 && pronum < num)
{
//防止出現(xiàn)前一個(gè)進(jìn)程執(zhí)行完到下一個(gè)進(jìn)程到達(dá)之間無進(jìn)程進(jìn)入
EnterQueue(queue, &pro[pronum]);
pronum++;
}
}
printf("平均周轉(zhuǎn)時(shí)間為%.2f\t平均帶權(quán)周轉(zhuǎn)時(shí)間為%.2f\n", sum_T_time / (num + 0.0), sum_QT_time / (num + 0.0));
}
//時(shí)間片輪轉(zhuǎn)（RR）
void RR(program pro[], int num)
{
printf("請輸入時(shí)間片大小");
int timeslice; scanf("%d", ×lice);
printf("進(jìn)程 到達(dá)時(shí)間 服務(wù)時(shí)間 進(jìn)入時(shí)間 完成時(shí)間 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間\n");
sortWithEnterTime(pro, num);
programQueue* queue = (programQueue*)malloc(sizeof(programQueue));
Queueinit(queue);
pro[0].start_time = pro[0].enter_time;
EnterQueue(queue, &pro[0]);
int time = 0;
int pronum = 1;
float sum_T_time = 0, sum_QT_time = 0;
while (queue->size > 0)
{
program* curpro = poll(queue); // 從隊(duì)列中取出頭節(jié)點(diǎn)
if (time < curpro->enter_time)
time = curpro->enter_time;
if (timeslice >= curpro->running_time)
{
// 如果剩余時(shí)間小于時(shí)間片 則此任務(wù)完成
for (int tt = time; tt <= time + curpro->running_time && pronum < num; tt++)
{
// 模擬進(jìn)程的執(zhí)行過程
if (tt >= pro[pronum].enter_time)
{
// 統(tǒng)計(jì)從此任務(wù)開始到結(jié)束之間有幾個(gè)進(jìn)程到達(dá)
pro[pronum].start_time = tt;
EnterQueue(queue, &pro[pronum]);
pronum++;
}
}
time += curpro->running_time;
curpro->running_time = 0;
curpro->done_time = time;
int T_time = curpro->done_time - curpro->start_time;
float QT_time = T_time / (curpro->copyRunning_time + 0.0);
sum_T_time += T_time;
sum_QT_time += QT_time;
printf("%s\t%d\t%d\t %d\t %d\t %d\t %.2f\n", curpro->name, curpro->enter_time, curpro->copyRunning_time,
curpro->start_time, curpro->done_time, T_time, QT_time);
if (queue->size == 0 && pronum < num)
{
//防止出現(xiàn)前一個(gè)進(jìn)程執(zhí)行完到下一個(gè)進(jìn)程到達(dá)之間無進(jìn)程進(jìn)入
pro[pronum].start_time = pro[pronum].enter_time;
EnterQueue(queue, &pro[pronum]);
pronum++;
}
continue;
}
for (int tt = time; tt <= time + timeslice && pronum < num; tt++)
{
//模擬進(jìn)程的執(zhí)行過程
if (tt >= pro[pronum].enter_time)
{
// 統(tǒng)計(jì)從此任務(wù)開始到結(jié)束之間有幾個(gè)進(jìn)程到達(dá)
pro[pronum].start_time = tt;
EnterQueue(queue, &pro[pronum]);
pronum++;
}
}
time += timeslice;
curpro->running_time -= timeslice;
EnterQueue(queue, curpro); //當(dāng)前程序未完成 繼續(xù)添加到隊(duì)列中
if (queue->size == 0 && pronum < num)
{
//防止出現(xiàn)前一個(gè)進(jìn)程執(zhí)行完到下一個(gè)進(jìn)程到達(dá)之間無進(jìn)程進(jìn)入
pro[pronum].start_time = pro[pronum].enter_time;
EnterQueue(queue, &pro[pronum]);
pronum++;
}
}
printf("平均周轉(zhuǎn)時(shí)間為%.2f\t平均帶權(quán)周轉(zhuǎn)時(shí)間為%.2f\n\n", sum_T_time / (num + 0.0), sum_QT_time / (num + 0.0));
}
//選擇菜單
void choiceMenu()
{
printf("請選擇進(jìn)程調(diào)度算法：\n");
printf("1.先來先服務(wù)算法\n");
printf("2.短進(jìn)程優(yōu)先算法\n");
printf("3.高優(yōu)先級優(yōu)先\n");
printf("4.時(shí)間片輪轉(zhuǎn)算法\n");
}test.cpp：?
#define _CRT_SECURE_NO_WARNINGS 1
#include"course.h"
int main()
{
int proNum = 5; //5個(gè)進(jìn)程
program pro[5];
inputProgram(pro, proNum);
choiceMenu();
int choice;
do
{
scanf("%d", &choice);
switch (choice)
{
case 1:
system("cls");
FCFS(pro, proNum);
choiceMenu();
break;
case 2:
system("cls");
SJF(pro, proNum);
choiceMenu();
break;
case 3:
system("cls");
HPF(pro, proNum);
choiceMenu();
break;
case 4:
system("cls");
RR(pro, proNum);
choiceMenu();
break;
default:
printf("輸入錯誤，請重新嘗試\n");
break;
}
} while (choice);
return 0;
}
本次的分享就到此為止了，感謝您的支持，如果您有不同意見，歡迎評論區(qū)積極交流文章來源地址http://www.zghlxwxcb.cn/news/detail-735279.html
到了這里，關(guān)于操作系統(tǒng)進(jìn)程調(diào)度算法的模擬實(shí)現(xiàn)（c語言版本）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
