操作系统 第三章进程管理1

第二章进程管理1第三章进程管理•3.1进程基本概念•3.2进程调度•3.3进程同步和互斥•3.4经典的同步、互斥问题•3.5进程通信•3.6死锁•3.7线程第二章进程管理2重点和难点：•进程的定义和特征•用信号量机制解决进程同步、互斥•死锁及其解决方法第二章进程管理3§3.1进程基本概念一、进程的引入二、进程的概念三、进程的特征四、进程状态及其转换五、进程控制块六、进程的创建和撤消第二章进程管理4学习要求（1）牢固掌握进程的概念（2）深入理解进程最基本的属性是动态性和并发性（3）掌握进程与程序的主要区别（4）掌握进程的基本状态及其转换发生的典型事件（5）理解进程的一般组成，应深入理解进程控制块的作用第二章进程管理5一、进程的引入•程序的顺序执行、程序的并发执行特征比较程序的顺序执行程序的并发执行1顺序性1间断性2封闭性2失去封闭性3可再现性3不可再现性第二章进程管理6进程的引入•多道程序系统的特点是并行性。为了充分利用系统资源，在主存中同时存放多道作业运行•各程序由于同时存在于主存中，它们之间必定会存在相互依赖，相互制约的关系。（间接制约关系、直接制约关系）•在多道程序系统所带来的复杂环境中，程序具有了并行、制约、动态的特性，原来的程序概念，难以刻画系统中的情况了。–程序本身完全是静态的概念–程序概念也反映不了系统中的并行特性第二章进程管理7•一个较大的程序通常都是由若干个程序段组成。在程序执行时，必须按照某种先后次序逐个执行，仅当前一操作执行完后，才能执行后继操作。例如：在进行计算时，总是先输入用户的程序和数据，然后才能计算，计算完成后再将结果打印出来。1、程序的顺序执行第二章进程管理8I1C1P1P2I2C1程序顺序执行时的前驱图对于一个程序段中的多条语句来说，也有一个执行顺序的问题。如果对于下述三条语句的程序段：S1：a：＝x＋yS2：b：＝a－5S3：C：＝b＋1(其中S2必须在a被赋值以后才能执行；同样S3也只能在b被赋值以后才能执行)第二章进程管理9程序顺序执行时的特征–顺序性：按照程序结构所指定的次序（可能有分支或循环）–封闭性：独占全部资源，计算机的状态只由于该程序的控制逻辑所决定–可再现性：初始条件相同则结果相同。第二章进程管理102.程序的并发执行I1I2I4I3C1C2C3P1C4P4P3P2程序并发执行时的前驱图第二章进程管理11•程序并发执行：一组逻辑上相互独立的程序或程序段在执行过程中，其执行时间在客观上相互重叠，即一个程序段的执行，尚未结束，另一个程序段的执行已经开始的这种执行方式。第二章进程管理12程序并发执行时的特征•间断性•失去封闭性–是多个程序共享系统中的各种资源，因而这些资源的状态将由多个程序来改变•不可再现性第二章进程管理13二、进程的定义•进程有许多各式各样的定义（1）进程是可以并发执行的计算部分（2）进程是一个独立的可以调度的活动（3）进程是一个抽象的实体，当它执行某个任务时，将要分配和释放各种资源（4）行为的规则叫程序，程序在处理机上执行的活动称为进程。（5）一个进程是一系列逐一执行的操作，而操作的确切含义则有赖于以何种详尽程度来描述进程。第二章进程管理14进程：一个具有一定独立功能的程序在一个数据集合上的一次动态执行过程。（在这里，程序指一组操作序列，而数据集则是接受程序规定操作的一组存储单元的内容。）第二章进程管理15•比较进程和程序的区别：答：1、进程是一个动态的概念，进程的实质是程序的一次执行过程，动态性是进程的基本特征，同时进程是有一定的生命期的；而程序只是一组有序指令的集合，本身并无运动的含义，是静态的。2、不同的进程可以包含同一个程序，同一个程序在执行中也可以产生多个进程。3、进程有生命周期，有诞生有消亡，短暂的；而程序是相对长久的第二章进程管理163.1进程的基本概念一、进程的引入二、进程的概念三、进程的特征四、进程的状态及其转换五、进程控制块六、进程的创建和撤消第二章进程管理17三、进程的特征1．动态性2.并发性3.独立性进程实体是一个能独立运行的基本单位，同时也是系统中独立获得资源和独立调度的基本单位。没有建立进程的程序，不能作为一个独立的单位参加运行。4.异步性5.结构特性从结构上看，进程由程序段、数据段及PCB三部分组成。第二章进程管理18四、进程的状态及其转换1、进程的三种基本状态（1）就绪状态（Ready）当进程已经分配到除CPU以外的所有必要的资源后，只要能再获得处理机，就可以立即执行（2）执行状态（Running）（运行状态）指进程已获得处理机而执行的状态。第二章进程管理19（3）阻塞状态（Block）（等待状态）进程因为发生某个事件而暂停执行时的状态（如：请求I/O、申请缓冲空间等）。有时也称“等待”状态或“睡眠”状态。第二章进程管理202、进程状态转换①就绪→执行：调度②执行→等待：等待某个事件发生而睡眠③等待→就绪：因等待的事件发生而唤醒④执行→就绪：时间片用完或出现高优先进程第二章进程管理21附：进程状态的转换1．就绪状态执行状态处于就绪状态的进程，当进程调度程序为它分配了处理机后，该进程便由就绪状态变为执行状态，正在执行的进程也称为当前进程。2.执行状态阻塞状态正在执行的进程因发生某件事件而无法执行。例如：进程请求访问临界资源，而该资源正被其它进程访问，则请求该资源的进程将由执行状态转变为阻塞状态。第二章进程管理223.执行状态就绪状态正在执行的进程，如果事件发生或中断而被暂停执行，该进程便由执行状态转变为就绪状态。（分时系统中，时间片用完；抢占调度方式中，优先权高抢占处理机）4．执行状态终止状态当一个进程经完成或发生某事件，如程序中出现地址越界、非法指令等错误，而被异常结束时，进程将由执行状态转变为终止状态。第二章进程管理23就绪结束执行阻塞事件发生进程调度等待某事件完成时间片用完创建进程状态转换示意图第二章进程管理24五、进程控制块进程的静态描述：PCB+程序+数据集各部分的作用：进程控制块：用于描述进程情况及控制进程运行所需的全部信息。程序段：是进程中在CPU上执行的程序代码段。数据段：一个进程的数据段，可以是进程对应的程序加工处理的原始数据，也可以是程序执行后产生的中间或最终数据。第二章进程管理251、进程控制块中的信息进程控制块中主要包括用于描述和控制进程运行的信息。（1）进程标识符信息进程标识符用于唯一的标识一个进程。•外部标识符。由创建者提供，通常是由字母、数字组成，往往是用户（进程）访问该进程使用。外部标识符便于记忆，如：计算进程、打印进程、发送进程、接收进程等。•内部标识符：为了方便系统使用而设置的。在所有的OS中，都为每一个进程赋予一个唯一的整数，作为内部标识符。第二章进程管理26（2）处理机状态信息（现场信息）主要是由处理机各种寄存器中的内容所组成。通用寄存器：又称为用户可视寄存器，可被用户程序访问，用于暂存信息。指令寄存器PC：存放要访问的下一条指令的地址。程序状态字PSW：其中含有状态信息。（条件码、执行方式、中断屏蔽标志等）用户栈指针：每个用户进程有一个或若干个与之相关的用户栈，用于存放过程和系统调用参数及调用地址。栈指针指向该栈的栈顶。第二章进程管理27（3）进程调度信息在PCB中还存放了一些与进程调度有关的信息。进程状态：指明进程当前的状态，作为进程调度和对换时的依据。进程优先级：用于描述进程使用处理机的优先级别的一个整数，优先级高的进程优先获得处理机。进程调度所需要的其他信息：（进程已等待CPU的时间总和、进程已执行的时间总和）阻塞原因：这是进程由执行状态转变为阻塞状态所等待发生的事件。第二章进程管理282、PCB的组织方式常用的组织方式有两种：链接方式、索引方式。（1）链接方式：具有相同状态的PCB，用其中的链接字，链接成一个队列。这样就可以形成就绪队列、若干个阻塞队列和空白队列等。对其中的就绪队列常按照进程优先权的大小排列，把优先权高的进程的PCB排在队列前面。第二章进程管理29执行指针就绪队列指针阻塞队列指针空闲队列指针PCB1PCB2PCB3PCB4PCB5PCB6PCB7PCB8PCB9430879013……第二章进程管理30（2）索引方式：系统根据所有进程的状态，建立几张索引表。例如：就绪索引表、阻塞索引表。并把各索引表在内存的首地址记录在内存中的一些专用单元中。每个索引表的表目中，记录具有相同状态的某个PCB在PCB表中的地址。第二章进程管理31执行指针就绪表指针阻塞表指针就绪索引表阻塞索引表PCB3PCB4PCB5PCB7PCB6PCB2PCB1按索引方式组织PCB第二章进程管理32六、进程的创建和撤消•由原语实现：一般地，把系统状态下执行的某些具有特定功能的程序段称为原语•和进程控制有关的原语有：创建原语、撤销原语、阻塞原语、唤醒原语进程阻塞过程当有阻塞事件发生时，进程便调用阻塞原语block把自己阻塞进程唤醒过程当阻塞进程所期待的事件出现时，则调用唤醒原语wakeup，将等待事件的进程唤醒。唤醒原语执行的过程是：把被阻塞进程从阻塞队列中移出，将其PCB插入到就绪队列中。第二章进程管理331、进程的创建（1）申请空白的PCB为新进程分配唯一的数字标识符，并从PCB表项中申请一个空白的PCB（2）为新建立的进程分配资源（3）初始化PCB填写PCB相关表项，将进程的状态设置为“就绪”状态（4）将新进程插入就绪队列第二章进程管理34入口查PCB链表有空PCB？PCB入就绪队列将有关参数填入PCB相应项取空闲PCB块返回创建失败无创建原语流程图有第二章进程管理352、进程的撤消（1）将该进程所拥有的全部资源，或者归还给它的父进程，或者归还给系统。（2）撤消该进程的PCB表项。第二章进程管理36练习1、正在执行的进程由于时间片用完而被暂停执行，此时进程应从执行状态变为__⑴__状态；处于阻塞状态的进程，在进程等待事件出现后，应转变为__⑵__状态，若正在执行的进程申请I/O则应转变为（3）状态。•A.阻塞B.就绪C.执行D.撤消E.创建2、一个进程状态转换发生，有无另一个转换一定发生，试举例说明第二章进程管理373.2进程调度一、调度级别二、进程调度功能三、进程调度算法四、进程调度时机五、进程上下文第二章进程管理38一、调度级别•高级调度（作业调度、宏观调度）•中级调度（交换调度）－－进程在内、外存之间进行切换。引入中级调度的目的是为了提高内存的利用率和系统吞吐量•低级调度（进程调度）第二章进程管理39图：处理机三级调度作业调度作业运行状态外存外存(盘)交换区作业后备状态作业提交状态作业完成状态终止作业就绪态阻塞态中级调度主存进程调度运行态就绪态阻塞态第二章进程管理40二、进程调度功能1、记录系统中所有进程的执行情况2、选择占有处理机的进程3、进行进程上下文的切换第二章进程管理41三、进程调度算法进程调度的算法较多，在设计进程调度算法时应考虑的因素多，比如：尽量提高资源利用率减少处理机的空闲时间对于用户作业要较合理的平均响应时间，以及尽可能地增强CPU的处理能力第二章进程管理421、先进先出进程调度算法（FIFO）按照进程就绪的先后次序来调度进程优点:实现简单缺点:没考虑进程的优先级第二章进程管理432、基于优先数的调度（HPF—HighestPriorityFirst）优先选择就绪队列中优先级最高的进程投入运行优先级根据优先数来决定第二章进程管理44确定优先数的方法静态优先数法：在进程创建时指定优先数，在进程运行时优先数不变动态优先数法：在进程创建时创立一个优先数，但在其生命周期内优先数可以动态变化。如等待时间长优先数可改变第二章进程管理45思考：静态优先权和动态优先权相比：更易于实现的是：（静态优先权）运行开销较小的是：（静态优先权）更需要谨慎确定初始优先权的是：（静态优先权）更能反映运行环境变化的是：（动态优先权）.第二章进程管理46两种占用CPU的方式可剥夺式（可抢占式）：当有比正在运行的进程优先级更高的进程就绪时，系统可强行剥夺正在运行进程的