山东专升本操作系统讲义

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无操作系统时的计算机系统 （1）电子管计算机（19461958），无操作系统，由手工控制作业的输入输出，通过控制台开关启

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

4、过程：用户将作业交到机房，操作员将一批作业输入到辅存（如磁带）上，形成一个作业队列。当需要调入作业时，由监控程序从这一批中选一道作业调入内存运行。当这一作业完成时，监控程序调入另一道程序，直到这一批作业全部完成。（2）单道批处理系统：系统对作业的处理都是成批地进行的、且在内存中始终只保持一道作业。（3）单道批处理系统的特征：自动性，顺序性，单道性。在单道批处理系统中，内存中仅有一道作业，它无法充分利用系统中的所有资源，致使系统性能较差。3多道批处理系统（1）多道程序设计技术：在内存中放多道程序,使它们在管理程序的控制下相互穿插地运行。引入多道程序设计技术的好处：1）提高CPU的利用率；2）提高

5、内存和I/O设备的利用率；3）增加系统吞吐量。（2）多道批处理系统：用户所提交的作业都先存放在外存上并排成一个队列，称为“后备队列”；然后，由作业调度程序按一定的算法从后备队列中选择若干个作业调入内存，使它们共享CPU和系统中的各种资源。（3）多道批处理系统的特征：1）多道性：在内存中可同时驻留多道程序，并允许它们并发执行；2）无序性：多个作业完成的先后顺序与它们进入内存的顺序之间，并无严格的对应关系；3）调度性：作业从提交给系统开始直至完成需要经过两次调度：作业调度和进程调度。（4）多道批处理系统的优缺点：1）资源利用率高；2）系统吞吐量大；3）平均周转时间长；4）无交互能力。（5）操作系统

6、的定义：操作系统是一组控制和管理计算机硬件和软件资源，合理地对各类作业进行调度，以及方便用户使用的程序的集合。4分时系统（1）引入原因：推动分时系统形成和发展的主要动力是用户的需要：人-机交互、共享主机、方便上机。（2）概念：分时系统是指在一台主机上连接了多个带有显示器和键盘的终端，同时允许多个用户共享主机中的资源，每个用户都可以通过自己的终端以交互的方式使用计算机。 （3）关键问题：为实现分时系统，其中，最关键的问题是如何使用户能与自己的作业进行交互，即使有多个用户同时通过自己的键盘键入命令，系统也应能全部地及时接收并处理。（4）改变方法：为了实现人机交互，必须彻底改变原来的批处理系统的运行

7、方式：（1）用户作业直接进入内存；（2）不允许一个作业长期占有处理机，为此规定每个作业只运行一个很短的时间（时间片），然后暂停该作业的运行，立即调度下一个程序运行。（5）分时系统的特征： = 1 * GB3 多路性（即同时性）：允许在一台主机上同时联接多台联机终端，系统按分时原则为每个用户服务。 = 2 * GB3 独立性：每个有用户各占一个终端，彼此独立操作，互不干扰。 = 3 * GB3 及时性：用户的请求能在很短时间内获得响应。 = 4 * GB3 交互性：用户可通过终端与系统进行广泛的人机对话。5实时系统（1）实时系统是指系统能及时（或即时）响应外部事件的请求，在规定的时间内完成对该事

8、件的处理，并控制所有实时任务协调一致运行。它主要应用于实时控制系统（如飞机自动驾驶，核反应堆）和实时信息处理系统（如飞机订票）。（2）实时任务的分类 = 1 * GB3 按任务执行时是否呈现周期性来划分：周期性实时任务和非周期性实时任务。 = 2 * GB3 按对截止时间的要求来划分：它又可分为硬实时任务和软实时任务。硬实时任务是系统必须满足任务对截止时间的要求，否则可能出现难以预测的结果，如化学反应的控制系统。软实时任务也联系着一个截止时间，但并不严格，若偶尔错过了任务的截止时间，对系统产生的影响也不会太大，如数字视频、音频处理系统。 （3）实时系统与分时系统特征的比较：多路性；独立性；及时

9、性；交互性；可靠性。6微机操作系统的发展（1）单用户单任务操作系统只允许一个用户上机，且只允许用户程序作业一个任务运行。主要配置在8位和16位微机上。最有代表性的单用户单任务操作系统是CP/M（8位）和MSDOS（16位）。（2）单用户多任务操作系统只允许一个用户上机，但允许用户把程序分为若干个任务，使它们并发执行，从而有效地改善了系统的性能。最有代表性的单用户多任务操作系统是微软公司推出的Windows。（3）多用户多任务操作系统允许多个用户通过各自的终端使用同一台机器，共享主机系统中的各种资源，而每个用户程序又可进一步分为几个任务，使它们能并发执行，从而可进一步提高资源利用率和系统吞吐量。

