教学材料《操作系 统》-3

3.1进程的引入和定义3.1.1程序的顺序执行与特点当用户要求计算机完成某项工作时，必须使用一定的指令，按照一定的步骤编写能在计算机上运行的“程序”。“程序”是指令的集合，它体现了用户要求计算机完成特定功能的执行步骤。在早期的计算机系统中，编制一个程序时，通常是按顺序进行设计的。这个程序运行时，将独占整个计算机系统中的各种软件、硬件资源，其他程序只能等待。我们把一个具有独立功能的程序独占处理机直至得到最终结果的过程称为程序的顺序执行。下一页

返回3.1进程的引入和定义假设有n个用户作业，每个作业都有相应的3个程序段。若用节点代表各程序段的操作：用节点I代表输入，节点P代表计算，节点O代表打印，用箭头指示操作的先后次序，则顺序程序的执行过程如图3-1表示。显然，程序的顺序执行具有下述特征。1．顺序性处理机的操作严格按照程序所规定的顺序执行。一个程序开始执行时必须要等到前一个程序已执行完成。绝对不可能出现在一个程序执行过程中，又夹杂另一个程序执行的现象。上一页

下一页

返回3.1进程的引入和定义2．封闭性程序执行的最终结果由给定的初始条件决定。程序一旦开始执行，其执行结果不受外界因素的影响。任何时候，位于内存中的程序可以使用系统中的一切资源，不可能有其他程序与之竞争。3．可再现性程序执行的最终结果与执行速度无关，只要程序执行时的环境和初始条件相同，无论执行多少次，程序的运算结果都是相同的。程序执行时独占系统中的全部软、硬件资源，资源的使用状态（除了初始状态）只能由程序本身确定。换言之，只有该程序的操作才能改变它，它不受外界因素的影响。上一页

下一页

返回3.1进程的引入和定义3.1.2程序的并发执行及其特点为了提高计算机系统的处理能力和资源的利用率，就应该让多道程序同时在计算机中交替执行。当一道程序不使用CPU时，另一道程序应马上占用CPU，使CPU和各种外设并行工作，这样就可大大提高CPU的利用率。由于通道和中断技术的出现，在计算机系统中引入了多道程序系统，使得多个程序在时间上可以重叠执行，称之为并发执行。采用多道程序后系统资源得到了充分的利用。在内存中可同时驻留多道程序，从宏观上看，多道程序在同时执行，而微观上这几道程序是交替地按顺序执行的，如图3-2所示。上一页

下一页

返回3.1进程的引入和定义对于单CPU系统而言，它们只能轮流地占用CPU。也就是说，程序的并发执行是指一组在逻辑上互相独立的程序在一段时间间隔之内的交替执行。由此可见，程序的并发执行在其执行时间上存在着宏观上的相互重叠。相对单道程序系统而言，并发程序的引入提高了系统资源的利用率，但由于并发进程共享处理机、内存、外设等系统资源，并发进程的执行就产生了与单道环境下的顺序程序执行不同的特点，具体如下。1．程序的封闭性和可再现性不复存在由于多道程序共享系统内的各种资源，使得资源的状态不再受制于一道程序，而是由多道程序的活动共同决定。上一页

下一页

返回3.1进程的引入和定义2．程序之间的相互制约性一组并发程序执行时，虽然它们各白具有相对独立的功能，但由于它们共享系统中的软、硬件资源，同时程序之间相互合作完成一项共同任务，这使得并发程序之间常常相互依赖、相互制约。由此可见，相互制约将导致并发程序具有“执行-暂停-执行”的活动规律，使程序的执行出现了间断性。3．程序与计算不再一一对应程序是指令的有序集合，是静态的概念；而计算是指令序列在CPU上的执行过程，是动态的概念。程序顺序执行时，一个程序只能对应一个计算，程序与计算之间存在着一一对应的关系。上一页

下一页

返回3.1进程的引入和定义而程序并发执行时，一个共享程序可被多个用户作业调用，以使该程序处于多个执行过程中，从而形成了多个计算，显然这时程序与计算已不再一一对应。4．独立性并发程序在执行过程中，既然是一个独立的执行实体，它也就必然作为一个独立的单位去获取资源，否则将无法独立运行。例如，每当某接收程序要接收数据时，必须申请相应数量的缓冲区，只要系统为它分配了所需的缓冲区后，它便可执行接收操作。由于信息的到达是随机的，因此接收进程随时都有申请缓冲区的要求，用完后要立即释放缓冲区。上一页

下一页

返回3.1进程的引入和定义3.1.3进程的定义与特征1．进程的定义多道程序在执行时，需要共享系统资源，从而导致各程序在执行过程中出现相互制约的关系，程序的执行表现出间断性的特征。这些特征都是在程序的执行过程中发生的，是动态的过程，而传统的程序本身是一组指令的集合，是一个静态的概念，无法描述程序在内存中的执行情况，即无法从程序的字面上看出它何时执行，何时停顿，也无法看出它与其他执行程序的关系，因此，程序这个静态概念已不能如实反映程序并发执行过程的特征。为了深刻描述程序动态执行过程的性质，人们引入了“进程(process)”概念。上一页

下一页

返回3.1进程的引入和定义进程这一概念的引入，主要是为描述多道程序并发活动的复杂性。由于进程是一个动态过程，它不像静态的程序那样可以编制和存储。正是因为进程随时处于变化之中，人们强调的侧重点不同，使进程的概念难以统一。比较典型的定义为：进程是并发程序在一个数据集合上的一次执行过程，是系统进行资源分配和调度的一个独立单位。2.进程与程序的区别和联系从进程的定义可以看出，进程与程序有关，而又与程序不同。进程是对程序进一步抽象的描述，进程与程序的区别和联系可以简要描述如下：(1)进程是程序的执行过程，是一个动态的概念；而程序是指令的有序集合，是一个静态的概念。上一页

下一页

返回3.1进程的引入和定义(2)进程是程序的一次执行过程，因而它是有生命周期的，也就是说，进程的存在是暂时的，而程序的存在是永久的。(3)进程具有并发性，可以反映各自的执行过程，而程序则不能。(4)进程的组成包括程序和数据等，而程序仅是指令的有序集合。(5)进程间常常存在相互制约的关系，而程序很难反映各自的制约关系。(6)一个程序可以对应多个进程。(7)一个进程也可以包含多个程序，因为主程序执行时可以调用子程序。上一页

