经典的进程同步问题 |
您所在的位置：网站首页 › 操作系统生产者消费者问题流程图 › 经典的进程同步问题 |
经典的进程同步问题
|
经典的进程同步问题-----生产者-消费者问题详解
一、问题描述二、问题分析三、信号量设置四、记录型信号量解决生产者-消费者问题五、使用AND型信号量解决生产者-消费者问题六、使用信号量集解决生产者-消费者问题七、使用管程解决生产者-消费者问题
进程同步问题是一个非常重要且相当有趣的问题，因而吸引了很多学者对他进行研究。 本文就选取其中较为代表性的生产者-消费者问题来进行学习，以帮助我们更好的理解进程同步的概念及实现方法。 一、问题描述有一群生产者进程在生产产品，并将这些产品提供给消费者进程进行消费。 为了使生产这边进程与消费进程能够并发的执行，在两者之间设置了一个具有n 个缓冲区的缓冲池，生产者进程将其他生产的产品放到一个缓冲区中，消费者进程可以从一个缓冲区中取走产品去消费。 需要注意的是，尽管所有的生产者和消费者都是以异步的方式运行的，但是他们之间必须保持同步， 既不允许消费者进程在缓冲区为空时去取产品， 也不允许生产者进程在缓冲区已满且产品尚未被取走时向缓冲区投放产品。 下图是一个生产者与消费者进程执行的流程图，比图中我们可以很清晰的看到上述的三个进程间的关系，其中生产者和消费者中操作缓冲区都需要先进行申请，也就是进入区，操作完成后要执行释放，也就是退出区，通过这样来实现对缓冲池的互斥访问。 通过图中的贯通两个进程的虚线来实现生产者和消费者的同步关系。 由于有界缓冲池是一个临界资源，必须互斥使用，这时可以利用互斥信号量 mutex 来实现诸进程对缓冲池的互斥使用。 因为是互斥信号量，所以 mutex 初值为 1。 另外，可以设置两个同步信号量： 一个表示缓冲池中空缓冲区的数目，用empty 表示，初值 为缓冲池的大小 n； 另一个表示已满缓冲区的数目，即缓冲池中消息的数量，用 full 表示，初值为 0； 除了信号量外，我们可以使用循环链表来表示有界缓冲池，假设缓冲池的大小为 n，我们用 buffer[n] 来表示， 另外还有两个队首指针in 和 队尾指针 out ，其初值都为 0。 四、记录型信号量解决生产者-消费者问题首先我们使用记录型信号量来解决生产者-消费者问题，根据上面的分析，我们先给出伪代码： int in=0, out=0; // item 为消息的结构体 item buffer[n]; semaphore mutex=1, empty=n, full=0; // 初始化信号量 void producer(){ do{ // 生产者产生一条消息 producer an item next p; ...... // 判断缓冲池中是否仍有空闲的缓冲区 P(empty); // 判断是否可以进入临界区（操作缓冲池） P(mutex); // 向缓冲池中投放消息 buffer[in] = nextp; // 移动入队指针 in = (in+1) % n; //退出临界区，允许别的进程操作缓冲池 V(mutex); // 缓冲池中数量的增加，可以唤醒等待的消费者进程。 V(full); }while(true); } void consumer(){ do{ //判断缓冲池中是否有非空的缓冲区（消息） P(full); // 判断是否可以进入临界区（操作缓冲池） P(mutex); nextc = buffer[out]; // 移动出队指针 out = (out+1) % n; // 退出临界区，允许别的进程操作缓冲池 V(mutex); // 缓冲池中空缓冲区数量加1， 可以唤醒等待的生产者进程 V(empty); // 消费消息 consumer the item in next c; }while(true); }通过上面的伪代码，我们可以看到， 在每个程序中用于实现互斥的 P(mutex) 和 V(mutex) 必须成对的出现，并且要出现在同一个程序中； 对于用于控制进程同步的信号量 full 和 empty，其P/V 操作也必须成对的出现， 但他们分别处于不同的程序之中。 还有比较重要的就是，每个程序中多个P操作顺序不能颠倒， 比如，应先执行对资源信号量的P操作-P(empty)， 再执行对互斥信号量的P操作- P(mutex)， 否则可能会因为持有了互斥锁，但是没有空闲的缓冲区而导致生产者进程阻塞， 但是别的进程又无法进入临界区，导致发生死锁。 下面给出对应的Java 多线程的实现，为了简单，临界缓冲池我使用了一个长度为50 的list 来模拟，代码如下： // 记录型信号量 static final Semaphore mutex = new Semaphore(1); static List buffer = new ArrayList(); static final Semaphore empty = new Semaphore(50); static final Semaphore full = new Semaphore(0); static Integer count = 0; static class Producer extends Thread{ Producer(String name){ super.setName(name); } } @Override public void run(){ do{ try{ // 判断缓冲池中是否仍有空闲的缓冲区 empty.acquire(); // 判断是否可以进入临界区（操作缓冲池） mutex.acquire(); log.info("生产了一条消息：%d", count); // 向缓冲池投放消息 buffer.add(count++); // Thread.sleep(1000); // 释放资源 full.release(); mutex.release(); }catch( InterruptedException e ){ log.error("生产消息时产生异常！"); } }while(true); } static class Consumer extends Thread { Consumer(String name) { super.setName(name); } @Override public void run() { do { try { //判断缓冲池中是否仍有空闲的缓冲区 full.acquire(); //判断是否可以进入临界区（操作缓冲池） mutex.acquire(); log.info("消费了一条消息：【{}】", buffer.remove(0)); //Thread.sleep(1000); empty.release(); mutex.release(); } catch (InterruptedException e) { log.error("消费消息时产生异常！"); } } while (true); } } public static void main(String[] args) { //测试 Producer p1 = new Producer("p1"); Producer p2 = new Producer("p2"); Consumer c1 = new Consumer("c1"); Consumer c2 = new Consumer("c2"); p1.start(); p2.start(); c1.start(); c2.start(); } 五、使用AND型信号量解决生产者-消费者问题 ... //定义信号量并初始化 void producer(){ do { //生产者产生一条消息 producer an item nextp; ... //判断缓冲池中是否仍有空闲的缓冲区&&是否可以进入临界区 Swait(empty, mutex); //向缓冲池中投放消息 buffer[in] = nextp; //移动入队指针 in = (in + 1) % n; //退出临界区&&消息数量加1，可以唤醒等待的消费者进程 Ssignal(mutex, full); }while(true); } void consumer(){ do { //判断缓冲池中是否有消息&&是否可以进入临界区 Swait(full, mutex); //从缓冲池中取出消息 nextc = buffer[out]; //移动出队指针 out = (out + 1) % n; //退出临界区&&缓冲池中空缓冲区数量加1，可以唤醒等待的生产者进程 Ssignal(mutex, empty); //消费消息 consumer the item in nextc; ... }while(true); } 六、使用信号量集解决生产者-消费者问题信号量集是对AND型型号量的一次扩展，其代码不同的就在于wait操作可以一次申请多个资源和可以设置资源分配下限，下面是伪代码： ... //定义信号量并初始化 void producer(){ do { producer an item nextp; ... //判断缓冲池中是否仍有空闲的缓冲区&&是否可以进入临界区 Swait(empty, 1, 1, mutex, 1, 1); //向缓冲池中投放消息 buffer[in] = nextp; //移动入队指针 in = (in + 1) % n; //退出临界区&&消息数量加1，可以唤醒等待的消费者进程 Ssignal(mutex, 1, full, 1); }while(true); } void consumer(){ do { //判断缓冲池中是否有消息&&是否可以进入临界区 Swait(full, 1 ,1 , mutex, 1, 1); //从缓冲池中取出消息 nextc = buffer[out]; //移动出队指针 out = (out + 1) % n; //退出临界区&&消息数量减1，可以唤醒等待的生产者进程 Ssignal(mutex, 1, empty, 1); //消费消息 consumer the item in nextc; ... }while(true); } 七、使用管程解决生产者-消费者问题 对管程，我们在前面的文章中详细的进行了介绍，在这里也使用管程来解决实际的问题，伪代码如下 Monitor ProducerConsumer { intem buffer[N]; int in=0,out=0; condition notempty,notfull;//条件变量 非空和非满 int count=0;//缓冲区中消息的数量 //放消息的过程 void put(item x){ //如果缓冲池满了，则将线程阻塞到notfull中 if(count >= N){ cwait(notfull); } //向缓冲池中投放消息 buffer[in] = nextp; //移动入队指针 in = (in + 1) % N; //缓冲区中消息加一 count++; //唤醒因为没消息消费阻塞的消费者线程 signal(notempty); } //取消息的过程 void get(item x){ //如果缓冲池为空，则将线程阻塞到notempty中 if(count do { //生产者产生一条消息 producer an item nextp; ... PC.put(nextp);//将消息放入到缓冲池中 }while(true); } void consumer(){ item x; do { PC.get(x);//从缓冲池中取出消息 consumer the item in nextc;//消费消息 ... }while(true); } |
【本文地址】
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |