操作系统算法.docx

例子：T0时刻的资源分配情况

假定系统中有四个进程P1,P2,P3,P4和三种类型的资源R1,R2,R3，每一种资源的数量分别

为9、3、6,T0时刻的资源分配情况如表2.4所示:

Max

Allocation

Need

Available

R

R

2

R

3

R1

R2

R3

R

R

2

R

3

R

R

2

R

3

P1

3

1

0

0

2

0

P2

6

1

3

6

1

2

0

0

1

P3

3

1

4

2

1

1

1

0

3

P4

4

2

2

0

0

2

4

2

0

利用安全性算法，分析T0时刻的资源分配情况，可得如表2.5所示的信息。

从T0时刻的安全性分析可知，T0时刻存在着一个安全序列P2,P1，P4,P3,故T0时刻系统是安全的。

假设T0时刻，进程P1申请资源，其请求向量为Request1(0,0,1),系统按银行家算法进行检查：

Requestl(0,0,1)WNeed1(2,2,2)，且

Requestl(0,0,1)WAvailable(0,1,1)

故，系统试探性地为P1分配资源，并修改Available,Allocation1和Need1向量如表2.6所示

10.地址映射问题例题：

例1.已知某分页系统，主存容量为64K,页面大小为1K,对一个4页大的作业，其0,1，2，3页分别被分配到主存的2，4，6，7块中。请将十进制的逻辑地址1023、2500、3500、4500转换成物理地址。

计算公式：物理地址哄号*页面大小+块内地址

逻辑地址1023：

页号：1023/1024=0

页内地址：1023

页号

炽

Q

2

1

4

2

6

3

1

瓦表

对应物理块号，2

故物理地址为：2*1024+1023=3071

逻辑地址2500:

页号：2500/1024=2

对应物理块号：6

页内地址：452

故物理地址为：6*1024+452=6596

计算公式：物理地址=块号*页面大小+块内地址

逻辑地址3500:

页号：3500/1024=3

对应物理块号：7

I页内地址：428

故物理地址为：7*1024+428=7596

逻辑地址4500:

动态分配算法笠匚1024=4

越界

动态划分与分配算法（续）

例如,如图3.6

-有一个128MB的内存，其中操作系统自身占用

8MB,剩下的120MB空间供用户进程使用。

?依次装入进程P1、P2、P3、P4、P5、P6,剩下一个10MB的空闲分区。

-一段时间之后，进程P1、P3、P5执行结束，释

放出3个空闲分区。内存中共有4个空闲分区，

囹3.7动态划分的I种分算法

例二：?对于一个将页表存放在内存中的分页系统：

（1） 如果访问内存需要0.2%s有效访问时间为多少？

（2） 如果加一快表，且假定在快表中找到页表项的几率高达90%，则有效访问时间又是多少（假定查快表需花的时间为0）？

解：（1）需两次访问内存，故有效访问时间为：

2*0.2gs=0.4gs

（2）若能从快表中直接找到相应的页表项，则可立即形成物理地址去内存访问相应的数据;

否则，仍需两次访问内存。有效访问时间为：

0.9*0.2+（1-0.9）*0.2*2=0.22*

例三：在一个分段式存储管理系统中，其段表见表1。求表2中逻辑地址对应的物理地址

在一个分段式存储管理系硕:套段表见表私求表2中

-C

【例3

j逻辑地址对应的物理地址

O-

解:

⑴由表1知，段号为0的段的内存起始地址为210,段长为500。由表2知，逻辑地址的段内位移为430。因为43（X500,所以该融地址是吝法也其对应的物理地址为：

1210+430=640

⑵由表1知，段号为1的段的内存起始地址为2350,段长为20.由表2知，逻辑地址的段内位彗为10.

因为10C20，所以该逻辑地址是合法的。箕对应的物理地址为：

2350+10=2360

⑶由表1知，段号为2的段的内存起始地址为1。0,

^500Q

段长为90。由表2知，逻辑地址的段内位移为500,因为50090即逻辑地址的段内位移500已超忌了段长90,所以该逻辑地址是非法的。

思考题：

1、某系统采用页式存储管理策略，拥有逻辑空间32页，每页2K，拥有物理空间1M。

（1） 写出逻辑地址的格式；

（2） 若不考虑访问权限等，进程的页表有多少项？每项至少有多少位？

（3） 如果物理空间减少一半，页表结构应相应作怎样的改变？

：（1）该系统拥有谡辑空间32页，故逻辑地址中:I页号必须用5位来描述;而每页为2K,因此『页内

i地址必须用11位描述，这样可得到它的谡辑地iI址格衣口下： I

I15 11|10 0

, 二 ； 6

员内地址

（2）每个进程最多有32个页面，因此，进程的页表项最多为32