选择一个调度算法,实现处理器调度。
一、实验目的
在采用多道程序设计的系统中,往往有若干个进程同时处于就绪状态。当就绪状态进程个数大于处理器数时,就必须依照某种策略来决定哪些进程优先占用处理器。本实验模拟在单处理器情况下处理器调度,帮助自己加深了解处理器调度的工作。
二、实验题目
选择一个调度算法,实现处理器调度。
三、背景材料
(一)设计一个按优先数调度算法实现处理器调度的程序
[提示]:
1、 假定系统有五个进程,每一个进程用一个进程控制块PCB来代表,进程控制块的格式为:
进程名
指针
要求运行时间
优先数
状态
进程名——作为进程的标识,假设五个进程的进程名分别为P1,P2,P3,P4,P5。
指针——按优先数的大小把五个进程连成队列,用指针指出下一个进程的进程控制块的首地址,最后一个进程中的指针为“0”。
要求运行时间——假设进程需要运行的单位时间数。
优先数——赋予进程的优先数,调度时总是选取优先数大的进程先执行。
状态——可假设有两种状态,“就绪”状态和“结束”状态。五个进程的初始状态都为“就绪”,用“R”表示,当一个进程运行结束后,它的状态为“结束”,用“E”表示。
2、在每次运行你所设计的处理器调度程序之前,为每个进程任意确定它的“优先数”和“要求运行时间”。本实验由于为了检查的方便,优先数和运行时间采用下表中的数值。
3、为了调度方便,把五个进程按给定的优先数从大到小连成队列。用一单元指出队首进程,用指针指出队列的连接情况。例如:
队首标志
K2
K1
P1
K2
P2
K3
P3
K4
P4
K5
P5
0
K4
K5
K3
K1
2
3
1
2
4
1
5
3
4
2
R
R
R
R
R
PCB1
PCB2
PCB3
PCB4
PCB5
4、处理器调度总是选队首进程运行。采用动态改变优先数的办法,进程每运行一次优先数就减“1”。由于本实验是模拟处理器调度,所以,对被选中的进程并不实际的启动运行,而是执行:
优先数-1
要求运行时间-1
来模拟进程的一次运行。
提醒注意的是:在实际的系统中,当一个进程被选中运行时,必须恢复进程的现场,让它占有处理器运行,直到出现等待事件或运行结束。在这里省去了这些工作。
5、进程运行一次后,若要求运行时间¹0,则再将它加入队列(按优先数大小插入,且置队首标志);若要求运行时间=0,则把它的状态修改成“结束”(E),且退出队列。
6、 若“就绪”状态的进程队列不为空,则重复上面(4)和(5)的步骤,直到所有进程都成为“结束”状态。
7、 在所设计的程序中应有显示或打印语句,能显示或打印每次被选中进程的进程名以及运行一次后进程队列的变化。
可以为五个进程任意确定一组“优先数”和“要求运行时间”,启动所设计的处理器调度程序,显示或打印逐次被选中进程的进程名以及进程控制块的动态变化过程。
#include
#include
using namespace std;
//-----------------------
struct _proc
{
char name[32];
struct _proc *next;
int run_time;
int priority;
int state;//就绪为
};
_proc *root;
//向就绪队列中插入进程,按照降序
void Insert(_proc* pr)
{
_proc *q=root;//方便插入,MATCH_
word
word文档格式规范word作业纸小票打印word模板word简历模板免费word简历
_1714148416501_0插入位置的前面的进程
_proc *p=root->next;
if(root->state!=0)
{
while(p!=NULL)//找插入位置
{
if(p->priority>pr->priority)//优先级小于时,继续遍历
{
q=p;
p=p->next;
}
else//找到插入
{
break;
}
}
}
pr->next=p;//插入
q->next=pr;
++root->state;//进程个数加一
}
//创建进程
_proc Creat(char name[],int priority,int run_time)
{
_proc pr;
strcpy(pr.name,name);
pr.priority=priority;
pr.run_time=run_time;
pr.state=0;
pr.next=NULL;
return pr;
}
//删除就绪队列中对首进程
_proc* Delete()
{
_proc* pr=root->next;
root->next=root->next->next;
--root->state;
return pr;
}
//对就绪队列排序,按照降序
void Sort()
{
if(root->next->run_time==0)//要执行时间为时,从就绪队列中删除该进程
{
Delete();
root->next->state=1;
}
else//不为时,先删除,再根据变化后的优先级,插入到相应位置
{
_proc *pr=Delete();
Insert(pr);
}
}
//输出执行进程号
void OutPut()
{
cout<next->name<next->priority;//修改进程的优先级和运行时间,状态
--root->next->run_time;
}
void Solve()
{
//根结点
root=new _proc;
root->state=0;//state记录就绪队列中的进程个数
root->next=NULL;//指向第一个进程
//创建几个进程,并插入就绪队列
_proc pr1=Creat("p1",2,1);
Insert(&pr1);
_proc pr2=Creat("p2",3,5);
Insert(&pr2);
_proc pr3=Creat("p3",1,3);
Insert(&pr3);
_proc pr4=Creat("p4",2,4);
Insert(&pr4);
_proc pr5=Creat("p5",4,2);
Insert(&pr5);
cout<<"调度序列:"<state!=0)
{
OutPut();
Sort();
}
}
int main()
{
Solve();
getchar();
getchar();
return 0;
}
(二)设计一个按时间片轮转法实现处理器调度的程序。
1、 假定系统有五个进程,每一个进程用一个进程控制块PCB来代表。进程控制块的格式为:
进程名
指针
要求运行时间
已运行时间
状态
进程名——作为进程的标识,假设五个进程的进程名分别为Q1,Q2,Q3,Q4,Q5。
指针——进程按顺序排成循环队列,用指针指出下一个进程的进程控制块的首地址,最后一个进程的指针指出第一个进程的进程控制块首地址。
要求运行时间——假设进程需要运行的单位时间数。
已运行时间——假设进程已经运行的单位时间数,初始值为“0”。
状态——有两种状态,“就绪”和“结束”,初始状态都为“就绪”,用“R”表示。当一个进程运行结束后,它的状态为“结束”,用“E”表示。
2、 每次运行所设计的处理器调度程序前,为每个进程任意确定它的“要求运行时间”。
3、把五个进程按顺序排成循环队列,用指针指出队列连接情况。另用一标志单元记录轮到运行的进程。例如,当前轮到P2执行,则有:
标志单元
K2
K1
Q1
K2
Q2
K3
Q3
K4
Q4
K5
Q5
K2
K3
K4
K5
K1
2
3
1
2
4
1
0
0
0
0
R
R
R
R
R
PCB1
PCB2
PCB3
PCB4
PCB5
4、处理器调度总是选择标志单元指示的进程运行。由于本实验是模拟处理器调度的功能,所以,对被选中的进程并不实际的启动运行,而是执行:
已运行时间+1
来模拟进程的一次运行,表示进程已经运行过一个单位的时间。
请同学注意:在实际的系统中,当一个进程被选中运行时,必须置上该进程可以运行的时间片值,以及恢复进程的现场,让它占有处理器运行,直到出现等待事件或运行满一个时间片。在这时省去了这些工作,仅用“已运行时间+1”来表示进程已经运行满一个时间片。
5、进程运行一次后,应把该进程的进程控制块中的指针值送到标志单元,以指示下一个轮到运行的进程。同时,应判断该进程的要求运行时间与已运行时间,若该进程的要求运行时间¹已运行时间,则表示它尚未执行结束,应待到下一轮时再运行。若该进程的要求运行时间=已运行时间,则表示它已经执行结束,应指导它的状态修改成“结束”(E)且退出队列。此时,应把该进程的进程控制块中的指针值送到前面一个进程的指针位置。
6、若“就绪”状态的进程队列不为空,则重复上面的4和5的步骤,直到所有的进程都成为“结束”状态。
7、在所设计的程序中应有显示或打印语句,能显示或打印每次选中进程的进程名以及运行一次后进程队列的变化。
可以为五个进程任意确定一组“要求运行时间”,启动所设计的处理器调度程序,显示或打印逐次被选中的进程名以及进程控制块的动态变化过程。
#include
#include
using namespace std;
//-----------------------
struct _proc
{
char name[32];
struct _proc *next;
int run_time;
int alloc_time;
int state;//就绪为
};
_proc *root;
//向就绪队列中插入进程,按照降序
void Insert(_proc* pr)
{
if(root->next==NULL)
{
root=pr;
pr->next=pr;
return;
}
pr->next=root->next;//插入
root->next=pr;
root=pr;
}
//创建进程
_proc Creat(char name[],int run_time,int alloc_time)
{
_proc pr;
strcpy(pr.name,name);
pr.run_time=run_time;
pr.alloc_time=alloc_time;
pr.state=0;
pr.next=NULL;
return pr;
}
//删除就绪队列中对首进程
void Delete()
{
if(root->next==root)
{
root=NULL;
return;
}
root->next=root->next->next;
}
//输出进程号,模拟进程执行
void OutPut()
{
cout<next->name<next->alloc_time;//修改进程
}
void Solve()
{
//根结点
root=new _proc;
root->state=0;//state记录就绪队列中的进程个数
root->next=NULL;//空循环链表,指向自身
//创建几个进程,并插入就绪队列
_proc pr1=Creat("Q1",2,1);
Insert(&pr1);
_proc pr2=Creat("Q2",3,0);
Insert(&pr2);
_proc pr3=Creat("Q3",1,0);
Insert(&pr3);
_proc pr4=Creat("Q4",2,0);
Insert(&pr4);
_proc pr5=Creat("Q5",4,0);
Insert(&pr5);
cout<<"调度序列:"<next->alloc_time==root->next->run_time)//执行完毕
{
Delete();//从就绪队列中,删除该进程
continue;
}
root=root->next;//root指针后移,执行下一个进程做准备
}
}
int main()
{
Solve();
getchar();
getchar();
return 0;
}
四、实验
内容
财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容
1、设计一个按背景材料中指定优先数的优先数调度算法实现处理器调度的程序
2、设计一个按时间片轮转法实现处理器调度的程序。
#include "stdio.h"
#include
#include
#define getpch(type) (type*)malloc(sizeof(type))
#define NULL 0
struct pcb { /* 定义进程控制块PCB */
char name[10];
char state;
int super;
int ntime;
int rtime;
struct pcb* link;
}*ready=NULL,*p;
typedef struct pcb PCB;
sort() /* 建立对进程进行优先级排列函数*/
{
PCB *first, *second;
int insert=0;
if(ready==NULL)
{
p->link=ready;
ready=p;
}
else /* 进程比较优先级,插入适当的位置中*/
{
first=ready;
second=first->link;
while(second!=NULL)
{
first=first->link;
second=second->link;/*插尾*/
}
if(insert==0) first->link=p;
}
}
input() /* 建立进程控制块函数*/
{
int i,num;
system("cls"); /*清屏*/
printf("\n 请输入进程号?");
scanf("%d",&num);
for(i=0;iname);
printf("\n 输入进程运行时间:");
scanf("%d",&p->ntime);
printf("\n");
p->rtime=0;p->state='w';
p->link=NULL;
sort(); /* 调用sort函数*/
}
}
int space()
{
int l=0; PCB* pr=ready;
while(pr!=NULL)
{
l++;
pr=pr->link;
}
return(l);
}
disp(PCB * pr) /*建立进程显示函数,用于显示当前进程*/
{
printf("\n qname \t state \t super \t ndtime \t runtime \n");
printf("|%s\t",pr->name);
printf("|%c\t",pr->state);
printf("|%d\t",pr->super);
printf("|%d\t",pr->ntime);
printf("|%d\t",pr->rtime);
printf("\n");
}
check() /* 建立进程查看函数 */
{
PCB* pr;
printf("\n **** 当前正在运行的进程是:%s",p->name); /*显示当前运行进程*/
disp(p);
pr=ready;
printf("\n ****当前就绪队列状态为:\n"); /*显示就绪队列状态*/
while(pr!=NULL)
{
disp(pr);
pr=pr->link;
}
}
destroy() /*建立进程撤消函数(进程运行结束,撤消进程)*/
{
printf("\n 进程 [%s] 已完成.\n",p->name);
free(p);
}
running() /* 建立进程就绪函数(进程运行时间到,置就绪状态*/
{
(p->rtime)++;
if(p->rtime==p->ntime)
destroy(); /* 调用destroy函数*/
else
{
p->state='w';
sort(); /*调用sort函数*/
}
}
main() /*主函数*/
{
int len,h=0;
char ch;
input();
len=space();
while((len!=0)&&(ready!=NULL))
{
ch=getchar();
h++;
printf("\n The execute number:%d \n",h);
p=ready;
ready=p->link;
p->link=NULL;
p->state='R';
check();
running();
printf("\n 按任一键继续......");
ch=getchar();
}
printf("\n\n 进程已经完成.\n");
ch=getchar();
}