下一页

返回3.1进程的引入和定义3．进程的特征进程具有以下5大特征：1)动态性进程的实质是程序的一次执行过程，因此，动态性是进程最重要的特征。进程由操作系统建立与撤消，具有一定的生命周期。它由“创建”产生，由“调度”执行，因得不到所需资源而暂停执行，最后由“撤消”而死亡。2)并发性在一个系统中，可能同时存在多个进程，这些进程轮流占用CPU和各种系统资源，同时在系统中运行。上一页

下一页

返回3.1进程的引入和定义3)独立性进程是一个能够独立运行的基本单位，同时也是系统进行资源分配和调度的一个独立单位。进程在获得其必需的资源后便可执行，而当系统不能提供它所要求的资源时，它便暂停执行。在具有并发活动的系统中，未建立进程的程序不能作为一个独立单位运行。4)异步性各进程按照各白独立的、不可预知的速度向前推进，为了保证进程之间能协调运行和共享资源，系统必须提供某些设施来协调各进程的推进速度。上一页

下一页

返回3.1进程的引入和定义5)结构性为了描述进程的运行变化过程，并使之能够独立运行，应为每个进程配置一个进程控制块PCB。这样，从结构上看，进程是由程序、数据和进程控制块3部分组成的。上一页

返回3.2进程的状态与转换3.2.1进程的状态进程在其存在的生命周期内，由于并发执行及相互制约，使得它们的状态不断发生变化。例如，一个进程在等待输入／输出完成时不能继续运行；另一种情形是一个进程是可以运行的，但由于操作系统把处理机分配给了别的进程使用，于是它只能处于等待状态。只有当前占用CPU的进程，才是真正处于运行状态。为了描述进程在其生命周期内的变化过程及活动规律，我们采用一组状态来对进程的活动规律进行描述，但由于系统的不同，而又有所区别。一般来说，进程有3种基本状态：就绪状态、运行状态和阻塞状态。下一页

返回3.2进程的状态与转换1．就绪状态(ready)当进程获得除CPU外的一切所需资源，一旦得到CPU即可运行，则称此进程处于就绪状态。这是一种逻辑上的可运行状态。在多道程序系统中，处于就绪状态的进程可能是多个，为了便于管理，一般把它们排成一个队列，称就绪队列。2．运行状态(running)当进程获得了CPU及其他所需资源，正在CPU上运行，则称进程处于运行状态。在单CPU系统中，只有一个进程处于运行状态。在单机处理系统中，某一时刻，只有一个进程处于运行状态；在多机系统中，有多个进程同时处于运行状态。上一页

下一页

返回3.2进程的状态与转换3．阻塞状态(blocked)阻塞状态又称等待状态。正在运行的进程，因等待某一事件而暂时不能运行，它在等待某一事件的发生，则称此进程处于阻塞状态。这时即使CPU空闲，也会因为阻塞尚未消除而不能运行，所以称之为逻辑上的不可运行状态。处于阻塞状态的进程按不同的阻塞原因形成多个阻塞队列。3.2.2进程状态的转换进程在其生命周期内并非处于某个状态不变，而是随着白身的推进和外界条件的不断变化而相应地变化，从而使其从一种状态转变成另一种状态。上一页

下一页

返回3.2进程的状态与转换3种基本状态的转换可用图3-3表示。对于进程的状态转换过程应注意以下3点：

(1)一个进程从阻塞状态到运行状态必须经过就绪状态，而不能直接转换到运行状态。因为当某进程解除阻塞时，系统中可能有多个进程都处于就绪状态，这时系统必须根据一定的算法，选择一个就绪进程占用CPU(由进程调度完成)。

(2)一个进程由阻塞状态变为就绪状态总是由外界事件引起的，而不是由该进程自己引起的。

(3)一个进程由运行状态转换为阻塞状态，一般是由运行进程自己提出的。上一页

下一页

返回3.2进程的状态与转换进程之间由于存在同步、资源竞争、相互制约等关系，因此导致了各进程在其生命周期内存在状态的变化。以上3种状态是最基本的状态，但在实际操作系统中，往往不只这3种基本状态。不同的系统，处于对调度策略的考虑，有时把进程的状态做进一步的细化，如在不少系统中又加入了新建和终止这两种状态，如图3-4所示。(1)新建状态：当一个新进程刚刚建立，还未将其放入就绪队列时的状态，称为新建状态。操作系统在新建状态为新的用户进程分配资源，一旦新建进程进入就绪队列，它便从新建状态转变为就绪状态。上一页

下一页

返回3.2进程的状态与转换(2)终止状态：当一个进程已经正常结束或异常结束，操作系统已将其从系统队列中移出，但尚未撤消，这时称为终止状态。一般操作系统要在此状态收集一些数据或信息，如了解该进程用了多少CPU时间，使用了哪些资源等，以便记录。上一页

返回3.3进程的描述3.3.1进程的组成进程由程序、数据和进程控制块3部分组成：

(1)程序：主要用于描述进程所要完成的功能，是进程所依附的实体。

(2)数据：包括程序执行时所需要的数据和工作区。该部分只能为一个进程专用，是进程可修改的部分。数据和程序是进程完成所需功能的基础。

(3)进程控制块(PCB)：记录了进程的描述信息和控制信息，是进程动态特性的集中反映。进程控制块是进程存在的唯一标志，系统通过检测PCB的存在而感知进程的存在。下一页

返回3.3进程的描述3.3.2进程控制块为了对进程实现有效地管理和控制，当系统创建进程时，为每一个进程设置了一个进程控制块(processcontrolblock，PCB)。当进程被撤消时，系统收回其PCB。因此，系统对PCB的管理体现了对进程的管理。所以有必要了解进程控制块所包含的内容，但根据操作系统的不同，PCB所包含的内容也会有所不同。1．PCB的基本内容PCB的基本内容如下：(1)进程标识符：这是在系统内部用于标识进程的一个整数，也称为进程内部名称。上一页

