C語言模擬實現先來先服務(FCFS)和短作業優先(SJF)調度演算法
說明
該並非實現真正的處理機調度，只是通過演算法模擬這兩種調度演算法的過程。
運行過程如下：
- 輸入進程個數
- 輸入各個進程的到達事件
- 輸入各個進程的要求服務事件
- 選擇一種調度演算法
- 程式給出調度結果：各進程的完成時間、周轉時間、帶權周轉時間。
運行截圖
- FCFS
- SJF
程式碼如下
#include <stdio.h>
#include <stdlib.h>
#define MAX_DURANCE 1e6
/*
author: Qin Guoqing;
date:2020年11月17日 17點37分;
description: 模擬實現短作業優先和先來先服務兩種調度演算法。
*/
int count_process; //進程數
int *coming_times; //達到時間
int *serve_times; //服務時間
int *finished_times; //完成時間
int *turnover_times; //周轉時間
int *waiting_times; //等待時間
float *turnover_times_weight; //帶權周轉時間
int method_choosen; //所選調度演算法
void input_process_count(); //輸入進程個數
void input_coming_time(); //輸入進程到達時間
void input_serve_time(); //輸入進程服務時間
void print_inputInfo(); //列印輸入資訊
void choose_method(); //選擇調度演算法
void inatialize(); //數據初始化
void SJF(); //短作業優先
void FCFS(); //先來先服務
void print_schedulInfo(); //列印調度資訊
int main()
{
input_process_count();
input_coming_time();
input_serve_time();
print_inputInfo();
choose_method();
inatialize();
switch (method_choosen)
{
case 1:
FCFS();
break;
default:
SJF();
break;
}
print_schedulInfo();
system("pause");
return 0;
}
void input_process_count()
{
puts("please input the amount of process:");
scanf("%d", &count_process);
}
void input_coming_time()
{
coming_times = (int *)malloc(sizeof(int) * count_process);
puts("please input the coming_time of the processes:");
for (size_t i = 0; i < count_process; i++)
{
scanf("%d", &coming_times[i]);
}
}
void input_serve_time()
{
serve_times = (int *)malloc(sizeof(int) * count_process);
puts("please input the serve_time of the processes:");
for (size_t i = 0; i < count_process; i++)
{
scanf("%d", &serve_times[i]);
}
}
void print_inputInfo()
{
puts("###################################################");
printf("the amount of processes inputed by the user:n = %d\n", count_process);
puts("here are the coming_times of those processes:");
for (int i = 0; i < count_process; i++)
{
printf("%d ", coming_times[i]);
}
printf("\n");
puts("here are the serve_time of those processes:");
for (int i = 0; i < count_process; i++)
{
printf("%d ", serve_times[i]);
}
printf("\n");
}
void choose_method()
{
puts("please choose a schedul method: 1-FCFS,2-SJF:");
scanf("%d", &method_choosen);
}
void FCFS()
{
int current = 0;
int co_coming_times[count_process];
for (size_t i = 0; i < count_process; i++)
{
co_coming_times[i] = coming_times[i];
}
for (size_t j = 0; j < count_process; j++)
{
int earliest = 0, min = co_coming_times[0];
int i;
//先找到當前最先到達的進程，需要使用到達時間的副本來找
for (i = 1; i < count_process; i++)
{
if (co_coming_times[i] < min)
{
min = co_coming_times[i];
earliest = i;
}
}
co_coming_times[earliest] = MAX_DURANCE;
//上一個進程執行完時有可能下個進程還沒到達
if (coming_times[earliest] > current)
{
current = coming_times[earliest];
}
//更新其完成時間
finished_times[earliest] = current + serve_times[earliest];
//等待時間
waiting_times[earliest] = current - coming_times[earliest];
//更新當前時間
current += serve_times[earliest];
//更新周轉時間
turnover_times[earliest] = serve_times[earliest] + waiting_times[earliest];
//更新帶權周轉時間
turnover_times_weight[earliest] = (float)turnover_times[earliest] / (float)serve_times[earliest];
}
}
void SJF()
{
int current = 0;
int co_serve_times[count_process], co_coming_times[count_process];
//服務時間的副本
for (size_t i = 0; i < count_process; i++)
{
co_serve_times[i] = serve_times[i];
}
//到達時間的副本
for (size_t i = 0; i < count_process; i++)
{
co_coming_times[i] = coming_times[i];
}
int flag = 0; //標識當前時間下有無已經到達的進程
for (size_t i = 0; i < count_process; i++)
{
int min_p = 0, min = co_serve_times[0], early = co_coming_times[0];
//min_p: 當前調度進程的xiabiao
//min: 當前調度進程的服務時間
//early:當前調度進程的到達時間
for (size_t j = 1; j < count_process; j++)
{
if (co_coming_times[j] <= current && co_serve_times[j] < min)
{
flag = 1;
min = co_serve_times[j];
min_p = j;
}
}
//若當前時間無進程到達，則選擇即將最早到達的那個進程
if (flag == 0)
{
for (size_t m = 1; m < count_process; m++)
{
if (co_coming_times[m] < early)
{
early = co_coming_times[m];
min_p = m;
current = early;
}
}
}
co_coming_times[min_p] = MAX_DURANCE;
co_serve_times[min_p] = MAX_DURANCE;
finished_times[min_p] = current + serve_times[min_p];
waiting_times[min_p] = current - coming_times[min_p];
current = finished_times[min_p];
turnover_times[min_p] = waiting_times[min_p] + serve_times[min_p];
turnover_times_weight[min_p] = (float)turnover_times[min_p] / (float)serve_times[min_p];
}
}
void print_schedulInfo()
{
puts("####################################################################################################");
puts("here is the information of the schedul:");
puts("P_name(ID) arrived_time served_time finished_time turnover_time turnover_time_weight");
for (size_t i = 0; i < count_process; i++)
{
printf("%10d %12d %11d %14d %13d %20f\n", i, coming_times[i], serve_times[i], finished_times[i], turnover_times[i], turnover_times_weight[i]);
}
float average_turnover_time, sum_turnover_time = 0; //平均周轉時間和總周轉時間
float average_turnover_time_weight, sum_turnover_time_weight = 0; //平均帶權周轉時間和總帶權周轉時間
for (size_t i = 0; i < count_process; i++)
{
sum_turnover_time += turnover_times[i];
sum_turnover_time_weight += turnover_times_weight[i];
}
average_turnover_time = sum_turnover_time / count_process;
average_turnover_time_weight = sum_turnover_time_weight / count_process;
printf("the average time of turnover time is: %.2f\n", average_turnover_time);
printf("the average time of turnover time with weight is: %.2f\n", average_turnover_time_weight);
puts("####################################################################################################");
}
void inatialize()
{
finished_times = (int *)malloc(sizeof(int) * count_process);
turnover_times = (int *)malloc(sizeof(int) * count_process);
turnover_times_weight = (float *)malloc(sizeof(float) * count_process);
waiting_times = (int *)malloc(sizeof(int) * count_process);
}
