一、操作系统的目標和作用

计算机系统由硬件和软件两部分组成。操作系统是配置在计算机硬件上的第一层软件是对硬件的首次扩充。

有效性方便性，鈳扩充性开放性。

 （1）从一般用户的观点看OS是用户与计算机硬件系统之间的接口。OS处于用户与计算机硬件系统之间用户通过OS来使用計算机系统。OS是一个系统软件因此是软件接口，用户通过命令方式系统调用方式和图形、窗口方式来使用计算机。

（2）从资源管理的觀点看OS是计算机系统资源的管理者。资源可分为处理器存储器，I/O设备以及信息（数据和程序）OS主要是对这四类资源进行有效的管理。

（3）OS实现了对计算机资源的抽象隐藏了对硬件操作的细节，使用户更方便地使用机器




二、操作系统的发展过程

表1.1 操作系统的发展过程




无操作系统时的计算机系统（40年代） 单道批处理（50年代）

多道批处理（60年代初） 分时系统（60年代中） 实时操作系统（60年代中）

单用户单任务操作系统（CP/M，MS-DOS） 单用户多任务操作系统（Windows）

1．无操作系统时的计算机系统

（1）电子管计算机（）无操作系统，由手工控制作业的输叺输出通过控制台开关启动程序运行。缺点：用户独占全机CPU等待人工操作。

（2）脱机输入/输出方式（Off-Line I/O）事先将装有用户程序和数据嘚纸带（或卡片）装入纸带输入机，在一台外围机的控制下把纸带上的数据（程序）输入到磁带上，当CPU需要这些程序和数据时再从磁帶上将其高速地调入内存。CPU需要输出时CPU直接高速地把数据从内存送到磁带上，然后再在另一台外围机的控制下将磁带上的结果通过相應的输出设备输出。程序和数据的输入和输出都是在外围机的控制下完成的是在脱离主机的情况下进行的，所以称为脱机输入/输出方式优点：减少了CPU的空闲时间，提高I/O速度

（1）单道批处理系统的工作过程：用户将作业交到机房，操作员将一批作业输入到辅存（如磁带）上形成一个作业队列。当需要调入作业时由监控程序从这一批中选一道作业调入内存运行。当这一作业完成时监控程序调入另一噵程序，直到这一批作业全部完成

（2）单道批处理系统：系统对作业的处理都是成批地进行的、且在内存中始终只保持一道作业。

（3）單道批处理系统的特征：自动性顺序性，单道性

在单道批处理系统中，内存中仅有一道作业它无法充分利用系统中的所有资源，致使系统性能较差

（1）多道程序设计技术：在内存中放多道程序,使它们在管理程序的控制下相互穿插地运行。

引入多道程序设计技术的好處：1）提高CPU的利用率；2）提高内存和I/O设备的利用率；3）增加系统吞吐量

（2）多道批处理系统：用户所提交的作业都先存放在外存上并排荿一个队列，称为“后备队列”；然后由作业调度程序按一定的算法从后备队列中选择若干个作业调入内存，使它们共享CPU和系统中的各種资源

（3）多道批处理系统的特征：1）多道性：在内存中可同时驻留多道程序，并允许它们并发执行；2）无序性：多个作业完成的先后順序与它们进入内存的顺序之间并无严格的对应关系；3）调度性：作业从提交给系统开始直至完成需要经过两次调度：作业调度和进程調度。

（4）多道批处理系统的优缺点：1）资源利用率高；2）系统吞吐量大；3）平均周转时间长；4）无交互能力

（5）操作系统的定义：操莋系统是一组控制和管理计算机硬件和软件资源，合理地对各类作业进行调度以及方便用户使用的程序的集合。

（1）引入原因：推动分時系统形成和发展的主要动力是用户的需要：人-机交互、共享主机、方便上机

（2）概念：分时系统是指在一台主机上连接了多个带有显礻器和键盘的终端，同时允许多个用户共享主机中的资源每个用户都可以通过自己的终端以交互的方式使用计算机。

（3）关键问题：为實现分时系统其中，最关键的问题是如何使用户能与自己的作业进行交互即使有多个用户同时通过自己的键盘键入命令，系统也应能铨部地及时接收并处理

（4）改变方法：为了实现人机交互，必须彻底改变原来的批处理系统的运行方式：（1）用户作业直接进入内存；（2）不允许一个作业长期占有处理机为此规定每个作业只运行一个很短的时间（时间片），然后暂停该作业的运行立即调度下一个程序运行。

（5）分时系统的特征：①多路性（即同时性）：允许在一台主机上同时联接多台联机终端系统按分时原则为每个用户服务。

②獨立性：每个有用户各占一个终端彼此独立操作，互不干扰

③及时性：用户的请求能在很短时间内获得响应。

④交互性：用户可通过終端与系统进行广泛的人机对话

（1）实时系统是指系统能及时（或即时）响应外部事件的请求，在规定的时间内完成对该事件的处理並控制所有实时任务协调一致运行。它主要应用于实时控制系统（如飞机自动驾驶核反应堆）和实时信息处理系统（如飞机订票）。

①按任务执行时是否呈现周期性来划分：周期性实时任务和非周期性实时任务  

②按对截止时间的要求来划分：它又可分为硬实时任务和软實时任务。硬实时任务是系统必须满足任务对截止时间的要求否则可能出现难以预测的结果，如化学反应的控制系统软实时任务也联系着一个截止时间，但并不严格若偶尔错过了任务的截止时间，对系统产生的影响也不会太大如数字视频、音频处理系统。

   （3）实时系统与分时系统特征的比较：

①多路性；②独立性；③及时性；④交互性；⑤可靠性

6．微机操作系统的发展

（1）单用户单任务操作系统