10、UNIX OS是美国电报电话公司的Bell实验室开发的，已被广泛应用于多种中、小型机上。现在最有影响的两个能运行在微机上的UNIX操作系统的变型是Solaris OS和Linux OS，后者源代码是公开的。三、操作系统的基本特性1并发性。并发是指在内存中放多道作业，在一个时间段上来看，每一道作业都能不同程度地向前推进，但在任何一个时间点上只能有一道占用CPU。并行性是指两个或多个事件在同一时刻发生；并发性是指两个或多个事件在同一时间间隔内发生。在多道程序环境下，并发性是指在一段时间内，宏观上有多个程序在同时运行，但在单处理机系统中，每一时刻却仅能有一道程序执行，故微观上这些程序只能是分时地交替

11、执行。为了实现程序并发执行引入了进程，进程是可以并发执行的，同时使CPU和I/O设备可以并行工作。2共享性共享是指系统中的资源可供内存中多个并发执行的进程(线程)共同使用。两种共享方式：（1）互斥共享方式（如打印机），一段时间内只允许一个进程访问（2）同时访问方式（如磁盘设备）允许在一段时间内由多个进程“同时”对它们进行访问。3虚拟性虚拟是指通过某种技术把一个物理实体映射为若干个对应的逻辑实体。虚拟是操作系统管理系统资源的重要手段，可提高资源利用率。 时分复用技术：分时使用某个设备提高其利用率，如虚拟处理机（多道程序设计技术），虚拟设备（SPOOLing技术）。空分复用技术：主要提高存储空间的

12、利用率，如虚拟磁盘技术，虚拟存储器技术。4异步性异步性指在多个进程并发执行过程中，各个进程运行时间、运行顺序具有不确定性，进程以不可预知的速度向前推进。在有些课本中称之为不确定性。四、操作系统的主要功能1处理机管理功能处理机管理的主要任务是对处理机进行分配，并对其运行有效的控制和管理。处理机的分配和运行都是以进程为基本单位。因此对处理机的管理可归结为对进程的管理。 处理机管理功能包括进程控制、进程同步、进程通信、调度 。2存储器管理功能存储器管理的主要任务，是为多道程序的运行提供良好的环境，方便用户使用存储器，提高存储器的利用率，以及能从逻辑上扩充内存。存储器管理要具备下列功能：内存分配，内存

13、保护，地址映射，内存扩充。 3设备管理功能设备管理用于管理计算机系统中所有的外围设备， 而设备管理的主要任务是，完成用户进程提出的I/O请求；为用户进程分配其所需的I/O设备；提高CPU和I/O设备的利用率；提高I/O速度；方便用户使用I/O设备。设备管理应具有功能：缓冲管理，设备分配，设备处理，设备独立性和虚拟设备4文件管理功能文件管理的主要任务是为每个文件分配必要的外存空间，提高外存的利用率，并能有助于提高文件系统的运行速度。文件系统管理的功能：文件存储空间管理，目录管理，文件的读/写管理和保护 5操作系统与用户之间的接口（1）用户接口：提供给用户使用的接口，用户可通过该接口取得操作系统的

14、服务，可分为联机用户接口，脱机用户接口，图形用户接口。（2）程序接口：提供给程序员在编程时使用的接口，是用户程序取得操作系统服务的惟一途径。它是由一组系统调用组成的，每一个系统调用都是一个能完成特定功能的子程序。五、OS结构设计1传统的操作系统结构（1）无结构操作系统（2）模块化结构OS：该技术是基于“分解”和“模块化”原则来控制大型软件的复杂度的。将OS按其功能划分为若干个具有一定独立性和大小的模块。（3）分层式结构OS：从物理机器开始， 在其上面先添加一层具有一定功能的软件A1, 由于A1是建立在完全确定的物理机器上的，在经过精心设计和几乎是穷尽无遗的测试后，可以认为A1是正确的；然后再在

