HYZ-OS-2013-进程管理.pptVIP

1,2019年7月11日星期四,北京交通大学计算机学院何永忠,操作系统（A）,北京交通大学计算机学院 何永忠 副教授,第二章：进程管理,2,2019年7月11日星期四,北京交通大学计算机学院何永忠,本节主要内容,重点：并发进程的制约 进程并发执行带来的难题：失去封闭性和可再现性，是并发编程的难点 重点难点：解决方法 临界资源 临界区,3,2019年7月11日星期四,北京交通大学计算机学院何永忠,第二章 进程管理,2.1 进程的基本概念 2.2 进程控制 2.3 进程同步 2.4 经典进程同步问题 2.5 管程 2.6 进程通信 2.7 线程,4,2019年7月11日星期四,北京交通大学计算机学院何永忠,2.3 进程同步,2.3.1 并发进程间制约关系 2.3.2 临界资源与临界区 2.3.3 进程同步机制准则 2.3.4 信号量机制 2.3.5 信号量机制应用基础,5,2019年7月11日星期四,北京交通大学计算机学院何永忠,并发进程间制约关系,资源共享关系间接制约（竞争关系） 多个进程彼此无关，独立完成自己的任务 必然会共享I/O设备等资源，导致对资源的争夺 系统须协调诸进程对资源的（互斥）访问 相互合作关系直接制约（合作关系） 多个进程共同合作完成一个任务 系统应保证相互合作的诸进程在执行次序上的协调（同步）。,6,2019年7月11日星期四,北京交通大学计算机学院何永忠,程序并发执行错误的举例,共享初值为5的变量N的两进程（线程）A、B A: N:=N+1 B: N:=N-1 两个进程并发执行的结果是什么？ 先A后B: N=5 先B后A: N=5 还有其他可能的执行结果吗？,7,2019年7月11日星期四,北京交通大学计算机学院何永忠,并发性,计算机中执行的是机器代码，并发最小粒度是机器指令！,8,2019年7月11日星期四,北京交通大学计算机学院何永忠,程序并发执行不可再现性举例,程序A: N=N+1 0040102F mov eax,dword ptr ebp-4 00401032 add eax,1 00401035 mov dword ptr ebp-4,eax 程序B: N=N-1 0040102F mov eax,dword ptr ebp-4 00401032 sub eax,1 00401035 mov dword ptr ebp-4,eax,9,2019年7月11日星期四,北京交通大学计算机学院何永忠,程序并发执行不可再现性举例,A1.0040102F mov eax,dword ptr ebp-4 A2.00401032 add eax,1 A3.00401035 mov dword ptr ebp-4,eax B1.0040102F mov eax,dword ptr ebp-4 B2.00401032 sub eax,1 B3.00401035 mov dword ptr ebp-4,eax,10,2019年7月11日星期四,北京交通大学计算机学院何永忠,程序并发执行不可再现性举例,前提条件 1、同一个进程里面的代码顺序执行 例如：A2 A1 A3 B1 B2 B3 错误！ 2、引入了进程后，进程切换时保持并恢复了现场（上下文切换），从而保证一个进程中断后下次执行操作系统已经恢复为原来寄存器的值。,11,2019年7月11日星期四,北京交通大学计算机学院何永忠,程序并发执行不可再现性举例,A1.0040102F mov eax,dword ptr ebp-4 B1.0040102F mov eax,dword ptr ebp-4 A2.00401032 add eax,1 A3.00401035 mov dword ptr ebp-4,eax B2.00401032 sub eax,1 B3.00401035 mov dword ptr ebp-4,eax 结果: N=4,12,2019年7月11日星期四,北京交通大学计算机学院何永忠,程序并发执行不可再现性举例,B1.0040102F mov eax,dword ptr ebp-4 A1.0040102F mov eax,dword ptr ebp-4 B2.00401032 sub eax,1 A2.00401032 add eax,1 B3.00401035 mov dword ptr ebp-4,eax A3.00401035 mov dword ptr ebp-4,eax,结果：6,13,2019年7月11日星期四,北京交通大学计算机学院何永忠,并发执行序列的总数,程序1：M条指令 程序2：N条指令 并发执行序列数目： (M+N)!/(M!*N!) C NM+N,14,2019年7月11日星期四,北京交通大学计算机学院何永忠,2.3 进程同步,2.3.1 并发进程间制约关系 2.3.2 临界资源与临界区 2.3.3 进程同步机制准则 2.3.4 信号量机制 2.3.5 信号量机制应用基础,15,2019年7月11日星期四,北京交通大学计算机学院何永忠,临界资源,一段时间内只允许一个进程访问的资源 打印机 许多物理设备、变量及表格 举例 两个进程A、B共享变量N，M(初值均为5) A: P=1；N:=N+1；M=N+1；Q=2; B: X=1；N:=N-1；M=N-1；Y=2； M,N值就是临界资源，只要能保证互斥的访问，就不会出现错误的结果,16,2019年7月11日星期四,北京交通大学计算机学院何永忠,如何保证互斥的访问临界资源？,临界区：每个进程中访问临界资源的那段代码称为临界区 A: P=1；N:=N+1；M=N+1；Q=2; B: X=1；N:=N-1；M=N-1；Y=2； 如果共享该临界资源的每个进程能互斥的进入自己的临界区，就能保证对临界资源的互斥访问。,17,2019年7月11日星期四,北京交通大学计算机学院何永忠,单车道如何保障安全通行？,临界区,18,2019年7月11日星期四,北京交通大学计算机学院何永忠,单车道如何保障安全通行？,1、小汽车请求进入 2、空闲？则放行,19,2019年7月11日星期四,北京交通大学计算机学院何永忠,单车道如何保障安全通行？,1、客车请求进入 2、已占用？等待,20,2019年7月11日星期四,北京交通大学计算机学院何永忠,单车道如何保障安全通行？,1、小车通知退出 2、临界区为空闲,21,2019年7月11日星期四,北京交通大学计算机学院何永忠,访问临界资源的循环进程描述,进程P1 begin repeat 进入区(wait) 临界区（N=N+1） 退出区(signal) until false; end,进程P2 begin repeat 进入区(wait) 临界区 (N=N-1) 退出区(signal) until false; end,22,2019年7月11日星期四,北京交通大学计算机学院何永忠,临界区分析,每个进程中访问临界资源的那段代码称为临界区 保证诸进程互斥地进入自己的临界区是实现它们对临界资源的互斥访问的充要条件,23,2019年7月11日星期四,北京交通大学计算机学院何永忠,临界区分析,访问相同临界资源的两个（多个）临界区之间需要互斥访问。否则，访问不同临界资源的两个临界区无需互斥。 例如A、B、C三个程序，哪些是互斥的？ A:M=M+1; B:M=M-1;N=N+1; C:N=N-1;,24,2019年7月11日星期四,北京交通大学计算机学院何永忠,2.3 进程同步,2.3.1 并发进程间制约关系 2.3.2 临界资源与临界区 2.3.3 进程同步机制准则 2.3.4 信号量机制 2.3.5 信号量机制应用基础,25,2019年7月11日星期四,北京交通大学计算机学院何永忠,26,2019年7月11日星期四,北京交通大学计算机学院何永忠,723事故原因,雷击导致信号控制系统故障，D3115在闭塞区间（临界区）中，后车D301没有看到正确信号（红灯），而是错误的绿灯！,27,2019年7月11日星期四,北京交通大学计算机学院何永忠,软件方法 软件方法基本思路 在进入区检查和设置一些标志，如果已有进程在临界区，则在进入区通过循环检查进行等待；在退出区修改标志 问题：设置什么标志和如何检查标志 历史上的四种算法,进程互斥实现方法,28,2019年7月11日星期四,北京交通大学计算机学院何永忠,软件互斥算法1,process1 repeat while (turn !=1); 临界区 turn=2;forever; ,process 2 repeat while (turn !=2); 临界区 turn=1;forever; ,共享单标志 int turn = 1;,对它访问在临界区 外,会出现意外吗？,29,2019年7月11日星期四,北京交通大学计算机学院何永忠,共享变量turn没有问题,while (turn !=1); 把turn读入寄存器 寄存器减一 结果为0退出循环 否则循环执行 turn=1; 把1存入turn;,30,2019年7月11日星期四,北京交通大学计算机学院何永忠,算法1分析,优点： 保证只有一个进程在临近区 缺点： 两个进程强制轮流进入临界区，容易造成资源利用不充分。 如：在P1让出临界区之后，P2使用临界区之前，P1不可能再次使用临界区。,31,2019年7月11日星期四,北京交通大学计算机学院何永忠,软件互斥算法2,process1 repeat while (flag2); flag1=true; 临界区 flag1=false; forever; ,process 2 repeat while (flag1); flag2 = true; 临界区 flag2=false; forever; ,共享双标志 bool flag1 = false; bool flag2 = false;,32,2019年7月11日星期四,北京交通大学计算机学院何永忠,优点 不要求交替进入临界区 缺点 P1和P2可能同时进入临界区 flag1=flag2=false P1: while(flag2) P2: while(flag1) P1: flag1=true P2: flag2=true,算法2分析,33,2019年7月11日星期四,北京交通大学计算机学院何永忠,软件互斥算法3,process1 repeat flag1=true; while (flag2); 临界区 flag1=false; forever; ,process 2 repeat flag2 = true; while (flag1); 临界区 flag2=false; forever; ,共享双标志 bool flag1 = false; bool flag2 = false;,34,2019年7月11日星期四,北京交通大学计算机学院何永忠,优点 防止两个进程同时进入临界区 缺点 P1和P2可能都进入不了临界区 flag1=flag2=false P1: flag1=true P2: flag2=true P1: while(flag2) P2: while(flag1),算法3分析,35,2019年7月11日星期四,北京交通大学计算机学院何永忠,软件互斥算法4-peterson算法,process1 repeat flag1=true; turn=2; while (flag2 ,process 2 repeat flag2 = true; turn=1; while (flag1 ,共享三标志 turn=1; bool flag1 = false; bool flag2 = false;,缺点：并发进程数未知？,36,2019年7月11日星期四,北京交通大学计算机学院何永忠,三种硬件方法 “测试并设置”指令 “交换”指令 “开关中断”指令 进入临界区前执行：执行“关中断”指令 离开临界区后执行：执行“开中断”指令,进程互斥硬件方法,37,2019年7月11日星期四,北京交通大学计算机学院何永忠,优点 适用于任意数目的进程、单处理器或多处理器上 简单、容易验证其正确性 可以支持进程有多个临界区 缺点 等待时要耗费CPU时间。 可能“饥饿”：从等待进程中随机选择一个进入临界区，有的进程可能一直选不上。 可能死锁。,硬件方法优缺点,38,2019年7月11日星期四,北京交通大学计算机学院何永忠,进程同步机制基本准则,空闲让进（效率） 当无进程处于临界区时，可允许一个请求进入临界区的进程立即进入自己的临界区 忙则等待（正确性） 当已有进程进入自己的临界区时，所有企图进入临界区的进程必须等待 有限等待（公平性） 对要求访问临界资源的进程，应保证该进程能在有限时间内进入自己的临界区 让权等待（效率） 当进程不能进入自己的临界区时，应释放处理机,39,2019年7月11日星期四,北京交通大学计算机学院何永忠,信号量奠基者 Dijkstra,Dijkstra was born in 1930 in Rotterdam, The Netherlands the son of a chemist father and a mathematician mother. Died in 2002. Won 1972 Turing Award. Contributions: Synchronization shortest path algorithm dining philosophers deadly embrace,40,2019年7月11日星期四,北京交通大学计算机学院何永忠,Dijkstra信号量机制,信号量机制有两个原语操作 进入前：P 原语（=wait） 退出后：V 原语(=signal) 其中P是荷兰语的Passeren，相当于英文的pass, V是荷兰语的Verhoog,相当于英文中的incremnet。,41,2019年7月11日星期四,北京交通大学计算机学院何永忠,单车道如何保障安全通行？,临界区,42,2019年7月11日星期四,北京交通大学计算机学院何永忠,单车道如何保障安全通行？,1、小汽车请求进入 2、绿灯？！ 3、放行同时红灯亮,wait,43,2019年7月11日星期四,北京交通大学计算机学院何永忠,单车道如何保障安全通行？,1、客车请求进入 2、红灯？！ 3、等待绿灯。,wait,44,2019年7月11日星期四,北京交通大学计算机学院何永忠,单车道如何保障安全通行？,1、小车通知退出 2、红灯变绿灯,signal,45,2019年7月11日星期四,北京交通大学计算机学院何永忠,整型信号量,整型信号量 s s=1 ：表示绿灯； s=0 表示红灯 wait(s): while s0 do no_op; s:=s-1; signal(s): s:=s+1;,有何弊端？,46,2019年7月11日星期四,北京交通大学计算机学院何永忠,利用信号量实现互斥子程序,process1: begin repeat N=N-1; until false; end,process2: begin repeat N=N+1; until false; end,47,2019年7月11日星期四,北京交通大学计算机学院何永忠,利用信号量实现互斥子程序,process1: begin repeat wait(mutex); N=N-1; signal(mutex); until false; end,process2: begin repeat wait(mutex); N=N+1; signal(mutex); until false; end,Var mutex: semaphore :=1;,48,2019年7月11日星期四,北京交通大学计算机学院何永忠,记录型信号量机制,type semaphore=record value: integer; L: list of process; end,procedure wait(s) Var s: semaphore; begin s.value:=s.value - 1; if s.value0 then block(s.L); end,procedure signal(s) Var s: semaphore; begin s.value:=s.value + 1; if s.value0 then wakeup(s.L); end,49,2019年7月11日星期四,北京交通大学计算机学院何永忠,记录型信号量实现互斥,process1: begin repeat wait(mutex); N=N-1; signal(mutex); until false; end,Process2,3： begin repeat wait(mutex); N=N+1; signal(mutex); until false; end,Var mutex: semaphore :=1;,50,2019年7月11日星期四,北京交通大学计算机学院何永忠,记录型信号量值如何变化,1、进程P1 执行wait操作申请进入临界区，那么mutex=? 能否进入？ 2、进程P2 执行wait操作申请进入临界区，mutex=? 能否进入？ 3、进程P1执行signal操作退出临界区， 那么mutex=? 4、然后P2？,51,2019年7月11日星期四,北京交通大学计算机学院何永忠,记录型信号量值如何变化,1、进程P1 执行wait操作申请进入临界区，那么mutex=?，能否进入？ 2、进程P2 执行wait操作申请进入临界区，mutex=?能否进入？ 3、进程P3 执行wait操作申请进入临界区，mutex=?能否进入？ 4、进程P1执行signal操作退出临界区， 那么mutex=? 5、然后，哪个进程被唤醒？,52,2019年7月11日星期四,北京交通大学计算机学院何永忠,互斥信号量物理意义,值为1：表示当前有一个临界资源可用，或者最多可允许一个进程进入该资源对应的临界区 值为0：表示临界资源已经被占用，或者已有一个进程进入该资源对应的临界区 值为负：其绝对值表示等待使用该资源的进程数。,53,2019年7月11日星期四,北京交通大学计算机学院何永忠,记录型信号量,process1: begin repeat wait(mutex); 临界区; signal(mutex); until false; end,Process2,3: begin repeat wait(mutex); 临界区; signal(mutex); until false; end,Var mutex: semaphore :=2;,54,2019年7月11日星期四,北京交通大学计算机学院何永忠,记录型信号量值如何变化,1、进程P1 执行wait操作申请进入临界区，那么mutex=?，能否进入？ 2、进程P2 执行wait操作申请进入临界区，mutex=?能否进入？ 3、进程P3 执行wait操作申请进入临界区，mutex=?能否进入？ 4、进程P1