山东专升本操作系统讲义.docx

《山东专升本操作系统讲义.docx》由会员分享，可在线阅读，更多相关《山东专升本操作系统讲义.docx（44页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、操作系统讲义（上）第一章操作系统概述主要知识点：一、操作系统的目标和作用计算机系统由硬件和软件两局部组成。操作系统是配置在计算机硬件上的第一层软件，是对硬件的首次 扩充。1 .操作系统的目标：有效性，方便性，可扩充性，开放性。2 .操作系统的作用（1）从一般用户的观点看，OS是用户与计算机硬件系统之间的接口。OS处于用户与计算机硬件系统 之间，用户通过OS来使用计算机系统。OS是一个系统软件，因此是软件接口，用户通过命令方式，系统调 用方式和图形、窗口方式来使用计算机。（2）从资源管理的观点看，OS是计算机系统资源的管理者。资源可分为处理器，存储器，I/O设备以 及信息（数据和程序）。OS主要

2、是对这四类资源进行有效的管理。（3） OS实现了对计算机资源的抽象，隐藏了对硬件操作的细节，使用户更方便地使用机器。二、操作系统的开展过程表1.1操作系统的开展过程操作系统的产生操作系统的形成微机操作系统的开展无操作系统时的计算机系统（40年代）单道批处理（50年代）多道批处理（60年代初） 分时系统（60年代中）实时操作系统（60年代中）单用户单任务操作系统（CP/M, MS-DOS）单用户多任务操作系统（Windows）多用户多任务操作系统（UNIX, Solaris OS, Linux）.无操作系统时的计算机系统（1）电子管计算机（19461958）,无操作系统，由手工控制作业的输入输出

3、，通过控制台开关启动程 序运行。缺点：用户独占全机，CPU等待人工操作。（2）脱机输入/输出方式（Off-Line I/O）,事先将装有用户程序和数据的纸带（或卡片）装入纸带输 入机，在一台外围机的控制下，把纸带上的数据（程序）输入到磁带上，当CPU需要这些程序和数据时，再 从磁带上将其高速地调入内存。CPU需要输出时，CPU直接高速地把数据从内存送到磁带上，然后再在另一 台外围机的控制下，将磁带上的结果通过相应的输出设备输出。程序和数据的输入和输出都是在外围机的控 制下完成的，是在脱离主机的情况下进行的，所以称为脱机输入/输出方式。优点：减少了 CPU的空闲时间, 提高1/0速度。1 .单道

4、批处理系统（1）单道批处理系统的工作过程：用户将作业交到机房，操作员将一批作业输入到辅存（如磁带）上, 形成一个作业队列。当需要调入作业时，由监控程序从这一批中选一道作业调入内存运行。当这一作业完成 时，监控程序调入另一道程序，直到这一批作业全部完成。一个作业从提交开始直到完成往往要经历下述三级调度。1 .高级调度高级调度又称宏观调度、作业调度或长程调度，其主要任务是按一定的原那么从外存处于后备状态的作业 中挑选一个（或多个）作业，给它（们）分配内存、输入/输出设备等必要的资源，并建立相应的进程，以 使它（们）获得竞争处理机制的权利。批处理系统中大多配有作业调度，而其他系统中通常不需要配置作业

5、调度。作业调度的执行效率较低， 通常为几分钟一次。（1）作业:作业不仅包含了通常的程序和数据，还应配有一个作业说明书，系统根据该说明书来对程序 的运行进行控制。（2）作业步：在作业运行期间，每个作业都必须经过假设干个相对独立，又相互关联的顺序加工步骤才能 得到结果，把其中每一个加工步骤称为一个作业步。（3）作业流：假设干个作业进入系统后，被依次存放在外存上，这便形成了输入的作业流；在操作系统的 控制下，逐个作业进行处理，便是处理作业流。（4）作业控制块：为了管理和调度作业，在多道批处理系统中为每个作业设置了一个作业控制块，它是 作业在系统中存在的标志，其中保存了系统对作业进行管理和调度所需的全

6、部信息。（5）作业调度需决定的问题：决定接纳多少个作业，决定接纳哪些作业2 .低级调度低级调度又称微观调度、进程调度或短程调度，其主要任务是按某种策略和方法选取一个处于就绪状态 的进程，将处理机分配给它。进程调度的运行频率很高，一般几十毫秒要运行一次。（1）低级调度的功能：保存处理机的现场信息；按某种算法选取进程；把处理器分配给进程。（2）低级调度的三个机制：排队器，分派器和上下文切换机制。（3）低级调度的方式：非抢占式，抢占式。非抢占式是指一旦把处理机分配给某进程后，不管它要运行多长时间，都一直让它运行下去，决不会 因为时钟中断等原因而抢占正在运行进程的处理机，即使有某个更为重要或紧迫的进程