15、A1上添加一层新软件A2，如此一层一层地自底向上增添软件层，每一层都实现若干功能，最后总的构成一个能满足需要的OS。 2微内核结构 所谓微内核技术，是指精心设计的、能实现现代OS核心功能的小型内核，它与一般的OS(程序)不同， 它更小更精炼，它不仅运行在核心态，而且开机后常驻内存， 它不会因内存紧张而被换出内存。微内核并非是一个完整的OS， 而只是为构建通用OS提供一个重要基础。微内核所提供的功能，通常都是一些最基本的功能，如进程管理、低级存储器管理、中断和陷入处理。微内核结构特征：以微内核为OS核心，以客户/服务器为基础，采用面向对象的程序设计方法。进程管理主要知识点： 一、 进程的基本概念

16、1. 一个程序通常由若干个程序段组成，这些程序段必须按照某种先后次序执行，仅当前一个操作（程序段）执行完后才能执行后继操作，这类计算过程就是程序的顺序执行过程。程序顺序执行的特征：顺序性，封闭性，可再现性。2前趋图 前趋图是一个有向无循环图，图中的每个结点可以表示一条语句、一个程序段或一个进程，结点间的有向边表示两个结点之间存在的偏序或前趋关系“ ”： =（Pi, Pj ）| Pj 必须在Pj 开始执行之前完成3. 程序的并发执行 程序的并发执行是指若干个程序（或程序段）同时在系统中运行，这些程序（或程序段）的执行在时间上是重叠的，即一个程序（或程序段）的执行尚未结束，另一个程序（或程序段）的

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

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

19、程与程序的区别进程是程序在处理机上的一次执行过程，是一个动态的概念；而程序是代码的有序集合，其本身没有任何运行的含义，是静态的概念。进程是一个状态变化的过程，是有生命周期的（因创建而产生，因调度而执行，因得不到资源而暂停等，因撤消而消亡）；而程序是永久的，可以长久保存。进程与程序的组成不同。进程是由程序、数据和进程控制块组成的；程序仅是代码的有序集合。进程与程序之间不是一一对应的。通过多次运行，同一个程序可以对应多个进程；通过调用关系，一个进程可以包含多个程序。进程状态及其变化 进程执行时的动态特性决定了进程具有多种状态。事实上，运行中的进程至少具有以下3种基本状态。就绪状态。进程已获得除处理

20、机以外的所有资源，一旦获得处理机就可以立即执行，这时进程所处的状态为就绪状态。执行状态。当一个进程获得必要地资源并正在处理机上运行时，此进程所处的状态为执行状态。执行状态又称运行状态。阻塞状态。正在执行的进程，由于发生某事件而暂时无法继续执行（如等待输入/输出完成），此时进程所处的状态为阻塞状态。阻塞状态又称等待状态或睡眠状态。 进程并非固定处于某一种状态，其状态会随着自身的运行和外界条件的变化而发生变化。通常，可以用一个进程状态变化图来说明系统中每个进程可能具备的状态，以及引起状态发生变化的可能原因。图2.1 进程三状态转换图调度时间片用完I/O完成I/O完成挂起状态。当用户在自己的程序运行

21、期间发现有可疑问题时,希望暂时使自己的程序静止下来,这种静止状态称为挂起状态。图2.2 进程五状态转换图创建状态和终止状态创建状态：创建一个进程一般要通过两个步骤: 为一个新进程创建PCB，并填写必要的管理信息；把该进程转入就绪状态并插入就绪状态之中。终止状态：终止一个进程一般要通过两个步骤: 等待操作系统进行善后处理；将PCB清零，并将PCB空间返还系统。创建状态连接就绪状态；终止状态连接执行状态图2.3 进程加入创建，终止状态转换图进程控制块 为了管理和控制进程的运行，系统为每个进程定义了一个数据结构进程控制块（Process Control Block ,PCB），用于记录进程的属性信息

22、。当创建一个进程时，系统为该进程建立一个PCB：当进程执行时，系统通过其PCB了解进程的现行状态信息，以便对其进行控制和管理：当进程结束时，系统收回其PCB，该进程随之消亡。由此可见，系统根据PCB感知进程的存在，PCB是进程存在的唯一标志。PCB所包含的内容：进程标识符，处理机状态，进程调度信息，进程控制信息 在一个系统中，通常存在许多进程，为了对它们进行有效管理，应该用适当方法将PCB组织起来。目前常用链表或表格将PCB组织起来。二、 进程控制 进程控制的职责是对系统中的所有进程实施有效地管理。其功能包括进程的创建、进程的撤销、进程的阻塞与唤醒等，进程的挂起与激活。这些功能一般由操作系统内

