一:并发进程(concurrent processes)
-1-1:前趋图:
是有向无环图，图中每个结点表示一个语句、一个计算步骤、或一个进程。
之类的边是有向边,表示偏序or前趋 的关系
(Pi->Pj):Pi->Pj表示Pj启动的一个条件是Pi完成 ,节点的权重表示计算时间or代码量
没有入度的点叫做起始点,没有出度的点叫做终止节点
eg:
-1-2顺序执行:
(1)内部顺序性:对于一个进程来说，它的所有指令是按序执行的。
(2)外部顺序性:对于多个进程来说，所有进程的活动是依次执行的。
特性:
(1)连续性: 指令逐条执行
(2)封闭性: 不受其它程序及外界因素影响
(3)可再现性: 结果与推进速度无关
-1-3:程序的并发执行:
(1)内部并发性:指一个程序内部的并发性
(2)外部并发性:指多个程序之间的并发性。
并发程序的特性:
（1）间断性：程序交叉执行。
（2）非封闭性：一个进程的运行环境可能被其它进程所改变，从而相互影响。
（3）不可再现性：由于交叉的随机性，并发程序的多次执行可能对应不同的交叉，因而不能期望重新运行的程序能够再现上次运行的结果。
比如都对一个共享变量a操作,一个让a自增,一个要输出a,可能先输出,也可能先修改
-1-4:程序并发的条件:
失去了封闭性但是保持可再现性:
我们用读写集合来表示:P1和P2可以再现的条件:
(P1的读和P2的写集合 并 P1的写和P2的读 并 P1和P2的写 集合为空)
例子:
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和S3,S2和S3,S3和S4不能并发
-1-5:并发的表示:
第一种:
cobegin S1,S2,S3...; //里面填写语句
......
coend ;
第二种:
parbegin S1 S2 .......;
..........
parend;
一些和时间相关的错误:
1：进程执行不正确的交叉(interleave);
2：同时对一个公共变量(x)操作，其中一个进程的操作没有结束，另一个进程也对公共变量进行操作，使得公共变量处于一种不确定的状态，用数据库的术语说就是失去了变量x的数据完整性。
二:进程互斥(mutual exclusion)
-2-1:共享变量与临界区
共享变量（shared variable）:多个进程都需要访问的变量。
临界区域（critical region）:访问共享变量的程序段。把临界区与其所对应的共享变量联系起来称为关于某一种共享变量的临界区
程序表示:
共享变量: shared <一组变量>
临界区域: region <一组变量> do <语句＞
-2-2:临界区域和进程互斥:
互斥的定义:多个进程不能同时进入关于同一组共享变量的临界区域，否则可能发生与时间有关的错误，这种现象称为进程互斥。(包含了任何时刻只有一个进程处在一个共享变量的临街区域,任何时刻最多只能有1个进程处于同一个组共享变量的不同临界区域)
-2-3:进程互斥的实现
3个要求:
mutual exclusion(互斥进入): 一次只允许一个进程进入关于同一组公共变量的临界区,其中有的话要求其他请求者等待
Progress(空闲让进): 临界区空闲时，放行一个进入者；
bounded waiting(有限等待): 一个想要进入临界区的进程在等待有限个进程进入并离开临界区后获得进入临界区的机会。
-2-3-1:软件实现:
完全用程序实现，不需特殊硬件指令支持,可用于单CPU和多CPU环境中。有忙式等待问题。
我们去逐步的去设计:
尝试1:
用turn表示轮到谁了,访问完临界区后再交给对方
问题:不满足进展性: P0和P1必须交替进入临界区.
尝试2:
如果对方要进入,我们就忙等,直到对方释放.先标记自己正在访问然后处理,最后给自己标注false,表示访问完成
问题:不满足互斥性: flag[0]=flag[1]=false. (两个进程都执行完后,两个标志位都是false,下次容易两个都同时进入导致互斥被破坏)
尝试3:
初始化两个flag为0,一开始表示自己有意愿去访问临界区,如果对方也有意愿or正在进行,我们就等,当对方退出,取消自己的flag,我们再进入,退出的识货,也取消自己的意愿
问题:不满足进展性:两个flag都是true,进程P1和进程P2都不能进入临界区.
Dekkel算法(结合了上面的flag和turn):
每次都是先表示自己想访问临界区,如果对方也想访问:检查是否轮到对方了,如果是,那么说明现在对方正在访问临界区,我们就取消我们的意愿,直到turn到我们,重新标记自己的flag.
访问临界区后,把会和交给对方,自己的意愿清空
Peterson算法:
先表示我自己有意愿访问临界区,但是把回合交给对方,如果回合是对方且对方有意愿,我们就忙等. 否则就该我们去访问临界区了,访问完取消自己的flag标记
Lamport面包店算法:
设置一个发号者，按0,1,2,…, 发号。想进入临界区的进程抓号，抓到号之后按由小到大的次序依次进入,(可以互斥发号,保证不会抓到相同的号;也可以允许抓到相同的号,然后按照进程的编号依次进入)
choosing表示i抓号ing
number记录抓的号
先标记自己在抓号,然后从里面抓一个最大的号,然后从0到n-1看看其他的人是否在抓号,如果在,就忙等, 如果抓号完成而且自己要比他后进入面包店,忙等.最后才能进入临界区
最后离开的时候要丢弃自己的号
如果没有choosing,会不满足互斥性:
1和2可以同时抓号,而且可能2比1更快,然后2直接进入临界区,2进入之后,离开之前,因为判断是号码相同,但是1比2进程更优先,所以1也会进入
3个特性(管理原则)看看是否满足:
互斥性(mutual exclusion)
多个进程竞争进入临界区时, 下述条件之一成立:
(1)一个进程抓到最小号:情形(1)抓到最小号的进程获准进入临界区;
(2)若干进程抓到最小号:情形(2)编号最小抓到最小号的进程获准进入临界区, 其它进程将在第一个while循环或第二个while循环处等待, 因而满足互斥性.
进展性(progress)
当仅有一个进程想进入临界区时, 该进程可以立即进入;
当有多个进程想进入临界区时其二元组(number[i],i)最小的进程获准进入, 因而确定进入临界区进程的决策将在有限时间内确定.
有限等待性(bounded waiting)
对任意一个想要进入临界区的进程Pi, 设其抓到号码为number[i], 按二元组(number[i],i)次序排在Pi之前的竞争进程数量是有限的, 在最坏情况下Pi将等待n-1个排在其前面的进程进入并离开临界区后获得进入临界区的资格, 因而满足有限等待性.
Eisenberg/Mcguire算法:
变量:
算法步骤:
先标记自己想进入临界区,看看当前到谁了,从当前的turn开始去遍历,如果指向的人也想or正在临界区,那么我们就重新从turn开始,否则就看看j指向的下一个
退出循环后,我们就可以标记自己in_cs了(更高优先级的等待or运行)
j从0遍历到n,如果指向我们自己或者这个人没有in_cs的状态,我们就去看下一个
最后如果J<n,说明有其他的in_cs,继续循环,否则就到我们啦!!
进入临界区
最后循环,将turn交给一个want_in 或者 in_cs的人,然后标记自己结束访问 ,
检查3个特性是否都满足:
互斥性:仅当flag[i]==in_cs, 且对所有j!=i, flag[j]!=in_cs时, 进程Pi才进入临界区域, 因而满足互斥性.
进展性:临界区空闲时, 排在序列turn, turn+1, …, n-1,0,1, 2,…,turn-1最前面的申请进入临界区的进程获准进入临界区, 因而满足进展性.
有限等待性:进程离开临界区时,按循环次序turn+1, …, n-1,0,1, 2,…,turn-1确定唯一一个竞争进程为其后继, 所以一个进程最多等待n-1个进程进入并离开临界区后一定能进入临界区, 因而满足有限等待性.
-2-3-2:进程互斥的硬件实现:
test_and_set(int& target)
int test_and_set(int &target){
int temp;
temp=target;
*target=1;
return (temp);
}
方法1:
.对一组公共变量，int lock;（初始=0);
Pi进入：While test_and_set(&lock);
Pi离开：lock=0;
满足互斥性，进展性，不满足有限等待性。(可能忙等)
方法2:
一开始表示自己正在等待,key赋值为1,如果lock锁上了,而且我还在等(没人唤醒我),继续等
让锁没了or我被唤醒,继续执行,
进入临界区
从I+1开始看看其他的在等的,尝试去唤醒
如果没有需要唤醒的(i==j),那么就释放锁,,如果有,就唤醒对方,锁就交给他来管了
硬件提供的Swap方法
void swap(int &a,&b){
int temp;
temp:=*a; *a:=*b; *b:=temp;
};
对一组公共变量：int lock (初始=0);
对一个进程空间：int key;
Pi进入：key=1;
do swap(&lock,&key)
while (key==1);
Pi离开：lock=0;
一开始两个(key和lock都是1:那么只有lock被释放了,才有可能出现key=0 ; 一开始lock是0,那么也会直接进入临界区 ,不管那种最后lock都会变成key对应的1)
注意:
(1) test_and_set指令和swap指令是原子的，不可中断的(在单CPU情况下)。
(2) test_and_set实际上是：将内存中一个单元的内容取出，再送一个新值。
(3) swap实际上是：交换内存两个单元的内容
3,硬件提供关中断和开中断两个指令
-2-4:多处理机下的互斥
实例
关中断
{ Critical Region}
开中断
注意:(1) 开关中断只在单CPU系统中有效;(多CPU可能被其他的CPU访问共享区域)
(2) 影响并发性。
单CPU, 指令间交叉, test_and_set, swap指令是原子的;
多CPU, 指令周期间交叉, test_and_set, swap指令不是原子的;
三:进程同步(synchronization)
引入:
经典的UNIX系统:通过关中断实现互斥(提高处理机的优先级)
特点:简单,开销小,影响并发性, 关中断后代码很短
在SMP系统中采用自旋锁
-3-1:进程同步的概念
通过上面的例子,发现:一组进程，为协调其推进速度，在某些关键点处需要相互等待与相互唤醒，进程之间这种相互制约的关系称为进程同步。
同步机制的定义的要求:
用于实现进程同步的工具,这个工具要求:描述能力够用;可实现;高效;使用方便.
进程同步的定义:
一组进程，如果它们单独不能正常进行，但并发可以正常进行，称这种现象为进程合作
-3-2:信号量与PV操作:
信号量变量:一个提前定义的变量,我们根据我们的需要去声明就好
P操作:
申请一个资源,如果s->value的值小于0,将这个PCB放入S->queue的队尾,状态也变成等待态
V操作:
释放一个资源,如果有s->value在等待,就去唤醒对头的PCB,进入就绪态
关于信号量:
必须置一次初值，只能置一次初值，初值>=0;
只能执行P操作和V操作，所有其它操作非法。
发现如果:
当s->value>=0时，s->queue为空；
当s->value<0时，|s->value|为队列s->queue的长度；
当s->value初 =1时，可以实现进程互斥；
当s->value初 =0时，可以实现进程间的简单同步；
当s->value 为非1的正整数时，可以用来管理同种组合资源，申请资源执行一次P操作，归还资源执行一次V操作；
PV操作的实现:
注意到这里的PV操作应该是原子的,所以有可以尝试用开关中断来实现PV操作
void P(semaphore *s){
disable interrupt;//不允许中断
s->value--;//申请
if (s->value<0)//没有足够资源
{asleep(s->queue)//等待
enable interrupt;//允许中断
goto CPU dispatcher;//CPU调度其他的进程
}else//有足够的资源,没有其他的操作
enable interrupt;
}
void V(semaphore *s){
disable interrupt;
s->value++;
if (s->value≤0)
{wakeup(s->queue)
enable interrupt;
}else
enable interrupt;
}
用TestAndSet和Swap来实现
void P(semaphore *s){
while(TS(s->flag));//当s->flag为0
s->value--;//申请
if (s->value<0){//资源不够,进入队列等待
asleep(s->queue)
s->flag=0;
goto CPU dispatcher;
}else//资源够
s->flag=0;
}
-3-3:使用sem和pv实现进程互斥
Var mutex: semaphore=1;
(临界区要互斥访问)
通过sem和pc操作来实现进程同步
无论P1再快,它会在等待先动作完成,V操作后,才会进行后动作
回到一开始的例子:售票
就是只有:关车门后才会启动车子,只有到站才能开车门
下面介绍具体的几个算法:
例1:生产者和消费者的例子:
一共有k个箱子,生产者申请一个箱子后,进行生产物品,消费者申请物品,并且释放箱子
在这里,我们的共享变量是箱子,所以在在这里就需要PV操作帮我们去维护
在这里,我们需要:1,一个互斥访问信号量,一个表示箱子的数量的信号量,一个表示物品数量的信号量
Program producers_consumers;
Var B:Array[0,…,k-1]Of item;
S1,S2,mutex:semaphore;
in,out:0..k-1;
代码:
Procedure producer
cycle
produce a product
P(S1);
P(mutex);
B[in]:=product;
in:=(in+1)mod k;
V(mutex);
V(S2)
end
Procedure consumer
cycle
P(s2);
P(mutex);
x:=B[out];
out:=(out+1)mod k;
V(mutex);
V(S1);
consume x;
end;
例子2:读者和写者问题(对同一个资源的读写)
要求:RR可以同时,WW,RW不能同步
方法一:
不同时RR,改进:
专门定义一个read_count:
Var mutex:semaphore; (initial value is 1){
// Reader:
P(mutex);
read_count:=read_count+1;
If read_count=1 Then
P(r_w_w);
V(mutex);
{读操作}
P(mutex);
read_count:=read_count-1;
If read_count=0 Then
V(r_w_w);
V(mutex);
}
一个read_count变量,两个信号量:mutex实现read_count互斥访问,一个r_w_w实现Rw,WW不可以同时
一个问题,读者源源不断，read_count不归0，写者会被饿死。
策略：一旦有写者等待，新到达读者等待，正在读的读者都结束后，写者进入。
例子3:哲学家就餐
对于哲学家,他们:
Do{
思考
取左叉，取右叉
进食
放左叉，放右叉
}While(1)
只有他们拿到了餐叉才能进食,餐叉是共享的资源
最简单,但是会出问题(5个哲学家):
var fork : array [0…4] of semaphore;
fork [0], fork [1], fork [2], fork [3], fork [4] :=1;
process PH ( i) begin
repeat
think;
P (fork [i]);
P(fork [(i+1)mod 5]);
eat;
V(fork[ i]);
V(fork[(i+1) mod 5]);
end;
会出现死锁的情况:每个人都拿了左边的叉子
所以进一步改进:只有能同时拿到两个才拿,不然就释放然后去等待
针对等待的人,加入一个st状态组数去记录每个人的状态,同时加入一个等待队列,所以只有!!:If (state[I]=hungry) and (state[(I-1)mod 5]!=eating) and (state[(I+1)mod 5]!=eating)
才可以去吃,取餐叉
在这里state数组是共享的变量,需要一个锁来实现互斥访问,
代码:
Repeat
思考
P(mutex);
state[I]:=hungry;
test(I);
V(mutex);
P(self[I]);
取左叉，取右叉；
进食
放左叉，放右叉；
P(mutex);
state[I]:=thinking;
test((I-1)mod 5);
test((I+1)mod 5);
V(mutex)
Until false;
详细的程序:
Program dining_philosophers
var state:array[0..4]of (thinking,hungry,eating);//记录状态
self:array[0..4]of semaphore;//
mutex:semaphore;
procedure test(I:0..4)
begin
if (state[I]=hungry)and
(state[(I-1)mod 5]<>eating)
and(state[(I+1)mod 5]<>eating) then
begin state[I]:=eating;
V(self[I])// 满足条件,就释放它,允许他去取餐叉
end
end;
Procedure philosopher(I:0..4)
begin
cycle
{thinking}//思考
P(mutex);//互斥访问
state[I]:=hungry;//标记
test(I);//尝试看看自己可以取餐叉吗
V(mutex);//出临界区
P(self[I]);//表示想去吃,(如果test有v操作,才会进入下面,不然就只有阻塞)
pick_up_fork(I); //取左
pick_up_fork((I+1)mod 5);//取右
{Eating};
put_down_fork(I); //放左
put_down_fork((I+1)mod 5); //放右
P(mutex); //进入临界区
state[I]:=thinking;//标记状态
test((I-1)mod 5);//去尝试唤醒左右
test((I+1)mod 5);
V(mutex);//退出临界区
end
end
还是有可能出现:一个人的左边右边来来回回交替吃饭,让中间的人直接饿死,等等其他的情况,所以可以加入一个count,5个人最多允许4个人去申请餐叉,可以一定的去解决
例子4:吸烟者问题:
3个供应:x提供tobacco and match;y提供match and wrapper;z提供:wrapper and tobacco.
3个消费:A::占用match and wrapper;B::占用wrapper and tobacco.;C::占用tobacco and match;.
要求:
XYZ同时只有一个可以生产,XYZ只有一个消费后再生成
S:让XYZ互斥访问
下面介绍SP,SV:
一、Simultaneous P - operation（同时 P 操作）
原理：SP(S₁,t₁,d₁;...;Sₙ,tₙ,dₙ) 用于同时对多个信号量进行操作。首先检查条件 if S₁>=t₁ and... and Sₙ>=tₙ ，即每个信号量 Sᵢ 的值是否大于等于对应的阈值 tᵢ 。若满足，就执行 for I:=1 to n do Sᵢ:=Sᵢ - dᵢ ，将每个信号量的值减去对应的 dᵢ ，表示获取相应资源。若不满足，就把执行进程放入第一个不满足条件（Sᵢ<tᵢ ）的信号量的等待队列，并把程序计数器设为 SP 操作开始处，以便进程被唤醒时重新检查条件。
作用：可用于确保进程一次性获取多个资源，避免因部分资源获取失败导致的死锁等问题，比如在哲学家就餐问题中，可用于让哲学家同时获取左右两边叉子对应的信号量 。
二、Simultaneous V - operation（同时 V 操作）
原理：SV(S₁,d₁;...;Sₙ,dₙ) 中，通过 for(i = 1; i <= n; i++) Si = Si + di; 对多个信号量同时进行增加操作，即释放资源。然后 Remove all processes waiting in the queue associated with Si into ready queue; 把等待在这些信号量相关队列中的进程移到就绪队列，唤醒等待进程。
作用：用于同时释放多个资源，并唤醒因等待这些资源而阻塞的进程，协调进程间资源的释放与获取 。
-3-4:CCR
因为PV过于底层,容易用错<可以使用region V when B do S
执行S条件:没有其它进程处于与V相关的条件临界区中,进入S时B为true
当然CCR和PV效果等价,但是效率比较低
举例:
简单批处理读入->执行->打印,三者同步
PROGRAM batch;
{定义缓冲区类型，用于实现生产者-消费者模式的环形缓冲区}
TYPE buffer=RECORD
slots: ARRAY[0..n-1]of T; {存储数据的数组，n为缓冲区大小}
head,tail: 0..n-1 initial (0,0); {head指向缓冲区头部，tail指向缓冲区尾部，初始都为0}
size: 0..n initial (0); {缓冲区当前元素数量，初始为0}
END;
{声明两个缓冲区实例，分别存储卡片图像和行图像}
VAR inbuff: buffer(cardimage); {输入缓冲区，存储从读卡机读取的卡片图像}
outbuff: buffer(lineimage); {输出缓冲区，存储待打印的行图像}
{将缓冲区声明为共享资源，用于进程同步}
RESOURCE ib: inbuff; ob: outbuff;
COBEGIN {并发执行多个进程}
{读卡进程：从读卡机读取卡片并放入输入缓冲区}
PROCESS reader;
VAR card: cardimage
LOOP
Read card from cardreader; {从物理读卡机读取卡片数据}
{临界区：访问输入缓冲区，需要满足缓冲区未满的条件}
REGION ib WHEN inbuff.size<n DO
inbuff.slots[inbuff.tail]:=card; {将卡片数据放入tail指向的位置}
inbuff.size := inbuff.size+1; {缓冲区元素数量加1}
inbuff.tail := (inbuff.tail+1) MOD n; {tail指针循环后移一位}
ENDDO
ENDLOOP
ENDPROCESS
{处理进程：从输入缓冲区取卡片，处理后放入输出缓冲区}
PROCESS executer;
VAR card:cardimage; {临时存储从输入缓冲区取出的卡片}
line:lineimage; {临时存储处理后生成的行数据}
LOOP
{临界区：访问输入缓冲区，需要满足缓冲区非空的条件}
REGION ib WHEN inbuff.size>0 DO
card := inbuff.slots[inbuff.head]; {从head位置取出卡片数据}
inbuff.size := inbuff.size-1; {缓冲区元素数量减1}
inbuff.head := (inbuff.head+1)MOD n {head指针循环后移一位}
ENDDO
Process card and generate line {处理卡片数据，生成行数据}
{临界区：访问输出缓冲区，需要满足缓冲区未满的条件}
REGION ob WHEN outbuff.size<n DO
outbuff.slots[outbuff.tail] := line; {将行数据放入输出缓冲区tail位置}
outbuff.size := outbuff.size+1; {输出缓冲区元素数量加1}
outbuff.tail := (outbuff.tail+1)MOD n; {输出缓冲区tail指针循环后移}
ENDDO
ENDLOOP
ENDPROCESS
{打印进程：从输出缓冲区取行数据并打印}
PROCESS printer;
VAR line:lineimage; {临时存储从输出缓冲区取出的行数据}
LOOP
{临界区：访问输出缓冲区，需要满足缓冲区非空的条件}
REGION ob WHEN outbuff.size>0 DO
line := outbuff.slots[outbuff.head]; {从输出缓冲区head位置取出行数据}
outbuff.size := outbuff.size-1; {输出缓冲区元素数量减1}
outbuff.head := (outbuff.head+1)MOD n; {输出缓冲区head指针循环后移}
ENDDO
Print line on lineprinter; {将行数据打印到物理打印机}
ENDLOOP
ENDPROCESS
COEND.
条件临界区的实现效率是比较低的
1,这主要是条件表达式b的计算，由于b中可能包含进程局部信息，每个欲进入条件临界区的进程必须自己计算b的值,而不能由调度程序统一计算．
2,因为进入条件临界区必须同时满足互斥和b为真两个条件，任何一个条件不满足都将使进程等待，这样在条件临界区的入口处会形成一个等待队列．
3,当处于条件临界区内的进程执行完s后，全局变量将发生变化，可能使某些条件临界区语句的b变为真，这时需要唤醒等待进程并由被唤醒的进程重新计算其b的值，而计算结果有可能仍为假，进程将重新回到等待状态．本质上来说，这也是一种忙式等待．
