1 /*************************************************************************  2     > File Name: LinkList.c  3     > Author: ICKelin  4     > Mail: 18277973721@sina.cn   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-3300  *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     //FCFS449     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 }

job1    8    60    2job2    8.5    50    0job3    9    10    3job4    9.5    20    1