7、进入就绪队列，仍然 让正在执行的进程继续执行，直到该进程完成或发生某种事件而进入阻塞状态时，才把处理机分配给更为重 要或紧迫的进程。抢占式是指当一个进程正在处理机上执行时，假设有某个更为重要或紧迫的进程需要使用处理机，那么立 即暂停正在执行的进程，将处理机分配给这个更为重要或紧迫的进程。抢占原那么有：优先权原那么，短作业优 先原那么，时间片原那么等。3 .中级调度中级调度又称中程调度，主要目的是为了提高内存利用率和系统吞吐量，其主要任务是按照给定的原那么 和策略，将处于外存对换区中的重又具备运行条件的就绪进程调入内存，或将处于内存就绪状态或内存阻塞 状态的进程交换到外存对换区中。中级调度主要涉

8、及内存管理，因此将在存储管理局部介绍。三种调度中，进程调度运行频率最高，在分时系统中通常是WlOOms便进行一次进程调度，因而进程 调度算法不能太复杂。作业调度往往是发生在一个（批）作业运行完毕，退出系统，而需要重新调入一个（批） 作业进入时，帮作业调度的周期较长，大约几分钟一次。中级调度的运行频率，介于上述两种调度之间。 二、调度队列模型和调度准那么 1.调度队列模型（1）仅有进程调度的调度队列模型在分时系统中，通常仅设置了进程调度，用户键入的命令和数据，都直接送入内存，对于命令，是由OS 为之建立一个进程。常把就绪进程组织成FIFO队列形式。（2）具有高级和低级调度的调度队列模型在批处理系

9、统中，不仅进程调度，而且还需要有作业调度。与仅有进程调度的调度队列模型的区别： 就绪队列的形式：在批处理系统中，最常用的是最高优先权调度算法，相应的最常用的就绪队列形式 是优先权队列。（仅有进程调度的模型就绪队列采用FIFO队列形式）设置多个阻塞队列。（3）同时具有三级调度的调度队列模型os引入中级调度，可把进程的就绪状态分为内存就绪和外存就绪，阻塞状态分成内存阻塞和外存阻塞。2.选择调度方式和算法的准那么(1)面向用户的准那么周转时间短：评价批处理系统性能的准那么a.周转时间：指作业被提交给系统开始，到作业完成为止的时间间隔。分为作业周转时间和进程周转 时间，作业周转时间包括：作业在外存上的

10、等待时间；进程在就绪队列中等待时间；进程在cpu上执行时间; 等待I/O时间。作为系统管理者希望作业平均周转时间最短，有利于大多数用户。可把平均周转时间描述为:b.带权周转时间：作业的周转时间7与系统为它提供服务的时间7S之比，即胎7/7S称为，而平均带权周转时间那么可表示为:响应时间快：评价分时系统性能的准那么响应时间：指从用户通过键盘提交一个请求开始，到系统首次产生响应为止的时间间隔。它包括：键盘 请求送入处理机时间；处理机处理请求时间；形成响应送回终端时间。截止时间有保证：评价实时系统性能的准那么截止时间：某任务必须开始执行的最迟时间，或必须完成的最迟时间。优先权原那么：在批处理，分时，

11、实时系统中都使用让紧急作业及时得到处理，有时甚至是立即抢占。(2)面向系统的准那么系统吞吐量高：评价批处理系统性能的重要指标吞吐量：指在单位时间内系统完成的作业数。处理器利用率好：适用于大中型多用户系统，不适于单用户或实时系统各类资源的平衡利用：适用于大中型多用户系统，不适于单用户或实时系统三、调度算法1 .先来先服务调度算法先来先服务调度算法是一种最简单的调度算法，可用于作业调度也可用于进程调度。(1)作业调度：每次调度是从后备队列中，选择一个或多个最先进入该队列的作业，将它们调入内存， 为它们分配资源，创立进程，然后放入就绪队列。(2)进程调度：从就绪队列中，选择一个最先进入该队列的进程，

12、把处理器分配给该进程，使之得到执 行。该进程一旦占有了处理器，它就一直运行下去，直到该进程完成或因发生事件而阻塞，才退出处理器。假设采用先来先服务调度算法，并且一个运行时间长的进程占有了处理机，那么会使很多晚到的运行时间短 的进程等待时间过长，引起许多短进程用户的不满。比拟有利于长作业(进程)，而不利于短作业(进程) 因此，先来先服务算法很少用作主要调度策略，但它常作为一种辅助调度算法使用。2,短作业(进程)优先调度算法(1)短作业优先(SJF)：从后备队列中选择一个或假设干个估计运行时间最短的作业，将它们调入内存运 行。(2)短进程优先(SPF)：从就绪队列中选择一个估计运行时间最短的进程，

