进程同步
进程同步机制
进程同步机制：利用他们保证程序执行的可再现性
进程同步的基本概念：某进程未获得合作进程发来的消息之前应该进程等待，消息到来之后方可继续合作关系
进程间两种形式的制约关系
间接相互制约关系 — 源于资源共享
直接相互制约关系 — 源于进程合作
临界资源：互斥访问
进程间采取互斥方式，实现对资源的共享
生产者消费者问题：
生产者进程和消费者进程都以异步方式运行，但它们之间必须保持同步。
把一次仅允许一个进程访问的资源叫做临界资源
临界区
每个进程中访问临界资源的那段代码
对欲访问的临界资源进行检查
若此刻未被访问，设正在访问的标志 ……进入区
访问临界资源 ……临界区
将正在访问的标志恢复为未被访问的标志 ……退出区
其余部分 ……剩余区
进程互斥：两进程不能同时进入访问同一临界资源的临界区
同步机制应遵循的规则
空闲让进
忙则等待
有限等待
让权等待
信号量机制
整型信号量
定义：整型量，除初始化外，仅能通过两个原子操作来访问
P操作 wait(S):
While (S<=0) do no-op;
S–;
V操作 signal(S):
S++;
P、V操作是原子操作，不可中断。
记录型信号量
引入整型变量value(代表资源数目)、进程链表List (链接所有等待进程)
用S.value的初值表示系统中某种资源的数目。
记录型数据结构：
1 | typedef struct{ |
对信号量S的一次P操作意味着进程请求一个单位的该类资源，因此S.value–，表示资源数减1，当S.value＜0时表示该类资源已分配完毕，因此进程应调用block原语进行自我阻塞，主动放弃处理机，并插入该类资源的等待队列S.L中。
对信号量S的一次V操作意味着进程释放一个单位的该类资源，因此需要执行 S.value++，表示该资源数加1，若加1后仍是 S.value≤0，表示依然有进程在等待该类资源，因此应调用wakeup原语幻想等待队列中的第一个进程。
信号量>0，代表可用资源的数量
信号量<0，代表由于申请信号量，代表的资源而阻塞的进程数量
遵循了“让权等待”原则，不会出现“忙等”现象
AND型信号量
ADN型信号量主要针对的是一个进程需要获取两个或更多的共享资源执行任务时的问题。
基本思想：对若干个临界资源的分配采取原子操作的方式
- 要么把它所请求的资源全部分配到进程，要么一个也不分配。为此，在wait中加入了一个“AND”条件，故称为AND同步，或称为同时wait操作，即 Swait
信号量集
信号量集主要针对的是执行进程时一次需要N个单位的某类临界资源的问题
对AND型信号量机制加以扩充，对进程所申请的所有资源以及每类资源不同的资源量需求，在一次P、V原语操作中完成申请或释放。
进程对信号量Si的测试值不再是1，而是该资源的分配下限ti，即要求Si>=ti。一旦允许分配，进程对该资源的需求值为di，即表示资源占用量，进行Si:=Si-di的操作，对应的Swait和Ssignal格式为：
Swait(S1,t1,d1,...,Sn,tn,dn);Ssignal(S1,d1,...,Sn,dn);
Swait(S,d,d)：此时信号量集中只有一个信号量S，但允许它每次申请d个资源，当现有资源数量少于d时，不予分配。
Swait(S,1,1)：此时信号量集已蜕化为一般的记录型信号量（S>1时）或互斥信号量（S=1）。
Swait(S,1,0)：当S>=1时，允许多个进程进入某特定区；当S变为0后，将阻止任何进程进入特定区，相当于一个可控开关。
信号量的应用
实现进程互斥：
设置mutex为互斥信号量，初值为1，取值范围为（-1,0，1）。
当mutex = 1 时，表示两个进程皆未进入互斥的临界区
当mutex = 0 时，表示有一个进程进入临界区运行，另一个必须等待，挂入阻塞队列
当mutex = -1 时，表示有一个进程正在临界区运行，另外一个进程因等待而阻塞在信号量队列中，需要被当前已在临界区运行的进程退出时唤醒。
wait(mutex)和signal(mutex)操作必须成对出现，缺少P（mutex）将会导致系统混乱，不能保证对临界资源的访问，缺少V（mutex）将会使临界资源永远不被释放，从而使因等待该资源而阻塞的进程永远不能被唤醒。
信号量机制实现前驱关系
每一对前驱关系都是一个进程同步问题
- 要为每一对前驱关系各设置一个同步变量
- 在“前操作”之后对相应的同步变量执行V操作
- 在“后操作”之前对相应的同步变量执行P操作
例如：
实现S1执行后执行S2
进程P1：S1； signal（S）； (S为P1,P2共用的信号量)
进行P2：wait(S); S2；
信号量机制实现同步关系：
p1，p2两进程因合作完成一项任务而共用一个变量x。进程p2将处理结果送入x；进程p1将x的结果打印。
经典的进程同步问题
生产者消费者问题
相互合作关系的一种抽象
问题描述：
一组生产者进程和一组消费者进程共享一个初始为空、大小为 n 的缓冲区，只有缓冲区没满时，生产者才把消息放入缓冲区，否则必须等待；
只有缓冲区不空时，消费者才能从中读取消息，否则必须等待。由于缓冲区是临界资源，它只允许一个生产者放入消息，或一个消费者从中取出消息。
可利用记录型信号量解决生产者—消费者问题：
- 可利用互斥信号量mutex实现诸进程对缓冲池的互斥使用，初值为1；
- 信号量 full 用于记录当前缓冲池中的“满”缓冲区数，初值为 0；
- 信号量 empty 用于记录当前缓冲池中“空”的缓冲区数，初值为 n；
描述如下：
加锁信号量的顺序不能打乱，否则容易出现死锁，也就是P(mutex)需要跟在P(full);前面
利用AND信号量解决生产者—消费者问题：
使用Swait(empty,mutex)代替wait(empty)，wait(mutex)，Ssignal(empty,mutex)代替signal(empty)，signal(mutex)
full和mutex也是一样
例题：
描述：
桌子上有一个盘子，每次只能向其中放入一个水果。
爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专吃盘子中的橘子，女儿专等吃盘子中的苹果。
只有盘子为空时，爸爸或妈妈才可以向盘子中放一个水果；仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出。
分析：
爸爸和妈妈是互斥关系，爸爸和女儿、妈妈和儿子是同步关系，而且这两对进程必须连起来，儿子和女儿之间没有互斥和同步关系，因为他们是选择条件执行。
信号量 plate 表示互斥信号量，用于确定是否可以往盘子中放水果，初值为 1 表示允许放入一个；
信号量 apple 表示盘中是否还有苹果，初值为 0表示没有不许取；orange 表示盘中是否有橘子，初值同样为 0，orange=1 表示盘子中由橘子允许取
哲学家进餐问题
问题描述：
一张圆桌上坐着5名哲学家，每两名哲学家之间的桌子上摆着一根筷子，两根筷子之间是一碗米饭。
哲学家倾注毕生精力于思考和进餐，哲学家思考时不影响其他人。只有当哲学家饥饿时，才试图拿起左、右两根筷子——一根一根地拿起。
若筷子已在他人手上，则需要等待。饥饿地哲学家只有同时拿到了两根筷子才能开始进餐，进餐完毕，放下筷子继续思考
分析：
5 名哲学家与左右邻座对其中间的筷子的访问时互斥关系。
显而易见，5 个哲学家对应5 个进程，问题解决的关键就是如何让一名哲学家拿到左右两根筷子而不造成死锁或饥饿现象
解决方法有两个：一是让他们同时拿两根筷子；二是对每名哲学家的动作制定规则，避免饥饿或死锁现象的发生。
信号量设置：互斥信号量数组 chopstick[5]={1,1,1,1,1}，用于对 5 个筷子的互斥访问；哲学家编号顺序：0~4，哲学家 I 左边筷子的编号为 i，哲学家右边筷子的编号为(i+1)%5。
使用记录型信号量：
使用AND信号量
1 | Swait(chopstick[(i+1) % 5], chopstick[i]); |
读者写者问题
问题描述与分析
一个数据文件或记录可被多个进程共享。
只要求读文件的进程称为“Reader进程”，其它进程则称为“Writer进程”。允许多个进程同时读一个共享对象，但不允许一个Writer进程和其他Reader进程或Writer进程同时访问共享对象
“读者——写者问题”是保证一个 Writer 进程必须与其他进程互斥地访问共享对象的同步问题。
互斥信号量wmutex: 实现 Reader 与 Writer
进程间在读或写时的互斥
整型变量Readcount：表示正在读的进程数目;
以Readcount为例：
由于只要有一个 Reader 进程在读，便不允许 Writer 进程写。
∴仅当Readcount=0，即无 Reader 进程在读时，Reader
才需要执行Wait(wmutex)操作。若Wait(wmutex)操作成功，Reader
进程便可去读，相应地，做Readcount+1操作。
使用记录型信号量解决读者写者问题
使用信号量集机制解决读者写者问题
Swait(mx, 1, 1; L, RN, 0)语句表示仅当既无writer进程在写(mx=1)，又无reader进程在读(L=RN)，writer进程才能进入临界区写。
Swait(mx, 1, 0)语句起着开关的作用。只要无writer进程进入写，mx=1，reader进程就都可以进入读。但只要一旦有writer进程进入写时，mx=0，则任何reader进程就都无法进入读。
