CPU Scheduling.c

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <string.h>
#include <time.h>

#define getpch(type) (type*)malloc(sizeof(type))

typedef struct pcb PCB;

struct pcb {
    int id;
    char name[10];
    int time_start;
    int time_need;
    int time_left;
    int time_used;
    char state;
};

void _sleep(int n) {
    clock_t goal;
    goal = (clock_t) n * CLOCKS_PER_SEC + clock();
    while (goal > clock());
}

char _keygo() {
    char c;
    printf("Press any key to exit.");
    c = getch();
    return c;
}


int time_unit = 2;
const int maxnum = 10;
int num = 5;
PCB pcbdata[maxnum] = {
    {1000, "A", 0, 4, 4, 0, 'R'},
    {1001, "B", 1, 3, 3, 0, 'R'},
    {1002, "C", 2, 5, 5, 0, 'R'},
    {1003, "D", 3, 2, 2, 0, 'R'},
    {1004, "E", 4, 4, 4, 0, 'R'},
};

PCB pcbdata_1[maxnum] = {
    {1010, "Job1", 1, 9, 9, 0, 'R'},
    {1011, "Job2", 1, 16, 16, 0, 'R'},
    {1012, "Job3", 1, 3, 3, 0, 'R'},
    {1013, "Job4", 1, 11, 11, 0, 'R'},
};

PCB pcbdata_2[maxnum] = {
    {1020, "P1", 10, 8, 8, 0, 'R'},
    {1021, "P2", 12, 12, 12, 0, 'R'},
    {1022, "P3", 14, 4, 4, 0, 'R'},
    {1023, "P4", 16, 6, 6, 0, 'R'},
};

PCB pcbdata_3[maxnum] = {
    {1030, "A", 0, 7, 7, 0, 'R'},
    {1031, "B", 5, 4, 4, 0, 'R'},
    {1032, "C", 7, 13, 13, 0, 'R'},
    {1033, "D", 12, 9, 9, 0, 'R'},
};

int ready[maxnum];
int order[maxnum];

void process_each_slice(pcb* p) {
    if (p->time_used == 0) {
        printf("Process %s start.\n", p->name);
    }
    if (p->time_left <= 0)
        return ;
    p->time_left = p->time_left - 1;
    p->time_used = p->time_used + 1;
    printf("Process %s time left: %d\n", p->name, p->time_left);
    
}

void input() {
    int i;
    printf("The num of process is: ");
    scanf("%d", &num);
    for (i=0; i<num; ++i){
        pcbdata[i].id = 1000 + i;
        printf("Input the name of process#%d", i+1);
        scanf("%s", *pcbdata[i].name);
        printf("Input the averal time of process#%d", i+1);
        scanf("%d", &pcbdata[i].time_start);
        printf("Input the serve time ot process#%d", i+1);
        scanf("%d", &pcbdata[i].time_need);
        // Initialize the time_left, equaling to time_need
        pcbdata[i].time_left = pcbdata[i].time_need;
        printf("\n");
        pcbdata[i].time_used = 0;
        pcbdata[i].state = 'R';
    }
}

void FCFS() {
    int i, j, temp, used_time;
    double k;
    for (i=0; i<num; ++i) {
        order[i] = pcbdata[i].time_start;
        ready[i] = i;
    }
    for (i=0; i<num; ++i) {
        for (j=i+1; j<num; ++j){
            if (order[i] > order[j]) {
                temp = order[i];
                order[i] = order[j];
                order[j] = temp;
                temp = ready[i];
                ready[i] = ready[j];
                ready[j] = temp;       
            }
        }
    }
    printf("FCFS: \n");
    used_time = pcbdata[ready[0]].time_start;
    for (i=0; i<num; i++) {
        printf("Process#%d: %s\n", i+1, pcbdata[ready[i]].name);
        printf("Averal Time -- %d, serve time: %d\n", pcbdata[ready[i]].time_start, pcbdata[ready[i]].time_need);
        printf("Process is running. \n");
        _sleep(1);
        printf("%s Finished!\n", pcbdata[ready[i]].name);
        used_time += pcbdata[ready[i]].time_need;
        j = used_time - pcbdata[ready[i]].time_start;
        k = (float)j / pcbdata[ready[i]].time_need;
        printf("Finished time: -- %d, running time: %d, running time with weight: %.1f\n", used_time, j, k);
    }
    printf("All finished.\n");
}

