简单的进程优先级动态调度

cup运行： 每执行一次，优先级减一，运行时间减一。

就绪队列中的进程：每次按优先级降序排序（优先级越大越优先执行），若优先级相等再按时间升序排序（时间越小越优先执行）。

所用知识点：结构体数组、结构体排序。

1 /*******************************************  2 *  3 *  File    : pro.c  4 *  describe: 操作系统进程调度，动态优先级算法  5 *  Author  : 阿Q  6 *  Iime    : 2016.11.19  7 *  8 *******************************************/  9 #include
     
       10 #define P 5 11 #define PrintF(proprety) printf("%s\t",proprety) 12 struct pcb {         //定义进程结构 13     int pid;             //进程Id 14     struct pcb *next;  //指向下一个进程 15     int time;    //进程所需执行的时间 16     int priority;  //进程优先级 17     int state;  //进程执行的状态，只有0、1状态.0未执行，1已执行 18 }; 19 struct pcb pro[P]= {
   //初始化5个进程 20     {
   0,1,6,3,0}, 21     {
   1,2,4,4,0}, 22     {
   2,3,4,3,0}, 23     {
   3,4,4,2,0}, 24     {
   4,0,1,0,0}, 25 }; 26  27 /******************************************* 28 * 29 *  Function : 显示所有进程的状态 30 * 31 *******************************************/ 32 void display() { 33     int i=0,property=5; 34     PrintF("\npid"); 35     for(i=0; i
      
       time==0||aa->state==1)return 1; 68     else if(bb->time==0||bb->state==1)return -1; 69  70     if(bb->priority!=aa->priority) 71         return (bb->priority - aa->priority); 72     else 73         return (aa->time - bb->time); 74 } 75  76 /******************************************* 77 * 78 *  Function : 进程排序 需要子函数 cmp() 79 * 80 *******************************************/ 81 void reSort() { 82     qsort(pro,P,sizeof(pro[0]),cmp); 83 } 84  85 /******************************************* 86 * 87 *  Function : 检查是否存在未执行完的程序 88 * 89 *******************************************/ 90 int check() { 91     int i=0; 92     for(i=0; i
       
        0) {107             pro[i-1].next=0;108         }109         if(i<(P-1))110             pro[i].next=pro[i+1].pid;111     }112 }113 114 int main() {115     int f=0,i=1;116     printf("初始状态为：");117     display();118     while(check()) {
   //每执行完一次，测试是否还有进程未执行完119         printf("第%d次运行后:",i++);120         //pro[0]为第一个进程，这里当作是在CUP中执行的进程.每次执行执行时间减一，优先级减一。121         pro[0].time-=1;//执行一次进程执行时间减一122         pro[0].priority-=1;//动态优先级，每执行一次优先级减一123 124         if(pro[0].time==0)pro[0].state=1,pro[0].priority=-1,pro[0].next=0;//如果该进程执行完毕，及执行时间为0,则状态该为1，同时调整优先级，指针调制为0125         reSort();//重排进程126         rePoint();//重排指针127         display();//输出128     }129     printf("进程以全部运行完毕\n");130     return 0;131 }
       
      
     

 

具有就绪队列、阻塞队列的动态优先级调度。

1 /**********************************************************************************************************************  2 *  3 *  File      :  pro.cpp  4 *  Time      :  2016.12.04  5 *  Introduce :  CPU每执行一次,就绪队列中进程优先级+1，CPU执行中的进程优先级-3，阻塞中的优先级不增加，增加阻塞时间。  6 *  如果就绪队列中进程的优先级比CPU中的进程优先级高，则CPU中的进程进入阻塞队列，进程最长阻塞时间默认为3(每次+1，>=3,进入就绪队列）。  7 *  8 **********************************************************************************************************************/  9 #include
     
       10 #include
      
        11 #define N 6 12  13 // 待插入就绪队列的进程数据 14 int id[N]       = { 0,  1,  2,  3,  4,  5 }; 15 int priority[N] = { 14, 38, 27,  9,  7, 18 }; 16 int cpuTime[N]  = { 0,  0,  0,  0,  0,  0 }; 17 int allTime[N]  = { 5,  2,  3,  4,  2,  1 }; 18  19  20 /********************************* 21 * 22 *  模拟进程/PCB数据结构 23 * 24 *********************************/ 25  26 // 枚举进程的状态：就绪、执行、阻塞、完成 27 enum STATE { Ready, Run, Block, Finish }; 28  29  30 // 建立PCB结构体 31 struct PCB { 32     int id;                     // 标志数 33     int priority;               // 优先数 34     int cpuTime;                // 已占CPU时间 35     int allTime;                // 还需占CPU时间 36     int blockTime;              // 已被阻塞的时间 37     STATE state;                // 进程状态 38     PCB *pre;                   // PCB的前指针 39     PCB *nxt;                   // PCB的后指针 40 }; 41  42  43 /********************************* 44 * 45 *  模拟进程队列 46 * 47 *********************************/ 48  49 // 进程入列 50 void queQush(PCB *process, PCB *queHead) { 51     process->pre = NULL; 52     process->nxt = queHead->nxt; 53     if(queHead->nxt != NULL) { 54         // 非第一个入列 55         queHead->nxt->pre = process; 56     } 57     queHead->nxt = process; 58 } 59 // 进程出列 60 void quePop(PCB *process, PCB *queHead) { 61     if(process->pre != NULL) { 62         // 不是头节点 63         process->pre->nxt = process->nxt; 64     } else { 65         queHead->nxt = process->nxt; 66     } 67     if(process->nxt != NULL) { 68         // 不是尾节点 69         process->nxt->pre = process->pre; 70     } 71     // 清空进程指针 72     process->pre = process->nxt = NULL; 73 } 74 // 查看队列里进程的信息 75 void queWalk(PCB *queHead) { 76     PCB *pro = queHead->nxt; 77     if(pro == NULL) { 78         printf("(无进程)\n"); 79         return; 80     } 81     while(pro != NULL) { 82         printf("id:%d,  pri:%d,  alltime:%d\n", pro->id, 83                pro->priority, pro->allTime); 84         pro = pro->nxt; 85     } 86 } 87  88 /********************************* 89 * 90 *  模拟就绪队列 91 * 92 **********************************/ 93  94 int readyQueNum;                // 就绪队列的进程数量 95 PCB readyQueHead;               // 就绪队列的头部 96 PCB *readyMaxProcess;           // 就绪队列中优先级最高的进程 97  98  99 // 进程插入到就绪队列100 void readyQueQush(PCB *process) {101     readyQueNum ++;102     process->state = Ready;103     queQush(process, &readyQueHead);104 }105 // 优先级最高的进程出列106 PCB* readyQuePop() {107     readyQueNum --;108     quePop(readyMaxProcess, &readyQueHead);109     return readyMaxProcess;110 }111 //更新就绪队列112 void readyQueUpdate() {113     int maxPriority = -1;114     PCB *pro = readyQueHead.nxt;115     if(pro == NULL) {116         // 就绪队列没有进程117         readyMaxProcess = NULL;118         return;119     }120     while(pro != NULL) {121         pro->priority ++;122         if(pro->priority > maxPriority) {123             maxPriority = pro->priority;124             readyMaxProcess = pro;125         }126         pro = pro->nxt;127     }128 }129 // 返回就绪队列最高优先级的值130 int readyMaxPriority() {131     return readyMaxProcess->priority;132 }133 // 查看就绪队列里进程的信息134 void readyQueWalk() {135     printf("就绪队列里的进程信息为：\n");136     queWalk(&readyQueHead);137 }138 139 140 /*********************************141 *142 *  模拟阻塞队列143 *144 *********************************/145 146 #define EndBlockTime 3          // 进程最长被阻塞时间147 148 149 int blockQueNum;                // 阻塞队列的进程数量150 PCB blockQueHead;               // 阻塞队列的头部151 PCB *blockMaxProcess;           // 阻塞队列中优先级最高的进程152 153 154 // 进程插入到阻塞队列155 void blockQueQush(PCB *process) {156     blockQueNum ++;157     process->blockTime = 0;158     process->state = Block;159     queQush(process, &blockQueHead);160 }161 // 优先级最高的进程出列162 PCB* blockQuePop() {163     blockQueNum --;164     quePop(blockMaxProcess, &blockQueHead);165     return blockMaxProcess;166 }167 // 每个时间片，更新阻塞队列里进程的信息168 void blockQueUpdate() {169     int maxPriority = -1;170     PCB *pro = blockQueHead.nxt;171     while(pro != NULL) {172         pro->blockTime ++;173         if(pro->blockTime >= EndBlockTime) {174             PCB *process = pro;175             pro = pro->nxt;176             // 阻塞时间到，调入就绪队列177             blockQueNum --;178             quePop(process, &blockQueHead);179             readyQueQush(process);180         } else if(pro->priority > maxPriority) {181             // 更新阻塞队列里优先级最高的进程指针182             maxPriority = pro->priority;183             blockMaxProcess = pro;184             pro = pro->nxt;185         }186     }187 }188 // 查看阻塞队列里进程的信息189 void blockQueWalk() {190     printf("阻塞队列里的进程信息为：\n");191     queWalk(&blockQueHead);192 }193 194 195 /********************************196 *197 *  模拟动态优先权的进程调度198 *199 *********************************/200 201 // 初始化数据202 void initData() {203     // 初始化就绪队列和阻塞队列204     readyQueNum = blockQueNum = 0;205     readyMaxProcess = blockMaxProcess = NULL;206     readyQueHead.pre = readyQueHead.nxt = NULL;207     blockQueHead.pre = blockQueHead.nxt = NULL;208     // 初始化进程进入就绪队列209     int i, maxPriority = -1;210     for(i = 0; i < N; i ++) {211         // 分配一个PCB的内存空间212         PCB *pro = (PCB *)malloc(sizeof(PCB));213         // 给当前的PCB赋值214         pro->id        = id[i];215         pro->priority  = priority[i];216         pro->cpuTime   = cpuTime[i];217         pro->allTime   = allTime[i];218         pro->blockTime = 0;219         if(pro->allTime > 0) {220             // 插入到就绪队列中221             readyQueQush(pro);222             // 更新就绪队列优先级最高的进程指针223             if(pro->priority > maxPriority) {224                 maxPriority = pro->priority;225                 readyMaxProcess = pro;226             }227         }228     }229 }230 // 模拟cpu执行1个时间片的操作231 void cpuWord(PCB *cpuProcess) {232     cpuProcess->priority -= 3;//优先级-3233     if(cpuProcess->priority < 0) {234         cpuProcess->priority = 0;235     }236     cpuProcess->cpuTime ++;237     cpuProcess->allTime --;238     // 显示正执行进程的信息：239     printf("CPU正执行的进程信息为：\n");240     printf("id:%d,  pri:%d,  alltime:%d\n", cpuProcess->id,241            cpuProcess->priority, cpuProcess->allTime);242 }243 244 245 int main() {246     int timeSlice   = 0;         // 模拟时间片247     int cpuBusy     = 0;         // 模拟cpu状态248     PCB *cpuProcess = NULL;      // 当前在cpu执行的进程249 250     // 初始化数据251     initData();252     // 模拟进程调度253     while(1) {254         if(readyQueNum == 0 && blockQueNum == 0 && cpuBusy == 0) {255             // 就绪队列、阻塞队列和cpu无进程，退出256             break;257         }258         if(cpuBusy == 0) {259             // cpu空闲，选择一个进程进入cpu260             if(readyQueNum > 0) {261                 // 选择绪队列优先级最高的进程262                 cpuProcess = readyQuePop();263             } else {264                 // 就绪队列没有进程，改为选择阻塞队列优先级最高的进程265                 cpuProcess = blockQuePop();266             }267             cpuProcess->cpuTime = 0;268             cpuProcess->state = Run;269             cpuBusy = 1;270         }271         timeSlice ++;272         printf("\n第%d个时间片后：\n", timeSlice);273         // 模拟cpu执行1个时间片的操作274         cpuWord(cpuProcess);275         if(cpuProcess->allTime == 0) {276             cpuProcess->state = Finish;277             printf("\t--\t--\t--进程 %d 完成任务\n",cpuProcess->id);278             // 释放已完成进程的PCB279             free(cpuProcess);280             cpuBusy = 0;281         }282         // 更新就绪队列和阻塞队列里的进程信息283         blockQueUpdate();284         readyQueUpdate();285         // 查看就绪队列和阻塞队列的进程信息286         readyQueWalk();287         blockQueWalk();288         if(cpuBusy == 1 && readyQueNum >0 &&289                 cpuProcess->priority < readyMaxPriority()) {290             // 需抢占cpu，当前执行的进程调入阻塞队列291             blockQueQush(cpuProcess);292             cpuProcess = readyQuePop();293         }294     }295     printf("\n模拟进程调度算法结束\n");296     return 0;297 }