实验一处理机调度
一、实验内容
选择一个调度算法，实现处理机调度。
二、实验目的
多道系统中，当就绪进程数大于处理机数时，须按照某种策略决定哪些进程优先占用处理机。本实验模拟实现处理机调度，以加深了解处理机调度的工作。
三、实验题目
1、设计一个按优先权调度算法实现处理机调度的程序；
2、设计按时间片轮转实现处理机调度的程序。
PCB内容要求 ：
进程名/PID；
要求运行时间（单位时间）；
优先权；
状态：
PCB指针；
1、可随机输入若干进程，并按优先权排序；
2、从就绪队首选进程运行：优先权-1
要求运行时间-1
要求运行时间=0时，撤销该进程
3、重新排序，进行下轮调度；
源代码：
#include
#include
#include
#include
typedef struct pcb
{
char PID[50];
int needTime;//需要运行时间
int priority;//优先权
char state[20];//进程状态
struct pcb *next;
}PCB;
typedef struct
{
PCB* front;
PCB* rear;
}ProcessQueue;
void SelectAlgorithm();
void CreateQProcess(ProcessQueue &Q,char*,int time,int pri,char*);
void ProcessSchedule();
void InitQueue(ProcessQueue &Q);
void visitQueue(ProcessQueue &Q);
bool RunProcess(PCB* rp,ProcessQueue &Q);
bool NonPreemptivePriority(ProcessQueue &Q);//非抢占式优先权调度
void delProcess(PCB* delp);
bool RunProcessPreem(PCB* rp,ProcessQueue &Q);//抢占式优先执行进程
bool PreemptivePriority(ProcessQueue &Q);
void RR(ProcessQueue &Q);
int main()
{
int iSel;
int i = 0;
SelectAlgorithm();
ProcessQueue readyQ;//就绪进程队列
PCB newpcb;
InitQueue(readyQ);
printf("请选择调度算法：");
do
{
scanf("%d",&iSel);
} while (!(iSel == 1 || iSel == 2 || iSel == 3));
while(i ＜ 3)
{
printf("请输入要创建的进程:\n");
fflush(stdin);
gets(newpcb.PID);fflush(stdin);
scanf("%d",&newpcb.needTime);fflush(stdin);
scanf("%d",&newpcb.priority);fflush(stdin);
gets(newpcb.state);fflush(stdin);
CreateQProcess(readyQ,newpcb.PID,newpcb.needTime,newpcb.priority,newpcb.state);
printf("创建了一个进程\n");
++i;
}
visitQueue(readyQ);//显示的是各个进程的优先权
switch(iSel)
{
case 1:
while(NonPreemptivePriority(readyQ));//非抢占优先权调度
break;
case 2:
PreemptivePriority(readyQ);//抢占式优先权调度
break;
case 3:
RR(readyQ);
break;
}
return 0;
}
void SelectAlgorithm()
{
printf("1.非抢占式优先权调度\n");
printf("2.抢占式优先权调度\n");
printf("3.时间片轮转调度\n");
}
void InitQueue(ProcessQueue &Q)//初始化进程队列
{
Q.front = Q.rear = (PCB*)malloc(sizeof(PCB));
if(!Q.front) exit(-1);
Q.front-＞next = NULL;
}
void CreateQProcess(ProcessQueue &Q,char* pid,int time,int pri,char* st)//指定进程入就绪队列，将优先权高的插在队列前面
{
PCB* p = (PCB*)malloc(sizeof(PCB));
if(!p) exit(-1);
strcpy(p-＞PID,pid); p-＞needTime = time;
p-＞priority = pri; strcpy(p-＞state,st);
p-＞next = NULL;
PCB* q = Q.front-＞next, *old = Q.front;
if(!q)//如果原队列为空
{
Q.rear-＞next = p;
Q.rear = p;//q == NULL
}
else//如果原队列不为空
{
for(;q != NULL;)
{
if(p-＞priority ＞ q-＞priority)
{
old-＞next = p;
p-＞next = q;
return;
}
q = q-＞next;
old = old-＞next;
if(q == NULL)
{
Q.rear-＞next = p;
Q.rear = q;//q == NULL
}
}
}
}
void ProcessSchedule()
{
}
void visitQueue(ProcessQueue &Q)//访问进程队列
{
PCB* p = (PCB*)malloc(sizeof(PCB));
if(!p) exit(-1);
p = Q.front-＞next;
while(p != NULL)
{
printf("%d,",p-＞priority);
p = p-＞next;
}
printf("\n");
int i = 0;
}
bool PreemptivePriority(ProcessQueue &Q)
{
PCB* rprocess;
if(!Q.front-＞next)
{
printf("就绪队列中没有进程可以调度！\n");
return false;
}
else
{
rprocess = Q.front-＞next;//选择优先权最高的进程
Q.front-＞next = Q.front-＞next-＞next;//将进程移除就绪队列
while(rprocess != NULL)//抢占式优先调度
{
RunProcessPreem(rprocess,Q);
if(rprocess-＞needTime == 0)
{
delProcess(rprocess);
if((rprocess = Q.front-＞next) == NULL)
{
printf("就绪队列中没有进程可以调度！\n");
return false;
}
else
{
Q.front-＞next = Q.front-＞next-＞next;
continue;
}
}
if(Q.front-＞next != NULL)
{
if(rprocess-＞priority ＜ Q.front-＞next-＞priority)//判断运行了1个时间后还是否具有最高优先权
{
/*rprocess-＞next = Q.front-＞next-＞next;//正在运行中的进程因为优先权降低，重新进入就绪队列
temp = Q.front-＞next;
Q.front-＞next = rprocess;
rprocess = temp;//rprocess保存运行进程*/
CreateQProcess(Q,rprocess-＞PID,rprocess-＞needTime,rprocess-＞priority,rprocess-＞state);//正在运行中的进程因为优先权降低，重新进入就绪队列
rprocess = Q.front-＞next;
Q.front-＞next = Q.front-＞next-＞next;
}
}
}
}
return true;
}
bool NonPreemptivePriority(ProcessQueue &Q)//非抢占式优先权调度
{
PCB* rprocess;//存放要调度运行的进程
if(!Q.front-＞next)
{
printf("就绪队列中没有进程可以调度！\n");
return false;
}
else
{
rprocess = Q.front-＞next;
Q.front-＞next = Q.front-＞next-＞next;//已经调度，从就绪队列中删除进程
if(RunProcess(rprocess,Q))
{
delProcess(rprocess);
printf("就绪队列状态:\n");
visitQueue(Q);
}
return true;
}
}
bool RunProcess(PCB* rp,ProcessQueue &Q)//执行进程
{
while(rp-＞needTime)
{
printf("进程%s正在运行...\n",rp-＞PID);
printf("PID[50]\tneedTime\tpriority\tstate[20]\n");
printf("%s\t%d\t\t%d\t\t%s\n",rp-＞PID,rp-＞needTime,rp-＞priority,rp-＞state);
Sleep(1000);
--rp-＞needTime;
}
return true;
}
bool RunProcessPreem(PCB* rp,ProcessQueue &Q)//抢占式优先,RR执行进程
{
printf("进程%s正在运行...\n",rp-＞PID);
printf("PID[50]\tneedTime\tpriority\tstate[20]\n");
printf("%s\t%d\t\t%d\t\t%s\n",rp-＞PID,rp-＞needTime,rp-＞priority,rp-＞state);
Sleep(1000);
--rp-＞needTime;
--rp-＞priority;
return true;
}
void delProcess(PCB* delp)//撤销进程
{
free(delp);
}
void RR(ProcessQueue &Q)
{
PCB* running = Q.front-＞next;
PCB* old = Q.front;
while(Q.front-＞next != NULL)
{
if(running)
{
RunProcessPreem(running,Q);
if(running-＞needTime == 0)//撤销进程
{
old-＞next = running-＞next;
delProcess(running);
running = old-＞next;
continue;
}
old = old-＞next;
running = running-＞next;
}
else
{
old = Q.front;
running = old-＞next;
}
}
printf("就绪队列中没有进程可以调度！\n");
}
以下是使用时间片轮转算法的一次执行：
选择算法3：
进程输入，此处输入1，1，1，1，2，2，2，2，3，3，3，3测试。
下面是时间片轮转法的调度结果：
由于水平太菜了，写出来的上述代码可以大大优化，而且很多功能没有实现，例如进程没有设置挂起状态。运行时不能输入进程，只能在一开始创建进程，没有添加后背队列。只是粗略模拟了三种处理机调度算法。
二〇##年十二月十五日星期三 1:28:25 AM