CPU调度算法（操作系统实验）

#include <stdio.h> struct Process { int id; //进程号 int arrive_time; //进程的到达时间 int runtime; //进程的运行时间 int priority; //进程的优先级 bool attend_compelete; //该进程是否参与竞争 Process *next; }; struct Grant { int start; //该区间的起始时间 int end; //该区间的结束时间 int procID; //在该区间运行的进程 Grant *next; }; struct Performance { int procID; //进程号 int turnaround; //周转时间 int response; //响应时间 Performance *next; }; //存盘 bool save(Process *head, char *path = "job.dat") { FILE *fout = fopen(path, "wb"); if (fout == NULL) { printf("Error when save file!"); return false; } //头节点为空，中只是为了统一算法 head = head->next; while (head != NULL) { int a = fwrite(head, sizeof(Process), 1, fout); head = head->next; } fclose(fout); return true; } //装载 bool load(Process *head, char *path = "job.dat") { FILE *fin = fopen(path, "rb"); if (fin == NULL) { printf("Error when load file!"); return false; } Process *p, *q; q = head; /* int length = fseek(fin, 0, SEEK_END); int n = length/sizeof(Process); for (int i=0; i<n; i++) { p = new Process(); fread(p, sizeof(Process), 1, fin); q->next = p; q = p; } */ p = new Process(); while (1 == fread(p, sizeof(Process), 1, fin)) { p->attend_compelete = false; q->next = p; q = p; p = new Process(); } q->next = NULL; delete p; fclose(fin); return true; } //////////////////////////////////////////////// //释放空间 void free(Process *head) { Process *p = head->next; while (p != NULL) { head->next = p->next; delete p; p = head->next; } } void free(Performance *head) { Performance *p = head->next; while (p != NULL) { head->next = p->next; delete p; p = head->next; } } void free(Grant *head) { Grant *p = head->next; while (p != NULL) { head->next = p->next; delete p; p = head->next; } } ///////////////////////////////////////////////////////// //显示 void display(Process *head) { head = head->next; printf("\n进程名称\t到达时间\t运行时间\t优先级\n"); while (head != NULL) { printf("P%d\t\t%d\t\t%d\t\t%d\n", head->id, head->arrive_time, head->runtime, head->priority); head = head->next; } } void display(Performance *phead) { phead = phead->next; printf("\n进程名称 响应时间 周转时间\n"); while (phead != NULL) { printf("P%d\t%d\t%d\n", phead->procID, phead->response, phead->turnaround); phead = phead->next; } } void display(Grant *ghead) { //ghead = ghead->next; //while (ghead != NULL) //{ // printf("%d_%d_%d\n", ghead->start, ghead->procID, ghead->end); // ghead = ghead->next; //} printf("\n甘特图:\n"); if (ghead == NULL) return; Grant *p = ghead->next; if (p == NULL) return; Grant *q = p->next; while (q != NULL) { printf(" <%d> ", p->start); int n = p->end - p->start; for (int i=0; i<n; i++) printf("P%d", p->procID); if (q->start != p->end) { printf(" <%d> ", p->end); n = q->start - p->end; for (int i=0; i<n; i++) printf("空"); } p = q; q = q->next; } printf(" <%d> ", p->start); int n = p->end - p->start; for (int i=0; i<n; i++) printf("P%d", p->procID); printf(" <%d>\n", p->end); } //////////////////////////////////////////////////////////////// //按照arrive_time属性排序 Process *sort(Process *head) { if (head == NULL) return NULL; Process *q = head->next; if (q == NULL) return NULL; Process *p = q->next; Process *s, *t; //插入排序 while (p != NULL) { if (p->arrive_time >= q->arrive_time) { p = p->next; q = q->next; continue; } s = head; t = s->next; //找到要插入的位置 while (p->arrive_time >= t->arrive_time) { s = s->next; t = t->next; } //插入 q->next = p->next; p->next = s->next; s->next = p; //p的指针需要复原，它指到需插入的位置了 p = q->next; } return head; } //按照procID属性排序 Performance * sort(Performance *head) { if (head == NULL) return NULL; Performance *q = head->next; if (q == NULL) return NULL; Performance *p = q->next; Performance *s, *t; //插入排序 while (p != NULL) { if (p->procID >= q->procID) { p = p->next; q = q->next; continue; } s = head; t = s->next; //找到要插入的位置 while (p->procID >= t->procID) { s = s->next; t = t->next; } //插入 q->next = p->next; p->next = s->next; s->next = p; //p的指针需要复原，它指到需插入的位置了 p = q->next; } return head; } //////////////////////////////////////////////////////////////////////////////////////// //找出参与竞争的进程中的最小值，参数by表示根据何种属性选择（1表示runtime;2表示priority;） Process *min(Process *head, int by = 1) { Process *p = head->next; Process *min = NULL; while (p != NULL) { if (p->attend_compelete) { min = p; break; } p = p->next; } if (p == NULL) return NULL; p = p->next; while (p != NULL) { if (p->attend_compelete) { bool swap = false; switch (by) { case 1: swap = p->runtime < min->runtime; break; case 2: swap = p->priority < min->priority; break; } if (swap) { min = p; } } p = p->next; } return min; } //SJF或Priority算法画Grant图，which = 1时用SJF算法,which = 2时用SJF算法 Grant * SJF_Priority(Process *head, int which = 1) { if (head == NULL) return NULL; Grant *ghead = new Grant(); Grant *gtail = ghead; ghead->next = NULL; sort(head); //根据到达时间排序 Process *p = head->next; Process *q = p->next; p->attend_compelete = true; //同时到达 while (q != NULL && q->arrive_time == p->arrive_time) { q->attend_compelete = true; q = q->next; } Grant *node; Process *run = min(head, which); int t = run->arrive_time; //时间轴 int tn; //下一个取值时间 //所有进程都同时到达 if(q == NULL) { //tn = TimeNeeded(head); //tn的值取此组进程的运行时间之和 //Process * last = max(head, 3); //if (last->arrive_time + last->runtime > tn) // tn = last->arrive_time + last->runtime; //tn为所需时间的最大值 tn = run->runtime + t; } else { //tn取下一个进程到达时间和此进程运行时间的最小值 tn = (q->arrive_time < run->runtime) ? q->arrive_time : run->runtime; } while (t < tn) { run = min(head, which); if (run == NULL) break; node = new Grant(); gtail->next = node; gtail = node; node->next = NULL; node->start = t; node->procID = run->id; node->end = tn; run->runtime -= (node->end - node->start); if (run->runtime <= 0) run->attend_compelete = false; run = min(head, which); //在下一个到达时间之前没有时间多或者在下一个到达时间之前所有进程都运行结束，将产生一段时间(tn-t)的CPU空闲 t = tn; if (q == NULL) //所有进程都已经到达 { if (run == NULL) break; tn += run->runtime; } else { p = q; if (t < p->arrive_time) //时间还在下一个就绪进程到达之前 { if (run != NULL) //并且还有未完成的进程 { tn += run->runtime; continue; } else //所有进程都已完成 { t = p->arrive_time; tn = t; } } q = q->next; p->attend_compelete = true; //同时到达 while (q != NULL && q->arrive_time == p->arrive_time) { q->attend_compelete = true; q = q->next; } run = min(head, which); //此时tn的值为下一个要运行的进程运行结束的时间，但不一定是最终要取值的下一个时间 tn = run->runtime + tn; if (q != NULL) { //tn取下一个进程到达时间和此进程运行结束的时间的最小值 tn = (q->arrive_time < tn) ? q->arrive_time : tn; } } } return ghead; } //轮转法调度，参数slice为时间片的大小 Grant *RR(Process *head, int slice) { if (head == NULL