a.8×2K=16k b.16K×4=64K c.232=4GBytes
8.18 考虑一个分页式的逻辑地址空间（由32个2KB的页组成），将它映射到一个1MB的物理内存空间。
a.该处理器的逻辑地址空间格式是什么？
b.页表的长度和宽度是多少（忽略“访问权限”位）？ c.如果物理内存空间减少了一半，则会对页表有什么影响？ 解答 a.
36
页码（5） 偏移量（11） b.32个页表项长，每个页表项9个bits宽 c.如果页表项还是32个且页大小不变，那么每个页表项变为8bits宽
8.19 UNIX内核可以在需要时动态地在虚存中增加一个进程的栈，但却从不缩小这个栈。考虑下面的例子：一个程序调用一个C语言程序，这个子程序在栈中分配一个本地数组，一共需要10KB大小，内核扩展这个栈段来适应它。当这个子程序返回时，内核应该调整栈指针并释放空间，但它却未被释放。解释为什么可以缩小栈以及UNIX内核为什么没有缩小栈。 解答
可以通过释放再分配不使用的页来缩减栈的大小。按照惯例，在超出当前栈顶范围内内存中的值没有定义。在全部的体系结构中，标志栈顶部的指针在一个定义完好的记录中。因此可以读取栈的内容且按要求释放不使用的页。不缩小栈的原因是这样做的效果很小。如果用户程序重复调用子程序需要附加的空间来分配给局部变量（一个很可能的情况），然后许多时间会被浪费在释放重分配栈空间
第9章 单处理器调度
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 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
37
Tr/Ts 1.00 1.80 3.00 2.00 1.60
SPN Tf 3.00 10.00 5.00 15.00 20.00
Tr 3.00 9.00 2.00 6.00 8.00 Tr/Ts 1.00 1.80 1.00 1.20 1.60
SRT Tf 3.00 10.00 5.00 15.00 20.00
Tr 3.00 9.00 2.00 6.00 8.00 Tr/Ts 1.00 1.80 1.00 1.20 1.60
HRRN Tf 3.00 8.00 10.00 15.00 20.00
Tr 3.00 7.00 7.00 6.00 8.00 Tr/Ts 1.00 1.40 3.50 1.20 1.60
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 Tr/Ts 2.33 2.00 1.50 1.80 1.60
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
Tr/Ts 1.33 1.80 2.50 1.80 1.60
9.2对下面的集合重复习题9.1的要求 进程 A B C D A A A A A A A A B B B B B B B B B C B B C B C C B B B B B B D D B D B B B B B B B B C B B B D B B D B B B B B D B B B B B B D D B D B B B B B B C 2 1 11.00 9.00 9.00 3.00 1.00 1.00 6.00 4.00 4.00 11.00 9.00
B B B B B B D B C D D C B C B B D B D D D D D B D D D D D D B D 到达时 0 1 2 3 1 9 1 9 1.88 5.60 1.32 5.60 1.32 6.20 1.74 7.40 1.85 7.00 1.81
处理时间 D B D D D D D D D D B D D D B 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 A Ta 0 Ts 1 FCFS Tf 1.00 Tr 1.00 Tr/Ts 1.00 RRq=1 Tf 1.00 Tr 1.00 Tr/Ts 1.00 RRq=4 Tf 1.00 Tr 1.00 Tr/Ts 1.00 SPN Tf 1.00 Tr 1.00
B
1 9 10.00 9.00 1.00 18.00 17.00 1.89 15.00 14.00 1.56 10.00 9.00 D 3 9 20.00 17.00 1.89 20.00 17.00 1.89 20.00 17.00 1.89 20.00 17.00
38
9.00 3.22 9.00 1.44 9.00 2.11 9.00
Tr/Ts 1.00 1.00 9.00 1.89 3.22 SRT Tf 1.00 11.00 3.00 20.00 Tr 1.00 10.00 1.00 17.00 9.00 Tr/Ts 1.00 1.11 1.00 1.89 1.25 HRRN Tf 1.00 10.00 11.00 20.00 Tr 1.00 9.00 9.00 17.00 9.00 Tr/Ts 1.00 1.00 9.00 1.89 3.22 FBq=1 Tf 1.00 19.00 3.00 20.00 Tr 1.00 18.00 1.00 17.00 9.25 Tr/Ts 1.00 2.00 1.00 1.89 1.47 FB Tf 1.00 18.00 3.00 20.00 q=2i Tr 1.00 17.00 1.00 17.00 9.00 Tr/Ts 1.00 1.89 1.00 1.89 1.44
9.3证明在非抢占调度算法中，对于同时到达的批处理作业，SPN提供了最小平均等待时间。假设调度器只要有任务就必须执行。
我们能够证明在一批n个作业同时到达且忽略以后到来的作业。试验会延伸包含以后的作业。假设各作业到来的顺序是：t1<=t2<=??<=tn.假设n个使用者必须等到工作1的完成：n-1个使用者必须等到工作2的完成，依次继续。那么，平均反应时间是[n*t1+(n-1)*t2+??+tn]/n。如果我们在这个时间表中做些改变，例如调换工作j和k（j
9.4假设一个进程的每一次瞬间执行时间（burst-time模式）为6，4，6，4，13，13，13，假设最初的猜测值为10。请画出类似于图9.9的图表。 数据图如下： 平均观察 1 2 3 4 5 6 7 观测值 6 4 6 4 13 13 13 平均值 0.00 3.00 3.33 4.00 4.00 5.50 6.57 apha=0.8 0.00 4.80 4.16 5.63 4.33 11.27 12.65 alpha=0.5 0.00 3.00 3.50 4.75 4.38 8.69 10.84 9.5考虑下面的公式，它可以替代Sn+1=αTn+(1-α)Sn,Xn+1=min[Ubound,max[Lbound,(βSn+1)]] 其中，Ubound和Lbound是预先选择的估计值T的上限和下限。Xn+1的值用于最短进程优先的算法，并且可以代替Sn+1。α和β有什么功能，它们每个取最大值和最小值会产生什么影响？
第一个等式等同于等式9.3，所以参数使指数起平滑作用。参数β是延迟变化参数。一个较小的β值将会时在观察次数里更快的适应改变，但估计上会产生更多的波动。一个诡辩的这种估计类型的程序收录于Applied Optimal Estimation。
9.6在图9.5下面的例子中，在控制权限转移到B之前，进程A运行2个时间单元，另外一个场景是在控制权限转移到B之前，进程A运行3个时间单元。在反馈调度算法中，这两种场景的策略有什么不同？ 关键要看进程A是否一开始就被放置在队列中。如果是，它在被抢占前就被赋予2个额外的时间单元。 9.7在一个非抢占的单处理器系统中，在刚刚完成一个作业后的时间t，就绪队列中包含三个作业。这些作业分别在时间t1，t2，t3处到达，估计执行时间分别为r1，r2，r3。图9.18显示了它们的响应比随着时间线形增加。使用这个例子，设计一种响应比调度的变体，称为极小极大响应比调度算法，它可以使给定的一批作业的最大响应比最小。
首先，调度器计算t+r1+r2+r3时刻的响应比，如果三个进程都结束，此时，进城3就有最高响应比，因此调度器就执行该进程，然后在t+r1+r2时刻继续执行进程1和2直到结束。因此，进程1的响应比最小，
39
其次进程2在t时间被选中执行。这种算法在每个进程结束的时候重复一次并且考虑新加入的进程。但注意这种算法和最高响应比算法不完全相同。后者在t时刻会选择进程1。直觉上看，当前算法通过不断的推迟具有最少响应比增值的进程从而减小最高响应比
9.8证明，对给定的一批作业，上一习题中的最大响应比调度算法能够使它们的最大响应时间最小
这个证明，来自于P. Mondrup, is reported in [BRIN73]。考虑在时间t时的队列，仅仅在前一个进程结束且忽略以后工作的到来。等待执行的作业被编号从1到n：
作业： 1 2 ?? I ?? n 到达时间： t1 t2 ?? ti ?? tn 服务时间： r1 r2 ?? ri ?? rn 我们假设作业i在完成前能达到最高的响应时间比。当作业1到n都执行结束，总时间为 Ti=t+r1+r2+??+ri，作业i的响应比为Ri（Ti）+（Ti-ti）/ri 执行作业i的原因是它的响应比将是以下作业在Ti时最小的： Ri(Ti)=min[R1(Ti),R2(Ti),??,Ri(Ti)] 考虑不同序列中同样的n个作业的排序结果：
作业： a b ?? j ?? z 到达时间： ta tb ?? tj ?? tz 服务时间： Ra rb ?? rj ?? rz
在新的序列中，我们选择最小的后继服务作业，从a到j，包括从1到i最初的后继。当作业a到j被执行结束，总时间为Tj=t+ra+rb+??+rj 作业j的响应比是Rj(Tj)+(Tj-tj)/rj 由于作业1到j是作业a到j的一个子集，那么总的服务时间Ti-t一定小于等于总的服务时间Tj-t.又响应比随着时间增加而增加，Ti<=Tj,意味Rj(Tj)>=Rj(Ti)
人们还知道，作业J是其中的之一，作业j在时间Ti有最小的响应比。上述不平等的，因此可以延长如下：Rj(Tj)>=Rj(Ti)>=Ri(Ti).换言之，在调度算法改变后，会有作业j达到响应比Rj(Tj)，它会大于等于最高的响应比Ri(Ti).
这证明有效期一般为优先考虑的都是非递减函数的时间。例如，在一个FIFO制度，优先增加线性与等候时间，在同样的速度，为所有作业机会。因此，目前的证据表明，该FIFO的算法最大限度地减少候车时间，对于给定了一批作业。
9.9驻留时间Tr被定义成一个进程花费在等待和被服务上的总平均时间。说明对FIFO，若平均服务时间为Ts，则有Tr=Ts/（1-ρ），其中ρ为使用率。
在我们开始以前，有一个结果，这是必要的，具体情况如下。假设一个项目拥有T服务时间，而实际服务了时间h。那么，预期的残留服务时间E [T/T > h] = Ts。那就是，无论多久，一个项目服务，预计剩余服务时间，只是平均服务时间为项目。这一结果，虽然反以直觉是正确的，正如我们现在查看，考虑到指数的概率分布函数：F(x) = Pr[X ≤ x] = 1 – e–ux，那么，我们有Pr[X > x] = e-ux。现在让我们看看X多于X +h的条件概率：
，则
因此，概率分布为服务时间给予确已送达期限x是相同的概率分布，总服务时间。因此，预期价值的剩余服务时间是一样的原来预期值的服务时间。与这一结果，我们现在可以着手将原问题。当一个项目展开服务以来，总的响应时间，该项目将包括它自己的服务时间，再加上服务的时候，所有的物品摆在它面前的，在排队。预期总体响应时间由三部分组成。 ? 预计到达进程的服务时间=Ts。
? 预计所有目前正在等待服务的进程程的服务时间。值为w × Ts，w是平均等待服务时间。
40
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库《操作系统精髓与设计原理·第五版》习题答案(8)在线全文阅读。
相关推荐：