13、将处理器分配给该进程，使 之占有处理器并执行，直到该进程完成或因发生事件而阻塞，然后退出处理器，再重新调度。短作业优先调度算法照顾到了系统中占大局部的短进程，有效地降低了作业的平均等待时间，提高了系 统的吞吐量。但对长作业不利，没有考虑紧迫度，根据估计时间不准确。3.高优先权优先调度算法对于作业调度从后备队列中选择一个优先级最高的作业，调入内存运行。对于进程调度从就绪队列中选 择一个优先级最高的进程，让其获得处理器并执行。(1)优先权调度算法的类型：基于优先权的调度算法还可以按调度方式不同分为非抢占式优先权调度算法和抢占式优先权调度算 法。非抢占式优先权调度算法的实现思想是系统一旦将处理机分配

14、给就绪队列中优先权最高的进程后，该 进程便一直运行下去，直到由于其自身的原因（任务完成或等待事件）主动让出处理机时，才将处理机分配 给另一个更高优先权的进程。抢占式优先权调度算法的实现思想是将处理机分配给优先权最高的进程，使之运行。在进程运行过程 中，一旦出现了另一个优先权更高的进程时，进程调度程序就停止原运行进程，而将处理机分配给新出现的 高优先权进程。（2）优先权的类型进程的优先权用于表示进程的重要性及运行的优先性。进程优先权通常分为两种：静态优先权和动态优 先权。静态优先权是在创立进程时确定的，确定之后在整个进程运行期间不再改变。确定静态优先权的依据 有进程的类型、进程所使用的资源、进程

15、的估计运行时间等因素。进程所索取的资源越多，估计的运行时间 越长，进程的优先权越低。进程类型不同，优先权也不同，如联机用户进程的优先权高于脱机用户进程的优 先权。动态优先权是指在创立进程时，根据系统资源的使用情况和进程的当前特点确定一个优先权，在进程 运行过程中在根据情况的变化调整优先权。动态优先权一般根据进程占有CPU时间的长短、进程等待CPU时 间的长短等因素确定，占有处理机的时间越长，那么优先权越低；等待时间越长，那么优先权越高。（3）高响应比优先调度算法高响应比优先调度算法是从就绪队列中选择一个响应比最高的进程，让其获得处理器执行，直到该进程 完成或因等待事件而退出处理器为止。（优先权

16、）响应比R =（要求服务时间+作业等待时间）要求服务时间从上式可见：假设等待时间相同，那么要求服务时间愈短,其优先权愈高一SPF；假设服务时间相同，优先权决定于等待时间一-FCFS；长作业假设等待时间足够长，优先级会升高，也能获得CPU。由此可看出此算法既照顾了短进程，又考虑了进程到达的先后次序，也不会使长进程长期得不到服务， 因此是一个比拟全面考虑的算法；但每次进行调度时，都需要对各个进程计算响应比。所以系统开销很大， 比拟复杂。适于批处理系统 4.基于时间片轮转调度算法在时间片轮转调度算法中，系统将所有就绪进程按到达时间的先后次序排成一个队列，进程调度程序总 是悬着队列中的第一个进程执行，

17、并规定执行一定时间（例如100ms,该时间称为时间片）。当该进程使用完 这一时间片时（即使进程并未完成其运行），系统将它送至就绪队列队尾，再把处理机分配给下一个就绪进 程。这样，处于就绪队列中的进程就可以依次轮流地获得一个时间片的处理时间，然后回到队列尾部，如此 不断循环，直至完成为止。在时间片轮转调度算法中，时间片的大小对系统性能的影响很大。如果时间片太大，以至于所有进程都 能在一个时间片内执行完毕，那么时间片轮转调度算法就退化成先来先服务调度算法。如果时间片很小，那么 处理机将在进程结束之间频繁切换，处理机真正用于运行用户进程的时间将减少。因此时间片的大小应选择 恰当，一个较为可取的大小是

18、，时间片略大于一次典型的交互所需要的时间，这样可使大多数进程在一个时 间片内完成。5.多级反响队列调度算法多级反响队列调度算法的实现思想如下：首先应设置多个就绪队列，并为各个队列赋予不同的优先权。第一个队列的优先权最高，第二个队列次 之，其余队列的优先权逐次降低。其次，每个队列中进程执行时间片的大小也各不相同，进程所在队列的优先权愈高，其相应的时间片愈 短。例如，第i+1个队列的时间片是第i个队列时间片的两倍。第三，当一个新进程进入内存后，首先将它放入第一个队列的末尾，按先来先服务的原那么排队等待调度。 当轮到该进程时，如果能在次时间片内完成，便可准备撤离系统；如果它在一个时间片结束是尚未完成