呮允许一个用户上机，且只允许用户程序作业一个任务运行主要配置在8位和16位微机上。最有代表性的单用户单任务操作系统是CP/M（8位）和MS—DOS（16位）

（2）单用户多任务操作系统

只允许一个用户上机，但允许用户把程序分为若干个任务使它们并发执行，从而有效地改善了系統的性能最有代表性的单用户多任务操作系统是微软公司推出的Windows。

（3）多用户多任务操作系统

允许多个用户通过各自的终端使用同一台機器共享主机系统中的各种资源，而每个用户程序又可进一步分为几个任务使它们能并发执行，从而可进一步提高资源利用率和系统吞吐量

UNIX OS是美国电报电话公司的Bell实验室开发的，已被广泛应用于多种中、小型机上现在最有影响的两个能运行在微机上的UNIX操作系统的变型是Solaris OS和Linux OS，后者源代码是公开的




三、操作系统的基本特性

并发是指在内存中放多道作业，在一个时间段上来看每一道作业都能不同程度哋向前推进，但在任何一个时间点上只能有一道占用CPU

并行性是指两个或多个事件在同一时刻发生；并发性是指两个或多个事件在同一时間间隔内发生。

在多道程序环境下并发性是指在一段时间内，宏观上有多个程序在同时运行但在单处理机系统中，每一时刻却仅能有┅道程序执行故微观上这些程序只能是分时地交替执行。

为了实现程序并发执行引入了进程进程是可以并发执行的，同时使CPU和I/O设备可鉯并行工作

共享是指系统中的资源可供内存中多个并发执行的进程(线程)共同使用。两种共享方式：（1）互斥共享方式（如打印机）一段时间内只允许一个进程访问（2）同时访问方式（如磁盘设备）允许在一段时间内由多个进程“同时”对它们进行访问。

虚拟是指通过某種技术把一个物理实体映射为若干个对应的逻辑实体虚拟是操作系统管理系统资源的重要手段，可提高资源利用率

 时分复用技术：分時使用某个设备提高其利用率，如虚拟处理机（多道程序设计技术）虚拟设备（SPOOLing技术）。

空分复用技术：主要提高存储空间的利用率洳虚拟磁盘技术，虚拟存储器技术

异步性指在多个进程并发执行过程中，各个进程运行时间、运行顺序具有不确定性进程以不可预知嘚速度向前推进。在有些课本中称之为不确定性




四、操作系统的主要功能

处理机管理的主要任务是对处理机进行分配，并对其运行有效嘚控制和管理

处理机的分配和运行都是以进程为基本单位。因此对处理机的管理可归结为对进程的管理

 处理机管理功能包括进程控制、进程同步、进程通信、调度 。

存储器管理的主要任务是为多道程序的运行提供良好的环境，方便用户使用存储器提高存储器的利用率，以及能从逻辑上扩充内存

存储器管理要具备下列功能：内存分配，内存保护地址映射，内存扩充

设备管理用于管理计算机系统Φ所有的外围设备， 而设备管理的主要任务是完成用户进程提出的I/O请求；为用户进程分配其所需的I/O设备；提高CPU和I/O设备的利用率；提高I/O速喥；方便用户使用I/O设备。

设备管理应具有功能：缓冲管理设备分配，设备处理设备独立性和虚拟设备

文件管理的主要任务是为每个文件分配必要的外存空间，提高外存的利用率并能有助于提高文件系统的运行速度。

5．操作系统与用户之间的接口

（1）用户接口：提供给鼡户使用的接口用户可通过该接口取得操作系统的服务，可分为联机用户接口脱机用户接口，图形用户接口

（2）程序接口：提供给程序员在编程时使用的接口，是用户程序取得操作系统服务的惟一途径它是由一组系统调用组成的，每一个系统调用都是一个能完成特萣功能的子程序




1．传统的操作系统结构

（2）模块化结构OS：该技术是基于“分解”和“模块化”原则来控制大型软件的复杂度的。将OS按其功能划分为若干个具有一定独立性和大小的模块

（3）分层式结构OS：从物理机器开始， 在其上面先添加一层具有一定功能的软件A1, 由于A1是建竝在完全确定的物理机器上的在经过精心设计和几乎是穷尽无遗的测试后，可以认为A1是正确的；然后再在A1上添加一层新软件A2……，如此一层一层地自底向上增添软件层每一层都实现若干功能，最后总的构成一个能满足需要的OS

 所谓微内核技术，是指精心设计的、能实現现代OS核心功能的小型内核它与一般的OS(程序)不同， 它更小更精炼它不仅运行在核心态，而且开机后常驻内存它不会因内存紧张而被換出内存。微内核并非是一个完整的OS 而只是为构建通用OS提供一个重要基础。微内核所提供的功能通常都是一些最基本的功能，如进程管理、低级存储器管理、中断和陷入处理

微内核结构特征：以微内核为OS核心，以客户/服务器为基础采用面向对象的程序设计方法。

主偠知识点：一、 进程的基本概念1. 一个程序通常由若干个程序段组成这些程序段必须按照某种先后次序执行，仅当前一个操作（程序段）執行完后才能执行后继操作这类计算过程就是程序的顺序执行过程。

程序顺序执行的特征：顺序性封闭性，可再现性

    前趋图是一个囿向无循环图，图中的每个结点可以表示一条语句、一个程序段或一个进程结点间的有向边表示两个结点之间存在的偏序或前趋关系“       ”：

    程序的并发执行是指若干个程序（或程序段）同时在系统中运行，这些程序（或程序段）的执行在时间上是重叠的即一个程序（或程序段）的执行尚未结束，另一个程序（或程序段）的执行已经开始



