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



 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.        d.40M,20M,10M,的起始地址是80M,230M,360M.       

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=2，因此每个页表可以包含22bit中的8个bit，所以需要三级索引。

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

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

 

9.1考虑下面的进程集合：

进程名	到达时间	处理时间
A	0	3
B	1	5
C	3	2
D	9	5
E	12	5

对这个集合，给出类似于表9.5和图9.5的分析。

每格代表一个时间单位，方框中的数表示当前运行的进程               

A

A

A

B

B

B

B

B

C

C

D

D

D

D

D

E

E

E

E

E

A

B

A

B

C

A

B

C

B

D

B

D

E

D

E

D

E

D

E

E

A

A

A

B

B

B

B

C

C

B

D

D

E

D

E

E

E

E

D

E

A

A

A

C

C

B

B

B

B

B

D

D

D

D

D

E

E

E

E

E

A

A

A

C

C

B

B

B

B

B

D

D

D

D

D

E

E

E

E

E

A

A

A

B

B

B

B

B

C

C

D

D

D

D

D

E

E

E

E

E

A

B

A

C

B

C

A

B

B

D

B

D

E

D

E

D

E

D

E

E

A

B

A

A

C

B

B

C

B

B

D

D

D

D

D

E

E

D

E

E

第一到第八行依次是FCFS   RR, q=1  RR, q=4  SPN  SRT  HRRN  

Feedback, q=1   Feedback, q=2(i)  

                     A        B        C        D         E  

Ta         0         1         3         9         12

Ts          3         5         2         5          5

FCFS         Tf         3         8         10         15          20

Tr          3.00     7.00     7.00     6.00     8.00     6.20

Tr/Ts     1.00     1.40     3.50     1.20     1.60     1.74

RR q = 1     Tf         6.00     11.00     8.00     18.00     20.00

Tr 6.00 10.00 5.00 9.00 8.00 7.60

Tr/Ts     2.00     2.00     2.50     1.80     1.60     1.98

RR q = 4     Tf         3.00     10.00     9.00     19.00     20.00

Tr         3.00     9.00     6.00     10.00     8.00     7.20

Tr/Ts     1.00     1.80     3.00     2.00     1.60     1.88

SPN         Tf         3.00     10.00    5.00     15.00     20.00

Tr         3.00     9.00     2.00     6.00     8.00     5.60

Tr/Ts     1.00     1.80     1.00     1.20     1.60     1.32

SRT         Tf         3.00     10.00     5.00     15.00     20.00

Tr         3.00     9.00     2.00     6.00     8.00     5.60

Tr/Ts     1.00     1.80     1.00     1.20     1.60     1.32

HRRN         Tf         3.00     8.00     10.00     15.00     20.00

Tr         3.00     7.00     7.00     6.00     8.00     6.20

Tr/Ts     1.00     1.40     3.50     1.20     1.60     1.74

FB q = 1     Tf         7.00     11.00     6.00     18.00     20.00

Tr         7.00     10.00     3.00     9.00     8.00     7.40

Tr/Ts     2.33     2.00     1.50     1.80     1.60     1.85

FB         Tf         4.00     10.00     8.00     18.00     20.00

q = 2i        Tr         4.00     9.00     5.00     9.00     8.00     7.00

Tr/Ts     1.33     1.80     2.50     1.80     1.60     1.81

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    4    5    Elapsed time

A  B     C    D    E    5

A  B     C    D    E    10

A    B    C    D    E    15

A    B        D    E    19

A  B            D    E    23

A  B         D    E    27

A  B                E    30

A  B                E    33

A  B                E    36

A                  E    38

A                E    40

A                E    42

A                    43

A                    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            B            9

4            E            9 + 12 = 21

6            A            21 + 15 = 36

7            C            36 + 3 = 39

9            D            39 + 6 = 45

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

c.

Job     Turnaround Time

A        15

B        15 + 9 = 24

C        24 + 3 = 27

D        27 + 6 = 33

E        33 + 12 = 45

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

d.

Running     Job     Turnaround Time

Time

3            C            3

6            D            3 + 6 = 9

9            B            9 + 9 = 18

12             E            18 + 12 = 30

15            A            30 + 15 = 45

平均周转时间是: (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

B

B

A

A

C

C

A

A

B

B

A

A

C

C

A

A

A

A

B

B

A

C

C

A

C

A

A

B

B

A

A

C

C

C

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个时间单元。

最早期限

A

A

C

C

E

E

D

D

有自愿空闲时间的最早期限

B

B

C

C

E

E

D

D

A

A

先来先服

A

A

C

C

D

D

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

    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的期限内。继续这个过程，我们可以知道，这三个任务的所有期限都能实现。