任务调度①问题描述多用户多任务操作系统中，多个任务同时共享计算机系统资源。

为了使多个任务均能够顺利执行，操作系统要按一定的原则对它们进行调度，使它们按一定的次序进行。

设只有一个CPU，现有多个任务，它们需要CPU服务的时间已知。

在下列假设下，按平均等待时间最短为原则，设计算法求出任务的执行顺序。

●忽略任务提交的时间差，即认为各任务同时提交。

●各任务不同时提交。

②基本要求●为任务列表设计数据结构和存储结构。

●任务输入，至少包括任务编号及所需CPU的服务时间，任务数不得少于5个。

●如果按提交顺序执行，求出每个任务的开始执行时间、终止时间、等待时间和所有任务的平均等待时间。

●按平均等待时间最短，设计任务调度算法，输出任务的执行序列；求出每个任务的开始执行时间、终止时间、等待时间和所有任务的平均等待时间；并把结果与上一时间对比。

③设计要点提示●为使各任务平均等待时间最短，如果忽略任务提交的时间差，调度时应该按短任务优先进行调度，即：按照各任务需要CPU服务时间的长短，确定执行顺序，短的在前，长的在后。

例：任务列表2如下，则执行序列如表3所示。

表3 任务执行序列行排序。

●如果考虑任务提交的时间差，应该按“最短剩余时间”优先进行调度。

调度发生在每次任务提交时，从未完成任务中选择需要CPU时间最短的任务。

例：任务提交情况如表4所示。

表4 任务列表1s时，P2提交，此时，P2需要CPU服务时间为4，P1还需7，则暂停P1，先运行P2。

2s时，P3提交，此时，P1、P2、P3各自需CPU服务时间为：7、3、12，所以继续运行P2。

依次类推，直至所有任务完成。

#include<stdio.h>#include<stdlib.h>#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->time<p->time){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->time>q->time){a=r->name;r->name=q->name;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 nif(head->next->next){t=p->gettime-n;n=p->gettime;while(t!=0){if(t>head->next->time){t=t-head->next->time;printf(" %d ",head->next->name);printf("\n");head->next=head->next->next;}else {if(t<head->next->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 np=p->next;}//end while pr=head->next;q=r->next;while(q){if(r->time>q->time){a=r->name;r->name=q->name;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);if(a==1){ p=first->next;printf("任务所需CPU时间(s)\n");while(p){printf(" %d ",p->name);printf(" %d",p->time);printf("\n");p=p->next;}}else waitlest(first);}else shijiancha(first);}。