南京大学：《操作系统》课程教学资源（PPT课件）第三章（3.3）并发进程概述

并进程概迷 选程的顺序性与顺序程序设计 煤进程的并发性与并发程序设计 煤与时间有关的错误 ※进程的交往:竞争与协作

并发进程概述 进程的顺序性与顺序程序设计 进程的并发性与并发程序设计 与时间有关的错误 进程的交往：竞争与协作

选程的顺序性 一个进程在顺序外理器上的执行是 严格按序的 兴一个进程只有当一个操作结東后, 才能开始后继操作

进程的顺序性 一个进程在顺序处理器上的执行是 严格按序的 一个进程只有当一个操作结束后， 才能开始后继操作

顺序程序设计 顺序程序设计是把一个程序设计成 一个顺序执行的程序模块 顺序程序设计具有如下的特点 ◆程序执行的顺序性 ◆程序环境的封闭性 ◆程序执行结果的确定性 ◆计算过程的可再现性

顺序程序设计 顺序程序设计是把一个程序设计成 一个顺序执行的程序模块 顺序程序设计具有如下的特点： 程序执行的顺序性 程序环境的封闭性 程序执行结果的确定性 计算过程的可再现性

顺序程序设计 一--单------4一一-单一÷-一------一---------一 顺序程序设计的例 while(1)i input, process, output) 130150 228280300 378430450 时间 输入机 处理器 磁带机 处理器利用率:52/(78+52+20≈35%

顺序程序设计 顺序程序设计的例 while(1) { input，process，output} 78 输入机 处理器 磁带机 130150 228 280 300 378 430 450 时 间 处理器利用率：52/(78+52+20)≈35%

串行工作

串行工作 i1 p1 o1 i2 p2 o2 ．．．

进程的并发性 煤进程执行的并发性:一组进程的执行在 时间上是宜鱼的 并发进程的无关性无关的并发进程是指 它们分别在不同的变量集合上操作 煤并进程的交往性

进程的并发性 进程执行的并发性：一组进程的执行在 时间上是重叠的 并发进程的无关性无关的并发进程是指 它们分别在不同的变量集合上操作 并发进程的交往性

无 关的并发进程 无关的并发进程:一组并发进程分 别在不同的变量集合上操作,一个 选程的执行与其它并发进程的冼展 无头 煤 Bernstein亲件 R(pi)={al,a2,an},程序p在执行期间引用的变量集 w(pi)={b1,b2,bm},程序pi在执行期间改变的变量集 考两个程序的变量集交梟之和为空 R(ploW(p2)UR(p2)nW(plOW(pI)nw(p2= 则并发进程的执行与时间无关

无关的并发进程 无关的并发进程：一组并发进程分 别在不同的变量集合上操作，一个 进程的执行与其它并发进程的进展 无关 Bernstein条件： R(pi)={a1,a2,…an}，程序pi在执行期间引用的变量集 W(pi)={b1,b2,…bm}，程序pi在执行期间改变的变量集 若两个程序的变量集交集之和为空集 R(p1)∩W(p2)∪R(p2)∩W(p1)∪W(p1)∩W(p2)={} 则并发进程的执行与时间无关

紫例如,有如下四条语句: 二1:a:一夂一- S2:b:=z+1 S3: c =a-b S4:W:=c+1 戏于是有:R(S1)={xy},R(S2){z},R(S3)={a,b}, R(S4)={c};W(Sl={a},W(S2)={b},W(S3)={c}, W(S4)={w} 紫可见S1和S2可并发执行,因为,满足 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条 件。其他语句间因变量交集之和非空，并发执行 可能会产生与时间有关的错误

无关的并发进程 两个元关的进程并发执行的例 时间_206276130101702 280300320378430450 输入机 处理器 磁带机 磁带机一 打印机 处理器利用率:(52+42)/(78+52+20)≈63%

无关的并发进程 两个无关的进程并发执行的例 处理器利用率：(52+42)/(78+52+20)≈63% 78 输入机 处理器 磁带机 130150 228 280300 378 430450 时 间 磁带机 打印机 20 62 170 320

交往的并发冼程 米交往的并发进程:一组并发进程共享某些变量, 个进程的执行可能影响其它并发进程的结鼎 煤并发程序设计的例子 while(l)i input, send j while(1)i receive, process, send j while(1)i receive, output 78130150 208228 286306 364384 时间 输入机 处理器 磁带机 处理器利用率:(52*n)/(78*n+52+20)◇67%

交往的并发进程 交往的并发进程：一组并发进程共享某些变量， 一个进程的执行可能影响其它并发进程的结果 并发程序设计的例子 while(1) { input，send } while(1) { receive，process，send } while(1) { receive，output } 处理器利用率：（52 * n） /（78*n+52+20） 67% 78 输入机 处理器 磁带机 130150 208228 286306 364384 时 间