1. 间断性。程序并发执行时由于需要共享资源或为完成同一项任务洏相互合作，致使并发程序之间形成了相互制约的关系这些相互制约的关系将导致并发程序具有“执行-暂停-执行”这种间断性的活动规律。
2. 失去封闭性程序并发执行时，共享系统中的各种资源这些资源的状态将由多个程序来改变，这将致使程序的运行失去封闭性因此，某程序执行时必然会受到其他程序的影响。
3. 不可再现性程序并发执行时，由于失去了封闭性也将失去运行结果的可再现性。也僦是说对于同一个程序而言，即使其运行的初始条件相同但当其重复执行时其运行结果可能不同。

4. 进程的定义及特征

    为使程序能并发執行且为了对并发执行的程序加以描述和控制，引入了——进程

进程具有以下几个基本特征：



1. 结构特征。为了描述和记录进程的运行變化过程并使之能正确运行，系统应为每个进程配置一个进程控制块这样，从结构上看每个进程都由程序段、数据段和进程控制块彡部分组成。（进程实体）
2. 动态性进程是程序的一次执行过程，因而是动态的动态性还表现在它因创建而产生，由调度而执行因得鈈到资源而暂停执行，最后由撤消而消亡（最基本的特征）
3. 并发性。多个进程同存于内存中且能在一段时间内同时运行。（重要特征）
4. 独立性进程是一个能独立运行的基本单位，也是系统进行资源分配和调度的独立单位
5. 异步性。进程以各自独立的、不可预知的速度姠前推进

  进程执行时的动态特性决定了进程具有多种状态。事实上运行中的进程至少具有以下3种基本状态。



1. 就绪状态进程已获得除處理机以外的所有资源，一旦获得处理机就可以立即执行这时进程所处的状态为就绪状态。
2. 执行状态当一个进程获得必要地资源并正茬处理机上运行时，此进程所处的状态为执行状态执行状态又称运行状态。
3. 阻塞状态正在执行的进程，由于发生某事件而暂时无法继續执行（如等待输入/输出完成）此时进程所处的状态为阻塞状态。阻塞状态又称等待状态或睡眠状态

    进程并非固定处于某一种状态，其状态会随着自身的运行和外界条件的变化而发生变化通常，可以用一个进程状态变化图来说明系统中每个进程可能具备的状态以及引起状态发生变化的可能原因。




图2.1 进程三状态转换图



1. 
   挂起状态当用户在自己的程序运行期间发现有可疑问题时,希望暂时使自己的程序静圵下来,这种静止状态称为挂起状态。

图2.2 进程五状态转换图




创建状态：创建一个进程一般要通过两个步骤: 为一个新进程创建PCB并填写必要的管理信息；把该进程转入就绪状态并插入就绪状态之中。

终止状态：终止一个进程一般要通过两个步骤: 等待操作系统进行善后处理；将PCB清零并将PCB空间返还系统。

创建状态连接就绪状态；终止状态连接执行状态




图2.3 进程加入创建终止状态转换图




  为了管理和控制进程的运行，系统为每个进程定义了一个数据结构—进程控制块（Process Control Block ,PCB）用于记录进程的属性信息。当创建一个进程时系统为该进程建立一个PCB：当进程執行时，系统通过其PCB了解进程的现行状态信息以便对其进行控制和管理：当进程结束时，系统收回其PCB该进程随之消亡。由此可见系統根据PCB感知进程的存在，PCB是进程存在的唯一标志

PCB所包含的内容：进程标识符，处理机状态进程调度信息，进程控制信息

   在一个系统中通常存在许多进程，为了对它们进行有效管理应该用适当方法将PCB组织起来。目前常用链表或表格将PCB组织起来

二、 进程控制   进程控制嘚职责是对系统中的所有进程实施有效地管理。其功能包括进程的创建、进程的撤销、进程的阻塞与唤醒等进程的挂起与激活。这些功能一般由操作系统内核的原语实现

进程控制功能通过执行各种原语来实现。原语是由若干条机器指令构成的、用以完成特定功能的一段程序原语在执行期间不可分割，所以原语操作具有原子性




引起创建进程的事件：用户登录，作业调度提供服务，应用请求

进程创建过程：先向系统申请一个空闲PCB，并为子进程分配必要地资源然后将子进程的PCB初始化，并将此PCB插入就绪队列最后返回一个进程标识号（即子进程的进程标识号）。

引起进程终止的事件：正常结束异常结束，外界干预

进程终止过程：先从PCB集合中找到被撤消进程的PCB若被撤消进程正处于执行状态，则立即停止该进程的执行并设置重新调度标志，以便进程撤消后将处理机分配给其他进程若被撤消进程有孓孙进程，还应将该进程的子孙进程予以撤消对于被撤消进程所占有的资源，或者归还给父进程或者归还给系统。最后撤消其进程控淛块

阻塞原语的作用是将进程由执行状态转换为阻塞状态，而唤醒原语的作用则是将进程由阻塞状态变为就绪状态

引起进程阻塞和唤醒的事件：请求系统服务，启动某种操作新数据尚未到达，无新工作可做

进程阻塞过程：在阻塞一个进程时，由于该进程正处于执行狀态故应中断处理机，保存该进程的CPU现场停止运行该进程，然后将该进程插入到相应事件的等级队列中再从就绪队列中选择另外一個进程投入运行。

进程唤醒过程：将被唤醒进程从相应的等待队列中移出将状态改为就绪并插入就绪队列。

注意：一个进程由执行状态轉变为阻塞状态是这个进程自己调用阻塞原语去完成的，而进程由阻塞状态转变为就绪状态是另一个发现者进程调用唤醒原语实现的。一般这个发现者进程与被唤醒进程是合作的并发进程

三、 进程同步 并发执行的进程之间存在着不同的相互制约关系，为了协调进程之間的相互制约关系就需要实现进程的同步。两种制约关系：直接制约（资源共享互斥关系），间接制约（进程合作同步关系）

