操作系统原理_方敏_进程管理.ppt

第三章 进程管理,操作系统课程组,第2页,内容回顾,第3页,一、进程的定义,曾经的定义 进程是程序的一次执行； 进程是可以和别的计算并发执行的计算； 进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位…… 教材中的定义 进程是程序的一次执行，该进程可与其它进程并发执行；它是一个动态的实体，在传统的操作系统设计中，进程既是资源的基本分配单元，也是基本的执行单元第4页,二、为什么要引入进程的概念？,顺序执行程序 指的是在有多个程序需要执行的情况下，处理器严格按照某一顺序按序执行，每次只执行一个程序其实质是单道程序系统 特点 顺序性 资源独占性 可再现性 不足 效率低下,第5页,二、为什么要引入进程的概念？,多道程序设计 同一时刻内存中存放了多个作业，处理器交替运行不同的作业提高了系统的效率，尤其是资源利用率 特点 多道 宏观上并行 微观上串行 问题 系统管理复杂化,第6页,二、为什么要引入进程的概念？,程序并发执行带来的新特征 资源共享性； 独立性和制约性； 程序执行的间断性； 结果不可再现第7页,二、为什么要引入进程的概念？,与时间有关的错误,… a = n //n表示剩余的票数 if (a>=1) { a = a-1; //售出一张票n = a; } ……,… a = n //n表示剩余的票数 if (a>=1) { a = a-1; //售出一张票n = a; } ……,因为这种错误和相对执行速度有关，因此称为与时间有关的错误。

服务器,第8页,二、为什么要引入进程的概念？,结论： 程序的并发执行使得程序的执行情况不可预见，其结果不再唯一，成为一个动态的过程而程序是一个静态的概念，不再能切实反映程序执行的各种特征（独立性、并发性、动态性）第9页,三、进程的定义与控制,进程与程序的区别和联系,（1）程序是静态的，进程是动态的程序是有序代码的集合；进程是程序的一次执行2）进程是暂时的，程序的永久的进程是一个变化的过程，有生命周期，暂时存在，程序没有生命周期，可长久保存3）进程还是操作系统资源分配和保护的基本单位，程序没有此功能4）进程与程序的对应关系通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序5）进程与程序的结构不同第10页,三、进程的定义与控制,进程的组成,第11页,三、进程的定义与控制,进程控制块（PCB） 定义：是操作系统用来记录进程详细状态和相关信息的基本数据结构，它和进程是一一对应的，是进程存在的唯一标识 作用：提供进程的各种信息，以便操作系统控制和管理第12页,三、进程的定义与控制,PCB结构,第13页,三、进程的定义与控制,操作系统对PCB的管理：集中统一管理,,内存,,PCB表,第14页,三、进程的定义与控制,进程的创建 操作系统为进程创建进程控制块和分配地址空间的过程就是进程创建的过程。

创建进程标识,分配内存和其它资源,初始化进程控制块,将创建的进程置于就绪队列,,,,第15页,三、进程的定义与控制,进程的执行,运行 Running,进程占有处理机，处理机正在执行该进程的程序进程已获得除处理机外的所需资源，等待分配处理机执行也叫等待、挂起、睡眠态，此时进程因等待某种条件（如I/O操作或进程同步）无法运行引起进程阻塞的原因很多，系统将根据不同的阻塞原因将进程插入某个相应的阻塞队列中第16页,三、进程的定义与控制,进程状态转换及原因,第17页,三、进程的定义与控制,运行,就绪,阻塞,,,,,被调度,时间片用完，中断,资源释放或事件完成,等待资源 和事件,五种进程状态转换,第18页,三、进程的定义与控制,七种进程状态转换,第19页,三、进程的定义与控制,进程的组织管理——队列,第20页,三、进程的定义与控制,进程控制 进程控制的主要任务是：创建和撤销进程以及进行进程间的状态转换这包括： 创建一个进程 撤销一个进程 改变进程状态 实现进程间的通信 这些由操作系统内核通过执行各种原语完成第21页,三、进程的定义与控制,原语（primitive） 由若干条机器指令构成的可完成特定功能的程序段，它是一个 “原子操作(atomic operation)”过程，作为一个整体而不可分割－－要么全都完成，要么全都不做（类似数据库中的“事务”）。

