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

7.6. 如果使用动态分区方案，下图所示为在某个给定的时间点的内存配置：阴影部分为已经被分配的块；空白部分为空闲块。接下来的三个内存需求分别为40MB，20MB和10MB。分别使用如下几种放置算法，指出给这三个需求分配的块的起始地址。a.首次适配b.最佳适配c.临近适配（假设最近添加的块位于内存的开始）d.最坏适配答：a.40M的块放入第2个洞中,起始地址是80M.20M的块放入第一个洞中.起始地址是20M.10M的块的起始地址是120M。b.40M,20N,10M的起始地址分别为230M,20M和160M.

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

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

7.8. 考虑一个伙伴系统，在当前分配下的一个特定块地址为011011110000. a. 如果块大小为4，它的伙伴的二进制地址为多少？ b. 如果块大小为16，它的伙伴的二进制地址为多少？ 答：

a. 011011110100 b. 011011100000

7.14. 在一个简单分段系统中，包含如下段表： 起始地址 长度（字节） 660 248

1752 442 222 198 996 604

对如下的每一个逻辑地址，确定其对应的物理地址或者说明段错误是否会发生： a. 0，198 b. 2，256 c. 1，530 d. 3，444 e. 0，222 答：

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

c. 段1长度为422,所以会发生错误 d. 996+444=1440 e. 660+222=882.

8.1 假设在处理器上执行的进程的也表如下所示。所有数字均为十进制数，每一项都是从0开始记数的，并且所有的地址都是内存字节地址。页尺寸为1024个字节。 虚拟页号 有效位 访问位 修改位 页帧号 0 1 1 0 4 1 1 1 1 7 2 0 0 0 — 3 1 0 0 2 4 0 0 0 — 5 1 0 1 0

a． 描述CPU产生的虚拟地址通常是如何转化成一个物理主存地址的。 b． 下列虚拟地址对应于哪个物理地址（不用考略页错误）？ （i）1052 （ii）2221 （iii）5499 解答

a：由虚拟地址求得页号和偏移量，用虚拟页号作为索引页表，得到页帧号，联系偏移量得到物理地址 b:(i)1052=1024+28 查表对应的页帧号是7，因此物理地址为7*1024+28=7196 (ii)2221=2*1024+173 此时出现页错误

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

8.2 考虑一个使用32位的地址和1KB大小的页的分页虚拟内存系统。每个页表项需要32位。需要限制页表的大小为一个页。 a．页表一共需要使用几级？

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

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

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

含210/4=28项，因此每个页表可以包含22bit中的8个bit，所以需要三级索引。 b：第二级页表有28个页表项，第一级页表有26个页表项。

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

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

虚拟页号 页帧 加载时间 访问时间 R位 M位 2 0 60 161 0 1 1 1 130 160 1 0 0 2 26 162 1 0 3 3 20 163 1 1

当虚拟页4发生错误时，使用下列内存管理策略，哪一个页帧将用于置换？解释原因。 a.FIFO（先进先出）算法 b.LRU（最近最少使用）算法 c.Clock算法

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

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

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

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

c:清除页帧3的R位（最早加载），清除页帧2的R位，（次最早加载），换出的是页帧0因为它的R位为0。

d:换出的是页帧3中的虚拟页3，因为它将最晚被访问到。 e:一共有6个错误，如下

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/33c:这两种策略对这个特殊的页轨迹（执行顺序）是等效的。

8.17假设一个任务被划分为4个大小相等的段，并且系统为每个段建立了一个有8项的页描述符表。因此，该系统是分段与分页的组合。假设页尺寸为2KB。a.每段的最大尺寸为多少？b.该任务的逻辑地址空间最大为多少？c.假设该任务访问到物理单元00021ABC中的一个元素，那么为它产生的逻辑地址的格式是什么？该系统的物理地址最大为多少？解答

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

9.1考虑下面的进程集合： 进程名 A B C D E 到达时间 0 1 3 9 12 处理时间 3 5 2 5 5 对这个集合，给出类似于表9.5和图9.5的分析。

每格代表一个时间单位，方框中的数表示当前运行的进程 A A A A A A A A A B A A A A B B A A A A A A A A B B B C C B C A B C B C C B B C B A B B B B C B B B B B B B A B B C C B B B B C C B C B B C B B C D B B B C D B D B D D D D B D D D D D D D D D D E E D D D E D D D D D D D D D D E E D D D E D E D E E E E D E E E E E E E E E E D E E E E D D E E D E E E E E E E E E E E E E 第一到第八行依次是FCFS RR, q=1 RR, q=4 SPN SRT HRRN Feedback, q=1 Feedback, q=2(i)