23、核的原语实现。进程控制功能通过执行各种原语来实现。原语是由若干条机器指令构成的、用以完成特定功能的一段程序。原语在执行期间不可分割，所以原语操作具有原子性。进程创建引起创建进程的事件：用户登录，作业调度，提供服务，应用请求。进程创建过程：先向系统申请一个空闲PCB，并为子进程分配必要地资源，然后将子进程的PCB初始化，并将此PCB插入就绪队列，最后返回一个进程标识号（即子进程的进程标识号）。2进程终止引起进程终止的事件：正常结束，异常结束，外界干预进程终止过程：先从PCB集合中找到被撤消进程的PCB，若被撤消进程正处于执行状态，则立即停止该进程的执行，并设置重新调度标志，以便进程撤消后将处理机

24、分配给其他进程。若被撤消进程有子孙进程，还应将该进程的子孙进程予以撤消。对于被撤消进程所占有的资源，或者归还给父进程，或者归还给系统。最后撤消其进程控制块。3. 进程阻塞与唤醒阻塞原语的作用是将进程由执行状态转换为阻塞状态，而唤醒原语的作用则是将进程由阻塞状态变为就绪状态。引起进程阻塞和唤醒的事件：请求系统服务，启动某种操作，新数据尚未到达，无新工作可做。进程阻塞过程：在阻塞一个进程时，由于该进程正处于执行状态，故应中断处理机，保存该进程的CPU现场，停止运行该进程，然后将该进程插入到相应事件的等级队列中，再从就绪队列中选择另外一个进程投入运行。进程唤醒过程：将被唤醒进程从相应的等待队列中移出

25、，将状态改为就绪并插入就绪队列。注意：一个进程由执行状态转变为阻塞状态，是这个进程自己调用阻塞原语去完成的，而进程由阻塞状态转变为就绪状态，是另一个发现者进程调用唤醒原语实现的。一般这个发现者进程与被唤醒进程是合作的并发进程。三、 进程同步并发执行的进程之间存在着不同的相互制约关系，为了协调进程之间的相互制约关系，就需要实现进程的同步。两种制约关系：直接制约（资源共享，互斥关系），间接制约（进程合作，同步关系）1.临界资源一次仅允许一个进程使用的资源称为临界资源。许多物理设备都属于临界资源，如打印机、绘图机等。除物理设备外，还有许多变量、数据等都可以被若干进程共享，它们也属于临界资源。在每个进

26、程中，访问临界资源的那段程序称为临界区。为了保证临界资源的正确使用，可以把临界资源的访问分为四个部分：（1）进入区。为了进入临界区使用临界资源，在进入区检查可否进入临界区；如果可以进入临界区，则应设置正在访问临界区的标志，以阻止其他进程同时进入临界区。（2）临界区。进程中访问临界资源的那段代码，又称临界段。（3）退出区。将正在访问临界区的标志清除。（4）剩余区。代码中的其余部分。2.同步机制应遵循的规则（1）空闲让进。当没有进程处于临界区时，可以允许一个请求进入临界区的进程立即进入临界区。（2）忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待。（3）有限等待。对要求访问临界资

27、源的进程，应保证能在有限时间内进入临界区。（4）让权等待。当进程不能进入临界区时，应释放处理机。3.信号量机制1）记录型信号量S是一个确定的二元组，其中S.value是一个具有非负初值的整型变量，S.L是一个初始状态为空的队列，用来记录因该信号量而处于阻塞状态的进程。整型变量S.value表示系统中某类资源的数目，当其值 大于0时，表示系统中当前可用资源的数目；当其值小于0时，其绝对值表示系统中因请求该类资源而被阻塞的进程数目。除信号量的初值外，信号量的值仅能有P操作（又称Wait操作）和V操作（又称Signal操作）改变。一个信号量的建立必须经过说明，即应该准确说明S的意义和初值（注意：这个

28、初值不是一个负值）。每个信号量都有相应的队列，在建立信号量时，队列为空。P、V操作以原语方式实现，信号量的值仅能由这两条原语加以改变。P、V操作的定义如下：（1）P操作。P操作记为P（S），其中S为一个信号量，它执行时主要完成下述动作： S = S-1； 若S0阻塞该进程，并将它插入该信号量的等待队列中。 （2）V操作。V操作记为V(S),S为一个信号量，它执行时主要完成下述动作： S=S+1; 若S0从信号量等待队列中移出一个进程，使其变为就绪状态并插入就绪队列，然后再返回原进程继续执行。2）AND型信号量3）信号量集4）管程4. 利用信号量实现互斥利用信号量能方便的实现进程互斥。设S为两个

