【作業系統】先來先服務和短作業優先演算法（C語言實現）
- 2020 年 11 月 27 日
- 筆記
- C語言, 先來先服務和短作業優先進程調度演算法, 作業系統
【作業系統】 先來先服務演算法和短作業優先演算法實現
介紹:
1.先來先服務 (FCFS: first come first service)
如果早就緒的進程排在就緒隊列的前面，遲就緒的進程排在就緒隊列的後面，那麼先來先服務(FCFS: first come first service)總是把當前處於就緒隊列之首的那個進程調度到運行狀態。也就說，它只考慮進程進入就緒隊列的先後，而不考慮它的下一個CPU周期的長短及其他因素。FCFS演算法簡單易行，是一種非搶佔式策略，但性能卻不大好。
簡單來說，先來先服務就是那個進程到達時間最早，那麼CPU就先處理哪個進程。
2.短作業優先（SJF, Shortest Job First）
對預計執行時間短的作業（進程）優先分派處理機。通常後來的短作業不搶先正在執行的作業。
也就是說，不但要考慮進程的到達時間，還要考慮進程需要運行的時間。
當一個進程正在運行時，假如有其他的進程到達，那麼這些到達的進程就需要按照其需要運行的時間長短排序，運行時間短的在前，運行時間長的在後。
例子：
話不多說，直接上程式碼。第一次寫，有很多不足的地方。希望大家看到可以幫忙糾正一下，謝謝大家。
#include <stdio.h>
#include <stdlib.h>
#define MAX 10
typedef struct PCB {
int id,arrive_time,service_time,start_time,finish_time; //進程id、到達時間、服務時間、開始時間、完成時間
float zhouzhuan_time,daiquanzhouzhuan_time; //周轉時間、帶權周轉時間。。。只能說我的拼英。。。emm，。。尷尬。。
int status;
}PCB;
typedef enum {
OK,ERROR
}Status;
typedef enum {
FALSE,TRUE
}Bool;
typedef PCB datatype;
typedef struct LinkQueue {
int front;
int rear;
int length;
datatype* base;
}quene;
int arrive[MAX]; // 記錄每個作業的到達時間
int service[MAX]; //記錄每個作業的服務時間
int num; //輸入的進程個數
quene init(){
quene q_pcb;
q_pcb.base = (datatype *)malloc(sizeof(datatype)*MAX);
q_pcb.front = q_pcb.rear = 0;
q_pcb.length = 0;
return q_pcb;
}
Bool isFull(quene *q) {
if ((q->rear + 1) % MAX == q->front) {
return TRUE;
}
return FALSE;
}
Bool isEmpty(quene *q) {
if (q->rear == q->front) {
return TRUE;
}
return FALSE;
}
Status rudui(quene *q,datatype p){ //入隊。。。emmmm。。。尷尬。。。當時腦子抽了。。寫成了拼英。 後來寫完了。。。用的地方太多了。。就沒修改了。。
if (isFull(q))
{
return ERROR;
}
*(q->base + q->rear) = p;
q->rear=(q->rear + 1) % MAX;
q->length ++;
return OK;
}
Status chudui(quene *q){ //出隊。。。emmmm。。。尷尬。。。當時腦子抽了。。寫成了拼英。 後來寫完了。。。用的地方太多了。。就沒修改了。。
if (isEmpty(q) == TRUE) {
return ERROR;
}
q->length --;
q->front = (q->front+1)%MAX;
return OK;
}
void input(quene *q) /* 建立進程式控制制塊隊列 */
{
printf("請輸入進程的個數:\n");
scanf("%d",&num);
printf("請輸入各進程的服務時間:\n");
int count = num;
int count2 = num;
int i = 0;
while(i < count2)
{
datatype temp;
temp.id = i;
temp.status = 0; //將所有的訪問狀態都置為0 表示未加入隊列
scanf("%d",&temp.service_time);
service[i] = temp.service_time;
rudui(q,temp);
i ++;
}
i = 0;
printf("length=%4d\n",q->length);
printf("請輸入各進程的到達時間:\n");
while (i < count)
{
scanf("%d",&(q->base+i)->arrive_time);
arrive[i] = (q->base+i)->arrive_time;
i ++;
}
}
void print_pcb(quene *q){ //格式化列印 ， 並計算相關的資訊
float ave_zhouzhuan = 0;
float ave_daiquan = 0;
for (int i = 0; i < q->length; i++)
{
if(i == 0){
(q->base+i)->start_time = (q->base+i)->start_time; //第一個的開始時間
}
else
{
(q->base+i)->start_time = (q->base+i-1)->finish_time;
}
(q->base+i)->finish_time = (q->base+i)->start_time + (q->base+i)->service_time; //結束時間
(q->base+i)->zhouzhuan_time = (float)((q->base+i)->finish_time - (q->base+i)->arrive_time); //周轉時間
if((q->base+i)->service_time == 0){
(q->base+i)->daiquanzhouzhuan_time = (q->base+i)->zhouzhuan_time;
}
else
{
(q->base+i)->daiquanzhouzhuan_time = (q->base+i)->zhouzhuan_time/(q->base+i)->service_time; //帶權周轉時間
}
ave_zhouzhuan += (q->base+i)->zhouzhuan_time;
ave_daiquan += (q->base+i)->daiquanzhouzhuan_time;
}
printf("進程ID\t到達時間\t服務時間\t開始時間\t結束時間\t周轉時間\t帶權周轉時間\n");
for (int i = 0; i < q->length; i++)
{
printf("%4d\t%8d\t%8d\t%8d\t%8d\t%8f\t%8f\n",(q->base+i)->id,(q->base+i)->arrive_time,(q->base+i)->service_time,(q->base+i)->start_time,(q->base+i)->finish_time,(q->base+i)->zhouzhuan_time,(q->base+i)->daiquanzhouzhuan_time);
}
printf("平均周轉時間=%f\n",ave_zhouzhuan/q->length);
printf("平均帶權周轉時間=%f\n",ave_daiquan/q->length);
}
void sort(int array[]){ //排序。 從大到小的順序。
int temp;
for(int i = 0;i < num -1;i ++){
for(int j = i + 1;j < num;j ++){
if(array[i] > array[j]){
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
}
int select__min_arrive(quene *q){ //從到達的進程隊列中挑選出到達時間最早的
int min = (q->base+q->front)->arrive_time;
for(int i = 1;i < q->length; i ++){
if (min > (q->base+q->front+i)->arrive_time && (q->base+q->front+i)->status == 0)
{
min = (q->base+q->front+i)->arrive_time;
}
}
return min;
}
int select__min_service(quene *qu){ //從到達的進程隊列中挑選出所有進程中最短一個進程的服務時間
int min = (qu->base+qu->front)->service_time;
for(int i = 0;i < qu->length; i ++){
if (min > (qu->base+qu->front+i)->service_time && (qu->base+qu->front+i)->status == 0)
{
min = (qu->base+qu->front+i)->service_time;
}
}
return min;
}
int main(){
quene q = init();
input(&q);
int select;
sort(arrive); //按照到達時間排序
sort(service); // 按照服務時間長短排序
printf("\n");
printf("1.先來先服務\t2.短作業優先\t請輸入你的選擇：\n");
scanf("%d",&select);
quene new_q,new_quene; //兩個隊列。第一個表示先來先服務隊列。第二個是短作業優先隊列。
switch (select)
{
case 1:
new_q = init();
for(int i = 0;i < q.length; i ++){ //先來先服務 ： 按照到達時間排序然後依次查找入隊列
for(int j = 0;j < q.length;j ++){
if((q.base+q.front+j)->arrive_time == arrive[i] && (q.base+q.front+j)->status == 0){
rudui(&new_q,*(q.base+j));
(q.base+j)->status = 1;
}
}
}
print_pcb(&new_q);
break;
case 2:
int flag = 0;
new_quene = init();
quene min_arrive = init(); //用來存放當一個進程正在運行時，新到達的隊列
int count = 0;
for(int i = 0;i < q.length; i ++){ //先讓第一個到達的入隊列
for(int j = 0;j < q.length;j ++){
if(i == 0 && flag == 0){ //保證第一個到達作業裝入系統
if((q.base+j)->arrive_time == arrive[0] && (q.base+j)->status == 0){
rudui(&new_quene,*(q.base+j));
(q.base+j)->status = 1; //防止重複訪問
break;
}
}
else{ //後面的按照服務時間長短入隊列
// if((q.base+j)->service_time == service[i] && (q.base+j)->status == 0){
// // sjf[index] = (q.base+j)->id;
// // index ++;
// rudui(&new_quene,*(q.base+j));
// (q.base+j)->status = 1;
// }
}
}
break;
}
int service,arrive,start,finish; //用於存放正在運行的進程的服務時間、到達時間、開始時間、完成時間。
for(int i = 0; i < q.length;i ++){ //按照sjf演算法確定後續入隊的順序
if (i == 0)
{
start = (new_quene.base+i)->arrive_time;
(new_quene.base+i)->start_time = (new_quene.base+i)->arrive_time;
(new_quene.base+i)->finish_time = (new_quene.base+i)->arrive_time + (new_quene.base+i)->service_time;
}
else
{
start = (new_quene.base+i-1)->finish_time;
(new_quene.base+i)->finish_time = (new_quene.base+i)->start_time + (new_quene.base+i)->service_time;
}
service = (new_quene.base+i)->service_time;
arrive = (new_quene.base+i)->arrive_time;
finish = start + (new_quene.base+i)->service_time;
for(int j = 0;j < q.length;j ++){ //假如一個進程運行結束前，有新的進程到達，那麼就加入一個臨時隊列。
if ((q.base+j)->arrive_time <= finish && (q.base+j)->status == 0)
{
// printf("進程ID\t到達時間\t服務時間\n"); //調試的時候用的
// printf("%8d\t%8d\t%8d\n",(q.base+j)->id,(q.base+j)->arrive_time,(q.base+j)->service_time);
rudui(&min_arrive,*(q.base+j));
count ++;
flag = 1;
}
}
if(flag == 0){ //在一個進程執行時，如果沒有其他的進程到達，那就直接挑選出最早到達的加入到sjf作業調度隊列
int min_arrive_time = select__min_arrive(&q);
for (int j = 0; j < q.length; j++)
{
if((q.base+j)->arrive_time == min_arrive_time && (q.base+j)->status == 0){
(q.base+j)->status = 1;
rudui(&new_quene,*(q.base+j));
break;
}
}
}
if (flag == 1) //在一個進程執行時，如果有其他的進程到達，那麼就要從已經到達的隊列中挑選出服務時間最短的加入sjf隊列
{
// printf("進入待隊列的進程ID\t到達時間\t服務時間\n"); //主要時調試的時候用的
// for (int j = 0; j < min_arrive.length; j++)
// {
// printf("%8d\t%8d\t%8d\n",(min_arrive.base+min_arrive.front+j)->id,(min_arrive.base+min_arrive.front+j)->arrive_time,(min_arrive.base+min_arrive.front+j)->service_time);
// }
int min_service_time = select__min_service(&min_arrive);
for (int j = 0; j < q.length; j++)
{
// printf("%d\t | \t", (q.base+j)->status);
if((q.base+j)->service_time == min_service_time && (q.base+j)->status == 0){
(q.base+j)->status = 1;
rudui(&new_quene,*(q.base+j));
flag = 0;
break;
}
}
}
for (int j = 0; j < count; j++) //因為每一個作業運行時，都可能會有新到達的進程，所以需要先把上一個進程運行時到達的進程隊列給清空
{
chudui(&min_arrive);
}
count = 0;
}
for(int i = 0;i < new_quene.length; i ++){ //因為計算周轉時間等的都放在print_PCB函數中了，所以為了後面直接用那個函數所以就又初始化了一遍
(new_quene.base + i)->start_time = 0;
(new_quene.base + i)->finish_time = 0;
}
print_pcb(&new_quene); //格式化列印並計算開始時間。完成時間，等的一些數據
break;
}
system("pause");
}
希望大家看到不足的地方可以糾正一下。謝謝大家！
完美撒花！
