《操作系统PV操作的作业参考答案》由会员分享，可在线阅读，更多相关《操作系统PV操作的作业参考答案（18页珍藏版）》请在金锄头文库上搜索。
1、关于调度算法 【例 1】下表给出作业 l，2，3 的提交时间和运行时间。采用先来先服务调度算法和短作业优先调度算法，试问作业调度次序和平均周转时间各为多少？（时间单位：小时，以十进制进行计算。）作业号 提交时间 运行时间 1 2 3 0.0 0.4 1.0 8.0 4.0 1.0 分析解这样的题关键是要根据系统采用的调度算法，弄清系统中各道作业随时间的推进情况。我们用一个作业执行时间图来形象地表示作业的执行情况，帮助我们理解此题。 采用先来先服务调度算法，是按照作业提交的先后次序挑选作业，先进入的作业优先被挑选。然后按照“排队买票” 的办法，依次选择作业。其作业执行时间图如下：采用短作业优先调
2、度算法，作业调度时根据作业的运行时间，优先选择计算时间短且资源能得满足的作业。其作业执行时间图如下：由于作业1，2，3是依次到来的，所以当开始时系统中只有作业 1，于是作业 1 先被选中。在 8.0 时刻，作业 1 运行完成，这时系统中有两道作业在等待调度，作业 2 和作业 3，按照短作业优先调度算法，作业 3 只要运行 1 个时间单位，而作业 2 要运行4 个时间单位，于是作业 3 被优先选中，所以作业 3 先运行。待作业 3 运行完毕，最后运行作业 2。作业调度的次序是 1，3，2。另外，要记住以下公式：作业 i 的周转时间 Ti作业完成时间作业提交时间 系统中个作业的平均周转时间 ，其中
3、 Ti 为作业 i 的周转时间。 解：采用先来先服务调度策略，则调度次序为 l、2、3。 作业号 提交时间 运行时间 开始时间 完成时间 周转时间1 0.0 8.0 0.0 8.0 8.02 0.4 4.0 8.0 12.0 11.63 1.0 1.0 12.0 13.0 12.0平均周转时间 T（811.612）/310.53 采用短作业优先调度策略，则调度次序为 l、3、2。 作业号 提交时间 运行时间 开始时间 完成时间 周转时间1 0.0 8.0 0.0 8.0 8.03 1.0 1.0 8.0 9.0 8.02 0.4 4.0 9.0 13.0 12.6平均周转时间 T（8812.6
4、）/39.53 思考题 1 请同学们判断这句话：作业一旦被作业调度程序选中，即占有了 CPU。（ ）提示：需要清楚作业调度和进程调度的区别。 【例 2】考虑下述页面走向：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6当内存块数量分别为 3 时，试问 FIFO、LRU、OPT 这三种置换算法的缺页次数各是多少? 答：缺页定义为所有内存块最初都是空的，所以第一次用到的页面都产生一次缺页。当内存块数量为 3 时： 发生缺页中断的次数为 16。在 FIFO 算法中，先进入内存的页面被先换出。当页 6 要调入时，内存的状态为 4、1、5，考查页 6 之前调入的页面，分别为
5、 5、1、2、4，可见 4 为最先进入内存的，本次应换出，然后把页 6 调入内存。发生缺页中断的次数为 15。在 LRU 算法中，最近最少使用的页面被先换出。当页 6 要调入时，内存的状态为 5、2、1，考查页 6之前调入的页面，分别为 5、1、2，可见 2 为最近一段时间内使用最少的，本次应换出，然后把页 6 调入内存。 发生缺页中断的次数为 11。在 OPT 算法中，在最远的将来才被访问的页面被先换出。当页 6 要调入时，内存的状态为1、2、5，考查页 6 后面要调入的页面，分别为 2、1、2、，可见 5 为最近一段时间内使用最少的，本次应换出，然后把页 6 调入内存。 【例 3】在一个单
6、道的程序设计系统中，有 3 个作业 J1、J2、J3，它们到达输入井的时间分别为8：50、9：00、9：30，它们需要执行的时间分别为 1.5 小时、0.4 小时、1 小时。系统在 10：00 按响应比高者优先算法对它们进行调度，请回答： （1）作业被选中执行的次序是什么？（2）三个作业被选中时的响应比分别是多少？分析 响应比作业周转时间/作业运行时间 作业等待时间/作业运行时间系统在 10：00，计算作业的响应比：以 J1 为例，它的作业计算时间是 1.5 小时，即 90 分钟；J1 从 8：50 到达输入井，在 10：00 时刻，J1 的等待时间为 70 分钟，因此作业 J1 的响应比为：
7、170 分钟/90 分钟=1.77 同理，J2：160 分钟/24 分钟=3.5 J3：130 分钟/60 分钟=1.5因此按照响应比高者优先算法，优先调度 J2。在 10：24，J2 完成。这时计算 J1、J3 的响应比：J1： 1（7024）分钟/90 分钟=2.04 J3：1（3024）分钟/60 分钟 =1.9 按照响应比高者优先算法，优先调度 J1。在 11：54，J1 完成，系统调度 J3，J3 的响应比为 1（302490 ）分钟/60 分钟=3.4 因此，作业被选中执行的次序是 J2、J1、J3。三个作业被选中时的响应比分别是：J1，2.04；J2，3.5；J3，3.4。解：（
8、1）作业被选中执行的次序是 J2、J1、J3。（2）三个作业被选中时的响应比分别是：J1，1.04；J2，2.5；J3， 2.4。思考题 2 某作业的提交时间为 10：30，需要运行的时间为 1 小时，假设 11：00 开始调度，它的响应比是 。【例 4】设有进程 A、B、C、D 依次进入就绪队列（相隔一个时间单位），它们的优先级（优先数大的优先级较高）如下表所示：进程 CPU 时间 优先数 A 20 3 B 15 1 C 8 4 D 10 3 试问采用“先来先服务 ”、“静态优先数法”调度算法（注：优先数大的优先级高），选中进程的执行次序。解：采用先来先服务调度算法，按照进程进入就绪队列的先
9、后次序占有 CPU，其执行次序是 A-B-C-D。采用静态优先数法，进程 A 最先就绪，在 0 时刻先占有 CPU 运行，随后 1 时刻进程 B 进入就绪队列，2时刻进程 C 进入就绪队列，3 时刻进程 D 进入就绪队列。由于采用静态优先数法，不容许随时间的推移改变进程的优先级，所以当进程 A 运行结束时，系统的就绪队列中有 B、C 、D 三个进程，而进程 C 优先级最高，于是选中 C；这样分析下去，进程的执行次序是 A-C-D-B。思考题 3 时间片轮转调度算法是为了（ ）。A多个终端都能得到系统的及时响应 B先来先服务C优先级高的进程先使用 CPU D紧急事件优先处理 参考解答 思考题 1
10、：错误。作业被作业调度程序选中，说明作业处于运行状态，即该作业进入内存并以进程的形式存在于系统中，但属于该作业的进程可能处于运行、就绪和等待状态，只有处于运行状态的进程才能占有处理机，而其余两种状态的进程并不占有处理机。 作业调度和进程调度的区别： 一个作业从进入系统到最后完成，一般至少要经历两级调度：作业调度和进程调度。 作业调度是宏观上的高级调度，它的主要功能是根据一定的算法，从输入井中选中若干个作业，分配必要的资源，如主存、外设等，为它们建立初始状态为就绪的作业进程。 进程调度是微观上的低级调度，它的主要功能是根据一定的算法将 CPU 分派给就绪队列中的一个进程。一般的操作系统都必须有进
11、程调度。 可见在多道系统中，作业调度与进程调度是相互配合来实现多道作业的并行执行的。两者的关系可用下图表示。思考题 2：1.5（注：作业等待 0.5 小时，运行 1 小时，响应比=10.5/1=1.5 ）思考题 3：A【例 5】考虑一个由 8 个页面，每页有 1024 个字节组成的逻辑空间，把它装入到有 32 个物理块的存储器中，问： （1）逻辑地址需要多少二进制位表示？ （2）物理地址需要多少二进制位表示？ 分析 在分页存储管理中，逻辑地址结构如下图所示。 它由两个部分组成：前一部分表示该地址所在页面的页号 p；后一部分表示页内地址（页内位移）d。页号的地址位数决定了页的多少，假设页号有 2
12、0 位，则地址空间中最多可容纳的页面数为 220，即 1MB 个页面。页内地址位数确定了每页的大小，若页内地址为 12 位，则每页大小为 212，即 2KB。 同理，物理地址中块号的地址位数决定了块的数量。由于页式存储管理内存空间块的大小与页面大小相同，所以物理地址中块内地址与逻辑地址中的页内地址位数相同。 解 因为页面数为 8=23，故需要 3 位二进制数表示。每页有 1024 个字节，1024=2 10，于是页内地址需要 10位二进制数表示。32 个物理块，需要 5 位二进制数表示（32=2 5）。 （1）页的逻辑地址由页号和页内地址组成，所以需要 3+10=13 位二进制数表示。 （2）
13、页的物理地址由块号和页内地址的拼接，所以需要 5+10=15 位二进制数表示。 【例 6】若在一分页存储管理系统中，某作业的页表如下所示。已知页面大小为 1024 字节，试将逻辑地址 1011，2148，4000，5012 转化为相应的物理地址。000B 页号 块号 0，则该进程继续执行；否则释放队列中第一个等待信号量的进程。V 操作的意义：我们用信号量及 PV 操作来实现进程的同步和互斥。PV 操作属于进程的低级通信。什么是信号量？信号量（semaphore ）的数据结构为一个值和一个指针，指针指向等待该信号量的下一个进程。信号量的值与相应资源的使用情况有关。当它的值大于 0 时，表示当前可
14、用资源的数量；当它的值小于 0 时，其绝对值表示等待使用该资源的进程个数。注意，信号量的值仅能由 PV 操作来改变。一般来说，信号量 S0 时，S 表示可用资源的数量。执行一次 P 操作意味着请求分配一个单位资源，因此S 的值减 1；当 S0 时，表示已经没有可用资源，请求者必须等待别的进程释放该类资源，它才能运行下去。而执行一个 V 操作意味着释放一个单位资源，因此 S 的值加 1；若 S0，表示有某些进程正在等待该资源，因此要唤醒一个等待状态的进程，使之运行下去。利用信号量和 PV 操作实现进程互斥的一般模型是： 进程 P1 进程 P2 进程 Pn P（S）； P（S）； P（S）；临界区
15、； 临界区； 临界区；V（S）； V（S）； V（S）； 其中信号量 S 用于互斥，初值为 1。使用 PV 操作实现进程互斥时应该注意的是：（1）每个程序中用户实现互斥的 P、V 操作必须成对出现，先做 P 操作，进临界区，后做 V 操作，出临界区。若有多个分支，要认真检查其成对性。（2）P 、 V 操作应分别紧靠临界区的头尾部，临界区的代码应尽可能短，不能有死循环。（3）互斥信号量的初值一般为 1。利用信号量和 PV 操作实现进程同步PV 操作是典型的同步机制之一。用一个信号量与一个消息联系起来，当信号量的值为 0 时，表示期望的消息尚未产生；当信号量的值非 0 时，表示期望的消息已经存在。
16、用 PV 操作实现进程同步时，调用 P 操作测试消息是否到达，调用 V 操作发送消息。使用 PV 操作实现进程同步时应该注意的是：（1）分析进程间的制约关系，确定信号量种类。在保持进程间有正确的同步关系情况下，哪个进程先执行，哪些进程后执行，彼此间通过什么资源（信号量）进行协调，从而明确要设置哪些信号量。（2）信号量的初值与相应资源的数量有关，也与 P、V 操作在程序代码中出现的位置有关。（3）同一信号量的 P、V 操作要成对出现，但它们分别在不同的进程代码中。【例 10】生产者-消费者问题在多道程序环境下，进程同步是一个十分重要又令人感兴趣的问题，而生产者-消费者问题是其中一个有代表性的进程同步问题。下面我们给出了各种情况下的生产者-消费者问题，深入地分析和透彻地理解这个例子，对于全面解决操作系统内的同步、互斥问题将有很大帮助。（1）一个生产者，一个消费者，公用一个缓冲区。定义两个同步信