void SJF() {
    int processNum = 4;
    int i, j, used_time;
    double k;
    int nextP = -1, minStart = 9999;
    int finishedFlag[processNum + 1];
    memset(finishedFlag, 1, sizeof(int) * (processNum + 1));
    finishedFlag[processNum] = processNum;
    for (i=0;i<processNum;++i) {
        if (minStart > pcbdata_1[i].time_start) {
            nextP = i;
            minStart = pcbdata_1[i].time_start;
        }else if(minStart == pcbdata_1[i].time_start){
            if (pcbdata_1[nextP].time_need > pcbdata_1[i].time_need){
                nextP = i;
                minStart = pcbdata_1[i].time_start;
            }
        }
    }
    printf("SJF: \n");
    used_time = pcbdata_1[nextP].time_start;
    while(finishedFlag[processNum] > 0) {
        finishedFlag[nextP] = 0;
        printf("Process#%d: %s\n", processNum-finishedFlag[processNum], pcbdata_1[nextP].name);
        printf("Averal Time -- %d, serve time: %d\n", pcbdata_1[nextP].time_start, pcbdata_1[nextP].time_need);
        printf("Process is running. \n");
        _sleep(1);
        printf("%s Finished!\n", pcbdata_1[nextP].name);
        used_time += pcbdata_1[nextP].time_need;
        j = used_time - pcbdata_1[nextP].time_start;
        k = (float)j / pcbdata_1[nextP].time_need;
        printf("Finished time: -- %d, running time: %d, running time with weight: %.1f\n", used_time, j, k);
        finishedFlag[processNum]--;

        minStart = 9999;
        for (i=0;i<processNum;++i) {
            if (finishedFlag[i] && used_time > pcbdata_1[i].time_start && minStart > pcbdata_1[i].time_need) {
                nextP = i;
                minStart = pcbdata_1[i].time_need;
            }
        }
    }
}

void HRF() {
    int processNum = 4;
    int i, j, used_time;
    double k;
    int nextP = -1, minStart = 9999;
    int finishedFlag[processNum + 1];
    double priority, max;
    memset(finishedFlag, 1, sizeof(int) * (processNum + 1));
    finishedFlag[processNum] = processNum;
    for (i=0;i<processNum;++i) {
        if (minStart > pcbdata_2[i].time_start) {
            nextP = i;
            minStart = pcbdata_2[i].time_start;
        }
    }
    printf("HRF: \n");
    used_time = pcbdata_2[nextP].time_start;
    while(finishedFlag[processNum] > 0) {
        finishedFlag[nextP] = 0;
        printf("Process#%d: %s\n", nextP+1, pcbdata_2[nextP].name);
        printf("Averal Time -- %d, serve time: %d\n", pcbdata_2[nextP].time_start, pcbdata_2[nextP].time_need);
        printf("Process is running. \n");
        _sleep(1);
        printf("%s Finished!\n", pcbdata_2[nextP].name);
        used_time += pcbdata_2[nextP].time_need;
        j = used_time - pcbdata_2[nextP].time_start;
        k = (float)j / pcbdata_2[nextP].time_need;
        printf("Finished time: -- %d, running time: %d, running time with weight: %.1f\n", used_time, j, k);
        finishedFlag[processNum]--;

        max = -1;
        for (i=0;i<processNum;++i) {
            if (finishedFlag[i]){
                priority = (used_time - pcbdata_2[i].time_start + pcbdata_2[i].time_need) / pcbdata_2[i].time_need;
                if (max < priority) {
                    nextP = i;
                    max = priority;
                }
            }
        }
    }
}