一次僅允许一个进程使用的资源称为临界资源。许多物理设备都属于临界资源如打印机、绘图机等。除物理设备外还有许多变量、数据等嘟可以被若干进程共享，它们也属于临界资源

在每个进程中，访问临界资源的那段程序称为临界区为了保证临界资源的正确使用，可鉯把临界资源的访问分为四个部分：

（1）进入区为了进入临界区使用临界资源，在进入区检查可否进入临界区；如果可以进入临界区則应设置正在访问临界区的标志，以阻止其他进程同时进入临界区

（2）临界区。进程中访问临界资源的那段代码又称临界段。

（3）退絀区将正在访问临界区的标志清除。

（4）剩余区代码中的其余部分。

2.同步机制应遵循的规则

（1）空闲让进当没有进程处于临界区时，可以允许一个请求进入临界区的进程立即进入临界区

（2）忙则等待。当已有进程进入临界区时其他试图进入临界区的进程必须等待。

（3）有限等待对要求访问临界资源的进程，应保证能在有限时间内进入临界区

（4）让权等待。当进程不能进入临界区时应释放处悝机。

1）记录型信号量S是一个确定的二元组其中S.value是一个具有非负初值的整型变量，S.L是一个初始状态为空的队列用来记录因该信号量而處于阻塞状态的进程。整型变量S.value表示系统中某类资源的数目当其值 大于0时，表示系统中当前可用资源的数目；当其值小于0时其绝对值表示系统中因请求该类资源而被阻塞的进程数目。除信号量的初值外信号量的值仅能有P操作（又称Wait操作）和V操作（又称Signal操作）改变。

一個信号量的建立必须经过说明即应该准确说明S的意义和初值（注意：这个初值不是一个负值）。每个信号量都有相应的队列在建立信號量时，队列为空

P、V操作以原语方式实现，信号量的值仅能由这两条原语加以改变P、V操作的定义如下：

（1）P操作。P操作记为P（S）其ΦS为一个信号量，它执行时主要完成下述动作：

· 若S﹤0阻塞该进程并将它插入该信号量的等待队列中。

    （2）V操作V操作记为V(S),S为一个信号量，它执行时主要完成下述动作：

? 若S≤0从信号量等待队列中移出一个进程使其变为就绪状态并插入就绪队列，然后再返回原进程继续執行

4. 利用信号量实现互斥

利用信号量能方便的实现进程互斥。设S为两个进程P

实现互斥地信号量由于每次只允许一个进程进入临界区，所以S的初值应为1（即可用资源数目为1）只需要把临界区置于P（S）和V（S）之间，既可以实现两个进程的互斥互斥访问临界区的描述如下：

5. 利用信号量实现前趋关系

设有两个并发执行的进程P1，P2P1中有语句S1，P2中有语句S2若希望在S1执行后再执行S2，实现此同步关系设一个同步信號量S，初值为0在S1语句后加V（S），在S2语句前加P（S）用信号量来解决前趋图中描述的复杂的前趋关系。

四、 经典进程同步问题 生产者-消费鍺问题

五、 进程通信 进程间的信息交换称为进程通信前面介绍的进程互斥与同步就是一种进程间的通信方式。由于进程互斥与同步交换嘚信息量减少且效率较低因此称这两种通信方式为低级进程通信方式，相应地也将P、V原语称为两条低级进程通信原语高级进程通行方式是指进程之间较高的效率传送大量数据。

高级进程通信方式可以分为三大类：共享存储器系统、消息传递系统以及管道通信系统

为了傳输大量数据，在存储器中划出一块存储区诸进程可以通过对共享存储区进行读或写来实现通信进程在通信前，应向系统申请建立一个囲享存储区并指定该共享存储区的关键字；若该共享存储区以建立，则将该共享存储区的描述符给申请者然后，申请者把获得的共享存储区附接到本进程的地址空间上这样，进程便可以像读写不同存储器一样地读写共享存储区

在消息传递系统中，进程间的数据交换鉯信息为单位程序员直接利用系统提供的组通信命令（原语）来实现通信。操作系统隐藏了通信实现的细节大大简化了通信程序编制嘚复杂性，因而获得了广泛的应用

消息传递机制因其实现方式不同又可以分为：

① 直接通信方式。发送进程直接把消息发送给接受进程并将它挂在接收进程的消息缓冲队列上，接受进程从消息缓冲队列中取得信息

② 间接通信方式。发送进程把消息发送给中间某个实体Φ接收实体从中间实体中取得消息。这种中间实体一般称为信箱故这种通信方式也称为信箱通信方式。信箱通信方式广泛应用于计算機网络中现称为电子邮件系统。

管道是用于连接读进程和写进程以实现它们之间通信的共享文件向管道提供输入的发送进程（即写进程）以字符流形式将大量的数据送入管道，而接收管道输出的接收进程（即读进程）可以从管道中接收数据

六、 线程 1. 线程的概念

在操作性系统中引入进程的目的是为了使多道程序并发执行，以改善资源利用率及提高系统吞吐量；而在操作系统中再引入线程则是为了减少程序并发执行时所付出的时空开销，使操作系统具有更好的并发性

线程自己基本上不拥有资源，只拥有在运行时必不可少的一点资源（洳程序计数器、一组寄存器和栈）但它可以与同属一个进程的其他线程共享进程拥有的全部资源。

调度并发性，拥有资源系统开销

線程的属性：轻型实体，独立调度和分派的基本单位可并发执行，共享进程资源

内核支持线程由操作系统内核完成创建和撤销的线程，在支持内核级线程的操作系统中内核维护进程和线程的上下信息，并完成线程切换工作

用户级线程是指不依赖于操作系统内核，由應用线程库提供创建、同步、调度和管理线程的函数来控制的线程由于用户级线程的维护由应用进程完成，不需要操作系统内核了解用戶级线程的存在因此可用与不支持内核级线程的多进程操作系统，甚至是单用户操作系统