19、， 调度程序便将该程序转入第二个队列的末尾，再同样地按先来先服务原那么等待调度执行；如果它在第二个队 列中运行一个时间片后仍为完成，再以同样方法将它转入第三个队列。如此下去，直到最后一个队列中使用 时间片轮转调度算法。第四，仅当第一个队列空闲时，调度程序才调度第二个队列中的进程运行；仅当第1至（i-1）个队列 均为空时，才会调度第i个队列中的进程运行。当处理机正为第i个队列中的某进程服务时，假设又有新进程 进入优先权较高的队列，那么此时新进程将抢占正在运行进程的处理机，即由调度程序把正在执行的进程放回 第i个队列末尾，重新将处理机分配给新进程。可以看出，多级队列调度算法优先照顾I/O繁忙的进程

20、。I/O繁忙的进程在获得一点CPU时间后就会提 出输入/输出请求，因此它们总是被保持在1、2级等较前面的队列中，总能获得较多的调度机会。对于CPU 繁忙的进程，它们需要较长的CPU时间，因此会逐渐地由级别高的队列往下降，以获得更多的CPU时间，它 们“沉”得越深，被调度到的机会就越少。但是，一旦被调度到，就会获得更多的CPU时间。四、实时调度1.实现实时调度的基本条件（1）提供必要的信息：就绪时间、开始截止时间和完成截止时间、处理时间、资源要求、优先级；（2）系统处理能力强：在实时系统中，通常都有着多个实时任务。假设处理机的处理能力不够强，那么有 可能因处理机忙不过来而使某些实时任务不能得到及

21、时处理，从而导致发生难以预料的后果。（3）采用抢占式调度机制：在含有硬实时任务的实时系统中，广泛采用抢占机制。当一个优先权更高 的任务到达时，允许将当前任务暂时挂起，而令高优先权任务立即投入运行，这样便可满足该硬实时任务对 截止时间的要求。（4）具有快速切换机制对外部中断的快速响应能力。为使在紧迫的外部事件请求中断时系统能及时响应，要求系统具有快速 硬件中断机构，还应使禁止中断的时间间隔尽量短，以免耽误时机（其它紧迫任务）。快速的任务分派能力。在完成任务调度后，便应进行任务切换。为了提高分派程序进行任务切换时的 速度，应使系统中的每个运行功能单位适当的小，以减少任务切换的时间开销。2 .实时调

22、度算法的分类（1）非抢占式调度算法非抢占式轮转调度算法：该算法常用于工业生产的群控系统中，由一台计算机控制假设干个相同的（或 类似的）对象，为每一个被控对象建立一个实时任务，并将它们排成一个轮转队列。调度程序每次选择队列 中的第一个任务投入运行。非抢占式优先调度算法：该算法常用于有一定时间要求的实时控制系统之中。当这些要求较为严格的 实时任务到达时，把它们安排在就绪队列的队首，等待当前任务自我终止或运行完成后才能被调度执行。（2）抢占式调度算法基于时钟中断抢占的优先权调度算法：在某实时任务到达后，如果该任务的优先级高于当前任务的优 先级，这时并不立即抢占当前任务的处理机，而是等到时钟中断到来时

23、，调度程序才剥夺当前任务的执行， 将处理分配给新到的高优先权任务。立即抢占的优先权调度算法：一旦出现外部中断，只要当前任务未处于临界区，便立即剥夺当前任务 的执行，把处理机分配给请求中断的紧急任务。3 .常用实时调度算法（1）最早截止时间优先即EDF（Earliest Deadline First）算法该算法根据任务的开始截止时间来确定任务的优先级，截止时间越早，优先级越高。在就绪队列中任务 按其截止时间排列，队首任务先分配处理机。可以是抢占式或非抢占式。（2）最低松弛度优先即LLF（Least Laxity First）算法该算法是根据任务紧急（或松弛）的程序，来确定任务的优先级。任务的紧急

