计算机进程调度算法FCFS、RR、SJF的实现

调度算法，在Linux环境下用C语言编写程序，模拟FCFS、RR、SJF等进程调度算法，以及利用信号量等方法解决哲学家就餐问题。

在主进程中，创建 20 个子线程，分别模拟进程调度算法FCFS、RR、SJF的实现，并分析子线程调度顺序是否正确。

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <string.h>
#include <unistd.h>
#include <time.h>
#include <sys/wait.h>

#define THREADNUM 20        //子线程数量

pthread_mutex_t DeviceMutex ;

struct VirtualPCB {
    int tid;            //线程id
    int priority;        //优先级
    int arriveTime;        //到达时间
    int waitTime;        //等待时间
    int startTime;        //开始时间
    int runTime;        //运行时间
    int endTime;        //完成时间
    int aroundTime;        //周转时间
    int tempRunTime;    //临时运行时间，用于记时RR
    int isFinish;        //是否结束 0/1
}PCBs[THREADNUM];


// 初始化PCB
void initPCB(){
    int i;
    srand(time(NULL));
    for(i = 0; i < THREADNUM; i++){
        PCBs[i].tid = i + 1;
        PCBs[i].priority =    rand()%19 + 1;        //权重为0~19范围内
        PCBs[i].tempRunTime = PCBs[i].runTime = rand()%19 + 1;        //运行的时间0~19范围内
        PCBs[i].arriveTime = 0;        //同时到达
        PCBs[i].waitTime = 0;
        PCBs[i].isFinish = 0;
    }
}

// 子线程功能实现
void* childFunc(void *arg){
    int n = *(int *)arg;
    while(1){
        pthread_mutex_lock(&DeviceMutex);    //锁
        printf("线程%-2d:  TID:%-2d 权重:%-2d 到达时间：%-2d 运行时间:%-2d \n",n,PCBs[n-1].tid,PCBs[n-1].priority,PCBs[n-1].arriveTime,PCBs[n-1].runTime);
        pthread_mutex_unlock(&DeviceMutex);        //解锁
        sleep(5);    //延时5s
        break;
    }
    pthread_exit(0);
}

//子线程：创建20个
void* childThread(void* vargp) {
    int ret[THREADNUM];
    initPCB();        //初始化
    pthread_t tid[THREADNUM];
    pthread_mutex_init(&DeviceMutex,NULL);
    int i,j;

    printf("20个子线程的情况如下：\n");
    for(i=0; i<THREADNUM; i++) {
        int k =i+1; 
        ret[i] = pthread_create(&tid[i],NULL,&childFunc, &k);
        if(ret[i] == 0) { sleep(1); }
        else{ printf("线程%2d failed!\n",i+1); } 
    }
    for(j=0; j<THREADNUM; j++)
    pthread_join (tid[i], NULL);
    pthread_mutex_destroy(&DeviceMutex);
    pthread_exit(0);
}

//FCFS 先到先服务
void handleFCFS(){
    printf("\n\n################# FCFS (单位：s)#################\n");

    int j;
    int start = 0;        //开始时间
    float waitTime = 0.0;
    for( j = 0; j < THREADNUM; j++){
        //默认为0同时到达，且程序还未finish
        if(PCBs[j].isFinish == 0){
            printf("线程: %2d  开始运行时刻: %3d  运行时间: %2d\n",PCBs[j].tid,start,PCBs[j].runTime);
            waitTime += (float)start;        //计算等待时间
            start += PCBs[j].runTime;        //计算运行时间
            PCBs[j].isFinish=1;
        }
    }
    printf("\n总共等待时间：%f",waitTime);
}    

// SJF  短作业优先
void handleSJF() {
    printf("\n\n################# SJF (单位：s)#################\n");
    //重新初始化
    int k;
    for(k = 0 ;k < THREADNUM; k++) { PCBs[k].isFinish = 0; }

    int i,j;
    int start = 0;        //开始时间
    float waitTime = 0.0;

    for(i = 1; i < THREADNUM; i++) {    //运行时间范围1~19s
        for(j = 0; j < THREADNUM; j++){
            // 因为是按照最短作业优先，则当运行时间等于i时且未finish执行
            if((PCBs[j].runTime == i) && (PCBs[j].isFinish == 0)){
                printf("线程: %2d  开始运行时刻: %3d 运行时间: %2d\n",PCBs[j].tid,start,PCBs[j].runTime);
                waitTime += (float)start;
                start += PCBs[j].runTime;
                PCBs[j].isFinish = 1;        //标记为结束
            }
        }
    }
    printf("\n总共等待时间：%f", waitTime);
}

//优先级优先
void handlePriority(){
    printf("\n\n################# Priority (单位：s)#################\n");
    //重新初始化
    int k;
    for(k = 0 ;k < THREADNUM; k++) { PCBs[k].isFinish = 0; }

    int i,j;
    int start = 0;        //开始时间
    float waitTime = 0.0;

    for(i = 1; i < THREADNUM; i++) {    //权重
        for(j = 0; j < THREADNUM; j++){
            // 因为是按照权重值越小优先，则当权重值等于i时且未finish执行
            if((PCBs[j].priority == i) && (PCBs[j].isFinish == 0)){
                printf("线程: %2d  开始运行时刻: %3d 运行时间: %2d\n",PCBs[j].tid,start,PCBs[j].runTime);
                waitTime += (float)start;
                start += PCBs[j].runTime;
                PCBs[j].isFinish = 1;        //标记为结束
            }
        }
    }
    printf("\n总共等待时间：%f", waitTime);
}

//RR：轮转法
void handleRR(int eachTime){
    printf("\n\n################# RR (单位：s,时间片：%d)#################\n",eachTime);
    //重新初始化
    int n,totaltime;
    for(n = 0 ; n < THREADNUM; n++) { PCBs[n].isFinish = 0; }

    int i,j,k,m;
    int start = 0;        //开始时间
    float waitTime = 0;
    int tempTime = 0;    //统计运行时间累加

    for(j = 0; j < 20*THREADNUM; j = j + eachTime) {    //每次循环加一个时间片，执行一个时间片长度程序
        k = (j % (20*eachTime)) / eachTime;        // 记录当前执行程序下标
        if(PCBs[k].tempRunTime > 0){    //运行时间大于0
            tempTime = eachTime;
            if(PCBs[k].tempRunTime - eachTime <= 0){    //程序运行结束
                tempTime = PCBs[k].tempRunTime;        //运行时间记录
                PCBs[k].waitTime = start + tempTime - PCBs[k].runTime;    //等待时间
            }
            //否则继续保留
            printf("线程: %2d 开始运行时刻: %3d 运行时间:%2d \n",PCBs[k].tid, start,tempTime);
            start += tempTime;
            PCBs[k].tempRunTime -= eachTime;
        }
    }

    for(m = 0; m < THREADNUM; m++) {
        waitTime += PCBs[m].waitTime;
    }
    printf("\n总共等待时间：%f\n", waitTime);
}


int main(){

    int ret1;
    //创建主线程
    pthread_t tid1;
    ret1 = pthread_create(&tid1,NULL,&childThread,NULL);
    if(ret1 == 0) { printf("creating child threads...\n...\n"); sleep(20); }
    else{ printf("Create Main Thread failed!\n"); }

    //handleFCFS();    // FCFS 先到先处理
    //handleSJF();    // 短作业优先
    //handlePriority();        //优先级
    handleRR(10);        //时间分段为10s

    return 0;
}

运行结果：