第三章 进程管理(1)

1第三章进程管理概述进程的描述进程控制进程互斥和同步（重点）进程间通信死锁问题（难点）进程其他方面的举例线程为了描述程序在并发执行时对系统资源的共享，我们需要一个描述程序执行时动态特征的概念，这就是进程。本章将讨论进程概念、进程控制和进程间关系。本章内容3.1.1程序的顺序执行和并发执行程序的执行有两种方式：顺序执行和并发执行。顺序执行是单道批处理系统的执行方式，也用于简单的单片机系统现在的操作系统多为并发执行，具有许多新的特征。引入并发执行的目的是为了提高资源利用率3.1概述3.1.1程序的顺序执行和并发执行1.程序的顺序执行程序：完成所要求的功能时,所应采取的顺序步骤，是执行指令的有序集合。程序的顺序执行：具有独立功能的程序独占CPU直至得到最终结果的过程3.1概述3.1.1程序的顺序执行和并发执行1.程序的顺序执行顺序执行的特征顺序性：按照程序结构所指定的次序（可能有分支或循环）封闭性：独占全部资源，计算机的状态只由于该程序的控制逻辑所决定可再现性：初始条件相同则结果相同。3.1概述3.1.1程序的顺序执行和并发执行2.程序的并发执行程序并发执行的目的：提高计算机的处理能力提高资源利用率分为两种形式：多道程序环境下的多道程序的并发执行在某道程序的几个程序段中，包含可同时执行或可颠倒顺序执行的代码。3.1概述3.1.1程序的顺序执行和并发执行2.程序的并发执行定义：程序的并发执行是指一组在逻辑上互相独立的程序或程序段在执行时间上客观上互相重叠，即一个程序或程序段的执行尚未结束，另一个程序（段）的执行已经开始的执行方式。并发：在一段时间内的同时并行并行：在同一物理时刻的同时3.1概述请求带输入3.1.1程序的顺序执行和并发执行2.程序的并发执行时间tCPU外设CPU外设启动带磁带输入结束中断中断处理请求磁盘输入启动盘结束中断中断处理请求盘输入启动盘调度B请求带输入启动带结束中断中断处理调度A结束中断中断处理调度B用户程序监督程序磁盘设备磁带设备用户程序A用户程序B监督程序磁盘设备磁带设备3.1概述3.1.1程序的顺序执行和并发执行2.程序的并发执行并发执行的特征间断(异步)性：“走走停停”，一个程序可能走到中途停下来，失去原有的时序关系；失去封闭性：共享资源，受其他程序的控制逻辑的影响。如：一个程序写到存储器中的数据可能被另一个程序修改，失去原有的不变特征;失去可再现性：失去封闭性－失去可再现性；外界环境在程序的两次执行期间发生变化，失去原有的可重复特征。3.1概述3.1.1程序的顺序执行和并发执行2.程序的并发执行不加控制的并发执行所带来的影响例：利用堆栈管理一块内存区中各数据块的使用情况。用getaddr(top)从栈顶取出相应的内存块的地址。用reladdr(blk)将数据块的地址（以bkl为地址）放入堆栈中。3.1概述3.1.1程序的顺序执行和并发执行2.程序的并发执行procgetaddr(top)Beginlocalr;1.1rs[top];1.2toptop+1;1.3return(r);end;Procreladdr(blk)Begin2.1toptop-1;2.2s[top]blk;End;分析getaddr(top)与reladdr(blk)的并发执行012345t……abtop2.1toptop-11.1rs[top]1.2toptop+11.3return(r)2.2s[top]blktopblktop什么原因？说明什么问题？3.1概述3.1.1程序的顺序执行和并发执行2.程序的并发执行例子的说明getaddr()和reladdr()的并发执行，产生了错误的结果，不同执行顺序得到不同的结果，程序的执行不再具有封闭性和结果的可再现性。原因：对公共变量（堆栈或堆栈指针）的共享引起的。为了获得结果的可再现性，程序的并发执行是需要条件的。3.1概述3.1.1程序的顺序执行和并发执行2.程序的并发执行并发执行的条件：达到封闭性和可再现性并发执行失去封闭性的原因是共享资源的影响，去掉这种影响就行了。1966年，由Bernstein给出并发执行的条件。（这里没有考虑执行速度的影响。）。程序P(i)针对的读变量集和写变量集为R(i)和W(i)。任意两个程序P(i)和P(j)可并发的条件：R(i)W(j)=，andW(i)R(j)=,and保证一个程序的两次读之间数据不变化W(i)W(j)=保证写的结果不丢掉现在的问题是这个条件不好检查。怎么办？3.1概述3.1.2进程的定义一个具有一定独立功能的程序在一个数据集合上的一次动态执行过程。简言之，进程是程序的一次执行活动。进程描述了程序的动态执行过程；它对应虚拟处理机、虚拟存储器和虚拟外设等资源的分配和回收；反映系统中程序执行的并发性、随机性和资源共享引入多进程，提高了对硬件资源的利用率，但又带来额外的空间和时间开销，增加了OS的复杂性3.1概述3.1.2进程的定义1.进程的特征动态性：进程对应程序的执行进程是动态产生：创建--〉运行--〉消亡进程在其生命周期内，在三种基本状态之间转换独立性：各进程的地址空间相互独立，除非采用进程间通信手段并发性：任何进程都可以同其他进程一起向前推进异步性：每个进程都以其相对独立的不可预知的速度向前推进结构化：进程=代码段+数据段+PCB3.1概述3.1.2进程的定义2.进程与程序的区别进程是动态的，程序是静态的：炒菜菜谱进程是暂时的，程序的永久的：进程是一个状态变化的过程，程序可长久保存。进程与程序的组成不同：进程的组成包括程序、数据和进程控制块（即进程状态信息）。进程与程序的对应关系：通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序。进程具有并发/并行特征，程序没有。进程具有独立性和异步性进程是竞争计算机资源的基本单位。3.1概述3.1.2进程的定义3.进程举例正在运行的Web浏览器是一个进程，正在运行的Windows资源管理器是一个进程，正在运行的VisualC＋＋编程环境也是一个进程在计算机中处于运行状态的任何一个程序都是一个进程，一个进程拥有内存、CPU时间等一系列资源3.1概述3.1.2进程的定义4.进程与作业用户线程进程作业步作业作业步进程线程由用户创建由系统创建由用户指定…..…..…..3.1概述3.1.2进程的定义4.进程与作业作业是用户向计算机提交任务的实体，用户向计算机提交作业后，系统将它放入外存中的作业等待队列等待执行；进程则是完成用户任务的执行实体，是向系统申请分配资源的基本单位一个作业可由多个进程组成，且必须至少由一个进程组成，但反过来不成立。作业的概念主要用在批处理系统中；而进程的概念用在几乎所有的多道系统中。3.1概述3.2.1进程的组成进程=程序+数据+进程控制块PCB程序是进程的不可缺少的组成部分；如果一个程序段允许被共享，则它应该是可重入的，或纯代码段数据是进程处理的对象进程控制块是进程的控制结构，包含了进程的描述信息、控制信息和资源信息以及现场保护区，是进程的唯一标识，系统通过PCB管理和控制进程。3.2进程的描述3.2.2进程控制块PCB(ProcessControlBlock)进程控制块是由OS维护的用来记录进程相关信息和管理进程而设置的一个专门的数据结构包含了进程的描述信息、控制信息和资源信息以及现场保护区PCB是进程动态特性的集中反映系统通过PCB感知进程的存在，通过PCB中所包含的各项变量的变化，掌握进程的状态以达到控制进程活动的目的3.2进程的描述3.2.2进程控制块PCB(ProcessControlBlock)PCB结构的全部或部分常驻内存；PCB随进程的创建而填写，随进程的撤消而释放；系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志进程与PCB是一一对应的3.2进程的描述3.2.2进程控制块PCB(ProcessControlBlock)进程控制块的内容进程描述信息：进程标识符(processID)，唯一，通常是一个整数进程名，通常基于可执行文件名用户标识符(userID)进程组关系(processgroup)3.2进程的描述3.2.2进程控制块PCB(ProcessControlBlock)进程控制块的内容进程控制信息：当前状态优先级(priority)代码执行入口地址程序的外存地址运行统计信息（执行时间、页面调度）进程间同步和通信；阻塞原因3.2进程的描述3.2.2进程控制块PCB(ProcessControlBlock)进程控制块的内容资源占用信息：虚拟地址空间的现状、打开文件列表CPU现场保护结构：寄存器值（通用、程序计数器PC、状态PSW，地址包括栈指针）3.2进程的描述3.2.3进程上下文进程上下文是对进程执行活动全过程的静态描述。进程上下文由进程的用户地址空间内容、硬件寄存器内容及与该进程相关的核心数据结构组成（正文段、数据集、堆栈）3.2进程的描述3.2.3进程上下文用户级上下文：进程的用户地址空间（包括用户栈各层次），包括用户正文段、用户数据段和用户栈；寄存器级上下文：程序寄存器、处理机状态寄存器、栈指针、通用寄存器的值；系统级上下文：静态部分（PCB和资源表格）动态部分：核心栈（核心过程的栈结构，不同进程在调用相同核心过程时有不同核心栈）3.2进程的描述3.2.3进程上下文进程上下文结构PCB各种控制表指针栈区数据集正文集各种寄存器3.2进程的描述3.2.4PCB的组织方式PCB表：系统把所有PCB组织在一起，并把它们放在内存的固定区域，就构成了PCB表PCB表的大小决定了系统中最多可同时存在的进程个数，称为系统的并发度3.2进程的描述3.2.4PCB的组织方式组织方式链表同一状态的进程其PCB成一链表，多个状态对应多个不同的链表各状态的进程形成不同的链表：就绪链表、阻塞链表3.2进程的描述3.2.4PCB的组织方式PCB1PCB2PCB3PCB4PCB5PCB6PCB7PCBn......空PCB运行态就绪态等待1等待267510153.2进程的描述3.2.4PCB的组织方式索引表同一状态的进程归入一个index表（由index指向PCB），多个状态对应多个不同的index表各状态的进行形成不同的索引表：就绪索引表、阻塞索引表PCBTableReadyBlockedPCBTableIndexTableReadyBlocked3.2进程的描述3.2.5进程的状态及其转换1.核心态和用户态进程的执行状态可分为用户执行状态和系统执行状态用户执行状态，又称用户态，进程的用户程序段执行时，该程序处于用户态。用户态时不可直接访问受保护的OS代码；系统执行状态，又称系统态，核心态，进程的系统程序执行时，该进程处于系统态。核心态时可以执行OS代码，可以访问全部进程空间。划分用户态和系统态的原因：把用户程序和系统程序分开，以利程序的保护和共享但增加了系统复杂度和系统开销3.2进程的描述3.2.5进程的状态及其转换2.进程的三种基本状态就绪态（Ready）：一个进程已经具备运行条件，但由于无CPU暂时不能运行的状态（当调度给其CPU时，立即可以运行。“万事俱备，只欠东风”。位于“就绪队列”中执行态（Running）：进程占有了包括CPU在内的全部资源，并在CPU上运行等待态（Blocked）：阻塞态、挂起态、封锁态、冻结态、睡眠态。指进程因等待某种事件的发生而暂时不能运行的状态（即使CPU空闲，该进程也不可运行）。处于等待态的进程位于等待队列中。不同系统设置的进程状态数目不同3.2进程的描述运行Running就绪Ready等待Blocked3.2.5进程的状态及其转换2.进程的三种基本状态基本状态间的转换3.2进程的描述3.2.5进程的状态及其转换2.进程的三种基本状态在进程运行过程中，由于进程自身进展情况及外界环境的变化，这三种基本状态可以依据一定的条件相互转换就绪运行:调度程序选择一个新的进程运行运行就绪:运行进程用完了时间片运行进程被中断，因为一高优先级进程处于