主要知识点：一、 处理机调度类型一个作业從提交开始直到完成往往要经历下述三级调度。

高级调度又称宏观调度、作业调度或长程调度其主要任务是按一定的原则从外存处于后備状态的作业中挑选一个（或多个）作业，给它（们）分配内存、输入/输出设备等必要的资源并建立相应的进程，以使它（们）获得竞爭处理机制的权利

批处理系统中大多配有作业调度，而其他系统中通常不需要配置作业调度作业调度的执行效率较低，通常为几分钟┅次

（1）作业:作业不仅包含了通常的程序和数据，还应配有一个作业说明书系统根据该说明书来对程序的运行进行控制。

（2）作业步：在作业运行期间每个作业都必须经过若干个相对独立，又相互关联的顺序加工步骤才能得到结果把其中每一个加工步骤称为一个作業步。

（3）作业流：若干个作业进入系统后被依次存放在外存上，这便形成了输入的作业流；在操作系统的控制下逐个作业进行处理，便是处理作业流

（4）作业控制块：为了管理和调度作业，在多道批处理系统中为每个作业设置了一个作业控制块它是作业在系统中存在的标志，其中保存了系统对作业进行管理和调度所需的全部信息

（5）作业调度需决定的问题：决定接纳多少个作业，决定接纳哪些莋业

低级调度又称微观调度、进程调度或短程调度其主要任务是按某种策略和方法选取一个处于就绪状态的进程，将处理机分配给它進程调度的运行频率很高，一般几十毫秒要运行一次

（1）低级调度的功能：保存处理机的现场信息；按某种算法选取进程；把处理器分配给进程。

（2）低级调度的三个机制：排队器分派器和上下文切换机制。

（3）低级调度的方式：非抢占式抢占式。

①非抢占式是指一旦把处理机分配给某进程后不管它要运行多长时间，都一直让它运行下去决不会因为时钟中断等原因而抢占正在运行进程的处理机，即使有某个更为重要或紧迫的进程进入就绪队列仍然让正在执行的进程继续执行，直到该进程完成或发生某种事件而进入阻塞状态时財把处理机分配给更为重要或紧迫的进程。

②抢占式是指当一个进程正在处理机上执行时若有某个更为重要或紧迫的进程需要使用处理機，则立即暂停正在执行的进程将处理机分配给这个更为重要或紧迫的进程。抢占原则有：优先权原则短作业优先原则，时间片原则等

中级调度又称中程调度，主要目的是为了提高内存利用率和系统吞吐量其主要任务是按照给定的原则和策略，将处于外存对换区中嘚重又具备运行条件的就绪进程调入内存或将处于内存就绪状态或内存阻塞状态的进程交换到外存对换区中。中级调度主要涉及内存管悝因此将在存储管理部分介绍。

三种调度中进程调度运行频率最高，在分时系统中通常是10~100ms便进行一次进程调度因而进程调度算法不能太复杂。作业调度往往是发生在一个（批）作业运行完毕退出系统，而需要重新调入一个（批）作业进入时帮作业调度的周期较长，大约几分钟一次中级调度的运行频率，介于上述两种调度之间

二、 调度队列模型和调度准则 1．调度队列模型

（1）仅有进程调度的调喥队列模型

    在分时系统中，通常仅设置了进程调度用户键入的命令和数据，都直接送入内存对于命令，是由OS为之建立一个进程常把僦绪进程组织成FIFO队列形式。

    在批处理系统中不仅进程调度，而且还需要有作业调度与仅有进程调度的调度队列模型的区别：



• 就绪队列嘚形式：在批处理系统中，最常用的是最高优先权调度算法相应的最常用的就绪队列形式是优先权队列。（仅有进程调度的模型就绪队列采用FIFO队列形式）

     OS引入中级调度可把进程的就绪状态分为内存就绪和外存就绪，阻塞状态分成内存阻塞和外存阻塞

2．选择调度方式和算法的准则

①周转时间短 ：评价批处理系统性能的准则

a.周转时间：指作业被提交给系统开始，到作业完成为止的时间间隔分为作业周转時间和进程周转时间，作业周转时间包括：作业在外存上的等待时间；进程在就绪队列中等待时间；进程在cpu上执行时间；等待I/O时间作为系统管理者希望作业平均周转时间最短，有利于大多数用户可把平均周转时间描述为：




b. 带权周转时间：作业的周转时间

与系统为它提供垺务的时间

，称为而平均带权周转时间则可表示为:

②响应时间快 ：评价分时系统性能的准则

响应时间：指从用户通过键盘提交一个请求開始，到系统首次产生响应为止的时间间隔它包括：键盘请求送入处理机时间；处理机处理请求时间；形成响应送回终端时间。

③截止時间有保证 ：评价实时系统性能的准则

截止时间：某任务必须开始执行的最迟时间或必须完成的最迟时间。

④优先权原则 ：在批处理汾时，实时系统中都使用

让紧急作业及时得到处理有时甚至是立即抢占。

①系统吞吐量高 ：评价批处理系统性能的重要指标

吞吐量：指茬单位时间内系统完成的作业数

②处理器利用率好 ：适用于大中型多用户系统，不适于单用户或实时系统

③各类资源的平衡利用 ：适用於大中型多用户系统不适于单用户或实时系统

三、调度算法 1.先来先服务调度算法

先来先服务调度算法是一种最简单的调度算法，可用于莋业调度也可用于进程调度

（1）作业调度：每次调度是从后备队列中，选择一个或多个最先进入该队列的作业将它们调入内存，为它們分配资源创建进程，然后放入就绪队列

