操作系统课后题 课后作业 第三次作业

660 248

d.40M,20M,10M,的起始地址是

1752 442

b. 011011100000

a. 011011110100

起始地址 长度（字节）

80M,230M,360M.

7.14. 在一个简单分段系统中，包含如下段表：

a. 如果块大小为4，它的伙伴的二进制地址为多少？

b. 如果块大小为16，它的伙伴的二进制地址为多少？

7.8. 考虑一个伙伴系统，在当前分配下的一个特定块地址为011011110000.

址是20M.10M的块的起始地址是120M。b.40M,20N,10M的起始地址分别为230M,20M和160M.

指出给这三个需求分配的块的起始地址。a.首次适配b.最佳适配c.临近适配（假设最近添加的块位于内

7.6. 如果使用动态分区方案，下图所示为在某个给定的时间点的内存配置：阴影部分为已经被分配的

存的开始）d.最坏适配答：a.40M的块放入第2个洞中,起始地址是80M.20M的块放入第一个洞中.起始地

块；空白部分为空闲块。接下来的三个内存需求分别为40MB，20MB和10MB。分别使用如下几种放置算法，

c.40M,20M,10M的起始地址是80M,120160M.

解答

解答

答：

996 604

222 198

（i）1052

5 1 0 1 0

3 1 0 0 2

1 1 1 1 7

0 1 1 0 4

e. 0，222

d. 3，444

c. 1，530

b. 2，256

a. 0，198

4 0 0 0 —

2 0 0 0 —

（ii）2221

（iii）99

e. 660+222=882.

d. 996+444=1440

b. 222+156=378

表的大小为一个页。

a．页表一共需要使用几级？

c. 段1长度为422,所以会发生错误

a. 段0定位在660,所以我们有物理地址660+190=858.

并且所有的地址都是内存字节地址。页尺寸为1024个字节。

b． 下列虚拟地址对应于哪个物理地址（不用考略页错误）？

b．每一级页表的大小是多少？提示：一个页表的大小比较小。

(iii)99=5*1024+379 对应的页帧号为0 因此物理地址是379

a． 描述CPU产生的虚拟地址通常是如何转化成一个物理主存地址的。

b:(i)1052=1024+28 查表对应的页帧号是7，因此物理地址为7*1024+28=7196

对如下的每一个逻辑地址，确定其对应的物理地址或者说明段错误是否会发生：

包含210/4=2，因此每个页表可以包含22bit中的8个bit，所以需要三级索引。

c．在第一级使用的页较小与在最底下一级使用的页较小相比，那种策略使用最小个数的页？

a：由虚拟地址求得页号和偏移量，用虚拟页号作为索引页表，得到页帧号，联系偏移量得到物理地址

a：虚拟内存可以分为232/210= 222页，所以需要22个bit来区别虚拟内存中的一页，每一个页表可以

8.2 考虑一个使用32位的地址和1KB大小的页的分页虚拟内存系统。每个页表项需要32位。需要页

8.1 假设在处理器上执行的进程的也表如下所示。所有数字均为十进制数，每一项都是从0开始记数的，

(ii)2221=2*1024+173 此时出现页错误

虚拟页号 有效位 访问位 修改位 页帧号

b：第二级页表有28个页表项，第一级页表有26个页表项。

c：如果顶层有26个页表项将会减少使用空间，在这种情况下，中间层页表有26个并且每个都有28个页表项，底层有214个页并且每个都有28个页表项，因此共有1+26+214页=16,449页。如果中间层有26个页表项，那么总的页数有1+28+214页=16,1页。如果底层有26个页表项，那么总的页表数是1+28+216页=65,973页。

8.4 一个进程分配给4个页帧（下面的所有数字均为十进制数，每一项都是从0开始计数的）。上一次把一页装入到一个页帧的时间，上一次访问页帧中的页的时间，每个页帧中的虚拟页号以及每个页帧的访问位（R）和修改位（M）如下表所示（时间均为从进程开始到该事件之间的时钟时间，而不是从事件发生到当前的时钟值）。

虚拟页号 页帧 加载时间 访问时间 R位 M位2 0 60 161 0 11 1 130 160 1 00 2 26 162 1 03 3 20 163 1 1a.FIFO（先进先出）算法b.LRU（最近最少使用）算法c.Clock算法

d.最佳（使用下面的访问串）算法