29、进程P1、P2实现互斥地信号量，由于每次只允许一个进程进入临界区，所以S的初值应为1（即可用资源数目为1）。只需要把临界区置于P（S）和V（S）之间，既可以实现两个进程的互斥。互斥访问临界区的描述如下：5. 利用信号量实现前趋关系设有两个并发执行的进程P1，P2，P1中有语句S1，P2中有语句S2，若希望在S1执行后再执行S2，实现此同步关系，设一个同步信号量S，初值为0，在S1语句后加V（S），在S2语句前加P（S）。用信号量来解决前趋图中描述的复杂的前趋关系。四、 经典进程同步问题生产者-消费者问题哲学家进餐问题读者-写者问题五、 进程通信进程间的信息交换称为进程通信。前面介绍的进程互斥与

30、同步就是一种进程间的通信方式。由于进程互斥与同步交换的信息量减少且效率较低，因此称这两种通信方式为低级进程通信方式，相应地也将P、V原语称为两条低级进程通信原语。高级进程通行方式是指进程之间较高的效率传送大量数据。1.进程通信的类型高级进程通信方式可以分为三大类：共享存储器系统、消息传递系统以及管道通信系统。（1）共享存储器系统为了传输大量数据，在存储器中划出一块存储区诸进程可以通过对共享存储区进行读或写来实现通信。进程在通信前，应向系统申请建立一个共享存储区，并指定该共享存储区的关键字；若该共享存储区以建立，则将该共享存储区的描述符 给申请者。然后，申请者把获得的共享存储区附接到本进程的地址

31、空间上，这样，进程便可以像读写不同存储器一样地读写共享存储区。（2）消息传递系统在消息传递系统中，进程间的数据交换以信息为单位，程序员直接利用系统提供的组通信命令（原语）来实现通信。操作系统隐藏了通信实现的细节，大大简化了通信程序编制的复杂性，因而获得了广泛的应用。消息传递机制因其实现方式不同又可以分为： 直接通信方式。发送进程直接把消息发送给接受进程，并将它挂在接收进程的消息缓冲队列上，接受进程从消息缓冲队列中取得信息。 间接通信方式。发送进程把消息发送给中间某个实体中，接收实体从中间实体中取得消息。这种中间实体一般称为信箱，故这种通信方式也称为信箱通信方式。信箱通信方式广泛应用于计算机网络

32、中，现称为电子邮件系统。两种方式的主要区别：a.发送和接收原语。 直接通信原语为send(receiver,message),receive(sender,message)； 间接通信原语为send(mailbox,message),receive(mailbox,message)；它还需要提供有关信箱创建和撤消的原语。b.提供对方的标识符。直接通信要求发送双方显式地提供对方的标识符，对接收进程，如果允许它同时接收多个进程发来的消息，则接收原语中的发送进程标识符可以是通信完成后返回值；间接通信则不要求它们显式地提供对方的标识符，而只需提供信箱标识。c.通信链路。 直接通信，进程只需提供对方的标

33、识符便可进行通信，在收发双方之间建立通信链路由系统自动完成，并且在收发双方之间有且仅有一条通信链路；间接通信仅当一对进程共享某个信箱时，它们之间才有通信链路，而且一条链路可对应多个进程，每对进程间也可以有多条链路。d.实时性。直接通信通常只能提供实时通信；间接通信则既可实现实时通信也可实现非实时通信。（3）管道通信系统管道是用于连接读进程和写进程以实现它们之间通信的共享文件，向管道提供输入的发送进程（即写进程）以字符流形式将大量的数据送入管道，而接收 管道输出的接收进程（即读进程）可以从管道中接收数据。六、 线程1. 线程的概念在操作性系统中引入进程的目的是为了使多道程序并发执行，以改善资源利

34、用率及提高系统吞吐量；而在操作系统中再引入线程，则是为了减少程序并发执行时所付出的时空开销，使操作系统具有更好的并发性。线程自己基本上不拥有资源，只拥有在运行时必不可少的一点资源（如程序计数器、一组寄存器和栈），但它可以与同属一个进程的其他线程共享进程拥有的全部资源。线程与进程的比较：调度，并发性，拥有资源，系统开销线程的属性：轻型实体，独立调度和分派的基本单位，可并发执行，共享进程资源2.线程的实现内核支持线程，由操作系统内核完成创建和撤销的线程，在支持内核级线程的操作系统中，内核维护进程和线程的上下信息，并完成线程切换工作。用户级线程是指不依赖于操作系统内核，由应用线程库提供创建、同步、调