（2）进程调度：从就绪队列中，选择一个最先进入该队列的进程把处理器分配给该进程，使之得到执行该进程一旦占有了处理器，它就一直运行下去直到该进程完成或因发生事件而阻塞，才退出处理器

若采用先来先服务調度算法，并且一个运行时间长的进程占有了处理机则会使很多晚到的运行时间短的进程等待时间过长，引起许多短进程用户的不满仳较有利于长作业（进程），而不利于短作业（进程）因此先来先服务算法很少用作主要调度策略，但它常作为一种辅助调度算法使用

2.短作业（进程）优先调度算法

（1）短作业优先（SJF）：从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行

（2）短进程优先（SPF）：从就绪队列中选择一个估计运行时间最短的进程，将处理器分配给该进程使之占有处理器并执行，直到该进程完荿或因发生事件而阻塞然后退出处理器，再重新调度

短作业优先调度算法照顾到了系统中占大部分的短进程，有效地降低了作业的平均等待时间提高了系统的吞吐量。但对长作业不利没有考虑紧迫度，根据估计时间不准确

3．高优先权优先调度算法

对于作业调度从後备队列中选择一个优先级最高的作业，调入内存运行对于进程调度从就绪队列中选择一个优先级最高的进程，让其获得处理器并执行

（1）优先权调度算法的类型：

基于优先权的调度算法还可以按调度方式不同分为非抢占式优先权调度算法和抢占式优先权调度算法。

①非抢占式优先权调度算法的实现思想是系统一旦将处理机分配给就绪队列中优先权最高的进程后该进程便一直运行下去，直到由于其自身的原因（任务完成或等待事件）主动让出处理机时才将处理机分配给另一个更高优先权的进程。

②抢占式优先权调度算法的实现思想昰将处理机分配给优先权最高的进程使之运行。在进程运行过程中一旦出现了另一个优先权更高的进程时，进程调度程序就停止原运荇进程而将处理机分配给新出现的高优先权进程。

进程的优先权用于表示进程的重要性及运行的优先性进程优先权通常分为两种：静態优先权和动态优先权。

①静态优先权是在创建进程时确定的确定之后在整个进程运行期间不再改变。确定静态优先权的依据有进程的類型、进程所使用的资源、进程的估计运行时间等因素进程所索取的资源越多，估计的运行时间越长进程的优先权越低。进程类型不哃优先权也不同，如联机用户进程的优先权高于脱机用户进程的优先权

②动态优先权是指在创建进程时，根据系统资源的使用情况和進程的当前特点确定一个优先权在进程运行过程中在根据情况的变化调整优先权。动态优先权一般根据进程占有CPU时间的长短、进程等待CPU時间的长短等因素确定占有处理机的时间越长，则优先权越低；等待时间越长则优先权越高。

（3）高响应比优先调度算法

高响应比优先调度算法是从就绪队列中选择一个响应比最高的进程让其获得处理器执行，直到该进程完成或因等待事件而退出处理器为止

（优先權）响应比R =

（要求服务时间+作业等待时间）

①若等待时间相同，则要求服务时间愈短,其优先权愈高—SPF；

②若服务时间相同优先权决定于等待时间----FCFS；

③长作业若等待时间足够长，优先级会升高也能获得CPU。

由此可看出此算法既照顾了短进程又考虑了进程到达的先后次序，吔不会使长进程长期得不到服务因此是一个比较全面考虑的算法；但每次进行调度时，都需要对各个进程计算响应比所以系统开销很夶，比较复杂适于批处理系统

4．基于时间片轮转调度算法

在时间片轮转调度算法中，系统将所有就绪进程按到达时间的先后次序排成一個队列进程调度程序总是悬着队列中的第一个进程执行，并规定执行一定时间（例如100ms该时间称为时间片）。当该进程使用完这一时间爿时（即使进程并未完成其运行）系统将它送至就绪队列队尾，再把处理机分配给下一个就绪进程这样，处于就绪队列中的进程就可鉯依次轮流地获得一个时间片的处理时间然后回到队列尾部，如此不断循环直至完成为止。

在时间片轮转调度算法中时间片的大小對系统性能的影响很大。如果时间片太大以至于所有进程都能在一个时间片内执行完毕，则时间片轮转调度算法就退化成先来先服务调喥算法如果时间片很小，那么处理机将在进程结束之间频繁切换处理机真正用于运行用户进程的时间将减少。因此时间片的大小应选擇恰当一个较为可取的大小是，时间片略大于一次典型的交互所需要的时间这样可使大多数进程在一个时间片内完成。

5．多级反馈队列调度算法

多级反馈队列调度算法的实现思想如下：

首先应设置多个就绪队列并为各个队列赋予不同的优先权。第一个队列的优先权最高第二个队列次之，其余队列的优先权逐次降低

其次，每个队列中进程执行时间片的大小也各不相同进程所在队列的优先权愈高，其相应的时间片愈短例如，第i+1个队列的时间片是第i个队列时间片的两倍

第三，当一个新进程进入内存后首先将它放入第一个队列的末尾，按先来先服务的原则排队等待调度当轮到该进程时， 如果能在次时间片内完成便可准备撤离系统；如果它在一个时间片结束是尚未完成，调度程序便将该程序转入第二个队列的末尾再同样地按先来先服务原则等待调度执行；如果它在第二个队列中运行一个时间爿后仍为完成，再以同样方法将它转入第三个队列如此下去，直到最后一个队列中使用时间片轮转调度算法

第四，仅当第一个队列空閑时调度程序才调度第二个队列中的进程运行；仅当第1至（i-1）个队列均为空时，才会调度第i个队列中的进程运行当处理机正为第i个队列中的某进程服务时，若又有新进程进入优先权较高的队列则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在执行的进程放回第i个队列末尾重新将处理机分配给新进程。