原语主要是通过屏蔽各种中断和固化技术保证其原子性的 分类 进程控制原语 进程通信原语 进程管理原语 其他方面的原语,1、进程创建原语 2、进程撤销原语 3、进程阻塞原语 4、进程唤醒原语 5、进程挂起原语 6、进程激活原语,第22页,三、进程的定义与控制,进程的特征 并发性：执行时间可以重叠； 动态性：有生命周期，存在不同的状态； 独立性：独立执行，是资源分配和调度的独立单位； 制约性：虽然独立执行，但可能存在相互制约关系； 异步性：各进程执行时间相对独立，不确定； 结构性：拥有固定结构第23页,四、进程调度,进程调度：就是按照一定的算法，从就绪队列中选择某个进程占用CPU的方法——对CPU资源进行合理的分配使用，以提高处理机利用率，并使各进程公平得到处理机资源第24页,四、进程调度,确定进程调度算法原则 进程调度的任务是：有效的选择占用CPU的进程，控制协调系统安全、高效的工作设计者,第25页,四、进程调度,进程调度算法 先来先服务调度算法 (FCFS, First Come First Served)特点： 简单、可靠； 容易理解、实现方便； 非抢占式的 缺点： 作业的平均等待时间过长，系统效率低下； 不适合于分时系统。

CPU,,第26页,四、进程调度,基于优先数的调度算法(Priority Scheduling Algorithm) 思想：给每一个进程设置一个优先数(优先级)，系统在调度时优先选择具有高优先级的进程占用CPU具有相同优先数的进程按照FCFS算法执行 优先数的确定： 运行前：可根据外设的使用情况，运行时间的长短，紧急程度，重要程度等因素确定 运行中：1）静态优先数法：进程创建时就规定好它的优先 数，这个数值在进程运行时不变2）动态优先数法：进程的优先数在执行过程中可以根据情况变化而改变(UNIX中采用的方法)第27页,四、进程调度,优点： 灵活通过不同的优先级设置策略，可以强调不同的性能 实现也较为方便 通过优先级的动态调整，可以平衡系统性能 问题： 静态优先数法——无穷阻塞 (Indefinite Blocking) 进程占用CPU的方式 非抢占式 (不可剥夺式)——FCFS 抢占式 (可剥夺式)——会使进程频繁调度，在设计时还应考虑进程切换的时间开销第28页,四、进程调度,时间片轮转法 (RR, Round Robin) 特点：专门为分时系统设计类似于FCFS算法但是增加了抢占及进程间的切换功能。

思想：系统规定一个时间长度(时间片/时间量)作为允许一个进程运行的时间，如果在这段时间该进程没有执行完，则必须让出CPU等待下一次分配的时间片 原理,第29页,四、进程调度,时间片的选择方法 固定时间片：分配给每个进程时间片相等； 可变时间片：根据进程的不同要求对时间片的大小实时修改 优点：公平性，及时性 问题：时间片大小的确定？ 过大：退化为FCFS算法，响应时间变长 过小：一个任务需要多个时间片执行，增加了进程切换次数，响应时间变长第30页,四、进程调度,多级反馈队列调度算法(Multilevel Feedback Queue Scheduling) 思想：引入多个就绪队列，通过对各队列的区别对待，达到一个综合的调度目标 原理：,目前最为通用、灵活的CPU调度算法，但也是最为复杂的第31页,五、进程间的相互作用,同步,data,定义：进程之间这种相互合作、协同工作的关系称为进程的同步 简单说来就是：多个相关进程在执行次序上的协调制约关系：直接制约第32页,五、进程间的相互作用,互斥,,,定义：当多个进程因为争夺临界资源而互斥执行称为进程的互斥制约关系：间接制约第33页,五、进程间的相互作用,临界资源处理不当带来的问题 执行结果错误,第34页,五、进程间的相互作用,死锁（Dead Lock）,,,,,在并发系统中，程序执行结果的正确性不仅取决于自身的正确性，还与其在执行过程中能否正确的与其它进程实施同步或互斥有关。

