操作系统习题.ppt
习题1、有两个优先级相同的进程、有两个优先级相同的进程P1和和P2，各自执行的，各自执行的操作如下，信号量操作如下，信号量S1和和S2初值均为初值均为0。试问。试问P1、P2并发执行后，并发执行后，x、y、z的值各为多少？的值各为多少？P1：P2：begin begin y:=1;x:=1;y:=y+2;x:=x+1;V(S1);P(S1);z:=y+1;x:=x+y;P(S2);V(S2);y:=z+y z:=z+x;end.end.现对进程语句进行编号，以方便描述。现对进程语句进行编号，以方便描述。P1：P2：begin begin y:=1;x:=1;y:=y+2;x:=x+1;V(S1);P(S1);z:=y+1;x:=x+y;P(S2);V(S2);y:=z+y z:=z+x;end.end.、和和是不相交语句，可以任何是不相交语句，可以任何次序交错执行，而结果是唯一的。接着无次序交错执行，而结果是唯一的。接着无论系统如何调度进程并发执行，当执行到论系统如何调度进程并发执行，当执行到语句语句时，可以得到时，可以得到x=5，y=3。按。按Bernstein条件，语句条件，语句的执行结果不受语的执行结果不受语句句的影响，故语句的影响，故语句执行后得到执行后得到z=4。最。最后，语句后，语句和和并发执行，最后结果为：并发执行，最后结果为：语句语句先执行，再执行先执行，再执行：x=5，y=7，z=9。语句语句先执行，再执行先执行，再执行：x=5，y=12，z=9。2、在、在UNIX系统中运行以下程序，最多可产系统中运行以下程序，最多可产生出多少进程生出多少进程?画出进程家属树。画出进程家属树。main()fork();/*pc(程序计数器程序计数器)，进程，进程A fork();fork();解：首先采用解：首先采用fork()创建的子进程，其程序创建的子进程，其程序是复制父进程的；其次，父、子进程都从是复制父进程的；其次，父、子进程都从调用后的那条语句开始执行。调用后的那条语句开始执行。当进程当进程A执行后，派生出子进程执行后，派生出子进程B，当进程当进程A、B执行后，各派生出子进程执行后，各派生出子进程C、D，当进程当进程A、B、C、D执行后，各派生出子进执行后，各派生出子进程程E、F、G、H。这时进程。这时进程A共派生出共派生出7个个子进程。子进程。ABCEDFGH3、有一个仓库，可以存放、有一个仓库，可以存放A和和B两种产品，两种产品，但要求：但要求：（1）每次只能存入一种产品（）每次只能存入一种产品（A或或B）；）；（2）NA产品数量产品数量-B产品数量产品数量M。其中，其中，N和和M是正整数。试用是正整数。试用P、V操作描述操作描述产品产品A与产品与产品B的入库过程。的入库过程。分析本题给出的第一个条件是临界资源的访问控本题给出的第一个条件是临界资源的访问控制，可用一个互斥信号量解决该问题。第制，可用一个互斥信号量解决该问题。第二个条件可以分解为：二个条件可以分解为：NA产品数量产品数量B产品数量产品数量 A产品数量产品数量B产品数量产品数量M也就是说，也就是说，A产品的数量不能比产品的数量不能比B产品的数量产品的数量少少N个以上，个以上，A产品的数量不能比产品的数量不能比B产品的产品的数量多数量多M个以上。个以上。解：在本题中，可以设置两个信号量来控制解：在本题中，可以设置两个信号量来控制A、B产品的存放数量，产品的存放数量，sa表示当前允许表示当前允许A产品比产品比B产品多入库的数量，产品多入库的数量，即在当前库存量和即在当前库存量和B产品不入库的情况下，产品不入库的情况下，还可以允许还可以允许sa个个A产品入库；产品入库；sb表示当前允许表示当前允许B产品比产品比A产品多入库的数量，产品多入库的数量，即在当前库存量和即在当前库存量和A产品不入库的情况下，产品不入库的情况下，还可以允许还可以允许sb个个B产品入库。产品入库。初始时，初始时，sa为为M1，sb为为N1。当往库中。当往库中存放入一个存放入一个A产品时，则允许存入产品时，则允许存入B产品的产品的数量也增加数量也增加1；当往库中存放入一个；当往库中存放入一个B产品产品时，则允许存入时，则允许存入A产品的数量也增加产品的数量也增加1。var mutex：semaphore=1;/*互斥信号量互斥信号量*/sa，sb：semaphore；sa=M-1;sb=N-1;mian()while(1)取一个产品；取一个产品；if(取的是取的是A产品产品)P(sa);P(mutex);将将A产品入库；产品入库；V(mutex);V(sb);else /*取的产品是取的产品是B*/P(sb);P(mutex);将将B产品入库；产品入库；V(mutex);V(sa);4、公路上有一座桥，该桥一次只允许一辆汽、公路上有一座桥，该桥一次只允许一辆汽车在桥上行驶。当桥上有汽车时，其它汽车在桥上行驶。当桥上有汽车时，其它汽车不能上桥。试问：车不能上桥。试问：这是一个同步问题还是互斥问题？这是一个同步问题还是互斥问题？用信号量和用信号量和P、V操作描述并发过程的活动。操作描述并发过程的活动。（1）这一问题是互斥问题。桥是汽车进程互）这一问题是互斥问题。桥是汽车进程互斥使用的资源。斥使用的资源。（2）每了辆汽车对应一个进程，进程数量不）每了辆汽车对应一个进程，进程数量不确定。用确定。用Pi（i=0,1,2,）表示汽车进程；）表示汽车进程；设互斥信号量设互斥信号量s，其初值为，其初值为”1”。汽车进程汽车进程Pi的过程可描述如下：的过程可描述如下：汽车进程Pi （i=1，2,3）P(S)汽车上桥 在桥上行驶 汽车下桥 V(S)5、有一阅览室，读者进入时必须先在一张登、有一阅览室，读者进入时必须先在一张登记表上进行登记，该表为每一个座位列出记表上进行登记，该表为每一个座位列出一个表目，包括座位号、姓名，读者离开一个表目，包括座位号、姓名，读者离开时要撤消登记信息。阅览室有时要撤消登记信息。阅览室有180个座位，个座位，试问：试问：为描述读者的动作，应编写几个程序？应设为描述读者的动作，应编写几个程序？应设置几个进程？进程和程序之间的对应关系置几个进程？进程和程序之间的对应关系如何？如何？试用试用P、V操作描述这些进程间的同步关系。操作描述这些进程间的同步关系。解：（解：（1）每个读者都可视为一个进程，有多）每个读者都可视为一个进程，有多少个读者就有多少个进程，这些进程称为少个读者就有多少个进程，这些进程称为读者进程，设为读者进程，设为Pi(I=0,1,2,)。读者进程。读者进程Pi执行的程序包括：登记、阅览、撤消。每执行的程序包括：登记、阅览、撤消。每个读者的活动都相同，所以其程序也相同。个读者的活动都相同，所以其程序也相同。进程与程序之间的关系是：各读者进程共进程与程序之间的关系是：各读者进程共享同一个程序。享同一个程序。（2）在读者进程执行的程序中，对登记与撤消都需）在读者进程执行的程序中，对登记与撤消都需要互斥执行，其信号量要互斥执行，其信号量S1的初值为的初值为1；而对进入；而对进入阅览室需互斥执行，信号量阅览室需互斥执行，信号量s2的初值为的初值为180。读者进程读者进程Pi P(S2)P(S1)登记登记 V(S1)阅览阅览P(S1)撤消撤消 V(S1)V(S2)6、在单、在单CPU和两台和两台I/O(I1,I2)设备的多道程序设计环境设备的多道程序设计环境下，同时投入三个作业运行。它们的执行轨迹如下：下，同时投入三个作业运行。它们的执行轨迹如下：Job1：I2(30ms)、CPU(10ms)、I1(30ms)、CPU(10ms)Job2：I1(20ms)、CPU(20ms)、I2(40ms)Job3：CPU(30ms)、I1(20ms)如果如果CPU、I1和和I2都能并行工作，优先级从高到低为都能并行工作，优先级从高到低为Job1、Job2和和Job3，优先级高的作业，优先级高的作业可以抢占优先可以抢占优先级低的作业的级低的作业的CPU，但不抢占，但不抢占I1和和I2。试求：。试求：(1)每每个作业从投入到完成分别所需的时间。个作业从投入到完成分别所需的时间。(2)从投入到从投入到完成完成CPU的利用率。的利用率。(3)I/O设备利用率。设备利用率。答：画出三个作业并行工作图如下答：画出三个作业并行工作图如下(图中着图中着色部分为作业等待时间色部分为作业等待时间)：CPUI1I2Job1Job2Job3时间时间(ms)CPU CPU0 10 20 30 40 50 60 70 80 90 I1 I1CPUCPU I2 I2CPU I1CPU Job1 Job2 Job3Job2 Job1 Job2 Job3Job1 Job2 Job1Job3Job1从投入到运行完成需80ms，Job2从投入到运行完成需90ms，Job3从投入到运行完成需90ms。CPU使用时间为10+10+10+10+20+10=70。所以CPU利用率为70/90=77.8%。设备I1空闲时间段为：20ms至40ms，故I1的利用率为70/90=77.8%。设备I2空闲时间段为：30ms至50ms，故I2的利用率为70/90=77.8%。
