操作系统经典习题 - 图文

.

习题：

1. 进程同步，信号量机制实现

设有6个程序s1,…, s6，它们在并发系统中执行时如图所示的制约关系，试用wait和signal原语来实现它们之间的同步。（10分）

S5 S2 S3 S4 S1

Var a, b, c, d, e, f, g, h; semaphore:= 0, 0, 0, 0, 0, 0, 0; begin

parbegin

begin S1; signal(a); signal(b);signal(c); end; begin wait(a); S2; signal(d); end; begin wait(b); S3; signal(f); end; begin wait(c); S4; signal(g); end;

begin wait(d); S5; signal(e); end;

begin wait(e); wait(f); wait(g); S6; end;

parend end

S6 2. 进程同步，信号量机制实现。详见上课讲的例题 3. 有如下进程，后一个依次比前一个晚一个时间单位到达，

作业 A B C 运行时间 优先级 3 1 2 3 1 5 .

.

D E 1 5 4 6 （1）画出下列调度算法下的调度时间图：FCFS、抢占式\\非抢占式SPF、抢占式\\非抢占式HPF、HRRN和RR（q=1,q=2）

（2）对于上述每种算法，各个作业的周转时间是多少？平均周转时间是多少？

（3）对于上述每种算法，各个作业的带权周转时间和平均带权周转时间各是多少？

相应比=【(等待时间=现在时刻减去到达时间)+服务时间】/服务时间

作业 算法 到达时间 服务时间 完成时间 FCFS 周转时间 带权周转时间 完成时间 SPF(非) 周转时间 带权周转时间 完成时间 SPF(抢) 周转时间 带权周转时间 HPF（非) 完成时间 A 0 3 3 3 1 3 3 1 3 3 1 3 B 1 1 4 3 3 4 3 3 11 10 10 11 C 2 2 6 4 2 7 5 2.5 5 3 1.5 5 D 3 1 7 4 4 5 2 2 12 9 9 12 E 4 5 12 8 1.6 12 8 1.6 10 6 1.2 10 平均 4.4 2.32 4.2 2.02 6.2 4.54 .

.

周转时间 带权周转时间 完成时间 HPF（抢) 周转时间 带权周转时间 完成时间 HRRN 周转时间 带权周转时间 完成时间 RR（r=1） 周转时间 带权周转时间 3 1 11 11 11/3 3 3 1 7 7 7/3 10 10 12 11 11 4 3 3 2 1 1 3 1.5 4 2 1 6 4 2 8 6 3 9 9 10 7 7 7 4 4 5 2 2 6 1.2 9 5 1 12 8 1.6 12 8 1.6 6.2 4.54 7.2 4.72 4.4 2.32 4.8 1.92 4. 作出页式存储管理系统中地址变换机构图。已知某作业页表如下：

0 2 1 5 2 9 3 8 试借助地址变换机构图求出逻辑地址对应的物理地址（1页为1024字节）

(1) 2968 （2）4599 （3）0FCCH

解：分析逻辑地址除以页面大小=商是页号：余数是页内地址偏移 根据页号查找页表中的页号判断是（缺页中断，越界中断...） 物理地址=块号*块大小+地址偏移

.

.

其中十六进制的直接转换为四位二进制计算

1.2968/1024=2...920 物理地址：9*1024+920=10136 2.4599/1024=4...503 越界中断

3.0FCCH二进制为：111111001100/2^10=11...111001100 物理地址：8*1024+972=9164

5. 有一虚拟存储系统，某作业运行中使用的操作数所在的页号依次为：4 3 2 1 4 3 5 4 3 2 5 1 2 4 2 5 3 4 1 5

在内存中为该作业进程开辟3个物理块。分别采用FIFO、LRU页面淘汰算法，图示该作业运行的置换情况，并计算相应的缺页率？ 1.最佳置换算法是置换以后永不使用的页面即“向后看”

4 3 2 1 4 3 5 4 3 2 5 1 2 4 2 5 3 4 1 5 4 4 4 1 1 1 5 5 5 4 4 4 1 3 3 3 4 4 4 2 2 2 5 5 5 2 2 2 3 3 3 1 1 1 3 3

2.FIFO是淘汰最先进入的页面 缺页率：(7/20)*100%=35%

LRU算法是淘汰选择最近久未使用的页面就是“向前看”

4 3 2 1 4 3 5 4 3 2 5 1 2 4 2 5 3 4 1 5 4 4 4 1 1 1 5 2 2 2 2 2 2 4 4 4 3 3 3 4 4 4 4 5 5 4 4 3 3 3 5 2 2 2 3 3 3 3 1 1 5 5 5 1 1

缺页率：(4/20)*100%=20%

6. 假设磁盘有200个磁道（编号为0～199）的移动头磁盘，在完成

.