模拟thread.doc

操作系统设计报告一 需求分析在多道处理程序运行环境下，进程数目一般多于处理机数目，使得进程要通过竞争来使用处理机。这就要求系统能按照某种算法，动态地把处理机分配给就绪队列中的一个进程，使之运行，分配处理机的任务是由进程调度程序完成的。一个进程被创建后，系统为了便于对进程进行管理，将系统中的所有进程按照其状态，将其组成不同的进程队列。于是系统中有运行进程队列、就绪队列和各种事件的进程等待队列。进程调度的功能就是从就绪队列中挑选一个进程到处理机上运行。进程调度的算法有多种，常用的有优先级调度算法、先来先服务算法、时间片轮转算法。二 概要设计最高优先级优先调度算法动态优先数是指在进程创建时先确定一个初始优先数， 以后在进程运行中随着进程特性的改变不断修改优先数，这样，由于开始优先数很低而得不到CPU的进程，就能因为等待时间的增长而优先数变为最高而得到CPU运行。例如：在进程获得一次CPU后就将其优先数减少3。或者，进程等待的时间超过某一时限时增加其优先数的值，等等。简单轮转法调度算法 所有就绪进程按 FCFS排成一个队列，总是把处理机分配给队首的进程，各进程占用CPU的时间片相同。即将CPU的处理时间划分成一个个相同的时间片，就绪队列的诸进程轮流运行一个时间片。当一个时间片结束时，如果运行进程用完它的时间片后还未完成，就强迫运行机制进程让出CPU，就把它送回到就绪队列的末尾，等待下一次调度。同时，进程调度又去选择就绪队列中的队首进程，分配给它一时间片，以投入运行。直至所有的进程运行完毕。短作业优先调度算法 所有就绪进程按所需时间由少到多排成一个队列，依次运行队列中的进程，并列表显示出来，每个进程的开始运行时间减去进入内存时间就是该进程的等待时间，每个进程的结束运行时间减去进入内存时间就是该进程的周转时间，每个进程的周转时间除于服务时间就是带权周转时间。三 详细设计一优先权调度算法：1、用户可以自行输入进程的数量，每一个进程由进程控制块（ PCB）表示，各种队列均采用链表数据结构。2、 进程控制块包含如下信息：进程号、cpu时间、所需要时间、优先数、状态 等等。3、 在每次运行程序时都要输入“进程数量”、“进程名称及占用时间”。4、 按照优先数的高低进行排列5、 处理机调度队首元素运行。采用动态优先数办法，进程每运行一次优先数减“3”，同时将已运行时间加“1”。6、 进程运行一次后，若要求运行时间不等于已运行时间，则再将它加入就绪队列；否则将其状态置为“F”,且退出就绪队列。7、 “R”状态的进程队列不为空，则重复上面步骤，直到所有进程都成为“F”状态。流程图: 开始初始化PCB，输入各进程信息按优先级加入就绪队列就绪队列空结束就绪队列中首进程运行标为Cpu时间+1，进入下一个进程进程运行时间满足所需时间进程运行完成。进程优先数减3，插入就绪队列中。NYN 图.最高优先级优先调度算法流程图主要代码：void priority(char algo)PCB q;prt1(algo);for(int i = 0; i0)q.needtime-;if(q.needtime = 0)q.state = 3;if(q.state!=3)q.prio-=3;pp.push(q);while(!pq.empty()q = pq.top();pq.pop(); if(q.needtime = 0)q.state = 3;prt2(algo , q);prt1(algo);pp.push(q);pq = pp;pp = pqempty; printf(*n); printf( 输出结束n);getchar();二时间片轮转算法：1、 用户可以自行输入进程的数量，每一个进程由进程控制块（ PCB）表示，各种队列均采用链表数据结构。2、 按照进程输入的先后顺序排成一个队列。再设一个队首指针指向第一个到达进程的首址。3、 执行处理机调度时，开始选择队首的第一个进程运行。另外，再设一个当前运行进程的指针，指向当前正在运行的进程。4、 考虑到代码的可重用性, 轮转法调度程序和最高优先级优先调度是调用同一个模快进行输出5、 在规定的时间片内进程是根据先来先服务的方式配列的，每个进程只运行时间片大小的时间然后转到下一个进程运行。直到所有进程运行完为止。流程图初始化PCB、输入进程信息和时间片大小开始进程按输入顺序插入到队列中就绪队列空结束就绪队列首进程运行运行进程占用cup时间到达 所需时间进程完成把运行进程插入到队尾NYN图. 简单轮转法调度算法流程图主要代码：void Roundrun(int timeSlice)while(run != NULL)run-cputime = run-cputime + timeSlice;run-needtime = run-needtime - timeSlice;run-round+=timeSlice;run-count+;if(run-needtime needtime = 0;run-next = finish;finish = run;if(run != tail)tail-next = ready;elseready = NULL;run-state = F;run = NULL;if(ready != NULL)firstin();elseif(ready != NULL)run-state = W;tail = run;run = ready; /就绪队列的头指针赋值给运行run - state = R; /进程状态变为等待状态ready = ready - next; /就绪队列头指针移到下一个进程prt(r);三短作业优先调度算法1,用户可以自行输入进程的数量，每一个进程由进程控制块（ PCB）表示，各种队列均采用链表数据结构。2，按照进程服务时间由少到多顺序排成一个队列。再按顺序依次执行。主要代码：void short_timefirst(char algo)PC q;int t;prt3();for(int j = 0; j N ; j+)pj.state = R;for(int i=0;iN;i+)if(p1i.state = W) p1i.waittime=Tim;if(strcmp(,)=0) p1i.state = R;prit(i);p1i.state = F;p1i.cputime=p1i.needtime;p1i.needtime=0;elseprit(i);pj.state = F;pj.cputime=pj.needtime;pj.needtime=0;pj.waittime=Tim;Tim+=pj.cputime;printf(*n); for(int i=0;iN;i+) prit(i);printf(*n); printf( 输出结束n);getchar();四 调试分析、测试结果一进入系统显示欢迎界面二如果选择P进行优先数算法则提示输入进程数：三输入进程号和运行时间：四输出优先数算法信息：五可以继续选择R进行时间片轮转算法，并输入时间片大小：六输出时间片轮转算法信息：附录#include#include#include#includeusing namespace std;typedef struct nodechar name10;int prio;int round;int needtime;int cputime;int count;int state;struct node *next;bool operator (const node& o)const if(state = o.state) return prio o.state;PCB;priority_queue pq,pqempty,pp,qq;PCB *finish,*ready,*tail,*run;int N , Num;typedef struct nodchar name10;int needtime;int cputime;int waittime;int state;struct node *next;PC;PC p10;PC p110;int Tim=0;void firstin() run=ready;run-state=R;ready=ready-next;void prt1(char a)if(a=P)printf(* 进程号 cpu时间 所需要时间 优先数 状态 *n);else printf(* 进程号 cpu时间 所需时间 记数 时间片 状态 *n); void prt2(char a,PCB q)if(a=P) printf(* %-10s %-10d %-10d %-10d %-10d *n,,q.cputime,q.needtime+Tim,q.prio,q.state);else printf(* %-10s %-10d %-10d %-10d %-10d %-10c *n,,q.cputime,q.needtime+Tim,q.count,q.round,q.state);void prt22(char a,PCB *q)printf(* %-10s %-10d %-10d %-10d %-10d %-10c*n,q-name,q-cputime,q-needtime,q-count,q-round,q-state);void prt(char algo)PCB *q;prt1(algo);if(run!=NULL) prt22(algo,run); q=ready; while(q!=NULL&q!=run)prt22(algo,q);if(q-next = run) break;else q = q-next;q=finish;while(q!=NULL)prt22(algo,q);q=q-next;getchar();void priority(char algo)PCB q;prt1(algo);for(int i = 0; i0)q.needtime-;if(q.needtime = 0)q.state = 3;if(q.state!=3)q.prio-=3;pp.push(q);while(!pq.empty()q = pq.top();pq.pop(); if(q.needtime = 0)q.state = 3;prt2(algo , q);prt1(algo);pp.push(q);pq = pp;pp = pqempty; printf(*n); printf( 输出结束n);getchar();void create1(char algo)PCB p;int i,time;char na10;ready=NULL;finish=NULL;run=NULL;printf( 输入进程号和运行时间：n);printf();for(i=1;inext =q;tail=tail-next;void create2(char algo)PCB *p;int i,time;char na10;ready=NULL;finish=NULL;run=NULL;printf( 输入进程号和运行时间：nn);printf();for(i=1;iname,na);p-cputime=0; p-needtime=time; p-state=W; p-round =0;p-count =0;if(ready!=NULL) insert2(p);elsep-next=ready; ready=p;tail=ready;printf( 时间片轮转法输出信息:n);printf(*n); run=ready; ready=ready-next;tail-next =run;run-state=R;prt(algo);void Roundrun(int timeSlice)while(run != NULL)run-cputime = run-cputime + timeSlice;run-needtime = run-needtime - timeSlice;run-round+=timeSlice;run-count+;if(run-needtime needtime = 0;run-next = finish; finish = run;if(run != tail)tail-next = ready;elseready = NULL;run-state = F;run = NULL;if(ready != NULL)firstin();elseif(ready != NULL)run-state = W;tail = run;run = ready; run - state = R; ready = ready - next; prt(r);printf( 输出结束n);printf(*n); int cmp(const void *a,const void *b)return (struct nod*)a)-needtime - (struct nod*)b)-needtime;void create3(char algo)int i,time;char na10;printf( 输入进程号和运行时间：n);printf();for(i=0;iN;i+)scanf(%s,na);scanf(%d,&time);if(i!=N) printf();strcpy(,na);pi.cputime=0; pi.needtime=time; pi.waittime=0; pi.state=W;p1i=pi; qsort(p,N,sizeof(p0),cmp);printf(短作业优先算法输出信息:n);printf(*n);void prt3()printf(* 进程号 cpu时间 所需要时间 已等待时间 状态 *n); void prit(int i)PC q=p1i;printf(* %-10s %-10d %-10d %-10d %-10c *n,,q.cputime,q.needtime,q.waittime,q.state);void short_timefirst(char algo)PC q;int t;prt3();for(int j = 0; j N ; j+)pj.state = R;for(int i=0;iN;i+)if(p1i.state = W) p1i.waittime=Tim;if(strcmp(,)=0) p1i.st