24、度越高，其优先级越高， 并使之优先执行。松弛度最低的任务排在队列最前面，调度程序总是选择就绪队列中的首任务执行。该算法 主要采用抢占调度方式。五.产生死锁的原因和必要条件.死锁的概念所谓死锁是指多个进程因竞争资源而造成的一种僵局，假设无外力作用，这些进程都将无法向前推进。死 锁是计算机系统和进程所处的一种状态。1 .死锁产生的原因死锁产生的原因有以下两点：（1）系统资源缺乏。（2）进程推进顺序不当。2 .死锁产生的必要条件死锁产生的必要条件有以下四条：（1）互斥条件。进程要求对所分配的资源进行排它性控制，即在一段时间内某资源仅为一个进程所占 有。（2）请求和保持条件。局部分配条件又称请求和保持

25、条件。进程每次申请它所需要的一局部资源，在 等待新资源的同时，进程继续占有已分配到的资源。（3）不剥夺条件。进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走，即只能由获得该 资源的进程自己来释放。（4）环路等待条件。存在一种进程资源的循环等待链，链中每一个进程已获得的资源同时被链中下一 个进程所请求。3 .处理死锁的基本方法（1）预防死锁：通过设置某些限制条件，去破坏死锁四个必要条件中的一个或多个，来防止死锁。（2）防止死锁：不事先采取限制去破坏产生死锁的条件，而是在资源的动态分配过程中，用某种方法 去防止系统进入不平安状态，从而防止死锁的发生。（3）检测死锁：事先并不采取任何限制，也

26、不检查系统是否进入不平安区，允许死锁发生，但可通过 检测机构及时检测出死锁的发生，并精确确定与死锁有关的进程和资源，然后采取适当措施，将系统中已发 生的死锁清除掉（4）解除死锁：与检测死锁相配套，用于将进程从死锁状态解脱出来。常用的方法是撤消或挂起一些 进程。以回收一些资源，再将它们分配给处于阻塞状态的进程，使之转为就绪状态。六、预防死锁的方法L死锁的预防要想防止死锁的发生，只需破坏死锁产生的四个必要条件之一即可。互斥条件是设备的固有特性，不能 改变。（1）摒弃“请求和保持”条件为了破坏局部分配条件，可以采用预先分配方法。预先静态分配法要求进程在其运行之前一次申请它所 需要的全部资源，在它的资

27、源为满足前。这种方法既简单有平安，但降低了资源的利用率。以打印机为例， 一个作业可能只在最后完成时才需要打印计算结果，但在作业运行前就把打印机分配给了它，那么在作业的 整个执行过程中打印机完全处于闲置状态。（2）摒弃“不剥夺”条件为了破坏剥夺条件，可以可以指定这样的策略：一个已获得某些资源的进程，假设新的资源请求不能立即 得到满足，那么它 必须释放所有已获得的资源，以后需要资源时在重新申请。这意味着一个进程已获得的资 源在运行过程中可被剥夺，从而破坏了不剥夺条件。该策略实现起来比拟复杂，释放已获得资源可能造成前 一段工作的失效，重复申请和释放资源会增加系统的开销，降低系统吞吐量。（3）摒弃“环

28、路等待”条件为了破坏环路等待条件，可以采用有序资源分配法。有序资源分配法的实现思想是将系统中的所有资源 都按类型赋予一个编号（如打印机为1,磁带机为2）,要求每一个进程均严格地按照编号递增的次序请求资 源，同类资源一次申请完。也就是说，只要进程提出请求资源Ri,那么在以后的请求中，只能请求排在R后面 的那些资源（i为资源编号），不能在请求编号低于R的那些资源。对资源请求作了这样的限制后，系统中就 不会在再出现几个进程对资源的请求成为环路的情况。这种方法存在的主要问题是各种资源编号后不宜修改，从而限制了新设备的增加；尽管在为资源编号是 已考虑到大多数作业实际使用这些资源的顺序，但也经常会发生作业

29、使用资源的顺序与系统规定顺序不同的 情况，从而造成资源的浪费。2 .死锁的防止在预防死锁的方法中所采取的几种策略，总的来说都施加了较强的限制条件，虽然实现起来较为简单， 但却严重地损害了系统的性能。在防止死锁的方法中，所施加的限制条件较弱，有可能获得较好的系统性能。 在该方法中，把系统的状态分为平安状态和不平安状态，只要能使系统始终处于平安状态，便可以防止死锁 的发生。（1）平安状态与不平安状态在防止死锁的方法中，允许进程动态地申请资源，系统在进行资源分配之前，先计算资源分配的平安性, 假设此次分配不会导致系统进入不平安状态，便将资源分配给进程，否那么让进程等待。假设在某一时刻，系统能按某种顺