下一页

返回3.3进程的描述对于不同的进程不能使用相同的标识符。在创建一个进程时，由系统为它分配一个唯一的内部标识符。进程在系统内部有唯一的标识符，同时系统为了对进程进行管理，在系统外部也有其外部用户标识符，说明进程的隶属关系。用户标识符一般由字母和数字组成。(2)位置信息：即存储指针，用于指出进程的程序和数据在内存或外存上的地址，把PCB与其程序和数据联系起来。(3)当前状态：说明进程所处的状态，如运行、就绪或阻塞状态等。它是系统调度进程的依据之一。若进程处于阻塞状态，则应在PCB中说明阻塞的原因。上一页

下一页

返回3.3进程的描述(4)进程的优先级：标志进程要求CPU的优先级别，可由用户提供或系统设置。它也是系统调度进程的依据之一。(5)现场保护区：当进程在执行过程中由于某一事件发生而放弃CPU时，需要将CPU的现场（如指令计数器、状态寄存器等）内容保存到此区，以便此进程再次获得CPU时恢复使用。(6)占用资源清单：列出进程所需资源及当前已分配到的资源。(7)队列指针：为了对PCB进行管理，一般将处于同一状态的进程链接在一个队列，其队首指针和各PCB的链接指针记录于此。上一页

下一页

返回3.3进程的描述(8)互斥与同步机构：实现进程间的互斥与同步时所必需的机构，如信号量机构等。(9)家族关系：系统中的进程通常具有创建另一进程的功能。创建进程的进程称为父进程，被创建的进程称为子进程。PCB应记录本进程与其家族成员间的关系。2．PCB的组织方式在多道程序设计环境中同时会创建多个进程。当计算机系统只有一个CPU时，每次只能让一个进程运行，其他进程处于就绪状态或阻塞状态。为了对这些进程进行管理，操作系统要做两件事：上一页

下一页

返回3.3进程的描述(1)把处于相同状态的进程的PCB，通过各白的队列指针连在一起，形成一个个队列。(2)为每个队列设置一个头指针，它总是指向排在队列之首的进程的PCB。排在队尾进程的PCB，其队列指针的内容应该为一个特殊的符号．以表示这是该队的队尾。在单CPU系统中，任何时刻系统中都只有一个进程处于运行状态，运行队列中只能有一个PCB存在；一般地，系统中所有处于就绪状态的进程的PCB排成一队，称为“就绪队列”。就绪队列中会有多个进程的PCB排在里面，它们形成处理机分配的候选对象。如果就绪队列中没有PCB存在，则称该队列为空；所有处于阻塞状态进程的PCB，应该根据阻塞的原因进行排队，每一个都称为一个“阻塞队列”。上一页

下一页

返回3.3进程的描述为了对进程进行合理地组织和管理，系统中的所有PCB应该按一定方式组织起来。目前一般常用的有以下两种组织方式：(1)线性表方式：不管进程的状态，将所有PCB连续存放在内存中。这种方式最简单，适用于系统中进程数目不多的情况。它的缺点是调度进程时往往要查找整张表。它的改进方式是将相同状态的PCB组织在同一张表格中（如就绪表和阻塞表），表中的每一单元分别指出各个PCB的起始地址。PCB线性表结构如图3-5所示。上一页

下一页

返回3.3进程的描述(2)链接表方式：将处于相同状态的PCB组成队列，如运行队列、就绪队列和阻塞队列。这种方式在每个PCB中增加一个链指针表项，以指示队列中下一个PCB起始地址。系统还需设置固定单元以指出各队列的头，即队列中第一个PCB的起始地址。PCB链接表结构如图3-6所示。就绪队列的排队原则与调度策略有关；阻塞队列可以有多个，以对应不同的阻塞原因。系统还可以把目前没有使用的PCB构成一个空闲队列。这种组织PCB的方式便于管理，利于动态分配内存，灵活方便。上一页

返回3.4进程的调度3.4.1进程控制原语1．原语进程控制是进程管理的重要组成部分。进程控制就是系统使用一些具有特定功能的程序段来创建、撤消进程以及完成进程各状态间的转换，从而使多个进程能够并发执行、实现系统资源共享、提高运行效率和资源利用率。进程在其生命周期内都是由操作系统来控制的。操作系统是由一系列具有特定功能的、能够独立运行的程序组成的。组成操作系统的程序和普通程序的最大区别在于：前者比普通程序具有更高的权限，可以访问所有寄存器和存储区，是被称为系统调用或者原语的程序。下一页

返回3.4进程的调度原语(primitive)是由若干条指令构成的，用于完成特定功能的一段程序，它是机器指令的延伸。因为进程控制是操作系统中最基本、最重要的内容，必须保证绝对的正确，所以进程控制操作都是进程控制原语。原语具有不可分割性，即原语在执行期间不响应中断或不能和其他程序并发执行。为了保证原语的不可分割性，可以通过两种方法来实现：软件硬化的方法，即将一个原语硬化为一条机器指令；屏蔽中断的方法，即在原语执行前屏蔽中断，原语操作完成后开放中断。现代操作系统多采用后一种方法。2．进程控制原语操作系统中用于进程控制的原语一般有：创建原语、撤消原语、阻塞原语和唤醒原语。上一页

下一页

返回3.4进程的调度1)创建原语(createprimitive)进程的创建是由创建原语来实现的。创建者称为父进程，被建立的进程称为子进程，子进程又可以创建它的子进程。所有进程自己不能产生，只能由父进程建立。创建一个进程有两种方法：一是由操作系统建立；二是由其他进程创建。创建的进程一般有两类，即系统进程和用户进程。系统进程一经创建，便与系统共存亡，不能被撤消且常驻内存；它们在进程调度程序的统一调度下，为用户服务。用户进程是动态地产生和消亡的，在进入系统时产生，在退出系统时消亡。上一页

下一页