35、度和管理线程的函数来控制的线程。由于用户级线程的维护由应用进程完成，不需要操作系统内核了解用户级线程的存在，因此可用与不支持内核级线程的多进程操作系统，甚至是单用户操作系统。处理机调度与死锁主要知识点： 一、 处理机调度类型一个作业从提交开始直到完成往往要经历下述三级调度。1.高级调度高级调度又称宏观调度、作业调度或长程调度，其主要任务是按一定的原则从外存处于后备状态的作业中挑选一个（或多个）作业，给它（们）分配内存、输入/输出设备等必要的资源，并建立相应的进程，以使它（们）获得竞争处理机制的权利。批处理系统中大多配有作业调度，而其他系统中通常不需要配置作业调度。作业调度的执行效率较低，通常为

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

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

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

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

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

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

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

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

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

45、权调度算法和抢占式优先权调度算法。 = 1 * GB3 非抢占式优先权调度算法的实现思想是系统一旦将处理机分配给就绪队列中优先权最高的进程后，该进程便一直运行下去，直到由于其自身的原因（任务完成或等待事件）主动让出处理机时，才将处理机分配给另一个更高优先权的进程。 = 2 * GB3 抢占式优先权调度算法的实现思想是将处理机分配给优先权最高的进程，使之运行。在进程运行过程中，一旦出现了另一个优先权更高的进程时，进程调度程序就停止原运行进程，而将处理机分配给新出现的高优先权进程。（2）优先权的类型进程的优先权用于表示进程的重要性及运行的优先性。进程优先权通常分为两种：静态优先权和动态优先权。 =

46、 1 * GB3 静态优先权是在创建进程时确定的，确定之后在整个进程运行期间不再改变。确定静态优先权的依据有进程的类型、进程所使用的资源、进程的估计运行时间等因素。进程所索取的资源越多，估计的运行时间越长，进程的优先权越低。进程类型不同，优先权也不同，如联机用户进程的优先权高于脱机用户进程的优先权。 = 2 * GB3 动态优先权是指在创建进程时，根据系统资源的使用情况和进程的当前特点确定一个优先权，在进程运行过程中在根据情况的变化调整优先权。动态优先权一般根据进程占有CPU时间的长短、进程等待CPU时间的长短等因素确定，占有处理机的时间越长，则优先权越低；等待时间越长，则优先权越高。（3）高

47、响应比优先调度算法高响应比优先调度算法是从就绪队列中选择一个响应比最高的进程，让其获得处理器执行，直到该进程完成或因等待事件而退出处理器为止。 （优先权）响应比R = （要求服务时间+作业等待时间） 要求服务时间从上式可见： = 1 * GB3 若等待时间相同，则要求服务时间愈短,其优先权愈高SPF； = 2 * GB3 若服务时间相同，优先权决定于等待时间FCFS； = 3 * GB3 长作业若等待时间足够长，优先级会升高，也能获得CPU。由此可看出此算法既照顾了短进程，又考虑了进程到达的先后次序，也不会使长进程长期得不到服务，因此是一个比较全面考虑的算法；但每次进行调度时，都需要对各个进程

48、计算响应比。所以系统开销很大，比较复杂。 适于批处理系统4基于时间片轮转调度算法在时间片轮转调度算法中，系统将所有就绪进程按到达时间的先后次序排成一个队列，进程调度程序总是悬着队列中的第一个进程执行，并规定执行一定时间（例如100ms，该时间称为时间片）。当该进程使用完这一时间片时（即使进程并未完成其运行），系统将它送至就绪队列队尾，再把处理机分配给下一个就绪进程。这样，处于就绪队列中的进程就可以依次轮流地获得一个时间片的处理时间，然后回到队列尾部，如此不断循环，直至完成为止。 在时间片轮转调度算法中，时间片的大小对系统性能的影响很大。如果时间片太大，以至于所有进程都能在一个时间片内执行完毕，

