进程调度模拟
浏览数：21 /
时间：2015年06月20日
操作系统实验作业。简单写一下，都写到一个文件去来。
1 /************************************************************************* 2 > File Name: LinkList.c 3 > Author: ICKelin 4 > Mail: [email protected] 5 > Created Time: 2014年12月12日 星期五 02时27分14秒 6 ************************************************************************/ 7 8 #include<stdio.h> 9 #include<string.h> 10 #include<errno.h> 11 #include<stdlib.h> 12 #include<unistd.h> 13 #include<sys/wait.h> 14 #include<limits.h> 15 16 #define WAIT 0x01 17 #define READY 0x02 18 #define RUNNING 0x03 19 #define FINISH 0x04 20 21 #define MAX_PROCESS 255 22 #define INFINITY 65535 23 #define MAX_PRORITY 4 24 25 #define O_FCFS 0x01 26 #define O_SJF 0X02 27 #define O_HRRF 0x03 28 #define O_DEF 0x04 29 30 #define IF_FCFS(a) (a == O_FCFS?1:0) 31 #define IF_SJF(a) (a == O_SJF?1:0) 32 #define IF_HRRF(a) (a == O_HRRF?1:0) 33 34 35 36 struct pcb 37 { 38 int pid; //进程id 39 char pname[256]; //进程名称 40 int priority; //优先级 41 double submit_time; //进程提交时间 42 double run_time; //进程需要运行时间 43 double start_time; //进程开始时间 44 double end_time; //进程结束时间 45 double wait_time; //进程等待时间 46 double response_time; //响应时间 结束时间-开始时间 47 double round_time; //平均带权时间 响应时间/运行时间 48 int status; //进程状态,WAIT,READY,RUNNING FINISH 49 }; 50 51 typedef struct pcb DataType; 52 53 typedef struct list 54 { 55 int size; 56 DataType infor; 57 struct list* next; 58 }*linklist, *pNode, Node; 59 60 int insert_node(linklist, pNode, int); 61 void show_linklist(linklist); 62 63 void error(char *msg) 64 { 65 fprintf(stderr,"msg error with: %s\n",msg, strerror(errno)); 66 exit(1); 67 } 68 69 linklist init_linklist() 70 { 71 linklist list = NULL; 72 list = malloc(sizeof( struct list) ); 73 if(list != NULL) 74 { 75 list->next = NULL; 76 list->size = 0; 77 } 78 79 return list; 80 } 81 //链表复制 82 linklist copy_linklist(linklist list) 83 { 84 linklist backup = init_linklist(); 85 if(backup == NULL) 86 error("init linklist"); 87 linklist head = list->next; 88 89 while(head != NULL) 90 { 91 pNode temp = malloc(sizeof(Node)); 92 temp->infor = head->infor; 93 temp->next = NULL; 94 95 insert_node(backup,temp,O_DEF); 96 head = head->next; 97 } 98 return backup; 99 } 100 //尾插法 101 int insert_node(linklist list, pNode node, int option) 102 { 103 int flag = 0; 104 105 linklist head = list; 106 if(head->next == NULL) 107 { 108 node->next = head->next; 109 head->next = node; 110 list->size++; 111 return list->size; 112 } 113 while( head->next !=NULL) 114 { 115 //对于FCFS，需要有序插入 116 if( IF_FCFS(option) && head->next->infor.submit_time> node->infor.submit_time) 117 { 118 node->next = head->next; 119 head->next = node; 120 flag = 1; 121 break; 122 } 123 head = head->next; 124 } 125 //对于SFJ或者FCFS的尾部，简单插入到尾部即可 126 if(!flag) 127 { 128 node->next = head->next; 129 head->next = node; 130 } 131 list->size++; 132 return list->size; 133 134 } 135 136 137 void show_linklist(linklist list) 138 { 139 linklist head = list->next; 140 printf("pid pname submit run start finish average round\n"); 141 while(head!=NULL) 142 { 143 printf("%d\t",head->infor.pid); 144 printf("%s\t",head->infor.pname); 145 printf("%6.2lf\t",head->infor.submit_time); 146 printf("%6.2lf\t",head->infor.run_time); 147 printf("%6.2lf\t",head->infor.start_time); 148 printf("%6.2lf\t",head->infor.end_time); 149 printf("%6.2lf\t",head->infor.wait_time); 150 printf("%6.2f\n",head->infor.round_time); 151 head = head->next; 152 } 153 } 154 155 /* 156 * FCFS原理： 157 * 队列按照提交时间排序，取队头 158 * fork一个子进程，运行 159 * 父进程等待子进程结束 160 * 填充数据结构 161 * 162 * */ 163 164 void FCFS(linklist list) 165 { 166 linklist finish_list = init_linklist(); 167 if(finish_list == NULL) 168 error("init finish linklist"); 169 linklist head = list->next; 170 double start = head->infor.submit_time; 171 int index = 0; 172 while(head!=NULL) 173 { 174 double run_time = head->infor.run_time; 175 head->infor.start_time = start; 176 int pid; 177 int status; 178 if( (pid = fork())<0 ) 179 error("fork"); 180 else if(pid == 0) //子进程 181 { 182 fprintf(stdout,"%s is running\n", head->infor.pname); 183 head->infor.status = RUNNING; 184 sleep(run_time/10); 185 exit(1); 186 } 187 else //父进程 188 { 189 head->infor.pid = pid; 190 waitpid(pid,&status,0); 191 fprintf(stdout,"%s is finished\n", head->infor.pname); 192 head->infor.end_time = start + run_time; 193 //从提交时间到结束时间 194 head->infor.wait_time = head->infor.end_time - head->infor.submit_time; 195 head->infor.round_time = head->infor.wait_time/ head->infor.run_time; 196 //head->infor.status = FINISH; 197 pNode temp = malloc(sizeof(Node)); 198 if(temp == NULL) 199 error("out of memory"); 200 temp = head; 201 start = head->infor.end_time; 202 203 head = head->next; 204 } 205 206 } 207 printf("FCFS Result:\n"); 208 show_linklist(list); 209 } 210 211 /* 212 * SJF原理: 213 * SJF相对与FCFS来说，多了个运行时间的判断 214 * 还是按照提交时间排序 215 * 选出提交时间<当前时间&&运行时间最小&&status == READY的节点 216 * fork子进程，运行 217 * 父亲进程等待子进程结束 218 * 填充数据结构 219 * 220 * */ 221 222 void SJF(linklist list) 223 { 224 //就绪 225 linklist head = list; //这样不用再找前驱。利用前驱的后继去对比。对上，得到前驱 226 //完成 227 linklist finish_list = init_linklist(); 228 229 if(finish_list == NULL) 230 error("init finish linklist"); 231 232 double start = head->next->infor.submit_time; 233 234 235 double min = INFINITY; 236 237 pNode node = malloc(sizeof( Node)); 238 while(list->next != NULL) 239 { 240 head = list; 241 min = INFINITY; 242 while(head->next!=NULL) 243 { 244 if(head->next->infor.status == WAIT && head->next->infor.submit_time <= start && min > head->next->infor.run_time) 245 { 246 min = head->next->infor.run_time; 247 node = head; 248 } 249 head = head->next; 250 } 251 252 253 //等待队列删除,删除需要前驱，node是要删除节点的前驱 254 255 pNode temp = malloc(sizeof(Node)); 256 257 temp = node->next; 258 temp->infor.status = RUNNING; 259 260 node->next = node->next->next; 261 262 //创建子进程 263 int pid ; 264 if((pid = fork())<0) 265 error("fork"); 266 else if(pid == 0) //子进程 267 { 268 printf("%s is running!\n", temp->infor.pname); 269 double run = temp->infor.run_time; 270 sleep(run/10); 271 exit(1); 272 } 273 274 else //父进程 275 { 276 int status; 277 waitpid(pid,&status,0); 278 printf("%s is finishd!\n", temp->infor.pname); 279 temp->infor.pid = pid; 280 temp->infor.start_time = start; 281 temp->infor.end_time = start + temp->infor.run_time; //结束时间 282 temp->infor.response_time = temp->infor.end_time - temp->infor.submit_time; 283 temp->infor.round_time = temp->infor.response_time/temp->infor.run_time; 284 temp->infor.wait_time = temp->infor.end_time - temp->infor.submit_time; 285 Node node = *temp; 286 insert_node(finish_list, temp,O_SJF); 287 start = start + temp->infor.run_time; 288 } 289 290 } 291 292 printf("SJF Result: \n"); 293 show_linklist(finish_list); 294 } 295 296 /* 297 * 优先权调度，非抢占式原理 298 * 跟SJF原理相似，二级排序根据优先级来排序 299 * 约定优先级为0-3 300 * 301 * */ 302 303 void priority_weak(linklist list) 304 { 305 //就绪 306 linklist head = list; //这样不用再找前驱。利用前驱的后继去对比。对上，得到前驱 307 //完成 308 linklist finish_list = init_linklist(); 309 310 if(finish_list == NULL) 311 error("init finish linklist"); 312 313 double start = head->next->infor.submit_time; 314 315 316 int min = 4; 317 318 pNode node = malloc(sizeof( Node)); 319 while(list->next != NULL) 320 { 321 head = list; 322 min = 4; 323 while(head->next!=NULL) 324 { 325 if(head->next->infor.status == WAIT && head->next->infor.submit_time <= start && min > head->next->infor.priority) 326 { 327 min = head->next->infor.priority; 328 node = head; 329 } 330 head = head->next; 331 } 332 333 334 //等待队列删除,删除需要前驱，node是要删除节点的前驱 335 336 pNode temp = malloc(sizeof(Node)); 337 338 temp = node->next; 339 temp->infor.status = RUNNING; 340 341 node->next = node->next->next; 342 343 //创建子进程 344 int pid ; 345 if((pid = fork())<0) 346 error("fork"); 347 else if(pid == 0) //子进程 348 { 349 printf("%s is running!\n", temp->infor.pname); 350 double run = temp->infor.run_time; 351 sleep(run/10); 352 exit(1); 353 } 354 355 else //父进程 356 { 357 int status; 358 waitpid(pid,&status,0); 359 printf("%s is finishd!\n", temp->infor.pname); 360 temp->infor.pid = pid; 361 temp->infor.start_time = start; 362 temp->infor.end_time = start + temp->infor.run_time; //结束时间 363 temp->infor.response_time = temp->infor.end_time - temp->infor.submit_time; 364 temp->infor.round_time = temp->infor.response_time/temp->infor.run_time; 365 temp->infor.wait_time = temp->infor.end_time - temp->infor.submit_time; 366 Node node = *temp; 367 insert_node(finish_list, temp,O_SJF); 368 start = start + temp->infor.run_time; 369 } 370 371 } 372 373 printf("priority_weak Result: \n"); 374 show_linklist(finish_list); 375 } 376 377 /* 378 * 优先权调度，抢占式原理 379 * 利用链表的方式 380 * 调度原则： 381 * 初始化情况下，就绪队列按照提交时间升序排序 382 * 选择当前队头，从就绪队列中删除，并且放入运行队列中，计算运行结束时间， 383 * 从链表中找出小于或等于计算出的运行结束时间，并且优先级最小的 384 * 记下提交时间，这个提交时间-运行队列队头的提交时间就是队头此次运行的时间。 385 * 迭代以上过程，直到就绪队列为空，运行队列为空。则调度完成。 386 * 387 * */ 388 void priority_strong(linklist ready_list) 389 { 390 391 linklist running_list = init_linklist(); 392 if(running_list == NULL) 393 error("init linklist"); 394 linklist finish_list = init_linklist(); 395 if(finish_list == NULL) 396 error("init linklist"); 397 398 while(ready_list->next!=NULL) //就绪队列不是空 399 { 400 linklist running_head = running_list->next; 401 double start = running_head->infor.submit_time; 402 double end = start + running_head->infor.run_time; 403 linklist ready_head = ready_list; //为了方便删除，用下一个节点去对比 404 int prority = MAX_PRORITY; 405 while(ready_head->next!=NULL&& ready_head->next->infor.submit_time<end) 406 { 407 pNode to_run; 408 if(ready_head->infor.priority<prority) 409 { 410 to_run = ready_head; 411 prority = ready_head->infor.priority; 412 } 413 ready_head = ready_head->next; 414 } 415 //找到优先级最高的。且在范围内的 416 } 417 418 419 printf("priority_strong Result:\n"); 420 show_linklist(ready_list); 421 } 422 423 424 int main(int argc,char *argv[]) 425 { 426 linklist list = init_linklist(); 427 if(list ==NULL) 428 error("init_linklist"); 429 printf("please input process infor(end with EOF):\n"); 430 printf("name start run priority\n"); 431 432 pNode node = malloc(sizeof(Node)); 433 if(node == NULL) 434 error("out of memory"); 435 436 //输入 437 while(~scanf("%s%lf%lf%d",node->infor.pname, &node->infor.submit_time, &node->infor.run_time, &node->infor.priority)) 438 { 439 node->infor.status = WAIT; 440 insert_node(list, node,O_FCFS); //构建就绪队列，省去后备队列 441 node = malloc(sizeof(Node)); 442 if(node == NULL) 443 error("out of memory"); 444 } 445 446 printf("\nReady! go..\n"); 447 show_linklist(list); 448 //FCFS 449 linklist backup = copy_linklist(list); 450 FCFS(backup); 451 //优先权调度，非抢占式子调度 452 backup = copy_linklist(list); 453 priority_weak(backup); 454 //SJF算法 455 //backup = copy_linklist(list); 456 //SJF(backup); 457 //优先权调度，抢占式调度 458 //backup = copy_linklist(list); 459 //priority_strong(list); 460 }
优先权调度，抢占式的代码有问题。
提供一个输入文件input，重定向标准输入即可。
job1 8 60 2 job2 8.5 50 0 job3 9 10 3 job4 9.5 20 1
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
