1、操作系统练习题第一章什么是操作系统的基本功能? 答：操作系统的职能是管理和控制汁算机系统中的所有硬、软件资源，合理地组织计算机工作流程，并为用户提供一个良好的工作环境和友好的接口。操作系统的基本功能包括：处理机管理、存储管理、设备管理、信息管理(文件系统管理)和用户接口等。2什么是批处理、分时和实时系统?各有什么特征? 答：批处理系统(batchprocessingsystem)：操作员把用户提交的作业分类，把一批作业编成一个作业执行序列，由专门编制的监督程序(monitor)自动依次处理。其主要特征是：用户脱机使用计算机、成批处理、多道程序运行。 分时系统(timesharingoperat
2、ionsystem)：把处理机的运行时间分成很短的时间片，按时间片轮转的方式，把处理机分配给各进程使用。其主要特征是：交互性、多用户同时性、独立性。实时系统(realtimesystem)：在被控对象允许时间范围内作出响应。其主要特征是：对实时信息分析处理速度要比进入系统快、要求安全可靠、资源利用率低。3多道程序(multiprogramming)和多重处理(multiprocessing)有何区别?答；多道程序(multiprogramming)是作业之间自动调度执行、共享系统资源，并不是真正地同时执行多个作业；而多重处理(multiprocessing)系统配置多个CPU，能真正同时执行多
3、道程序。要有效使用多重处理，必须采用多道程序设计技术，而多道程序设计原则上不一定要求多重处理系统的支持。4讨论操作系统可以从哪些角度出发，如何把它们统一起来?答：讨论操作系统可以从以下角度出发： (1)操作系统是计算机资源的管理者； (2)操作系统为用户提供使用计算机的界面； (3)用进程管理观点研究操作系统，即围绕进程运行过程来讨论操作系统。上述这些观点彼此并不矛盾，只不过代表了同一事物(操作系统)站在不同的角度来看待。每一种观点都有助于理解、分析和设计操作系统。第2章 进程控制与同步解 析 题 1. 叙述进程和程序的主要区别。解：进程和程序是既有联系又有区别的两个概念，它们的主要区别如下：
4、（1）程序是指令的有序集合，其本身没有任何运行的含义，它是一个静态的概念。而进程是程序在处理机上的一次执行过程，它是一个动态概念。（2）程序的存在是永久的。而进程则是有生命期的，它因创建而产生，因调度而执行，因得不到资源而暂停，因撤消而消亡。（3）程序仅是指令的有序集合。而进程则由程序、数据和进程控制块组成。（4）进程与程序之间不是一一对应的，即同一程序同时运行于若干不同的数据集合上，它将属于若干个不同的进程；而一个进程可以执行多个程序。2. 图2.7给出了四个进程合作完成某一任务的前趋图，试说明这四个进程间的同步关系，并用P、V操作描述它。解：说明任务启动后S1先执行。当S1结束后，S2、S
5、3可以开始执行。S2、S3完成后，S4才能开始执行。为了确保这一执行顺序，设三个同步信号量b2、b3、b4分别表示进程S2、S3、S4是否可以开始执行，其初值均为0。这四个进程的同步描述如下：int b1=； /* 表示进程S2是否可以开始执行 */int b2=； /* 表示进程S3是否可以开始执行 */int b3=； int b4=； /* 表示进程S4是否可以开始执行 */main（ ） cobegin S1（ ）； S2（ ）； S3（ ）； S4（ ）； coendS1（ ） v（b1）； v（b2）；S2（ ） p（b1）； v（b3）； S3（ ） p（b2）； v（b4）；S
6、4（ ） p（b3）； p（b4）； 3. 某系统的进程状态转换图如图所示，请说明：（1）引起各种状态转换的典型事件有哪些?（2）当我们观察系统中某些进程时，能够看到某一进程产生的一次状态转换能引起另一进程作一次状态转换。在什么情况下，当一个进程发生转换3时能立即引起另一个进程发生转换1？（3）试说明是否会发生下述因果转换：2 13 24 1解：（1）在本题所给的进程状态转换图中，存在四种状态转换。当进程调度程序从就绪队列中选取一个进程投入运行时引起转换1；正在执行的进程如因时间片用完而被暂停执行就会引起转换2；正在执行的进程因等待的事件尚未发生而无法执行（如进程请求完成I/O）则会引起转换3
7、；当进程等待的事件发生时（如I/O完成）则会引起转换4。（2）如果就绪队列非空，则一个进程的转换3会立即引起另一个进程的转换1。这是因为一个进程发生转换3意味着正在执行的进程由执行状态变为阻塞状态，这时处理机空闲，进程调度程序必然会从就绪队列中选取一个进程并将它投入运行，因此只要就绪队列非空，一个进程的转换3能立即引起另一个进程的转换1。（3）所谓因果转换指的是有两个转换，一个转换的发生会引起另一个转换的发生，前一个转换称为因，后一个转换称为果，这两个转换称为因果转换。当然这种因果关系并不是什么时候都能发生，而是在一定条件下才会发生。21：当某进程发生转换2时，就必然引起另一进程的转换1。因为
8、当发生转换2时，正在执行的进程从执行状态变为就绪状态，进程调度程序必然会从就绪队列中选取一个进程投入运行，即发生转换1。32：某个进程的转换3决不可能引起另一进程发生转换2。这是因为当前执行进程从执行状态变为阻塞状态，不可能又从执行状态变为就绪状态。41：当处理机空闲且就绪队列为空时，某一进程的转换4就会引起该进程的转换1。因为此时处理机空闲，一旦某个进程发生转换4，就意味着有一个进程从阻塞状态变为就绪状态，因而调度程序就会将就绪队列中的此进程投入运行。4. 在单处理机的分时系统中，分配给进程P的时间片用完后，系统进行切换，结果调度到的仍然是进程P。有可能出现上述情形吗?如果可能请说明理由。解
9、：有可能出现上述情况。例如，若在进程P时间片用完后，被迫回到就绪队列时，就绪队列为空，这样进程P就是就绪队列中惟一的一个进程，于是调度程序选中的进程必然是进程P；又如在按优先级调度的系统中，就绪队列按进程优先级排列，在进程P时间片用完之后回到就绪队列时，若其优先级高于当前就绪队列中的其他进程，则它将排在就绪队列之首，从而再次被调度程序选中并投入运行。5.（北京大学1990年试题） 写出P、V操作的定义。 有三个进程PA、PB和PC合作解决文件打印问题：PA将文件记录从磁盘读入主存的缓冲区1，每执行一次读一个记录；PB将缓冲区1的内容复制到缓冲区2，每执行一次复制一个记录；PC将缓冲区2的内容打
10、印出来，每执行一次打印一个记录。缓冲区的大小等于一个记录大小。请用P、V操作来保证文件的正确打印。解： P、V操作是两条原语，它们的定义如下：P操作 P操作记为P（S），其中S为一信号量，它执行时主要完成下述动作：S = S1若S0，则进程继续运行。若S0，则该进程被阻塞，并将它插入该信号量的等待队列中。V操作 V操作记为V（S），S为一信号量，它执行时主要完成下述动作：S = S1若S0，则进程继续执行。若S0，则从信号量等待队列中移出队首进程，使其变为就绪状态。 在本题中，进程PA、PB、PC之间的关系为：PA与PB共用一个单缓冲区，而PB又与PC共用一个单缓冲区，其合作方式可用图2.12
11、表示。当缓冲区1为空时，进程PA可将一个记录读入其中；若缓冲区1中有数据且缓冲区2为空，则进程PB可将记录从缓冲区1复制到缓冲区2中；若缓冲区2中有数据，则进程PC可以打印记录。在其他条件下，相应进程必须等待。事实上，这是一个生产者-消费者问题。为遵循这一同步规则。应设置四个信号量empty1、empty2、full1、full2，信号量empty1及empty2分别表示缓冲区1及缓冲区2是否为空，其初值为1；信号量full1及full2分别表示缓冲区1及缓冲区2是否有记录可供处理，其初值为0。其同步描述如下：int empty1=1；int empty2=1； int full1=0；int
12、 full2=0；main（ ） cobegin PA（ ）； PB（ ）； PC（ ）； coendPA（ ） while （1） 从磁盘读一个记录； p（empty1）； 将记录存入缓冲区1； v（full1）； PB（ ） while（1） p（full1）； 从缓冲区1中取出记录； v（empty1）； p（empty2）； 将记录存入缓冲区2； v（full2）； PC（ ） while（1） p（full2）； 从缓冲区2中取出记录； v（empty2）； 打印记录； 6.有一个仓库，可以存放A和B两种产品，但要求：（1）每次只能存入一种产品（A或B）；（2）NA产品数量B产品数量
13、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
14、为M1，sb为N1。当往库中存放入一个A产品时，则允许存入B产品的数量也增加1；当往库中存放入一个B产品时，则允许存入A产品的数量也增加1。产品A、B的入库过程描述如下：int mutex=1； /*互斥信号量*/int sa=M1； int sb=N1；main（ ） while（1） 取一个产品； if（取的是A产品） p（sa）； p（mutex）； 将产品入库； v（mutex）； v（sb）； else /*取的产品是B*/ p（sb）； p（mutex）； 将产品入库； v（mutex）； v（pa）； 从本题的解法可以看出，当有比较复杂条件出现时，可以把复杂条件分解成一组简单条件
15、，这样就能很容易地写出对应的程序流程了。10.公共汽车上，司机和售票员的工作流程如下：为保证乘客的安全，司机和售票员应密切配合协调工作。请用PV操作来实现司机和售票员之间的同步。在始发站等待Semaphore S1=0,S2=1 Process 司机 L1: P（S1） 启动 行车 停车 V（S2） Goto L1 Process 售票员 L2；P（S2） 开门 关门 V（S1） 售票 Goto L2 在始发站开车门等待Semaphore S1=0,S2=0 Process 司机 L1: P（S1） 启动 行车 停车 V（S2） Goto L1 Process 售票员 L2；关门V（S1）售票
16、 P（S2）开门 Goto L2 第3章 调度与死锁四、分析题1. 为什么说采用有序资源分配法不会产生死锁？解：为了便于说明，不妨设系统中有m类资源，n个进程，分别用R1，R2，Rm（1，2，m可看作资源编号）和P1，P2， Pn表示。根据有序资源分配法可知，进程申请资源时必须按照资源编号的升序进行，即任何进程在占有了Ri类资源后，再申请的资源Rj的编号j一定大于i。因此在任一时刻，系统中至少存在一个进程Pk，它占有了较高编号的资源Rh，且它继续请求的资源必然是空闲的，因而Pk可以一直向前推进直至完成，当Pk运行完成后即会释放它占有的所有资源；在Pk完成之后，剩下的进程集合中同样会存在一个进程
17、，它占有了较高编号的资源，且它继续请求的资源必然是空闲的，因而它可以一直向前推进直至完成；以此类推，所有进程均可运行完成，故不会发生死锁。2. 有相同类型的5个资源被4个进程所共享，且每个进程最多需要2个这样的资源就可以运行完毕。试问该系统是否会由于对这种资源的竞争而产生死锁。解：该系统不会由于对这种资源的竞争而产生死锁。因为在最坏情况下，每个进程都需要2个这样的资源，且每个进程都已申请到了1个资源，那么系统中还剩下1个可用资源。无论系统为了满足哪个进程的资源申请而将资源分配给该进程，都会因为该进程已获得了它所需要的全部资源而确保它运行完毕，从而可将它占有的2个资源归还给系统，这就保证了其余三
18、个进程能顺利运行。由此可知，该系统不会由于对这种资源的竞争而产生死锁。3.考虑下列资源分配策略：对资源的申请和释放可以在任何时候进行。如果一个进程提出资源请求时得不到满足，若此时无 由于等待资源而被阻塞的进程，则自己就被阻塞；若此时已有等待资源而被阻塞的进程，则检查所有由于等待资源而被阻塞的进程。如果它们有申请进程所需要的资源，则将这些资源取出分配给申请进程。例如，考虑一个有3类资源的系统，系统所有可用资源为（4，2，2），进程A申请（2，2，1），可满足；进程B申请（1，0，1），可满足；若A再申请（0，0，1），则被阻塞。此时，若C请求（2，0，0），它可以分到剩余资源（1，0，0），并从
19、A已分到的资源中获得一个资源，于是进程A的分配向量变成（1，2，1）而需求向量变成（1，0，1）。 这种分配策略会导致死锁吗？如果会，请举一个例子；如果不会，请说明产生死锁的哪一个必要条件不成立？ 这种分配方式会导致某些进程的无限等待吗？为什么？解：本题所给的资源分配策略不会产生死锁。因为本题给出的分配策略规定若一进程的资源得不到满足，则检查所有由于等待资源而被阻塞的进程，如果它们有申请进程所需要的资源，则将这些资源取出分配给申请进程。从而破坏了产生死锁必要条件中的不剥夺条件，这样系统就不会产生死锁。这种方法会导致某些进程无限期的等待。因为被阻塞进程的资源可以被剥夺，所以被阻塞进程所拥有的资源
20、数量在其被唤醒之前只可能减少。若系统中不断出现其他进程申请资源，这些进程申请的资源与被阻塞进程申请或拥有的资源类型相同且不被阻塞，则系统无法保证被阻塞进程一定能获得所需要的全部资源。例如，本题中的进程A申请（2，2，1）后再申请（0，0，1）被阻塞。此后，进程C又剥夺了进程A的一个资源，使得进程A拥有的资源变为（1，2，1），其需求向量为（1，0，1）。之后，若再创建的进程总是只申请第1和第3类资源，总是占有系统所剩下的第1和第3类资源的全部且不阻塞，那么进程A将会无限期地等待。4.一台计算机有8台磁带机。它们由N个进程竞争使用，每个进程可能需要3台磁带机。请问N为多少时，系统没有死锁危险，并
21、说明原因。解：当N为1，2，3时，系统没有产生死锁的危险。因为，当系统中只有1个进程时，它最多需要3台磁带机，而系统有8台磁带机，其资源数目已足够系统内的1个进程使用，因此绝不可能发生死锁；当系统中有2个进程时，最多需要6台磁带机，而系统有8台磁带机，其资源数目也足够系统内的2个进程使用，因此也不可能发生死锁；当系统中有3个进程时，在最坏情况下，每个进程都需要3个这样的资源，且假定每个进程都已申请到了2个资源，那么系统中还剩下2个可用资源，无论系统为了满足哪个进程的资源申请而将资源分配给该进程，都会因为该进程已获得了它所需要的全部资源而确保它运行完毕，从而可将它占有的3个资源归还给系统，这就保
22、证了其余进程能顺利运行完毕。由此可知，当N为1，2，3时，该系统不会由于对这种资源的竞争而产生死锁。5.设系统中有3种类型的资源（A，B，C）和5个进程P1、P2、P3、P4、P5，A资源的数量为17，B资源的数量为5，C资源的数量为20。在T0时刻系统状态见下表所示。系统采用银行家算法实施死锁避免策略。T0时刻系统状态最大资源需求量已分配资源数量ABCABCP1559212P2536402P34011405P4425204P5424314剩余资源ABC233 T0时刻是否为安全状态？若是，请给出安全序列。 在T0时刻若进程P2请求资源（0，3，4），是否能实施资源分配？为什么？ 在的基础上，
23、若进程P4请求资源（2，0，1），是否能实施资源分配？为什么？ 在的基础上，若进程P1请求资源（0，2，0），是否能实施资源分配？为什么？解：由题目所给出的最大资源需求量和已分配资源数量，可以计算出T0时刻各进程的资源需求量Need，Need最大资源需求量分配资源数量：资源需求量ABCP1347P2134P3006P4221P5110 利用银行家算法对此时刻的资源分配情况进行分析，可得此时刻的安全性分析情况：WorkNeedAllocationWork+AllocationFinishP52 3 31 1 03 1 45 4 7trueP45 4 72 2 12 0 47 4 11trueP3
24、7 4 110 0 64 0 511 4 16trueP211 4 161 3 44 0 215 4 18trueP115 4 183 4 72 1 217 5 20true从上述情况分析中可以看出，此时存在一个安全序列P5，P4，P3，P2，P1，故该状态是安全的。 在T0时刻若进程P2请求资源（0，3，4），因请求资源数（0，3，4）剩余资源数（2，2，3），所以不能分配。 在的基础上，若进程P4请求资源（2，0，1），按银行家算法进行检查： P4请求资源（2，0，1） P4资源需求量（2，2，1） P4请求资源（2，0，1） 剩余资源数（2，3，3）试分配并修改相应数据结构，资源分配情况
25、如下：AllocationNeedAvailableP12 1 23 4 70 3 2P24 0 21 3 4P34 0 50 0 6P44 0 50 2 0 P53 1 41 1 0再利用安全性算法检查系统是否安全，可得此时刻的安全性分析情况：WorkNeedAllocationWork+AlloFinishP40 3 20 2 04 0 54 3 7trueP54 3 71 1 03 1 47 4 11trueP37 4 110 0 64 0 511 4 16trueP211 4 161 3 44 0 215 4 18trueP115 4 183 4 72 1 217 5 20true从上
26、述情况分析中可以看出，此时存在一个安全序列P4，P5，P3，P2，P1，故该状态是安全的，可以立即将P4所申请的资源分配给它。 在的基础上，若进程P1请求资源（0，2，0），按银行家算法进行检查： P1请求资源（0，2，0） P1资源需求量（3，4，7） P1请求资源（0，2，0） 剩余资源数（0，3，2） 试分配并修改相应数据结构，资源分配情况如下：AllocationNeedAvailableP12 3 23 2 70 1 2P24 0 21 3 4P34 0 50 0 6P44 0 50 2 0 P53 1 41 1 0再利用安全性算法检查系统是否安全，可用资源Available（0，1
27、，2）已不能满足任何进程的资源需求，故系统进入不安全状态，此时系统不能将资源分配给P1。6. 若在后备作业队列中等待运行的同时有三个作业1、2、3，已知它们各自的运行时间为a、b、c，且满足关系abc，试证明采用短作业优先调度算法能获得最小平均周转时间。解：由于短作业优先调度算法总是在后备作业队列中选择运行时间最短的作业作为调度对象，因此对短作业优先调度算法而言，这三个作业的总周转时间为T1=a(ab)(abc)=3a2bc 若不按短作业优先调度算法来调度这三个作业，不失一般性，假定调度顺序为2、1、3，则其总周转时间为T2=b(ba)(bac)=3b2ac 式得：T2T1=ba0由此可见，短
28、作业优先调度算法能获得最小平均周转时间。7. 设有4道作业，它们的提交时间及执行时间如下：作业号提交时间执行时间110.02.0210.21.0310.40.5410.50.3试计算在单道程序环境下，采用先来先服务调度算法和最短作业优先调度算法时的平均周转时间和平均带权周转时间，并指出它们的调度顺序。（时间单位：小时，以十进制进行计算。）解：若采用先来先服务调度算法，则其调度顺序为1、2、3、4。作业号提交时间执行时间开始时间完成时间周转时间带权周转时间110.02.010.012.02.01.0210.21.012.013.02.82.8310.40.513.013.53.16.2410.50.313.513.83.311.0平均周转时间 T=(2.02.83.13.3)/4=2.8平均带权周转时间 W=(12.86.211)/4=5.25若采用短作业优先调度算法，则其调度顺序为1、4、3、2。作业号提交时间执行时间开始时间完成时间周转时间带权周转时间110.02.010.012.02.01.0410.50.312.012.31.86.0310.40.512.312.82.44.8210.21.012.813.83.63.6平均周转时间 T=(2.01.
