一、进程的并发执行
并发执行进程间存在各种制约关系。其中，直接制约关系：一个进程依赖于另一个进程的消息或信号，进程的同步被用于解决进程间的直接制约关系。间接制约：各并发的进程速度受公有资源约束，进程的互斥用于解决该关系。
————
1、与时间有关的错误
引用变量集：某个进程需要读取的变量集合。
改变变量集：某个进程需要保存或改变的变量集合。
变量集：某个进程的引用变量集和改变变量集的统称。
无关进程：在不同变量集上操作的进程，即他们的变量集交集为空。
交互进程：进程的变量集的交集不为空。
交互式进程在执行中共享了公共变量，由于运行时间、进度的不同，往往会导致进程不再具有可再现性，而这种错误往往与时间有关，因此称为与时间有关的错误。
——————
2.Bernstein条件（解决与时间有关的错误）
如果并发执行的各程序段中的语句或指令满足Bernstein条件，则并发执行不影响封闭性和可再现性。
Bernstein的内容：
设Pi是一个进程，R（Pi）是Pi的引用变量集，W（Pi）是Pi的改变变量集，对于进程P1和进程P2只要满足：
①R（P1）∩W（P2）=∅
②R（P2）∩W(P1)＝∅
③W（P1）∩W（P2）=∅
则并发执行与时间无关
同理对于两个相邻语句S1，S2，只要满足上述三个条件也可以并发执行（将S替换为P）
————
3、临界资源与临界区
临界资源：在系统中，有些资源，只能同时被一个进程所使用，这类资源叫做临界资源，有硬件的也有软件的。
临界区：把使用到临界资源的那一段程序称之为临界区或临界部分。
在程序的描述中，用下列标准形式来描述临界区：
when <类名> do <临界区> od被定义为相同类名的所有临界区处于同一个临界区集合，使用到同一临界资源。
因此类名相同的临界区集合中只能有一个临界区正在被执行。
可见，要求进入同一临界区集合的进程之间构成互斥关系。
好的解决临界区问题方案的四个条件：
①不能让一个进程无限停留在临界区内
②不应对CPU的数量和速度做任何假设
③不能强迫一个进程无限期地等待进入临界区
④当没有进程在临界区时，在剩余区运行的任意程序不得妨碍正在等待进入的其他进程的发展。
——————
二、进程的互斥
指的是对于某公有资源，如果一个进程正在使用，其他想使用该资源的进程就必须等待。
1、软件实现方法
①严格轮换法
在代码中，使多个进程严格地进出临界区。
可以保证进程互斥访问临界资源，但被强制以交替的次序轮流进入会造成忙等待和资源利用不充分的问题。
②Dekker算法
③Peterson算法
每个进程有一个flag，flag==true表明其要求进入临界区。还设有一公共变量turn，turn=i表示进程i可以进入。
一个进程要进入临界区要先判断其他进程不要求进入或不在临界区
————————
2、硬件实现方法
①关中断
单处理机计算机中，若一个进程访问临界资源，就关闭所有中断，访问完成后，再打开中断，就保证了进程在访问临界资源时不会切换到其他进程，其他进程也就不会进入该临界区。
优点是简单。缺点：不适合多CPU系统；关中断使用不当会造成严重后果。
②使用测试和设置指令
测试和设置指令是一条机器指令，不会被中断。
设置一个刚刚变量use初始化为0，use=0时表示资源未被占用。use=1表示资源被占用。
进程执行时，测试并设置变量，当use=0时，设置use为1，表示该进程获得了临界资源使用权；当use为1，重复测试该指令，直到其为0.
使用完临界资源退出时，将use设置为0。
优点：方便地保证多个进程互斥进入临界区
缺点：造成忙等待的情况。
③使用对换指令
对换指令（Swap）也是一条不会被中断的原子指令，功能是交换两个字的内容。
实现方法：
使用一个use，等于0时表示未占用，等于1表示占用。再定义一个局部变量k初始化为1.进入临界区前use与k交换值。若交换后k=0，表示未占用则进入临界区。若交换后k=1，则继续交换直到k=0
也会造成忙等待。
三、进程的同步
1、同步的概念
两个或多个进程为了合作完成同一个任务，基于某个条件，在执行速度或某些确定的时序点必须互相协调，在进程关系上存在依赖或相互依赖的关系。例如，一个进程在执行到某一个节点时，必须要收到另一个进程完成到某种程度的信号才能继续执行，否则只能等待。
——————
2、同步实现的方法
在下面的方法中，进程在等待某个条件发生时将阻塞而不是忙等待。
通过进程之间的通信原语来完成：sleep和wakeup。
举例说明：
有两个进程，进程1（其中有语句S1）和进程2（其中有语句S2）。要求S1执行完成才能开始S2的执行。若进程2已经执行到S2而S1还未执行，则进程2将使用sleep使自己阻塞。当进程1完成S1后进程1使用wakeup将进程2唤醒。
——————
3、生产者-消费者
举例说明：存在两个程序，程序1和程序2，他们共用一个固定大小的缓冲区。程序1不断形成信息保存到缓冲区，而程序2不断从缓冲区调用、取走信息。
要达成这种关系，要满足以下两点：
①缓冲区至少有一条消息消费者才能取走，否则将阻塞，知道生产者放入消息后将其唤醒。
②缓冲区未满，生产者才能放入消息，否则生产者阻塞，等待消费者取走消息后将其唤醒。