返回3.4进程的调度创建一个进程的主要工作是为被创建进程申请建立一个PCB，并填入相应的初始值。因此，调用创建原语的进程必须提供PCB中的相关参数，包括PCB的内部标识符、进程的初始状态、优先级数、内存存放的起始地址、资源清单等，以便填入其中。当PCB的各项参数配置完成后，将新进程的现行状态置为“就绪”，并将其插入就绪队列和进程的家族队列中。进程具体的创建过程如图3-7所示。2)撤消原语(destroyprimitive)当一个进程完成其任务后或由于某些错误异常结束后，应予以撤消，以便释放其所占用的资源给其他进程。撤消原语一般由其父进程或祖先进程发出，进程自己不会撤消白己。上一页

下一页

返回3.4进程的调度当撤消一个进程时，该进程连同其子孙进程一并撤消。首先，根据该进程的外部标识符查找进程控制块PCB和内部标识符，并且必须明确进程所处的运行状态。然后根据被撤消进程所处的状态，决定不同的执行步骤。若被撤消进程处于执行状态，应立即停止其执行，且撤消其全部子进程，释放其占用的所有资源。当被撤消进程从处理器退出后，为了提高CPU的利用率，应由进程调度程序从就绪队列中选择一新的进程投入运行。若被撤消进程不处于执行状态，则将其从相应队列中移除，并将其占用的全部资源释放。撤消进程的具体步骤如图3-8所示。上一页

下一页

返回3.4进程的调度3)阻塞原语(blockprimitive)正在CPU上运行的进程，由于等待某一事件的到来（如从键盘输入数据、写盘、等待某进程发来数据等），在该事件尚未发生时，调用阻塞原语阻塞自己，实现从运行状态到阻塞状态的转换。其具体操作过程是：由进程的外部标识符查找进程的PCB并获取该进程的内部标识符，然后停止现行进程的运行，保存CPU的现场信息，将进程转入阻塞状态，并将阻塞进程插入等待相应事件的阻塞队列中。具体操作过程如图3-9所示。上一页

下一页

返回3.4进程的调度4)唤醒原语(wakeupprimitive)处于阻塞状态的进程，当其所等待的事件发生后，由唤醒原语将其由阻塞状态转为就绪状态。但是，阻塞进程不能自己唤醒自己，它是由“发现者”——进程调用唤醒原语来唤醒的。唤醒进程的操作过程是：由进程的外部标识符查找进程的PCB并获取该进程的内部标识符，将该进程从阻塞队列中移出，并将其置为就绪状态，插入相应的就绪队列中，等待调度程序的调度。唤醒进程的过程如图3-10所示。3.4.2进程调度1．进程调度的功能上一页

下一页

返回3.4进程的调度在多道程序系统中，有多个进程同时存在。多个进程共享处理机资源势必会引起进程竞争使用处理机，那么如何把处理机有效地分配给多个处于就绪状态的进程，并使之顺利地执行呢？这就是进程调度所要解决的问题。进程调度性能的好坏，将直接影响到处理机的利用率和系统的性能。因而，进程调度便成为操作系统设计的中心问题之一。进程调度的主要任务是实现进程由就绪状态到执行状态的转变。要完成进程调度，系统要随时了解每一个进程的情况，如进程状态、优先级和所用资源等，这些信息都记录在每个进程的PCB中。上一页

下一页

返回3.4进程的调度进程调度的主要功能如下：(1)记录系统中各个进程的情况，并将相关信息填入PCB中的相应表项，根据表项中的内容和状态做出选择。(2)根据系统确定的调度算法，决定把处理机分配给就绪队列的哪一个进程，并决定分配多长时间。当有更高优先权的进程进入就绪队列时，是停止现行进程的运行，还是在就绪状态继续等待，由进程的调度方式决定。(3)执行实际的CPU分配工作，更新被调度进程和正在运行进程的PCB表项，修改其进程状态，保存当前运行进程的CPU现场，并将其插入相应的等待队列。将被调度进程的CPU现场建立或者恢复，使其转入运行状态，进程调度程序将CPU的控制权移交给运行进程。上一页

下一页

返回3.4进程的调度2．进程调度的基本概念1)进程调度的层次一般来说，操作系统对处理机的调度可分为以下3级：(1)高级调度（又称为作业调度或长程调度）。它按照一定的原则和策略从外存后备队列中选择一个或多个作业进入内存，并为选中的作业分配必要的资源；同时创建相应的作业进程，并将该作业进程插入就绪队列中，以使该作业的进程获得竞争处理机的权利。高级调度的工作频率一般在秒或分时间量级，而对调度算法的要求不太高。它解决的主要问题一是接纳多少个作业；二是接纳哪些作业。上一页

下一页

返回3.4进程的调度(2)低级调度（又称为微观调度或短程调度）。它的主要功能是按照某种方式和策略从就绪队列中选取一个就绪状态的进程以占用处理机，使之处于执行状态。执行进程调度功能的程序称为进程调度程序，由它实现处理机在多个进程间的转换。低级调度的工作频率一般在毫秒时间量级，对调度算法的要求非常高，因为算法的好坏直接影响到系统的整体效率。它要解决的问题是：①What:按什么原则分配CPU-调度的算法。②When:何时分配CPU-调度的时机。③How:如何分配CPU-CPU的调度过程。上一页

下一页

返回3.4进程的调度(3)中级调度（又称为交换调度或中程调度）。它主要是为了提高内存的利用率，往往在带有虚拟存储的系统中增加该调度。其主要作用是在内存和外存对换区之间进行进程交换，以解决内存紧张问题。即它将内存中处于阻塞状态的某些进程调至外存对换区，以腾出内存空间，而将外存对换区中已具备运行条件的进程重新调入内存，准备执行。一个进程在运行期间可能要多次调进、调出。中级调度的工作频率一般在不小于秒时间量级，对调度算法的要求相对高些。高级调度、中级调度与进程调度相互配合，实现作业的并发执行。上一页

下一页

返回3.4进程的调度3．进程调度方式所谓进程调度方式，是指一个进程占用CPU后，若有更高优先权的进程进入就绪队列时其分配CPU的方式。一般来说有以下两种调度方式：1)剥夺式进程调度（又称为抢占式进程调度）当一个进程正在CPU上运行时，系统可根据某种原则，将其占用的CPU剥夺，分配给其他进程。剥夺的主要原则有：有更高优先级的进程进入就绪队列时，就中止现行进程的运行，将CPU分配给更高优先级的进程；短进程可以剥夺长进程的CPU的运行；时间片用完后交出CPU重新调度以确定将CPU分配给哪个进程。上一页

