1、链表操作：实现链表队列的初始化和输出。
//stu00.c 作业初始化及输出基本操作，程序模板，由学生完成缺失代码 #include#include #include #define TASK_COUNT 5 int iArrivePoint[TASK_COUNT] = { 0,1,2,3,4 }; int iTaskLen[TASK_COUNT] = { 4,3,5,2,4 }; char cPname[TASK_COUNT] = { 'A','B','C','D','E' }; //PCB节点链的定义 typedef struct _Pcb { int pid; //进程ID int arriveP; //到达时间点 int taskLen; //任务总时长 int beginP; //任务开始时间点 int finishP; //任务完成时间点 int remains; //未执行的时长 char cPname;//进程名称 int priority; //优先级 struct _Pcb * next; }PCB; //初始化PCB队列 PCB* InitPcbQue() { PCB* headOfPcb = NULL; PCB* curPcbNode; int i, indexP; / //在循环结构中创建节点并加入到链表中 //最终链表中进程顺序为A、B、C、D、E for (i = 0; i < TASK_COUNT; i++) { curPcbNode = (PCB*)malloc(sizeof(PCB)); indexP = TASK_COUNT - i - 1; curPcbNode->pid = indexP; curPcbNode->arriveP = iArrivePoint[indexP]; curPcbNode->taskLen = iTaskLen[indexP]; curPcbNode->remains = iTaskLen[indexP]; curPcbNode->cPname = cPname[indexP]; curPcbNode->finishP=0; curPcbNode->next = headOfPcb; headOfPcb = curPcbNode; } // return headOfPcb; } //输出链表信息 void PrintPcbQue(PCB* headPcb) { PCB* curPcb; curPcb = headPcb; //不能直接使用headPcb节点输出,会改变链表结构 //在循环结构中输出节点信息 //输出：A:4,B:3,C:5,D:2,E:4, while(curPcb!=NULL) { printf("%C:%d,", curPcb->cPname, curPcb->taskLen); curPcb = curPcb->next; } / return; } //清空队列 void ClearPcbQue(PCB* headPcb) { PCB* onePcb; / } int main() { PCB * pHead=NULL; pHead=InitPcbQue(); PrintPcbQue(pHead); ClearPcbQue(pHead); return 0; }
2、先来先服务：编写模拟进程调度的先来先服务程序
//stu01.c FCFS进程调度算法，程序模板，由学生完成缺失代码 #include#include #include #define TASK_COUNT 5 int iArrivePoint[TASK_COUNT] = { 0,1,2,3,4 }; int iTaskLen[TASK_COUNT] = { 4,3,5,2,4 }; char cPname[TASK_COUNT] = { 'A','B','C','D','E' }; //PCB节点链的定义 typedef struct _Pcb { int pid; //进程ID int arriveP; //到达时间点 int taskLen; //任务总时长 int beginP; //任务开始时间点 int finishP; //任务完成时间点 int remains; //未执行的时长 char cPname;//进程名称 int priority; //优先级 struct _Pcb * next; }PCB; //初始化PCB队列 PCB* InitPcbQue() { PCB* headOfPcb = NULL; PCB* curPcbNode; int i, indexP; for (i = 0; i < TASK_COUNT; i++) { curPcbNode = (PCB*)malloc(sizeof(PCB)); //注意链表操作时最先入链的会排在最后。 indexP = TASK_COUNT - i - 1; curPcbNode->pid = indexP; curPcbNode->arriveP = iArrivePoint[indexP]; curPcbNode->taskLen = iTaskLen[indexP]; curPcbNode->remains = iTaskLen[indexP]; curPcbNode->cPname = cPname[indexP]; curPcbNode->next = headOfPcb; headOfPcb = curPcbNode; } //printf("InitPcbQue finished.n"); return headOfPcb; } //输出链表信息 void PrintPcbQue(PCB* headPcb) { PCB* curPcb; curPcb = headPcb; //不能直接使用headPcb节点输出,会改变链表结构 while (curPcb != NULL) { printf("%C:%d,", curPcb->cPname, curPcb->finishP); curPcb = curPcb->next; }; return; } //清空队列 void ClearPcbQue(PCB* headPcb) { PCB* onePcb; while (headPcb != NULL) { onePcb = headPcb; headPcb = headPcb->next; free((void *)onePcb); } } PCB* headInitPcb; int FCFS() { //先来先服务 //请在begin end语句间补全程序语句实现短作业优行算法调度进程 / //对进程序列进行排序 int totalTaskLen = 0; headInitPcb = InitPcbQue(); PCB* itFCFSPcb = headInitPcb; / //在循环结构中输出进程执行序列和完成时间 while(itFCFSPcb!=NULL) { totalTaskLen=totalTaskLen+itFCFSPcb->taskLen; itFCFSPcb->finishP=totalTaskLen; printf("%C:%d,",itFCFSPcb->cPname,itFCFSPcb->finishP); itFCFSPcb=itFCFSPcb->next; } / //清空短作业排序的PCB链表 ClearPcbQue(headInitPcb); / //程序输出总周转时间(所有进程周转时间之和) return totalTaskLen; } int main() { FCFS(); return 0; }
3、时间片轮转进程调度
//as02.c RoundRobin进程调度算法，程序模板，由学生完成缺失代码 //输出：B:10,D:11,A:12,E:17,C:18, #include#include #include #define TASK_COUNT 5 int iArrivePoint[TASK_COUNT] = { 0,1,2,3,4 }; int iTaskLen[TASK_COUNT] = { 4,3,5,2,4 }; char cPname[TASK_COUNT] = { 'A','B','C','D','E' }; //PCB节点链的定义 typedef struct _Pcb { int pid; //进程ID int arriveP; //到达时间点 int taskLen; //任务总时长 int beginP; //任务开始时间点 int finishP; //任务完成时间点 int remains; //未执行的时长 char cPname;//进程名称 int priority; //优先级 struct _Pcb* next; }PCB; //初始化PCB队列 PCB* InitPcbQue() { PCB* headOfPcb = NULL; PCB* curPcbNode; int i, indexP; for (i = 0; i < TASK_COUNT; i++) { curPcbNode = (PCB*)malloc(sizeof(PCB)); //注意链表操作时最先入链的会排在最后。 indexP = TASK_COUNT - i - 1; curPcbNode->pid = indexP; curPcbNode->arriveP = iArrivePoint[indexP]; curPcbNode->taskLen = iTaskLen[indexP]; curPcbNode->remains = iTaskLen[indexP]; curPcbNode->cPname = cPname[indexP]; curPcbNode->next = headOfPcb; headOfPcb = curPcbNode; } //printf("InitPcbQue finished.n"); return headOfPcb; } //输出链表信息 void PrintPcbQue(PCB* headPcb) { PCB* curPcb; curPcb = headPcb; //不能直接使用headPcb节点输出,会改变链表结构 while (curPcb != NULL) { // printf("%C:%d,", curPcb->cPname, curPcb->finishP); printf("%C,", curPcb->cPname); curPcb = curPcb->next; } printf("n"); return; } //清空队列 void ClearPcbQue(PCB* headPcb) { PCB* onePcb; while (headPcb != NULL) { onePcb = headPcb; headPcb = headPcb->next; free((void*)onePcb); } } PCB* headInitPcb; PCB* RRHeadP = NULL;//就绪队列头指针 PCB* RRRearP = NULL;//就绪队列尾指针 PCB* finishHead = NULL;//完成的进程节点 PCB* finishRear = NULL;//完成的进程节点 //将新进程PCB节点移到队尾 void AddNewToRear(PCB* newNode) { RRRearP->next = newNode; RRRearP = newNode; } //将完成任务的节点加到完成进程队尾 void AddToFinishQ(PCB* newNode) { PCB* onePcb; if (finishHead == NULL) { finishHead = (PCB*)malloc(sizeof(PCB)); memcpy((void*)finishHead, (void*)newNode, sizeof(PCB)); finishHead->next = NULL; finishRear = finishHead; } else { onePcb = (PCB*)malloc(sizeof(PCB)); memcpy((void*)onePcb, (void*)newNode, sizeof(PCB)); onePcb->next = NULL; finishRear->next = onePcb; finishRear = onePcb; } } //执行一个时间片，从就绪队列首执行进程一个时间片， //该结点PCB剩余时长减一，然后后移到队尾 int TimeSliceGo(int iTimeNum) { int iRet = -1; PCB* oneNode; PCB* twoNode; //首个进程PCB递减一个数值 RRHeadP->remains--; if (RRHeadP->remains == 0) {//当前进程执行完毕 RRHeadP->finishP = iTimeNum; //进程执行完当前PCB进入完成队列 AddToFinishQ(RRHeadP); //1.执行完全部进程 if (RRHeadP == RRRearP) {//全部运行结束 iRet = 0; } else { //删除队首pcb twoNode = RRHeadP; oneNode = RRHeadP->next; RRHeadP = oneNode; free((void*)twoNode); } } else {//当前节点进入队列尾部 if (RRHeadP == RRRearP) {//只有一个节点啥也不做 } else { oneNode = RRHeadP->next; RRRearP->next = RRHeadP; RRRearP = RRRearP->next; RRRearP->next = NULL; RRHeadP = oneNode; } } return iRet; } //时间片轮转调度算法，实现方法1 int RoundRobin() { //时间片轮转法，在同一时刻，新建进程先入队列尾，刚结束的进程后入队尾 PCB* headPcb = NULL; PCB* oldNode = NULL;//指向旧节点队列 PCB* newNode = NULL;//指向新节点队列 PCB* oneNode = NULL; PCB* itOldPcb = NULL; //请在begin end语句间补全程序语句实现时间片轮转算法调度进程 //对进程序列进行排序 //得到原始的进程任务列表 headInitPcb = InitPcbQue(); itOldPcb = headInitPcb->next; //初始化就绪进程队列 RRHeadP = (PCB*)malloc(sizeof(PCB)); memcpy((void*)RRHeadP, (void*)headInitPcb, sizeof(PCB)); RRHeadP->next = NULL; RRRearP = RRHeadP; int iGoValue = 1, timeNum = 1; while (iGoValue != 0) { if (itOldPcb != NULL) { if (itOldPcb->arriveP == timeNum) { oneNode = (PCB*)malloc(sizeof(PCB)); memcpy((void*)oneNode, (void*)itOldPcb, sizeof(PCB)); oneNode->next = NULL; AddNewToRear(oneNode); itOldPcb = itOldPcb->next; } } //检查 //j是时间片编号 iGoValue = TimeSliceGo(timeNum); //printf("timeNum=%d,", timeNum); //PrintPcbQue(RRHeadP); timeNum++; } //计算每个进程的周转时间 int iTotal = 0; oneNode = finishHead; while (oneNode != NULL) { //周转时间=结束时间-到达时间 iTotal += oneNode->finishP - oneNode->arriveP; printf("%c:%d ", oneNode->cPname, oneNode->finishP - oneNode->arriveP); oneNode = oneNode->next; } //printf(" iTotal:%dn", iTotal); //程序输出总周转时间(所有进程周转时间之和) return 0; } int main() { RoundRobin(); return 0; } //到达进程队列 PCB* arrivePcbQue = NULL; //当前到达进程 PCB* curarrivePcb = NULL; //执行进程队列 PCB* exePcbQue = NULL; //执行进程队尾 PCB* exePcbQueTail = NULL; //当前执行时间 int curExeTime = 0; //时间片大小 int RRTimeSlice = 1; int RRTimeSliceRemains = 0; //调度执行进程exePcbQue一个时间片RRTimeSlice， //如果完毕释放，调度下一个。 //将当前调度的进程剩余的时间RRTimeSliceRemains传递给下一个调度的进程。 //如果没有执行完毕，则将该执行进程放到执行队列尾。 void exeRRPcb()//int &RRTimeSliceRemains) { PCB* exePcbHead = exePcbQue; int remainsTime = exePcbHead->remains - RRTimeSlice - RRTimeSliceRemains; if (exePcbHead->taskLen == exePcbHead->remains)//如果是第一次执行 exePcbHead->beginP = curExeTime; //如果执行完毕，则释放 if (remainsTime <= 0) { curExeTime += exePcbHead->remains; exePcbHead->finishP = curExeTime; printf("%C:%d,", exePcbHead->cPname, exePcbHead->finishP);// -exePcbHead->arriveP); RRTimeSliceRemains -= remainsTime; exePcbQue = exePcbQue->next; free((void*)exePcbHead); } //否则放到执行进程队列队尾 else { exePcbHead->remains -= RRTimeSlice; curExeTime += RRTimeSlice; exePcbQueTail->next = exePcbHead; exePcbQueTail = exePcbHead; exePcbQue = exePcbQue->next; exePcbQueTail->next = NULL; RRTimeSliceRemains = 0; } } //将从当前到达进程curarrivePcb开始， //到达时间<= curExeTime + RRTimeSlice的进程插入到执行进程尾。 void InsertRRexePcbQueTail() { while (curarrivePcb != NULL && curarrivePcb->arriveP <= (curExeTime + RRTimeSlice)) { exePcbQueTail->next = curarrivePcb; exePcbQueTail = curarrivePcb; curarrivePcb = curarrivePcb->next; exePcbQueTail->next = NULL; } } void InsertRRexePcbQueHead() { while (curarrivePcb != NULL && curarrivePcb->arriveP <= (curExeTime))// +RRTimeSlice)) { PCB* tempPcb = curarrivePcb; curarrivePcb = curarrivePcb->next; tempPcb->next = exePcbQue; exePcbQue = tempPcb; } } //时间片轮转调度算法，实现方法2 void RR() { while (exePcbQue != NULL) { InsertRRexePcbQueTail(); exeRRPcb(); // InsertRRexePcbQueHead(); // PrintPcbQue(exePcbQue); } }
4、短作业优先调度算法
//输出：A:4,D:6,B:9,E:13,C:18, #include#include #include #define TASK_COUNT 5 int iArrivePoint[TASK_COUNT] = { 0,1,2,3,4 }; int iTaskLen[TASK_COUNT] = { 4,3,5,2,4 }; char cPname[TASK_COUNT] = { 'A','B','C','D','E' }; //PCB节点链的定义 typedef struct _Pcb { int pid; //进程ID int arriveP; //到达时间点 int taskLen; //任务总时长 int beginP; //任务开始时间点 int finishP; //任务完成时间点 int remains; //未执行的时长 char cPname;//进程名称 int priority; //优先级 struct _Pcb * next; }PCB; //初始化PCB队列 PCB* InitPcbQue() { PCB* headOfPcb = NULL; PCB* curPcbNode; int i, indexP; for (i = 0; i < TASK_COUNT; i++) { curPcbNode = (PCB*)malloc(sizeof(PCB)); //注意链表操作时最先入链的会排在最后。 indexP = TASK_COUNT - i - 1; curPcbNode->pid = indexP; curPcbNode->arriveP = iArrivePoint[indexP]; curPcbNode->taskLen = iTaskLen[indexP]; curPcbNode->remains = iTaskLen[indexP]; curPcbNode->cPname = cPname[indexP]; curPcbNode->next = headOfPcb; headOfPcb = curPcbNode; } return headOfPcb; } //输出链表信息 void PrintPcbQue(PCB* headPcb) { PCB* curPcb; curPcb = headPcb; //不能直接使用headPcb节点输出,会改变链表结构 while (curPcb != NULL) { printf("%C:%d,", curPcb->cPname, curPcb->finishP); curPcb = curPcb->next; } printf("n"); return; } //清空队列 void ClearPcbQue(PCB* headPcb) { PCB* onePcb; while (headPcb != NULL) { onePcb = headPcb; headPcb = headPcb->next; free((void *)onePcb); } } //对旧链表进行排序，生成短作业在前的新PCB队列 PCB* BuildSortedPcbSF(PCB* theOldHead) { PCB * headPcb = NULL; PCB * oldNode = NULL;//指向旧节点队列 PCB * newNode = NULL;//指向新节点队列 PCB *oneNode = NULL; //复制头节点 headPcb = (PCB *)malloc(sizeof(PCB)); memcpy((void*)headPcb, (void*)theOldHead, sizeof(PCB)); headPcb->next = NULL; oldNode = theOldHead->next; newNode = headPcb; //生成短作业在前的新PCB队列 while (oldNode != NULL) { //当前节点任务时长比头节点小，则插入头节点前 if ((oldNode->taskLen) < (headPcb->taskLen)) { newNode = (PCB *)malloc(sizeof(PCB)); memcpy((void*)newNode, (void*)oldNode, sizeof(PCB)); newNode->next = headPcb; headPcb = newNode; oldNode = oldNode->next; continue; } //从新队列首进行查找合适的位置 newNode = headPcb; while (newNode->next != NULL) { if ((oldNode->taskLen) >= (newNode->next->taskLen)) { newNode = newNode->next; continue; } if ((oldNode->taskLen) < (newNode->next->taskLen)) { oneNode = (PCB *)malloc(sizeof(PCB)); memcpy((void*)oneNode, (void*)oldNode, sizeof(PCB)); oneNode->next = newNode->next; newNode->next = oneNode; //插入成功后，节点要后移。 oldNode = oldNode->next; break; } } if (newNode->next == NULL) { oneNode = (PCB *)malloc(sizeof(PCB)); memcpy((void*)oneNode, (void*)oldNode, sizeof(PCB)); oneNode->next = NULL; newNode->next = oneNode; oldNode = oldNode->next; continue; } } //清除旧pcb链表 ClearPcbQue(theOldHead); return headPcb; } PCB* headInitPcb; int SJF() { //短作业优先 PCB* headSFPcb; PCB* newNode; PCB* itComePcb = NULL;//任务到达的进程列表 PCB* itSFPcb = NULL; PCB* readyPcb = NULL;//当前就绪队列 //得到原始的进程任务列表 headInitPcb = InitPcbQue(); itComePcb = headInitPcb->next; //计算每个PCB的周转时长 int totalTaskLen = 0; int i = 0; int j = 0; //就绪队列开始只有一个就绪进程 readyPcb = (PCB *)malloc(sizeof(PCB)); memcpy((void*)readyPcb, (void*)headInitPcb, sizeof(PCB)); readyPcb->next = NULL; PCB* finishHead = NULL;//完成的进程节点 PCB* finishRear = NULL;//完成的进程节点 int iStartP = 0, iFinishedP = 0; //请在begin end语句间补全程序语句实现短作业优先算法调度进程 while (readyPcb != NULL) { //1.从ready队列将首个PCB移到完成队列中 if (finishHead == NULL) { finishHead = readyPcb; newNode = readyPcb->next; finishHead->next = NULL; finishRear = finishHead; readyPcb = newNode; } else { finishRear->next = readyPcb; newNode = readyPcb->next; //队尾指针后移一个 finishRear = finishRear->next; finishRear->next = NULL; readyPcb = newNode; } //计算当前进程结束时间点 iFinishedP = iFinishedP + finishRear->taskLen; finishRear->finishP = iFinishedP; //2.处理就绪队列 //查看原始队列是否为空 int iAddNewPcb = 0; while (itComePcb != NULL) { //从到达进程队列里查找所有早于刚完成的任务时间点，加入就绪队列中 if (itComePcb->arriveP <= iFinishedP) { //新节点暂时放队首没问题，后面会排序 newNode = (PCB *)malloc(sizeof(PCB)); memcpy((void*)newNode, (void*)itComePcb, sizeof(PCB)); newNode->next = readyPcb; readyPcb = newNode; //遍历原始进程队列 itComePcb = itComePcb->next; //就绪队列中添加了新进PCB iAddNewPcb = 1; } } if (iAddNewPcb) { //对当前就绪进程队列按任务时长进行排序，短任务在前 readyPcb = BuildSortedPcbSF(readyPcb); } } PrintPcbQue(finishHead); //清空短作业排序的PCB链表 ClearPcbQue(finishHead); return totalTaskLen; } //调度执行进程exePcb，完毕释放。 void exeSJPcb(PCB *exePcb) { exePcb->finishP = exePcb->beginP + exePcb->taskLen; printf("%C:%d,", exePcb->cPname, exePcb->finishP); free((void *)exePcb); } PCB *arrivePcbQue = NULL; //从到达进程队列arrivePcbQue中找到当前执行进程执行完之前exePcbfinishP //到达进程队列arrivePcbQue中任务时间最短的进程SJPcb返回并从到达进程队列中删除该结点。 PCB* FindSJPcb(int exePcbfinishP) { //假设就绪队列的第一个节点就是最短进程 PCB *SJPcb = arrivePcbQue; PCB *SJPrePcb = NULL; PCB *curPcb = arrivePcbQue; PCB *curPrePcb = NULL; while(curPcb != NULL && curPcb->arriveP <= exePcbfinishP) { if(curPcb->taskLen < SJPcb->taskLen) { SJPrePcb = curPrePcb; SJPcb = curPcb; } curPrePcb = curPcb; curPcb = curPcb->next; } if(SJPrePcb == NULL) { arrivePcbQue = SJPcb->next; } else { SJPrePcb->next = SJPcb->next; } return SJPcb; } //对到达的进程队列进行最短进程调度，算法2 void SJF1() { //总是执行到达队列的第一个进程 int exePcbfinishP = 0; while(arrivePcbQue != NULL) { PCB* SJPcb = FindSJPcb(exePcbfinishP); SJPcb->beginP = exePcbfinishP; exePcbfinishP = SJPcb->beginP + SJPcb->taskLen; exeSJPcb(SJPcb); } } int main() { arrivePcbQue = InitPcbQue(); SJF1(); return 0; }