void time_slice() {
    int i, j, temp, used_time, running;
    double running_weight;
    int finished[num+1];
    for (i=0; i<num; ++i) {
        order[i] = pcbdata[i].time_start;
        ready[i] = i;
    }
    for (i=0; i<num; ++i) {
        for (j=i+1; j<num; ++j){
            if (order[i] > order[j]) {
                temp = order[i];
                order[i] = order[j];
                order[j] = temp;
                temp = ready[i];
                ready[i] = ready[j];
                ready[j] = temp;
            }
        }
    }
    memset(finished, 0, sizeof(int) * num);
    finished[num] = num;
    i = 0;
    used_time = pcbdata[ready[0]].time_start;
    while(finished[num] > 0) {
        if (!finished[ready[i]] && used_time >= pcbdata[ready[i]].time_start) {
            for (j=0;j<time_unit;++j) {
                if (pcbdata[ready[i]].time_left > 0){
                    process_each_slice(&pcbdata[ready[i]]);
                    used_time = used_time + 1;
                }
            }
            if (pcbdata[ready[i]].time_left <= 0){
                running = used_time - pcbdata[ready[i]].time_start;
                running_weight = (float)running / pcbdata[ready[i]].time_need;
                printf("Process %s finished. Finished time: %d, running time: %d, running time with weight: %.1f\n",
                       pcbdata[ready[i]].name, used_time, running, running_weight);
                finished[ready[i]] = 1;
                finished[num]--;
            }
        }
        i = i++ % num;
    }
}

void MRLA() {
    int i, j;
    int used_time, running;
    double running_weight;
    int processNum = 4;
    int p_sep[3] = {0, 2, 6};
    int unfinished = processNum;
    int minPrc, minPri;
    int minStart=9999, nextPrc=0;
    int pri[processNum];
    for (i=0; i<processNum; i++) {
        pri[i] = 9999;
        if (minStart > pcbdata_3[i].time_start){
            nextPrc = i;
            minStart = pcbdata_3[i].time_start;
        }
    }
    used_time = pcbdata_3[nextPrc].time_start;
    pri[nextPrc] = 0;
    while (unfinished > 0) {
        if (pcbdata_3[nextPrc].time_left > 0){
            process_each_slice(&pcbdata_3[nextPrc]);
            used_time = used_time + 1;
        }
        if (pcbdata_3[nextPrc].time_left <= 0) {
            unfinished--;
            running = used_time - pcbdata_3[nextPrc].time_start;
            running_weight = (float)running / pcbdata_3[nextPrc].time_need;
            printf("Process %s finished. Finished time: %d, running time: %d, running time with weight: %.1f\n",
                   pcbdata_3[nextPrc].name, used_time, running, running_weight);
        }
        for (i=0;i<processNum;i++) {
            if (pcbdata_3[i].time_start <= used_time && pcbdata_3[i].time_left > 0) {
                if (pcbdata_3[i].time_used == 0) {
                    pri[i] = 1;
                    continue;
                }
                for (j=0;j<3;j++) {
                    if(pcbdata_3[i].time_used < p_sep[j]) {
                        pri[i] = j;
                        break;
                    }
                    pri[i] = 3;
                }
            }
        }
        minPri = 9999;
        for (i=0;i<processNum;i++) {
            if (pcbdata_3[i].time_left > 0 && minPri > pri[i]) {
                nextPrc = i;
                minPri = pri[i];
            }
        }
    }
}


int main() {
    int i=0, sch=99;
    while (sch != 0){
        printf("Input the number of scheduiling algorithm: \n");
        printf("(1) FCFS\n");
        printf("(2) SJF\n");
        printf("(3) HRF\n");
        printf("(4) TimeSlice\n");
        printf("(5) MRLA\n");
        scanf("%d", &sch);
        switch (sch) {
            case 1: FCFS(); break;
            case 2: SJF(); break;
            case 3: HRF(); break;
            case 4: time_slice(); break;
            case 5: MRLA(); break;
        }
    }
    _keygo();

    return 0;
}

void dis_pcb(PCB *pr) {
    printf("PCB of %d\n", pr->name);
    printf("Symbol -- %d, state -- %c, averal time -- %d\n",
           pr->id, pr->state, pr->time_start);
    printf("Server time -- %d, left time -- %d, used time -- %d\n",
           pr->time_need, pr->time_left, pr->time_used);
    printf("---------------------------\n");
}

void dis_pcb_all(){
    int i;
    printf("***States of all process****\n");
    for (i=0; i<num; ++i) {
        dis_pcb(&pcbdata[i]);
    }
}

void dis_ready() {
    int i;
    printf("Ready queue: \n");
    for (i=0; i<num-1; ++i) {
        printf("%s--", pcbdata[order[i]].name);
    }
    printf("%s\n", pcbdata[order[i]].name);
}