操作系统系列实验[1]---进程调度模拟实验1
Operating System series trials[1]---Process Manipulate simulate trail 1
EmilMatthew(EmilMatthew@126.com)
摘要:
本文来自于我的操作系统课程设计的系列实验.通过这个实验，用C语言模拟实现动态优先数的进程调度算法。并通过VC的SDK绘画程序将这一动态过程呈现出来.
Abstract:
This article is selected from the series trials of my operating system curriculum design. The main goal of this trial is to simulate the dynamic priority algorithm in process manipulate which use C language. What’s more, by the using of the drawing api under vc sdk programming method, the process of the algorithm could be showed out.
关键词:进程调度,动态优先级策略,计算机模拟
1.实验目的:
观察、体会操作系统的进程调度方法，并通过一个简单的进程调度模拟程序的实现，加深对进程调度算法，进程切换的理解。
2．实验内容:
采用动态优先数的方法，编写一进程调度程序模拟程序。模拟程序只进行相应的调度模拟操作。
[提示]：
(1) 假定系统有五个进程，每一个进程用一个进程控制块PCB来代表，进程控制块的格式为：
进程名
指针
要求运行时间
优先数
状态
其中，进程名——作为进程的标识，假设五个进程的进程名分别为P1，P2，P3，P4，P5。
指针——按优先数的大小把五个进程连成队列，用指针指出下一个进程的进程控制块的首地址，最后一个进程中的指针为“0”。
要求运行时间——假设进程需要运行的单位时间数。
优先数——赋予进程的优先数，调度时总是选取优先数大的进程先执行。
状态——可假设有两种状态，“就绪”状态和“结束”状态。五个进程的初始状态都为“就绪”，用“R”表示，当一个进程运行结束后，它的状态为“结束”，用“E”表示。
(2) 在每次运行你所设计的处理器调度程序之前，为每个进程任意确定它的“优先数”和“要求运行时间”。
(3) 为了调度方便，把五个进程按给定的优先数从大到小连成队列。用一单元指出队首进程，用指针指出队列的连接情况。
(4) 处理器调度总是选队首进程运行。采用动态改变优先数的办法，进程每运行一次优先数就减“1”。由于本实习是模拟处理器调度，所以，对被选中的进程并不实际的启动运行，而是执行：
优先数-1
要求运行时间-1
来模拟进程的一次运行。
提醒注意的是：在实际的系统中，当一个进程被选中运行时，必须恢复进程的现场，让它占有处理器运行，直到出现等待事件或运行结束。在这里省去了这些工作。
(5) 进程运行一次后，若要求运行时间〉0，则再将它加入队列（按优先数大小插入，且置队首标志）；若要求运行时间=0，则把它的状态修改成“结束”（E），且退出队列。
(6) 若“就绪”状态的进程队列不为空，则重复上面（4）和（5）的步骤，直到所有进程都成为“结束”状态。
(7) 在所设计的程序中应有显示或打印语句，能显示或打印每次被选中进程的进程名以及运行一次后进程队列的变化。
(8) 为五个进程任意确定一组“优先数”和“要求运行时间”，启动所设计的处理器调度程序，显示或打印逐次被选中进程的进程名以及进程控制块的动态变化过程。
3. 程序及运行情况:
3.1程序框架:
1根据条件创建PCB表，可分为随机函数式生成和指定优先级顺序生成两种。
2对PCB表中的各进程按优先级的顺序进行排序。（采用自顶向下的冒泡排序法）
3将PCB表中的各项按从前到后的顺序加入至就绪队列中.
4主摸拟过程:
注:
1runProcess为当前活动进程.这里进程的优先权数值越小，则代表其优先权越高。
2 当遇到当前插入就绪队列的进程runProcess的优先权和就绪队列中的某些进程的优先权相等时，则将runProcess置于就绪队列中的与其优先权相等的元素中的最后一个元素的后面.
while(就绪队列不为空||runProcess不为空)
{
延时
If(runProcess不为空)
{
输出当前活动进程的各属性值(如进程名，优先值,剩余运行时间)
将当前活动进程的优先值加1，剩余运行时间减1.
If(当前进程的剩余运行时间为0)
{
当前进程状态置1，并加至结束队列中.
更新PCB表中的内容.
}
else if(就绪队列不为空)//为空时就剩下一个进程，无需再加入队列
{
当前进程状况置为准备状态
根据动态优先数将当前的进程插入到就绪队列的适当的位置 更新PCB表.
}
}
If(runProcess不为空&&runProcess->remainSecs==0)
//处理只剩下最后一个进程且剩余运行时间>0的情况
置 runProcess为NULL.
if(就绪队列不为空)
{
从就绪队列中弹出一个进程给runProcess
置runProcess的状态为运行态.
更新PCB表
}
}
3.2核心数据结构及相关算法实现:
3.2.1PCB表及摸拟的进程的定义:
#define STA_READY 0
#define STA_RUN 1
#define STA_END 2
struct PCBNode
{
char processName[20];
int processID;
int remainSecs;
int priorityNum;
int staturs;
struct PCBNode* next;
};
typedef struct PCBNode* PCBList;
typedef struct PCBNode* ptrPCBNode;
struct Process
{
char processName[20];
int processID;
int staturs;
int priorityNum;
int remainSecs;
struct Process* next;
};
typedef struct Process* ptrProcess;
3.2.2和PCB表相关的函数
3.2.2.1 PCB表的排序算法(采用基于链表的冒泡算法)
void sortPCB(PCBList inPCBList)
{
ptrPCBNode outerP,innerP,a,b;
int flag=1;
if(inPCBList==NULL||inPCBList->next==NULL)
{
printf("in sortPCB,inPCBList is null\n");
}
outerP=inPCBList;
while(outerP->next!=NULL)
{
flag=1;
innerP=inPCBList;
/*Correction: should be:while(p->next!=NULL&&p->next->next!=NULL)//in C Language Usage.*/
while(innerP->next!=NULL&&innerP->next->next!=NULL)
//Correction: not innerP->next!=NULL
{ if(innerP->next->priorityNum>innerP->next->next->priorityNum)
{ flag=0;
a=innerP->next;
b=innerP->next->next;
a->next=b->next;
innerP->next=b;
b->next=a;
innerP=a;//Correction: add this to re point to new pos of innerP.
}
else
innerP=innerP->next;
}
if(flag)
break;
outerP=outerP->next;
}
}
3.2.2.2 PCB表的更新函数
void updatePCBList(PCBList pcbList,ptrProcess runProcess)
{
PCBList tmpNode;
tmpNode=pcbList;
tmpNode=tmpNode->next;
if(tmpNode==NULL||runProcess==NULL)
{
printf("in updataPCBList,null ptr pass in\n!");return;}
while(tmpNode!=NULL)
{
if(tmpNode->processID==runProcess->processID)
{
tmpNode->remainSecs=runProcess->remainSecs;
tmpNode->priorityNum=runProcess->priorityNum;
tmpNode->staturs=runProcess->staturs;
strcpy(tmpNode->processName,runProcess->processName);
break;
}
tmpNode=tmpNode->next;
}
}
3.2.3就绪队列及结束队列的实现:
采用的是带头结点的链表的作为队列实体(主要考虑插入运算的方便)
typedef ptrProcess PtrQueueType;
typedef struct Process QueueDataType;
typedef struct
{
PtrQueueType head;
PtrQueueType rear;
PtrQueueType emptyHead;
}ptrQueue;
typedef ptrQueue* pQueue;
队列的相关算法:
pQueue createNullQueueWithHead()
{
pQueue tmpQueue;
/*not a good handle below*/
tmpQueue=(pQueue)malloc(sizeof(ptrQueue));
tmpQueue->emptyHead=(PtrQueueType)malloc(sizeof(QueueDataType));
tmpQueue->head=NULL;
tmpQueue->rear=NULL;
return tmpQueue;
}
int isEmpty(pQueue inQueue)
{
return inQueue->head==NULL;
//Correction: here at the last node ,after dequeue ,the rear may not be null
}
PtrQueueType deQueue(pQueue inQueue)
{
PtrQueueType tmpQueue;
if(isEmpty(inQueue)||inQueue==NULL)
{
printf("in deQueue,inQueue is null\n");
return NULL;
}
tmpQueue=inQueue->head;
inQueue->head=inQueue->head->next;
inQueue->emptyHead->next=inQueue->head;
return tmpQueue;
}
void enQueue(pQueue inQueue,PtrQueueType inNode)
{
if(inQueue==NULL||inNode==NULL)
{
printf("in enQueue,inQueue is null\n");
return ;
}
if(inQueue->rear==NULL&&inQueue->head==NULL)
//first node to be created.
{
inQueue->rear=(PtrQueueType)malloc(sizeof(QueueDataType));
inQueue->rear=inNode;
inQueue->head=inQueue->rear;
inQueue->emptyHead->next=inQueue->head;
}
else
{
/*Correction : use the rear->next for the new enqueue's pos*/
inQueue->rear->next=(PtrQueueType)malloc(sizeof(QueueDataType));
inQueue->rear->next=inNode;
inQueue->rear=inQueue->rear->next;
inQueue->rear->next=NULL;
}
}
/*attention :this insert algorithm has effects only on the queue with an empty head*/
void insert(pQueue inQueue,PtrQueueType inNode)
{
PtrQueueType p;
if(inQueue==NULL||inNode==NULL)
{
printf("in insert,inQueue is null\n");
return ;
}
p=inQueue->emptyHead;
while(p->next!=NULL&&p->next->priorityNum<=inNode->priorityNum)
p=p->next;
/*maybe will have errors when stop at p->next==null*/
if(p==inQueue->emptyHead)/*Correction Adjust to the head*/
{
inNode->next=p->next;
p->next=inNode;
inQueue->head=inNode;
}
else
{
inNode->next=p->next;
p->next=inNode;
}
//Correction: To Adjust the rear
while(p->next!=NULL)
p=p->next;
inQueue->rear=p;
}
3.2.4主摸拟算法实现过程:采用从外部文件读入参数的方法当mode值为0时,则表示从外部文件设定相关的进程信息.
#include <windows.h>
#include <stdio.h>
#include <time.h>
#include "Ulti.h"
#include "PCB.h"
#include "EQueue.h"
#define DEBUG 1
char *inFileName="inputData.txt";
char *outFileName="outputData.txt";
int main(int argc,char* argv[])
{
/*--------Open file--------*/
FILE* inputFile;
FILE* outputFile;
int bDelay;
/*=--------creation part-------*/
char mode;
int numOfThread;
PCBList pcbList,p;
ptrPCBNode tmpNode;
/*--------main process-------*/
pQueue readyQueue,endQueue;
ptrProcess runProcess,tmpProcess;
int count;
if((inputFile=fopen(inFileName,"rb"))==NULL)
{
printf("open inputFile error\n");
return -1;
}
if((outputFile=fopen(outFileName,"wb"))==NULL)
{
printf("open outputFile error\n");
return -1;
}
printf("oepn files success \n");
/*Create the PCB Table*/
/*create a pcbList with a null head.*/
pcbList=(ptrPCBNode)malloc(sizeof(struct PCBNode));
p=pcbList;
fscanf(inputFile,"mode=%c\r\n",&mode);
fscanf(inputFile,"numOfThread=%d\r\n",&numOfThread);
fscanf(inputFile,"delay=%d\r\n",&bDelay);
printf("------------program init starts------------\n");
fprintf(outputFile,"------------program init starts------------\r\n");
if(mode=='0')/*Read process definition from the file*/
{
/*Creation with input list*/
int i;
for(i=0;i<numOfThread;i++)
{
tmpNode=(ptrPCBNode)malloc(sizeof(struct PCBNode));
fscanf(inputFile,"%d,%d,%s\r\n",&tmpNode->priorityNum,&tmpNode->remainSecs,tmpNode->processName);
tmpNode->processName[strlen(tmpNode->processName)]='\0';
tmpNode->processID=i;
tmpNode->staturs=STA_READY;
if(tmpNode->remainSecs>0)
{
p->next=tmpNode;
p=p->next;
printf("ProcessID:%d,Name:%s,Priority:%d,RemainSecs:%d Staturs: Ready\n",tmpNode->processID,tmpNode->processName,tmpNode->priorityNum,tmpNode->remainSecs);
fprintf(outputFile,"ProcessID:%d,Name:%s,Priority:%d,RemainSecs:%d Staturs: Ready\r\n",tmpNode->processID,tmpNode->processName,tmpNode->priorityNum,tmpNode->remainSecs);
}
}
p->next=NULL;//Correction: add this to has effects in sort algorithm
}
else if(mode=='1')
{
int i;
srand((unsigned int)time (NULL));
for(i=0;i<numOfThread;i++)
{
tmpNode=(ptrPCBNode)malloc(sizeof(struct PCBNode)); tmpNode->priorityNum=(int)eRandom(10);
tmpNode->remainSecs=(int)eRandom(10);
tmpNode->processID=i;
strcpy(tmpNode->processName,"Process");
tmpNode->processName[7]=48+i;
tmpNode->processName[8]='\0';
tmpNode->staturs=STA_READY;
if(tmpNode->remainSecs>0)
{
p->next=tmpNode;
p=p->next;
printf("ProcessID:%d,Name:%s,Priority:%d,RemainSecs:%d Staturs: Ready\n",tmpNode->processID,tmpNode->processName,tmpNode->priorityNum,tmpNode->remainSecs);
fprintf(outputFile,"ProcessID:%d,Name:%s,Priority:%d,RemainSecs:%d Staturs: Ready\r\n",tmpNode->processID,tmpNode->processName,tmpNode->priorityNum,tmpNode->remainSecs);
}
}
p->next=NULL;//Correction: add this to has effects in sort algorithm
}
else
{
printf("mode is illegal!\n");
return -1;
}
printf("------------program init ends------------\n");
fprintf(outputFile,"------------program init ends------------\r\n");
/*Sort the pcb table*/
sortPCB(pcbList); //8:56 test ok
if(DEBUG)printf("sortPCB successfully\n");
/*init queue*/
endQueue=createNullQueueWithHead();
readyQueue=createNullQueueWithHead();
tmpNode=pcbList;
tmpNode=tmpNode->next;
while(tmpNode!=NULL) //9:38 test ok
{
tmpProcess=(ptrProcess)malloc(sizeof(struct Process));
tmpProcess->processID=tmpNode->processID;
tmpProcess->staturs=tmpNode->staturs;
tmpProcess->priorityNum=tmpNode->priorityNum;
tmpProcess->remainSecs=tmpNode->remainSecs;
strcpy(tmpProcess->processName,tmpNode->processName);
enQueue(readyQueue,tmpProcess);
tmpNode=tmpNode->next;
}
if(DEBUG)printf("create readyQueue successfully\n");
runProcess=NULL;
/*The core of process management*/
printf("------------start of main simulation program------------\n");
fprintf(outputFile,"------------start of main simulation program------------\r\n");
count=0;
while(!isEmpty(readyQueue)||runProcess!=NULL)
{
if(bDelay)
eDelay(1000);/*DELAY 1 SECS*/
if(runProcess!=NULL)
{
count++;
printf("Line:%d ProcessID:%d,Name:%s,Priority:%d,RemainSecs:%d Staturs: Running\n",count,runProcess->processID,runProcess->processName,runProcess->priorityNum,runProcess->remainSecs);
fprintf(outputFile,"Line:%d ProcessID:%d,Name:%s,Priority:%d,RemainSecs:%d Staturs: Running\r\n",count,runProcess->processID,runProcess->processName,runProcess->priorityNum,runProcess->remainSecs);
runProcess->priorityNum++;
runProcess->remainSecs--;
if(runProcess->remainSecs==0)/*if time use out,end the process*/
{
runProcess->staturs=STA_END;
enQueue(endQueue,runProcess);
updatePCBList(pcbList,runProcess);
count++;
printf("Line:%d ProcessID:%d,Name:%s,Priority:%d,RemainSecs:%d Staturs: Ends\n",count,runProcess->processID,runProcess->processName,runProcess->priorityNum,runProcess->remainSecs);
fprintf(outputFile,"Line:%d ProcessID:%d,Name:%s,Priority:%d,RemainSecs:%d Staturs: Ends\r\n",count,runProcess->processID,runProcess->processName,runProcess->priorityNum,runProcess->remainSecs);
}
else if(!isEmpty(readyQueue))
{
runProcess->staturs=STA_READY;
insert(readyQueue,runProcess);
updatePCBList(pcbList,runProcess);
}
}
/*apply new mem for the new node*/
//Correction:runProcess!=NULL should be placed at front
if(runProcess!=NULL&&runProcess->remainSecs==0)//for the last thread consult.&& runProcess!=firstNode(NULL)
runProcess=NULL;
if(!isEmpty(readyQueue))
{
runProcess=(ptrProcess)malloc(sizeof(struct Process));
/*wake up a new thread*/
runProcess=deQueue(readyQueue);
runProcess->staturs=STA_RUN;
updatePCBList(pcbList,runProcess);
}
}//10:03 test ok
printf("------------end of main simulation program------------\n");
fprintf(outputFile,"------------end of main simulation program------------\r\n");
fclose(inputFile);
fclose(outputFile);
printf("program ends successfully\n");
getchar();
return 0;
}
3.3实验改进:
考虑到实验的数据输出量较大，如果直接观察不是十分方便，所以考虑采用图形的方式来演示这一算法过程.
采用Windows SDK编程中所提供的API函数及根据图形学原理编写的直线算法进行绘制.
具体实现不再详述，主要的工作就是在原来文本输出的位置改以以图形进行演示的方法.
3.4实验结果:
3.4.1给出一组由随机方生成初始进程状态值后调度运行的结果:
------------program init starts------------
ProcessID:0,Name:Process0,Priority:8,RemainSecs:8 Staturs: Ready
ProcessID:1,Name:Process1,Priority:0,RemainSecs:4 Staturs: Ready
ProcessID:2,Name:Process2,Priority:1,RemainSecs:8 Staturs: Ready
ProcessID:3,Name:Process3,Priority:3,RemainSecs:6 Staturs: Ready
ProcessID:4,Name:Process4,Priority:5,RemainSecs:4 Staturs: Ready
------------program init ends------------
------------start of main simulation program------------
Line:1 ProcessID:1,Name:Process1,Priority:0,RemainSecs:4 Staturs: Running
Line:2 ProcessID:2,Name:Process2,Priority:1,RemainSecs:8 Staturs: Running
Line:3 ProcessID:1,Name:Process1,Priority:1,RemainSecs:3 Staturs: Running
Line:4 ProcessID:2,Name:Process2,Priority:2,RemainSecs:7 Staturs: Running
Line:5 ProcessID:1,Name:Process1,Priority:2,RemainSecs:2 Staturs: Running
Line:6 ProcessID:3,Name:Process3,Priority:3,RemainSecs:6 Staturs: Running
Line:7 ProcessID:2,Name:Process2,Priority:3,RemainSecs:6 Staturs: Running
Line:8 ProcessID:1,Name:Process1,Priority:3,RemainSecs:1 Staturs: Running
Line:9 ProcessID:1,Name:Process1,Priority:4,RemainSecs:0 Staturs: Ends
Line:10 ProcessID:3,Name:Process3,Priority:4,RemainSecs:5 Staturs: Running
Line:11 ProcessID:2,Name:Process2,Priority:4,RemainSecs:5 Staturs: Running
Line:12 ProcessID:4,Name:Process4,Priority:5,RemainSecs:4 Staturs: Running
Line:13 ProcessID:3,Name:Process3,Priority:5,RemainSecs:4 Staturs: Running
Line:14 ProcessID:2,Name:Process2,Priority:5,RemainSecs:4 Staturs: Running
Line:15 ProcessID:4,Name:Process4,Priority:6,RemainSecs:3 Staturs: Running
Line:16 ProcessID:3,Name:Process3,Priority:6,RemainSecs:3 Staturs: Running
Line:17 ProcessID:2,Name:Process2,Priority:6,RemainSecs:3 Staturs: Running
Line:18 ProcessID:4,Name:Process4,Priority:7,RemainSecs:2 Staturs: Running
Line:19 ProcessID:3,Name:Process3,Priority:7,RemainSecs:2 Staturs: Running
Line:20 ProcessID:2,Name:Process2,Priority:7,RemainSecs:2 Staturs: Running
Line:21 ProcessID:0,Name:Process0,Priority:8,RemainSecs:8 Staturs: Running
Line:22 ProcessID:4,Name:Process4,Priority:8,RemainSecs:1 Staturs: Running
Line:23 ProcessID:4,Name:Process4,Priority:9,RemainSecs:0 Staturs: Ends
Line:24 ProcessID:3,Name:Process3,Priority:8,RemainSecs:1 Staturs: Running
Line:25 ProcessID:3,Name:Process3,Priority:9,RemainSecs:0 Staturs: Ends
Line:26 ProcessID:2,Name:Process2,Priority:8,RemainSecs:1 Staturs: Running
Line:27 ProcessID:2,Name:Process2,Priority:9,RemainSecs:0 Staturs: Ends
Line:28 ProcessID:0,Name:Process0,Priority:9,RemainSecs:7 Staturs: Running
Line:29 ProcessID:0,Name:Process0,Priority:10,RemainSecs:6 Staturs: Running
Line:30 ProcessID:0,Name:Process0,Priority:11,RemainSecs:5 Staturs: Running
Line:31 ProcessID:0,Name:Process0,Priority:12,RemainSecs:4 Staturs: Running
Line:32 ProcessID:0,Name:Process0,Priority:13,RemainSecs:3 Staturs: Running
Line:33 ProcessID:0,Name:Process0,Priority:14,RemainSecs:2 Staturs: Running
Line:34 ProcessID:0,Name:Process0,Priority:15,RemainSecs:1 Staturs: Running
Line:35 ProcessID:0,Name:Process0,Priority:16,RemainSecs:0 Staturs: Ends
------------end of main simulation program------------
3．4．2给出一组在指定进程初始状态的条件下摸拟程序进行的图形演示结果:
其中的Pri 及SevTime列分别表示初始时各进程的优先数及剩余运行时间.
可以看到，运行的结果完全符合动态优先数调度算法.
4．实验过程中出现的问题及解决方法。
4.1由于对摸拟程序的核心数据结构---基于“链表结构的带头结点的队列”的一些其本运算法在初期考虑时欠妥，导致后期耗费大量时间在调试上，这是非常不值得的。应继续加强在动手写程序前把难点及核心算法想清，想准的能力.
4．2发现了C语言在应用中的一些比较容易忽略，却极易导致程序出错的地方。
如while(p->next->next!=NULL&&p->next!=NULL)在使用中当p->next已为NULL时，则p->next->next将被视为”invalidate asscess.”
改成while(p->next!=NULL&&p->next->next!=NULL)就消除了这一隐患.
5．实验体会。
通过这个实验，加强了我对操作系统中进程调度原理的理解，同时在稍大程
序的的整体的编制能力上再一次得到的加强.
参考资料:
[1]何炎祥,李飞,李宁,计算机操作系统,清华大学出版社,2002.
完成日:06/01/07
本文最佳浏览定位:
http://www.emilmatthew.zk.cn/EmilPapers/06_2proMag/index.htm
算法测试程序下载:
代码1:进程模拟调度程序:
http://emilmatthew.51.net/EmilPapers/06_2proMag/Code1.rar
代码2:图形版本的调度程序:
http://emilmatthew.51.net/EmilPapers/06_2proMag/Code2.rar
若直接点击无法下载，请将下载的超链接粘接至浏览器地址栏后按回车.若不出意外，此时应能下载.
