课程设计报告

( 2011-- 20xx年度第1学期)

名 称： 操作系统原理课程设计B 院 系：班 级： 学 号： 101909010121 学生姓名： 孙 刚 指导教师： 设计周数：

成 绩：

日期：20xx年 12 月11日

华 北 电 力 大 学 科 技 学 院 实 验 报 告

实验一 单处理器系统的进程调度

一、实验目的

在采用多道程序设计的系统中，往往有若干个进程同时处于就绪状态。当就绪进程个数大于处理器数时，就必须依照某种策略来决定哪些进程优先占用处理器。本实验模拟在单处理器情况下的处理器调度，帮助学生加深了解处理器调度的工作。

二、实验要求

1．设计一个按时间片轮转法实现处理器调度的程序，每个程序由一个PCB表示。

2．程序执行中应能在屏幕上显示出各进程的状态变化，以便于观察调度的整个过程。

三、实验原理

(1)

PCB来代表。进程控制块的格式为：

其中，进程名——作为进程的标识，假设五个进程的进程名分别为Q1，Q2，Q3，Q4，Q5。

指针——进程按顺序排成循环队列，用指针指出下一个进程的进程控制块的首地址，最后一个进程的指针指出第一个进程的进程控制块首地址。

要求运行时间——假设进程需要运行的单位时间数。

已运行时间——假设进程已经运行的单位时间数，初始值为“0”。

状态——有两种状态，“就绪”和“结束”，初始状态都为“就绪”，用“R”表示。当一个进程运行结束后，它的状态为“结束”，用“E”表示。

(2)

每次运行所设计的处理器调度程序前，为每个进程任意确定它的“要求运行时间”。

(3) 把五个进程按顺序排成循环队列，用指针指出队列连接情况。另用一标志单元记录轮到运行的进程。例如，当前轮到P2执行，则有：

标志单元

第 页 共 页

华 北 电 力 大 学 科 技 学 院 实 验 报 告

K1

(4) 处理器调度总是选择标志单元指示的进程运行。由于本实验是模拟处理器调度的功能，所以，对被选中的进程并不实际的启动运行，而是执行：

已运行时间+1

来模拟进程的一次运行，表示进程已经运行过一个单位的时间。

请同学注意：在实际的系统中，当一个进程被选中运行时，必须置上该进程可以运行的时间片值，以及恢复进程的现场，让它占有处理器运行，直到出现等待事件或运行满一个时间片。在这时省去了这些工作，仅用“已运行时间+1”来表示进程已经运行满一个时间片。

(5) 进程运行一次后，应把该进程的进程控制块中的指针值送到标志单元，以指示下一个轮到运行的进程。同时，应判断该进程的要求运行时间与已运行时间，若该进程的要求运行时间?已运行时间，则表示它尚未执行结束，应待到下一轮时再运行。若该进程的要求运行时间=已运行时间，则表示它已经执行结束，应指导它的状态修改成“结束”（E）且退出队列。此时，应把该进程的进程控制块中的指针值送到前面一个进程的指针位置。

(6) 若“就绪”状态的进程队列不为空，则重复上面的（4）和（5）的步骤，直到所有的进程都成为“结束”状态。

(7) 在所设计的程序中应有显示或打印语句，能显示或打印每次选中进程的进程名以及运行一次后进程队列的变化。

(8) 为五个进程任意确定一组“要求运行时间”，启动所设计的处理器调度程序，显示或打印逐次被选中的进程名以及进程控制块的动态变化过程。

PCB1

K2

PCB2

K3

PCB3

K4

PCB4

K5

PCB5

四、实验所需仪器、设备、材料

PC机

五、实验思路

高响应比优先Rp值定义为：Rp=（已等待时间+要求运行时间）/要求运行时间=1+已等待时间/要求运行时间

高响应比优先算法实际是FCFS和SJF的一个折衷 分析：

(1) 若干作业同时到达，短作业先调入执行； (2) 若干作业要求执行时间相同，先到作业先执行 (3) 一般情况，按计算Rp值调度

