对于非科班出身的我，，，最近自学操作系统做了一些进程同步的笔记，写出来，希望能对大家有帮助，我是参照哈工大张英涛老师的视频和汤子瀛的书写的：
进程与进程之间的合作机制：
信号量机制！！！
信号量是一种数据结构。
信号量的值与相应资源的使用情况有关。
信号量的值仅由原语P、V操作改变
（1）整型信号量
整型数 S <=0 代表资源被占用，不可用 S>0代表空闲可用
P操作(wait)原语
V操作（signal）原语
|
Wait(S) While S<=0 do no-op(无行为) S:=S-1; //可用啦，那我就用咯 |
|
Signal(S) S:=S+1; |
wait(S) 和signal(S)是原子操作。
缺点：只要信号量小于等于0，不满足让权等待。就是不会先让其进入阻塞，把CPU让给别人用。
（2）记录型信号量（目前应用较广）
记录型结构，包含两个数据项：
|
Type semaphore = record Value:integer; L:lise of process; end |
S.value为资源信号量初值，是某类资源的数目；
value大于0 的时候代表可用资源数目
value<0时候，绝对值代表等待使用资源的进程个数。也就是扔进阻塞队列。
wait操作申请某一个单位资源
|
Procedure wait(s) Var S:semaphore; Begin S.value:=S.value-1; If S.value<0 then block(s,L); End |
signal操作：释放一个资源
|
Procedure signal(s) Var S:semaphore; Begin S.value = S.value+1; If S.value<=0 then wakeup(s,L) //这里小于0的话，说明还有进程在等待。 end |
当S.value=1则是访问临界资源，是互斥信号量。
死锁现象：
Pa pb
…… ……
wait(Dmutex) wait(Emutex)
wait(Emutex) wait(Dmutex)
…… ……
（3）AND型信号量
基本思想：将所需的资源一次性全部获取，使用后一次性全部释放。
|
Swait(s1,s2,..,sn) If s1>=1 and ... and sn>=1 then For i:=1 to n do Si:= si-1; End for Else 当发现第一个Si<1就把该进程放入阻塞等待队列，并将其程序计数器至于Swait操作的开始位置(也就是把下一条指令改下。) End if |
|
Ssignal(s1,s2,..,s3) For i:1 to n do Si := si +1; 将所有等待si的进程由等待队列取出放到就绪队列 End for |
用信号量能实现互斥：两个进程代码见下面
|
Var mutex:semaphore:=1; Begin Parbegin //从部分开始的代码 Process1:begin Repeat Wait(mutex); // P操作 信号量mutex Critical section Signal(mutex) Remainder section Until false; End
Process2:begin Repeat Wait(mutex); Critical section Signal(mutex); Reminder section Until false; end |
注意点：
wait(mutex) 和 signal(mutex) 必须成对出现。
经典的同步问题！！！！！！！！！！！！！！！
1、生产者-消费者问题
2、读者-写者问题
3、哲学家进餐问题
|
生产者-消费者问题 一组生产者进程生产产品给一组消费者消费。为使他们并发执行，设有一个n个缓冲区的缓冲池，生产者一次向一个缓冲区投入消息，消费者从一个缓冲区中取得消息。这是两个进程相互合作的模型。！
制约关系： （1）不允许消费者到一个空缓冲区中取数据 （2）不允许生产者向一个已满的缓冲区投入数据。 |
例如：输入时，输入进程是生产者，计算进程是消费者
输出时，计算进程是生产者，打印进程是消费者
这里用记录型信号量来解决生产者-消费者问题。区分下互斥量和信号量
（什么是记录型？用一个数据结构来表示，整型表示使用资源和等待进程数，队列表示阻塞队列）
（1）设有n个缓冲区，每个缓冲区存放一个消息，用互斥量mutex对缓冲池实现互斥访问。
所以这里第一个信号量是用来作为互斥用的，初值是1；;;;这是使得投入和取出这两个动作时互斥的，不能同时进行。！！！！
（2）用资源信号量empty和full分别表示缓冲池中空缓冲区及满缓冲区的数量。所以这里资源信号量是用来同步用的，empty初值是n,full初值是0。
|
Var mutex:semapjore:=1; Empty:semphore:=n; Full:semaphore:=0;
Buffer:array[0,...,n-1] of item; // 这里用数组形式，可以指明下一个数据存放位置用回环就好 In,out:integer:=0,0; //放入和取出的数据地址，就是数组的两个下表指向。
Procedure:begin Repeat …… Procedure an item nextp; // 生产下一个产品，就是产生一个数据 …… Wait(empty); // 申请成功则empty减一了呗 Wait(mutex); Buffer(in):=nextp; In:=(in+1) mod n; Signal(mutex); Signal(full); Until false; End
Consumer:begin Repeat Wait(full) Wait(mutex) Nextc := buffer(out); Out :=(out+1) mod n; Signal(mutex); Signal(empty); Consumer the item in nextc; //对应的，也有一个消费过程 Until false; End; |
注意点：
1：wait(mutex)和signal(mutex)必须成对出现。不过这里信号量的出现不是在同一个进程当中就是了。
2：这里mutex和empty full必须用mutex的类型变量把。不然也会出现同步问题。
3：这里P操作是不能颠倒的，否则会进入死锁，比如生产者应该先获取empty，因为在消费者那里也会对empty进行操作，。。所以一定要先锁定互斥量，再进行信号量，V操作倒是没有顺序要求。
2、哲学家进餐问题
有五个哲学家，他们的生活方式是交替进行思考和进餐。 哲学家们共用一个圆桌，有五张椅子，五个碗，五只筷子，所以一个科学家想吃饭应该同时拿起最近的左右筷子吃。所以要协调他们吃饭时间。 |
分析：筷子就是临界资源！在一段时间内只能有一个科学家使用。用一个信号量表示一个筷子，五个筷子就共有五个信号量，
var chopstick: array[0...4] of semaphore
每个信号量初始化为1；
用记录型信号量来解决
设第i个哲学家
|
Repeat Wait(chopstick[i])； Wait(chopstick[(i+1)mod 5]); // 由于这五个筷子是同个地位的，所以取哪个先都可以 Eat... Signal(chopstick[i]); Signal(chopstick[(i+1)mod 5]); Think; Until false; end |
但是，当五个哲学家同时饥饿，那么五个人同时拿起左边筷子，那么五个人就无限等待下去了。。。这就死锁了。
解决办法：
（1）至多四个人拿起左边筷子。。保证至少有一个人可以用餐，那么就能解决了。
（2）仅当左右两个筷子同时拿起才能进餐 类似AND型信号量
（3）规定奇数号的先拿起左边的，偶数号拿右边。。
用AND型信号量来解决哲学家问题：同一组人使用同一些东西。
var chopstick：array[0...4] ofsemaphore:={1,1,1,1,1};
|
Repeat Think; Swait( Chopstick[i] and chopstick[(i+1)mod 5]); Eat; Ssignal(Chopstick[i] and chopstick[(i+1)mod 5]); Think; Until false; end |
（3）读者-写者问题
|
一个数据文件或记录可被多个进程共享，其中，有些进程要求读，有些进程则要求写或修改。 把只要求读的进程 Reader进程 要求写修改的是Writer进程。 允许多个读者进程同时共享一个对象，不允许一个writer进程和多个Reader进程或Writer进程同时访问共享对象。 |
这里的共享对象不是临界资源，因为允许多个进程访问---读！
（1）为解决一个writer进程和reader进程互斥，设置一个互斥信号量Wmutex;
（2）设置一个整型变量Reader count表示正在读的进程数目。
（3）ReaderCount是可以被多个进程访问的临界资源，为它设置互斥信号量Rmutex;
（4）仅当Readercount = 0,表示无reader进程在读，Reader进程执行P操作。若P操作成功，Reader进程便可读，使得Readercount+1;其他Readercount的值就不需要P操作了。
记住Rmutex是为了保证多个线程访问Readercount个数同步问题才创建的！！
|
Var Rmutex,Wmutex:semaphore:= 1,1; Readercount:integer:=0; Begin Parbegin Reader:begin Repeat Wait(Rmutex); If (Readercount=0 then Wait(Wmutex)); Readercount++; Signal(Rmutex); Perform read operation; Wait(Rmutex); Readercount:=Readercount-1; If Readercount==0 then signal(Wmutex); Signal(Rmutex); Until false; End
Writer:begin Repeat Wait(Wmutex); Perform write operation; Signal(Wmutex); Until false; End Parend end
|