操作系统第二章进程的描述与控制.ppt

第二章,进程的描述与控制,进程是操作系统最重要，最基本的概念之一，这个概念对操作系统的理解，描述和设计都具有极其重要的意义。,本章讨论的主要问题,1、什么是进程？为什么要引入进程？ 2、如何描述进程？ 3、进程具哪些状态？这些状态之间如何进行转换？ 4、如何控制进程状态的转换？,2.1 程序的执行与特征 (一）,一 、程序的顺序执行及特征,如：有三条语句： s1： a：=x+y s2： b：=a-5 s3： c：=b+1,程序顺序执行的特征 ：,执行顺序用有向图表示:,s1,s2,s3,1.顺序性: 处理机操作严格按照程序所规定的顺序执行。,2.封闭性： 程序独占资源，除初始状态外，只有程序本身规定的操作才能够改变资源状况，即程序在封闭环境下运行。,3.可再现性: 程序的运行结果与它执行的速度无关。,一个具有独立功能的程序独占CPU直到完成的过程称为程序的顺序执行。,2.1 程序的执行与特征 （二）,1. 前趋图 （Precedence Graph） 用前趋图来描述并发执行的程序的特征。 前趋图 DAG（Directed Acyclic Graph） 结 点表示一条语句，一段程序或进程。 有向边表示两结点间的偏序或前趋关系。 前趋定义： （Pi , Pj) 记为： Pi Pj,二、 程序的并发执行及特征,其中： Pi 称为Pj的直接前趋。,2. 程序的并发执行,程序的并发执行是指在逻辑上相互独立的一组程序在执行时间上的相互重叠，即一个程序段的执行尚未结束，另一程序段的执行已经开始。,Pi,Pj,2、程序的并发执行,例：有三类程序并发执行： Ii输入程序 Ci计算程序 Pi打印程序,I1,I2,I3,I4,C1,C2,C3,C4,P1,P2,P3,P4,Ii Ci Pi,Ii Ci Ci Pi,前趋关系：,P i -1，Ci ，I i +1 可并发执行。,2.1 程序的执行与特征 （三）,Ii I i+1,Ci Ci+1,Pi Pi+1,问 题 程序的顺序执行与程序的并发执行有那些不同的特征？,2.1 程序的执行与特征 （四）,执行过程中可能有多个程序同时申请同一资源，带来了资源的动态分配。多道程序共享资源共同决定和影响资源的状态。因此，并发程序的执行结果与其执行的相对速度有关。,(1) 并发执行的程序间相互约束，相互依赖,显然，程序的并发执行与程序的顺序执行具有完全不同的特征，主要表现在：,各并发执行的程序共享资源，使本来并无逻辑关系的程序之间产生了相互制约的关系。而需要相互通信共同协作完成同一任务的程序之间相互依赖又相互制约。使各道程序走走停停，动态执行。,(2) 对系统资源争夺与共享,3、程序并发执行的特征,程序顺序执行 程序并发执行 顺序性 间断性 封闭性 无封闭性 可再现性 不可再现性,2.1 程序的执行与特征 （五）,不可再现性是程序并发执行时的间断性及失去封闭性的必然结果，即程序的执行结果与其执行速度有关。 例： 程序A 程序B . . . . N :=N+1 PRINT(N) . N :=0 . . . .,3、程序并发执行的特征,（1）执行顺序：（a），（b），（c） N值：n+1，n+1，0 （2）执行顺序：（b），（a），（c） N值： n，n+1， 0 （3）执行顺序：（b），（c），（a） N值： n， 0， 1,（a）,（b）,（c）,2.2 进程的描述 （一）,本节讨论关于进程的基本概念：,进程的定义 进程的特征 进程的状态 进程控制块,2019/11/5,10,装入模块,装入,内 存,装入程序,链接,装入,链接,运行,编译,2019/11/5,11,链接由链接程序将目标模块及其所需的库函数，装配 链接生成装入模块的过程。,一。程序的装入和链接,指令的执行 执行指令的基本过程分为两步，即: 从内存把指令读入的过程和执行的过程。 其中，读指令是根据程序计数器PC所指的地址读入，而执行的指令则是指令寄存器IR中的指令。 我们把指令的读入和执行过程称为一个执行周期。 图 指令的执行周期,图 计算机的基本硬件元素,图 控制器基本组成框图,14,进程是可并发执行的程序在给定数据集合上的一次执行过程，是系统进行资源分配和调度的一个独立的基本单位和实体，是执行一个映象程序的总环境，是一个动态的概念。,一.进程的定义 进程的引入是为了更好地描述程序并发执行的动态特征。,1.定义,2.2 进程的描述 （二）,进程是执行程序的动态过程动态概念。 程序是进程运行的静态文本静态概念。,2.2 进程的描述 （三）,一个进程可以执行一个或多个程序。 一个程序可以被多个进程执行。,程序可以作为一种资源以文件的形式长期保存。 进程只是一次执行过程，具有生命期。,2. 进程与程序的区别、联系,2.2 进程的描述 （四）,进程是程序的一次执行过程,具有生命期；它可以由系统创建并独立地执行，直至完成而被撤消。,进程是可以并发执行的基本单位，从宏观上看，它们可以“同时”执行。由于共享资源，进程间相互约束，相互依赖。,动态性,并发性,独立性,异步性,各个进程之间相互独立，是系统分配资源和能够被处理机调度的基本单位。,各个进程按照各自独立的、不可预知的速度异步向前推进。即进程按异步方式执行。,二.、进程的特征,2.2 进程的描述 （五）,1、 三种基本状态： 执行状态 （Executing） 就绪状态 （Ready） 阻塞状态 （Blocked）或等待（Wait）,阻塞 状态,就绪 状态,执行,状态,调度,I/O请求,进程,释放,时间 片到,新状态,结束,后备队列,新状态 结束状态,三、进程的基本状态,2、进程状态的细化,挂起状态（Suspend）： 对正在执行的进程，则停止执行。 对就绪状态的进程，则停止调度，并回收资源。 对阻塞状态的进程，则停止条件的发生。,称被挂起的进程是静止的 ,静止就绪（Readys）,静止阻塞（Blockeds）,称未被挂起的进程是活动的,活动就绪（Readya）,活动阻塞（Blockeda）,将进程挂起的原因： 1。系统工作负荷达到高峰，调整负荷，使系统正常运行。 2。人为挂起，停止某进程执行，以便研究分析。 3。系统需要，如系统故障，系统检测需要。,2.2 进程的描述 （六）,3、细化的进程状态图,活动 阻塞,执行 状态,活动 就绪,静止 就绪,静止 阻塞,调度,释放,I/O请求,激活,激活,挂起,挂起,挂起,释放,2.2 进程的描述 （七）,2.2 进程的描述 （八）,1、进程的描述 对进程的描述应该反映进程的存在及其变化，反映进程的动态特性。进程由程序，相应的数据集合，进程控制块三部分组成。,进程的程序 静态文本，描述进程所要完成的功能。 数 据 集 合 程序运行时所需的数据和工作区。,静态描述,动态描述,进程控制块PCB（Process Control Block）记录和描述进程的动态特性，描述进程的执行情况和状态变化。,四、进程控制块,2.2 进程的描述 （九）,进程标识信息 外部标识信息 内部标识信息 进程家族标识,处理机状态信息 通用寄存器 指令计数器 程序状态字（PSW）用户栈指针,进程调度信息 进程状态 进程优先级 其他调度信息 等待事件,进程控制信息 程序数据地址 进程同步及通信 资源清单 链接指针,2、PCB 块包含的信息,不同操作系统，PCB所包含的信息类型及数量可能有所不同，但一般包括两类信息。,1）调度信息 描述进程的当前状况，供进程调度使用。,2）现场信息 刻划了进程运行的情况；记录在进程运行过程中会改变的信息，以便进程中断后，再次被调度时能够继续运行。,PCB 块是一个进程存在的唯一标志 ，当系统创建一个进程时，为该进程设置一个 PCB，再利用PCB对进程进行控制和管理。当进程撤消时，系统回收它的PCB。,3、 PCB块的组织方式,链接方式 链接成各种就绪，阻塞及空白等各种队列。 索引方式 建立不同状态的索引表。,2.2 进程的描述 （十）,进程队列及其管理,处于同一状态的所有PCB链接在一起的数据结构称为进程队列。 同一状态进程的PCB既可按先来先到的原则排成队列;也可按优先数或其它原则排成队列。 通用队列组织方式： 线性方式、 链接方式 索引方式。,进程队列及其管理,PCB表,运行队列指针,就绪队列指针,等待队列1指针,等待队列2指针,空闲进程队列指针,链接方式,运行队列指针,就绪表指针,等待表1指针,索引方式,PCB表,PCB1,PCB2,PCB3,PCB4,PCB5,PCB6,PCBn,空闲表指针,等待索引表1,等待表2指针,2.3 进程控制 （一）,操作系统中，为了防止用户进程对OS及PCB等关键信息的破坏。 一个进程在其生命期中有两种机器运行状态： 系统态 （核心态,管态） 具有较高的访问权，可访 问核心模块。 用户态 （目态 ） 限制访问权。, 是机器指令的延伸，是非进程模块,不能并发执行。 执行过程不可中断，用微代码实现。,2、原 语（primitive）,一、操作系统的内核,1、进程运行状态,处理器,单处理器和多处理器系统 共享存储(紧密耦合)多处理机系统和分布存储(松散耦合)多处理机系统。,处理器状态,处理器怎么知道当前是操作系统还是一般用户程序在运行呢? 处理器状态标志: 管理状态（特权状态、系统模式、特态或管态）和用户状态（目标状态、用户模式、常态或目态)。处理器状态的转换。 处理器处于管理状态时，程序可以执行全部指令，使用所有资源，具有改变处理器状态的能力；处理器处于用户状态时，程序只能执行非特权指令 Intel Pentium的处理器状态有四种，支持4个保护级别，0级权限最高，3级权限最低,特权指令与非特权指令,机器指令的集合称指令系统 (1)数据处理类指令； (2)转移类指令； (3)数据传送类指令； (4)移位与字符串指令； (5)I/O类指令。,微程序控制指令,30,特权指令与非特权指令,从资源管理和控制程序执行的角度出发，必须把指令系统中的指令分作两部分：特权指令和非特权指令。 特权指令是指只能提供给操作系统的核心程序使用的指令，如启动I/O设备、设置时钟、控制中断屏蔽位、清主存、建立存储键，加载PSW等。,寄存器,计算机系统的处理器包括一组寄存器，其个数根据机型的不同而不同，它们构成了一级存储，比主存容量小 ，但访问速度快。 这组寄存器所存储的信息与程序的执行有很大关系，构成了处理器现场。,与操作系统相关的几种主要寄存器 寄存器与操作系统密切相关，因为它们是在处理机中交换数据的速度比内存更快、体积也更小，而价格又更贵的暂存器件。 处理机中寄存器的功能分为二类，即用户可编程的寄存器以及控制与状态寄存器。 机器语言或汇编语言的程序员可对用户可编程寄存器进行操作，以获得更高的执行效率等。 控制与状态寄存器则被用来对处理机的优先级、保护模式或用户程序执行时的调用关系等进行控制和操作。 一般来说，用户可编程寄存器和控制与状态寄存器之间没有严格的区分和限制，在不同的系统中，寄存器的功能和作用可能不完全相同。,典型的用户可编程寄存器包括以下几种： 1. 数据寄存器 编程人员可以通过程序赋予数据寄存器众多的功能。一般来说，对数据进行操作的任何机器指令都被允许访问数据寄存器。不过，根据硬件设置的规定，这些寄存器也可能只被允许进行浮点运算或被其他某些规定所限制。 2. 地址寄存器 地址寄存器一般用来存放内存中某个数据或指令的地址，或者存放某段数据与指令的入口地址以及被用来进行更复杂的地址计算。下面几种寄存器都可被认为是地址寄存器：,(1） 地址标识位寄存器； (2） 内存管理用各种始地址寄存器； (3） 堆栈指针； (4） 设备地址寄存器等。 3. 条件码寄存器 条件码寄存器也称标志寄存器。条件码寄存器的比特位由处理机硬件设置。 典型的控制与状态寄存器包括以下几种： 4. 程序计数器PC 程序计数器内装有下一周期被执行指令的地址。 5. 指令寄存器IR 指令寄存器内装有待执行指令。,6. 程序状态字PSW 程序状态字寄存器的各个比特位代表系统中当前的各种不同状态与信息。如执行模式是否允许中断等。 7. 中断现场保护寄存器 如果系统允许不同类型的中断存在，则会设置一组中断现场保护寄存器以便保存被中断程序的现场和链接中断恢复处。 8. 过程调用用堆栈 堆栈被用来存放过程调用时的调用名、调用参数、以及返回地址等。 寄存器被广泛应用于计算机系统中，它们与操作系统有着非常直接和密切的关系。操作系统设计人员只有在完全掌握和了解硬件厂商所提供的各种寄存器的功能和接口之后，才能进行操作系统设计。,程序状态字寄存器,计算机如何知道当前处于何种工作状态？这时能否执行特权指令？通常操作系统都引入程序状态字PSW（Program Status Word）来区别不同的处理器工作状态 PSW用来控制指令执行顺序并保留和指示与程序有关的系统状态，主要作用是实现程序状态的保护和恢复 每个程序都有一个与其执行相关的PSW，每个处理器都设置一个PSW寄存器。程序占有处理器执行，它的PSW将占有PSW寄存器,程序状态字寄存器,PSW寄存器包括以下内容： 程序基本状态： (1) 程序计数器； (2) 条件码； (3）处理器状态位。 中断码。保存程序执行时当前发生的中断事件。 中断屏蔽位。指明程序执行中发生中断事件时，是否响应出现的中断事件。,2.3 进程控制 （二）,内核是OS的控制和协调中心，由它组织，启动和协调系统中各种活动。通常由各种原语构成。,操作系统内核,内核是OS中最重要最核心的部分。OS的内核紧靠硬件，由那些使用频率高，与硬件紧密相关的模块构成；如中断处理程序，设备驱动程序等。,2.3 进程控制 （三）,二.内核的功能 1）中断处理 中断是OS内核最重要的功能之一。系统中的所有中断 都由内核响应。中断是进程并发执行的基础， OS是由中断驱动的。,2）原语操作 原语操作包括涉及CPU管理，存储管理，设备管理，文件管理的各种基本操作。,3) 时钟管理 OS的许多重要操作，如：按时间片轮转调度，实时系统中的截止时间控制等，都依赖于时钟管理。,2.3 进程控制 （四）,中 断 源 引起中断的异步事件（如：系统调用，I/ O 请求，进程调度， 设备驱动，文件处理等）。 中断请求 向CPU发出中断信号。 中断响应 CPU停止执行当前进程，分辨中断请求的类型。 中断处理 CPU将请求交相关的中断处理程序处理。 中断返回 众多处理结束，返回断点。,内核对中断的有限处理方式,中断源,中断请求,中断响应,转中断 处理程序,退出中断,向CPU,保护CPU现场 识别中断源,恢复CPU现场,2.3 进程控制 （五）,创建原语 create（）,撤消原语 destroy（）,阻塞原语 block（）,唤醒原语 wakeup（）,挂起原语 suspend（）,激活原语 active（）,三 . 进程控制原语,2.3 进程控制 （四）,创建进程有两种方式：由系统程序模块创建，或由父进程创建。,算法步骤： 1. 向PCB集合申请一个空闲的PCB，并获取其内部标识； 2. 将有关信息填入PCB； 3. 将该进程置为就绪状态，并插入就绪队列。,创建原语 create（）,对进程的控制一般通过原语操作实现。,创建原语 (create),创 建 原 语 算 法,查PCB集,有空PCB,N,创建失败,Y,取空表PCB（i）,将参数填入PCB（i）,将PCB（i）插入就绪队列,2.3 进程控制 （四）,算法步骤： 1. 根据外部标识检索PCB集，找到要撤消的PCB； 2. 从队列中撤消该进程 及其子孙进程，通常在一个递归过程中实现； 3. 释放被撤消进程所占有的资源，撤消进程控制块。,撤消原语 destroy（）,当进程完成或产生异常中断时，应立即撤消，并释放其所有资源。,撤消原语 (destroy）,撤 消 原 语 算 法,查PCB集和进程家族,有此PCB？,N,出错处理,Y,释放进程所占资源,释放PCB（i）结构,该PCB有子进程？,Y,N,2.3 进程控制 （五）,进程在执行过程中，需要等待某些条件发生时，由该进程调用阻塞原语把进程从执行状态转换为阻塞状态。,算法步骤： 中断CPU执行，将CPU的当前状态保存到PCB的现场信息。 2. 将进程的当前状态置为阻塞状态； 3. 将进程的PCB插入到该事件的阻塞队列中。,阻塞原语 block（）,2.3 进程控制 （五）,算法步骤： 1. 在等待队列中找到该进程，将其P的当前状态置为就绪； 2. 将进程从等待队列中撤消，并插入到就绪队列中。,唤醒原语 wakeup（）,当处于阻塞状态的进程所等待的事件发生后，使用唤醒原语将进程从等待状态转换为就绪状态。,2.3 进程控制 （六）,进程在执行过程中，根据用户或系统的某种需要，调用挂起原语将进程从活动状态转换为静止状态。,算法步骤： 1. 根据外部标识检索PCB集，找到要挂起的PCB块； 2. 检查被挂进程的当前状态： 执 行 态 静止就绪，并转调度程序，重新调度。 活动就绪 静止就绪 活动阻塞 静止阻塞,挂起原语 suspend（）,2.3 进程控制 （六）,算法步骤： 1. 检查被挂进程的当前状态： 2. 将进程从相应的静止状态 活动状态。,激活原语 active（）,当外于静止状态的进程所等待的激活事件发生后，使用激活原语将进程从静止状态转换为活动状态。,一. UNIX系统的核心结构 UNIX系统分为三个层次：核心、用户接口及实用程序、应用程序。,2.4 UNIX系统中的进程（一）,UNIX核心 ： 包括四大资源管理功能。由以下部分组成：,1、进程控制子系统 负责处理机管理和存储管理，包括进程控制、进程通信、进程调度及段页式存储管理。,2、文件子系统 将慢速外设备看作广义的文件。文件子系统功能包括：文件管理、高速缓冲机制及设备驱动。,3、两个接口 核心与硬件的接口 （一组驱动程序，基本例程） 核心与SHELL的接口（系统调用，命令解释程序）,2.4 UNIX系统中的进程（二）,3。两个接口 核心与硬件的接口 （一组驱动程序，基本例程） 核心与SHELL的接口 （系统调用，命令解释程序）,文件子系统,进程控制子系统,系统调用接口,硬 件,硬件控制,用户程序,核心级,用户级,硬件级,2.4 UNIX系统中的进程（三）,PCB 块数据结构,1。进程表项（PROC结构）：核心数据。 2。U区（USER结构） ： PROC的扩充数据。 3。系统区表项 ：段在物理存储器的位置等信息。 4。本进程区表 ：本段起始虚地址，指向系统区表中 的本进程区表项的指针。,2.4 UNIX系统中的进程（四）,进程的唯一标识。 拥有该进程的用户标识。 记录该进程的当前状态（九种）。 记录使该进程进入睡眠状态的事件。 进程及U区在内存或外存的位置。 记录其它进程发来的软中断信号。 进程执行时间及对资源的利用情况。 用于内存分配。 设置进程动态优先级。 指向U区进程正文、数据及栈在内存区域的指针。,1. 进程表项（PROC结构） 包括进程最常用的基本控制信息，常驻内存。,进程标识符PID 用户标识符UID 进程状态 事件描述符 进程及U区位置 软中断信号 计时域 进程大小 偏置值 指向U区内存区域 的指针,二、 PCB 块的数据结构,2.4 UNIX系统中的进程（五）,指向当前执行进程的进程表项。 （real user ID）由超级用户分配的户标 识符，用于用户登录验证。 （effective user ID）一般同上，可由系 统调用改变。 记录该进程已打开的所有文件。 记录当前根及当前目录。 对进程大小及读、写文件字节数，方式 及缓冲区大小等的限制。 记录进程（及其子进程）在核心态和用户态执行所用时间。 记录系统调用过程中的错误。 标识出该user 结构所对应的 proc结构。,USER结构所包含的信息只有在进程运行时才使用，不一定调入内存。,2、U区（USER结构）,进程表项指针 真正用户标识符 URUID 有效用户标识符 UEUID 文件描述表 文件运行环境 限制字段 计时器 出错字段 指向U区内存区域 的指针,2.4 UNIX系统中的进程（六）,UNIX系统中采用段页式储存管理，为了把虚地址映射到实际的物理地址，定义了两个表：进程区表，系统区表。 储存管理是进程并发执行的基础，因此，PCB中也定义了有关储存管理的字段： 3。系统区表项 4。本进程区表,三、进程的上、下文 进程是一个进程映象（Process Image）的执行过程，各进程并发执行，OS经常需要把控制从一个现行执行的进程转换到另一个进程，这个操作称为“关联转换”，或“上、下文转换”（context）。,进程上、下文是对进程执行活动全过程的描述。进程上、下文包括： 寄存器上、下文， 系统级上、下文， 用户级上、下文。,2.4 UNIX系统中的进程（七）,存放进程在运行过程中所产生的数据。 如R0、R1 用于系统进程与用户进程间传递参数。 存放CPU正常执行的下一条指令的虚地址。 包括当前进程的访