下一页

返回3.4进程的调度剥夺式进程调度方式灵活，在实时系统中，能保证实时信息得到及时的处理；在分时系统中，能保证用户获得可接受的响应时间。调度的基本原则是：当有更高优先级的进程要求使用CPU时，应该依据某种算法决定是否让该进程获取CPU来执行，具体的算法随操作系统的不同而不同。2)非剥夺式进程调度该方式规定，进程调度程序一旦把处理机分配给某进程后，便让它一直执行下去，直到该进程完成或发生某事件（如I/O请求）而阻塞时，才把处理机分配给其他进程。这种调度方式的优点是简单，系统开销小，但有可能导致系统性能的恶化，使紧急任务或短进程不能及时执行，而且这种方式不太灵活，系统效率较低。上一页

下一页

返回3.4进程的调度4．进程调度的时机进程调度发生在什么时机与引起进程调度的原因及进程调度方式有关。大体有以下几种：

(1)正在执行的进程执行完毕或出现异常情况。

(2)执行中的进程因提出I/O请求而暂停执行。

(3)在进程通信或同步过程中执行了某种原语操作，如P操作、阻塞原语等，使进程由运行状态变为阻塞状态。

(4)执行中的进程自己调用挂起原语将自己挂起。

(5)在时间片轮转法中，时间片用完。

(6)在剥夺式进程调度中，有一个比当前进程优先级更高的进程进入就绪队列。上一页

下一页

返回3.4进程的调度3.4.3进程调度算法进程调度算法的选择是否合理，将直接决定进程调度性能的优劣，它是一种服务于系统目标的策略。在设计时总希望达到最理想的目标，但在实际的操作系统中，调度算法往往需要折中考虑。一般地，在设计进程调度算法时应考虑以下几点：

(1)调度算法应与设计目标一致。

(2)注意系统资源的均衡使用。

(3)保证提交的作业在截止时间内完成。

(4)缩短作业的平均周转时间。上一页

下一页

返回3.4进程的调度对于不同的系统及系统目标，应采用不同的调度算法。例如，在批处理系统中，若希望得到大的吞吐量，通常采用短进程优先的进程调度算法；在分时系统中，则应保证每一个终端都具有合理的响应时间，宜采用轮转法；在实时系统中，为保证其及时性的特点，应采用优先级调度算法。1．先来先服务调度算法先来先服务(firstcomefirstserve，FCFS)调度算法是最简单的调度算法，其基本思想是把处理机分配给最先进入就绪队列的进程。也就是说，就绪队列是按进程进入的先后次序排队，调度时，选择就绪队列中的队首进程投入执行。该算法属于非剥夺式调度，简单、易于实现，但服务质量欠佳，忽视了紧急进程或者短进程对处理机的要求。上一页

下一页

返回3.4进程的调度2．短进程优先调度算法短进程优先(shortestprocessfirst，SPF)调度算法又称为短作业优先(shortestjobfirst，SJF)，调度算法与作业调度的短作业优先调度算法类似，是从就绪队列中选择“下一个CPU执行周期”最短的进程，为其分配处理机使之执行。该调度算法虽然可获得较好的调度性能，但实现难度较大，因为要准确预测下一个进程的CPU执行周期是很困难的。3．静态优先权调度算法优先权是在系统创建进程时即被确定的，该优先权在进程生存期内不再改变，这种优先权法称为静态优先权法。上一页

下一页

返回3.4进程的调度确定进程优先权的主要依据有：

(1)进程类型。进程可分为系统进程和用户进程，通常系统进程的优先级要高于用户进程的优先级，特别是在某些系统中的某些进程，必须赋予它一种特权，不管它何时需要处理机，都要尽快得到满足。

(2)进程对资源的需求。如估计执行时间、内存需要量、I/O设备的数量等。

(3)用户要求的优先级。根据用户作业的优先级，确定该作业所对应的进程优先级。静态优先权调度算法简单易行，但不精确，因为确定优先级所依据的特性会随进程的推进而改变。另外，该算法可能会使有些进程长期得不到处理机而处于等待状态。上一页

下一页

返回3.4进程的调度4．动态优先级调度算法动态优先级是指进程在执行期间，优先级一般随进程的等待时间、占用CPU的时间的长短而变化。一般来说，可根据以下原则来确定优先级的变化：(1)根据进程占用CPU时间的长短来确定。一个进程占用CPU的时间越长，则它被阻塞之后再次获得调度的优先级越低，反之就越大。这样做可防止一个长作业长期垄断处理机。(2)根据进程等待处理机时间的长短来决定。一个进程等待的时间越长，它的优先级就越大。动态优先级调度算法虽可获得良好的调度性能，但需要系统计算更新进程的动态优先级，增加了系统的开销。上一页

下一页

返回3.4进程的调度5．轮转法轮转法(roundrobin，RR)是指系统将所有就绪进程按先来后到的顺序排成一个队列，给队列中的每一个进程分配一个时间片。调度程序把CPU分配给队首进程，但其运行时间不能超过分配给它的时间片，如果时间片用完了，系统会产生一个时间中断，中止该进程的执行，将它送至就绪队列的末尾等待下一次调度，并把处理机分配给就绪队列的下一个进程，同样也让它执行一个时间片。这样，依次轮流地调度就绪队列中的各个进程，让每一个进程都可获得分配处理机的机会。上一页

下一页

返回3.4进程的调度6．多级反馈轮转法该调度算法结合了优先级调度算法与轮转法。它在系统中设置多个就绪队列，并赋予各队列不同的优先级和时间片，每个就绪队列中的优先级相同则按先来先服务原则排队。进程调度时，先在优先级最高的队列中轮转调度进程执行，仅当队列为空时，才轮转调度次优先级队列中的进程执行，以此类推。如果处理机正在服务第1级队列中的进程，又有新的就绪进程进入相应的就绪队列（当某一进程由阻塞状态被唤醒成为就绪状态时，应根据其现行的优先级决定新的就绪队列）时，将引起重新调度，把处理机分配给优先级高的队列中的进程。上一页