六、实验流程

第 页 共 页

华 北 电 力 大 学 科 技 学 院 实 验 报 告

第 页 共 页

华 北 电 力 大 学 科 技 学 院 实 验 报 告

七、实验源程序

#include<iostream>

using namespace std;

typedef struct PCB

{

int id; //进程名字p1、p2、p3、p4、p5

struct PCB *next;//指针指向下一个位置

int runtime; //运行时间

int priority;//优先级

char status;//状态

}*pcb;

void create(PCB *h)

{

int a,b; //a运行时间、b进程优先级

h->next=NULL;

for(int i=0;i<5;i++)

{

cout<<"-------P"<<i+1<<" :"<<endl;

cin>>a>>b;

PCB *p=new PCB;

PCB *q=h->next;

p->id=i+1;

p->runtime=a;

p->priority=b;

p->status='R';

if((q==NULL)||(p->priority>q->priority))

{

p->next=h->next;

h->next=p;

continue;

}

while((p->priority<q->next->priority)&&(q->next!=NULL)) {

q=q->next;

}

p->next=q->next;

q->next=p;

}

}

void sort(PCB *h)

{

if(h->next->runtime==0)

{

h->next->status='E';

第 页 共 页

华 北 电 力 大 学 科 技 学 院 实 验 报 告

h->next=h->next->next;

return;

}

PCB *p=h->next;

h->next=p->next;

PCB *q=h->next;

if((q==NULL)||(p->priority>q->priority))

{

p->next=h->next;

h->next=p;

return;

}

while((q->next!=NULL)&&(p->priority<=q->next->priority))

{

q=q->next;

}

p->next=q->next;

q->next=p;

}

void call(PCB *h)

{

cout<<"调用 P"<<h->next->id<<endl;

h->next->runtime--;

h->next->priority--;

}

void show(PCB *h)

{

PCB *p=h->next;

while(p!=NULL)

{

cout<<" p"<<p->id <<" "<<p->runtime <<" "<<p->priority <<" "<<p->status <<endl; cout<<"---------------------------------------------------------------------- "<<endl;

p=p->next;

}

}

void main()

{

cout<<" ** 请输入各个进程的运行时间及其优先级 **"<<endl; PCB *h=new PCB; create(h);

while(h->next!=NULL)

{

call(h);

sort(h);

show(h);

第 页 共 页

华 北 电 力 大 学 科 技 学 院 实 验 报 告

}

}

实验二 银行家算法实验

一、实验目的

熟悉银行家算法，理解系统产生死锁的原因及避免死锁的方法,加深记意。

二、实验要求

用高级语言编写和调试一个描述银行家算法的程序。

设计五个进程{P0，P1，P2，P3，P4}共享三类资源{A，B，C}的系统，{A，B，C}的资源数量分别为10，5，7。进程可动态地申请资源和释放资源，系统按各进程的申请动态地分配资源。要求程序具有显示和打印各进程的某一时刻的资源分配表和安全序列；显示和打印各进程依次要求申请的资源号以及为某进程分配资源后的有关资源数据。

三、实验原理

利用银行家算法避免死锁

1、银行家算法中的数据结构

（1）可利用资源向量Available

（2）最大需求规阵Max

（3）分配矩阵Allocation

（4）需求矩阵Need

2、银行家算法

（1）如果Requesti＜或=Need,则转向步骤2；否则，认为出错，因为它所需要的资源数已超过它所宣布的最大值。

（2）如果Request＜或=Available,则转向步骤（3）；否则，表示系统中尚无足够的资源，P1必须等待。

（3）系统试探把要求的资源分配给进程Pi,并修改下面数据结构中的数值：

Available:=Available-Requesti;

Allocation:=Allocationi+Request;

Needi:=Needi-request;

