使用动态优先权的进程调度算法的模拟.doc

使用动态优先权的进程调度算法的模拟（1）用C语言实现对5个进程采用动态优先权优先算法的进程调度。（2）每个用来标识进程的进程控制块PCB用结构来描述，包括以下字段：进程标识树ID进程优先数PRIORITY，并规定优先数越大的进程，其优先全越高。进程已占用的CPU时间CPUTIME。进程还需占用的CPU时间ALLTIME。当进程运行完毕时，ALLTIME变为0进程的阻塞时间STARTBLOCK，表示当进程再运行STARTBLOCK个时间片后，进程将进入阻塞状态进程被阻塞的时间BLOCKTIME，表示已阻塞的进程再等待BLOCKTIME个时间片后，将转换成就绪状态进程状态STATE（3）优先数改变的原则：进程在就绪队列中待一个时间片，优先数增加1进程每运行一个时间片，优先数减3（4）假设在调度前，系统中有5个进程，它们的初始状态如下：ID 0 1 2 3 4PRIORITY 9 38 30 29 0CPUTIME 0 0 0 0 0ALLTIME 3 3 6 3 4STARTBLOCK 2 -1 -1 -1 -1BLOCKTIME 3 0 0 0 0STATE READY READY READY READY READY（5）为了清楚的观察诸进度的调度过程，程序应将每个时间片内的进程的情况显示出来，具体格式如下：RUNNING PROG：i=ID 0 1 2 3 4PRIORITY P0 P1 P2 P3 P4CPUTIME C0 C1 C2 C3 C4ALLTIME A0 A1 A2 A3 A4STARTBLOCK T0 T1 T2 T3 T4BLOCKTIME B0 B1 B2 B3 B4STATE READY READY READY READY READY代码如下：#include#include void main()int ID5=0,1,2,3,4;int PRIORITY5=9,38,30,29,0;int CPUTIME5=0,0,0,0,0;int ALLTIME5=3,3,6,3,4;int STARTBLOCK5=2,-1,-1,-1,-1;int BLOCKTIME5=3,0,0,0,0;int str5;/1=READY,0=BLOCK,-1=ENDint max5(int PRIORITY50,int PRIORITY51,int PRIORITY52,int PRIORITY53,int PRIORITY54);int max4(int PRIORITY40,int PRIORITY41,int PRIORITY42,int PRIORITY43);int max3(int PRIORITY30,int PRIORITY31,int PRIORITY32);int max2(int PRIORITY20,int PRIORITY21);int i=1,a,b0,b1,b2,b3,b4,c0,c1,c2,c3,c4;/=if(max5(ALLTIME0,ALLTIME1,ALLTIME2,ALLTIME3,ALLTIME4)0)for(;max5(ALLTIME0,ALLTIME1,ALLTIME2,ALLTIME3,ALLTIME4)0;)if(ALLTIME00|ALLTIME10|ALLTIME20|ALLTIME30|ALLTIME40)a=max5(PRIORITY0,PRIORITY1,PRIORITY2,PRIORITY3,PRIORITY4);else if(ALLTIME0=0|ALLTIME10|ALLTIME20|ALLTIME30|ALLTIME40)a=max4(PRIORITY1,PRIORITY2,PRIORITY3,PRIORITY4);else if(ALLTIME00|ALLTIME1=0|ALLTIME20|ALLTIME30|ALLTIME40)a=max4(PRIORITY0,PRIORITY2,PRIORITY3,PRIORITY4);else if(ALLTIME00|ALLTIME10|ALLTIME2=0|ALLTIME30|ALLTIME40)a=max4(PRIORITY0,PRIORITY1,PRIORITY3,PRIORITY4);else if(ALLTIME00|ALLTIME10|ALLTIME20|ALLTIME3=0|ALLTIME40)a=max4(PRIORITY0,PRIORITY1,PRIORITY2,PRIORITY4);else if(ALLTIME00|ALLTIME10|ALLTIME20|ALLTIME30|ALLTIME4=0)a=max4(PRIORITY0,PRIORITY1,PRIORITY2,PRIORITY3);/=else if(ALLTIME0=0|ALLTIME1=0|ALLTIME20|ALLTIME30|ALLTIME40)a=max3(PRIORITY2,PRIORITY3,PRIORITY4);else if(ALLTIME0=0|ALLTIME10|ALLTIME2=0|ALLTIME30|ALLTIME40)a=max3(PRIORITY1,PRIORITY3,PRIORITY4);else if(ALLTIME0=0|ALLTIME10|ALLTIME20|ALLTIME3=0|ALLTIME40)a=max3(PRIORITY1,PRIORITY2,PRIORITY4);else if(ALLTIME0=0|ALLTIME10|ALLTIME20|ALLTIME30|ALLTIME4=0)a=max3(PRIORITY1,PRIORITY2,PRIORITY3);else if(ALLTIME00|ALLTIME1=0|ALLTIME2=0|ALLTIME30|ALLTIME40)a=max3(PRIORITY0,PRIORITY3,PRIORITY4);else if(ALLTIME00|ALLTIME1=0|ALLTIME20|ALLTIME3=0|ALLTIME40)a=max3(PRIORITY0,PRIORITY2,PRIORITY4);else if(ALLTIME00|ALLTIME1=0|ALLTIME20|ALLTIME30|ALLTIME4=0)a=max3(PRIORITY0,PRIORITY2,PRIORITY3);else if(ALLTIME00|ALLTIME10|ALLTIME2=0|ALLTIME3=0|ALLTIME40)a=max3(PRIORITY0,PRIORITY1,PRIORITY4);else if(ALLTIME00|ALLTIME10|ALLTIME2=0|ALLTIME30|ALLTIME4=0)a=max3(PRIORITY0,PRIORITY1,PRIORITY3);else if(ALLTIME00|ALLTIME10|ALLTIME20|ALLTIME3=0|ALLTIME4=0)a=max3(PRIORITY0,PRIORITY1,PRIORITY2);/=else if(ALLTIME0=0|ALLTIME1=0|ALLTIME2=0|ALLTIME30|ALLTIME40)a=max2(PRIORITY3,PRIORITY4);else if(ALLTIME0=0|ALLTIME1=0|ALLTIME20|ALLTIME3=0|ALLTIME40)a=max2(PRIORITY2,PRIORITY4);else if(ALLTIME0=0|ALLTIME1=0|ALLTIME20|ALLTIME30|ALLTIME4=0)a=max2(PRIORITY2,PRIORITY3);else if(ALLTIME0=0|ALLTIME10|ALLTIME2=0|ALLTIME3=0|ALLTIME40)a=max2(PRIORITY1,PRIORITY4);else if(ALLTIME0=0|ALLTIME10|ALLTIME2=0|ALLTIME30|ALLTIME4=0)a=max2(PRIORITY1,PRIORITY3);else if(ALLTIME00|ALLTIME1=0|ALLTIME2=0|ALLTIME3=0|ALLTIME40)a=max2(PRIORITY0,PRIORITY4);else if(ALLTIME00|ALLTIME1=0|ALLTIME2=0|ALLTIME30|ALLTIME4=0)a=max2(PRIORITY0,PRIORITY3);else if(ALLTIME0=0|ALLTIME10|ALLTIME20|ALLTIME3=0|ALLTIME4=0)a=max2(PRIORITY1,PRIORITY2);else if(ALLTIME00|ALLTIME1=0|ALLTIME20|ALLTIME3=0|ALLTIME4=0)a=max2(PRIORITY0,PRIORITY2);else if(ALLTIME00|ALLTIME10|ALLTIME2=0|ALLTIME3=0|ALLTIME4=0)a=max2(PRIORITY0,PRIORITY1);/=else if(ALLTIME00|ALLTIME1=0|ALLTIME2=0|ALLTIME3=0|ALLTIME4=0)a=PRIORITY0;else if(ALLTIME0=0|ALLTIME10|ALLTIME2=0|ALLTIME3=0|ALLTIME4=0)a=PRIORITY1;else if(ALLTIME0=0|ALLTIME1=0|ALLTIME20|ALLTIME3=0|ALLTIME4=0)a=PRIORITY2;else if(ALLTIME0=0|ALLTIME1=0|ALLTIME2=0|ALLTIME30|ALLTIME4=0)a=PRIORITY3;else if(ALLTIME0=0|ALLTIME1=0|ALLTIME2=0|ALLTIME3=0|ALLTIME40)a=PRIORITY4;/=if(a=PRIORITY0)i=0;PRIORITY0-=3;PRIORITY3+=1;PRIORITY1+=1;PRIORITY2+=1;PRIORITY4+=1;CPUTIME0+=1;ALLTIME0-=1;STARTBLOCK0-=1;STARTBLOCK3-=1;STARTBLOCK1-=1;STARTBLOCK2-=1;STARTBLOCK4-=1;BLOCKTIME3-=1;BLOCKTIME1-=1;BLOCKTIME2-=1;BLOCKTIME4-=1;else if(a=PRIORITY1)i=1;PRIORITY1-=3;PRIORITY0+=1;PRIORITY2+=1;PRIORITY3+=1;PRIORITY4+=1;CPUTIME1+=1;ALLTIME1-=1;STARTBLOCK1-=1;STARTBLOCK0-=1;STARTBLOCK3-=1;STARTBLOCK2-=1;STARTBLOCK4-=1;BLOCKTIME0-=1;BLOCKTIME3-=1;BLOCKTIME2-=1;BLOCKTIME4-=1; else if(a=PRIORITY2)i=2;PRIORITY2-=3;PRIORITY0+=1;PRIORITY1+=1;PRIORITY3+=1;PRIORITY4+=1;CPUTIME2+=1;ALLTIME2-=1;STARTBLOCK2-=1;STARTBLOCK0-=1;STARTBLOCK1-=1;STARTBLOCK3-=1;STARTBLOCK4-=1;BLOCKTIME0-=1;BLOCKTIME1-=1;BLOCKTIME3-=1;BLOCKTIME4-=1;else if(a=PRIORITY3)i=3;PRIORITY3-=3;PRIORITY0+=1;PRIORITY1+=1;PRIORITY2+=1;PRIORITY4+=1;CPUTIME3+=1;ALLTIME3-=1;STARTBLOCK3-=1;STARTBLOCK0-=1;STARTBLOCK1-=1;STARTBLOCK2-=1;STARTBLOCK4-=1;BLOCKTIME0-=1;BLOCKTIME1-=1;BLOCKTIME2-=1;BLOCKTIME4-=1;else if(a=PRIORITY4)i=4;PRIORITY4-=3;PRIORITY0+=1;PRIORITY1+=1;PRIORITY2+=1;PRIORITY3+=1;CPUTIME4+=1;ALLTIME4-=1;STARTBLOCK4-=1;STARTBLOCK0-=1;STARTBLOCK1-=1;STARTBLOCK2-=1;STARTBLOCK3-=1;BLOCKTIME0-=1;BLOCKTIME1-=1;BLOCKTIME2-=1;BLOCKTIME3-=1;if(BLOCKTIME0=-1)BLOCKTIME0=0;if(BLOCKTIME1=-1)BLOCKTIME1=0;if(BLOCKTIME2=-1)BLOCKTIME2=0;if(BLOCKTIME3=-1)BLOCKTIME3=0;if(BLOCKTIME4=-1)BLOCKTIME4=0;if(BLOCKTIME00)str0=0;elseif(BLOCKTIME0=0)str0=1;elseif(ALLTIME00)str1=0;elseif(BLOCKTIME1=0)str1=1;elseif(ALLTIME10)str2=0;elseif(BLOCKTIME2=0)str2=1;elseif(ALLTIME20)str3=0;elseif(BLOCKTIME3=0)str3=1;elseif(ALLTIME30)str4=0;elseif(BLOCKTIME4=0)str4=1;elseif(ALLTIME4=0)str4=-1;/=if(ALLTIME0=0)PRIORITY0=0;ALLTIME0=0;STARTBLOCK0=-1;BLOCKTIME0=0;if(ALLTIME1=0)PRIORITY1=0;ALLTIME1=0;STARTBLOCK1=-1;BLOCKTIME1=0;if(ALLTIME2=0)PRIORITY2=0;ALLTIME2=0;STARTBLOCK2=-1;BLOCKTIME2=0;if(ALLTIME3=0)PRIORITY3=0;ALLTIME3=0;STARTBLOCK3=-1;BLOCKTIME3=0;if(ALLTIME4id%d-id%d-id%d-id%d-id%dn,b0,b1,b2,b3,b4);/printf(BLOCK_QUENE:-id%d-id%d-id%d-id%d-id%dn,c0,c1,c2,c3,c4);printf(=n);printf(IDtt%dt%dt%dt%dt%dn,ID0,ID1,ID2,ID3,ID4);printf(PRIORITYt%dt%dt%dt%dt%dn,PRIORITY0,PRIORITY1,PRIORITY2,PRIORITY3,PRIORITY4);printf(CPUTIMEtt%dt%dt%dt%dt%dn,CPUTIME0,CPUTIME1,CPUTIME2,CPUTIME3,CPUTIME4);printf(ALLTIMEtt%dt%dt%dt%dt%dn,ALLTIME0,ALLTIME1,ALLTIME2,ALLTIME3,ALLTIME4);printf(STARTBLOCKt%dt%dt%dt%dt%dn,STARTBLOCK0,STARTBLOCK1,STARTBLOCK2,STARTBLOCK3,STARTBLOCK4);printf(BLOCKTIMEt%dt%dt%dt%dt%dn,BLOCKTIME0,BLOCKTIME1,BLOCKTIME2,BLOCKTIME3,BLOCKTIME4);printf(STATEtt%dt%dt%dt%dt%dn,str0,str1,str2,str3,str4);printf(tt1=READY,0=BLOCK,-1=ENDnnnn);elseprintf(nAll of the PROGS has been finished.n);/=int max5(int PRIORITY50,int PRIORITY51,int PRIORITY52,int PRIORITY53,int PRIORITY54)int PRIORITY_max;if(PRIORITY50PRIORITY51)PRIORITY_max=PRIORITY50;else PRIORITY_max=PRIORITY51;if(PRIORITY52PRIORITY_max)PRIORITY_max=PRIORITY52;elseif(PRIORITY53PRIORITY_max)PRIORITY_max=PRIORITY53;elseif(PRIORITY54PRIORITY_max)PRIORITY_max=PRIORITY54;elsePRIORITY_max=PRIORITY_max;return(PRIORITY_max);int max4(int PRIORITY40,int PRIORITY41,int PRIORITY42,int PRIORITY43)int PRIORITY_max;if(PRIORITY40PRIORITY41)PRIORITY_max=PRIORITY40;else PRIORITY_max=PRIORITY41;if(PRIORITY42PRIORITY_max)PRIORITY_max=PRIORITY42;elseif(PRIORITY43PRIORITY_max)PRIORITY_max=PRIORITY43;else PRIORITY_max=PRIORITY_max;return(PRIORITY_max);int max3(int PRIORITY30,int PRIORITY31,int PRIORITY32)int PRIORITY_max;if(PRIORITY30PRIORITY31)PRIORITY_max=PRIORITY30;else PRIORITY_max=PRIORITY31;if(PRIORITY32PRIORITY_max)PRIORITY_max=PRIORITY32;else PRIORITY_max=PRIORITY_max;return(PRIORITY_max);int max2(int PRIORITY20,int PRIORITY21)int PRIORITY_max;if(PRIORITY20PRIORITY21)PRIORITY_max=PRIORITY20;else PRIORITY_max=PRIORITY21;return(PRIORITY_max);/（使用VC6.0编译）前言:谈到在Windows创建线程的例子，在网上的很多的参考都是基于MFC的。其实，就操作系统实验这个前提而言，大可不必去碰那个大型的MFC的框架。1中提到了在Windows命令控制台下创建进程及线程的方法，本文对1中的方法加以了实现，并做些简单的进程及线程的测试程序。1、实验准备:要实验的Windows下的多线程实验，应做如下准备:a) 在新建中选”Win32 Console Application”An empty projectb) 选”工程”设置”选项，在”设置”中选择“C/C+”标签，在”Project Option”中，将”MLd”参数改成“MTd”(如图1)。(图片较大，请拉动滚动条观看)图1以上两步对实验成功至关重要，否则，即是代码无误，在连接时同样会出现问题。2、Windows下进程的创建:在1中，Windows的进程和线程模型被描述成”多进程，基于单进程的多线程”。在创建一个线程时，Windows会做大量的工作-创建一个新的地址空间，为进程分配资源以及创建一个基线程。CreateProcess函数的原型如下:CreateProcess(LPCTSTR lpApplicationName，/pointer to name of executable moudleLPTSTR cmdLine，/pointer to command line stringLPSECURITY_ATTRIBUTES lpProcessAttributes，/pointer to process security attributesLPSECURITY_ATTRIBUTES lpThreadAttributes，/pointer to theread security attributesBOOL bInheritHandle ，/handle inheritance flagDWORD dwCreationFlag，/various creation flagsLPVOID lpEnviroment，/Enviroment variableLPCTSTR lpCurrentDirectory， /Childs current directoryLPSTARTUPINFO lpStartupInfo， /pointer to StartupInfoLPPROCESS_INFORMATION lpProcessInformation /pointer to PROCESS_INFORMATION )虽然有很多参数，不过在现阶段的实验级别，大多数参数只要用默认值即可。下面要做的关于Windows使用进程的实验，在Linux系统下，可以使用类似:execve(char* cmdName ， char* cmdArgu)的语句从一个程序中去执行其它的程序。而如果在Windows下，当使用CreateProcess去执行相应的功能时，只要去改变cmdLine中的内容即可，其它的参数使用默认值，具体见代码1:代码1执行的功能是从命令行中启动这个名叫的launch的测试程序，在launch后面应加上保存有需要打开程序路径的文件名:如在命令行中键入:launch set.txt而set.txt中的内容为:C:WINDOWSSYSTEM32CALC.EXEC:WINDOWSSYSTEM32NOTEPAD.EXE NEW.TXTC:WINDOWSSYSTEM32CHARMAP.EXE路径的前半部分为”C:WINDOWS”，这当然要视你的Windows系统的类型以及系统盘的存放位置而定。如果是NT或2000的机器，则应使用WINNT./*测试程序1:示例如何使用进程的launch程序，通过在命令行中加载相应的命令文件，去按照命令文件中指定的程序路径打开相应的程序去执行*/#include #include #include #define MAX_LINE_LEN 80int main(int argc，char* argv)/local variablesFILE* fid;char cmdLineMAX_LINE_LEN;/CreateProcess parametersLPSECURITY_ATTRIBUTES processA=NULL;/DefaultLPSECURITY_ATTRIBUTES threadA=NULL;/DefaultBOOL shareRights=TRUE;/DefaultDWORD creationMask=CREATE_NEW_CONSOLE;/Window per process.LPVOID enviroment=NULL;/DefaultLPSTR curDir=NULL;/DefaultSTARTUPINFO startInfo;/ResultPROCESS_INFORMATION procInfo;/Result/1.Read the command line parametersif(argc!=2)fprintf(stderr，Usage:lanchn);exit(0);/2.Open a file that coutain a set of commandsfid=fopen(argv1，r);/3.For every command in the launch filewhile(fgets(cmdLine，MAX_LINE_LEN，fid)!=NULL)/Read a command from the fileif(cmdLinestrlen(cmdLine)-1=n)cmdLinestrlen(cmdLine)-1=0;/Remove NEWLINE/Create a new process to execute the commandZeroMemory(&startInfo，sizeof(startInfo);startInfo.cb=sizeof(startInfo);if(!CreateProcess(NULL，/File name of executablecmdLine，/command lineprocessA，/Process inherited securitythreadA， /Thread inherited securityshareRights，/Rights propagationcreationMask，/various creation flagsenviroment，/Enviroment variablecurDir， /Childs current directory&startInfo，&procInfo )fprintf(stderr，CreatProcess failed on error %dn，GetLastError();ExitProcess(0。); /Terminate after all commands have finished.return 0;通过上面这段极其简洁的代码，完成了看似有些难度的任务，让我们充分感受到采用一些高级的编程手段所带来的便捷与高效. 2、Windows线程的创建及实验:2.1 使用CreateThread在Windows下创建线程:在Windows中创建线程可以调用两个函数_beginthreadex和CreateThread两个函数，这里只介绍后者。CreateThread函数原型:HANDLE CreateThread(LPSECURITY_ATTRIBUTES lpThreadAttributes，/pointer to thread security attributesDWORD dwStackSize，/initial thread stack size， in bytesLPSECURITY_START_ROUTINE lpStartAddress，/pointer to thread functionLPVOID lpParameter，/argument for new threadDWORD dwCreationFlags，/creation flagsLPDWORD lpThreadId /pointer to returned thread identifier)其中，在本实验阶段比较重要的参数是第三和第四个:a)第三个参数是一个指向函数的指针，所以应传入的参数应为函数的地址，如&Func的形式.而这个传入的参数，则必须被声明成为:DWORD WINAPI threadFunc(LPVOID threadArgu);的形式.这个函数也就是要执行线程任务的那个函数体实体.这里应注意，传入应使用Func而非&Func。如：CreateThread(NULL，0，Func，)具体原因：我目前认为是系函数前部使用WINAPI所致。 b)第四个参数应是执行线程任务的函数体实体所需要的参数，即上面所举例的函数threadFunc的参数threadArgu，这在WINDOWS中被定义成一个LPVOID的类型，目前我认为，可以把它在功能上看成和void* 类似。参考:LPVOID的原型:typedef void far *LPVOID;所以，当你有自己需要的类型的参数传入时，可以用typedef struct int firstArgu，long secArgu，myType，* pMyType;将你想要传入的参数装入一个结构体中。在传入点，使用类似:pMyType pMyTpeyArgu;CreateThread(NULL，0，threadFunc，pMyTypeArgu，);在函数threadFunc内部的接收点，可以使用“强行转换”，如:int intValue=(pMyType)lpvoid)-firstArgu;long longValue=(pMyType)lpvoid)-secArgu; 2.2 线程实验1-创建N个随机线程，所有线程的执行时间均为T秒，观察每个线程的运行状况:为了使线程的运行趋于随机化，应先使用:srand(unsigned int)time (NULL);在每个线程的运行中，每个线程的睡眠时间为:sleepTime=1000+30*(int)eRandom(50+tNo);Sleep(sleepTime);这样，可以使进程的运行趋于随机化./*测试程序2：创建N个随机线程的随机实验.命令行输入参数:test threadNo runSecs */#include #include #include #include #include #define N 5#define Type floatstatic int runFlag=TRUE;DWORD WINAPI threadWork(LPVOID threadNo);int parseArgToInt(char* inNumChar);Type eRandom(int upLimit);typedef structint data;INTEGER;void main(int argc，char* argv)unsigned int runTime;int i;int threadNum;/int N;SYSTEMTIME now;WORD stopTimeMinute，stopTimeSecond;DWORD targetThreadID;/Get command line argument，Nif(argc!=3)printf(please enter:NThread n);return;threadNum=parseArgToInt(argv1);runTime=parseArgToInt(argv2);/Get the time the threads should run，runtime/Calculate time to halt/ runTime=60;/*in seconds.*/GetSystemTime(&now);printf(mthread:Suite starting aty system time%d，%d，%dn，now.wHour，now.wMinute，now.wSecond);stopTimeSecond=(now.wSecond+(WORD)runTime)%60;stopTimeMinute=now.wMinute+(now.wSecond+(WORD)runTime)/60;/FOR 1 TO NINTEGER* tmpInt;fo