必须对临界资源的访问进行控制第35页,五、进程间的相互作用,互斥解决方案 关中断法(开关中断指令) 也称为“硬件锁”，是实现互斥最简单的方法 做法：每个进程在进入临界区后先关中断，屏蔽其它请求，在离开之前再开中断 优点：实现简单 缺点：中断被关掉后，CPU不再响应任何外部事件，此时进程将会独占CPU，直至关闭中断，如果中断关闭时间过长，会造成严重后果，因此把开关中断的权力交给用户进程是很不明智的第36页,五、进程间的相互作用,锁变量法(测试和设置指令) 做法：设置一个共享(锁)变量W，初值为0当一个进程想进入其临界区时，它首先测试这把锁如果锁的值为0，则进程将其置为1并进入临界区若锁已经为1，则进程等待直到其变成0于是，0就表示临界区内没有进程，1表示已经有某个进程进入了临界区优点：较为简单 缺点：当有一个进程进入临界区后，其它试图进入的进程必须反复不断的测试W以便在W为0时进入，此时CPU会一直处于忙状态(busy waiting)因此这种方法效率也很低…… LOCK(W); //加锁原语 临界区; UNLOCK(W); //解锁原语 ……,第37页,五、进程间的相互作用,其它方法 Dekker算法：进程被强制轮流进入临界区(不管是否愿意)。

Peterson算法：设置标识指示是否又要求进入临界区……,第38页,五、进程间的相互作用,原则： 互斥：一次只允许一个进程进入临界区中，即各进程互斥访问临界资源 空闲则入，忙则等待：不能让等待进入临界区的进程“死等”，而谁也不能进入，即进程不能无限地停留在等待临界资源的状态 有限等待：每个进程占用临界资源的时间必须是有限的，使用完毕立刻释放资源第39页,五、进程间的相互作用,信号量(Semaphore)和P、V操作 信号量：1965年由荷兰学者Dijkstra提出，它是一种特殊的数据结构 功能：表示资源的实体 特殊之处： 每个信号量与一个队列关联； 其值只能通过初始化和P、V操作来访问 信号量的类型： 公用信号量：用于进程间的互斥，初值通常为1 私有信号量：用于进程间的同步，初值通常为0或n,第40页,五、进程间的相互作用,P、V操作 (均是原语),P操作：荷兰语“proberen”——“检测”之意意味着请求分配一个单位资源P(S)： //S为信号量 {S = S - 1;if (S < 0){调用进程被阻塞，进入S的等待队列；} },第41页,五、进程间的相互作用,V操作：荷兰语“verhogen”——“增量”之意，意味着释放一个单位资源。

V(S)： //S为信号量 {S = S + 1;if (S <= 0){从S的等待队列中唤醒一个进程使其进入就绪状态；} },第42页,,五、进程间的相互作用,信号量及P、V操作的应用 进程的互斥,semaphore S; //设置公有信号量 S = 1; //初值,{…P(S);print file1;V(S);… },{…P(S);print file2;V(S);… },第43页,五、进程间的相互作用,进程的同步——生产者与消费者问题,问题描述：,生产者,缓冲区,消费者,{cooking;P(S1);put in dish;V(S2); },,semaphore S1, S2 ; //设置私有信号量 S1=1; //表示盘子是否空 S2=0; //表示盘子里是否有东西,{P(S2);take out from dish;V(S1);eating; },。