- 顺序程序设计
单个程序内部只有在前一个操作结束后，才能开始后继操作，这称为程序内部顺序性；多个程序合力去完成一个计算任务，这些程序也按照调用次序有序执行，这称为程序外部顺序性。程序顺序执行的最终输出至于初始输入数据有关，而与时间无关，好处在于方便编码和调试，缺点在于效率不高 - 并发程序设计
自从操作系统引入并发程序设计技术后，程序的执行不再是顺序的，一个程序未执行完而另一个程序便已开始执行，程序外部的顺序特性消失，程序与计算不再一一对应。（《深入理解计算机系统》中控制流的概念可以很好地帮助理解并行和并发），并发的实质是处理器在几个程序之间的多路复用，产生了资源共享的需求。
并发程序的无关性
并发程序的无关性是进程的执行与时间无关的一个充分条件，在1966年由bernstein提出。只要满足Bernstein条件，并发执行的程序就可以保持封闭性和可再现性。
鉴于简书不支持LaTeX公式，有兴趣自己查吧，文字表述总是不如数学公式直观。
并发进程的交互
如果进程间不满足上面提及的Bernstein条件，那么他们就会因为共享计算机资源而存在竞争与协作关系(又称互斥与同步)
- 进程互斥是指若过个进程因相互争夺独占型资源而产生的竞争制约关系
- 进程同步是指为完成共同任务的并发进程基于某个条件来协调其活动，因为没需要在某些位置上排定执行的先后次序而等待、传递信号或消息所产生的协作制约关系
不难看出，进程互斥关系是一种特殊的进程同步关系，即逐次使用互斥共享资源，也是对进程使用资源的次序的一种协调。由此，我们提出同步机制这个概念，用于解决共享资源问题。
临界区
同上面的概念类似，两个或多个进程读写某些共享数据，而最后的结果取决于进程运行得精确时序(也就是这些进程不满足Bernstein条件)，我们把这种情况称为竞争条件。解决竞争条件的方法是实现互斥，即以某种手段确保当一个进程在使用一个共享变量或文件时，其他进程不能做同样的操作。
我们把对共享内存进行访问的程序片段称为临界区，如果存在某些方案，使得两个进程不可能同时处于临界区中，就能够避免竞争条件。对于这些方案，需要满足一下4个条件
- 任何两个进程不能同时处于其临界区
- 不应对CPU的速度和数量做任何假设
- 临界区外运行得进程不得阻塞其他进程
- 不能使进程无限期等待进入临界区
忙等待的互斥方案
本节将讨论几种实现互斥的方案。在这些方案中，当一个进程在临界区中更新共享内存时，其他进程将不会进入其临界区，也不会带来任何麻烦
1. 屏蔽中断
在单处理器系统中，最简单的方法就是使每个进程刚刚进入临界区后立即屏蔽所有中断，并在就要离开之前再打开中断。屏蔽中断后，时钟中断也会被屏蔽。CPU只有发生时钟中断或其他中断时才会进行进程切换，这样，在屏蔽中断之后CPU将不会被切换到其他进程。于是，一旦某个进程屏蔽中断之后，他就可以检查和修改共享内存，而不必担心其他进程介入。
- 把屏蔽中断的权利交给用户进程很不明智。如果一个进程屏蔽中断后不再打开中断，整个系统可能会因此终止。
- 对多CPU不适用。屏蔽中断仅仅对执行了disable指令的那个CPU有效，其他CPU仍能访问共享内存。
2.测试并加锁指令 TSL
某些计算机中，特别是那些设计为多处理器的计算机，都有以免一条指令：TSL RX, LOCK，称为测试并加锁(test and set lock)，它将一个内存字lock读到寄存器RX中，然后再该内存地址上存一个非零值。读字和写字操作保证是不可分割的，即该指令结束之前其他处理器均不允许访问该内存字。执行TSL指令的CPU将锁住内存总线，以禁止其他CPU在本指令结束之前访问内存。
为了使用TSL指令，要使用一个共享变量lock来协调对共享内存的访问。当lock为0时，任何进程都可以使用TSL指令将其设置为1，并读写共享内存。当操作结束是，进程用一条普通的move指令将lock的值重新设置为0.
enter_region:
TSL REGISTER, LOCK | 复制锁到寄存器并将锁设为1
CMP REGISTER, #0 | 锁是零吗？
JNE enter_region | 若不是零，说明锁已被设置，所以循环
RET |返回调用者，进入了临界区
leave_region:
MOVE LOCK, #0 |在锁中存入0
RET |返回调用者
可以看出TSL也是一个忙等待方案：进程在进入临界区之前先调用enter_region，在锁空闲之前一直循环等待。
3.对换指令 XCHG
一个可替代TSL的指令是XCHG，它原子性地交换了两个位置的内容，例如，一个寄存器与一个存储器字。
enter_region:
MOVE REGISTER, #1
XCHG REGISTER, LOCK
CMP REGISTER, #0
JNE enter_region
RET
leave_region:
MOVE LOCK, #0
RET
TSL和XCHG指令的函数形式描述在《操作系统教程》第五版有写，此处不详细描述。
4.严格轮询法
//进程0
while(True){
while(turn != 0); //循环
critical_region();
turn = 1;
noncritical_region();
}
//进程1
while(True){
while(turn !=1); //循环
critical_region();
turn = 0;
noncritical_region();
}
整型变量turn，初始值为0，用于记录轮到哪个进程进入临界区，并检查或更新共享内存。开始时，进程0检查turn，发现其值为0，于是进入临界区。进程也发现其值为0，所以在一个等待循环中不但测试turn，看其值何时变为1.连续测试一个变量直到某个值出现为止，称为忙等待。由于这种方式浪费CPU时间，所以通常应该避免。只有在有理由认为等待时间是非常短的情况下，才使用忙等待。用于忙等待的锁，称为自旋锁
这个算法的确避免了所有的竞争条件，但违反了临界区条件3（临界区外运行得进程不得阻塞其他进程），所以不是一个很好的方案。
5.Peterson解法
#define FALSE 0
#define TRUE 1
#define N 2 //进程数量
int turn; //现在轮到谁？
int interested[N]; //所有值初始化为0（FALSE）
void enter_region(int process)
{
int other; //另一个进程号
other = 1-process;
interested[process] = TRUE; //表示想进入临界区
turn = process;
while(turn == process && interested[other] ==TRUE); //挂起进程作用
}
void leave_region(int process)
{
interested[process] = FALSE; //表示离开临界区
}
在使用共享变量之前，各个进程使用其进程号0或1作为参数来调用enter_region。该调用在使用时将使进程等待，直到能安全地进入临界区。在完成对共享变量的操作之后，进程将调用leave_region，表示操作已完成，若其他的进程希望进入临界区，则现在就可以进入。
一开始，没有任何进程进入临界区中，现在进程0调用enter_region。它通过设置其数组元素和将turn置0来标识它希望进入临界区。由于进程1并不想进入临界区，所以enter_region很快便返回。如果进程1现在调用enter_region，进程1将在此处挂起直到interested[0]变成FALSE，该事件只有在进程0调用leave_region退出临界区时才会发生。
现在考虑两个进程几乎同时调用enter_region情况。它们都将自己的进程号存入turn，但只有后被保存进去的进程号才有效，前一个因被重写而丢失。假设进程1是后存入的，则turn为1。当两个进程都运行到while语句时，进程0将循环0次进入临界区，则进程1则将不断地循环而不能进入临界区，直到进程0退出临界区为止。
网友评论