《操作系统精髓与设计原理·第五版》习题答案(9)

剩余等待服务时间，如果现在有一个进程正在执行。这个值可以表示成为ρ × Ts，ρ是利用，因此一个进程正在服务的概率。Ts正如我们已证明是预计等待服务的时间。，因此，我们有

9.10一个处理器被就绪队列中的所有进程以无限的速度多路复用，且没有任何额外的开销（这是一个在就绪进程中使用轮转调度的理想模型，时间片相对于平均服务时间非常小）。说明对来自一个无限源的泊松输入和指数服务时间，一个进程的平均响应时间Rx和服务时间x由式Rx=x/(1-ρ)给出。

让我们把时间片在轮转调度中记为δ 。在这个问题中，δ相对于服务时间很小。现在，考虑一个新来的进程，它排在就绪队列的最后。我们假设这一特定的进程的服务时间为X ，是δ的

一些倍数：x = mδ。首先，让我们回答一个问题，多少时间花费在进程得到服务前的等待队列中。它必须等待所有排在它之前的q个进程结束服务后，从而初步等待时间= q δ。Q则是等待队列中的平均进程数目。现在，我们可以计算总时间花费在收到x秒钟的服务之前的等待时间。因为它必须经过队列m次，而每一次他们等待q δ秒，其总等待时间分列如下：

然后，响应时间是指等待时间和总服务时间Rx= wait time + service time= qx + x = (q + 1) x。谈到排队的公式，在附录A ，是指物品的数量，该系统的Q可表示为： Q=ρ/(1-ρ),则Rx=[ρ/(1-ρ)+1]*x=(x/1-ρ)*Rx=[ρ/(1-ρ)+1]*x=x/(1-ρ)

9.11大多数轮转调度器使用大小固定的时间片。给定支持小时间片的参数。现在给定一个支持大的时间片的参数。比较并对比两个参数所适用的系统和作业的类型。存在两种参数都合理的情况吗？ 一个论点主张一个小时间片：用一个小时间片会加强反应能力，多次运行的所有进程进行了短暂的时间片。当就绪队列有许多流程，这是互动性，反应能力是非常重要的如：一般用途的计算机系统。 一个论点主张一个大的时间片：利用大型公司将提高吞吐量和CPU利用率测量方面的实际工作，因为那里是不足的背景下切换，从而减少开销。

一个系统，其中既可能是适当的：有一些制度，即无论是中小企业还是大广，是合理的。例如：很长的行业，需要在短短数用户互动。虽然这种类型的工作可以被视为一个批处理工作，在某种意义上来说，它仍然需要与用户手中。因此，在时代的时候，有没有使用者之间的相互作用，时间片可能会增加优化，并在整个过程中的互动时间，时间片可能降至提供更好的应变能力。

9.12在排队系统中，新作业在得到服务之前必须等待一会儿。当一个作业等待时，它的优先级从0开始以速度α线形增加。一个作业一直等待到它的优先级达到正在运行中的作业的优先级，然后它开始与其他正在运行的作业使用轮转法平等地共享处理器，与此同时，它的优先级继续以比较慢的速度β增长。这个算法称为自私轮转法，因为在运行中的作业试图通过不断地增加它的优先级来垄断处理器。

首先，我们需要厘清意义的参数λ ' 。速度在项目到达第一盒（ \队列\专栏）是λ 。两个相邻的来港人士，以第二个选项（ \服务\的框） ，将得出一个稍微减慢，因为第二项是延迟其追逐的第一个项目。我们可以计算出垂直偏移Y的数字，在两种不同方式的基础上，几何形状的图表：

9.13一个使用轮转调度和交换的交互式系统，试图按如下方式对普通的请求给出有保证的响应：在所有就绪进程中完成一次轮转循环后，系统通过用最大响应时间除以需要服务的进程数目，确定在下一个循环中分配给每个就绪进程的时间片。请问是否是合理的解释？