(4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。

3、安全性算法

第 页 共 页

华 北 电 力 大 学 科 技 学 院 实 验 报 告

系统所执行的安全性算法可描述如下：

（1）设置两个向量

①工作向量Work。它表示系统可提供进程继续运行所需要的各类资源数目，它含有m个元素，执行安全算法开始时，Work:=Allocation;

②Finish。它表示系统是否有足够的资源分配给进程，使之运行完成，开始时先做Finish[i]:=false;当有足够资源分配给进程时，令Finish[i]:=true。

（2）从进程集合中找到一个能满足下述条件的进程：

①Finish[i]:=false

②Need</=Work

如找到，执行步骤（3）；否则，执行步骤（4）。

（3）当进程P获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行： Work：=Work+Allocation;

Finish[i]：=true;

Go to step 2;

（4）如果所有进程的Finish[i]=true,则表示系统处于安全状态；否则，系统处于不安全状态。

4、银行家算法之例

假设有五个进程{P0,P1,P2,P3,P4}和三种类型的资源{A，B，C}，每一种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图1所示。

图1

（1）T0时刻的安全性

利用安全性算法对T0时刻的资源分配情况进行分析，可得下表所示的T0时刻的安全性分析，从中得知，T0时刻存在着一个安全序列{P1，P3，P4，P2，P0}，故系统是安全的，如图2所示。

第 页 共 页

华 北 电 力 大 学 科 技 学 院 实 验 报 告

图2

（2） P1请求资源

P1发出请求向量Request(1,0,2),系统按银行家 算法进行检查：

(1)Request1(1,0,2)≤Need(1,2,2)

(2)Request1(1,0,2)≤Available(3,3,2)

(3)系统先假定可为P1分配资源，并修改Aailable，Allocation1和Need1向量，由此形成的资源变化情况如图1中的圆括号所示。

（4）我们再利用安全性检查此时系统是否安全。

由所进行的安全性检查得知，可以找到一个安全序列{P1，P3，P4，P2，P0}。因此，系统是安全的，可以立即将P1所申请的资源分配给它。

（3）P4请求资源

P4发出请求向量Request(3,3,0),系统按银行家算法进行检查：

(1)Request4(3,3,0)≤Need4(4,3,1)。

(2)Request4(3,3,0)>Available(2,3,0)，让P4等待。

（4） P0请求资源

P0发出请求向量Request0(0,2,0),系统按银行家算法进行检查：

（1）Request0(o,2,0)<或=Need0(7,4,3));

（5）进行安全性检查

可用资源Available{2,1,0}已不能满足任何进程的需要，故系统进入不安全状态，此时系统不分配资源。

如果在银行家算法中，把P0发出的请求向量改为Request(0,1,0),系统是否能将资源分配给它，请读者考虑

四、实验所需仪器、设备、材料

PC机

五、实验思路

银行家算法的基本思想是分配资源之前, 判断系统是否是安全的; 若是, 才分配。它是最具有代表性的避免死锁的算法。

设进程cusneed 提出请求REQUEST [i] ，则银行家算法按如下规则进行判断。

(1) 如果REQUEST [cusneed] [i]<= NEED[cusneed][i] ，则转(2) ；否则，出错。

(2) 如果REQUEST [cusneed] [i]<= AVAILABLE[cusneed][i] ，则转(3) ；否则，出错。

(3) 系统试探分配资源，，进

(4) 系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复 原状程等待 安全性检查算法

(1) 设置两个工作向量Work=AVAILABLE;FINISH

(2) 从进程集合中找到一个满足下述条件的进程， FINISH==false;

NEED<=Work;

第 页 共 页

华 北 电 力 大 学 科 技 学 院 实 验 报 告

如找到，执行(3) ；否则，执行(4)

(3) 设进程获得资源，可顺利执行，直至完成，从而释放资源。 Work+=ALLOCATION;

Finish=true;

(4) 如所有的进程Finish= true ，则表示安全；否则系统不安全

六、实验流程

七、实验源程序

#include<iostream>

using namespace std;

#include<string.h>

#include<stdio.h>

#define False 0

#define True 1

int Max[100][100]={0};//各进程所需各类资源的最大需求

int Avaliable[100]={0};//系统可用资源

