`

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

threadUP生活JDK活动 
阅读更多

      信号量 是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();
	}
}

 

 

分享到：
| ★经典问题—链表中的环问题
评论
5 楼 youjianbo_han_87 2014-05-30  
哲学家进餐的那个例子，从运行上来看，锁竞争还是特别厉害（或者说有死锁），并不是每次都能运行成功。
4 楼 Heart.X.Raid 2010-08-21  
恩  是我写错了，应该是：

if( Signs.status[pid]==Signs.THINKING&&
        Signs.status[lid]!=Signs.EATING&&
        Signs.status[rid]!=Signs.EATING)
3 楼 darxin 2010-08-20  
哲学家进餐问题中

test方法中所有的判断均指向了引入的参数pid，这样的判断没有意义！代码如下：

private void test(int pid){
    //如果当前哲学家左右手边的人都没有吃饭，则当前哲学家可以进餐
    if( Signs.status[pid]==Signs.THINKING&&
        Signs.status[pid]!=Signs.EATING&&
        Signs.status[pid]!=Signs.EATING){
        ...
    }
}

test方法要判断的是指定的哲学家是否可以吃饭，而不是线程对象所指向的哲学家。
所以我认为test方法应该修改成：

private void test(int pid){
    int lid=(pid+4)%5;
    int rid=(pid+1)%5;
    //如果当前哲学家左右手边的人都没有吃饭，则当前哲学家可以进餐
    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(); //释放一个许可
    }
}

如有不对的地方请指正。
2 楼 Heart.X.Raid 2010-08-19  
1楼，这样改好像没有什么区别吗？每个哲学家线程创建的时候就可以确定与其相邻哲学家的id了，在不在test里面加上lid和rid无所谓呀。我不懂为什么要这样？
1 楼 darxin 2010-08-19  
哲学家进餐问题的代码，test方法是否应该修改成如下的样子：

private void test(int pid){
    int lid=(pid+4)%5;
    int rid=(pid+1)%5;
    //如果当前哲学家左右手边的人都没有吃饭，则当前哲学家可以进餐
    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(); //释放一个许可
    }
}
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    多线程代码 经典线程同步互斥问题 生产者消费者问题

    a: 创建一个线程 b: 创建多个线程 c: 多线程访问同一资源 d: 经典线程同步互斥问题 e: 使用关键段解决子线程互斥问题 f: 利用事件实现线程同步问题 ...I: 信号量 semaphore 解决线程同步问题

    c++多线程同步——信号量

    在C++编程中，多线程同步是一种关键的技术，它允许多个执行线程协同工作，以避免数据竞争和死锁等并发...在MFC工程中，通过自定义信号量类和Windows API，我们可以有效地解决多线程同步问题，确保程序的正确性和性能。

    信号量机制实现线程同步

    4. **哲学家就餐问题**：这是一个经典的多线程同步问题，通过信号量解决。五个哲学家围坐在一张圆桌旁，每人面前有一根筷子。当一个哲学家想吃饭时，他需要左右两边的筷子。如果同时有两个哲学家去拿筷子，会导致...

    java 线程同步 信号量控制同步

    信号量机制可以用于解决生产者-消费者问题、哲学家就餐问题等。 Java 中的 synchronized 关键字可以用于实现线程同步。synchronized 关键字可以用来锁定对象或方法，防止多个线程同时访问同一个共享资源。 在 Java...

    信号量实现多线程同步

    利用多线程原理模拟生产与消费的互斥同步过程，使用了信号量

    线程同步机制代码，用c++写的，：使用Windows互斥信号量操作函数和同步机制的Peterson，实现进程互斥和同步

    小实验三：根据同步机制的Peterson软件解决方案尝试自己编程实现线程同步机制和用于上述线程并发问题的解决，并基于程序运行时间长短将其与基于Windows互斥信号量的线程同步机制的效率展开比较。 实验要求：线程主体...

    Visual C++信号量线程同步的简单实例工程

    本实例工程“Visual C++信号量线程同步的简单实例工程”聚焦于如何通过信号量（Semaphore）实现线程间的协调与同步，以确保资源的有效管理和避免竞态条件。 首先，我们需要理解什么是信号量。信号量是一种同步原语...

    使用信号量实现线程同步

    信号量（Semaphore）是实现线程同步的一种有效工具，它源于早期的计算机操作系统理论，由荷兰计算机科学家Dijkstra提出。在Windows系统中，信号量作为内核对象被广泛使用，可以用来控制对共享资源的访问。 信号量的...

    使用信号量（Semaphore）实现线程的同步

    信号量（Semaphore）是...信号量是解决线程同步问题的一种高效工具，通过合理的信号量控制，可以有效地避免死锁、饥饿等问题，提高系统资源的利用率。理解并正确使用信号量，对于编写高效、稳定的多线程程序至关重要。

    山东大学操作系统课设lab3使用信号量解决N线程屏障问题

    总的来说，解决N线程屏障问题的关键在于正确地使用信号量进行同步控制，确保所有线程在特定点等待，直至所有线程到达。在实验中，需要通过调试和修改代码，确保线程间的同步行为符合预期，避免出现竞态条件和其他...

    理发师问题-信号量PV操作实现

    通过使用信号量PV操作，实现了多线程同步，解决了理发师问题。下面是该解决方案的详细介绍。 信号量PV操作 信号量是一种同步机制，它可以用来解决多进程同步问题。PV操作是信号量的一种操作，它可以用来实现进程...

    易语言多线程控制：信号量控制线程数量

    信号量（Semaphore）是一种经典的同步机制，用于控制对共享资源的访问。在易语言中，我们可以利用其提供的信号量API来实现线程间的同步与互斥。信号量值可以用来表示资源的可用数量，当线程试图获取一个资源时，如果...

    VC多线程例程十及图解文档(使用信号量进行线程同步)

    本篇将深入探讨如何使用信号量进行线程同步，以确保程序的正确性。 信号量是多线程同步的一种重要工具，它是一个计数器，可以用来限制同时访问某个资源的线程数量。在VC++中，我们可以使用Windows API中的`...

    2.线程间同步和通信之信号量（静态）

    本教程将深入探讨如何使用信号量进行线程间的同步和通信，特别是在STM32平台上的实践应用。 信号量，作为一种资源管理机制，用于控制对共享资源的访问。在多线程环境中，当多个线程尝试同时访问有限资源时，信号量...

    vc++ multithread多线程教程---线程通信--利用事件对象,线程同步--使用信号量,线程同步--使用互斥量,线程同步--使用临界区

    本教程将深入探讨四种常见的线程同步机制：事件对象、信号量、互斥量以及临界区，帮助开发者理解和掌握如何在VC++中安全地实现多线程通信。 一、事件对象 事件对象是Windows API中用于线程间通信的一种同步机制。它...

    基于信号量的Linux多线程同步研究.pdf

    ### 基于信号量的Linux多线程同步研究 #### 摘要与背景 在多线程编程中，确保各个线程之间的同步是非常重要的，以避免出现资源竞争和死锁等问题。信号量是一种常用的同步机制，它可以有效管理线程间的资源共享。...

    sem_syn.rar_linux syn_信号量_线程 同步

    信号量是一种经典的同步机制，它是由Pete Karnagh提出的，用于解决进程间的同步和互斥问题。在Linux中，我们可以使用`sem_t`结构体和相关的系统调用来操作信号量。 1. **信号量的概念**： - 信号量分为两种类型：...

    操作系统线程同步算法

    在Windows操作系统中，提供了多种线程同步机制，如临界区、事件、信号量以及互斥量等。本主题将深入探讨未使用和使用Windows互斥量的线程同步方案，以及Peterson算法这一经典的软件解决方案。 首先，未使用Windows...

    信号量解决理发师问题

    在本案例中，通过运用信号量这一重要的同步工具来解决理发店中顾客与理发师之间的同步问题。 #### 信号量简介 信号量是一种广泛应用于操作系统中的进程同步机制。它本质上是一个整数值，用来控制多个进程对共享...

    经典进程同步问题（代码+文档）

    通过学习这些经典问题及其解决方案，开发者将能更好地理解和处理多线程环境中的同步与通信问题，提高系统的稳定性和效率。 在实际编程中，理解并掌握这些同步原语至关重要，因为它们是构建并发程序的基础。通过对...

Magicbox
Global site tag (gtag.js) - Google Analytics