30、序如Pl, P2,，Pn来为每个进程分配其所需的资源，直到最大需求， 使每个进程都可以顺利地完成，那么称此时的系统状态为平安状态，程序列（Pl, P2,，Pn为平安序列。假设某 一时刻系统中不存在这样一个平安序列，那么称此时的系统状态为不平安状态。虽然并非所有不平安状态都是死锁状态，但当系统进入不平安状态后，便可能进入死锁状态；反之，只 要系统处于平安状态，系统便可以防止进入死锁状态。（2）银行家算法银行家算法如下：设Requesti是进程Pi的请求向量，Requesti （j）=k表示进程Pi请求分配R类资源k个。当Pi发出资源 请求后，系统按下述步骤进行检查： 假设果RequestiNee

31、dn那么转向步骤；否那么出错，因为进程所需要的资源数以超过了它所宣布的最 大值。如果RequestiSAvailabe,那么转向步骤；否那么，表示系统中尚无足够放入空闲资源满足进程P的 申请，Pi必须等待。系统假设把资源分配给进程Pi,并修改相应数值：系统执行平安性算法，检查此次资源分配后系统是否处于平安状态。假设平安，才正式将资源分配给 进程Pi,以完本钱次分配；否那么，将本次的试分配作废，恢复原来的资源分配状态，让进程P等待。3 .死锁的检测和解除前面介绍的死锁预防和防止算法，都是在系统为进程分配资源时施加限制条件或进行检测，假设系统为进 程分配资源时不采取任何措施，那么应该提供死锁检测和

32、解除的手段。（1）资源分配图资源分配图是描述进程和资源申请和分配关系的一个有向图。该图由一组结点N和一组边E所构成，具 有下述形式的定义和限制：结点集N被分成两个互斥的子集，一个是进程结点子集P=Pl, P2,，Pn,另一个是资源结点子集 R=ri, 0，rm, N=PURo凡属于E中的一条边eE,都连接着P中的一个结点和R中的一个结点，e二p“门是资源请求边， 由进程指向进程门，它表示进程Pi请求一个单位的二资源。e=凸，Pi 是资源分配边，由资源口 指向进程P”它表示把一个单位的二资源分配给进程Pio通常，用圆圈代表一个进程，用方框代表一类资源。由于一种类型的资源可能有多个，我们用方框中的

33、 一个点代表一类资源中的一个资源。此时，请求边进程指向方框中的一个资源，分配边始于方框中的一个资 源。（2）死锁定理可以通过将资源分配图简化的方法来检测系统状态S是否为死锁状态，其简化方法如下： 在资源分配图中，找出一个既不阻塞又非孤立的进程结点Pi （即从进程集合中找到一个有边与它相 连，且资源申请数量小于系统中已有空闲资源数量的进程）。因进程Pi获得了它所需要的全部资源， 它能继续运行直至完成，然后释放它所占有的所有资源。这相当于消去Pi的所有请求边和分配边， 使之成为孤立结点。进程Pi释放资源后，可以唤醒因等待这些资源而阻塞的进程，从而可能使原来阻塞的进程变为非阻塞 进程。 在进行一系列

34、简化后，假设能消去图中所有的边，使所有进程都成为孤立结点，那么称该图是可简化的; 假设不能使该图完全简化，那么称该图是不可完全简化的。可以证明所有的简化顺序将得到相同的不可简化图。S为死锁状态的条件是当且仅当S状态的资源分配 图是不可完全简化的。该条件称为死锁定理。(3)死锁检测算法死锁检测算法的基本思想是：某时刻t系统中各类空闲资源向量w (t),对于系统中的一组进程 Ph P2, Pn ),找出其中的对各类资源请求数目均小于系统现在各类空闲资源数目的进程，这样的进程可以 获得所需要的全部资源并运行结束，当该进程加入到可运行结束的进程序列L中(检测开始时，L为空)。对 剩下的进程作上述考察，

35、直至再也找不到满足上述条件的进程为止。如果一组进程P1, P2,，Pn中有几 个进程不在序列L中，那么它们会发生死锁。(4)死锁的解除一旦检测出系统中出现了死锁，就应该将陷入死锁的进程从死锁状态中解脱出来，使系统恢复到正常状 态。解除死锁的常用方法有两种： 资源剥夺法。当发现死锁后，从其他进程那里剥夺做够数量的资源给死锁进程，以解除死锁状态。 撤销进程法。此方法是采用强制手段从系统中撤销一个或一局部死锁进程，并剥夺这些进程的资源 供其他死锁进程使用。最简单的撤销进程的方法是撤销全部死锁进程，是系统恢复到正常状态。但这种做法付出的代价太大。 另一方面是按照某种顺序逐个撤销死锁进程，直到有足够的资

