2024年1月23日发(作者：)
第二章
一、思考题
1.什么是PSW，它有何作用？
psw:操作系统将程序运行时的一组动态信息会聚在一起，称为程序的状态字
作用：实现程序状态的保护和恢复
3.为什么要把机器指令分成特权指令和非特权指令？
应用程序在执行有关资源管理的机制指令时易于导致系统混乱，造成系统或用户信息被破坏，因此在多道程序设计环境中，从资源管理和控制程序执行的角度出发，必须把指令系统中的指令分成这两类。
4.试分别从中断事件的性质、来源和实现角度对其进行分类
从中断事件的性质和激活的手段来说，可以分成两类：
（1）强迫性中断事件强迫性中断事件不是正在运行的程序所期待的，而是由于某种事故或外部请求信息所引起的，分为：
机器故障中断事件。
程序性中断事件。
外部中断事件。
输入输出中断事件。
（2）自愿性中断事件自愿性中断事件是正在运行的程序所期待的事件。
按事件来源和实现手段分类：
（1）硬中断；硬中断分为外中断（中断、异步中断）和内中断（异常、同步中断）；
（2）软中断；软中断分为信号和软件中断。
9.什么是系统调用？试述API、库函数及系统调用间的关系。叙述系统调用执行流程。
由操作系统实现的所有系统调用所构成的集合即程序接口或应用编程接口(Application Programming Interface，API)。系统调用是一种API，是应用程序同系统之间的接口。
库函数是语言本身的一部分，可以调用多个系统调用；系统调用（函数）是内核提供给应用程序的接口，属于系统的一部分，可以认为是某种内核的库函数；操作系统API是有系统调用（函数）的集合（也就是将许多的系统调用封装在了一起）。
一是编写系统调用服务例程；二是设计系统调用入口地址表，每个入口地址都指向一个系统调用的服务例程，有的还包括系统调用自带的参数个数；三是陷阱处理机制，需要开辟现场保护区，以保存发生系统调用时应用程序的处理器现场。应用程序执行系统调用，产生中断指向内核态，进入陷阱处理程序，它将按功能查询入口地址表，并转至对应服务例程执行，完成后退出中断，返回应用程序断点继续运行。
14.简述Linux的快中断和慢中断
快中断：快中断处理仅要保存被常规C函数修改的寄存器；中断处理时会屏蔽所有其他中断；中断处理完毕后，通常恢复现场返回被中断的进程继续执行(是非抢先式调度)。
慢中断：处理慢中断前需保存所有寄存器的内容，中断处理时，不屏蔽其他中断信号，慢中断处理完毕后，通常不立即返回被中断的进程，而是进入调度程序重新调度，调度结果未必是被中断的进程运行(是抢先式调度)。
17.讨论Linux系统的tasklet、work queue和softirq任务延迟处理进制。
（1）tasklet：能更好支持SMP，它基于软中断来实现，但比软中断接口简单，锁保护要求低；softirq保留给执行频率及时间要求特高的下半部分使用(如网络和SCSI)，多数场合下可使用tasklet。
使用tasklet的步骤：声明 、编程、调度 。
BH全局串行处理，不适应SMP环境，而不同tasklet可同时运行于不同CPU上，当然，系统保证相同tasklet不会同时在不同CPU上运行，在这种情形下，tasklet就不需要是可重入的。
在新版Linux中，tasklet是建议的异步任务延迟执行机制。
（2）work queue：Linux 2.5内核引入-工作队列，它把一个任务延迟，并交给内核线程去完成，且该任务总是在进程上下文中执行，通过工作队列执行的代码能占尽进程上下文的优势，最重要的是工作队列允许重新调度及阻塞。
默认的工作者线程:event/n
如果延迟执行的任务需要阻塞，需要获取信号量或需要获得大量主存时，那么，可选择工作队列，否则可使用tasklet或softirq。
(3) Sorfirq：（软中断）是一种软中断机制，亦即是一种信号机制，中断处理程序在其返回前标记下半部分，让其稍后执行；它又是一个框架，纳入了tasklet及为网络操作专门设计的软中断。
18.什么是进程？计算机系统中为什么要引入进程？
（1）进程定义：
进程是可并发执行的程序在某个数据集合上的一次计算活动，也是操作系统进行资源分配和保护的基本单位
（2）刻画系统的动态性，发挥系统的并发性，提高资源利用率。
程序是并发执行的，即不是连续而是走走停停的。程序的并发执行引起资源共享和竞争问题，执行的程序不再处在封闭环境中。
“程序”自身只是计算任务的指令和数据的描述，是静态概念无法刻画程序的并发特性，系统需要寻找一个能描述程序动态执行过程的概念，这就是进程。
它能解决系统的“共享性”，正确描述程序的执行状态。程序与程序的执行不再一一对应
19.进程有哪些主要属性？试解释之
•共享性：同一程序同时运行于不同数据集合上时构成不同进程，即多个不同进程可执行相同的程序，所以进程和程序不是一一对应的。
•动态性：进程是程序在数据集合上的一次执行过程，是动态概念，同时它有生命周期，由创建而产生、由调度而执行、由事件而等待、由撤销而消亡；而程序是一组有序指令序列，是静态概念，所以程序作为系统中的一种资源是永远存在的
•独立性：每个进程是操作系统中的一个独立实体，有自己的虚存空间，程序计数器和内部状态；
•制约性：进程因共享进程资源或协同工作产生相互制约关系，造成进程执行速度的不可预测，必须对进程的执行次序或相对执行速度加以协调；
•并发性：多个进程的执行在时间上可以重叠，在单处理器系统中可并发执行；在多处理器环境中可并发执行。因此，并发的执行是可被打断的，或者说，进程执行完一条指令后在执行下一条指令前可能被迫让出处理器，由其它若干个进程执行若干条指令后才能再次获得处理器执行。
20.进程最基本的状态有哪些？哪些事件可能引起不同状态间的转换？
运行态、就绪态、等待态
（1）运行态-等待态：运行进程等待使用某种资源或者某事件发生
（2）等待态-就绪态：所需资源得到满足或某事件已经完成
（3）运行态-就绪态：运行时间片到时或出现更高优先级的进程，当前进程被迫让出处理器。
（4）就绪态-运行态：当CPU空闲时，调度程序选中一个就绪进行执行
21.五态模型的进程中，新建态和终止态的主要作用是什么？
新建态：对应于进程被创建时的状态，进程尚未进入就绪队列，对于进程管理非常有用。
终止态：进程完成任务到达正常结束点或者因错误而终止，或被操作系统及有终止权的进程时所处的状态。进入终止态程序不再执行，等待操作系统进行善后处理。
24.什么是进程的挂起状态？列出挂起进程的主要特征。
（1）为了让某些进程暂时不参与低级调度，释放它占有的资源，将其置于磁盘对换区中，以平滑系统负荷的目的而需引入挂起态；
（2）特征：
•该进程不能立即被执行。
•挂起进程可能会等待事件，但所等待事件是独立于挂起条件的，事件结束并不能导致进程具备执行条件。
•进程进入挂起状态是由于操作系统、父进程或进程本身阻止它的运行。
•结束进程挂起状态的命令只能通过操作系统或父进程发出
25.试述组成进程的基本要素，并说明其作用。
控制块：存储进程的标志信息，现场信息和控制信息；
程序块：规定进程的一次运行所应完成的功能；
核心块：用来保护中断/异常现场，保存函数调用的参数和返回地址；
数据块：存放各种私有数据
26.何谓进程控制块（PCB）？它包含哪些基本信息？
（1）进程控制块P C B ，是操作系统用于记录和刻划进程状态及有关信息的数据结构。也是操作系统掌握进程的唯一资料结构，它包括进程执行时的情况，以及进程让出处理器后所处的状态、断点等信息。
（2）进程控制块包含三类信息
标识信息
现场信息
控制信息
28.请列举组织进程队列的各种方法
通用队列组织方式：
线性方式
链接方式
索引方式
30.什么是进程上下文？简述其主要内容
操作系统中把进程物理实体和支持进程运行的环境合称为进程上下文。
当系统调度新进程占有处理器时，新老进程随之发生上下文切换。进程的运行被认为是上下文中执行。
进程上下文组成
•用户级上下文
•系统级上下文
•寄存器上下文
31.什么是进程切换？试述进程切换的主要步骤
（1）进程切换是让处于运行态的进程中断运行，让出处理器，这时要做一次进程上下文切换、即保存老进程状态而装入被保护了的新进程的状态，以便新进程运行
（2）保存被中断进程的处理器现场信息
修改被中断进程的进程控制块有关信息，如进程状态等
把被中断进程的PCB加入有关队列
选择下一个占有处理器运行的进程
修改被选中进程的PCB的有关信息
根据被选中进程设置操作系统用到的地址转换和存储保护信息
根据被选中进程恢复处理器现场
32.什么是模式切换？它与进程切换之间有何区别？
模式切换即CPU模式切换，是从用户态到核心态或者核心态到用户态的转换是CPU模式切换，此时仍然在同一个进程中运行。模式切换不同于进程切换，它不一定会引起进程状态的转换，也不一定会引起进程切换，在完成系统调度服务或中断处理之后，可通过逆向模式来恢复被中断进程的运行。
35.在操作系统引入进程概念后，为什么还有引入线程的概念？
操作系统中再引入线程，则是为了减少程序并发执行时所付出的时空开销，使得并发粒度更细、并发性更好。
38.试从调度、并发性、拥有资源和系统开销等四个方面对传统进程和多线程进程进行比较。
40.试对下列系统任务进行比较：
（1）创建一个线程和创建一个进程
（2）两个进程间通信与同一进程中的两个线程间通信
（3）同一进程中的两个线程的上下文切换和不同进程中两个线程的上下文切换。
43.列举线程的组织方式和应用场合。
答：线程组织方式：（1）调度员/工作者方式
（2）组模式
（3）流水线模式
应用场合：（1）前台和后台工作
（2）C/S应用模式
（3）异步处理
（4）加快执行速度
（5）设计用户接口
45.试分析Linux系统的进程和线程。
进程描述符task_struct中包含：进程标识、链接信息、调度信息、文件信息、虚存空间信息、信号处理信息等。
Linux中认为线程就是共享地址空间及其他资源的进程，故并没有单独为线程定义数据结构，有一套在用户模式下运行的线程库-pthread，但每个线程都拥有惟一隶属于自己的task_struct
48.处理器调度分为哪几种类型？简述各种调度的主要任务。
答：（1）高级调度：在多道处理操作系统中，从输入系统的一批作业中按照预定的调度策略挑选若干个作业进入主存，为其分配所需资源，并创建作业的相应用户进程后便完成启动阶段的高级调度任务；
（2）中级调度：根据主存资源决定主存中所能容纳的进程数目，并根据进程的当前状态来决定辅助存储器和主存中的进程的对换；
（3）低级调度：根据某种原则决定就绪队列中的哪个进程或内核级线程获得处理器，并将处理器让出给它使用。
49.试述衡量一个处理器调度算法优劣的主要任务。
根据调度机制 的三个逻辑功能程序模块组成来评判：
（1）队列管理程序
（2）上下文切换程序
（3）分派程序
52.解释：（1）作业周转时间；（2）作业带权周转时间；（3）相应时间；（4）吞吐率。
答：（1）作业周转时间：批处理用户从系统提交作业开始，到作业完成为止的时间间隔；
（2）作业带权周转时间：在操作系统中，带权周转时间反映作业（或进程）长短问题，带权周转时间越大，作业（或进程）越短；带权周转时间越小，作业（或进程）越长。
（3）响应时间：从交互式进程提交一个请求至得到响应之间的时间间隔称为响应时间。
（4）吞吐率：单位时间CPU处理作业的个数。
53.试述作业、进程、线程和程序之间的关系。
进程是操作系统结构的基础；是一个正在执行的程序；计算机中正在运行的程序实例；可以分配给处理器并由处理器执行的一个实体；由单一顺序的执行显示，一个当前状态和一组相关的系统资源所描述的活动单元。
线程（thread, 台湾称 执行绪）是"进程"中某个单一顺序的控制流。也被称为轻量进程（lightweight processes）。计算机科学术语，指运行中的程序的调度单位。
作业：用户在一次运算过程中，或一次事务处理中要求计算机所做的全部工作的总和。
进程是在自身的虚拟地址空间正在运行的一个程序
程序运行产生进程
程序是一组静态的指令集，不占用系统运行资源
进程是随时都可能发生变化的，动态的。占用系统运行资源的程序
一个程序可以产生多个进程
作业嘛，是一个或多个正在执行的相关进程。一般来讲当进程与作业控制相关联时才被称为作业
55.在时间片轮转低度调级算法中，根据哪些因素确定时间片的长短？
答：进程数目、切换开销、系统效率及响应时间等多方面因素。
57.为什么多级反馈队列算法能较好地满足各种用户的需求？
答：高级调度的主要任务是根据某种算法，把外存上处于后备队列中的那些作业调入内存。低级调度是保存处理机的现场信息，按某种算法先取进程，再把处理器分配给进程。引入中级调度的主要目的是为了提高内存利用率和系统吞吐量。使那些暂时不能运行的进程
不再占用内存资源，将它们调至外存等待，把进程状态改为就绪驻外存状态或挂起状态。
58.分析静态优先数和动态优先数低级调度算法各自的优缺点。
答：静态优先级在进程或线程创建时确定，且生命周期中不再改变，可按照外部指定和内部指定方法计算静态优先级。静态优先级算法的实现简单，但会产生饥饿现象，使某些低优先级进程或线程无限期对的被推迟进行。
动态优先级使各进程或线程优先级随时间而改变，克服了静态优先级的饥饿问题，等待时间足够长的进程或线程会因其优先级不断提高而被调度运行。
62.在多级反馈队列中，对不同的队列分配大小不同的时间片值，其意义何在?
应用题
1.下列指令中，哪些只能在内核态运行？
（1）读时钟日期 （2）访管指令 （3）设时钟日期 （4）加载PSW
（5）置特殊寄存器 （6）改变存储器映像图 （7）启动I/O指令
4.在按照动态优先数调度进程的系统中，每个进程的优先数需定时重新计算。在处理器不断在进程之间交替的情况下，重新计算进程优先数的时间从何而来？
许多操作系统重新计算进程的优先数在时钟中断处理例程中进行，由于中断是随机碰到哪个进程，就插入哪个进程中运行处理程序，并把处理时间记在这个进程的账上。
7.
8.
10. 按照最短作业优先的算法可以使平均响应时间最短。X取值不定，按照以下情况讨论： 1）
x≤3 次序为：x，3，5，6，9 2）
3 5 6 9 11. ( l ) FCFS 调度算法 ( 2 ）优先级调度算法 ( 3 ）时间片轮转法 按次序ABCDEBCDECDEDEE 轮转执行。 12． 16. 20. 21. A 10:00 12:40 160 B 10:20 10:50 30 C 10:30 11:50 80 D 10:50 13:00 130 E 12:00 12:20 80 F 11:50 1200 50 平均作业周转时间 =(160+30+80+130+80+50)/6=88.33 26. (1) Job4最后一个完成 (2) 各个作业的平均周转时间为：(90+40+120+120+30)/5 = 80 各个作业的平均带权周转时间为：(1.8+1+2.4+6+3)/5 = 2.84 32. 循环周期为4*100+400=800ms A类进程需要2*1000/100=20个时间片的执行时间，B类进程需要2*1000/400=5个时间片的执行时间， A类进程的平均周转时间为20*0.8=16s B类进程的平均周转时间为5*0.8=4s 第三章 思考题： 一：试述顺序程序设计的特点，以及采用顺序程序设计的优缺点。 答：顺序程序设计的特性： （1）：执行的顺序性。一个程序在处理器上严格按序执行的，每一个操作必须在下一个操作开始之前结束。 （2）：环境的封闭性。运行程序独占全机资源，资源状态只能由此程序本身决定和改变，也不受外界因素的影响。 （3）：结果的确定性。程序在执行过程中允许出现中断，但这种中断不会对程序的最终结果产生影响。 （4）：过程的可在现行。程序针对同一个数据结构的执行过程在下一次执行时会重现，即重复执行的程序会获得相同的执行过程和计算结果。 程序顺序执行与其速度无关，即程序的最终输出仅与初始输入数据有关，而与时间无关。优点：为程序的编制和调试带来很大方便。缺点：计算机系统的效率不高。 二：试述并发程序设计的特点，以及采用并发程序设计的优缺点。 答：特性：从宏观上看：并发性反映一个时间段内有几个程序都处于运行但运行尚未结束的状态；从微观上看：任一时刻仅有一个程序的一个操作在处理器上执行。程序的并发执行产生资源共享的需求，从而使程序失去封闭性、顺序性、确定性、可在现行。 优点： （1）：若为单处理系统，可以有效地利用资源，让处理器和设备、设备和设备同时工作，充分发挥硬部件的并行工作能力； （2）：若为多处理系统，可让进程在不同处理器上物理的并行工作，加快计算速度； （3）：简化程序设计任务，一般来说，编制并发执行的小程序进度快，容易保持正确性。可见，计算机硬部件能并行工作仅具备提高效率的可能性而并行工作的实现还需要通过并发程序设计和操作系统引入并发技术来发挥。 五：解释并发进程的无关性和交互性。 答：无关性：无关的并发进程是指他们分别在不同的变量集合上操作，一个进程的执行与其他并发进程的进展无关，即一个进程不会改变另一个与其并发执行的晋城的变量。 交互性：交互的并发进程共享某些变量，一个进程的执行可能会影响其他进程的执行结果，交互的并发进程之间具有制约关系。 六：并发进程的执行可能产生于时间有关的错误，试各举一例来说明于时间有关错误的两种表现形式。 答：时间有关的错误有两种形式，一是结果不唯一，二是永远等待。 结果不唯一：飞机售票问题。 永远等待：内存资源的管理问题。 八：试述进程的互斥和同步两个概念之间的异同。 答：进程互斥是指若干进程因相互争夺独占性资源而产生的竞争制约关系。 进程同步是指为完成共同任务的并发进程基于某个条件来协调其活动，因为需要在某些位置上排定执行的先后顺序而等待、传递顺序或消息所产生的协调制约关系。进程互斥关系是一种特殊的进程同步关系，即逐次使用进程同步资源，也是对进程使用资源的次序的一种协调。 九：什么是临界区和临界资源？临界区管理的基本规则是什么？ 答：并发进程中与共享变量有关的程序称为临界区。共享变量所代表的资源称为临界资 源。 临界区管理的基本规则： （1）：一次至多只有一个进程进入临界区内执行。 （2）：如果已有近程在临界区中，试图进入此临界区的其他程序应等待。 （3）：进入临界区内的进程应在有限时间内退出，以便让等待队列中的一个进程进入。 可把临界区的调度原则总结为三句话：互斥使用，有空让进；忙碌要等，有限等待；择一而入，算法可行。 十二：那些硬件设施可以实现临界区的管理，简述其的用法。 答：1：关中断。用法：在进程进入临界区时关中断，进程进入临界区时开中断。终端被关闭后，时钟中断也被屏蔽，进程上下文切换都是由中断事件引起的，这样进程的执行再也不会被打断，因此采用关中断、开中断的办法就能确保并发进程互斥的进入临界区。 2：测试并设置指令。用法：使用硬件所提供的“测试并设置“机器指令TS（Test and Set），可把这条指令看做函数，他有布尔型参数x和返回条件码，当TS（&x）测到x值为true时则置x为false，且根据所测试到的x值形成条件码。 3：兑换指令。用法：为每个临界区设置布尔型锁变量。 十三：什么是信号量？如何对其进行分类？ 答：信号量：将交通管制中的多种颜色的信号灯管理方法引入操作系统，让多个进程通过特殊变量展开交互。一个进程在某一关键点上被迫停止执行直至接受到对应的特殊变量值，通过这一措施，任何复杂的进程交互要求均可达到满足，这种特殊变量就是信号量。 对其进行分类：按用途分有两种:公用信号量；私有信号量。按取值分为两种：二值信号量；一般信号量，又称计数信号量。 十五：何谓管程？他有什么属性？ 答：管程是指吧分散在各个进程之间的临界区集中起来管理，并把共享资源用数据用数据结构抽象的表示，由于临界区是访问资源的代码段，建立一个“秘书“程序管理到来的访问。管程与进程具有同等的表达能力。 管程的属性：进程调用管程的过程是有一定的限制。 （1）：共享性。管程中的移出过程可悲所有要调用管程的进程共享。 （2）：安全性。管程的局部变量只能由此管理的过程访问，不允许进程访问或其他管程来直接访问，一个管程的过程也不应该访问非局部于他的变量。 （3）：互斥性。在任意时刻共享资源的进程可以访问管程中的管理此资源的过程，但最多只有一个调用者能够真正地进入管程，其他调用者必须等待直至管程可用。 十六：试述管程中条件变量的含义和作用。 答：含义：条件变量是出现在关城内的一种数据结构，且只有在管程中才能被访问，其功能是进程可以在该条件变量上等待或被唤醒他对管程内的所有过程是全局的，只能通过两个原语操作来控制它。 十七：试比较管程与进程的不同点。 答：（1）：管程定义的是公用数据结构，而进程所定义的是私有数据结构； （2）：管程把共享变量上的同步操作集中起来统一管理，而临界区却分散在每个进程中； （3）：管程是为解决进程共享资源的互斥而建立的，而进程是为战友系统资源和实现系统并发性而引入的； （4）：管程被欲使用共享资源的所有进程所调用，管程和调用它的进程不能明确并行工作；而进程之间能够并行工作，并发性是其固有特性。 （5）：管程可作为语言或操作系统成分，不必创建或撤销；而进程有生命周期，由创建产生至撤销便消失。 十八：已经有信号量和pv操作可用作同步工具，为什么还要有消息传递机制？ 答：进程同步本质上是一种仅传送信号的进程通信，通过修改信号量，进程之间可以建立联系，相互协同运行和协同工作，但他缺乏传递数据的能力。在多任务系统中，可由多个进程分工协作完成同一任务，于是他们需要共享一些数据，和相互交换信息，在很多场合需要交换大批量数据可以通过通信机制来完成。 二十二：试述信号通信机制及其实现。 答：（1）：每个进程task_struct结构中signal域专门保存接收到的信号，内核根据所发生的时间产生相应的信号并发送给接收数据。 （2）：进程task_struct结构中的blocked是信号屏蔽标记，相当于中断屏蔽寄存器。 （3）：信号处理函数的入口存放在进程task_struct的sigaction[]数组中，利用sigction函数为进程设置信号处理函数。 （4）：函数sigaction(signo,act,oldacd)为指定信号设置处理函数。 （5）：函数kill(pid,sig)用来向指定的进程或进程组发送指定信号。 （6）：信号检测和相应总发生在系统空间。 23：试述进程的低级通信机制以及其高级通信机制。 24：什么是死锁？什么是饥饿？试举生活中的例子加以说明。 答：如果一个进程集合中的每个进程都在等待只能由此集合中的其他进程才能引发的事件，而无限期的陷入僵持的局面称为死锁。 25：试述产生死锁的必要条件。 答：（1）：互斥条件：临界资源是独占资源，进程应互斥且排他的使用这些资源。 （2）：占有和等待资源：进程在等待资源得不到满足而等待时，不释放以占有资源。 （3）：不剥夺条件：又称为不可抢占，已获资源只能有进程自愿释放，不允许被其他进程剥夺。 （4）：循环等待条件：又称环路条件，存在循环等待链，其中每个进程都在循环等代练中等待下一个进程所处有的资源，造成这组进程处于永远等待状态。 26：列举死锁的各种防止策略。 答：破坏条件1（互斥条件）：使资源可同时访问而不是互斥使用，就没有锦城湖阻塞在资源上，从而不发生死锁。 破坏条件2（战友和等待条件）：静态分配是指进程必须在执行之前就申请需要的全部资源，且直至所需要的资源全部得到满足后才开始执行。 破坏条件3（不剥夺条件）：剥夺调度能够防止死锁但只是用于内存和处理器资源。 破坏条件4（循环等待条件）：采用层次分配策略，将系统中所有资源排列到不同层次中。 27：何谓银行家算法？试述其基本思想。 答：银行家算法：一种能够避免死锁的调度方法。基本思想：系统中所有进程放入进程集合，在安全状态下系统受到进程的资源请求后，先把资源试探性的分配给他，然后系统将剩下的可用资源和进程集合中的其他进程还需要的资源数作比较，找出剩余资源能满足最大需求量的进程，从而保证进程运行完毕并归还全部资源；这时吧这个进程从进程集合中删除，归还其所占用的所有资源，系统的剩余资源则更多；反复执行上述步骤，最后检查进程集合，若为空则表明本次申请可行，系统处于安全状态，可以真正实施本次分配，否则只要进程集合非空，系统便处于不安全状态，本次资源分配暂不实施，让申请资源的进程等待。 28：解释进程-资源分配图，死锁的判定法则，死锁定理。 答：设某个计算机系统中有多种资源和多个进程，每个资源类用一个方框表示，方框中的黑圆点表示此资源类中的各个资源，每个进程用一个类来表示，用有向边表示进程申请资源和资源被分配的情况。 死锁判定： （1）：如果进程-资源分配图中无环路，此时系统没有发生死锁。 （2）：如果进程-资源分配图中有环路，且每个资源类中仅有一个资源，则系统中发生死锁。此时环路是系统发生死锁的充要条件，环路中的进程就是死锁中的进程。 （3）：如果进程-资源分配图中有环路，且所涉及的资源类中有多个资源，则环路的存在只是系统发生死锁的必要条件而不是充分条件，系统不一定会发生死锁。 死锁定理即系统产生死锁的充要条件为：当且仅当此状态的进程-资源分配图是不可完全简化的。 29：系统有输入及和打印机各一台，现有两个进程都要使用他们，采用PV操作实现请求使用和归还资源后还会产生死锁吗？说明理由，若是，则给出防止死锁的方法。 答：不会产生死锁，因为系统的输入机和行式打印机作为临界资源分别用两个信号量表示，初值为1，在需要使用它们时用P操作申请，在需要归还他们时用V操作释放，这样就保证了两个进程对输入机和行式打印机的互斥作用，可防止死锁的产生。 34：什么是竞争条件？ 答：多个进程并发访问和操作同一数据且执行结果与访问的特定顺序有关，称为竞争条件 35：什么是忙式等待？ 答：不进入等待状态的等待称为忙式等待。 38：试举出系统资源分配图有环锁和环而不锁的示例。 答： 应用题： 1：有三个并发进程：R负责从输入设备读入信息块，M负责对信息块加工处理；P负责打印输出信息块。今提供； 1） 一个缓冲区，可放置K个信息块； 2） 二个缓冲区，每个可放置K个信息块； 试用信号量和P、V操作写出三个进程正确工作的流程。 答： 2：设有n个进程共享一个互斥段，如果： (1)每次只允许一个进程进入互斥段； (2)每次最多允许m个进程（m≤n）同时进入互斥段。 试问：所采用的信号量初值是否相同？信号量值的变化范围如何？ 答：所采用的互斥信号量初值不同。 1）互斥信号量初值为1，变化范围为[-n+1，1]。当没有进程进入互斥段时，信号量值为1；当有1个进程进入互斥段但没有进程等待进入互斥段时，信号量值为0；当有1个进程进入互斥段且有一个进程等待进入互斥段时，信号量值为-1；最多可能有n-1个进程等待进入互斥段，故此时信号量的值应为-(n-1)也就是-n+1。 2）互斥信号量初值为m，变化范围为[-n+m，m]。当没有进程进入互斥段时，信号量值为m；当有1个进程进入互斥段但没有进程等待进入互斥段时，信号量值为m-1；当有m个进程进入互斥段且没有一个进程等待进入互斥段时，信号量值为0；当有m个进程进入互斥段且有一个进程等待进入互斥段时，信号量值为-1；最多可能有n-m个进程等待进入互斥段，故此时信号量的值应为-(n-m)也就是-n+m。 3：有两个优先级相同的进程P1和P2，各自执行的操作如下，信号量S1和S2初值均为0。试问 P1、P2并发执行后，x、y、z的值各为多少？ P1： P2： begin begin y:=1; x:=1; y:=y+3; x:=x+5; V(S1); P(S1); z:=y+1; x:=x+y; P(S2); V(S2); y:=z+y z:=z+x; end. End. 5：有一阅览室，读者进入时必须先在一张登记表上登记，该表为每一座位列出一个表目，包括座号、姓名，读者离开时要注销登记信息；假如阅览室共有100个座位。试用：1）信号量和P、V操作；2）管程，来实现用户进程的同步算法。 答：1) 使用信号量和P、V操作： 6：在一个盒子里，混装了数量相等的黑白围棋子。现在用自动分拣系统把黑子、白子分开，设分拣系统有二个进程P1和P2，其中P1拣白子；P2拣黑子。规定每个进程每次拣一子；当一个进程在拣时，不允许另一个进程去拣；当一个进程拣了一子时，必须让另一个进程去拣。试写出两进程P1和P2能并发正确执行的程序。 答：实质上是两个进程的同步问题，设信号量S1和S2分别表示可拣白子和黑子，不失一 般性，若令先拣白子。 coend 8：设公共汽车上，司机和售票员的活动分别如下： 司机的活动：启动车辆：正常行车；到站停车。 售票员的活动：关车门；售票；开车门。 在汽车不断地到站、停车、行驶过程中，这两个活动有什么同步关系？用信号量和P、V操作实现它们的同步。 答：在汽车行驶过程中，司机活动与售票员活动之间的同步关系为：售票员关车门后，向司机发开车信号，司机接到开车信号后启动车辆，在汽车正常行驶过程中售票员售票，到站时司机停车，售票员在车停后开门让乘客上下车。因此，司机启动车辆的动作必须与售票员关 车门的动作取得同步；售票员开车门的动作也必须与司机停车取得同步。 应设置两个信号量：s1、s2；s1表示是否允许司机启动汽车(其初值为0)；s2表示是否允许售票员开门(其初值为0)。用P、V原语描述如下： 9：一个快餐厅有4类职员：（1）领班：接受顾客点菜；（2）厨师：准备顾客的饭菜；（3）打包工：将做好的饭菜打包；（4）出纳员：收款并提交食品。每个职员可被看作一个进程，试用一种同步机制写出能让四类职员正确并发运行的程序。 答：S的值表示它代表的物理资源的使用状态：S>0表示还有共享资源可供使用。S=0表示 共享资源正被进程使用但没有进程等待使用资源。S<0表示资源已被分配完，还有进程等待使用资源。 10：二个并发进程并发执行，其中，A、B、C、D、E是原语，试给出可能的并发执行路径。 Process P Process Q begin begin A； C； B； D； C； end； end； 16：另一个经典同步问题：吸烟者问题(patil，1971)。三个吸烟者在一个房间内，还有一个香烟供应者。为了制造并抽掉香烟，每个吸烟者需要三样东西：烟草、纸和火柴，供应者有丰富货物提供。三个吸烟者中，第一个有自己的烟草，第二个有自己的纸和第三个有自己的火柴。供应者随机地将两样东西放在桌子上，允许一个吸烟者进行对健康不利的吸烟。当吸烟者完成吸烟后唤醒供应者，供应者再把两样东西放在桌子上，唤醒另一个吸烟者。试采用： (1)信号量和P、V操作； (2)管程编写他们同步工作的程序。 18：系统有同类资源m个，被n个进程共享，问：当m＞n和m≤n时，每个进程最多可以请求多少个这类资源时，使系统一定不会发生死锁? 答：当m≤n时，每个进程最多请求1个这类资源时，系统一定不会发生死锁。当m>n时，如果m/n不整除，每个进程最多可以请求”商+1”个这类资源，否则为”商”个资源，使系统一定不会发生死锁。 19：N个进程共享M个资源，每个进程一次只能申请/释放一个资源，每个进程最多需要M个资源，所有进程总共的资源需求少于M+N个，证明该系统此时不会产生死锁。 答：设max（i）表示第i个进程的最大资源需求量，need(i)表示第i个进程还需要的资源量，alloc(i)表示第i个进程已分配的资源量。由题中所给条件可知： max(1)+┅+max(n)=(need(1)+┅+need(n))+((alloc(1)+┅+alloc(n)) 21：Jurassic公园有一个恐龙博物馆和一个花园，有m个旅客和n辆车，每辆车仅能乘一个旅客。旅客在博物馆逛了一会，然后，排队乘坐旅行车，当一辆车可用时，它载入一个旅客，再绕花园行驶任意长的时间。若n辆车都已被旅客乘坐游玩，则想坐车的旅客需要等待。如果一辆车已经空闲，但没有游玩的旅客了，那么，车辆要等待。试用信号量和P、V操作同步m个旅客和n辆车子。 答： 23：设当前的系统状态如下，系统此时Available=(1，1，2)： Claim Allocation 进程, R1 R2 R3 R1 R2 R3 P1 3 2 2 1 0 0 P2 6 1 3 5 1 1 P3 3 1 4 2 1 1 P4 4 2 2 0 0 2 (1) 计算各个进程还需要的资源数Cki-Aki? (2) 系统是否处于安全状态，为什么? (3) P1发出请求向量request2(1，0，1)，系统能把资源分给它吗？ (4) 若在P2申请资源后，若P1发出请求向量request1(1，0，1)，系统能把资源分给它吗？ (5) 若在P1申请资源后，若P3发出请求向量request3(0，0，1)，系统能把资源分给它吗？ 答： (1) P1，P2，P3，P4的Cki-Aki分别为：(2，2，2)、(1，0，2)、(1，0，3)、(4，2，0) (2) 系统处于安全状态，存在安全序：P2，P1，P3，P4 (3) 可以分配，存在安全序列：P2，P1，P3，P4。 (4) 不可以分配。 (5) 不可以分配。 24：系统有A、B、C、D共4种资源，在某时刻进程P0、P1、P2、P3和P4对资源的占有和需求情况如表，试解答下列问题： Allocation Claim Available 进程 A B C D A B C D A B C D P0 0 0 3 2 0 0 4 4 1 6 2 2 P1 1 0 0 0 2 7 5 0 P2 1 3 5 4 3 6 10 10 P3 0 3 3 2 0 9 8 4 P4 0 0 1 4 0 6 6 10 (1)系统此时处于安全状态吗？ (2) 若此时P1发出request1(1、2、2、2)，系统能分配资源给它吗？为什么？ 答： (1)系统处于安全状态，存在安全序列：P0，P3，P4，P1，P2。 (2)不能分配，否则系统会处于不安全状态。 25：把死锁检测算法用于下面的数据，并请问： Available=(1，0，2，0) 1 1 0 0 3 0 1 1 0 1 1 2 Allocation= 0 1 0 0 Need= 3 1 1 1 1 0 0 0 1 1 0 1 0 0 1 0 =2 1 1 0 0 0 0 0 (1)此时系统此时处于安全状态吗？ (2)若第二个进程提出资源请求request2(0，0，1，0)，系统能分配资源给它吗？ (3)若第五个进程提出资源请求request5(0，0，1，0)，系统能分配资源给它吗？ 答： (1)此时可以找出进程安全序列：P4，P1，P5，P2，P3。故系统处于安全状态。 (2)可以分配，存在安全序列：P4，P1，P5，P2，P3。 (3)不可分配，系统进入不安全状态。 26:考虑一个共有150个存储单元的系统，如下分配给三个进程，P1最大需求70,己占有25；P2最大需求60,己占有40；P3最大需求60,己占有45。使用银行家算法，以确定下面的任何一个请求是否安全。(1)P4进程到达，P4最大需求60,最初请求25个。(2)P4进程到达，P4最大需求60,最初请求35。如果安全，找出安全序列；如果不安全，给出结果分配情况。 答： 29：进程A1、A2、…、An1通过m个缓冲区向进程B1、B2、…、Bn2不断地发送消息。发送和接收工作符合以下规则： (1) 每个发送进程每次发送一个消息，写进一个缓冲区，缓冲区大小与消息长度相等； (2) 对每个消息，B1、B2、…、Bn2都需接收一次，并读入各自的数据区内； (3) 当M个缓冲区都满时，则发送进程等待，当没有消息可读时，接收进程等待。试用信号量和PV操作编制正确控制消息的发送和接收的程序。 答： 30：某系统有R1设备3台，R2设备4台，它们被P1、P2、P3和P4进程共享，且已知这4个进程均按以下顺序使用设备：→申请R1→申请R2→申请R1→释放R1→释放R2→释放R1 (1) 系统运行中可能产生死锁吗？为什么？ (2) 若可能的话，请举出一种情况，并画出表示该死锁状态的进程—资源图。 答： 39：一组生产者进程和一组消费者进程共享九个缓冲区，每个缓冲区可以存放一个整数。 生产者进程每次一次性向3个缓冲区写入整数，消费者进程每次从缓冲区取出一个整数。请用：(1)信号量和P、V操作； (2)管程，写出能够正确执行的程序。 答： 41：下述流程是解决两进程互斥访问临界区问题的一种方法。试从“互斥”(mutual exclusion)、“空 闲让进”(progress)、“有限等待”(bounded waiting)等三方面讨论它的正确性。如果它是正确的， 则证明之；如果它不正确，请说明理由。 program attemp; var c1,c2:integer; procedure p1; (/* 对第一个进程p1 */) begin repeat Remain Section 1; repeat c1:=1-c2 until c2<>0; Critical Section; (/* 临界区 */) c1:=1 until false end; procedure p2; (/* 对另一个进程p2 */) begin repeat Remain Section 2; repeat c2:=1-c1 until c1<>0; Critical Section; (/* 临界区 */) c2:=1 until false end; begin (/* 主程序 */) c1:=1; c2:=1; cobegin p1;p2 (/* 两进程p1, p2开始执行 */) coend end. 答： 52：在一个分页存储管理系统中，用 free[index]数组记录每个页框状态，共有 n 个页框(index=0，…，n-1)。当free[index]=true时，表示第index个页框空闲，free[index]=false时，表示第index个页框。试设计一个管程，它有两个过程acquire和release分别负责分配和回收一个页框。 59：试利用一般信号量机制解决读者-写者问题。 答：设置互斥信号量wmutex 表示写者间、读者和写者间互斥 用readcount变量来记录读者数： Var rmutex,wmutex: semaphore:=1,1 ; readcount :integer :=0 ; begin parbegin reader:begin repeat P(rmutex) if readcount=0 then P(wmutex); readcount=readcount+1; V(rmutex) read text P(rmutex) readcount=readcount+1; if readcount=0 then V(wmutex); V(rmutex) until false writer:begin repeat P(wmutex); write text; V(wmutex); until false end parend end 60：试利用二值信号量解决生产者-消费者问题。 答：为解决并行所带来的死锁问题，在wait操作中引入AND条件，其基本思想是将进程在整个运行过程中所需要的所有临界资源，一次性地全部分配给进程，用完后一次性释放. 解决生产者－消费者问题可描述如下: var mutex,empty,full: semaphore:=1,n,0; buffer: array[0,...,n-1] of item; in,out: integer:=0,0; begin parbegin producer: begin repeat . produce an item in nextp; . wait(empty); wait(s1,s2,s3,...,sn); //s1,s2,...,sn为执行生产者进程除empty外其余的条件 wait(mutex); buffer(in):=nextp; in:=(in+1) mod n; signal(mutex); signal(full); signal(s1,s2,s3,...,sn); until false; end consumer: begin repeat wait(full); wait(k1,k2,k3,...,kn); //k1,k2,...,kn为执行消费者进程除full外其余的条件 wait(mutex); nextc:=buffer(out); out:=(out+1) mod n; signal(mutex); signal(empty); signal(k1,k2,k3,...,kn); consume the item in nextc; until false; end parend end
发布评论