静态优先级调度算法.docx
《静态优先级调度算法.docx》由会员分享，可在线阅读，更多相关《静态优先级调度算法.docx（18页珍藏版）》请在冰点文库上搜索。
静态优先级调度算法
__成绩（五级制）：
________
武汉科技大学城市学院
《操作系统》实验报告
院系武汉科技的大学城市学院
学生专业＿信科＿＿＿＿＿＿＿＿
年级班＿大三＿＿＿＿＿＿＿＿
课程名称＿操作系统＿
实验题目＿进程调度＿＿＿＿＿＿＿＿
学生姓名＿＿宋骋＿＿＿＿＿＿＿
指导教师＿＿郭冀生＿＿＿＿
2013年11月4日
实验二进程调度
一、实验目的
进程是操作系统最重要的概念之一，进程调度又是操作系统核心的重要内容。
通过该实验，要求同学们了解各进程在执行过程中的状态和参数的变化情况，以便于观察诸进程的调度过程。
二、实验内容及要求
按剥夺式优先数法对三个进程P1,p2,p3进行模拟调度，各进程的优先数静态设置，其中P1的优先数最高，P3的优先数最低。
每个进程都处于执行E（execute）,就绪R（ready）和等待W（wait）三种状态之一，并假定初始状态均为R.。
三个进程有如下同步关系：
P1因等待事件1被阻塞后由P2发现并唤醒之，P2因等待事件2被阻塞后由P3发现并唤醒之。
当系统进入运行，在完成必要的初始化工作以后便进入进程调度，首先选择优先数最高的进程使其进入执行（分配CPU）。
当执行进程因等待某个事件被阻塞或唤醒某个等待进程时，转入进程调度。
如果被唤醒的进程的优先数大于现行的执行进程，则剥夺现行进程的执行权，而将CPU分配给被唤醒的进程。
当系统处于死锁或三个进程都执行完毕时系统退出运行。
系统中应用到如下数据结构：
*进程控制块PCB；
*信号量sem；
*其它需要的数据结构。
由自己设计。
三、实验原理及步骤
根据现代操作系统的特征
1．并发性（concurrence）；
2．共享性（sharing）；
3．虚拟性（virtual）；
4．异步性（asynchronism）。
模拟出进程在执行中的状态变化过程；
体会进程申请资源、使用资源、归还资源；
体会死锁。
步骤（参考框图）
4、算法和流程图
可强占优先调度算法实现过程流程图（如下图）：
四、程序运行
1选择输入执行程序（如下图）
2可强占优先调度算法图（如下图）
五.设计总结：
通过该课程设计，加深了对系统进程调度机制的理解。
在抢占方式中实践了“抢占”必须遵循的原则：
优先权原则。
认识了几种进程调度算法的优缺点以及应用范围。
加强C++的编程能力，实现类的封
装。
附录：
程序及注释（用红色黑体标注自己设计的函数）
//进程PCB类和模拟cpu的进程类的声明
#include
#include
#include
#include
#include
#include
#include
#include
#include
#defineMAX_PHILOSOPHERS3//待测试的哲学家数
#defineZERO48//数字0的ASCII码
#defineDELAYrand（）%25
structPCB
{
charp_name[20];
intp_priority;
intp_needTime;
intp_runTime;
charp_state;
chardeadlock（）;
structPCB*next;
};
voidHighPriority（）;
voiddeadlock（）;
voidInformation（）;//形参的改变映射给实参说白了就是实参传过去不用return返回就可以把实参改变
charChoice（）;
structPCB*SortList（PCB*HL）;
intmain（intargc,char*argv[]）
{
Information（）;
charchoice=Choice（）;
switch（choice）
{
case'1':
system（"cls"）;
HighPriority（）;
break;
case'2':
system（"cls"）;
voiddeadlock（）;
break;
default:
break;
}
system（"pause"）;
return0;
}
voidInformation（）
{
printf（"\n\n"）;
printf（"*********************************************\n"）;
printf（"模拟进程调度算法\n"）;
printf（"*********************************************\n\n\n"）;
printf（"静态优先级调度算法"）;
printf（"死锁问题"）;
printf（"按回车键进入演示程序"）;
getchar（）;
system（"cls"）;
system（"cls"）;
}
charChoice（）
{
printf（"\n\n"）;
printf（"*********************************************\n"）;
printf（"进程调度演示\n"）;
printf（"*********************************************\n\n\n"）;
printf（"1.演示最高优先数优先算法。
\n"）;
printf（"2.演示死锁问题。
\n"）;
printf（"3.退出程序。
\n\n\n\n"）;
printf（"选择进程调度方法:
"）;
printf（"selectafunction（1~3）:
"）;
charch=getchar（）;
returnch;
system（"cls"）;
}
voidHighPriority（）
{
structPCB*processes,*pt;
//pt作为临时节点来创建链表
processes=pt=（structPCB*）malloc（sizeof（structPCB））;
for（inti=1;i!
=4;++i）
{
structPCB*p=（structPCB*）malloc（sizeof（structPCB））;
printf（"进程号No.%d：
\n",i）;
printf（"输入进程名：
"）;
scanf（"%s",p->p_name）;
printf（"输入进程优先数：
"）;
scanf（"%d",&p->p_priority）;
printf（"输入进程运行时间：
"）;
scanf（"%d",&p->p_needTime）;
p->p_runTime=0;
p->p_state='W';
p->next=NULL;
pt->next=p;
pt=p;
printf（"\n\n"）;
}
getchar（）;//接受回车
//processes作为头结点来存储链表
processes=processes->next;
intcases=0;
structPCB*psorted=processes;
while
（1）
{
++cases;
pt=processes;
//对链表按照优先数排序
//psorted用来存放排序后的链表
psorted=SortList（psorted）;
printf（"Theexecutenumber:
%d\n\n",cases）;
printf（"****当前正在运行的进程是：
%s\n",psorted->p_name）;
psorted->p_state='R';
printf（"qnamestatesuperndtimeruntime\n"）;
printf（"%s\t%c\t%d\t%d\t%d\t\n\n",psorted->p_name,psorted->p_state,psorted->p_priority,psorted->p_needTime,psorted->p_runTime）;
pt->p_state='W';
psorted->p_runTime++;
psorted->p_priority--;
printf（"****当前就绪状态的队列为：
\n\n"）;
//pt指向已经排序的队列
pt=psorted->next;
while（pt!
=NULL）
{
printf（"qnamestatesuperndtimeruntime\n"）;
printf（"%s\t%c\t%d\t%d\t%d\t\n\n",pt->p_name,pt->p_state,pt->p_priority,pt->p_needTime,pt->p_runTime）;
pt=pt->next;
}
//pt指向已经排序的链表，判断链表是否有已用时间啊等于需要时间的
pt=psorted;
structPCB*ap;
ap=NULL;//ap指向pt的前一个节点
while（pt!
=NULL）
{
if（pt->p_needTime==pt->p_runTime）
{
if（ap==NULL）
{
pt=psorted->next;
psorted=pt;
}
else
ap->next=pt->next;
}
ap=pt;
pt=pt->next;
}
if（psorted->next==NULL）
break;
getchar（）;
}
}
structPCB*SortList（PCB*HL）
{
structPCB*SL;
SL=（structPCB*）malloc（sizeof（structPCB））;
SL=NULL;
structPCB*r=HL;
while（r!
=NULL）
{
structPCB*t=r->next;
structPCB*cp=SL;
structPCB*ap=NULL;
while（cp!
=NULL）
{
if（r->p_priority>cp->p_priority）
break;
else
{
ap=cp;
cp=cp->next;
}
}
if（ap==NULL）
{
r->next=SL;
SL=r;
}
else
{
r->next=cp;
ap->next=r;
}
r=t;
}
returnSL;
}
//
HANDLEh_mutex_chopsticks[MAX_PHILOSOPHERS];//互斥体数组，每根筷子需要一个互斥体
intthread_number[MAX_PHILOSOPHERS]={1,2,3};//定义死锁的个数
//会产生死锁的哲学家线程
intdeadlock_philosopher（LPVOIDdata）{
intphilosopher_number=*（int*）（data）;//哲学家编号
for（;;）
{
srand（（unsigned）time（NULL）*（philosopher_number+1））;
Sleep（DELAY）;
printf（"%s%c%s%c\n","Philosopher",ZERO+philosopher_number,"iswaitingchopstick",（ZERO+philosopher_number））;
WaitForSingleObject（h_mutex_chopsticks[philosopher_number],INFINITE）;
printf（"%s%c%s%c\n","Philosopher",ZERO+philosopher_number,"gotchopstick",（ZERO+philosopher_number））;
Sleep（DELAY/4）;
printf（"%s%c%s%c\n","Philosopher",ZERO+philosopher_number,"iswaitingchopstick",（ZERO+（1+philosopher_number）%MAX_PHILOSOPHERS））;
WaitForSingleObject（h_mutex_chopsticks[（（1+philosopher_number）%MAX_PHILOSOPHERS）],INFINITE）;
printf（"%s%c%s%c\n","Philosopher",ZERO+philosopher_number,"gotchopstick",（ZERO+（1+philosopher_number）%MAX_PHILOSOPHERS））;
printf（"%s%c%s\n","Philosopher",ZERO+philosopher_number,"iseating."）;
Sleep（DELAY）;
ReleaseMutex（h_mutex_chopsticks[philosopher_number]）;
printf（"%s%c%s%c\n","Philosopher",ZERO+philosopher_number,"releasedchopstick",ZERO+philosopher_number）;
ReleaseMutex（h_mutex_chopsticks[（1+philosopher_number）%MAX_PHILOSOPHERS]）;
printf（"%s%c%s%c\n","Philosopher",ZERO+philosopher_number,"releasedchopstick",（ZERO+（1+philosopher_number）%MAX_PHILOSOPHERS））;
Sleep（DELAY）;
}//endfor
return0;
}
//死锁时的初始化程序
voiddeadlock（）
{
charchoice;
inti=0;
HANDLEh_thread[MAX_PHILOSOPHERS];
printf（"可能出现死锁的哲学家就餐问题\n"）;
for（i=0;i{
h_mutex_chopsticks[i]=CreateMutex（NULL,FALSE,NULL）;
};
for（i=0;i{
h_thread[i]=CreateThread（NULL,0,（LPTHREAD_START_ROUTINE）（deadlock_philosopher）,&thread_number[i],0,NULL）;
};
WaitForMultipleObjects（MAX_PHILOSOPHERS,h_thread,TRUE,-1）;
do
{
choice=（char）getch（）;
}while（choice!
='2'）;
system（"cls"）;
deadlock（）;
printf（"\nPressanykeytoreturntomainmenu."）;
getch（）;
system（"cls"）;
}
//通过按序分配资源预防死锁的哲学家线程
intordered_allocation_philosopher（LPVOIDdata）
{
intphilosopher_number=*（int*）（data）;
for（;;）
{
srand（（unsigned）time（NULL）*（philosopher_number+1））;
Sleep（DELAY）;
if（philosopher_number==MAX_PHILOSOPHERS-1）{
printf（"%s%c%s%c\n","Philosopher",ZERO+philosopher_number,"iswaitingchopstick",（ZERO+（1+philosopher_number）%MAX_PHILOSOPHERS））;
WaitForSingleObject（h_mutex_chopsticks[（1+philosopher_number）%MAX_PHILOSOPHERS],INFINITE）;
Sleep（DELAY/4）;
printf（"%s%c%s%c\n","Philosopher",ZERO+philosopher_number,"iswaitingchopstick",ZERO+philosopher_number）;
WaitForSingleObject（h_mutex_chopsticks[philosopher_number],INFINITE）;
}
else{
printf（"%s%c%s%c\n","Philosopher",ZERO+philosopher_number,"iswaitingchopstick",ZERO+philosopher_number）;
WaitForSingleObject（h_mutex_chopsticks[philosopher_number],INFINITE）;
Sleep（DELAY/4）;
printf（"%s%c%s%c\n","Philosopher",ZERO+philosopher_number,"iswaitingchopstick",ZERO+（1+philosopher_number）%MAX_PHILOSOPHERS）;
WaitForSingleObject（h_mutex_chopsticks[（1+philosopher_number）%MAX_PHILOSOPHERS],INFINITE）;
}
printf（"%s%c%s\n","Philosopher",ZERO+philosopher_number,"iseating."）;
Sleep（DELAY）;
printf（"%s%c%s%c\n","Philosopher",ZERO+philosopher_number,"isreleasingchopstick",ZERO+philosopher_number）;
ReleaseMutex（h_mutex_chopsticks[philosopher_number]）;
printf（"%s%c%s%c\n","Philosopher",ZERO+philosopher_number,"isreleasingchopstick",ZERO+（1+philosopher_number）%MAX_PHILOSOPHERS）;
ReleaseMutex（h_mutex_chopsticks[（1+philosopher_number）%MAX_PHILOSOPHERS]）;
Sleep（DELAY）;
}//endfor
return0;
}
//通过按序分配资源预防死锁的初始化程序
voidordered_allocation（）
{
charchoice;
inti=0;
HANDLEh_thread[MAX_PHILOSOPHERS];
printf（"可能出现死锁的哲学家就餐问题\n"）;
for（i=0;ih_mutex_chopsticks[i]=CreateMutex（NULL,FALSE,NULL）;
};
for（i=0;ih_thread[i]=CreateThread（NULL,0,（LPTHREAD_START_ROUTINE）（ordered_allocation_philosopher）,&thread_number[i],0,NULL）;
};
WaitForMultipleObjects（MAX_PHILOSOPHERS,h_thread,TRUE,-1）;
do
{
choice=（char）getch（）;
}while（choice!
='2'）;
system（"cls"）;
deadlock（）;
printf（"\nPressanykeytoreturntomainmenu."）;
getch（）;
system（"cls"）;
}
升级会员 