返回3.5进程间的通信3.5.1进程通信的概念为了提高计算机系统的资源利用率和作业的处理速度，一个作业通常被分为若干个可以并发执行的进程。这些进程是异步的、相对独立的向前推进的。但由于它们是协同地完成一个指定的任务，所以它们应该保持联系。这种联系是指在并发执行的进程之间交换一定数量的信息，我们把这种联系称为进程通信。进程通信有以下几种方式。1．共享存储区这种通信方式在存储区中划出一块共享的区域，进程间可通过对共享存储区中的数据进行读写来实现通信。进程在通信前应向系统申请共享存储区的一个分区，并指定该分区的关键字。下一页

返回3.5进程间的通信若系统已经给其他进程分配了该分区，则将该分区分给申请者，申请者把获得的共享存储分区连接到本进程上，便可像读写普通存储器一样读写共享存储分区，以便实现进程的通信。2．邮件邮件机制实质上是一种间接通信方式，发送进程把信息放入邮箱中，接收进程从邮箱中获取信息。其实现机制如下：

(1)信箱。如果用户在公共的电子邮局中分配了一个邮箱，那么用户就在电子邮局的目录下获得了一个信箱文件。每个用户用信箱存放收到的电子邮件，并且邮件的接收者有权对信箱的内容进行处理。上一页

下一页

返回3.5进程间的通信(2)邮件格式。电子邮件的格式由邮件主题、收件人姓名、发件人姓名（默认为编写者）、邮件的大小、邮件附件等组成。

(3)邮件的发送。用户通过发送进程，将处于发送区中的邮件取出，送到接收进程的信箱中，同时激活通知进程，告知接收用户邮件已到来。

(4)通知进程。当接收用户打开邮箱时，信箱提醒用户有“新邮件”。

(5)邮件接收。邮件一旦存入接收用户的邮箱中，接收用户就可使用新邮件，并有权对邮件进行相应的处理。上一页

下一页

返回3.5进程间的通信3．共享文件这种通信方式是利用共享文件来实现进程间的通信，如图3-11所示。该共享文件称为管道，因而这种通信方式又称为管道通信。在这种方式中，以文件作为两个进程间的通信媒体，一个进程向其写入信息，另一个进程从中读取信息，就好像是一个管道，信息从一头流进，从另一头流出。信息是以字符流的形式写入和读出的，可以进行大批量的信息交换，其工作是以先进先出为顺序的单向通信方式。为了协调双方进程的通信，管道通信机制必须提供以下3个方面的协调能力：(1)当一个进程正在对管道进行读或写操作时，另一个进程必须等待。上一页

下一页

返回3.5进程间的通信(2)当写（输入）进程把数据写入管道后便阻塞等待，直到读（输出）进程取走数据后才将其唤醒。当读进程读空管道时也将阻塞等待，直到写进程将消息写入管道后，再将其唤醒。(3)确认对方是否存在。只有在进程双方都存在时，才可进行通信。3.5.2进程的互斥与同步在多道程序系统中，各个进程共享系统中的各种软硬件资源，而且各个进程也可以相互合作完成一项任务，这就使得进程之间产生了相互制约的关系。这些制约关系可以分为以下两种类型：上一页

下一页

返回3.5进程间的通信1．进程的互斥进程之间互相竞争某一个资源，这种关系就称为进程的互斥；或者说把多个进程不能同时使用同一临界资源，只能一个进程使用完后另一进程才能使用的这种现象称为进程的互斥。在多道程序系统中，各进程可以共享各类资源，但由于资源的类型不同，导致资源的分配方式也有所区别。共享资源可供多个进程共享使用；对于独享型资源（如打印机、输入机、某些变量、表格、队列等），只能是一个进程使用完后，另一进程才能使用。因此，操作系统必须能够识别这类资源，并采取相应的分配措施。为此，引入以下概念。上一页

下一页

返回3.5进程间的通信1)临界资源把一次只允许一个进程使用的资源，或者说不能同时共享的资源称为临界资源，如打印机、输入机和共享变量等。2)临界区把每个进程中访问临界资源的程序段代码称为临界区。为了实现对临界资源的互斥访问，就应该保证各进程互斥地进入自己的临界区。为此，每个进程在进入临界区之前，必须先提出申请，经允许后方可进入。用户在编写程序时，并不能确定程序是否是临界区，对临界区的判定是由操作系统进行的。上一页

下一页

返回3.5进程间的通信当操作系统发现某段程序使用系统的临界资源时，就将该程序段确定为临界区，并在临界区的开始和结束处做相应的处理，以使该进程处于临界区，而其他进程不能进入。3)临界区的使用原则为保证各进程互斥地进入临界区，必须用软件方法或同步机制来加以协调。协调准则如下：

(1)当有若干个进程申请进入临界区时，必须让其中的一个进程立即进入且最多只能是一个进程，以便有效地使用临界资源。

(2)当有多个进程申请进入临界区时，在有限时间内只有一个进程占据临界区。上一页

下一页

返回3.5进程间的通信(3)为保证每个进程都能及时地进入临界区，每个进入临界区的进程只能在临界区内停留有限的时间。遵循以上协调准则，可以得到临界区的调用原则如下：

(1)当无进程占据临界区时，允许一个进程立即进入。

(2)已有进程在临界区时，其他试图进入临界区的进程必须等待。

(3)当进程退出临界区时，若有等待进入临界区的进程，则允许其中的一个立即进入。上一页

下一页

返回3.5进程间的通信4)互斥的加锁实现用加锁／开锁实现进程互斥操作是一种最简单的方法。当某个进程进入临界区之后，该进程锁上临界区，直到它退出临界区为止。并发进程在申请进入临界区时，若测试该临界区已上锁，则该进程进入阻塞状态，直到临界区开锁之后再将其唤醒。可采用一元变量S代表某个资源的使用情况：S=0表示该资源可用；S=1表示该资源正在被使用。并发进程可通过测试该变量的值来决定进程是否进入临界区。上一页

下一页