49、则时间片轮转调度算法就退化成先来先服务调度算法。如果时间片很小，那么处理机将在进程结束之间频繁切换，处理机真正用于运行用户进程的时间将减少。因此时间片的大小应选择恰当，一个较为可取的大小是，时间片略大于一次典型的交互所需要的时间，这样可使大多数进程在一个时间片内完成。5多级反馈队列调度算法多级反馈队列调度算法的实现思想如下：首先应设置多个就绪队列，并为各个队列赋予不同的优先权。第一个队列的优先权最高，第二个队列次之，其余队列的优先权逐次降低。其次，每个队列中进程执行时间片的大小也各不相同，进程所在队列的优先权愈高，其相应的时间片愈短。例如，第i+1个队列的时间片是第i个队列时间片的两倍。第三，

50、当一个新进程进入内存后，首先将它放入第一个队列的末尾，按先来先服务的原则排队等待调度。当轮到该进程时， 如果能在次时间片内完成，便可准备撤离系统；如果它在一个时间片结束是尚未完成，调度程序便将该程序转入第二个队列的末尾，再同样地按先来先服务原则等待调度执行；如果它在第二个队列中运行一个时间片后仍为完成，再以同样方法将它转入第三个队列。如此下去，直到最后一个队列中使用时间片轮转调度算法。第四，仅当第一个队列空闲时，调度程序才调度第二个队列中的进程运行；仅当第1至（i-1）个队列均为空时，才会调度第i个队列中的进程运行。当处理机正为第i个队列中的某进程服务时，若又有新进程进入优先权较高的队列，则此

51、时新进程将抢占正在运行进程的处理机，即由调度程序把正在执行的进程放回第i个队列末尾，重新将处理机分配给新进程。可以看出，多级队列调度算法优先照顾I/O繁忙的进程。I/O繁忙的进程在获得一点CPU时间后就会提出输入/输出请求，因此它们总是被保持在1、2级等较前面的队列中，总能获得较多的调度机会。对于CPU繁忙的进程，它们需要较长的CPU时间，因此会逐渐地由级别高的队列往下降，以获得更多的CPU时间，它们“沉”得越深，被调度到的机会就越少。但是，一旦被调度到，就会获得更多的CPU时间。四、实时调度1实现实时调度的基本条件（1）提供必要的信息：就绪时间、开始截止时间和完成截止时间、处理时间、资源要求

52、、优先级；（2）系统处理能力强：在实时系统中，通常都有着多个实时任务。若处理机的处理能力不够强，则有可能因处理机忙不过来而使某些实时任务不能得到及时处理， 从而导致发生难以预料的后果。（3）采用抢占式调度机制：在含有硬实时任务的实时系统中，广泛采用抢占机制。当一个优先权更高的任务到达时，允许将当前任务暂时挂起，而令高优先权任务立即投入运行，这样便可满足该硬实时任务对截止时间的要求。（4）具有快速切换机制 = 1 * GB3 对外部中断的快速响应能力。为使在紧迫的外部事件请求中断时系统能及时响应，要求系统具有快速硬件中断机构，还应使禁止中断的时间间隔尽量短， 以免耽误时机(其它紧迫任务)。 =

53、2 * GB3 快速的任务分派能力。在完成任务调度后，便应进行任务切换。为了提高分派程序进行任务切换时的速度， 应使系统中的每个运行功能单位适当的小，以减少任务切换的时间开销。2实时调度算法的分类（1）非抢占式调度算法 = 1 * GB3 非抢占式轮转调度算法：该算法常用于工业生产的群控系统中，由一台计算机控制若干个相同的（或类似的）对象，为每一个被控对象建立一个实时任务，并将它们排成一个轮转队列。调度程序每次选择队列中的第一个任务投入运行。 = 2 * GB3 非抢占式优先调度算法：该算法常用于有一定时间要求的实时控制系统之中。当这些要求较为严格的实时任务到达时，把它们安排在就绪队列的队首，

54、等待当前任务自我终止或运行完成后才能被调度执行。（2）抢占式调度算法 = 1 * GB3 基于时钟中断抢占的优先权调度算法：在某实时任务到达后，如果该任务的优先级高于当前任务的优先级，这时并不立即抢占当前任务的处理机，而是等到时钟中断到来时，调度程序才剥夺当前任务的执行，将处理分配给新到的高优先权任务。 = 2 * GB3 立即抢占的优先权调度算法：一旦出现外部中断，只要当前任务未处于临界区，便立即剥夺当前任务的执行，把处理机分配给请求中断的紧急任务。3常用实时调度算法（1）最早截止时间优先即EDF(Earliest Deadline First)算法该算法根据任务的开始截止时间来确定任务的优