当虚拟页4发生错误时，使用下列内存管理策略，哪一个页帧将用于置换？解释原因。

e.在页错误之前给定上述内存状态，考虑下面的虚拟页访问序列： 4,0,0,2,4,2,1,0,3,2解答

a:页帧3，在时间20加载，时间最长。b:页帧1，在时间160访问距现在时间最长。为0。

e:一共有6个错误，如下

如果使用窗口大小为4的工作集策略来代替固定分配，会发生多少页错误？每个页错误何时发生？

c:清除页帧3的R位（最早加载），清除页帧2的R位，（次最早加载），换出的是页帧0因为它的R位d:换出的是页帧3中的虚拟页3，因为它将最晚被访问到。

8.6一个进程在磁盘上包含8个虚拟页，在主存中固定分配给4个页帧。发生如下顺序的页访问： 1,0,2,2,1,7,0,1,2,0,3,0,4,5,1,5,2,4,5,6,7,6,7,2,4,2,7,3,3,2,3a.如果使用LRU替换策略，给出相继驻留在这4个页帧中的页。计算主存的命中率。假设这些帧最初是空的。b.如果使用FIFO策略，重复问题（a）。c.比较使用这两种策略的命中率。解释为什么这个特殊的访问顺序，使用FIFO的效率接近于LRU。解答a:LRU：命中率=16/33

b:FIFO：命中率=16/33

a.8×2K=16kb.16K×4=Kc.232=4GBytes

c:这两种策略对这个特殊的页轨迹（执行顺序）是等效的。

8.17假设一个任务被划分为4个大小相等的段，并且系统为每个段建立了一个有的页描述符表。因

间最大为多少？c.假设该任务访问到物理单元00021ABC中的一个元素，那么为它产生的逻辑地址的格式

此，该系统是分段与分页的组合。假设页尺寸为2KB。a.每段的最大尺寸为多少？b.该任务的逻辑地址空

是什么？该系统的物理地址最大为多少？解答

AAAAAAAAEDCBA FCFS AAABAAAAAACCBBBCCBCBBBBABBBBBB931012BBCCB到达时间BBCBCBBBDCDDDBDDDDDDDDEEDDDDDD55253处理时间DDEEDEEEDEEEEEEEEEDEEEDEEEEEEE进程名 BBAAAAACBTfTaTr Ts CBB9.1考虑下面的进程集合：Feedback, q=1 Feedback, q=2(i) 第一到第八行依次是FCFS RR, q=1 RR, q=4 SPN SRT HRRN 每格代表一个时间单位，方框中的数表示当前运行的进程 3.50 7.00 C 对这个集合，给出类似于表9.5和图9.5的分析。Tr/Ts 330BCB1.00 3.00 A BAB851CBB1.40 7.00 B BBC23BDC10 DBD59DDD151.20 6.00 D DED DDD20 512E 1.60 8.00 DEDEDE1.746.20EEEDDEEEEEEERR q = 1 Tf 6.00 Tr/Ts

11.00 8.00 18.00 20.00

1.60 8.00 1.60 8.00 1.60 8.00 1.60 20.008.00 1.60 8.00 1.60 8.00 1.60

6.201.747.401.857.001.811.987.201.885.601.325.601.32

Tr 6.00 10.00 5.00 9.00 8.00 7.60

2.00 3.00 1.00 3.00 1.00 3.00 1.00 3.00 3.00 1.00 7.00 2.33 4.00 1.33 4.00 Tr

Tr/Ts

7.00 3.00 Tr Tr/Ts

HRRN

Tf Tr Tr/Ts

FB q = 1 Tf

Tr Tr/Ts

FB q = 2i

Tf

3.00 Tr Tr/Ts

SRT

Tf

2.00 9.00 1.80 9.00 1.80 9.00 1.80 8.00 7.00 1.40 10.00 2.00 9.00 1.80

2.50 6.00 3.00 2.00 1.00 2.00 1.00 10.00 7.00 3.50 3.00 1.50 5.00 2.50

1.80 10.00 2.00 6.00 1.20 6.00 1.20 15.00 6.00 1.20 9.00 1.80 9.00 1.80

RR q = 4 Tf

Tr

3.00 Tr/Ts

10.00 9.00 19.00 20.00

SPN Tf 10.005.00 15.00 20.00

10.00 5.00 15.00 20.00

11.00 6.00 18.00 20.00

10.00 8.00 18.00 20.00

