操作系统原理PPT课件

1、操作系统原理操作系统原理汕头大学计算机系汕头大学计算机系吴俊豪吴俊豪1第三章 并发进程3.1 并发进程3.2 临界区管理3.3 信号量与PV操作3.4 管程3.5 进程通信3.6 操作系统并发问题解决方案小结3.7 死锁3.8 Linux同步和通信机制3.1并发进程3.1.1顺序程序设计 3.1.2并发程序设计3.1.3进程的交互：协作和竞争 3.1.1 3.1.1 顺序程序设计顺序程序设计程序执行的顺序性是指该程序在处理器上的执行是严格有序的，只有在前一个操作结束后，才能开始后继操作，这称为程序内部的顺序性；如果完成一个任务需要若干不同的程序，则这些程序也按照调用次序严格有序执行，这称为程序

2、外部的顺序性。传统的程序设计方法是顺序程序设计，即把程序设计成顺序执行的指令序列，不同程序也按顺序执行。 顺序程序设计特点 程序执行的顺序性 按次序执行 程序环境的封闭性 执行不受外界因素的影响 执行结果的确定性 走走停停，但结果不受影响，与速度无关 计算过程的可再现性 每次计算的结果都相同编写和调试比较方便；但效率不高。顺序程序设计的优缺点3.1.2 进程的并发性进程执行的并发性：一组进程的执行在时间上是重叠的。并发性举例：有两个进程A(a1、a2、a3)和B(b1、b2、b3)并发执行。 a1、a2、a3、b1、b2、b3 顺序执行 a1、b1、a2、b2、a3、b3 并发执行从宏观上看，

3、并发性反映一个时间段中几个进程都在同一处理器上，处于运行还未运行结束状态。从微观上看，任一时刻仅有一个进程在处理器上运行。处理大量数据块的程序：输入i 处理p 输出o进程的并发性（举例）程序并发 执行 小程序 ：循环执行，“读入”数据块，将数据送入缓冲区 ；小程序 ：循环执行，“加工”缓冲区中的数据，把计算结果送缓冲区 ；小程序 ：循环执行，“输出”缓冲区 中的计算结果，让数据打印输出。进程的并发性（举例）观察程序并发 执行现象(1) 小程序操作数据块有先后次序，按数据块序号从小到大处理。(2) 不同小程序可以并发执行的，例如，“输入” i、“加工” p与“输出” o可并行操作。这样 CPU、

4、输入设备和输出设备可并行工作。(3) 小程序并发执行时，相互之间会产生制约关系，原因是小程序1与共享资源-缓冲区1，小程序2与 3共享资源-缓冲区2，出现了竞争共享资源问题。处理大量数据块的程序：输入i 处理p 输出o并发的实质是一个处理器在几个进程之间的多路复用，是对有限的物理资源强制行使多进程共享，消除计算机部件之间的互相等待现象，以提高系统资源利用率。并发进程分类：无关的，交互的。无关的并发进程一组并发进程分别在不同的变量集合上操作，一个进程的执行与其他并发进程的进展无关。并发进程的无关性是进程的执行与时间无关的一个充分条件，又称为Bernstein条件。交互的并发进程一组并发进程共享某

5、些变量，一个进程的执行可能影响其他并发进程的结果。BernsteinBernstein条件条件 Bernstein条件举例 例如，有如下四条语句： S1: a := x + y S2: b := z + 1 S3: c := a b S4: w := c + 1 于是有： R(S1)=x,y ,R(S2)=z，R(S3)=a,b，R(S4)=c； W(S1)=a, W(S2)=b，W(S3)=c，W(S4)=w。 S1和S2可并发执行，满足Bernstein条件。其他语句并发执行可能会产生与时间有关的错误。并发程序设计的优点 对于单处理器系统,可让处理器和各I/O设备同时工作,发挥硬部件的并行

