6.什么是优先图?什么是进程图?二者有何区别? 解:优先图是一种有向无环图,其结点对应于独立的语句(组),从结点i到结点j的有 向连线表示语句i必须在语句j开始执行之前完成进程图可看做是一种(有向)树结构,其中 每个结点是一个进程.从上个结点指向另一结点的有向连线指明前者创建了后者.优先图表征 语句之间的优先制约关系,而进程图则展示进程的创建关系。在一个进程图中,Pi到Pj的边 并不隐含Pi只能在Pj之后执行,而是表示Pi创建Pj,Pi和pj可以并发地执行 7.下述算法是解决两进程互斥访问临界区问题的一种方法。试从"互斥"、"空闲让进"、 有限等待″等三方面讨论它的正确性。如果它是正确的,则证明之:如果它不正确?请说明理由。 Var cl, c2: integer: =1, 1 begin remain section1 until c20 Critical section;/*临界区*/ until false remain section2 repeat Critical section /*临界区*/ until false 分析:在通过对共享变量的测试来实现进程互斥时,必须注意共享交量本身也应当是临界 资源,如果多个进程对它们进行同时共享,则可能会导致程序互斥算法的失败。在做这类题目 时,可将检查的重点放在将条件测试指令和前面(或后面)对测试指令中所用的共享变量的修 改操作相分割的情况下,该变量又刚好被其他进程修改的时候 答:本题中,p1、p2通过共享变量c1和c2来达到资源互斥使用的目的,其中,c1=1表示p1 不在临界区内,c2=1表示p2不在临界区内。通过检查可知 (1)该算法不能保证互斥访问临界区。 ①由于c1、c2的初值都为1,若pl先获得CP并申请进入临界区,则它可以进入临界区 在pl进入临界区后,c2=1,c1=0:②此时若进行进程调度并由p2获得CPU,而p2也试图进入临 界区,执行完C2:=1-C1后,C2=1,C1=0;③此时若又进行CPU调度,并且pl重新获得CPU,并在 返出临界区后执行c1:=1,则c2=1,c1=1:④若再进行CPU调度,并且由p2获得CPU,因c1=1,p2
6.什么是优先图?什么是进程图?二者有何区别? 解：优先图是一种有向无环图,其结点对应于独立的语句(组),从结点 i 到结点 j 的有 向连线表示语句 i 必须在语句 j 开始执行之前完成.进程图可看做是一种(有向)树结构,其中 每个结点是一个进程.从上个结点指向另一结点的有向连线指明前者创建了后者.优先图表征 语句之间的优先制约关系,而进程图则展示进程的创建关系。在一个进程图中,Pi 到 Pj 的边 并不隐含 Pi 只能在 Pj 之后执行,而是表示 Pi 创建 Pj,Pi 和 pj 可以并发地执行。 7.下述算法是解决两进程互斥访问临界区问题的一种方法。试从"互斥"、"空闲让进"、" 有限等待"等三方面讨论它的正确性。如果它是正确的,则证明之:如果它不正确?请说明理由。 Var c1,c2:integer:=1,1; begin parbegin p1:begin repeat remain section1; repeat c1:=1-c2; until c2<>0; Critical section; /*临界区*/ c1:=1; until false end p2:begin repeat remain section2; repeat; c2:=1-c1; until c1<>0; Critical section; /*临界区*/ c2:=1; until false end parend end 分析：在通过对共享变量的测试来实现进程互斥时,必须注意共享交量本身也应当是临界 资源,如果多个进程对它们进行同时共享,则可能会导致程序互斥算法的失败。在做这类题目 时,可将检查的重点放在将条件测试指令和前面(或后面)对测试指令中所用的共享变量的修 改操作相分割的情况下,该变量又刚好被其他进程修改的时候。 答:本题中,p1、p2 通过共享变量 c1 和 c2 来达到资源互斥使用的目的,其中,c1=1 表示 p1 不在临界区内,c2=1 表示 p2 不在临界区内。通过检查可知: (1)该算法不能保证互斥访问临界区。 ①由于 c1、c2 的初值都为 1,若 p1 先获得 CPU 并申请进入临界区,则它可以进入临界区。 在 p1 进入临界区后,c2=1,c1=0:②此时若进行进程调度并由 p2 获得 CPU,而 p2 也试图进入临 界区,执行完 C2:=1-C1 后,C2=1,C1=0;③此时若又进行 CPU 调度,并且 p1 重新获得 CPU,并在 返出临界区后执行 c1:=1,则 c2=1,c1=1:④若再进行 CPU 调度,并且由 p2 获得 CPU,因 c1=1,p2
进入临界区,而此时c2=1,c1=1;⑤若再进行CPU调度并由pl获得CPU,当pl再申请进入临界 区时,由于C2=1,P1将顺序进入临界区。可见,在这种情况下,pl和p2将同时进入临界区。 (2)该算法能保证空闲让进。因为,c1和C2的初值均为1;而c1只有在pl申请进入自己的 临界区时才可能变为0,一旦P1退出临界区,它的值又将被置为1:同样,c2只有在P2申请进 入自己的临界区时才可能变为0,一旦P2退出临界区,它的值又将被置为1。所以,当临界资源 空闲时,不管它是否曾经被使用过,C1和C2的值均为1:此时,若pl进程申请进入自己的临界 区,则先执行C1:=1-C2,将c1置为0,并因C2<>0条件成立而结束循环测试,随后进入自己的临 界区;对p2进程,情况也是如此。 (3)在该算法中,若一进程在临界区内执行,则另一进程将处于“忙等”。因此,在某些特殊 的情况下,有可能不能保证“有限等待”。 8.请描述在当前运行进程状态改变时,操作系统进行进程切换的步骤。 解:进程切换的步骤如下 (1)保存处理器内容 (2)对当前运行进程的PCB进行更新.包括改变进程状态和其他相关信息 (3)将这个进程的PCB移人适当的队列(就绪、因事件阻塞、就绪挂起等) (4)挑选其他进程执行; (5)对挑选进程PCB进行更新,包括将其状态改为运行; (6)对存储器管理数据结构进行更新 (7)恢复被选择进程上次移出时的处理器状态。 9.请举例说明如何利用信号量实现进程同步。 计算进 单缓冲区一→打印进程 图3.3是单缓冲的计算进程和打印远程 答:在用信号量机制实现同步时,只要找出进程之间的同步关系,并为每种同步关系设置 信号量,然后再在需要等待某种动作的地方插入P操作,在被等待的动作完成之后插人V操作。 例如,如图3.7所示的共享单缓冲的计算进程和打印进程之间存在两种同步图关系 (1)打印进程必须等待计算进程将计算结果放入缓冲之后,才能取数打印,因此,可为它们设 置一初值为0的信号量SA,表示缓冲区中是否有计算结果可供打印:并将P(SA)操作放在打印 进程取数打印的动作之前,V(SA)操作放在计算进程将计算结果放入单缓冲的动作之后。 (2)计算进程必须等打印进程将缓冲区中的前一个数据取走,缓冲区变空后,才能将下 个计算结果放入缓冲区,因此,可为它们设置一初值为1的信号量SB,表示是否有空闲的缓冲 区可供存放计算结果:并将P(SB)操作放在计算进程,将计算结果放入缓冲区的动作之前,而 将V(SB)操作放在打印进程腾出空闲缓冲之后。具体的同步算法可描述如下: Var SA, SB: semaphore: =0, 1 begin cp: begin compute next number add the number to buffer V (SA) ntil false d PP: begin
进入临界区,而此时 c2=1,c1=1;⑤若再进行 CPU 调度并由 p1 获得 CPU,当 p1 再申请进入临界 区时,由于 C2=1,P1 将顺序进入临界区。可见,在这种情况下,pl 和 p2 将同时进入临界区。 （2）该算法能保证空闲让进。因为,c1 和 C2 的初值均为 1;而 c1 只有在 pl 申请进入自己的 临界区时才可能变为 0,一旦 P1 退出临界区,它的值又将被置为 1；同样,c2 只有在 P2 申请进 入自己的临界区时才可能变为 0,一旦 P2 退出临界区,它的值又将被置为 1。所以,当临界资源 空闲时,不管它是否曾经被使用过,C1 和 C2 的值均为 1；此时,若 p1 进程申请进入自己的临界 区,则先执行C1:=1-C2,将c1置为0,并因C2<>O条件成立而结束循环测试,随后进入自己的临 界区;对 p2 进程,情况也是如此。 (3)在该算法中,若一进程在临界区内执行,则另一进程将处于“忙等”。因此,在某些特殊 的情况下,有可能不能保证“有限等待”。 8.请描述在当前运行进程状态改变时,操作系统进行进程切换的步骤。 解:进程切换的步骤如下: (1)保存处理器内容； (2)对当前运行进程的 PCB 进行更新.包括改变进程状态和其他相关信息； (3)将这个进程的 PCB 移人适当的队列(就绪、因事件阻塞、就绪挂起等)； (4)挑选其他进程执行； (5)对挑选进程 PCB 进行更新,包括将其状态改为运行； (6)对存储器管理数据结构进行更新； (7)恢复被选择进程上次移出时的处理器状态。 9.请举例说明如何利用信号量实现进程同步。 计算进程 单缓冲区 打印进程 图 3.3 是单缓冲的计算进程和打印远程; 答:在用信号量机制实现同步时,只要找出进程之间的同步关系,并为每种同步关系设置一 信号量,然后再在需要等待某种动作的地方插入P操作,在被等待的动作完成之后插人V操作。 例如,如图 3.7 所示的共享单缓冲的计算进程和打印进程之间存在两种同步图关系: (1)打印进程必须等待计算进程将计算结果放入缓冲之后,才能取数打印,因此,可为它们设 置一初值为 0 的信号量 SA,表示缓冲区中是否有计算结果可供打印:并将 P(SA)操作放在打印 进程取数打印的动作之前,V(SA)操作放在计算进程将计算结果放入单缓冲的动作之后。 (2)计算进程必须等打印进程将缓冲区中的前一个数据取走,缓冲区变空后,才能将下一 个计算结果放入缓冲区,因此,可为它们设置一初值为 1 的信号量 SB,表示是否有空闲的缓冲 区可供存放计算结果:并将 P(SB)操作放在计算进程,将计算结果放入缓冲区的动作之前,而 将 V(SB)操作放在打印进程腾出空闲缓冲之后。具体的同步算法可描述如下: Var SA,SB:semaphore:=0,1; begin parbegin cp:begin repeat compute next number; P(SB); add the number to buffer; V(SA); until false; end PP:begin