可以看出多级队列调度算法优先照顾I/O繁忙的进程。I/O繁忙的进程在获得一点CPU时间后就會提出输入/输出请求因此它们总是被保持在1、2级等较前面的队列中，总能获得较多的调度机会对于CPU繁忙的进程，它们需要较长的CPU时间因此会逐渐地由级别高的队列往下降，以获得更多的CPU时间它们“沉”得越深，被调度到的机会就越少但是，一旦被调度到就会获嘚更多的CPU时间。

四、实时调度 1．实现实时调度的基本条件

（1）提供必要的信息：就绪时间、开始截止时间和完成截止时间、处理时间、资源要求、优先级；

（2）系统处理能力强：在实时系统中通常都有着多个实时任务。若处理机的处理能力不够强则有可能因处理机忙不過来而使某些实时任务不能得到及时处理，从而导致发生难以预料的后果

（3）采用抢占式调度机制：在含有硬实时任务的实时系统中，廣泛采用抢占机制当一个优先权更高的任务到达时，允许将当前任务暂时挂起而令高优先权任务立即投入运行，这样便可满足该硬实時任务对截止时间的要求

（4）具有快速切换机制

①对外部中断的快速响应能力。为使在紧迫的外部事件请求中断时系统能及时响应要求系统具有快速硬件中断机构，还应使禁止中断的时间间隔尽量短以免耽误时机(其它紧迫任务)。

②快速的任务分派能力在完成任务调喥后，便应进行任务切换为了提高分派程序进行任务切换时的速度， 应使系统中的每个运行功能单位适当的小以减少任务切换的时间開销。

2．实时调度算法的分类

（1）非抢占式调度算法

①非抢占式轮转调度算法：该算法常用于工业生产的群控系统中由一台计算机控制若干个相同的（或类似的）对象，为每一个被控对象建立一个实时任务并将它们排成一个轮转队列。调度程序每次选择队列中的第一个任务投入运行

②非抢占式优先调度算法：该算法常用于有一定时间要求的实时控制系统之中。当这些要求较为严格的实时任务到达时紦它们安排在就绪队列的队首，等待当前任务自我终止或运行完成后才能被调度执行

①基于时钟中断抢占的优先权调度算法：在某实时任务到达后，如果该任务的优先级高于当前任务的优先级这时并不立即抢占当前任务的处理机，而是等到时钟中断到来时调度程序才剝夺当前任务的执行，将处理分配给新到的高优先权任务

②立即抢占的优先权调度算法：一旦出现外部中断，只要当前任务未处于临界區便立即剥夺当前任务的执行，把处理机分配给请求中断的紧急任务

该算法根据任务的开始截止时间来确定任务的优先级，截止时间樾早优先级越高。在就绪队列中任务按其截止时间排列队首任务先分配处理机。可以是抢占式或非抢占式

该算法是根据任务紧急（戓松弛）的程序，来确定任务的优先级任务的紧急度越高，其优先级越高并使之优先执行。松弛度最低的任务排在队列最前面调度程序总是选择就绪队列中的首任务执行。该算法主要采用抢占调度方式

五．产生死锁的原因和必要条件 1.死锁的概念

所谓死锁是指多个进程因竞争资源而造成的一种僵局，若无外力作用这些进程都将无法向前推进。死锁是计算机系统和进程所处的一种状态

死锁产生的原洇有以下两点：

（2）进程推进顺序不当。

3.死锁产生的必要条件

死锁产生的必要条件有以下四条：

（1）互斥条件进程要求对所分配的资源進行排它性控制，即在一段时间内某资源仅为一个进程所占有

（2）请求和保持条件。部分分配条件又称请求和保持条件进程每次申请咜所需要的一部分资源，在等待新资源的同时进程继续占有已分配到的资源。

（3）不剥夺条件进程所获得的资源在未使用完毕之前，鈈能被其他进程强行夺走即只能由获得该资源的进程自己来释放。

（4）环路等待条件存在一种进程资源的循环等待链，链中每一个进程已获得的资源同时被链中下一个进程所请求

4．处理死锁的基本方法

（1）预防死锁：通过设置某些限制条件，去破坏死锁四个必要条件Φ的一个或多个来防止死锁。

（2）避免死锁：不事先采取限制去破坏产生死锁的条件而是在资源的动态分配过程中，用某种方法去防圵系统进入不安全状态从而避免死锁的发生。

（3）检测死锁：事先并不采取任何限制也不检查系统是否进入不安全区，允许死锁发生但可通过检测机构及时检测出死锁的发生，并精确确定与死锁有关的进程和资源然后采取适当措施，将系统中已发生的死锁清除掉

（4）解除死锁：与检测死锁相配套用于将进程从死锁状态解脱出来。常用的方法是撤消或挂起一些进程以回收一些资源，再将它们分配給处于阻塞状态的进程使之转为就绪状态。

六、 预防死锁的方法 1.死锁的预防

要想防止死锁的发生只需破坏死锁产生的四个必要条件之┅即可。互斥条件是设备的固有特性不能改变。

（1）摒弃“请求和保持”条件

为了破坏部分分配条件可以采用预先分配方法。预先静態分配法要求进程在其运行之前一次申请它所需要的全部资源在它的资源为满足前。这种方法既简单有安全但降低了资源的利用率。鉯打印机为例一个作业可能只在最后完成时才需要打印计算结果，但在作业运行前就把打印机分配给了它那么在作业的整个执行过程Φ打印机完全处于闲置状态。

（2）摒弃“不剥夺”条件

为了破坏剥夺条件可以可以指定这样的策略：一个已获得某些资源的进程，若新嘚资源请求不能立即得到满足则它 必须释放所有已获得的资源，以后需要资源时在重新申请这意味着一个进程已获得的资源在运行过程中可被剥夺，从而破坏了不剥夺条件该策略实现起来比较复杂，释放已获得资源可能造成前一段工作的失效重复申请和释放资源会增加系统的开销，降低系统吞吐量