9.16 5个批作业，从A到E，同时到达计算机中心。它们的估计运行时间分别为15，9，3，6和12分钟，它们的优先级（外部定义）分别为6，3，7，9和4（值越小，表示的优先级越高）。对下面的每种调度算法，确定每个进程的周转时间和所有作业的平均周转时间（忽略进程切换的开销），并解释是如何得到这个结果的。对于最后三种情况，假设一次只有一个作业运行直到它结束，并且所有作业都完全是受处理器的。

a．时间片为1分钟的轮转法。b．优先级调度

c．FCFS（按15，9，3，6和12顺序运行）。d．最短作业优先

a: 时间片为1分钟的轮转法：1A B CA B CAAA BA B A BA BA BA A

DBB

2DDC

3EEDDDE

4510EEE27EEEEE

30333638401519235

Elapsed time

963EDCBA973AAA 15AEBDCDCAEB27 + 6 = 3324 + 3 = 2715 + 9 = 2433 + 12 = 43393 + 6 = 99 + 9 = 1839 + 6 = 4536 + 3 = 399 + 12 = 2130 + 15 = 4518 + 12 = 3021 + 15 = 3615d.c.12 b. Time 表10.5 习题10.1的执行简表A=45 min , B=35 min , C=13 min , D=26 min , E=42 min 进程 到达时间 执行时间 完成最后期限10.1考虑一组周期任务（3个），表10.5给了它们的执行简表。按照类似与图10.5的形式，给出关于这组任务的调度图。每个进程的周转时间Job Turnaround TimeE42Running Job Turnaround TimePriority Job Turnaround Time平均周转时间是(9+21+36+39+45)/5=30 min 平均周转时间是 (45+35+14+26+42)/5=32.2 min平均周转时间是: (3+9+18+30+45) / 5 = 21 min平均周转时间是(15+24+27+33+45) / 5 = 28.8 min A(1) 0 10 20 A(2) 20 10 40 . . . . . . . . . . . . B(1) 0 10 50 B(2) 50 10 100 . . . . . . . . . . . . C(2) 50 15 100 . . . . C(1) 0 15 50答：对于固定的优先级来说，我们以优先级是ABC来考虑这道题。每一方格代表五个时钟单元，方格里的字母是指现在正在运行的进程。第一行是固定的优先级；第二行表示的是使用完成最后期限的最早最后期限调度。表格如下：AAAAB B BBAAACCCCAACAABABBABAACACCACACAA对于固定优先级调度来说，进程C总是错过它的最后期限。10.2 考虑一组非周期性任务（5个），表10.6给出了它们的执行简表。按照类似于图10.6的形式给出关于这组任务的调度图。 表10.6 习题10.2的执行简表 进程 到达时间 执行时间 启动最后期限 A 10 20 100 B 20 20 30 C 40 20 60 D 50 20 80 E 60 20 70答：每一方格代表10个时间单元。最早期限有自愿空闲时间的最早期限先来先服AAABABCCCCCCEEDEEDDDDDAA10.3 这个习题用于说明对于速率单调调度，式（10.2）是成功调度的充分条件，但它并不是必要条件[也就是说，有些时候，尽管不满足式（10.2）也可能成功调度]。 任务P2: C2=30; T2=145

任务P1：C1=20; T1=100

c.

务是可以成功调度的。

任务P3: C3=68; T3=150

式（10.2）可以满足吗？

b.现在再往集合里增加以下任务：

D1=100; D2=145; D3=150

a.考虑一个任务集，它包括以下的周期任务：

使用速率单调调度，这些任务可以成功地调度吗？

b. 所有任务的使用率是0.86，已经超过界限0.779。

C．假设前述的三个任务的第一个实例在t=0是到达，并假设每个任务的第一个最后期限如下：

如果使用速率单调调度，请问这三个最后期限都能得到满足吗？每个任务循环的最后想、期限是多少？

20＋30＋68＝118。但是P1在一附加的时间区间（0，118）内初始化。因此P3直到

可以观察到在P3执行前P1，P2必须至少执行一次。因此P3的第一次瞬间完成时间不低于

答：a. P1, P2的总使用率是0.41，小于由方程10.2给出的对于两个任务的界限0.828，因此这两个任

118＋20＝138才完成他的第一次执行。在P3的期限内。继续这个过程，我们可以知道，这三个

任务的所有期限都能实现。