返回3.5进程间的通信利用加锁／开锁原语可以很方便地实现进程互斥。当某并发进程要进入临界区时，首先执行lock(S)原语，判断临界区中有无进程。这时若S=0，表示无进程进入临界区，它可以立即进入，同时将S置为1（关锁），禁止其他进程进入；若S=1，表示此时已有进程正在临界区中，它只能循环测试等待，当一个进程使用完临界区并退出时，执行unlock(S)原语，将S置为0，即开锁。虽然加锁／开锁原语简单方便地实现了进程的互斥，但效率非常低。因为当S=l时，等待进入临界区的进程将不断测试S，以等待S变为0，这就造成了CPU时间上的浪费。上一页

下一页

返回3.5进程间的通信一种改进的方法是：每当进程不能进入临界区时，不再以循环测试S的方法来等待，而是将该进程置为阻塞状态，插入S的等待队列WL中，并把CPU分配给别的进程；当进程退出临界区时，除了将S置为0（开锁）之外，还应检查S的等待队列WL是否为空，若不为空则表示有进程等待进入临界区，此时从WL(S)的等待队列中唤醒一个进程，并将该进程置为就绪状态插入就绪队列RL中。2．进程的同步在多道程序系统中，各并发进程之间存在着间接制约关系和直接制约关系。由间接制约关系我们引出了进程互斥的概念，并对临界资源的使用采取了相应的措施。上一页

下一页

返回3.5进程间的通信但是，并发进程之间也存在着合作关系，一组合作的并发进程以各白独立的速度向前推进，而各自的执行结果又互为对方的执行条件，从而限制了各进程的执行速度，例如前面介绍的读进程和写进程共享同一个单缓冲区。这样，如果没有相应的制约措施，进程的这种直接制约会造成CPU时间的大量浪费。一种简单可行的解决方法是：直接制约的进程相互给对方进程发送执行条件已经具备的信号。这样，被制约的进程可以省去对执行条件的测试。只要收到了制约进程发来的信号便可开始执行，而在未收到制约进程发来的信号前，进入阻塞状态。上一页

下一页

返回3.5进程间的通信我们把进程之间的这种协调关系称为进程的同步。也就是说，进程同步是指某些合作进程在执行过程中需要在执行进度上彼此协调，以完成相关的操作。其实，互斥关系也是一种协调关系，从广义上讲，互斥可看成是一种特殊的同步。3.5.3进程互斥与同步的实现1．信号量与P、V操作1)信号量在操作系统中，为了控制进程的互斥与同步，引入了信号量机制。信号量是由一对设计严格的程序原语，即P、V操作原语来实现的。上一页

下一页

返回3.5进程间的通信我们可以把信号量定义为：信号量是一个记录型的数据结构，用以协调并发进程之间的运行顺序，它仅能由P、V操作来改变。它由两个数据项，即整型变量V和指针变量S构成。前者是信号量的值，为一个整型量；后者是一个指针变量，指向在此信号量上等待的进程队列的队首。当信号量的取值大于或等于零时，代表可供并发进程使用的资源实体数；当信号量的值小于零时，则其绝对值代表系统中因等待使用该资源而阻塞的进程数。显然，用于进程互斥的信号量的初值应该大于零。上一页

下一页

返回3.5进程间的通信2)P、V操作P、V操作是定义在信号量机构上的两种操作，且它们在操作中的每一步都是不可分的，即P、V操作应是原语。P、V操作的物理意义是：

(1)执行一次P操作，意味着向系统请求分配一个单位的资源；

(2)执行一次V操作，意味着向系统释放一个单位的资源。由此可以得出P、V操作的主要动作。（假设s是在临界区内使用的与临界资源有关的信号量。）上一页

下一页

返回3.5进程间的通信P操作原语的主要动作如下：

(1)s-1。

(2)若s-1≥0，表明进程已申请到一个单位的资源，则该进程继续执行。

(3)若s<0，表明进程未申请到资源，则该进程被阻塞后插入该信号量的等待队列中，然后转到进程调度程序，选择另一进程占用CPU。V操作原语的主要动作如下：

(1)s+1。

(2)若s+1>0，表明此时系统中无进程因等待该资源而被阻塞，进程继续执行。上一页

下一页

返回3.5进程间的通信(3)若s+l≤0，表明此时系统中有进程因等待该资源而阻塞，此时从该信号量的等待队列中唤醒一个阻塞进程，然后再返回原进程继续执行或转入进程调度程序。可见使用P、V操作，信号量的入口值非常重要，它关系着进程是否进入等待状态，或者是否被唤醒。2．利用信号量实现进程互斥利用P、V原语和信号量，可以很方便地解决N个并发进程的互斥问题。设有两个进程互斥使用临界资源，为了协调进程的执行顺序，用公用信号量“S”代表该临界资源，其初值为1，表示尚无进程进入临界区。由上面几节的讨论可知，只需把临界区CS置于P(S)和V(S)之间，便可实现进程对临界资源的互斥使用。上一页

下一页

返回3.5进程间的通信当一个进程需要进入临界区时，必须先执行P操作原语，将信号量S减1。在一个进程完成对临界区的操作之后，必须执行V操作以释放所占用的临界区。由于信号量的初值为1，所以，当一个进程在执行P操作之后，S的值变为0，表示该进程可以进入临界区。在该进程未执行V操作之前，如果有另一个进程想进入临界区时，它也要先执行P操作。从而使S的值变为-1，因此，第二个进程被阻塞，直到第一个进程完成对临界区的操作。执行V操作之后，S的值变为0，从而唤醒第二个进程进入就绪队列，等待进程调度后再进入临界区。在第二个进程执行完V操作原语操作之后，如果没有其他进程申请进入临界区，则S又恢复到初值1。也就是说，P(S)表示进程提出进入临界区的请求，而V(S)表示进程已经退出临界区。上一页

下一页

返回3.5进程间的通信3．利用信号量实现进程的同步利用信号量同样能够很好地解决并发进程间的同步问题。从写进程与读进程同步的算法描述中可以看出，对于信号量sbuf，只有写进程才能对它进行P操作，而对于信号量sdata，也只有读进程才能对它进行P操作。我们把sbuf称为写进程的私有信号量，sdata称为读进程的私有信号量。其他进程只能对某进程的私有信号量进行V操作。相应地，我们把用于互斥的信号量称为公用信号量。需要注意的是，在使用P、V操作实现进程同步的同时，需要特别注意P操作的顺序，否则容易造成死锁；而V操作是释放资源的，因此，它的顺序无关紧要。上一页

