《操作系统习题.ppt》由会员分享，可在线阅读，更多相关《操作系统习题.ppt（28页珍藏版）》请在三一文库上搜索。
1、OS基本概念,OS的功能OS的功能模块OS的发展OS的概念OS的分类,进程的描述与控制,进程的概念进程和程序的区别进程的特征进程控制块进程控制原语,进程同步,进程互斥的含义互斥的硬、软件解决方法信号量机制解决互斥进程同步经典的进程同步问题进程通信,复习思考题 1（OS基本概念）,采用多道程序设计的主要优点是什么？现代操作系统的两个最基本的特征是 ( )和( )。批处理操作系统的主要缺点是（ ） 操作系统是计算机系统中的一个（ ），它管理和控制计算机系统中的（ ）。,复习思考题2（进程描述与控制）,名词解释：PCB 程序并发执行与顺序执行时产生了一些新特征，分别是（ ）、（ ）和（ ）。在操作系
2、统中引入线程概念的主要目的是（ ）。,答案,问答题：1.进程与程序有什么本质不同？2.为什么要引入进程概念？3.在什么条件下，一个进程的解封（BLOCKED-READY)会引起一个进 程的被调度(READY-RUNNING)4.进程控制块何时产生,何时消除,其作用是什么?5.有人曾描述过这样一种情形,在单处理机分时操作系统下,分配给进程A的时间片到后,系统进行切换.结果被调度到的进程仍然是A,有可能出现此情形吗?说明理由.,答案,答案,答案,答案,答案,6.有进程状态变迁图,如图所示 问:1)引起各种进程状态变迁的事件各是 什么? 2)在观察系统中的各个进程时,会见到 一个进程的状态变迁而引起
3、另一个 进程状态变迁的情形.在什么情形 下,一个进程的变迁3能立即引起另 一进程的变迁1? 3)在什么情形下,如果有的话,将发生 下述的因果变迁(2-1,3-2,4-1)?,运行,就绪,阻塞,1,2,4,3,答案,复习思考题 3（进程同步）,1.设公共汽车上，司机和售票员的活动分别是：司机： 售票员： 启动车辆 上乘客 正常行车 关车门 到站停车 售票 开车门 下乘客在汽车不断的到站、停车、行驶过程中，这两个活动是什么同步关系，并用信号灯的P，V操作实现其同步。,答案,2.理发师问题： 理发店由一个等候室（其中有N把椅子）和一个理发室（一把理发椅）组成。如果没有顾客来理发，理发师就在理发椅上睡
4、觉，如果一个顾客走进理发店，发现等候室的椅子都坐满，就离开理发店；如果理发师正忙于理发，那么该顾客就坐在一把椅子上空等；若理发师正在睡觉，则顾客就唤醒他。请用P，V操作来协调解决这一问题。,答案,3.过桥问题 从北或南来的汽车都必须通过横跨河上的一座桥，如图所示。由于桥面只能容纳一辆车的宽度，因此在任何时刻只能通过一辆或多辆来自同一方向的汽车，试利用信号量及其P，V操作，为南来北往的汽车编写程序，以保证它们安全地到达、驶过、离开此桥，以到达对岸。,北,桥,南,答案,4.桌上有一空盘，允许存放一只水果。爸爸可向盘中放苹果，也可向盘中放桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定当盘空时
5、一次只能放一只水果供吃者取用，请用P、V原语实现爸爸、儿子、女儿三个并发进程的同步。,答案,5.请用PV原语模拟两人下象棋的同步过程,答案,6.为什么在信号量S上定义的P，V操作 必须是不可分割的？7.产生死锁的必要条件是什么？ 解决死锁问题常用哪几种措施？8.一台计算机有8台磁带机。它们由N个进程竞 争使用，每个进程可能需要3台磁带机，请问 N为多少时，系统没有死 锁的可能，并说明原因。9.一个计算机系统拥有6台打印机，N个进程争夺使 用，每个进程要求2台，试问N取哪些值时，系统 不会发生死锁。,10.假定使用银行家算法，将某种资源分配给四个用户，具体情况如图所示。问：1) 这种资源的系统拥
6、有数总计是 多少？ 2）如果QIN再要一个资源，分给它后系统能处于安全 状态吗？ 3）倘若请求来自LU而不是QIN，情况怎样？,用户名,已获资源,最大资源数,WANG,LI,LU,QIN,1,1,2,4,6,5,4,7,当前剩余：2,11.设有两个优先级相同的进程P，Q程序分别如下：进程P： 进程Q: P1 y=1; Q1 x=1; P2 y=y+z; Q2 x=x+1; P3 V(s1); Q3 P(s1); P4 z=y+1; Q4 x=x+y; P5 P(s2); Q5 V(s2); P6 y=z+y; Q6 z=z+y;其中s1,s2是初值为0的信号量,z=2,若调度程序执行的策略是F
7、CFS，试问执行序列和运行结果是什么？,填空题,提高 CPU和外设的并行工作能力，进而提高整个系统的效率缺乏交互性减少程序并发执行时所付出的时空开销,名词解释:PCB 进程控制块PCB是为描述进程的运动变化过程而采用的一个与进程相联系的数据结构,用于记录管理进程所需的信息,描述进程的瞬间特征.它是进程存在的唯一标志,操作系统通过PCB而感知进程的存在.通常PCB包括进程标识符,进程的现行状态,进程起始地址,资源清单,进程优先级等内容.,返回,1.解答在多道程序系统里,才能提出程序与进程有什么本质区别的问题,在多道程序系统里,仍把程序视为完成一定功能的指令集合。至于进程，虽有多种定义，各有侧重。
8、但本质上是相同的。即主要强调进程是一个动态执行的过程这样一个概念。即进程是一个具有独立功能的程序，基于某个数据库集合在处理机上的执行过程和资源的分配管理。正因如此，进程和程序是两个既有区别又有联系的概念。其区别主要表现在：1.程序是一组指令的有序集合，没有任何执行的含义，是一个静态概念。而进程强调过程，是程序的一次执行活动，是一个动态概念。2.程序的存在是永久性的，进程则有其生命周期，它动态地被创建（于是此进程实体出现），调度执行，继而撤消（此进程实体死 亡），因此进程的存在是暂时的。3.程序仅是有序指令的集合，它不涉及到任何数据。进程既然是程序的一次执行活动，因此它的组成应包含程序和数据，除
9、此以外，还应有记录进程信息的“进程控制块”4.进程与程序之间不是一一对应的关系（）,返回,2.解答 在早期的单道程序系统里，一切系统资源都被运行程序所独占，CPU按照程序所规定的动作一步一步的顺序执行，不会受到该程序以外其他因素的影响，每次运行的结果都是相同的。 为了提高系统各种资源的利用率，引入了多道程序设计。在此环境下，同时保留在主存的几道用户程序都在执行着，都在按照自己程序规定的功能向前进展。于是这些逻辑上相互独立的程序，在执行时间上相互重叠，一个 程序的执行还没有结束，另一个程序的执行已经开始。即，各道程序之间是并行工作的，多道程序系统的本质就是把并发程序的执行引入到了计算机系统中。
10、程序运行，就要使用系统资源。多个程序并发执行，即共享系统的资源。但由于系统资源是有限的，不可能同时满足每个程序对它们的要求，因此程序之间必然会出现相互制约的关系，从而使各程序在系统内所处状态不断变化，时而在处理机上运行，时而因等待某事件的发生而阻塞 。所以，“程序”在多道程序里，表现出单道程序里不具有的特性：并发，制约和动态。为了区分两种不同的“程序”，故而引入了进程的概念。,返回,3.解答例如：当前CPU空闲，就绪队列为空，那么一个进程由于解除封锁而进入就绪队列时，就会立即引起调度。又如: 系统实行的是剥夺式调度策略，当一个比运行进程优先级高的进程进入就绪队列时，就重新进行调度。那么如果解封
11、的进程的优先级高于当前运行的进程的优先级，显然会引起一次重新调度。,返回,4.解答 当用户调用操作系统提供的创建原语时，就为所创建的进程申请一个PCB，PCB中记录进程的标识，状态等与该进程有关的信息，系统通过PCB而感知某一进程的存在。 有以下几种情况导致一个进程的撤消： 1.该进程完成自己的功能而正常结束； 2.由于某种错误而非正常结束； 3.祖先进程要求撤消某个进程； 撤消进程必须由操作系统的撤消原语进行，该原语释放撤消进程所占用的系统资源，同时释放其PCB。至此，该进程在系统中消亡。,返回,5.解答这是可能的。比如在进程A时间片到后，被迫回就绪队列时，队列恰为空。于是进程A排在就绪队列
12、首，则调度到的进程仍是A。又如就绪队列按优先级排列，在进程A时间片到后，回到就绪队列，由于其优先级高于当前就绪队列中的其它进程，因此它将排在就绪队列之首，从而再次被调度。,返回,6.解答 1）如图所示，变迁1由进程调度程序引起，变迁 2由时间片引起，变迁3由等待I/O完成，求同 步等引起，变迁4由阻塞 原因解除引起。 2）如果就绪队列非空，则一个 进程的变迁3就会 引起就绪队列中某个进程的变迁1发生。 3）当某一进程运行时间片时（即发生变迁2） 就必然引起某一进程的变迁1.某一进程的变迁 3 决不可能引起另一进程的变迁2.某一进程的 变迁 4有可能引起另一进程的变迁1。比如 ， 当运行队列和就
13、绪队列均空时，某一进程的变 迁4就会立即引起该进程的变迁1。,返回,1.解答在汽车不断地到站，停站，行驶过程中，售票员开车门，下乘客，上乘客和关车门的活动是在汽车到站停车后开始，开车前结束的。即，当汽车到站停车后，售票员可以开车门，下乘客，上乘客，关车门；当关好车门后，司机可以启动车辆，正常行车和到站停车。为此，我们引入两个信号量s1和s2,s1用来实现司机开车与售票员关门之间的同步，s2用来实现司机停车与售票员开门之间的同步，并假定汽车的初始状态为停车状态。其控制流程如下：var s1,s2:semaphore:=0,0;BEGIN parbegin driver: begin conduc
14、tor: begin repeat repeat p(s1); 上乘客； 启动车辆； 关车门； 正常行车； v(s1); 到站停车； 售票； v(s2); p(s2); until false; 开车门； end 下乘客； until false parend end END,返回,2解答：据题意，需设一个信号量s1，初值为0，用于控制理发师工作与顾客要求理发之间的关系；另设一个信号量s2,初值为0，用于控制顾客等候与顾客离去之间的同步关系。还需设一个计数器count,初值为0，当一个顾客到达时，count加1；离开时，减1。两种情况下都要根据count的不同取值而采取不同的操作。因为顾客进入
15、和离开时，都要对count操作，即count是顾客进入与离开的共享变量，所以要互斥操作。为此再设一互斥信号量mutex。Var s1,s2,mutex:semaphore:=0,0,1; customer:beginvar count:integer:=0; repeatBEGIN p(mutex); parbegin if(count=N+1) barber: begin v(mutex);exit; repeat count=count+1; rest; if(count1) v(mutex);p(s2); p(s1); else cuthair; v(s1); haircut; unti
16、l false . end p(mutex);count=count-1; parend if(count0) v(s2);v(mutex); exit;END end,返回,3解答： 以由南向北的汽车为例，如果它发现北方已有车上了桥，就应在南边等待，只有北方的车或车队全部通过桥面，然后才被唤醒。因此对南方的车辆应设置一个初值为0的记录型同步信号量delays,运行过程中，delays的绝对值，是南方等待过桥的车辆数目，若北方没有车在桥上，则南方来车后就可过桥，紧跟的车形成一个车队，依此通过，因此要有一个记录车队拥有车数的计数器south,初值为0，来一辆车，在south上加1；过一辆车，so
17、uth减1。当south为0时，表示南方车队全部过完，这时应唤醒北方等待过桥的所有汽车。对于由北向南的汽车，也同理。因此，应如下设置信号量与计数器：初值为1的互斥信号量：mutex (用于计数器的互斥操作） 初值为0的记录型同步信号量：delays 与delayn；初值为0的计数器：south 与 north 同步过程如下所述BEGIN SOUTHERNCARS：begin PARBEGIN repeat SOUTHERNCARS； 到达；p (mutex); NORTHERNCARS； if (northo) v(mutex);p(delays); PAREND else south=sou
18、th+1;v(mutex);END 过桥；离开； p(mutex); south=south-1; if (south=0) while(delayn0) v(delayn);v(mutex); until false end,返回,4.解答：在本题中，应设置三个信号量S、S1，S2；S表示盘子是否为空，其初值为1，S1表示盘中是否有桔子，其初值为0；信号量S2表示盘中是否有苹果，其初值为0。同步描述如下：int s=1; father :int s1=0; begin int s2=0; repeat BEGIN p(s); parbegin 将水果放入盘中； father( ); if (放入的是桔子）v(s1); son( ); else v(s2); daughter( ); until false parend endEND,son: daughter : begin begin repeat repeat p(s1); p(s2); 从盘中取出桔子； 从盘中取出苹果； v(s); v(s); 吃桔子； 吃苹果； until false until false end end,返回,