并发进程概述进程的顺序性与顺序程序设计进程的并发性与并发程序设计与时间有关的错误进程的交往:竞争与协作进程的顺序性一个进程在顺序处理器上的执行是严格按序的一个进程只有当一个操作结束后,
才能开始后继操作顺序程序设计顺序程序设计是把一个程序设计成一个顺序执行的程序模块顺序程序设计具有如下的特点:
程序执行的顺序性程序环境的封闭性程序执行结果的确定性计算过程的可再现性顺序程序设计顺序程序设计的例
while(1) { input,process,output }
78
输入机处理器磁带机
130150 228 280300 378 430450
时 间处理器利用率,52/(78+52+20)≈35%
串行工作
i1 p1 o1 i2 p2 o2
...
进程的并发性进程执行的并发性:一组进程的执行在时间上是重叠的并发进程的无关性 无关的并发进程是指它们分别在不同的变量集合上操作并发进程的交往性无关的并发进程无关的并发进程:一组并发进程分别在不同的变量集合上操作,一个进程的执行与其它并发进程的进展无关
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)={ }
则并发进程的执行与时间无关例如,有如下四条语句:
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条件 。 其他语句间因变量交集之和非空,并发执行可能会产生与时间有关的错误 。
无关的并发进程两个无关的进程并发执行的例处理器利用率,(52+42)/(78+52+20)≈63%
78
输入机处理器磁带机
130150 228 280300 378 430450时 间磁带机打印机
20 62 170 320
交往的并发进程交往的并发进程:一组并发进程共享某些变量,一个进程的执行可能影响其它并发进程的结果并发程序设计的例子
while(1) { input,send }
while(1) { receive,process,send }
while(1) { receive,output }
处理器利用率,( 52 * n) /( 78*n+52+20)? 67%
78
输入机处理器磁带机
130150 228 306208 286 384364时 间并行工作
i1
p1
i p o
o1
i2
p2
o2
i3
p3
o3
t1
t2
t3
进程时间并发程序设计并发程序设计是把一个程序设计成若干个可同时执行的程序模块的方法并发程序设计的特征:
并行性,共享性,交往性并发程序设计的优点:
对于单处理器系统,可让处理器和各个 I/O
设备同时工作,发挥硬部件的并行能力对于多处理器系统,可让各个进程在不同处理器上物理地并行,从而加快计算速度简化了程序设计任务采用并发程序设计的目的是:
充分发挥硬件的并行性,提高系统效率 。 硬件能并行工作仅仅有了提高效率的可能性,而硬部件并行性的实现还需要软件技术去利用和发挥 。 这种软件技术就是并发程序设计 。 并发程序设计是多道程序设计的基础,多道程序的实质就是把并发程序设计引入到系统中 。
与时间有关的错误对于一组交往的并发进程,执行的相对速度无法相互控制,各种与时间有关的错误就可能出现与时间有关的错误有两种表现形式结果不唯一永远等待
(结果不唯一)机票问题
process Ti ( i = 1,2 )
var Xi:integer;
begin
{按旅客定票要求找到 Aj};
Xi,= Aj;
if Xi>=1 then begin
Xi:=Xi-1; Aj:=Xi;{输出一张票 }; end
else {输出票已售完 };
end;
(永远等待)内存管理问题
procedure borrow (var B:integer)
begin
if B>x then
{申请进程进入等待队列等主存资源 }
x:=x-B;
{修改主存分配表,申请进程获得主存资源 }
end;
procedure return (var B:integer)
begin
x:=x+B;
{修改主存分配表 }
{释放等主存资源的进程 }
end;
进程的交往:竞争与协作并发进程之间的竞争关系进程的互斥并发进程之间的协作关系进程的同步资源竞争出现了两个控制问题:
一个是死锁 (Deadlock)问题,一组进程如果都获得了部分资源,还想要得到其他进程所占有的资源,
最终所有的进程将陷入死锁 。
另一个是饥饿 (Starvation) 问题,例如,三个进程 p1、
p2,p3均要周期性访问资源 R。 若 p1占有资源,
p2和 p3等待资源 。 当 p1离开临界区时,p3获得了资源 R。 如果 p3退出临界区之前,p1又申请并得到资源 R,如此重复造成 p2老是得不到资源 R。 尽管这里没有产生死锁,但出现了饥饿 。 对于临界资源,操作系统需要保证诸进程能互斥地访问这些资源,既要解决饥饿问题,又要解决死锁问题 。