【作業系統】 先來先服務演算法和短作業優先演算法實作
介紹:
1.先來先服務 (FCFS: first come first service)
如果早就緒的行程排在就緒佇列的前面，遲就緒的行程排在就緒佇列的后面，那么先來先服務(FCFS: first come first service)總是把當前處于就緒佇列之首的那個行程調度到運行狀態，也就說，它只考慮行程進入就緒佇列的先后，而不考慮它的下一個CPU周期的長短及其他因素，FCFS演算法簡單易行，是一種非搶占式策略，但性能卻不大好，
簡單來說，先來先服務就是那個行程到達時間最早，那么CPU就先處理哪個行程，
2.短作業優先（SJF, Shortest Job First）
對預計執行時間短的作業（行程）優先分派處理機，通常后來的短作業不搶先正在執行的作業，
也就是說，不但要考慮行程的到達時間，還要考慮行程需要運行的時間，
當一個行程正在運行時，假如有其他的行程到達，那么這些到達的行程就需要按照其需要運行的時間長短排序，運行時間短的在前，運行時間長的在后，
3.例子：
4.運行截圖
1.先來先服務
2.短作業優先
5.話不多說，直接上代碼，第一次寫，有很多不足的地方，希望大家看到可以幫忙糾正一下，謝謝大家，
#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)->arrive_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+new_quene.front+i)->arrive_time;
(new_quene.base+new_quene.front+i)->start_time = (new_quene.base+new_quene.front+i)->arrive_time;
(new_quene.base+new_quene.front+i)->finish_time = (new_quene.base+new_quene.front+i)->arrive_time + (new_quene.base+new_quene.front+i)->service_time;
}
else
{
start = (new_quene.base+new_quene.front+i-1)->finish_time;
(new_quene.base+new_quene.front+i)->finish_time = (new_quene.base+new_quene.front+i)->start_time + (new_quene.base+new_quene.front+i)->service_time;
}
service = (new_quene.base+new_quene.front+i)->service_time;
arrive = (new_quene.base+new_quene.front+i)->arrive_time;
finish = start + (new_quene.base+new_quene.front+i)->service_time;
for(int j = 0;j <= q.length;j ++){ //假如一個行程運行結束前，有新的行程到達，那么就加入一個臨時佇列，
if ((q.base+q.front+j)->arrive_time <= finish && (q.base+q.front+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+q.front+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+q.front+j)->arrive_time == min_arrive_time && (q.base+q.front+j)->status == 0){
(q.base+q.front+j)->status = 1;
rudui(&new_quene,*(q.base+q.front+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+q.front+j)->service_time == min_service_time && (q.base+q.front+j)->status == 0){
(q.base+q.front+j)->status = 1;
rudui(&new_quene,*(q.base+q.front+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");
}
希望大家看到不足的地方可以糾正一下，謝謝大家！
完美撒花！
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/228331.html
標籤：C++