调度算法，在Linux环境下用C语言编写程序，模拟FCFS、RR、SJF等进程调度算法，以及利用信号量等方法解决哲学家就餐问题。
在主进程中，创建 20 个子线程，分别模拟进程调度算法FCFS、RR、SJF的实现，并分析子线程调度顺序是否正确。
#include
#include
#include
#include
#include
#include
#include
#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
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
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;
}
运行结果：