char name[100]={0};//资源的名称

int Allocation[100][100]={0};//系统已分配资源

第 页 共 页

华 北 电 力 大 学 科 技 学 院 实 验 报 告

int Need[100][100]={0};//还需要资源

int Request[100]={0};//请求资源向量

int temp[100]={0};//存放安全序列

int Work[100]={0};//存放系统可提供资源

int M=100;//作业的最大数为100

int N=100;//资源的最大数为100

void showdata()//显示资源矩阵

{

int i,j;

cout<<"系统目前可用的资源[Avaliable]:"<<endl; for(i=0;i<N;i++)

cout<<name[i]<<" ";

cout<<endl;

for (j=0;j<N;j++)

cout<<Avaliable[j]<<" ";//输出分配资源

cout<<endl;

cout<<" Max Allocation Need"<<endl; cout<<"进程名 ";

for(j=0;j<3;j++){

for(i=0;i<N;i++)

cout<<name[i]<<" ";

cout<<" ";

}

cout<<endl;

for(i=0;i<M;i++){

cout<<" "<<i<<" ";

for(j=0;j<N;j++)

cout<<Max[i][j]<<" ";

cout<<" ";

for(j=0;j<N;j++)

cout<<Allocation[i][j]<<" ";

cout<<" ";

for(j=0;j<N;j++)

cout<<Need[i][j]<<" ";

cout<<endl;

}

}

int safe()//安全性算法

{

int i,k=0,m,apply,Finish[100]={0};

int j;

int flag=0;

Work[0]=Avaliable[0];

Work[1]=Avaliable[1];

第 页 共 页

华 北 电 力 大 学 科 技 学 院 实 验 报 告

Work[2]=Avaliable[2];

for(i=0;i<M;i++){

apply=0;

for(j=0;j<N;j++){

if (Finish[i]==False&&Need[i][j]<=Work[j]){ apply++;//只有apply为n时才能进行分配

if(apply==N){

for(m=0;m<N;m++)

Work[m]=Work[m]+Allocation[i][m];//变分配数 Finish[i]=True;//把完成的进程标志位1 temp[k]=i;//记录符合条件的是哪一组

i=-1;

k++;

flag++;

}

}

}

}

for(i=0;i<M;i++){

if(Finish[i]==False){

cout<<"系统不安全"<<endl;//不成功系统不安全 return -1;

}

}

cout<<"系统是安全的!"<<endl;//如果安全，输出成功 cout<<"分配的序列:";

for(i=0;i<M;i++){//输出运行进程数组

cout<<temp[i];

if(i<M-1) cout<<"->";

}

cout<<endl;

return 0;

}

int main()//主函数

{

int i,j,number,m,n,flag;

char ming;

cout<<"请首先输入系统可供资源种类的数量:";

cin>>n;

N=n;

for(i=0;i<n;i++)

第 页 共 页

华 北 电 力 大 学 科 技 学 院 实 验 报 告

{

cout<<"资源"<<i+1<<"的名称:";

cin>>ming;

name[i]=ming;

cout<<"资源的数量:";

cin>>number;

Avaliable[i]=number;

}

cout<<endl;

cout<<"请输入作业的数量:";

cin>>m;

M=m;

cout<<"请输入各进程的最大需求量("<<m<<"*"<<n<<"矩阵)[Max]:"<<endl; for(i=0;i<m;i++)

for(j=0;j<n;j++)

cin>>Max[i][j];

do{

flag=0;

cout<<"请输入各进程已经申请的资源量("<<m<<"*"<<n<<"矩阵)[Allocation]:"<<endl; for(i=0;i<m;i++)

for(j=0;j<n;j++){

cin>>Allocation[i][j];

if(Allocation[i][j]>Max[i][j])

flag=1;

Need[i][j]=Max[i][j]-Allocation[i][j];

}

if(flag)

cout<<"申请的资源大于最大需求量，请重新输入!\n";

}

while(flag);

showdata();//显示各种资源

safe();//用银行家算法判定系统是否安全

return 1;

}

