调度算法,在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; }
运行结果:
上一篇
Django踩坑笔记
Django踩坑笔记
下一篇
计算机网络-概述
计算机网络-概述
版权声明:《 计算机进程调度算法FCFS、RR、SJF的实现 》为DYBOY原创文章,转载请注明出处!
最后编辑:2018-10-24 00:10:53