C语言实现任务调度.doc

任务调度问题描述多用户多任务操作系统中，多个任务同时共享计算机系统资源。为了使多个任务均能够顺利执行，操作系统要按一定的原则对它们进行调度，使它们按一定的次序进行。设只有一个CPU，现有多个任务，它们需要CPU服务的时间已知。在下列假设下，按平均等待时间最短为原则，设计算法求出任务的执行顺序。l 忽略任务提交的时间差，即认为各任务同时提交。l 各任务不同时提交。基本要求l 为任务列表设计数据结构和存储结构。l 任务输入，至少包括任务编号及所需CPU的服务时间，任务数不得少于5个。l 如果按提交顺序执行，求出每个任务的开始执行时间、终止时间、等待时间和所有任务的平均等待时间。l 按平均等待时间最短，设计任务调度算法，输出任务的执行序列；求出每个任务的开始执行时间、终止时间、等待时间和所有任务的平均等待时间；并把结果与上一时间对比。设计要点提示l 为使各任务平均等待时间最短，如果忽略任务提交的时间差，调度时应该按短任务优先进行调度，即：按照各任务需要CPU服务时间的长短，确定执行顺序，短的在前，长的在后。例：任务列表2如下，则执行序列如表3所示。表2 任务列表任务所需CPU时间(s)任务所需CPU时间(s)P18P59P24P620P312P715P45表3 任务执行序列任务所需CPU时间(s)等待时间结束时间开始时间P14040P25494P389179P49172617P512263826P615385338P720537353l 根据上一问题的分析，需要根据任务列表，按任务的CPU服务时间进行排序。l 如果考虑任务提交的时间差，应该按“最短剩余时间”优先进行调度。调度发生在每次任务提交时，从未完成任务中选择需要CPU时间最短的任务。例：任务提交情况如表4所示。表4 任务列表任务提交时刻所需CPU时间(s)任务提交时刻所需CPU时间(s)P108P549P214P6520P3212P7615P4350时刻，只有P1，所以运行P1。1s时，P2提交，此时，P2需要CPU服务时间为4，P1还需7，则暂停P1，先运行P2。2s时，P3提交，此时，P1、P2、P3各自需CPU服务时间为：7、3、12，所以继续运行P2。依次类推，直至所有任务完成。#include #include#define MAXNUM 100typedef struct Node1 int name; int time; int gettime; struct Node1 *next;Lnode1; void waitlest(Lnode1 *p)Lnode1 *q,*head; int a,wt,st,ft; wt=0;st=0;ft=0; printf(任务 所需CPU时间(s) 等待时间 结束时间 开始时间n); head=p; while(head-next) q=head; p=q-next; while(p-next) q=q-next; p=p-next; if(q-timetime) a=q-name; q-name=p-name; p-name=a; a=q-time; q-time=p-time; p-time=a; printf( %d ,p-name); printf(%10d,p-time); wt=ft; st=wt; ft=ft+p-time; printf(%10d,wt); printf(%10d,ft); printf(%10d,st); printf(n); q-next=NULL; free(p); void shijiancha(Lnode1 *p)Lnode1 *first,*head,*q,*r; int a,n,t;printf(任务 n); first=p; p=first-next; n=p-gettime; q=(Lnode1*)malloc(sizeof(struct Node1); head=q; while(p) r=(Lnode1*)malloc(sizeof(struct Node1); q-next=r; q=q-next; q-next=NULL; q-name=p-name; q-time=p-time; q-gettime=p-gettime; r=head-next; if(r-next) if(r-next-next) q=r-next; while(q-next) if(r-timeq-time) a=r-name; r-name=q-name; q-name=a; a=r-time; r-time=q-time; q-time=a; q=q-next; r=r-next; /end while q n /end if r n n /end if r n if(head-next-next) t=p-gettime-n; n=p-gettime; while(t!=0) if(thead-next-time) t=t-head-next-time; printf( %d ,head-next-name); printf(n); head-next=head-next-next; else if(tnext-time) head-next-time=head-next-time-t; t=0; else t=0; printf( %d ,head-next-name); printf(n); head-next=head-next-next; /end while t /end if h n n p=p-next; /end while p r=head-next; q=r-next; while(q) if(r-timeq-time) a=r-name; r-name=q-name; q-name=a; a=r-time; r-time=q-time; q-time=a; q=q-next; r=r-next; r=head-next; while(r) printf( %d ,r-name); printf(n); r=r-next; /end shijianchavoid main()int t,a,b,n; Lnode1 *p,*q,*first; p=(Lnode1*)malloc(sizeof(struct Node1); first=p; a=0; printf(输入1，选择忽略提交任务的时间差；输入2，选择考虑提交任务的时间差:); scanf(%d,&b); do q=(Lnode1*)malloc(sizeof(struct Node1); p-next=q; p=p-next; printf(请输入任务名:); scanf(%d,&n); p-name=n; if(b=2) printf(请输入任务提交时刻:); scanf(%d,&t); p-gettime=t; else p-gettime=0; printf(请输入任务所需时间(s):); scanf(%d,&t); p-time=t; printf(是否继续添加任务？输入1继续提交，输入0结束提交 ); scanf(%d,&a); while(a!=0); p-next=NULL; if(b=1) printf(输入1：按提交顺序执行；输入2：按平均等待时间最短); scanf(%d,&a); i