第 页 共 页

华 北 电 力 大 学 科 技 学 院 实 验 报 告

实验三 主存储器空间的分配和回收

一、实验内容

主存储器空间的分配和回收。

二、实验目的

一个好的计算机系统不仅要有一个足够容量的、存取速度高的、稳定可靠的主存储器，而且要能合理地分配和使用这些存储空间。当用户提出申请存储器空间时，存储管理必须根据申请者的要求，按一定的策略分析主存空间的使用情况，找出足够的空闲区域分配给申请者。当作业撤离或主动归还主存资源时，则存储管理要收回作业占用的主存空间或归还部分主存空间。主存的分配和回收的实现与主存储器的管理方式有关的，通过本实验帮助学生理解在可变分区管理方式下应怎样实现主存空间的分配和回收。

三、实验原理

模拟在可变分区管理方式下采用最先适应算法实现主存分配和回收。

(1)可变分区方式是按作业需要的主存空间大小来分割分区的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入。随着作业的装入、撤离，主存空间被分成许多个分区，有的分区被作业占用，而有的分区是空闲的。例如：

为了说明哪些区是空闲的，可以用来装入新作业，必须要有一张空闲区说明表，格式如下：

第一栏

第二栏

? 长度——指出从起始地址开始的一个连续空闲的长度。

状态——有两种状态，一种是“未分配”状态，指出对应的由起址指出的某个长度的区域是空闲区。

(2) 当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个足够大的空闲区。有

第 页 共 页

华 北 电 力 大 学 科 技 学 院 实 验 报 告

时找到的空闲区可能大于作业需要量，这时应把原来的空闲区变成两部分：一部分分给作业占用；另一部分又成为一个较小的空闲区。为了尽量减少由于分割造成的空闲区，而尽量保存高地址部分有较大的连续空闲区域，以利于大型作业的装入。为此，在空闲区说明表中，把每个空闲区按其地址顺序登记，即每个后继的空闲区其起始地址总是比前者大。

(3) 采用最先适应算法（顺序分配算法）分配主存空间。

按照作业的需要量，查空闲区说明表，顺序查看登记栏，找到第一个能满足要求的空闲区。当空闲区大于需要量时，一部分用来装入作业，另一部分仍为空闲区登记在空闲区说明表中。

由于本实验是模拟主存的分配，所以把主存区分配给作业后并不实际启动装入程序装入作业，而用输出“分配情况”来代替。

(4) 当一个作业执行结束撤离时，作业所占的区域应该归还，归还的区域如果与其它空闲区相邻，则应合成一个较大的空闲区，登记在空闲区说明表中。

(5) 请按最先适应算法设计主存分配和回收的程序。假设初始时主存中没有作业，现按下面序列进行内存的申请与释放：

作业1申请300K，作业2申请100K，作业1释放300K，作业3申请150K，

作业4申请30K， 作业5申请40K， 作业6申请60K， 作业4释放30K。

请你为它们进行主存分配和回收，把空闲区说明表的初值以及每次分配或回收后的变化显示出来或打印出来。

四、流程图

第 页 共 页

华 北 电 力 大 学 科 技 学 院 实 验 报 告

五、源程序和注释

1.程序中使用的数据结构及符号说明。

int TABLE[4][2]={{0,512}};//TABLE[][]={起始地址,长度,状态}

int WORK[8][3]={{300,1,0},{100,2,0},{300,1,1},{150,3,0},{30,4,0},{40,5,0},{60,6,0},{30,4,1}}; //WORKE[][]={作业大小,作业次序/起始地址,操作类型(0申请/1释放)}

int i,j,k,flag=1,now,temp[2],once=0;//now 当前作业,temp[2]交换变量,once执行申请变量,i,j,k循环变量

2. 源程序和注释

#include<iostream>

using namespace std;

int TABLE[4][2]={{0,512}};//TABLE[][]={起始地址,长度,状态}