36、源供其他为被撤销的资源使用，消除死锁状态 为止。前三章知识点考察题一、名词解释操作系统批处理系统多道程序设计分时系统实时系统并发虚拟技术系统调用微内核结 构前趋图进程进程就绪状态进程的挂起进程控制块(PCB)原语临界资源临界区 互斥(管程，条件变量)管道信箱通信方式线程用户级线程内核支持 线程作业调度作业作业步作业流作业控制块进程调度排队器分派器上下文切换机制 抢占方式 非抢占方式 中级调度 周转时间 带权周转时间 响应时间截止时间吞吐量静态优先权动态优先权时间片死锁死锁防止死锁预防平安状态 二.填空题1 .分时系统追求的目标是.2 .从静态的观点看，操作系统中的进程是由程序段、数据和三局部组

37、成.3 .批处理操作系统中，作业存在的唯一标志是.4 .操作系统中的一种同步机制，由共享资源的数据及其在该数据上的一组操作组成，该同步机制称为5 .实时系统应具有两个基本特征：及时性和.6 .两个或两个以上进程均需要访问的变量成为.7 .产生死锁的四个必要条件是、和.8 .进程获得CPU而运行是通过 得到的.9 .设系统中有N个进程，那么系统中处于等待状态的进程最多为 个.10 .如果信号量S0,那么表示有 个进程等在S信号量的等待队列上.11 . 作业调度算法有最短的作业平均周转时间.12 .在操作系统中，不可中断执行的操作称为 操作.13 .当有一个进程从运行态到等待态，那么一定有一个进程

38、.14 .引入进程的主要目的是,进程存在的惟一标志是 o15 .是指通过破坏死锁产生的必要条件来防止死锁的发生。三.判断题1 . Windows XP是一个多用户、多任务的操作系统。2 .进程从运行状态变为等待状态是由于时间片中断发生.3 .优先数是进程调度的重要依据，一旦确定不能改变4 .进程申请CPU得不到满足时，其状态变为等待态.5 .在内存为M的分时系统中，当注册的用户有N个时,每个用户拥有M/N的内存空间.6 .当一个进程从等待态变成就绪态，那么一定有一个进程从就绪态变成运行态.7 .参与死锁的所有进程都占有资源.8 .有m个进程的操作系统出现死锁时，死锁进程的个数为kkWm.9 .

39、多个进程可以对应于同一个程序，且一个进程也可能会执行多个程序。10 .在引入线程的0S中，线程是资源分配和调度的基本单位。11 .信号量的初值不能为负数。12 . 一个进程正在临界区中间执行时，不能被中断四.选择题1 .操作系统的主要功能是管理计算机系统中的()。A程序和数据B进程 C资源 D作业.操作系统的基本功能不包括( )oA、处理器管理B、存储管理 C、用户管理 D、设备管理.在单处理机系统中实现并发技术后，()。A.各进程在某一时刻并行运行，CPU与外设间并行工作B.各进程在一个时间段内并发运行，CPU与外设间串行工作C.各进程在一个时间段内并发运行，CPU与外设间并行工作D.各进程

40、在某一时刻并行运行，CPU与外设间串行工作。4 .在分时系统中，导致创立进程的典型事件是oA用户注册B用户登录 C用户记账D用户通信5 .系统调用是oA、一条机器指令B、一组键盘操作命令C、0S中可以完成特定功能的子程序D、用户子程序6、采用多道批处理系统，可能会()A.增强人机交互性B.降低了设备的利用率C.缩短了每道程序执行时间D.延长了某些程序的周转时间7 .使进程由活动就绪状态转为静止就绪状态，应利用 原语；为使进程由执行状态转变为阻塞状态，应利用 原语；为使进程由静止就绪状态变为活动就绪状态，应利用 原语。(1) create (2) suspend (3)active (4)blo

41、ck (5) wakeup.选出下面描述的是哪一类操作系统：()该操作系统具有很强的交互性，可同时供多个用户使用，但时间响应不太及时；()该类操作系统在用户提交作业后，不提供交互能力，它所追求的是计算机资源的高利用率，大吞吐 量和作业流程自动化；()该类操作系统管理的是一个由多台计算机组成的系统，系统资源归局部所有，并被局部控制，用户 知道资源存放在何处，并可以共享资源；()该类操作系统管理的是一个由多台计算机组成的系统，互相之间无主次之分，相互协调，平衡系统 的负载，且共享系统资源；程序由系统中的全部或者局部计算机协同执行。()该类操作系统的系统响应时间的重要性超过系统资源的利用率，它被广泛

