《操作系统》实验二 进程调度.doc

实验二、多任务操作系统下的进程调度（综合性实验）一、实验目的进程是操作系统中最重要的概念之一,进程调度又是操作系统核心的主要内容。通过编写和调试进程调度程序,加深对进程调度工作和各种调度算法的了解。二、实验要求用C语言实现进程调度控制过程中的有关工作：现场保护与恢复，处理运行指针和进程调度。三、实验内容1、实验准备首先进行系统初始化 , 在创建了系统进程、各用户进程之后转进程调度控制程序 , 即进入多进程并发执行的状态。进程调度控制程序负责将 CPU 控制以从一个进程转向另一个进程。当进行控制权转接时必须做以下几件事 :保护当前运行进程的现场；处理当前运行进程 , 将该进程插入就绪队列或其它队列；选一优先级最高的进程作为运行进程；恢复被选中进程的现场。现场的保护与恢复是经过两个步骤完成的。其中,在保护现场时,首先将CPU现场信息送内存r区,然后再将r区内容保存到该进程pcb的reg区；恢复现场则相反,首先从被选中进程的 pcb的reg区中恢复现场信息到内存r区,然后用r区内容设置CPU各寄存器。 2、数据结构 struct pcbint id; /*进程标识*/int priority; /*优先数或轮转时间片数*/int cputime; /*已占用CPU的时间片数*/int alltime; /*进程所需的时间片数*/char status; /*进程状态指针*/*next; /*进程当前队列链接字*/*all_q_next; /*总链队列链接字*/ pcbanum;3、算法（1）优先数法进程就绪链按优先数大小从高到低排列，链首进程首先投入运行。每过一个时间片,运行进程所需运行的时间片数减1,说明它运行了一个时间片；优先数减3,因为一个进程运行时如果在一个片中完成不了， 其优先级应降低一级。（注意,在本程序中通过对进程的PCB执行”优先数-3“和“进程所需时间片数-1”以及“进程已占用CPU的时间片数+1”来模拟进程的一次运行。而在实际的系统中，当一个进程被选中运行时, 必须恢复进程的现场,让它占有CPU运行,直到出现等待事件或运行结束）。然后比较现行程序和就绪链链首进程的优先数,如果仍是现行进程高或者相同,就让现行进程继续运行,否则,将现行运行进程按其优先数大小插入就绪链,将其状态改为“就绪态”，并调度就绪链链首进程投入运行。直到所有的进程都运行完其各自的时间片数。（2）简单轮转法进程就绪链按进程进入的先后排列,进程每次占用CPU的轮转时间按其重要程度登入PCB中的“优先数/轮转时间片数”记录顶。每过一个时间片,运行进程占用CPU的时间片数加1,进程所需的时间片数减1（和优先数法类似，程序只是简单地通过PCB中的cputime+1,alltime-1来模拟进程的一次运行）。然后比较占用CPU的时间片数（即cputime）是否与该进程的轮转时间片数（即priority）相等,若相等则说明已到达轮转时间,应将现行运行进程排到就绪链链尾，调度链首进程占用CPU,并改变它们的进程状态,直到所有的进程完成各自的时间片（alltime=0）。4.程序构成由六个子程序构成，各子程序及其完成的工作为：（1）init子程序按照给定的进程调度算法（优先数法或简单轮转法）随机地产生5个进程控制块的内容,并形成进程控制块链。置链首进程为初始运行进程。（2）print子程序按格式打出调度信息及各进程控制块的内容，print子程序在每次进程调度的时候都要执行一次。（3）prisch子程序将优先数算法调度进程使之模拟运行。（4）insert子程序将落选的进程按优先数大小插入到就绪队到。（5）timesch子程序按简单轮转算法调度进程使之模拟运行。（6）insert1子程序将落选的进程链到就绪队队列末尾。各子程序之间的调度关系如下图2.1:main timesch init prisch Insert1printinsert 图2.1程序之间调度关系5、程序框图开始 输入调度算法轮转优先数优先数或轮转？生成按进入次序排列的PCB生成按优先数大小排列的PCB链首进程投入运行链首进程投入运行时间片到，进程时间片数-1,占用CPU时间+1时间片到，进程时间片数-1,优先数-3N占用CPU时间已到轮转时间N进程时间片数为0？N进程时间片数为0？YY优先数不小于链首进程？撤消该进程撤消该进程Y-从链首取一个进程运行进程退出，排列进程链尾从链首取一个进程Y队列为空？N队列为空？NY运行进程退出，按优先数插入进程链N结束结束四、进程调度示例1、问题描述本系统的同步机构采用的信号量上的P、V操作的机制;控制机构包括阻塞和唤醒操作；时间片中断处理程序处理模拟的时间片中断；进程调度程序负责为各进程分配处理机。系统中设计了3个并发进程。它们之间有如下同步关系：3个进程需要互斥使用临界资源s2,进程1和进程2又需互斥使用临界资源s1。本系统在运行过程中随机打印出各进程的状态变换过程 , 系统的调度过程及公共变量的变化情况。2、算法系统为进程设置了5种运行状态:e一一执行态;r一一高就绪态;t一一低就绪态(执行进程因时间片到限而转入)；w一等待态；c一完成态。各进程的初始状态均设置为r。系统分时执行各进程,并规定3个进程的执行概率均为33%。通过产生随机数x来模拟时间片。当进程process1访问随机数x时,若x0.33;当进程process2访问x时,若x0.33或x0.66;当进程process3访问x时,若x0.66,则分别认为各进程的执行时间片到限,产生“时间片中断“而转入低就绪态t。进程调度算法采用剥夺式最高优先数法。各进程的优先数通过键盘输入予以静态设置。调度程序每次总是选择优先数最大(优先权最高)的就绪进程投入执行。先从r状态进程中选择,再从t状态进程中选择。当现行进程唤醒某个等待进程,且被唤醒进程的优先数大于现行进程时,则剥夺现行进程的执行权。各进程在使用临界资源s1和s2时,通过调用信号量sem1和sem2上的P、V操作来实现同步。 阻塞和唤醒操作负责完成从进程的执行态到等待态以及从等待态到就绪态的转换。系统启动后,在完成必要的系统初始化后便执行进程调度程序。当执行进程因“时间片中断“或被排斥使用临界资源,或唤醒某个等待进程时，立即进行进程调度。当3个进程都处于完成状态后，系统退出运行。3、数据结构（1）、信号量semaphore,对应于临界资源s1和s2分别有sem1和sem2,均为互斥信号量,内容为： value 信号量值,初值为1;firstwr 等待链首指针,指示该信号量上第一个等待进程的标识数。（2）、现场保留区,用数组savearea34表示。即每个进程都有一个大小为4个单元的保留区,用来保存被“中断”时的现场信息,如通用寄存器的内容和断点地址等。此外 ,系统中还用到下列主要全程变量：exe 执行进程指针,其值为进程标识数 ;I 用来模拟一个通用寄存器 ;Addr 用来模拟程序计数器S1,s2 两个公共变量，用作共享临界资源4、程序描述#include#define TRUE 1#define FALSE 0#define MAXPRI 100#define NIL -1structint id;char status;int t nextwr;int prority;pcb3;structint value;int firstwr;sem2;char savearea34,addr;int I,s1,s2,seed,exe=NIL;init() /*initialization*/int j;for(j=0;j3;j+)pcbj.id=j;pcbj.status=r;pcbj.nextwr=NIL;printf(“nprocess%dpriority?”,j+1);scanf(“%d”,&I);pcbj.priority=I;sem0.value=1;sem0.firstwr=NIL;sem1.value=1; sem1.firstwr=NIL;for(I=1;i3;i+)for(j=0;j4;j+)saveareaij=0;float random( )int m;if(seedO)m=-seed;else m=seed(25173*seed+13849)%655365retrun(m/32767.0);timeint(ad) /*time slice interrupt*/char ad;float x;x=random();if(x0.33)& (exe=0)return (FALSE)if(x0.66)& (exe=1)return(FALSE);if(x1.O)&(exe=2)return(FALSE)saveareaexe0=I;saveareaexe1=ad;pcbexe.status=t;printf(“time silce interruptnprocess%d enter into ready.n”,exe+l);exe=NIL;return(TRUE);scheduler()int pd;if(pd=find()=NIL&exe= NIL)return(NIL); /*quit system*/if(pd!=NIL) if(exe=NIL)pcbpd.status=e;exe=pd;printf(“process%d is executing.n”,exe+1);else if(pcbpd.prioritypcbexe.priority) pcbexe.status=r;printf(“process%d enter into readyn,exe+1);pcbpd.status=e;exe=pd;printf(“process%d is execitingn”,exe+1);I=saveareaexe0;Addr= saveareaexe1;Return(exe);find()int j,pd=NIL;w=MAXPRI;for(j=0; j3; j+)if(pcbj.status=r)if(pcbj.priorityw)w=pcbj.priority;pd=j;if(pd=NIL)for (j=O;j3;j+)if(Pcbj.status=t)if(pcbj.priority=0)retrun(FALSE);block(se);saveareaexe0=I;saveareaexe1=ad;exe=NIL;return(TRUE);block(se)int se;int w;printf(process%d is blockedn”,exe+1);pcbexe.status=w;pcbexe.nextwr=NIL;if(w=semse.firstwr)=NIL)semse.firstwr=exe;else while(pcbw.nextwr!=NIL) w=pcbw.nextwr; pcbw.nextwr=exe; v(se,ad)int se;char ad;if(+semse.valueO)return(FALSE); wakeup(se);saveareaexe0=I;saveareaexe1=ad;return(TRUE);wakeup(se)int se;int w;w=semse.firstwr;if(w!=NIL)semse.firstwr=pcbw.nextwr;pcbw.status=r;printf(proces%d is waken upn”,w+1);process1()if(addr=a)goto a1;if(addr=b) goto b1;if(addr=c) goto c1;if(addr=d) goto d1;if(addr=e) goto e1;if(addr=f) goto fl;for (i=1;i6;i+)printf(“process1 calls P on the semaphore 1 n”);if(p(O,a)break;a1:printf(“process1 is executing in the critical section 1n”);if(timeint(b)break;b1:printf(“s1=%dn”,+s1);printf(“process1 calls V on semaphore 1 and quit critical section 1n”);if(v(O,c)break;c1: printf(“process1 calls P on the semaphore 2 n”);if(p(1,d)break;d1: printf(“process1 is executing cretical section 2n”);if(timeint(e)break;e1: printf(“s2=%dn”,+s2);printf(“process1 calls V on semaphore 2 and quit cretical section 2n”);if(v(1,f)break;f1:printf(“process 1 cycle count=%dn”,I);if(I6)return;eexit(0);process2()if(addr=a)goto a2;if(addr=b) goto b2;if(addr=c) goto c2;if(addr=d) goto d2;if(addr=e) goto e2;if(addr=f) goto f2;for (i=1;i6;i+)printf(“process2 calls P on the semaphore 2 n”);if(p(1,a)break;a2:printf(“process2 is executing in the critical section 2n”);if(timeint(b)break;b2:printf(“s2=%dn”,+s2);printf(“process2 calls V on semaphore 2 and quit critical section 2n”);if(v(1,c)break;c2: printf(“process2 calls P on the semaphore 1 n”);if(p(0,d)break;d2: printf(“process2 is executing cretical section 1n”);if(timeint(e)break;e2: printf(“s1=%dn”,+s1);printf(“process2 calls V on semaphore 1 and quit cretical section 1n”);if(v(0,f)break;f2:printf(“process 2 cycle count=%dn”,I);if(I6)return;eexit(1);process3()if(addr=a)goto a3;if(addr=b) goto b3;if(addr=c) goto c3;for (i=1;i6;+i)printf(“process3 calls P on the semaphore 2 n”);if(p(1,a)break;a3:printf(“process3 is executing on its critical sectionn”);if(timeint(b)break;b3:printf(“s2=%dn”,+s2);printf(“process3 calls V on semaphore 2 and quit critical section.n”);if(v(1,c)break;c3:printf(“process 3 cycle