2023年操作系统实验报告2

南大摩

CENTRALSOUTH

操作系统原理

实验报告

学生姓名徐心萌

学号

专业班级物联网工程1501

学院信息科学与工程学院

完毕时间2023年6月9日

目录

实验一银行家算法4

一、实验目的4

二、实验要求4

三、实验原理4

四、程序框图6

五、实验结果7

六、实验小结8

实验二页面置换算法9

一、实验目的9

二、实验要求9

三、实验原理9

四、程序框图10

五、实验结果12

六、实验小结12

实验三调度算法13

一、实验目的13

二、实验要求13

三、实验原理13

四、程序框图14

五、实验结果16

六、实验小结18

实验四地址转换19

一、实验目的19

二、实验要求19

三、实验原理19

四、程序框图20

五、实验结果22

六、实验小结23

程序清单24

实验一银行家算法

一、实验目的

1、进一步进一步理解死锁的概念、产生死锁的因素、避免死锁和

解除死锁的方法；

2、掌握运用银行家算法避免死锁的方法。

二、实验规定

模拟银行家算法避免死锁的实现过程

三、实验原理

银行家算法是一种最有代表性的避免死锁的算法。在避免死锁

方法中允许进程动态地申请资源，但系统在进行资源分派之前,系统必

须一方面拟定是否有足够的资源分派给该进程,然后计算本次分派资

源的安全性，若分派不会导致系统进入不安全状态，则分派，否则让进

城等待。

数据结构如下：

(1)可运用资源向量AvailabIe:具有m个元素的数组，其中

的每一个元素代表一类可运用的资源数目。假如Avai1ableD]=K,

则表达系统中现有Rj类资源K个。

(2)最大需求矩阵Max：一个nXm的矩阵，它定义了系统中

n个进程中的每一个进程对m类资源的最大需求。假如Max[i,j]=K,

则表达进程i需要Rj类资源的最大数目为K。

(3)分派矩阵Al1ocation：一个nXm的矩阵，它定义了系统

中每一类资源当前已分派给每一进程的资源数。如A1locati。n

[i,j]=K，则表达进程i当前已分得Rj类资源的数目为K。

⑷需求矩阵Need：一个nXm的矩阵，用以表达每一个进程尚

需的各类资源数。假如Need[iJ]=K,则表达进程i还需要Rj类资源

K个，方能完毕其任务。

四、程序框图

五、实验结果

S3C:\Users\xuxinmeng\Desktop\银行法\Debug\银行家喜去.exe

全序

列

—

进

程

安

号r1

-:X1

甘

求