只是，只要有相对很少有用户在该系统内。当时间片变小，以满足更多用户迅速两件事情发生： （ 1 ）处理器利用率下降，以及（ 2 ）在某一个点，时间片变得太小，以满足最琐碎的请求。用户将经历一个突然增加的响应时间，因为他们的要求，必须经过轮转调度好几次。

9.14多级反馈排队调度对哪种类型的进程有利，是受处理器限制的进程还是受I/O限制的进程？请简要说明原因。

41

如果一个进程占用过多处理器时间，它将会被移到一个低优先级的队列中。这会使受I/O限制的进程留在优先级高的队列中。

9.15在基于优先级的进程调度中，如果当前没有其他优先级更高的进程处于就绪状态，调度器将把控制给一个特定的进程。假设在进行进程调度决策时没有使用其他信息，还假设进程的优先级是在进程被创建是建立的，并且不会改变。在这样的系统中，为什么使用Dekker方法解决互斥问题是非常“危险”的？通过说明会发生什么和如何发生来解释该问题。

dekker的算法依靠的是对公平性的硬件和操作系统。使用的优先次序的风险饥饿如下。可能有这样的情况，如果出生是一种很快速的反复过程，因为它不断地发现Flag[ 1 ] =虚假的，不断进入其关键路段，而在P1，离开内部回路，它正在等待它反过来又可以不设置Flag[ 1 ]为真实，阻止这样做出生的读变量（记得进入该变发生下相互排斥）

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

42

c. Job A B C D E

Turnaround Time 15

15 + 9 = 24 24 + 3 = 27 27 + 6 = 33 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章 多处理器和实时调度

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 43

D 50 20 80 E 60 20 70 答：每一方格代表10个时间单元。

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的期限内。继续这个过程，我们可以知道，这三个任务的所有期限都能实现。 10.4 画一个与图10.9（b）相似的图，用来显示队同一个例子使用优先级置顶的事件顺序。 最早期限 A A C C E E D D 44

一旦T3进入他的临界区 ，他的优先级就被指定为高于T1。当T3离开他的临界区时，他被T1抢先。

第11章 I/O管理和磁盘调度

11.1考虑一个程序访问一个I/O设备，并比较无缓冲的I/O和使用缓冲区的I/O。说明使用缓冲区最多可

以减少2倍的运行时间。

如果计算的时间正好等于它的I/O时间（它是最佳环境），操作者和外围设备同时运行。如果单独运行，只要花费他们的一半时间，设C是整个程序的计算时间，T为所要求总的I/O时间，因而寄存器最好的运行时间是 max(C,T)，不需要寄存器的运行时间是C+T， 显然（(C+T)/2）≤max(C,T)≤(C+T).

11.2把习题11.1的结论推广到访问n个设备的程序中。 最佳比是（n+1）﹕n

11.3使用与表11.2类似的方式，分析下列磁道请求：27，129，110，186，147，41，10，64，120。假设

磁头最初定位在磁道100处，并且沿着磁道号减小的方向移动。假设磁头沿着磁道增大的方向移动，请给出同样的分析。 FIFO 下一个被访问的磁道 27 129 110 186 147 41 10 64 120 平均寻道横跨的磁道数 73 102 19 76 39 106 31 54 56 61.8 SSTF 下一个被访问的磁道 110 120 129 147 186 64 41 27 10 平均寻道横跨的磁道数 10 10 9 18 39 122 23 14 17 29.1 SCAN 下一个被访问的磁道 64 41 27 10 110 120 129 147 186 平均寻道横跨的磁道数 36 23 14 17 100 10 9 18 39 29.6 C-SCAN 下一个被访问的磁道 64 41 27 10 186 147 129 120 110 平均寻道横跨的磁道数 36 23 14 17 176 39 18 9 10 38 45

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库《操作系统精髓与设计原理·第五版》习题答案(9)在线全文阅读。