参考：https://www.bilibili.com/video/av31584226/?p=9
进程具有异步性的特征，异步性是指，各并发执行的进程以各自独立的，不可预知的速度向前推进。
回忆我们之前学习进程通信的时候的管道通信方式，如下图：
当时的一个特点就是：写进程必须把管道写满之后，读进程才能从管道中读取数据。
读进程和写进程并发地运行，由于并发必然导致异步性，因此“写数据”和“读数据”两个操作执行的先后顺序是不确定的。而实际应用中，又必须按照“写数据”->“读数据”的顺序来执行。如何解决这种异步问题，就是“进程同步”所讨论的内容。
同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系，进程间的直接制约关系就是源于它们之间的相互合作。（这里我觉得用我在java中学的线程同步模型理解起来就很快，就比如开了10个线程去计算一堆数据，开一个线程统计这10个线程的计算数据结果，那么就得等那10个线程执行完才能执行这统计的线程，这就是一种同步关系）
然后我们来聊一下进程互斥的东西：
进程的“并发”需要“共享”的支持，各个并发执行的进程不可避免的需要共享一些系统的资源，比如内存之类的。
而资源共享分为两种共享方式：
1.互斥共享 即一个时间段内只允许一个进程访问该资源
2.同时共享 即允许一个时间段内多个进程“同时”对它们进行访问（宏观上的同时，微观上可能是分时）
我们把一个时间段内只允许一个进程使用的资源称为临界资源。许多物理设备如摄像头，还有很多变量，数据等都属于临界资源。
对临界资源的访问，必须互斥地进行，亦称间接制约关系。进程互斥是指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待，当前访问临界资源的进程，释放该资源之后，另一个进程才能去访问临界资源。
对进程的互斥访问，逻辑上可以分为
1.进入区 加锁，其它进程不能进入
2.临界区 访问临界资源
3.退出区 释放锁，后其它进程可访问
4.剩余区 其他操作
进入区和退出区是负责实现互斥的代码段。
进程互斥需要遵循的原则：
1.空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区;
2.忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待;
3.有限等待。对请求访问的进程，应保证能在有限时间内进入临界区(保证不会饥饿) ;
4.让权等待。当进程不能进入临界区时，应立即释放处理机，防止进程忙等待（即进程处于等待状态却一直占用着处理机）。
下面是上面这部分内容的总结：
然后下一步看进程互斥的软件实现方法：
1.单标志法 2.双标志法 3.双标志后检查 4. peterson算法
1.单标志法。
算法思想:两个进程在访问完临界区后会把使用临界区的权限转交给另-一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予
turn的初值为0，即刚开始只允许0号进程进入临界区。（注意临界区和退出区！）
若P1先上处理机运行，则会一直卡在⑤。直到P1的时间片用完，发生调度，切换PO上处理机运行。代码①不会卡住PO,PO可以正常访问临界区，在PO访问临界区期间即时切换回P1，P1依然会卡在⑤只有PO在退出区将turn改为1后，P1才能进入临界区。
这样就满足了进程互斥的要求，即一个时间段内只允许一个进程访问该资源
turn表示当前允许进入临界区的进程号，而只有当前允许进入临界区的进程在访问了临界区之后，才会修改turn的值。也就是说，对于临界区的访问，一定是按P0→P1 > PO> P1....这样轮流访问。这种必须“轮流访问”带来的问题是，如果此时允许进入临界区的进程是PO，而PO一直不访问临界区，那么虽然此时临界区空闲，但是并不允许P1访问。
因此，单标志法存在的主要问题是:违背“空闲让进”原则。
（这个单标志法和我平时控制线程同步的方法很像啊，也就是一个共享信号量来传递信息）
2.双标志先检查法
算法思想:设置一个布尔型数组flag[]， 数组中各个元素用来标记各进程想进入临界区的意愿，比如“flag[0] = ture”意味着0号进程PO现在想要进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身对应的标志flag[i]设为true,之后开始访问临界区。
（意思就是那啥：你们都不上了我才上）
若按照①⑤②⑥③⑦..的顺序执行，PO 和P1将会同时访问临界区。因此，双标志先检查法的主要问题是:违反“忙则等待”原则。即一个进程占用了临界资源，你还来强占。
原因在于，进入区的“检查”和“上锁”两个处理不是一气呵成的。“检查” 后，“上锁”前可能发生进程切换。（如果12和56是原子操作，那么就没啥问题了）
3.双标志后检查法
即现上锁，后检查，1和2的顺序反了过来
意思就是，我先占着位置，你们都不用的时候我再进去。
若按照①⑤②...的顺序执行，PO 和P1将都无法进入临界区
因此，双标志后检查法虽然解决了“忙则等待”的问题，但是又违背了“空闲让进”和“有限等待”原则，会因各进程都长期无法访问临界资源而产生“饥饿”现象。
上面的全部问题都是由于进程的异步性导致的，即执行顺序的不一定性。
4.然后来看peterson算法
算法思想:双标志后检查法中，两个进程都争着想进入临界区，但是谁也不让谁，最后谁都无法进入临界区。Gary L. Peterson想到了一种方法，如果双方都争着想进入临界区，那可以让进程尝试“孔融让梨”，主动让对方先使用临界区，
下面是代码：
大家可以试着用123678或者162378顺序运行，会发现决定权在于谁最后一次运行turn的赋值，这样就不会忙时等待了。
Peterson算法用软件方法解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待三个原则，但是依然未遵循让权等待的原则。（即比如1进入3后，2还在8中，2一直占着处理机在那等待）
Peterson算法相较于之前三种软件解决方案来说，是最好的，但依然不够好。
下面是一个小总结：
接着我们来看进程互斥的硬件实现方法：
1.中断屏蔽方法
2.TestAndSet(TS指令/TSL指令)
3.Swap指令（XCHG指令）
1.中断屏蔽方法
它是利用“开/关中断指令”实现（与原语的实现思想相同，即在某进程开始访问临界区到结束为止都不运行被中断，也就是不能发送进程切换。因此也不可能发生两个同时访问临界区的情况）（原语的执行过程也是不能被中断的）
即 先关中断，关中断后即不允许当前进程被中断，也必然不会发生进程切换，然后进入临界区，直到当前进程访问完临界区，再执行开中断指令，才有可能有别的进程上处理机访问临界区。
优点：简单，高效
缺点：1.不适合用于多处理机；因为中断是针对单处理机而言的，你关了中断，只是关了这一个处理机上的中断，而其它处理机是可以访问这个临界区的。
2.只适用于操作系统内核进程，不适用于用户进程；因为开/关中断指令只能运行在内核态，这组指令如果能让用户随意使用会很危险；
2.TS指令/TSL指令
TestAndSet，简称TS指令，也有地方称为TestAndSetLock指令，或TSL指令。TSL指令是用硬件实现的，执行的过程不允许被中断，只能气呵成。以下是用C语言描述的逻辑
分析过程：
若刚开始lock是false,则TSL返回的old值为false, while 循环条件不满足，直接跳过循环，进入临界区。若刚开始lock是true,则执行TLS后old返回的值为true, while 循环条件满足，会一直循环，直到当前访问临界区的进程在退出区进行“解锁”。
（这个就很像java中CAS：compareandswap实现的自旋锁，如果有其它人在用，我就占着处理机等待，等你们都用完了我再上）
相比软件实现方法，TSL 指令把“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作。优点:实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞;适用于多处理机环境（因为操作了总线，具体我也不清楚，网上的解释感觉都不到位，我目测的理解就是所有处理机都必须通过总线去操作一样东西，而我操作之后就把总线关了，你们都进不来） 缺点:不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”（也就是自旋）
3.Swap指令
有的地方也叫Exchange指令，或简称XCHG指令。Swap指令是用硬件实现的，执行的过程不允许被中断，只能-气呵成。以下是用C语言描述的逻辑
（也就是我一直等到你们都不来了我才来）
逻辑上来看Swap和TSL并无太大区别，都是先记录下此时临界区是否已经被上锁(记录在old变量上)，再将，上锁标记lock设置为true,最后检查old，如果old为false则说明之前没有别的进程对临界区上锁，则可跳出循环，进入临界区。
优点:实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞;适用于多处理机环境缺点:不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”。
下面是上面知识点的简单总结：
接着，来到我们的重点：信号量机制
复习回顾+思考:之前学习的这些进程互斥的解决方案分别存在哪些问题?
进程互斥的四种软件实现方式(单标志法、双标志先检查、双标志后检查、Peterson算法)进程互斥的三种硬件实现方式(中断屏蔽方法、TS/TSL指令、Swap/XCHG指令)
1.在双标志先检查法中，进入区的“检查”、“上锁”操作无法一气呵成，从而导致了两个进程有可能同时进入临界区的问题;
2.所有的解决方案都无法实现“让权等待”
1965年，荷兰学者Diikstra提出了一种卓有成效的实现进程互斥、同步的方法- -信号量机制（迪杰斯特拉最短路径算法）
下面是简单的概述：
用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便的实现了进程互斥、进程同步。
信号量其实就是一个变量(可以是一个整数，也可以是更复杂的记录型变量)，可以用一个信号量来表示系统中某种资源的数量，比如:系统中只有一.台打印机，就可以设置-一个初值为1的信号量。
原语是一种特殊的程序段，其执行只能一气呵成，不可被中断。原语是由关中断/开中断指令实现的。软件解决方案的主要问题是由“进入区的各种操作无法--气呵成”，因此如果能把进入区、退出区的操作都用“原语”实现，使这些操作能“一气呵成”就能避免问题。
一对原语:wait(S)原语和signal(S)原语，可以把原语理解为我们自己写的函数，函数名分别为wait和signal,括号里的信号量S其实就是函数调用时传入的一个参数。
wait、signal 原语常简称为P、V操作(来自荷兰语proberen和verhogen)。因此，做题的时候常把wait(S)、signal(S) 两个操作分别写为P(S)、V(S)
信号量机制又分为整型信号量和记录型信号量
然后我们先来介绍 整型信号量
用一个整型数的变量作为信号量，用来表示系统中某种资源的数量。
与普通整数变量的区别：对信号量的操作只有三种，即初始化、P操作、V操作
比如：某计算机系统中有一台打印机。。代码如下：
看wait这个，由于原语的存在，保证了“检查”和“上锁”的一气呵成，避免了并发、异步导致的问题（可以和双标志先等待发作对比）
但是，它有存在的问题：不满足“让权等待”原则，会发生“忙等”。结合下面这个图就可以加以理解： 刚开始S=1，P0获得打印机资源，P1此时进入，由于S<=0，所以一直在那里占用着cpu资源而不干事。
（在while等待的时候由于原语问题，所以不可被中断，即进程不会被切换）
然后我们来看记录型信号量（重点）
代码如下：
解析：
wait(S)、signal(S) 也可以记为P(S)、V(S)，这对原语可用于实现系统资源的“申请”和“释放”。
S.value的初值表示系统中某种资源的数目。
对信号量S的一次P操作意味着进程请求一个单位的该类资源，因此需要执行S.value--, 表示资源数减1，当S.value<0时表示该类资源已分配完毕，因此进程应调用block原语进行自我阻塞(当前运行的进程从运行态阻塞态)，主动放弃处理机，并插入该类资源的等待队列S.L中。可见，该机制遵循了“让权等待”原则，不会出现“忙等”现象。
对信号量S的一次V操作意味着进程释放一个单位的该类资源，因此需要执行S.value++,表示资源数加1,若加1后仍是S.value<= 0，表示依然有进程在等待该类资源，因此应调用wakeup原语唤醒等待队列中的第一个进程(被唤醒进程从阻塞态>就绪态)。
前一个进程释放一个资源就唤醒一个新的进程进行使用
（没错，看到的第一眼就理解了，实在是太像java中的AQS了，我记得这样有个缺点是阻塞态到就绪态的相互转换比较消耗cpu资源，如果存在大量的转换的话就更可怕了，这比较适合切换频率比较低的情况，所以如果等待时间比较短的话，使用前面的自旋锁还是比较好的，等一下下就ok了，这些纯属个人见解，视频中没有提及），如果不理解的话建议看看视频的例子进行详细理解。
下面是信号量机制的总结：关键在于记录型信号量（其中PV写反了）
接下来也是信号量机制，是用信号量机制实现进程互斥、同步、前驱关系。感觉互斥前面已经讲了，就是两个进程怎么样避免同时访问临界资源。就下面这样的组织形式就ok了。
注意这里设置的信号量的值为1.
对不同的临界资源需要设置不同的互斥信号量。
P、V操作必须成对出现。缺少P(mutex)就不能保证临界资源的互斥访问。缺少V(mutex)会导致资源永不被释放，等待进程永不被唤醒。
然后讲讲进程同步：
前面已经说了基本概念，进程同步的目的就是为了确保程序执行的有序性。也就是进程间的各个代码段有序地推进。
如：
我们要怎么实现代码4运行在代码2之前呢？
用信号量实现进程同步:
1.分析什么地方需要实现“同步关系”，即必须保证“一前一后”执行的两个操作(或两句代码)
2.设置同步信号量S, 初始为0
3. 在“前操作”之后执行V(S)
4.在“后操作”之前执行P(S)
如下图：
这里注意信号量的值为0.
我们目的是要代码2执行后才能执行代码4：那么它是怎么确保的呢？
下面的分析一定要理解清楚：
若先执行到V(S)操作，则S++后S=1。 之后当执行到P(S)操作时，由于S=1，表示有可用资源，会执行S--，S的值变回0,P2进程不会执行block原语，而是继续往下执行代码4。
若先执行到P(S)操作，由于S=0，S-- 后S=-1,表示此时没有可用资源，因此P操作中会执行block原语，主动请求阻塞。之后当执行完代码2，继而执行V(S)操作，S++， 使S变回0,由于此时有进程在该信号量对应的阻塞队列中，因此会在V操作中执行wakeup原语，唤醒P2进程。这样P2就可以继续地执行代码4了.
其实这些我们理解后自己就很容易自己推出来了。
然后看完了信号量实现进程的互斥和同步，接着来看信号量实现前驱关系。
什么是前驱关系呢？
进程P1中有句代码S1，P2 中有句代码S2.... P6中有句代码S6。这些代码要求按如下前驱图所示的顺序来执行:
前驱关系就是多进程多代码直接的顺序控制，如上图就是s2必须执行在s1后，s6必须s4,s5,s6都执行完后才能执行，其实就是多重的同步关系。。
其实每一对前驱关系都是一个进程同步问题(需要保证一前一后的操作)因此，
1.要为每一对前驱关系各设置一个同步变量
2.在“前操作”之后对相应的同步变量执行V操作
3.在“后操作”之前对相应的同步变量执行P操作
如下图：
这就是我们给每一对控制加上的信号量。
然后来看我们的代码：
就比如看P6里面的S6的代码：有图可知它得再3，4，5执行后才能执行，由前面理解的规则，即后操作前加P，即添加多个P，无论顺序，以为条件是需要同时满足。所以这样就达到了我们的进程多重同步控制的目的。
下面是这部分知识点的总结。
嗯，就到这里了，感觉和java的JUC超级像的，所以很多东西一看就懂了。
欢迎交流讨论。