6、能力。对于多处理器系统,可让各进程在不同处理器上物理地并行，加快计算速度。简化程序设计任务。 采用并发程序设计的目的充分发挥硬件的并行性，提高系统效率。硬件能并行工作仅有了提高效率的可能性，硬部件并行性的实现需要软件技术去利用和发挥，这种软件技术就是并发程序设计。并发程序设计是多道程序设计的基础，多道程序的实质就是把并发程序设计引入到系统中。与时间有关的错误对于一组交互的并发进程，执行的相对速度无法相互控制，各种与时间有关的错误就可能出现。与时间有关错误的表现形式：结果不唯一永远等待 （结果不唯一）飞机票售票问题 / /* *飞机票售票问题飞机票售票问题* */ / void T1( ) vo

7、id T2( ) void T1( ) void T2( ) 按旅客订票要求找到按旅客订票要求找到Aj; Aj; 按旅客订票要求找到按旅客订票要求找到Aj;Aj; int X1=Aj; int X2=Aj; int X1=Aj; int X2=Aj; if(X1=1) if(X2=1) if(X1=1) if(X2=1) X1-; X2-; X1-; X2-; Aj=X1; Aj=X2; Aj=X1; Aj=X2; / /* *输出一张票输出一张票* */; /; /* *输出一张票输出一张票* */; /; else elseelse else / /* *输出信息输出信息 票已售完票已售完

8、“* */; /; /* *输出信息输出信息 票已售完票已售完“* */; /; （永远等待）内存资源管理问题 申请和归还内存资源问题申请和归还内存资源问题 int X=memory; /memoryint X=memory; /memory为初始内存容量为初始内存容量 voidvoid borrow(int B) void return(int B) borrow(int B) void return(int B) while(BX) X=X+B; while(BX) X=X+B; / /* *进程进程进入等待内存资源队列进入等待内存资源队列* */; /; /* *修改内存分配表修改内存分

9、配表* */; /; X=X-B ; X=X-B ; / /* *释放等内存资源进程释放等内存资源进程* */; /; / /* *修改内存分配表，进程获得内存资源修改内存分配表，进程获得内存资源* */; /; borrowborrow比较比较BXBX后，后，returnreturn抢先执行，此时无法释放抢先执行，此时无法释放“borrowborrow”进程（未进入等待队列），随后可能永远等待进程（未进入等待队列），随后可能永远等待3.1.3 进程的交互互斥：互斥： 进程互斥是指若干个进程因相互进程互斥是指若干个进程因相互争夺争夺独占型资源独占型资源时所产生的时所产生的竞争竞争关系。关系。

10、即若干进程要使用同一独占型共享资即若干进程要使用同一独占型共享资源时，任何时刻最多允许一个进程使用，源时，任何时刻最多允许一个进程使用，其他进程必须其他进程必须等待等待，直到占有资源的进程，直到占有资源的进程释放该资源。释放该资源。 例如，共享变量等。例如，共享变量等。竞争与协作竞争与协作互斥（资源竞争）的两个问题：1）死锁 一组进程中的每一个进程均无限期等待被该组进程中的另一个进程所占有且永远不会释放的资源。 2）饥饿 系统不能保证某个进程的等待时间上界，从而使该进程长时间等待，当等待时间给进程推进和响应带来明显影响时，称发生了进程饥饿。 当饥饿到一定程度的进程所赋予的任务即使完成也不再具有

11、实际意义时称该进程被饿死。 进程的交互：协作关系 某些进程为完成同一任务需要分工协作。 进程同步指为完成共同任务的并发进程基于某个条件来协调它们的活动，因为需要在某些位置上排定执行的先后次序而等待、传递信号或消息所产生的协作制约关系。同步：同步： 进程同步指为进程同步指为完成共同任务完成共同任务的并发进程需的并发进程需要要协调协调它们的活动，需要在某些位置上排它们的活动，需要在某些位置上排定执行的先后次序而定执行的先后次序而等待等待所产生的所产生的协作协作关关系。系。 即两个以上进程基于某个条件来协调它们即两个以上进程基于某个条件来协调它们的活动。例如，一个进程的执行依赖于协的活动。例如，一个进程的执行依赖于协作进程的消息或信号，当一个进程没有得作进程的消息或信号，当一