int WORK[8][3]={{300,1,0},{100,2,0},{300,1,1},{150,3,0},{30,4,0},{40,5,0},{60,6,0},{30,4,1}}; //WORKE[][]={作业大小,作业次序/起始地址,操作类型(0申请/1释放)}

int i,j,k,flag=1,now,temp[2],once=0;//now 当前作业,temp[2]交换变量,once执行申请变量,i,j,k循环变量

void first_01()//TABLE 功能的实现:申请作业功能

第 页 共 页

华 北 电 力 大 学 科 技 学 院 实 验 报 告

{

}

void first_02()//TABLE 功能的实现:释放作业功能 {

}

第 页 共 页 j=0; for(i=0;i<flag;i++) { if(WORK[now][1]==TABLE[i][0])//初始地址重复 { TABLE[i][0]=TABLE[i][0]-WORK[now][0]; TABLE[i][1]=TABLE[i][1]+WORK[now][0]; } else { } j++; once=0; for(i=0;i<flag;i++) { } if(once==0&&TABLE[i][1]>=WORK[now][0]) { TABLE[i][0]=TABLE[i][0]+WORK[now][0]; } TABLE[i][1]=TABLE[i][1]-WORK[now][0]; for(j=now;j<8;j++) { if(WORK[j][2]==1&&WORK[now][2]==0&&WORK[j][1]==WORK[now][1]) { WORK[j][1]=TABLE[i][0]; //释放作业的起始地址 } WORK[now][1]=TABLE[i][0]-WORK[now][0];//申请作业的起始地址 } once=1; } if(j==flag) { } flag++; TABLE[flag-1][0]=WORK[now][1]-WORK[now][0]; TABLE[flag-1][1]=WORK[now][0];

华 北 电 力 大 学 科 技 学 院 实 验 报 告

void first_03()////TABLE 功能的实现:输出及整合TABLE {

for(i=0;i<flag;i++)//判断长度为零时 { if(TABLE[i][0]==0) { } for(j=i+1;j<flag;j++) { } TABLE[j][0]=TABLE[j-1][0]; TABLE[j][0]=0; TABLE[j][1]=TABLE[j-1][1]; TABLE[j][1]=0; } for(i=0;i<flag;i++)//冒泡算法实现排序 { for(j=i;j<flag;j++) { } if(TABLE[i][0]>TABLE[j][0]) { } for(k=0;k<2;k++) { } temp[k]=TABLE[i][k]; TABLE[i][k]=TABLE[j][k]; TABLE[j][k]=temp[k];

}

cout<<"本次TABLE空闲区说明表"<<endl;

cout<<" "<<"起址"<<" "<<"长度"<<" "<<"状态"<<endl;

}

void main()

{

for(now=0;now<8;now++) { if(WORK[now][2]==0) {

第 页 共 页 for(i=0;i<flag;i++) { cout<<"第"<<i<<"栏"<<" "<<TABLE[i][0]<<" "<<TABLE[i][1]<<"未分配"<<endl; } cout<<endl;

华 北 电 力 大 学 科 技 学 院 实 验 报 告

}} } first_01(); } else if(WORK[now][2]==1) { first_02(); } first_03();

六、程序运行时的初值和运行结果。

1．作业初值：

作业1申请300K，作业2申请100K，作业1释放300K，作业3申请150K， 作业4申请30K， 作业5申请40K， 作业6申请60K， 作业4释放30K。

2．TABLE初值

TABLE[0]={0，512};

3．运行结果

第 页 共 页

华 北 电 力 大 学 科 技 学 院 实 验 报 告

4.如果在要申请一个100K的作业空间，能否满足？

因为剩余未分配空间中有大于100k的，可以满足。

七、实验小结

本次实验中，因自己开始就把TABLE的功能想全了，所以还是比较容易的，出现过如下问题：第一次：TABLE不增加，原因，flag++的执行条件错误；第二次：TABLE表中对同一作业执行多次，原因，残缺设置执行操作的once变量。经此实验，自己对程序设计更加熟练。缺点是习惯用数组而不习惯用指针。

第 页 共 页