A 0 3 3

B 1 5 8

C 3 2

D 9 5

E 12 5 8.00 1.60

6.20 1.74

Ta Ts

FCFS

Tf Tr Tr/Ts

10 7.00 3.50

15 20 6.00 1.20

3.00 1.00

7.00 1.40

RR q = 1 Tf 6.00 11.00 8.00 18.00 20.00

1.60 8.00 1.60 8.00 1.60 8.00 1.60 20.00 8.00 1.60 8.00 1.60 8.00 1.60

6.20 1.74 7.40 1.85 7.00 1.81 1.98 7.20 1.88 5.60 1.32 5.60 1.32

Tr 6.00 10.00 5.00 9.00 8.00 7.60 Tr/Ts

RR q = 4 Tf

Tr Tr/Ts

SPN

Tf

Tr Tr/Ts

SRT

Tf

Tr Tr/Ts

HRRN

Tf Tr Tr/Ts

FB q = 1 Tf

Tr Tr/Ts

FB q = 2i

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分钟的轮转法： 1

2

3 E E D D D E

4 5 10 E E E 27 E E E E E

30 33 36 38 40 15 19 23 5

Elapsed time

A B C D A B C D A A

B B

C D Tf

Tr Tr/Ts

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

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

3.00

10.00

9.00

19.00

20.00

3.00 10.00 5.00 15.00 20.00

3.00 10.00 5.00 15.00 20.00

7.00 11.00 6.00 18.00 20.00

4.00 10.00 8.00 18.00 20.00

A B A B A B A B A B A A

A A A

E

42 43 45

每个进程的周转时间

A=45 min , B=35 min , C=13 min , D=26 min , E=42 min 平均周转时间是 (45+35+14+26+42)/5=32.2 min b.

Priority Job Turnaround Time 3 4 6 7 9 c.

Job Turnaround Time A B C D E d.

Running Job Turnaround Time Time 3 6 9

C D B E A

3

3 + 6 = 9 9 + 9 = 18 18 + 12 = 30 30 + 15 = 45

15

15 + 9 = 24 24 + 3 = 27 27 + 6 = 33 33 + 12 = 45

B E A C D

9

9 + 12 = 21 21 + 15 = 36 36 + 3 = 39 39 + 6 = 45

平均周转时间是(9+21+36+39+45)/5=30 min

平均周转时间是(15+24+27+33+45) / 5 = 28.8 min

12 15

平均周转时间是: (3+9+18+30+45) / 5 = 21 min

10.1考虑一组周期任务（3个），表10.5给了它们的执行简表。按照类似与图10.5的形式，给出关于这组任务的调度图。

表10.5 习题10.1的执行简表

进程 到达时间 执行时间 完成最后期限 A(1) 0 10 20 A(2) 20 10 40 . . . . . . . . . . . . B(1) 0 10 50 B(2) 50 10 100 . . . . . . . . . . . . C(1) 0 15 50 C(2) 50 15 100 . . . .

答：对于固定的优先级来说，我们以优先级是ABC来考虑这道题。每一方格代表五个时钟单元，方格里的字母是指现在正在运行的进程。第一行是固定的优先级；第二行表示的是使用完成最后期限的最早最后期限调度。表格如下： A A

对于固定优先级调度来说，进程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个时间单元。 最早期限 有自愿空闲时间的最早期限 先来先服

10.3 这个习题用于说明对于速率单调调度，式（10.2）是成功调度的充分条件，但它并不是必要条件[也就是说，有些时候，尽管不满足式（10.2）也可能成功调度]。

A A A B A B C C C C C C E E D E E D D D D D A A A A B B B B A A A C C C C A A C A A B A B B A B A A C A C C A C A C A A a.考虑一个任务集，它包括以下独立的周期任务： 任务P1：C1=20; T1=100 任务P2: C2=30; T2=145

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

b.现在再往集合里增加以下任务： 任务P3: C3=68; T3=150 式（10.2）可以满足吗？

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

如果使用速率单调调度，请问这三个最后期限都能得到满足吗？每个任务循环的最后想、期限是多少？ 答：a. P1, P2的总使用率是0.41，小于由方程10.2给出的对于两个任务的界限0.828，因此这两个任务

是可以成功调度的。

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

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

＋68＝118。但是P1在一附加的时间区间（0，118）内初始化。因此P3直到118＋20＝138才完成他的第一次执行。在P3的期限内。继续这个过程，我们可以知道，这三个任务的所有期限都能实现。

本文来源：https://www.bwwdw.com/article/riu3.html