多级队列调度算法.doc

多级队列调度算法&银行家算法
LT
2
操作系统原理
上
机
报
告
院系： 计算机学院
班级： 191094—16
姓名： 熊金莲
学号： 20091003768

二 O 一 一 年 六 月
3
一：银行家算法
实验目的：
1、了解并掌握银行家算法的思想；
2、通过编程实现银行家算法；
实验步骤：
安全状态：系统按照某种序列为多个进程分配资源直到最大需求，如果能够保证所有进程全部顺利执行完毕，则称系统是安全的。
2、采取的数据结构
（1）可利用资源量Available
（2）最大需求矩阵Max
（3）分配矩阵Allocation[i]
（4）需求矩阵Need[i]
（5）请求矩阵Request[i]
3、银行家算法
设request：是Pi进程的请求向量，当Pi发了资源请求后，系统按下述步骤检查：
（1）如果Request[i]<= Need[i]，则转向步骤（2）；
（2）若Request[i] <=Available，则转向步骤（3）；
（3）系统试探性地把要求的资源分配给进程Pi，并修改以下数据结构的值：
Available=Available-Request[i]；
Allocation[i]= Allocation[i]+ Request[i]；
Need[i]= Need[i]- Request[i]；
（4）系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态，若安全，才正式将资源分配给Pi进程，完成本次分配；否则，试探性分配作废，恢复原来的资源分配状态，Pi进程进入等待状态。
4、安全性算法
（1）设置两个向量：工作向量work，它表示系统可提供给进程继续运行所需的各类资源数目，执行安全性算法开始时，work初值=Available；finish表示系统是否有足够的资源分配给里程，使之运行完成，开始时，finish[i]=false；当有足够资源分配给进程时，令finish[i]=true；
（2）从进程集合中找到满足下述条件的进程：
finish[i]= false；
Need[i] <= work；若找到执行（3），否则执行（4）；
（3）当进程Pi获得资源后，顺序执行直到完成，并释放它的资源，执行：
work= work+ Allocation[i]；
finish[i]= true；
go to step(2);
（4）若所有进程的finish[i]= true，则系统处于安全状态，否则，处于不安全状态。
5、具体代码实现如下
#define a 5
4
5
请输入需要请求的资源序列:2 0 1
该进程阻塞!
请输入进程序号:3
请输入需要请求的资源序列:0 0 2
新状态稳定,资源实际分配!
该运行结果与实验预期结果相符,即实现了银行家算法！！！！
二：多级队列调度算法
实验目的：
了解进程高度算法的原理及物理变换；
掌握简单轮转调度算法和短程优先调度算法，并对两种算法的效率进行简单分析
实验步骤：
设置好各种队列，两种算法均以链表作为调度队列，因为两种算法均只需要一个队列就能满足调度。
第一种算法的思想是采用的轮转调试，第二种采用的是短进程优先算法，确定好算法步骤，进行输入测试。
3设RQ分为RQ1和RQ2，RQ1采用轮转法，时间q=7.
 RQ1>RQ2，RQ2采用短进程优先调度
6
4、采取的数据结构
typedef struct tag_pcb
{
char name[8];
int need;
int turn;
struct tag_pcb *next;
}PCB;
5,大体设计思路
（1）/Test_of_Rotation_cycle循环轮转法
轮转法将CPU时间划分成若干个短的时间片断（通常小于100ms），将这些时间片断轮流分配给各个就绪进程使用。如果时间片结束时，进程还没有运行完，则CPU将被剥夺并分配给另一个就绪进程使用；如果进程在时间片结束前阻塞或结束，则CPU理解发生切换。
//RQ1采用轮转法
p=RQ1;
int flag=0;
while(p!=NULL)
{
while(p!=NULL&&p->need>0)
{
q=p;