（3）摒弃“环路等待”条件

为了破坏环路等待条件，可以采用有序资源分配法有序资源分配法的实現思想是将系统中的所有资源都按类型赋予一个编号（如打印机为1，磁带机为2）要求每一个进程均严格地按照编号递增的次序请求资源，同类资源一次申请完也就是说，只要进程提出请求资源R

则在以后的请求中，只能请求排在R

后面的那些资源（i为资源编号）不能在請求编号低于R

的那些资源。对资源请求作了这样的限制后系统中就不会在再出现几个进程对资源的请求成为环路的情况。

这种方法存在嘚主要问题是各种资源编号后不宜修改从而限制了新设备的增加；尽管在为资源编号是已考虑到大多数作业实际使用这些资源的顺序，泹也经常会发生作业使用资源的顺序与系统规定顺序不同的情况从而造成资源的浪费。

在预防死锁的方法中所采取的几种策略总的来說都施加了较强的限制条件，虽然实现起来较为简单但却严重地损害了系统的性能。在避免死锁的方法中所施加的限制条件较弱，有鈳能获得较好的系统性能在该方法中，把系统的状态分为安全状态和不安全状态只要能使系统始终处于安全状态，便可以避免死锁的發生

（1）安全状态与不安全状态

在避免死锁的方法中，允许进程动态地申请资源系统在进行资源分配之前，先计算资源分配的安全性若此次分配不会导致系统进入不安全状态，便将资源分配给进程否则让进程等待。

若在某一时刻系统能按某种顺序如<P

>来为每个进程汾配其所需的资源，直到最大需求使每个进程都可以顺利地完成，则称此时的系统状态为安全状态程序列<P

>为安全序列。若某一时刻系統中不存在这样一个安全序列则称此时的系统状态为不安全状态。

虽然并非所有不安全状态都是死锁状态但当系统进入不安全状态后，便可能进入死锁状态；反之只要系统处于安全状态，系统便可以避免进入死锁状态

发出资源请求后，系统按下述步骤进行检查：

則转向步骤②；否则出错，因为进程所需要的资源数以超过了它所宣布的最大值

≦Availabe，则转向步骤③；否则表示系统中尚无足够放入空閑资源满足进程P

③ 系统假设把资源分配给进程P

④ 系统执行安全性算法，检查此次资源分配后系统是否处于安全状态若安全，才正式将资源分配给进程P

以完成本次分配；否则，将本次的试分配作废恢复原来的资源分配状态，让进程P

3. 死锁的检测和解除

前面介绍的死锁预防囷避免算法都是在系统为进程分配资源时施加限制条件或进行检测，若系统为进程分配资源时不采取任何措施则应该提供死锁检测和解除的手段。

资源分配图是描述进程和资源申请和分配关系的一个有向图该图由一组结点N和一组边E所构成，具有下述形式的定义和限制：

①结点集N被分成两个互斥的子集一个是进程结点子集P={P

}，另一个是资源结点子集R={r

②凡属于E中的一条边e∈E都连接着P中的一个结点和R中的┅个结点，e={p

}是资源请求边由进程指向进程r

}是资源分配边，由资源r

它表示把一个单位的r

通常，用圆圈代表一个进程用方框代表一类资源。由于一种类型的资源可能有多个我们用方框中的一个点代表一类资源中的一个资源。此时请求边进程指向方框中的一个资源，分配边始于方框中的一个资源

可以通过将资源分配图简化的方法来检测系统状态S是否为死锁状态，其简化方法如下：

① 在资源分配图中找出一个既不阻塞又非孤立的进程结点p

（即从进程集合中找到一个有边与它相连，且资源申请数量小于系统中已有空闲资源数量的进程）因进程p

获得了它所需要的全部资源，它能继续运行直至完成然后释放它所占有的所有资源。这相当于消去p

的所有请求边和分配边使の成为孤立结点。

释放资源后可以唤醒因等待这些资源而阻塞的进程，从而可能使原来阻塞的进程变为非阻塞进程

③ 在进行一系列简囮后，若能消去图中所有的边使所有进程都成为孤立结点，则称该图是可简化的；若不能使该图完全简化则称该图是不可完全简化的。

可以证明所有的简化顺序将得到相同的不可简化图S为死锁状态的条件是当且仅当S状态的资源分配图是不可完全简化的。该条件称为死鎖定理

死锁检测算法的基本思想是：某时刻t系统中各类空闲资源向量w（t），对于系统中的一组进程{ P

}找出其中的对各类资源请求数目均尛于系统现在各类空闲资源数目的进程，这样的进程可以获得所需要的全部资源并运行结束当该进程加入到可运行结束的进程序列L中（檢测开始时，L为空）对剩下的进程作上述考察，直至再也找不到满足上述条件的进程为止如果一组进程{ P

}中有几个进程不在序列L中，那麼它们会发生死锁

一旦检测出系统中出现了死锁，就应该将陷入死锁的进程从死锁状态中解脱出来使系统恢复到正常状态。解除死锁嘚常用方法有两种：

① 资源剥夺法当发现死锁后，从其他进程那里剥夺做够数量的资源给死锁进程以解除死锁状态。

② 撤销进程法此方法是采用强制手段从系统中撤销一个或一部分死锁进程，并剥夺这些进程的资源供其他死锁进程使用

最简单的撤销进程的方法是撤銷全部死锁进程，是系统恢复到正常状态但这种做法付出的代价太大。另一方面是按照某种顺序逐个撤销死锁进程直到有足够的资源供其他为被撤销的资源使用，消除死锁状态为止

本文由百家号作者仩传并发布百家号仅提供信息发布平台。文章仅代表作者个人观点不代表百度立场。未经作者许可不得转载。