信号量解决经典线程同步问题

本文转自：http://hxraid.iteye.com/blog/739265

信号量 是E. W.Dijkstra在l965年提出的一种方法，它使用一个整型变量来累计唤醒次数，以供以后使用。在他的建议中引入一个新的变号类型，称作信号量(semapore )。一个信号量的值可以为0,表示没有积累下来的唤醒操作;或者为正值，表示有一个或多个被积累下来的唤醒操作。       Dijkstra建议设两种操作:Down和Up。对一信号量执行Down操作是检查其值是否大于0;若是则将其值减1(即用掉一个保存的唤醒信号)并继续。若值为0,则进程将睡眠，而且此时Down操作并未结束。检查数值，改变数值以及可能发生的睡眠操作均作为一个单一的、不可分割的原子操作(atomic action)完成。即保证一旦一个信号量操作开始，则在操作完成或阻塞之前别的进程均不允许访问该信号量。这种原子性对于解决同步间题和避免竞争条件是非常重要的。       Up操作递增信号量的值。如果一个或多个进程在该信号量上睡眠，无法完成一个先前的Down操作、则由系统选择其中的一个(例如，随机挑选)并允许其完成它的Down操作。于是，对一个有进程在其上睡眠的信号量执行一次Up操作之后，该信号量的值仍旧是0.但在其上睡眠的进程却少了一个。递增信号量的值和唤醒一个进程同样也是不可分割的。不会有进程因执行Up而阻塞。

          JDK的并发包就给我提供了一个类似的信号量类——Semaphore ，其中的acquire()和release()方法就相当于Down和Up操作，这两个方法的特殊之处在于对Semaphore对象的操作都是原子操作，由操作系统底层来支持。下面我们讲的四种经典线程同步问题，都是使用了Java编码。

 

 

1、生产者-消费者问题         由一个大小固定的仓库，生产者将生产的产品放入仓库，如果仓库满，则生成者被阻塞。消费者将仓库中的产品拿出来消耗，如果仓库空，则消费者被阻塞。

