探索并发编程（一）------操作系统篇(转)

原文地址 :这里

在多线程、多处理器甚至是分布式环境的编程时代，并发是一个不可回避的问题，很多程序员一碰到并发二字头皮就发麻，也包括我。既然并发问题摆在面前一个到无法回避的坎，倒不如拥抱它，把它搞清楚，决心花一定的时间从操作系统底层原理到Java的基础编程再到分布式环境等几个方面深入探索并发问题。先就从原理开始吧。

并发产生的原因

虽然从直观效果上，处理器是并行处理多项任务，但本质上一个处理器在某个时间点只能处理一个任务，属于串行执行。在单处理器的情况下，并发问题源于多道程序设计系统的一个基本特性：进程的相对执行速度不可预测，它取决于其他进程的活动、操作系统处理中断的方式以及操作系统的调度策略。在分布式环境下，并发产生的可能性就更大了，只要大家有依赖的共享资源，就有并发问题的出现，因为互相调用次序更加没法控制。

并发带来的问题

全局资源的共享充满了危险。不同任务对同一个共享资源的读写顺序非常关键
操作系统很难对分配资源进行最优化管理。挂起的线程占有了其他活动线程需要的资源
定位错误非常困难。这种问题来源和触发的不确定性，导致定位问题非常困难
限制分布式系统横向扩展能力
进程的交互

进程的交互方式决定了并发问题产生的上下文，解决并发问题也需根据进程交互方式的不同而不同对待。一般进程交互分为以下三种：

1）进程间相互独立

这种情况下虽然进程间没有数据共享，所做事情也互不联系，但它们存在竞争关系。计算机中有些临界资源比如I/O设备、存储器、CPU时间和时钟等等都需要通过竞争得到，你占用的时候就得保证别人没法占用，因此首先得解决这种互斥的需求。另外，要处理好这种临界资源的调度策略，处理不当就有可能发生死锁和饥饿

2）进程间通过共享合作

这种情况下进程间虽然执行的过程是相互独立的，互不知道对方的执行情况，但互相之间有共享的数据。因此除了有以上互斥需求和死锁饥饿的可能，另外还会有数据一致性的问题。当多个进程非原子性操作同一个数据时候，互相之间操作时序不当就有可能造成数据不一致

3）进程间通过通信合作

这种情况下进程间通过消息互相通信，知晓各自的执行情况，不共享任何资源，因此就可以避免互斥和数据不一致问题，但仍然存在死锁和饥饿的问题

并发问题的解决办法

操作系统解决并发问题一般通过互斥，为了提供互斥的支持，需要满足以下需求：

一次只允许一个进程进入临界区
一个非临界区停止的进程必须不干涉其他进程
不允许出现一个需要访问临界区的进程被无限延迟
一个进程驻留在临界区中的时间必须是有限的
临界区空闲时，任何需要进入临界区的进程必须能够立即进入
满足互斥的解决方案：

1）硬件支持

中断禁用
中断禁用简单说来就是在某一进程在临界区执行过程中禁用中断，不允许其他进程通过中断打断其执行。虽然这种方式可以保证互斥，但代价非常高，处理器被限制于只能交替执行程序，效率降低。另外不适用于多处理器环境。
专用机器指令
从硬件的角度提供一些机器指令，用于保证多个动作的原子性，通过适用这些具有原子性的指令来控制临界区的访问。比如提供符合以下逻辑的原子性指令：
boolean testset(int i){  
    if(i==0){  
        i=1;  
        return true;  
    }else{  
        return false;  
    }  
} 
boolean testset(int i){
    if(i==0){
        i=1;
        return true;
    }else{
        return false;
    }
}
在控制临界区的时候可以通过忙等待来保证只有一个进程停留在临界区，伪代码如下所示：
int bolt;  
void onlyOneThread(){  
    while(!testset(bolt)){  
        /*等待*/ 
    }  
    /*临界区*/ 
    bolt=0;  
} 
int bolt;
void onlyOneThread(){
    while(!testset(bolt)){
        /*等待*/
    }
    /*临界区*/
    bolt=0;
}
专用机器指令的优点是可以不限制处理器数量，也不限制临界区的数量，但它的问题是使用了忙等待，消耗处理器时间。并且也存在饥饿和死锁的问题
2）信号量

其原理是多个进程可以通过简单的信号进行合作，一个进程可以被迫在某一个位置停止，直到它收到一个特定的信号，再重新被唤起工作。这种方式最大优点就是解决了忙等待的问题。其核心和机器指令类似，通过提供原子性信号量控制方法，一般情况下提供等待和唤起两种操作原语，以较为简单的二元信号量原语为例，两种方法的伪代码如下：

void wait(semaphore s){  
    if(s.value==1){  
        s.value=0;  
    }else{  
        /*停止此线程，并把线程放入s的线程等待队列(s.queue)里*/ 
    }  
}  
void signal(semaphore s){  
    if(s.queue.size()==0){  
        s.value=1;  
    }else{  
        /*从s的线程等待队列(s.queue)里拿出一个线程，使其激活执行*/ 
    }  
} 
void wait(semaphore s){
    if(s.value==1){
        s.value=0;
    }else{
        /*停止此线程，并把线程放入s的线程等待队列(s.queue)里*/
    }
}
void signal(semaphore s){
    if(s.queue.size()==0){
        s.value=1;
    }else{
        /*从s的线程等待队列(s.queue)里拿出一个线程，使其激活执行*/
    }
}

两个方法的实现关键在于其原子性，当然也可以借助专用机器指令的方法来保障其原子性，毕竟这两种方法的执行不长，使用忙等待也问题不大。

再看互斥的问题，若使用信号量，则其具体实现如以下伪代码所示：

void onlyOneThread(){  
    wait(s);  
    /*临界区*/ 
    signal(s);  
} 
void onlyOneThread(){
    wait(s);
    /*临界区*/
    signal(s);
}

3）管程

信号量虽然解决了性能问题，但使得信号量的控制逻辑遍布在程序里，控制逻辑复杂以后很难整体上控制所有信号量。而管程的思路和面向对象类似，通过一个管程的概念把互斥和资源保护的细节封装在管程的内部，外部程序只需对管程的正确使用就能保证避免并发问题，管程的特点如下：

共享数据变量只能被管程的过程访问
一个进程通过调用管程的一个过程进入管程
只能有一个进程在管程中执行，其他进程被挂起，等待进入管程
4）消息传递

消息传递是通过消息通信的方式进程之间相互配合，满足互斥需求。这种方式最大好处就是可以运用与分布式环境。说到消息，抽象地看有两种操作方式：send和receive。从同步方式上看分为阻塞和非阻塞两种，其组合起来有以下 情况：

阻塞send，阻塞receive。发送进程和接收进程都被阻塞，直到信息交付，同步性最好
非阻塞send，阻塞receive。最为自然的一对组合
非阻塞send，非阻塞receive。
那么通过实现以上send和receive原语操作，就可达到互斥的目的，以下面伪代码为例，其中receive为阻塞的，send为非阻塞的：

void onlyOneThread(){  
    receive(box,msg);  
    /*临界区*/ 
    send(box,msg);  
} 
void onlyOneThread(){
    receive(box,msg);
    /*临界区*/
    send(box,msg);
}

小结

以上是从操作系统的底层来看待并发问题，平常的开发过程一般不需要了解，但透过其原理，我们可以发掘一些解决并发问题的思路。只有真正了解并发产生的原因和操作系统采取的办法，我们才能理解在更高一个层次（比如高级语言编程）为什么有那些控制和措施，为什么对一些代码要做并发控制。