返回3.6死锁在多道程序系统中，由于多个并发进程共享系统的资源，如使用不当，有可能造成一种僵局，即系统中两个或多个进程无限期地等待永远不会发生的条件，在无外力的干预下，这些进程都不能向前推进，我们称之为死锁。死锁会影响到系统的安全。3.6.1死锁产生的原因和必要条件1．死锁产生的原因死锁产生的原因有以下两点：

(1)系统资源不足。由于多个进程所共享的资源数量不足，可能造成对资源的竞争而产生死锁。

(2)进程推进顺序不恰当。下一页

返回3.6死锁2．死锁产生的必要条件死锁产生的必要条件有以下4点：

(1)互斥控制。进程对所要求的资源进行排它控制，在一段时间内一个资源仅能被一个进程使用。

(2)不可剥夺控制。进程对所获得的资源在未释放前，不能被其他进程剥夺。只有该进程释放资源后，别的进程才能使用。

(3)请求和保持。为了提高资源利用率，进程在运行过程中可随时提出对各种资源的请求，当进程因请求资源而阻塞时，对已获得的资源保持不放。上一页

下一页

返回3.6死锁(4)循环等待条件。在发生死锁时，进程所占有的资源必构成循环，即前一进程保持着后一进程所要求的资源。死锁产生的4个必要条件不是彼此孤立的，如条件(4)包括了前3个条件。研究它们可以得出防止死锁的各种方法。3.6.2死锁的预防与避免解决死锁一般采用两种方法：一种是设计无死锁的系统；另一种是允许系统出现死锁，然后排除它。设计无死锁的系统通常有两种途径，一种是死锁预防，另一种是死锁避免。如果允许系统出现死锁，则应有死锁的检测手段和解除手段。上一页

下一页

返回3.6死锁1．死锁的预防所谓死锁预防，就是在进程运行之前，预先防止死锁产生，这主要是通过破坏产生死锁的4个必要条件中的任一个来实现的。由于资源本身所具有的性质，要想破坏第(1)、(2)个条件是很困难的，甚至是不可能的。常用的死锁预防方法有以下几种：(1)资源的静态分配方法。即系统在进程运行之前，一次性地满足进程所要求的全部资源。进程在运行过程中只能释放资源而不能申请资源。由于资源是一次性全部分配，因此获得资源的进程不会进入等待状态。上一页

下一页

返回3.6死锁这种方法简单安全，但资源利用率较低，即使有的资源只在进程运行后期才使用，甚至于有的资源在正常运行中根本不使用，也要事先统一申请。(2)资源的顺序分配法。其基本思想是对系统的全部资源进行顺序编号，只允许进程按编号递增的次序申请。这样可破坏死锁的必要条件之一，即循环等待条件。但会给用户编制程序带来不必要的麻烦。(3)一个已占有资源的进程若要申请新的资源时，必须先释放已占有的资源，再次使用时，要重新申请。这样可破坏产生死锁的请求和保持必要条件。上一页

下一页

返回3.6死锁该策略要付出一定的代价，如一个进程放弃它所占有的资源，可能会丢失有关信息，需要重新申请资源时予以弥补，这样就增加了程序执行的时间；另外在极端情况下，可能出现进程重复申请／释放某资源的抖动现象，浪费系统资源并降低系统性能。2．死锁的避免死锁的避免，不是预先采取各种限制措施去破坏产生死锁的必要条件，而是在进程的执行过程中，对资源的动态分配采用某种限制方法，如管理程序对提出资源申请的进程进行核查，根据某种算法决定是否将资源分配给有申请要求的进程。上一页

下一页

返回3.6死锁其主要目的是知道将资源分配给申请进程后，在以后的运行时间里会不会产生死锁，产生死锁，则拒绝分配，否则分配。1)单项银行家算法可以把一个系统比做一个银行家，占用有限资金。银行家不可能满足所有借款人（进程）的最大需求总和，但可以满足一部分借款人的借款需求。待这些人的借款归还后，又可把这笔资金借给其他人。这样，当一个借款人提出借款要求时，银行家就要进行计算，以决定是否借给他，看他是否会造成银行家的资金被借光而使资金无法周转。上一页

下一页

返回3.6死锁2)多种资源银行家算法系统中往往不止一种资源，现在考虑多种资源银行家算法。假设系统有4类资源，分别用A、B、C、D表示，各类资源的总数用向量T=(6，3，4，2)表示。现有5个进程Pl、P2、P3、P4、P5，已获得资源的种类接数量用矩阵R表示，如表3-2所示。尚需资源的种类和数量用矩阵Q表示，如表3-3所示。向量P=(5，3，2，2)表示已分配的资源数，它是矩阵R各列相加的结果；向量S=(1，0，2，0)是向量T与向量P之差，即S=T-P，表示现在还剩一个A资源和两个C资源。上一页

下一页

返回3.6死锁现在给出多种资源银行家算法，具体如下：

(1)如果某一进程对某一资源提出请求，就假定先分配给它，然后修改矩阵R、矩阵Q和向量S。

(2)在矩阵Q中找出一行，使该行向量小于等于S。若不存在这样的向量，就说明没有进程能够获得全部资源运行到结束，很显然这会引起死锁。

(3)若被选到的那一行的进程获得了全部资源而运行结束，则设置该进程“能运行结束”标志，并把它的资源全部加入向量S中。(4)重复(2)和(3)，若所有进程都设置了“能运行结束”标志，则系统是安全的，可以进行实际分配；反之，就会发生死锁，则预先分配是不安全的，应予以撤消。上一页

下一页

返回3.6死锁36.3死锁的解除一旦发生了死锁后，系统不但要能检测出来，还应能采取相应的解除死锁的措施。目前，常采用的解除死锁的方法有两种：一种为删除法，即删除某些死锁进程而将其资源分配给其他死锁进程，直到其死锁解除为止；另一种为剥夺法