*[[3[O阵

第

已

大需

-矩

求[2][4]

分

配

版-g

75o143可利用矩阵

332

OO

4

矗

?进1

程

求

要

n

-一

序

kr列i3—r1

l/全•

1[O求

[2阵

需

矩

矩

n求.[4]

-大

久5

7O743可利用矩阵

OOO

OO532

OO

第

进

能3

比

进

程

全

列

凝

序

机

1^号IT

<-:-J

[4阵

已

需

大

巨

求

阵

配

瓦

5刀

7301O743可利用矩阵

322OOO

3O26OO

222OOO

433OO243743

“

〉

在

^新进&O

进

求

程,3

■[O

全序

列

1d2T仃

/fn-J

大需

[4求

求

p矩K

-5-可利用矩阵

取737OOO

2OO753

9O23O6oo

22222OOO

43OO2

^进2

^呈

求

?i进.

一

■要6OO

全序

列

蟹

进

程

号u⑷

/客ni

已

矩

需*[

大

阵

分

配]:

矩

求zE

取-可利用矩阵

7573ooO

32OOO

929O2ooo

22222OOO1055

程遹由：4、

，各资源要求：431

者全序列辨出[进程号]:

戛大需求矩阵，已分配矩阵,ooo可利用矩阵

ooo

ooo

ooo

OOO

1057

本次算法模拟已经完成!

六、实验小结

银行家算法是一个思绪很清楚的办法，在编写的过程中，在安全性

算法那一步思考了很久，思考找到安全序列的办法，最后选择用贪心

法求得安全序列。整个算法的核心重要是对于安全状态和不安全状态

的判断，分两步，第一部是系统对请求值的合法性进行检查，第二部是

安全性检查，看是否能找到看安全序列，若试探性分派后能找到安全

序列，则进行分派，否则不予分派，从而达成避免死锁的目的。

实验二页面置换算法

一、实验目的

1、进一步了解页面置换的原理和规定；

2、理解最佳置换算法、先进先出、最近最久未使用、最少使用等

各类置换算法的原理。

二、实验规定

运用各类置换算法实现对页面的置换

三、实验原理

1、先进先出置换算法（FIFO）：是最简朴的页面置换算法。这种

算法的基本思想是：当需要淘汰一个页面时，总是选择驻留主存时间

最长的页面进行淘汰，即先进入主存的页面先淘汰。其理由是:最早调

入主存的页面不再被使用的也许性最大。

2、最近最久未使用（LRU）算法：这种算法的基本思想是：运用局

部性原理，根据一个作业在执行过程中过去的页面访问历史来推测未

来的行为。它认为过去一段时间里不曾被访问过的页面，在最近的将

来也许也不会再被访问。所以，这种算法的实质是：当需要淘汰一个页

面时一，总是选择在最近一段时间内最久不用的页面予以淘汰。

四、程序框图

（FIFO置换算法）

（LRU置换算法）

4db木

五、实验结果

浦雄

轻

制tW

，

—

正獭

人

页

肯3

面号

页

0为.2

面号

第13

页

为.

面号

第24

页

为.

面号

第33

页

为

面号

第4.2

页

为.

第

5面号1

页

为.

第

6面号3

.

页

为

第

7面号4

料

科

日

料科

^会**

FIFO页面置换情况：

2-1-1

23-1

234

134

缺页次数：4缺页率：50.00%

*************************************************

******************福费蓄鲁蔡*整****************

LRU页面置换情况：

2-1-1

23-1

234

231

431

缺页次警5缺页率：625。］*****

六、实验小结

本实验研究了若干页面置换算法，在整个学习的过程中收获很多。

最后重点学习了先进先出和最近最久未使用这两种算法，这两种算法

均是对于最佳置换算法的改善。实验结果显示在这种序列下LRU置换

算法的缺页率并没有比FIFO算法更优秀，这源自于序列的特点，一

般情况下,LRU算法考虑到页面调入内存后的使用情况,结果比FIFO

更优一些。

实验三调度算法

一、实验目的

1、了解解决机调度的层次和调度算法的目的，调度的实质与意义；

2、熟悉各类调度算法的原理与实际应用。

二、实验规定

模拟实现各类调度算法

三、实验原理

1、先来先服务(FCFS)调度算法

先来先服务(FCFS)调度算法是一种最简朴的调度算法。当在作

业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或

多个最先进入该队列的作业，将它们调入内存，为它们分派资源、创

建进程，然后放入就绪队列。在进程调度中采用FCFS算法时，则每次

调度是从就绪队列中选择一个最先进入该队列的进程,为之分派解决

机，使之投入运营。该进程一直运营到完毕或发生某事件而阻塞后才

放弃解决机。

2、短作业优先(SJF)调度算法

最短优先调度算法是指对短作业或短进程优先调度的算法。它们

可以分别用于作业调度和进程调度。短作业优先(SJF)的调度算法是

从后备队列中选择一个或若干个估计运营时间最短的作业，将它们调

入内存运营。而短进程优先(SPF)调度算法则是从就绪队列中选出

一个估计运营时间最短的进程，将解决机分派给它，使它立即执行并

一直执行到完毕,或发生某事件而被阻塞放弃解决机时再重新调度。

A3、时间片轮转调度算法

在时间片轮转法中，系统将所有的就绪进程按先来先服务的原则

排成一个队列,每次调度时，把CPU分派给队首进程，并令其执行一

个时间片。当执行的时间片用完时，由一个计时器发出时钟中断请求,

调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末

尾；然后，再把解决机分派给就绪队列中新的队首进程，同时也让它

执行一个时间片。这样就可以保证就绪队列中的所有进程在一给定的

时间内均能获得一时间片的解决机执行时间。

4、优先级调度算法

当把优先级调度算法用于作业调度时，系统将从后备队列中选择

若干个优先权最高的作业装入内存。当用于进程调度时，该算法是把

解决机分派给就绪队列中优先权最高的进程

四、程序框图

（SJF调度算法）

（时间片轮转调度算法）

(优先级优先调度)

五、实验结果

/*****

度

务

调

/*1*:、

度**/

/2、

*调/

露

度*

片

/*3、/

调

先

、*

度

/*4级/

调*

/*出

0、

*十

/*****/

*:***/

请选择菜单项：1

请输入有n个进程(0<n<=50)：4

服

id：到达时间2完成时间周转时间带权周转时间

1：13321.00

2：13651.67

3：24972.33

4：313102.50

6.00

1.88

料

尸

"H廿

调*/

度

/*调

先

Is入*/

/*度

调*/*/

/*度

调*/

业/

3X始

度*

/**/

/*：

os生

”2

/***

请选择菜单项：2

请输入有n个进程(0<n<=50):4

1

2

1

3

3

4

d：到达时间服务时间完成时间周转时间带权周转时间

：12321.00

：13651.67

：23972.33

：3413102.50

6.00

：1.88

/*************************/

/*凌■调度*/

/*上罐*/

/*3、时面片?*/

4、爆级l先i调t度

/**/

/*0、痕出；*/

/**************5***********/

请选择菜单项：3

请输入有门个进程(0<n<=50):4

整

请A

到w

务^

服.

一

到

达群UB

服

务8

、

id：到达时间服务时间元成时间周转时间带权周转时间

1：12652.50

2；131093.00

3：231193.00

4：3413102.50

平均周转时间：8.25

年均带权周转时间：2.75

到

务

调

度

1J兀

/*25,

度

调

看

/*工

3业

寸

度

/*4调

/*Lt

1=基

述

度

/*0调

*/

/**『

***********/

请选择某单项：4

请输入有n个进程（0<n<=50）:

i篝-

BB1

日-3

先H

.如4

12«

达鼾

到-

B1

务-4

桀

黑8

先2

斯

达-

B3

务-4

H

吸

先5

优级

冼

id：到达时间服务时间完成时间周转时间带权周转时间

34

2：144831.00

1：12271.75

12

4：11492.25

3：3516133.25

平均周转时间:8.00

平均带权周转时间：2.06

六、实验小结

调度算法是操作系统最基础的算法之一，本次实验通过对先来先

服务、短作业优先、优先级优先、时间片轮转等算法的模拟进一步熟

悉了各类调度算法，无论是在加深对作业调度或者进程调度的理解上,

都收获很大。

实验四地址转换

一、实验目的

1、熟悉基本的分页、分段存储管理方式及其原理；

2、理解在分页分段存储管理方式中逻辑地址与物理地址的转化。

二、实验规定

模拟分页、分段存储管理方式逻辑地址与物理地址的转化

三、实验原理

1、分页存储管理方式:地址转换时，先从页表控制寄存器中找

到相应的页表，再以页号为索引去检索页表。查找操作由硬件执行。

在执行检索之前,先将页号与页表长度进行比较，假如页号大于或等

于页表长度,则表达本次所访问的地址已超越进程的地址空间。于是，

这一错误将被系统发现并产生一地址越界中断。若未出现越界错误，

则将页表始址与页号和页表项长度的乘积相加,便得到该表项在页表

中的位置，于是可从中得到该页的物理块号,将之装入物理地址寄存

器中。与此同时，再将有效地址寄存器中的页内地址送入物理地址寄

存器的块内地址字段中。这样便完毕了从逻辑地址到物理地址的变换。

2、分段存储管理方式：逻辑地址空间由一组段组成。每个段都

有名字和长度。地址指定了段名称和段内偏移。因此用户通过两个量

来指定地址：段名称和偏移。段是编号的，通过段号而非段名称来引

用。因此逻辑地址由有序对构成:〈segment-number,offset>«

段号s,段内偏移d>）段偏移d因该在0和段界线之间，假如合

法，那么就与基地址相加而得到所需字节在物理内存中的地址。因此

段表是一组基地址和界线寄存器对。

四、程序框图

（分页存储管理方式）

（分段存储管理方式）

结束

五、实验结果

B3C:\Users\xuxinmeng\Desktop\ififtt^^\Debug\itStit^^.exe

*******************************************

分页地址转换

公

入

数

、

页

■面114

Im刖

to±

号

灰00

P卧

-。

.位

标

苴

/心

志

人

I、1

ca弛

入

、

-存

王

号2

Im刖

Eo

卧

-P■号1

・

公

位

/标

苴

志

人

、1

In妙

E

刖

入

存

i王4

n号

!,>I■E

页^2

P与•

・

位

in〈-

标

-至志

刖o

入

，0

I、£

我L

号3

P.位

标

-志

人O

/a公-

、±R-

I司

表

页

志

主存

号

页

面号

0标w1

X2

主

志

标

页

面号

号

1存

w

主4

标

页

号

面

志

2号

存

主-1

标

页

号

志

3号

A%存

址-1

第

地

入

请-

®地

^耀

-：

理

地

物X12

U3

面

号

页Z

113

偏移量：57

分段地址转换

入

(1-100)：4

衣.

入

请限：100

人施址:0

衣•.

入

请限：200

入地址：300

肩.

入

-限：400

jH入

累地址：1000

次.

入

请

人限：200

请地址：10000

段表

1地S址0

.&:

.2OO地址3oo

.&:OO

址

.4地t1ooo

.&:OO

址

2地1OOOO

入

&:曲

OO辑s

址

请

逻

入

请:1

入

请

覆22

地

物:3

一22

六、实验小结

总的来说，逻辑地址和物理地址的转化在计算上是一个简朴的操

作，但是通过这次实验我们更应当了解到它的本质是对不同存储管理

方式的映射关系，了解段表、页表等结构，从而更好地理解存储管理

方式，这让我受益匪浅。

程序清单

1、银行家算法

#include<stdio.h>

#include<stdlib.h>

#ifndefMY_MAX

#defineMY_MAX5

#endif

intmaxl[5][3]={

{7,5,3},

{3,2,2},

{9,0,2),

{2,2,2},

(4,3,3}

};/*最大分派需求矩阵*/

intallocationl[5][3]={

(0,1,0),

(2,0,0},

{3,0,2},

{2,1,1},

(0,0,2)

};/*已分派矩阵*/

intneedl[5][3]={

(7,4,3},

{1,2,2),

(6,0,0},

(0,1,1},

(4,3,1)

/**/

/*生成拟定范围[min,max]内的数*/

intrandom_num(intmin,intmax)

(

inti,range;

doublej;

range=max-min;

i=rand();

j二((double)i/(double)RAND_MAX);〃伪数生成函数rand所能返回的最大数值

i=(int)(j*(double)range);

i+=min;

returni;

)

/*初始化数据*/

voidinitO_data(void)

(

inti,j;

n_proc=5;

type_src=3;

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

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

max[i][j]=maxl[i][j];

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

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

allocation[i][j]=allocationl[i][j];

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

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

need[i][j]=needl[i][j];

printf("进程号非法(越界)/n");

gotorequireO;

)

tmp=0;

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

tmp+=need[serial_proc][j];

if(!tmp)〃所有需要的资源数都为0

(

printf("[%d]该进程处在完毕状态/n",serial_proc);

gotorequireO;

)

printf("对[%d]进程洛资源规定：",serial_proc);

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

scanf_s("%d"/&request[serial_proc][j]);

printf(7n");

)

/*请求资源超过需求资源*/

intover_need()

(

intj;

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

if(request[serial_proc][j]>need[serial_proc][j])

(

printf("/t请求资源超过需求资源/n”)；

return1;

)

return0;

)

/*资源申请成功*/

intapply_success(intbe_need,intbe_avail)

(

if(be_need==0&&be_avail==0)

{return1;}

return

}

/*安全性检查*/

intcheck__security()

(

inti,j,tmp;

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

work[j]=available[j];

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

finish[i]=0;

t=0;

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

if(finish。]=:0)/*没有进行安全检查*/

{tmp=1;

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

if(need[i][j]>work[j])

tmp=0;

break;}

if(!tmp)

continue;

else

/*银行家算法*/

voidbankerf)

{intallocation-ttlO],available_t[10],need_t[10];/*临时变量*/

inttmp;

intj;

/*保存当前的资源分派*/

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

(

available_t[j]=available[j];

allocation_t[j]=allocation[serial_proc][j];

need_t[j]=need[serial_proc][j];

)

/*修改available,allocation,need矩阵*/

for(j=0;j<type_src;j++)〃尝试分派资源，成功就分派，不成功就恢复

(

available[j]-=request[serial_proc][j];

need[serial_proc][j]-=request[serial_proc][j];

allocation[serial_proc][j]+=request[serial_proc][j];

)

if(check_security())

{tmp=0;

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

tmp+=need[serial_proc][j];

if(!tmp)

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

available[j]+=allocation[serial_proc][j];

)

else

Ifnr(i—A,r

/*结果输出*/

voidoutput()

(

inti,j;

printf("\n安全序列输出[进程号]：");

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

(

printf("[%d]",index[i]);

)

printf("\n");

printf("最大需求矩阵，己分派矩阵，需求矩阵，可运用矩阵\n“);

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

(

printf("");

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

printf(”％2d”,max[i][j]);

printf("");

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

printf("%2d",allocation。][j]);

printf("");

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

printf("%2d"zneed[i][j]);

printf("");

if(i==serial_proc)

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

,,

printf("%2d/available[j]);

printf("");

printf(n\n");

printf(“本次算法模拟已经完毕！\n");

printf("继续?y/n“)；

if(getchar()=='y')

gotostart;

while(true){}

)

2、页面置换算法

#include"stdio.h"

include"stdlib.h',

typedefstructitem

(

intnum;〃页号

inttime;〃等待时间，LRU算法会用到这个属性

}Pro;

intpageNum;〃系统分派给作业的主存中的页面数

intmemoryNum;〃可用内存页面数

voidprint(Pro*pagel);〃打印当前主存中的页面

intSearch(intnuml,Pro*memoryl);〃在页面集memoryl中查找numl,假如找到,

返回其在memoryl中的下标，否则返回-1

intMax(Pro*memoryl);

intoptimal(intnum,inttag,Pro*memoryl,Pro*pagel);

intmain(void)

(

inti;

intcurmemory;〃调入主存中的页面个数

intmissNum;〃缺页次数

floatmissRate;〃缺页率

page[i].time=0;〃等待时间开始默认为0

)

for(i=0;i<memoryNum;i++)〃初始化内存中页面

(

memory[i].num=-1;〃页面为空用表达

memory[i].time=-1;

)

i=0;

curmemory=0;

crintf/"*************************************************'

printf(uFIFO页面置换算法\n“);

printf("\n")；

missNum=0;

printf("FIFO页面置换情况：\n");

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

(

if(Search(page[i].num,memory)<0)〃若在主存中没有找到该页面

(

missNum++;

memory[curmemory].num=page[i].num;

print(memory);

curmemory=(curmemory+1)%memoryNum;〃先进先出其实是从左到右循

环覆盖

)

}//endfor

missRate=(float)missNum/pageNum;

printf(“缺页次数：%d缺页率：%.2f%%\n",missNum,missRate*100);

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

(

for(intj=0;j<memoryNum;j++)

(

if(memory[j].num>=0)//time是指从上次被访问以来所经历的时间，这里

访问次数加1,所以这里time+1

(

memory[j].time++;I++;

)

)

〃若在主存中没有找到该页面

if(Search(page[i].numzmemory)<0)

(

missNum++；

if(i<memoryNum)

curmemory=i;〃内存未满，直接存入

else

curmemory=Max(memory);〃内存已满，找到离上次访问时间最久的

进行替换

memory[curmemory].num=page[i].num;〃替换操作

memory[curmemory].time=0;

print(memory);

curmemory=(curmemory+1)%memoryNum;

)

else

(

curmemory=Search(page[i].num,memory);

memory[curmemory].time=0;

curmemory=(curmemory+1)%memoryNum;

〃在页面集memoryl中查找numl,假如找到返回其在memoryl中的下标，否则返回-1

intSearch(intnuml,Pro*memoryl)

(

intj;

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

(

if(numl==memoryl[j].num)

returnj;

)

return-1;

)

intMax(Pro*memoryl)〃找到time最大的元素的下标

(

intmax=0;

for(intk=1;k<memoryNum;k++)

(

if(memoryl[k].time>memoryl[max].time)

max=k;

)

returnmax;

}

intoptimal(intnum,inttag,Pro*memoryl,Pro*pagel)

(

intk,j,min[100],min_k;

for(k=0;k<memoryNum;k++)〃初始化

min[k]=500;

for(k=0;k<memoryNum;k++)

{j=tag;

rlc/

3、调度算法

#include”stdio.h"

#defineN50

voidmain()

(

voidsjp();

voidfcfs();

voidsjf();

voidyxj();

inta;

while(true)

(

printf("\n\n");

printf("\t\t/*************************/"p

printf("\n\t\t/*1、先到先服务调度*/")；

printf("\n\t\t/*2、短作业优先调度*/")；

printf("\n\t\t/*3、时间片轮转调度*/")；

printf("\n\t\t/*4、优先级优先调度*/")；

printf("\n\t\t/*0、退出7\n")；

printf(H\t\t/************************

printf("\n\n\t请选择菜单项:\t");

scanf_s(”％d，&a);

printf("\n");

switch(a)

(

case1:fcfs();break;

case2:sjf();break;

case3:sjp();break;

printf(”n\t请重新输入:");

scanf_s("%d",&n);

)

printf("\n\n");

printf(“\t请输入时间片大小(0<sjp):\t");

,,,,

scanf_s(%d,&sjp);

while(sjp<=0)

(

printf("n\t请重新输入:");

scanf_s("%dH,&sjp);

)

structGzuo{