《天大《操作系统原理》学习笔记二.pdf》由会员分享，可在线阅读，更多相关《天大《操作系统原理》学习笔记二.pdf（34页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、操作系统原理学习笔记二 主主主主 题题题题：操作系统原理学习笔记 内内内内 容容容容：操作系统原理操作系统原理操作系统原理操作系统原理学习笔记学习笔记学习笔记学习笔记二二二二 进程管理进程管理进程管理进程管理 处理机是计算机系统的核心资源。操作系统的功能之一就是处理机管理。计算机系统的效率主要是由处理机决定的。处理机管理是整个操作系统的核心。现代计算机系统多数是多道系统，且为单处理机系统。处理机要同时运行多个作业的程序。合理有效地管理和分配处理机资源，是操作系统的一个十分重要的任务。处理机管理就是按照一定策略对处理机进行合理调配、以满足用户作业运行的需要。为了准确地描述系统内多个作业的运行情况
2、，以及对系统资源的管理和分配的情况，在现代计算机系统中都采用进程的概念。现代计算机系统都是以进程作为分配资源和独立运行的基本单位。所以处理机管理实质上是进程管理。一一一一、进程的基本概念进程的基本概念进程的基本概念进程的基本概念 进程是操作系统中最重要的、最基本的概念。对操作系统的设计和研究都是以进程作为出发点。进程的概念是从程序中产生的，但它与程序有着本质的不同。1、程序的顺序执行 程序是“一组有序的操作序列”。“操作”：机器指令、高级语言中的语句。“有序”：操作必须按照严格的先后次序进行，必须在前一个操作完成后，才能执行下一个操作。一个复杂的程序也可以分为若干个程序段，各个程序段也是依照一
3、定的次序逐个执行。程序本身具有的顺序执行的特点。在单道系统中程序执行时，具有顺序执行的特点，所以又把单道系统中的程序称为顺序程序。顺序程序具有如下特性：?顺序性、程序运行时处理机必须严格按照程序所规定的顺序执行有关操作。?可再现性、如果程序在不同的时间重复执行，只要执行时的初始条件相同，程序运行结果必然相同。操作系统原理学习笔记二?封闭性、程序在运行时独占全部系统资源，这些资源的状态只由程序本身确定，只有该程序的操作才能改变资源的状态。所以，程序在执行过程中不会受到外界因素的影响。?与时间无关性。程序的运行结果与它执行的速度无关。2、程序的并发执行 由于通道技术和中断技术的不断完善，计算机系统
4、出现了处理机与外部设备的并行工作方式，使得处理机可以同时运行多个用户的程序。这就是多道程序设计系统。在多道系统中，由于程序的运行环境发生了根本的变化,程序的执行方式有了本质的变化，它们从顺序执行成为并发执行。程序的并发执行是指一个程序的若干个程序段可以同时在系统中执行，它们在执行时间是重叠的。执行时间上有重叠的几个程序称为并发程序。“同时”和“执行时间重叠”是一个宏观概念。从微观上看，处理机在任一时刻只能执行一个程序，并发程序是在处理机上交替运行的。由于程序的并发执行使得系统资源不再由一道程序独占，而是由多道程序共享。程序的并发执行和资源共享之间是相辅相成的。只有允许程序的并发执行，才存在资源
5、共享的问题；只有有效地实现资源共享，才使得程序可以并发执行。多道系统中程序的并发执行和资源的共享，使得程序的运行环境有了根本的变化，并发执行的程序产生了与单道环境下顺序程序完全不同的特性。并发程序具有以下特性：?并发性 并发程序的若干程序段同时在系统中运行。这些程序段的执行在时间上是重叠的，一个程序段的执行尚未结束，另一个程序段的执行已经开始。?开放性 由于系统中的并发程序共享系统资源，资源的状态不再由一个程序确定，而是由多个程序的执行过程共同决定的。而程序在执行中与资源状态等外部因素有关，所以程序不再具有封闭性。程序在两次运行中，即使初始条件相同，它的运行结果可能完全不同，并发程序失去了可再
6、现性。begin integer N;N:=0;cobegin program A:begin L1:;N:=N+1;操作系统原理学习笔记二 goto L1;end;program B:begin L2:;print(N);N:=0;goto L2;end;coend;end;程序 A 和 B 是并发执行的，它们根据运行环境的情况按照各自独立的速度运行。由于它们共享一个变量 N，而 N 的值是由这两个程序共同确定的。所以一个程序的执行结果，与它和另一个程序的相对执行速度有密切的关系。A 执行 5 次循环后，N 的值是 5。它第 6 次循环时，在执行 N:=N+1 语句前，系统把处理机分配给程序
7、 B 使用。程序 B 在执行 print(N)时，打印 N 的值 5。A 执行第 6 次循环时，在执行 N:=N+1 语句之后，处理机分配给程序 B 使用。程序 B 在执行 print(N)时，打印 N 的值 6。两次运行结果截然不同。?相互制约性 有些并发程序同属于一个作业，它们需要共同协作完成某一任务，这些程序之间必定存在制约关系。并发程序由于在逻辑上或功能上存在的联系而产生的制约，称为直接制约。几个具有相对独立功能的并发程序，虽然它们在完成各自的功能方面不存在任何联系，但当它们竞争使用某一种共享资源时，将互相产生制约，获得资源的程序可以继续运行，其它需要使用这种资源的程序将处于等待状态，
8、直到获得该资源后才继续运行。并发程序由于共享系统资源而产生的制约称为间接制约。?动态性 程序与其执行过程不再一一对应。在顺序程序执行时，每一个程序只对应一个执行过程。但是并发程序执行时，一个程序可以对应多个执行过程。在单道系统中，资源的分配和管理是面向程序的，因为一个程序总是对应一个执行过程。在多道系统中，仍以程序做为资源分配和管理的对象，就很难描述。当并发执行的是同一个程序的情况下，就说不请在某个时刻处理机分配给了哪个程序使用。在多道系统中，资源的分配不能再以程序为对象，而必须把程序与其执行过程连系操作系统原理学习笔记二 在一起做为对象，这就是引进了进程概念。3、进程的定义和特性?进程是程序
9、在处理机上的执行活动。?进程是一个在处理机上可调度的实体。?进程是一个可以并发执行的计算过程。?进程是由伪处理机执行的一个程序。?进程是程序的一次执行。?进程是多道程序系统中控制程序管理下的基本程序单位。进程的定义：进程是一个具有一定独立功能的程序关于某个数据集合的一次运行活动，它是系统进行资源分配和调度的一个独立单位。进程的两个基本特性：?动态性：进程的实质是程序的一次运行活动，是一个动态的概念。进程是一个有生命的过程，它有从动态地产生、动态地执行到动态地消亡的生命周期。?并发性：系统中可以同时存在多个进程，各进程按照各自独立的、不可预知的速度向前推进。系统中的进程共享系统资源，系统以进程作
10、为资源分配和调度的单位。程序与进程的区别：?程序是一组指令的有序集合，用以指示处理机的操作，其本身并无运行的含义，是一个静止的概念。程序作为一种信息资源可以永久地存放在某种介质上。进程是程序执行的动态活动，它随程序的执行而诞生，随着程序执行结束而消亡。?静止状态的程序和数据是相互独立的信息集合，而进程中的程序和数据是一个不可分离的实体，数据是程序的处理对象。?一个程序可以对应多个进程。在多道系统中一个程序可以同时处理多个不同的数据集合，每个处理活动形成一个进程。使用进程的概念可以很好地描述并发程序的各种特性。进程的概念还能描述和揭示操作系统在实现各种功能时的动态活动情况。操作系统的设计人员基本
11、上都把进程作为构造现代操作系统的基本部件，把进程作为实现操作系统各种功能的基本单位。引进进程的概念后，在多道系统中就不再使用“并发程序”的概念了，而是使用“进程”来描述系统的各种活动。系统在对用户作业的管理和控制中也采用进程的观点，把用户作业看成由若干进程组成。二二二二、进程状态和进程实体进程状态和进程实体进程状态和进程实体进程状态和进程实体 1、进程的状态及转换 在多道系统中，由于多个进程同时动态地活动于系统之中，进程的状态必然处于动态的变化中。进程的状态分为以下三种基本状态：?就绪状态(Ready)。当一个进程获得了除处理机以外的一切所需资源，具备了可在处理机上运行的条件，一旦得到处理机即
12、可运行，则称此进程处于就绪状态。处于就绪状态的进程在逻辑上是处于可运行的状态。?运行状态(Run)。当一个进程获得了处理机及其它所需的一切资源，正在处理机上运行，则称此进程处于运行状态。对于单处理机系统，最多只能有一个进程处于运行状态。?阻塞状态(Blocked)。又称等待状态(Wait)。当一个在处理机上运行的进程，因操作系统原理学习笔记二 等待某一事件发生而不能继续运行时，则称此进程处于阻塞状态。处于阻塞状态的进程在逻辑上是处于不可运行的状态，即使处理机空闲它也不能运行。系统中的每个进程在任何时刻都处于三种基本状态之一。?就绪态-运行态。系统中可能有多个处于就绪状态的进程。当处理机可用时，
13、由系统按照一定的调度算法从就绪态的进程中选择其中一个使其占用处理机运行，则该进程就成为运行态。?运行态-就绪态。处于运行态的进程，当分配给它的时间片用完时，系统剥夺其处理机的使用权，该进程则转换成就绪态。?运行态-阻塞态。进程在运行过程中，有时需等待某一事件发生后，才能继续往下运行。这时，即使时间片未用完也不得不放弃处理机，从运行态变为阻塞态。例如，进程在使用设备输入输出数据时，要等待的事件就是输出输入操作的完成。这时其状态就由运行态转换成阻塞态。?阻塞态-就绪态。处于阻塞态的进程，若其等待的事件已经发生，则该进程从阻塞态变为就绪态。例如，设备为进程完成了输入输出操作后，表明进程等待的事件已经
14、发生，这时该进程需要使用处理机继续执行，则进入就绪态，等待系统把处理机分配给它使用。特别需要注意以下及点：?处于阻塞态的进程，当阻塞原因解除后，虽然再次具备了运行的条件，但不能直接转换成运行态。它必须首先转换成就绪态，经系统调度后才能成为运行态。?进程从运行态转换为就绪态是由系统决定的。当运行态的进程占用处理机的时间片规定的时间已到，则系统停止该进程的运行，使其进入就绪态。?进程从运行态转换成阻塞态是由进程本身提出的。?一个进程由阻塞态转换成就绪态总是由外部事件引起的。2、进程的实体 进程虽然是程序的一次运行活动，但它并不是一个抽象的概念，进程是一个实际存在的实体。进程实体是由程序、数据和进程
15、控制块三部分组成的。从进程的定义可知，进程包括一个具有独立功能的程序和一个数据集合。进程的程序决定了进程所要完成的功能。数据集合是程序在执行时的操作对象，它还包括程序执行时使用的工作区。程序和数据集合是进程存在的物质基础。此外，进程实体还包括一个进程控制块。在计算机系统内部，各个进程的状态和占用资源情况以及进程之间的关系是不断变化的，为了便于对进程进行管理和控制，系统必须记录下进程的这些信息。进程控制块 PCB(Process Control Block)就是记录进程有关信息的一个数据结构。操作系统在创建一个进程的同时就在内存中为该进程建立一个进程控制块，在进程被撤消时，系统回收进程控制块所占
16、用的内存空间，进程控制块也随之消失。所以说进程控制块是系统内进程存在的唯一标志，系统根据进程控制块才感知到进操作系统原理学习笔记二 程的存在。PCB 中所包括信息：?进程的标识信息：包括进程的名字、进程标识符等。每个进程只能有唯一的标识符，它是系统识别一个进程的依据。?进程的位置信息：指出构成进程的程序和数据所在内存中的位置、PCB 在有关队列中的位置等有关信息。?进程的状态信息：记录进程当前所处的状态，它是系统为进程分配处理机的主要依据。?进程的现场信息：当一个进程在运行的中途把处理机让给其它进程使用时，为了在再次占有处理机时能继续运行，必须保存当时的现场信息，如有关寄存器的值、指令计数器、
17、程序状态字等。?进程的管理信息：记录着进程占用资源的情况、进程的优先级、使用处理机的时间等信息。?进程的族亲信息：指向该进程的父进程和它的子进程等有关的指针。?进程的通信信息：给出该进程与其它进程进行通信时的有关信息。?为了便于对进程进行管理，系统把各个进程的 PCB 集中存放在内存的指定区域，并组织在一起形成 PCB 表。不同的操作系统采用不同的 PCB 表组织结构，PCB 表的物理组织结构直接关系到系统的效率。常用的有三种：线性表结构、索引表结构和链接表结构。1、线性表结构 把所有进程的 PCB，不管进程的状态如何全部放在内存中大小固定的一个连续区域中，形成一个线性表。这种结构比较简单，但
18、缺点是每次使用一个 PCB 时，往往要扫描整个 PCB 表。适用于进程数目较少的操作系统。操作系统原理学习笔记二 2、索引表结构 给状态相同进程的 PCB 建立一个索引表，就形成了就绪态索引表、阻塞态索引表 就绪态索引表只有一个。阻塞态则根据引起阻塞事件的不同而形成多个索引表。每个索引表使用一个指针指向处于该阻塞态进程的 PCB 首地址。使用索引表结构可以有效地提高查找 PCB 的速度。由于任何时刻只有一个进程处于运行态，所以直接用一个指针指向它的 PCB 即可。3、链接表结构 把处于各种不同状态的进程链接在一起形成一个个的队列。系统中所有的就绪态进程组成就绪队列。阻塞态进程根据等待事件的不同
19、而排在不同的阻塞队列中，阻塞队列又称等待队列。所以系统中通常存在着多个等待队列。每个队列使用一个头指针指向队列的第一个 PCB。运行态指针直接指向该进程的 PCB。三三三三、进程调度与进程控制进程调度与进程控制进程调度与进程控制进程调度与进程控制 在多道系统中存在着多个并发进程，它们都要使用处理机运行自己的程序，所以处理机成为进程竞争的主要资源。操作系统进程管理的核心任务是为多个进程合理地分配处理机资源，这就是处理机操作系统原理学习笔记二 调度。因为处理机调度是面向进程的，所以又称进程调度。进程调度是指按照一定的调度原则和某种调度算法从就绪队列中选择一个进程，把处理机分配给该进程运行。进程调度
20、又称为低级调度。在操作系统中，完成进程调度功能的程序称为进程调度程序。1、进程调度的功能 由于多个进程需要轮流使用处理机，所以完成处理机分配任务的进程调度是系统中最频繁的工作。引起进程调度：?占用处理机的运行态进程，因等待外部事件而放弃处理机成为阻塞态。?当进程运行的时间片到，系统将处理机分配给就绪队列中另个进程。?进程正常结束、中断处理。进程调度的主要功能是：?当前进程的现场信息记录在它的进程控制块中。?根据一定的调度算法，确定就绪队列中哪一个进程能获得处理机，以及占用多长时间。?回收和分配处理机。当前进程转入适当的状态后，系统回收处理机，然后把处理机分配给下一个进程。2、进程调度性能准则：
21、?处理机利用率 处理机运行时间与系统运行时间之比。尽可能使处理机处于工作状态，使其利用率达到最高。?吞吐量 吞吐量就是系统在单位时间内完成作业的平均数目，衡量处理机的工作负担和工作效率。尽量达到最大的吞吐量。?周转时间 从把作业提给系统计起，到系统完成作业所经过的时间，包括作业等待、在就绪队列中排队、在处理机上运行以及进行输入输出操作所花时间的总和。?等待时间 仅指进程在就绪态下的等待时间。?响应时间 指用户向系统发出请求到系统作出响应所经过的时间。3、进程调度方式 剥夺调度方式剥夺调度方式剥夺调度方式剥夺调度方式。又称可抢占方式。由系统“剥夺”运行态进程对处理机的使用权。当系统中出现更为“紧
22、迫或重要”的进程时，则立即停止正在运行的进程，将其转换为就绪状态，把处理机分配给那个紧迫的进程。运行态进程占用处理机到规定的时间片用完时，系统将中止该进程的运行，将其转换为就绪状态，把处理机分配给下一个进程。剥夺调度方式适用面广，系统并发性强，但设计或控制较复杂。当前的大多数操作系统都采用剥夺调度方式。非剥夺调度方式非剥夺调度方式非剥夺调度方式非剥夺调度方式。又称不可抢占方式。系统不能剥夺进程对处理机的使用权。操作系统原理学习笔记二 系统一旦把处理机分配给某个进程使用后，该进程就一直占用处理机运行下去。只有当该进程运行完毕，或因等待某种外部事件而不能继续运行自动放弃处理机时，系统才能把处理机分
23、配给其它进程。非剥夺调度方式减少了系统进程调度的次数，简化了程序设计，但系统性能较差。早期的计算机系统和当前简单的操作系统和某些批处理系统中采用。调度算法调度算法调度算法调度算法：3.1 先来先服务调度算法(FIFO)又称先进先出算法。按照各进程进入就绪队列的先后顺序调度并分配处理机执行。先进入就绪队列的进程，先分配处理机运行。采用的是非剥夺调度方式。FIFO 算法从表面上看对所有作业都是公平的，并且一个作业的等待时间是可能预先估计的。但当一个长作业排在就绪队列前面时，就会使排在其后的许多短作业等待很长的时间。这种算法不利于短作业，致使短作业的等待时间可能要远远超出它运行的时间。作业号 到达时
24、刻 运行时间 开始时刻 完成时刻 周转时间 等待时间 1 10 28 10 38 28 0 2 10 4 38 42 32 28 3 10 7 42 49 39 32 平均周转时间：33 时间单位 平均等待时间：20 时间单位 先来先服务调度：?算法简单。?易于程序实现。?性能较差。?在实际运行的操作系统中，很少单独使用这种算法，它常常配合其它调度算法一起使用。3.2 优先数法 按某种原则对就绪队列中的每个进程赋予一个优先级别，进程调度时则根据进程的优先级确定选择顺序。把处理机分配给就绪队列中优先级最高的进程。进程的优先级别常用数字表示，又称为进程的优先数。作业号 到达时刻 运行时间 开始时刻
25、 完成时刻 周转时间 等待时间 2 10 4 10 14 4 0 3 10 7 14 21 11 4 1 10 28 21 49 39 11 平均周转时间：18 时间单位 平均等待时间：5 时间单位 优先数算法一般采用剥夺调度方式，通过给紧迫的或重要的进程赋予较高的优先级，操作系统原理学习笔记二 就可以保证它们能够优先占用处理机运行。A.静态优先数法 进程在创建时就赋给它一个优先数，进程在整个生命周期内其优先数不再变化。系统进程高于用户进程。对资源要求少的进程高于要求多的。短作业优先于长作业。静态优先数法主要用于实时操作系统。因为在实时系统中进程的数目、各进程的轻重缓急的程度和运行顺序是预先确
26、定的。B.动态优先数法 给进程赋予某个优先数后，在进程的生命周期内需要根据进程特性的动态变化来修改其优先数。进程的优先数不是一成不变的，而是根据某种原则在动态地变化着。动态优先数修改原则：?已占用处理机的时间 一个进程占用处理机的时间越长，则下次调度时其优先级下降越低，反之则升高。?进程的等待时间。就绪进程等待处理机的积累时间越长，则其优先级升得越高，反之则降低。3.3 时间片轮转法(RR-Round Robin)就绪态进程按照先进先出的顺序排成一个环状结构的就绪队列，给队列中的每个进程分配一个时间片。当一个进程占用处理机运行完个时间片时，调度程序便将其插至就绪队列末尾，重新把处理机分配给队列
27、的下一个进程。如此重复，使就绪队列中的所有进程依次轮流占用处理机运行。时间片轮转法使用的是剥夺调度方式。时间片轮转法常用于分时系统中。时间片轮转法使用的是剥夺调度方式。时间片轮转法常用于分时系统中。选择时间片长度考虑的因素：?系统响应时间。如要求系统的响应时间要快，则时间片要短一些。?用户数目。用户数目多，就绪进程数目相应增多，则时间片就要短。?处理机运行速度。处理机运行速度快，则时间片可以短。在满足用户响应时间的前提下，时间片尽量取大一些，以利于提高系统效率。时间片的长度从几十毫秒到百毫秒。例如。一个分时系统有 20 个终端用户。如果进程的时间片规定为 30 毫秒，那么每个终端用户在 600
28、 毫秒内大约可获得一次处理机时间，则系统响应时间就是 600 毫秒。作业号 到达时刻 运行时间 开始时刻 完成时刻 周转时间 等待时间 1 10 28 10 49 39 11 2 10 4 14 18 8 4 3 10 7 18 29 19 12 平均周转时间：22 时间单位 平均等待时间：09 时间单位 操作系统原理学习笔记二 4、进程控制 进程控制的任务是对系统中全部进程实施有效的管理，通过控制它们状态的变化，使各个进程有条不紊地推进。进程的控制是由操作系统提供的一组系统调用(原语)实现的。用于进程控制的系统调用是直接控制进程状态的，若在执行过程中被其它并发的程序中断将引起系统的混乱。原语
29、(Primitive)：用以完成特定功能的、执行时不可分割的或不可中断的系统调用。4.1 创建进程原语 系统中所有的用户进程和大多数的系统进程是在系统运行过程中动态创建的。个进程可以创建一个新进程。创建新进程的那个进程称为父进程，被创建的新进程称为子进程。子进程在运行中又可去创建它的子进程。这样就形成了一棵进程树。创建进程的主要工作是建立 PCB 和装配进程的实体。创建进程原语主要完成的工作是：?为创建的进程分配 PCB 空间，置 PCB 中的有关域。?装载进程所需执行的程序和数据集合，并将其存储信息保存在 PCB 中。?把进程的启动值等置入 PCB 的现场域，例如，把程序入口地址置入 PCB
30、 现场域中指令计数器 PC 的值。?把新进程加入就绪队列，请求系统进行进程调度。4.2 撤消进程原语 当进程完成了指定的任务而正常结束时，或在运行过程中遇到某些意外事件无法继续运行(如产生错误)而非正常结束时，需要使用撤消进程原语把该进程从系统中撤消。撤消进程原语应由其父进程或祖先进程发出。进程一般不能自己撤消自己。当一个进程被撤消时，该进程的所有子进程以及它们的子孙进程都将被撤消，这样可以避免在系统中残留下一些失去族亲关系的孤立进程，因为这种孤立的进程将很难于管理。撤消进程原语完成的主要工作是：?查找要撤消进程的 PCB；?回收该进程所占的全部资源；?按照进程的树型结构递归地撤消其所有“子孙
31、”进程；?从进程所在的队列中删除其 PCB，回收 PCB 占用的内存区域。?若撤消的是正在运行的进程，则请求系统重新调度。4.3 进程等待原语 当一个进程等待某一事件出现时，该进程就调用等待原语将自己置为阻塞(等待)状态。进程等待原语的功能是：操作系统原理学习笔记二?通过中断使进程让出处理机。?把 CPU 现场送至现场保护区。?进程的状态置为阻塞态，并插入到相应的等待队列中。?请求系统进行进程调度，选择下一个进程进入运行态。4.4 唤醒进程原语 处于阻塞态的进程，当等待的事件发生后，必须唤醒处于等待状态的进程，使其转换成就绪态再次投入运行。阻塞态的等待进程不可能自己唤醒自己，当该进程所等待的事
32、件出现时，由“发现者”进程用唤醒进程原语唤醒它。一般情况下“发现者”进程和被唤醒进程是具有合作关系的并发进程。唤醒进程原语的功能是：?从相应的阻塞队列中查找等待该事件的等待进程。?把该进程从阻塞队列中删除，把它置为就绪态并插入到就绪队列中去。四四四四、进程的互斥与同步进程的互斥与同步进程的互斥与同步进程的互斥与同步 多个并发进程或者共享系统资源，或者合作完成某项任务，它们存在着必然的联系。多道系统中的并发进程并不能完全独立，它们之间存在着相互制约或彼此依赖的关系。这些关系可以归结为两种：同步与互斥。在多道系统中，一个作业能否正确运行，不仅取决于程序算法和程序设计的正确性，而且与各进程运行的相互
33、过程密切相关。当某进程和其它进程并发执行时，能否与其它进程实现正确的同步和互斥是十分重要的。并发进程之间的互斥与同步是关系到系统运行成败的关键问题。1、进程的互斥 并发进程共享系统资源使得它们之间产生了间接制约关系。如果几个并发进程各自按照自己的执行速率，毫无控制地随意共享资源，将导致某种错误产生。例如一台打印机，如果两个进程同时使用它输出数据，打印结果将使这两个进程的输出内容杂乱无章地混杂在一起。系统资源中每次只允许一个进程使用，而不能由多个进程同时共享的资源称为临界资源。“同时”是指资源由一个进程占用后但尚未结束使用的期间，另一个进程也开始了使用。为了保证共享临界资源的各个进程能正确运行，
34、当临界资源由一个进程占用后，其它进程如果要使用它，必须等待占用进程使用完毕并把它释放后，才能由另一个进程使用。多个进程在共享临界资源时的这种制约关系称为进程的互斥。大多数具有独占性的硬件设备都可能成为临界资源。由几个进程共同使用的变量、数据、表格、队列及工作区等也是临界资源。并发进程由于共享临界资源往往会导致某种与时间有关的错误或者说与进程推进速度有关的错误。例如：某机票自动售票系统有两个终端，它们分别运行进程 P1 和 P2，两进程在系操作系统原理学习笔记二 统中并发执行。变量 x 表示现有机票数量。两个进程的功能是首先读 x 的值，若 x 不为0，则把 x 减一，表示一张机票售出，然后把
35、x 的值重新写后它的存储单元中。begin integer x;x:=n;cobegin repeat P1(x);repeat P2(x);coend;end;procedure P1(x)begin read(x);if x=1 then x:=x-1;write(x);end;procedure P2(x)begin read(x);if x=1 then x:=x-1;write(x);end;由于两个并发进程按照各自的速度自主执行，它们占用处理机执行各自程序时，处理机在什么时间执行哪个进程的哪个语句是不能预先确定的，所以它们访问变量 x 的时间也是不可预 知的。假设，在 x 的值是
36、1，即只有一张机票时，两个进程占用处理机执行各自程序的时间顺序可能有以下两种情况：情况 1：终端 1 售出一张机票，而终端 2 已无机票可售。以上运行结果正确。情况 2：一张机票却售给了两个人，显然是错误的。在这种时序下，即使 x 的值 n 时，也会出现 x 被两次减一，其结果却是 n-1。出现这种错误的原因是两个进程同时共享变量 x 造成的。为了避免这种错误的出现，两个进程必须互斥地访问共享变量 x。在某个进程对变量 x 处理过程中，另一个进程如果要访问该变量必须等待前一个进程对 x 处理完毕后，它才能对变量 x 进行处理。操作系统原理学习笔记二 要求在进程的程序中必须把涉及到访问临界资源的
37、代码段从概念上分离出来。在进程的程序中，访问临界资源的哪段代码称为临界区。两个进程不能同时进入访问同一临界资源的临界区，这称为进程互斥。begin shared x:integer;x:=n;cobegin repeat P1(x);repeat P2(x);coend;end;procedure P1(x)region x do begin read(x);if x=1 then x:=x-1;write(x);end;procedure P2(x)region x do begin read(x);if x=1 then x:=x-1;write(x);end;为了使进程的临界区能够互斥地
38、执行，操作系统必须按照一定的准则对进入临界区的进程进行协调。进程互斥的协调准则是：?如果有若干个进程要求同时进入临界区，它们不应互相阻塞致使彼此都不能进入临界区。?每次至多有一个进程处在临界区内。?进程只能在有限时间内逗留在临界区。系统对进程进入临界区的调度原则是：?当一进程要进入临界区时，若没有其它进程在临界区内，则让该进程立即进入。?当已有进程在临界区内时，其它要进入临界区的进程必须等待。?当一个进程离开临界区时，若有其他等待进程，则允许其中之一进入临界区。2、进程的同步“同步”是指两个事件在时间顺序上存在着某种相互关系。进程的同步，则是指系统中有多个进程共同完成一项任务，这些进程之间存在
39、着直接制约关系，每一进程都要依赖于其它进程所产生的结果才能继续运行。这些进程执行过程中必须互相等待，协同动作，互通消息，相互配合。在多道程序系统中，一个作业通常被分为若干个可并发执行的进程，这些进程分别担负着不同的功能。通常，把共同完成一个任务的若干进程称为合作进程。合作进程在并发执行时必须同步推进才能得到正确的执行结果。操作系统原理学习笔记二 合作进程在执行时是相对独立地、异步地向前推进。但是，由于它们在逻辑上或功能上存在的联系而形成的直接制约关系，使得在实际执行过程中，它们不能各自按照自己的执行速度任意推进。合作进程在执行速度上必须相互协调，才能实现功能上的相互配合，最终得到正确的运行结果
40、。对于合作进程而言，它们必须在执行时序上相互协调才能共同完成给定的任务。当前面的一个进程没有完成功能时，后面的一个进程只有等待。合作进程在执行速度上必须要达到“同步”。合作进程在执行时序上的这种协调关系称为进程同步。操作系统进程管理的一个主要功能就是如何协调各进程的执行速度以实现进程的同步。无论进程互斥还是同步，它们都是并发进程在执行时间顺序上相互制约关系的表现。它们之间不同之处主要有以下三点：?互斥的各个进程在各自单独执行时都可以得到正确的运行结果，但是当它们在临界区内交叉执行时就可能出现问题。而同步的各个进程，如果各自单独执行将不会完成作业的特定任务，只要当它们互相配合、共同协调推进时才能
41、得到正确的运行结果。?互斥的进程只要求它们不能同时进入临界区，而至于哪个进程先进入则不会产生运行的错误。但同步的进程的协调关系是建立在它们之间执行时序的基础上，所以，各个进程必须按照严格的先后次序执行。?一般情况下，互斥的进程并不知道对方的存在，而同步的进程不仅知道其它进程的存在，还要通过与其它进程的通信来达到相互的协调。五五五五、P P P P、V V V V 操作操作操作操作 操作系统中实现进程互斥和同步的机制称为进程的同步机制，它由若干条原语组成。在多道系统中，一般都使用 P、V 操作原语实现进程的互斥和同步。1、P、V 操作原语 为了实现进程的互斥和同步，操作系统中引进了信号量(Sem
42、aphore)的概念。信号量具有以下特性：?信号量是一个整形变量。?每一个信号量表示一种系统资源的状况，其值表示该资源当前可用的数量，初值为非零。?每一个信号量都对应一个空或非空的等待队列。该队列就是信号量所代表的资源的等待队列。?对信号量只能实施 P、V 操作，只有 P、V 操作原语才能改变其值。1.1 P 操作原语 procedure P(var s:semaphore)begin s:=s-1;操作系统原理学习笔记二 if s0 then W(s);end w(s)表示将调用 P 操作原语的进程置成等待信号量 s 的状态。进程执行 P 操作时，首先将信号量 s 减 1，其结果若 so，则
43、该进程继续运行；若结果 so，则该进程继续执行。如果 s0 则释放 s 信号量等待队列中队首的进程，解除其阻塞状态。调用 V 操作的当前进程继续执行。P、V 操作的物理意义：?执行 P 操作：s:=s-1 意味着把 s 对应的一个资源分配给调用 P 操作的进程，资源的数量减少一个。若 s 减一后其值为 0，表示此类资源已全部分配给各个进程了。在此之后若又有进程请求该资源，在该进程调用 P 操作时，s 减 1 后成为负值，则执行 W(s)，该进程将转换为阻塞态并进入信号量 s 对应的等待队列中。当信号量 s 为负值时，它的绝对值表示在该信号量等待队列中的进程数目。?执行 V 操作时：s:=s+1
44、 意味着调用 V 操作的进程释放了一个信号量 s 对应的资源。s 加一后，若 s 为负值，表明 s 对应的等待队列中仍有等待该资源的阻塞进程，则调用 R(s)释放等待队列中的一个进程。被释放的进程是在执行 P 操作时因资源不足而进入阻塞态的，由于 V 操作释放了它所需的资源，它就转换为就绪态可以继续执行。P、V 操作是系统提供的原语。它们在执行时绝对不允许被中断。这样才能保证在任一时刻只能有一个进程访问该信号量，即进程对信号量只能互斥地访问。P、V 操作是一对操作。若有对某信号量的 P 操作，必须有对该信号量的 V 操作，反之亦然。这样才能保证资源被合理地分配和释放。2、用 PV 操作实现进程
45、互斥 利用信号量的概念和 P、V 操作可以方便地实现进程的互斥。在实现进程互斥时，信号量的初值设为 1，表示中只允许一个进程进入临界区。在进程执行过程中，当进入临界区时执行 P 操作，在离开临界区时执行 V 操作，使临界区位于对同一个信号量的 P 操作和 V 操作之间。在进程互斥中使用的信号量，每个进程都可以对它实施 P 操作，这样的信号量称为公用信号量。s:semaphore;s:=1;进程 A 进程 B P(s);P(s);临界区 CRA;临界区 CRB;V(s);V(s);操作系统原理学习笔记二 3、用 PV 操作实现进程同步 使用信号量和 PV 操作也可以实现进程的同步。例如，有两个进
46、程 T1 和 T2，T1 进程中有一 m1 语句，T2 中有一 m2 语句。在两个进程并发执行时，要求 T1 执行完 m1 语句后，T2 才能执行 m2 语句。在两个进程循环执行时，执行两个语句的次序总是 m1-m2-m1-m2。就是要求 T1 和 T2 同步运行。设定两个信号量 s1 和 s2，s1 的初值为 1，s2 的初值为 0。s1,s2:semaphore;s1=1,s2=0;cobegin repeat T1;repeat T2;coend;procedure T1:procedure T2:begin begin P(s1);P(s2);m1;m2;V(s2);V(s1);end
47、;end;信号量 s1 只能由 T1 对它实施 P 操作，信号量 s2 只能由 T2 对它实施 P 操作。只能由一个进程对其实施 P 操作的信号量称为该进程的私有信号量。s1 是 T1 的私有信号量，s2 是 T2 的私有信号量。无论是公用信号量还是私有信号量，任何进程都可以对它们实施 V 操作。进程同步中使用的信号量的物理意义：两个私有信号量对应的是一张通行证。操作系统原理学习笔记二 T1 的私有信号量 s1 的初值为 1，表示它得到了通行证，而 T2 私有信号量 s2 的为 0，表示它没有得到通行证。在两个进程相互推进的运行过程中，哪个进程的私有信号量为 1，就表示它持有通行证，就可以向前
48、推进。当 T1 执行在 P(s1)操作的 s1:=s1-1 相当把通行证交给系统，则 s1 为 0。在执行完 m1 后的 V(s2)操作中，把 s2 加 1，相当于把通行证交给了 T2，T2 就可以执行它的 m2 语句了。第一种情况是 T2 要在 T1 之前执行，但它没有通行证(s2=0)，在执行 P(s2)操作时将 s2 的值减为-1，则进入阻塞等待。s2 的值为-1 表示欠一张通行证。等到 T1 执行 m1 后的 V(s2)操作时，由于 s2 是-1，说明 s2 的私有进程在等待通行证，就把 T2 释放，让它执行 m2。T2 执行完 m2 在 V(s1)操作中把 s1 加 1，使 s1 为
49、 1，相当把通行证由交给了 T1。4、生产者消费者问题 生产者进程不断生产产品并把它们放入缓冲区内，消费者进程不断从缓冲区中取走产品进行消费。当缓冲区中产品已经放满时，表示生产速度高于消费而出现了供过于求。这时，生产者进程不能再生产而必须等待产品被消费。当缓冲区取空时，表示消费速度高于生产而出现了供不应求。这时，消费者进程不能再消费而必须等待产品的生产。生产和消费的进程必须达到同步运行，才能使供需平衡。生产者进程的私有信号量为 empty，表示缓冲区中空闲位置的数目，即可以容纳产品的数目。设有限缓冲区最大可容纳 n 个产品，所以 empty 的初值为 n。消费者进程的私有信号量为 full，表
50、示缓冲区内已有产品的数目，其初值为 0。由于两个进程都要访问缓冲区，生产者进程向缓冲区放入产品，和消费者进程从缓冲区取走产品，都不能同时进行。缓冲区是一个临界资源，两个进程访问缓冲区必须互斥地执行。设一个公用信号量 mutex，其初值为 1。mutex,empty,full:semaphore;mutex:=1;empty:=n;full=0;cobegin producer:begin L1:produce a product;P(empty);P(mutex);Add to buffer;V(full);V(mutex);操作系统原理学习笔记二 goto L1;end;consumer:b