42、地应用于卫星控制、导弹 发射、工业控制、飞机订票业务等领域。A.分时操作系统B.实时操作系统C.批处理操作系统D.多用户操作系统A.分时操作系统B.实时操作系统C.批处理操作系统D.单用户操作系统、A.分时操作系统B.批处理操作系统C.分布式操作系统D.网络操作系统A.分时操作系统 B.实时操作系统C分布式操作系统D.实用操作系统8 .在设计分时操作系统时，首先要考虑的是（）；在设计批处理系统时，首先要考虑的是（）；在设计实时操 作系统时，首先要考虑的是（）。A、灵活性和可适应性B、交互性和响应时间C、周转时间和系统吞吐量D、实时性和可靠性。9 .当一个进程处于（）时，就称为就绪状态。A它正等

43、着输入一批数据B它正等着协作进程的一个消息C它正等着分给它一个时间片D它正等着进入内存11多个进程同时存在于一个系统内，能在同一时间段内运行，被称为进程的（）。A.动态性 B.异步性 C.封闭性 D.并发性.如果系统中有n个进程，那么就绪队列中进程的个数最多为（）。A n+1 B n C n-l D 1. 一个进程被唤醒意味着（）。A.该进程重新占有了 CPU B.它的优先权变为最大C.其PCB移至等待队列队首D.进程变为就绪状态12 .关于线程以下的说法正确的选项是（）。A、线程是处理器的独立调度单位B、线程是资源分配的独立单位C、同一进程中多线程不能独立执行D、同一进程中每个线程有独立的主

44、存空间13 . 一种既有利于短小作业又兼顾到长作业的作业调度算法是 oA.先来先服务B.轮转C.最高响应比优先D.均衡调度16、某系统中有3个并发进程，都需要同类资源4个，试问该系统保证不会发生死锁的最少资源数是多少？A. 9 B. 10 C. 4 D. 12五.简答题1 .解释PV操作的含义及其信号量的物理意义。2 .列举操作系统的五大管理功能3、什么是多道程序设计，采用多道程序设计有什么好处？4 .列举进程调度算法.进程调度与作业调度有什么不同？5 .什么是死锁？引起死锁的原因是什么？6 .进程与线程的区别.进程与程序的区别7 .直接通信与间接通信的区别.死锁的必要条件8 .列举进程的状态

45、.分时系统与实时系统的比拟9 .简述高响应比优先调度算法。10 .处理死锁的方法有哪些？六.综合题1 .A和B两个程序，程序A顺序执行情况如下：计算20秒，使用设备10秒，计算10秒，使用设备20秒， 计算10秒；程序B顺序执行情况如下：使用设备20秒，计算20秒，使用设备10秒，计算10秒，使用设 备20秒。比拟单道和多道程序（不考虑管理开销，设备和cpu都必须互斥使用）情况下cpu和设备各自的 利用率是多少？2 .系统中有5个进程Pl, P2, P3, P4, P5如表。规定进程的优先数越小优先级越高。试描述在采用下述儿 种调度算法时，各个进程运行过程，并计算采用每种算法的进程平均周转时间

46、。假设忽略进程的调度时间。（1）先来先服务调度算法；（2）短进程优先调度算法；（3）抢占式优先级调度算法。进程到达时刻运行时间/ms优先数P1033P2265P3441P4652P58243 .假设有一个计算进程CP和一个打印进程PP,进程CP将计算结果送入由10个缓冲区组成的缓冲池，进 程PP从该缓冲区中取出数据并打印。为实现进程同步，设置信号量SC, SP,送数指针in、取数指针out。4 .试画出下面四条语句的前趋图，并用相应的PV操作实现各语句的同步关系S1: a=x+2;S2: b=y+4;S3: c=a+bS4: d=c+65.考虑某个系统在如下时刻的状态。AllocationA

47、B C DMaxA B C DAvailableA B C DP00012001215 2 0P110001750P213542356P300140656使用银行家算法回答下面的问题：（1） Need矩阵是怎样的？（2）系统是否处于平安状态?如平安，请给出一个平安序列。（3）如果从进程P1发来一个请求（042,0），这个请求能否立刻被满足?如平安，请给出一个平安序列。操作系统讲义（下）第四章存储器管理主要知识点：一、程序的装入和链接将一个用户源程序变为一个可在内存中执行的程序，通常要经过编译、链接和装入几个步骤：（1）编译。 由编译程序将用户源代码编译成假设干个目标模块。（2）链接。由链接程序将编译后形成的目标模块以及它们 所需要的库函数，链接在一起，形成一个装入模块。（3）装入。由装入程序将装入模块装入主存的过程。如内存内存编译程序产 生的F1标榜 块第一步第二步第三步图4.1源程序执行过程（2）单道批处理系统：系统对作业的处理都是成批