import java.util.concurrent.Semaphore; class Signs{ static Semaphore empty=new Semaphore(10); //信号量：记录仓库空的位置 static Semaphore full=new Semaphore(0); //信号量：记录仓库满的位置 static Semaphore mutex=new Semaphore(1); //临界区互斥访问信号量(二进制信号量)，相当于互斥锁。 } class Producer implements Runnable{ public void run(){ try { while(true){ Signs.empty.acquire(); //递减仓库空信号量 Signs.mutex.acquire(); //进入临界区 System.out.println("生成一个产品放入仓库"); Signs.mutex.release(); //离开临界区 Signs.full.release(); //递增仓库满信号量 Thread.currentThread().sleep(100); } } catch (InterruptedException e) { e.printStackTrace(); } } } class Consumer implements Runnable{ public void run(){ try { while(true){ Signs.full.acquire(); //递减仓库满信号量 Signs.mutex.acquire(); System.out.println("从仓库拿出一个产品消费"); Signs.mutex.release(); Signs.empty.release(); //递增仓库空信号量 Thread.currentThread().sleep(1000); } } catch (InterruptedException e) { e.printStackTrace(); } } } public class Test{ public static void main(String[] args) { new Thread(new Producer()).start(); new Thread(new Consumer()).start(); } }

2、哲学家进餐问题

 

      在1965年，Dijkstra提出并解决了一个他称之为哲学家进餐的同步问题。从那时起，每个发明新的同步原语的人都希望通过解决哲学家进餐间题来展示其同步原语的精妙之处。这个问题可以简单地描述：五个哲学家围坐在一张圆桌周围，每个哲学家面前都有一碟通心面，由于面条很滑，所以要两把叉子才能夹住。相邻两个碟子之间有一把叉子。       哲学家的生活包括两种活动:即吃饭和思考。当一个哲学家觉得饿时，他就试图去取他左边和右边的叉子。如果成功地获得两把叉子，他就开始吃饭，吃完以后放下叉子继续思考。

import java.util.concurrent.Semaphore; class Signs{ final static int THINKING=0; //哲学家的状态THINGING final static int EATING=1; //哲学家的状态EATING static int[] status=new int[5]; //哲学家的状态，默认都是THINGING static Semaphore[] s=null; //信号量：记录哲学家是否可以进餐，不能进餐则堵塞 static Semaphore mutex=new Semaphore(1); //临界区互斥访问信号量(二进制信号量)，相当于互斥锁 //初始化每个哲学家的进餐信号量，默认值都不能进餐 static{ s=new Semaphore[5]; for(int i=0;i<s.length;i++) s[i]=new Semaphore(0); }; } class Philosopher implements Runnable{ private int pid; //当前哲学家的序号 private int lid; //坐在左手边的哲学家序号 private int rid; //坐在右手边的哲学家序号 Philosopher(int id){ this.pid=id; this.lid=(id+4)%5; this.rid=(id+1)%5; } private void test(int pid){ //如果当前哲学家左右手边的人都没有吃饭，则当前哲学家可以进餐 if(Signs.status[pid]==Signs.THINKING&&Signs.status[lid]!=Signs.EATING&&Signs.status[rid]!=Signs.EATING){ Signs.status[pid]=Signs.EATING; //此时当前哲学家线程可以进餐，但其他哲学家线程很可能无法进餐 Signs.s[pid].release(); //释放一个许可 } } public void run(){ try { //尝试拿起叉子准备进餐 Signs.mutex.acquire(); test(pid); Signs.mutex.release(); //判断当前哲学家的进餐信号量，如果不能许可进餐，则当前线程阻塞 Signs.s[pid].acquire(); System.out.println("#"+pid+" 号哲学家正在进餐..."); //放下叉子，并唤醒旁边两个被阻塞进餐的哲学家，让他们尝试进餐 Signs.mutex.acquire(); Signs.status[pid]=Signs.THINKING; test(lid); //让左手边的哲学家尝试拿起叉子，如果可以，则释放这个哲学家的信号量许可 test(rid); //同上 Signs.mutex.release(); } catch (InterruptedException e) { e.printStackTrace(); } } } public class Test{ public static void main(String[] args) { new Thread(new Philosopher(0)).start(); new Thread(new Philosopher(1)).start(); new Thread(new Philosopher(2)).start(); new Thread(new Philosopher(3)).start(); new Thread(new Philosopher(4)).start(); } } 3、读者-写者问题    读者一写者问题(Courtois et al., 1971)为数据库访问建立了一个模型。例如，设想一个飞机定票系统，其中有许多竞争的进程试图读写其中的数据。多个进程同时读是可以接受的，但如果一个进程正在写数据库、则所有的其他进程都不能访问数据库，即使读操作也不行。

import java.util.concurrent.Semaphore; class Sign{ static Semaphore db=new Semaphore(1); //信号量：控制对数据库的访问 static Semaphore mutex=new Semaphore(1); //信号量：控制对临界区的访问 static int rc=0; //记录正在读或者想要读的进程数 } class Reader implements Runnable{ public void run(){ try { //互斥对rc的操作 Sign.mutex.acquire(); Sign.rc++; //又多了一个读线程 if(Sign.rc==1) Sign.db.acquire(); //如果是第一个读进程开始读取DB，则请求一个许可，使得写进程无法操作 DB Sign.mutex.release(); //无临界区控制，多个读线程都可以操作DB System.out.println("[R] "+Thread.currentThread().getName()+": read data...."); Thread.sleep(100); //互斥对rc的操作 Sign.mutex.acquire(); Sign.rc--; if(Sign.rc==0) Sign.db.release(); //如果最后一个读进程读完了，则释放许可，让写进程有机会操作DB Sign.mutex.release(); } catch (InterruptedException e) { e.printStackTrace(); } } } class Writer implements Runnable{ public void run(){ try { //与读操作互斥访问DB Sign.db.acquire(); System.out.println("[W] "+Thread.currentThread().getName()+": write data...."); Thread.sleep(100); Sign.db.release(); } catch (InterruptedException e) { e.printStackTrace(); } } } public class Test { public static void main(String[] args){ new Thread(new Reader()).start(); new Thread(new Reader()).start(); new Thread(new Writer()).start(); } }

4、理发师问题

      另一个经典的问题发生在理发店里。理发店里有一位理发师，一把理发椅和n把供等候理发的顾客坐的椅子。如果没有顾客，理发师便在理发椅上睡觉，当一个顾客到来时，他必须先叫醒理发师，如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，他们就坐下来等;如果没有空椅子，他就离开。

import java.util.concurrent.Semaphore; class Sign{ final static int CHAIRS=5; //椅子数量 static int waiting=0; //等待理发的顾客数 static Semaphore consumers=new Semaphore(0); //信号量：等候服务的顾客数 static Semaphore barber=new Semaphore(0); //信号量：等待顾客的理发师数 static Semaphore mutex=new Semaphore(1); //信号量：控制对临界区的访问 } class Barber implements Runnable{ public void run(){ try { while(true){ Sign.consumers.acquire(); //如果顾客数是0，则理发师睡觉 //互斥操作顾客等待waiting Sign.mutex.acquire(); Sign.waiting--; Sign.barber.release(); //一个理发师现在开始理发 Sign.mutex.release(); System.out.println("理发师"+Thread.currentThread().getName()+"正在理发..."); } } catch (InterruptedException e) { e.printStackTrace(); } } } class Customer implements Runnable{ public void run(){ try { //互斥操作顾客等待waiting Sign.mutex.acquire(); //如果还有椅子空余，则顾客坐在椅子上等待 if(Sign.waiting<Sign.CHAIRS){ Sign.waiting++; Sign.consumers.release(); //顾客理 Sign.mutex.release(); Sign.barber.acquire(); //如果理发师数量为0，则顾客等待 System.out.println("顾客"+Thread.currentThread().getName()+"正在被理发..."); }else{ Sign.mutex.release(); //理发店满人，顾客走人 } } catch (InterruptedException e) { e.printStackTrace(); } } } public class Test { public static void main(String[] args){ new Thread(new Barber()).start(); new Thread(new Customer()).start(); new Thread(new Customer()).start(); new Thread(new Customer()).start(); } }