55、先级，截止时间越早，优先级越高。在就绪队列中任务按其截止时间排列，队首任务先分配处理机。可以是抢占式或非抢占式。（2）最低松弛度优先即LLF(Least Laxity First)算法该算法是根据任务紧急（或松弛）的程序，来确定任务的优先级。任务的紧急度越高，其优先级越高，并使之优先执行。松弛度最低的任务排在队列最前面，调度程序总是选择就绪队列中的首任务执行。该算法主要采用抢占调度方式。五产生死锁的原因和必要条件1.死锁的概念所谓死锁是指多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程都将无法向前推进。死锁是计算机系统和进程所处的一种状态。2.死锁产生的原因死锁产生的原因有以下两点：

56、（1）系统资源不足。（2）进程推进顺序不当。3.死锁产生的必要条件死锁产生的必要条件有以下四条：（1）互斥条件。进程要求对所分配的资源进行排它性控制，即在一段时间内某资源仅为一个进程所占有。（2）请求和保持条件。部分分配条件又称请求和保持条件。进程每次申请它所需要的一部分资源，在等待新资源的同时，进程继续占有已分配到的资源。（3）不剥夺条件。进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走，即只能由获得该资源的进程自己来释放。（4）环路等待条件。存在一种进程资源的循环等待链，链中每一个进程已获得的资源同时被链中下一个进程所请求。4处理死锁的基本方法（1）预防死锁：通过设置某些限制条件，

57、去破坏死锁四个必要条件中的一个或多个，来防止死锁。（2）避免死锁：不事先采取限制去破坏产生死锁的条件，而是在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免死锁的发生。（3）检测死锁：事先并不采取任何限制，也不检查系统是否进入不安全区，允许死锁发生，但可通过检测机构及时检测出死锁的发生，并精确确定与死锁有关的进程和资源，然后采取适当措施，将系统中已发生的死锁清除掉（4）解除死锁：与检测死锁相配套，用于将进程从死锁状态解脱出来。常用的方法是撤消或挂起一些进程。以回收一些资源，再将它们分配给处于阻塞状态的进程，使之转为就绪状态。六、 预防死锁的方法1.死锁的预防要想防止死锁的发生

58、，只需破坏死锁产生的四个必要条件之一即可。互斥条件是设备的固有特性，不能改变。（1）摒弃“请求和保持”条件为了破坏部分分配条件，可以采用预先分配方法。预先静态分配法要求进程在其运行之前一次申请它所需要的全部资源，在它的资源为满足前。这种方法既简单有安全，但降低了资源的利用率。以打印机为例，一个作业可能只在最后完成时才需要打印计算结果，但在作业运行前就把打印机分配给了它，那么在作业的整个执行过程中打印机完全处于闲置状态。（2）摒弃“不剥夺”条件为了破坏剥夺条件，可以可以指定这样的策略：一个已获得某些资源的进程，若新的资源请求不能立即得到满足，则它 必须释放所有已获得的资源，以后需要资源时在重新申

59、请。这意味着一个进程已获得的资源在运行过程中可被剥夺，从而破坏了不剥夺条件。该策略实现起来比较复杂，释放已获得资源可能造成前一段工作的失效，重复申请和释放资源会增加系统的开销，降低系统吞吐量。（3）摒弃“环路等待”条件为了破坏环路等待条件，可以采用有序资源分配法。有序资源分配法的实现思想是将系统中的所有资源都按类型赋予一个编号（如打印机为1，磁带机为2），要求每一个进程均严格地按照编号递增的次序请求资源，同类资源一次申请完。也就是说，只要进程提出请求资源Ri，则在以后的请求中，只能请求排在Ri后面的那些资源（i为资源编号），不能在请求编号低于Ri的那些资源。对资源请求作了这样的限制后，系统中就

60、不会在再出现几个进程对资源的请求成为环路的情况。这种方法存在的主要问题是各种资源编号后不宜修改，从而限制了新设备的增加；尽管在为资源编号是已考虑到大多数作业实际使用这些资源的顺序，但也经常会发生作业使用资源的顺序与系统规定顺序不同的情况，从而造成资源的浪费。2. 死锁的避免在预防死锁的方法中所采取的几种策略，总的来说都施加了较强的限制条件，虽然实现起来较为简单，但却严重地损害了系统的性能。在避免死锁的方法中，所施加的限制条件较弱，有可能获得较好的系统性能。在该方法中，把系统的状态分为安全状态和不安全状态，只要能使系统始终处于安全状态，便可以避免死锁的发生。（1）安全状态与不安全状态在避免死锁的