7

我必须使用 Java 信号量来解决这个问题,但我不知道如何,也找不到任何相关的 Java 材料。事情是这样的:

有各种各样的线程:男人和女人。两者都想使用数量为 BATHROOM_SIZE 的相同资源。5条规则:

  1. 每个线程在发出需要使用资源的信号后,都应该等到他能够使用它。
  2. 防止出现超过 BATHOOM_SIZE 个线程同时使用资源的情况。
  3. 防止女性和男性同时使用 Bathoom。
  4. 线程应该同时使用资源。如果一种类型有很多线程,最多 BATHROOM_SIZE 线程应该使用资源。
  5. 防止饥饿。

结果

效劳于:

1女1男5女5男

失败:

5女1男,5男1女,2男2女,5男5女。

从星期一开始,我一直在努力让它发挥作用,现在我已经没有想法了。

代码

所以我的任务是编写实现浴室接口的浴室.java类:

public interface BathroomInterface {

    public static final int BATHROOM_SIZE = 3; //3 is just example
    void manEnter();
    void manExit();
    void womanEnter();
    void womanExit();
}

在系统中有许多男人和女人的线程,它们的工作方式如下:

for(int i = 0; i < n; i++) {
  bathroom.manEnter();
  //uses bathroom random amount of time
  bathroom.manExit();
}

for(int i = 0; i < m; i++) {
  bathroom.womanEnter();
  //uses bathroom random amount of time
  bathroom.womanExit();
}

我也有浴室.java类的方案,我必须扩展:

import java.util.concurrent.Semaphore;

public class Bathroom implements BathroomInterface {

    
    private Semaphore mutex = new Semaphore(1, true);

    public void womanEnter() {
        mutex.acquireUninterruptibly();
    }

    public void womanExit() {
        mutex.release();
    }

    public void manEnter() {
        mutex.acquireUninterruptibly();        
    }

    public void manExit() {
        mutex.release();
    }
}

这是我到目前为止所做的:

import java.util.concurrent.Semaphore;

public class Bathroom implements BathroomInterface {
    int manW=0, manU=0, womanW=0, womanU=0; //*U-using, *W-waiting
    private Semaphore mutex = new Semaphore(1, false);

    public void womanEnter() {
        womanW++;
        StateChange();
    }

    public void womanExit() {
        womanU--;
        mutex.release();
        StateChange();
    }

    public void manEnter(){
        manW++;
        StateChange();
    }

    public void manExit() {
        manU--;
        mutex.release();
        StateChange();
    }
    
    void StateChange() {
        if(womanU==0 && manU==0) {
            if(manW>womanW) {
                while(manW>0 && manU<BATHROOM_SIZE) {
                    manW--;
                    manU++;
                    mutex.acquireUninterruptibly();
                }
            }
            else {
                while(womanW>0 && womanU<BATHROOM_SIZE) {
                    womanW--;
                    womanU++;
                    mutex.acquireUninterruptibly();
                }
            }
        }
        if(womanU==0 && manU<BATHROOM_SIZE) {
            while(manW>0 && manU<BATHROOM_SIZE) {
                manW--;
                manU++;
                mutex.acquireUninterruptibly();
            }
        }
        if(manU==0 && womanU<BATHROOM_SIZE) {
            while(womanW>0 && womanU<BATHROOM_SIZE) {
                womanW--;
                womanU++;
                mutex.acquireUninterruptibly();
            }
        }
    }
}
4

4 回答 4

6

实际上,这个练习是使用监视器完成的,而不是信号量。你所做的大部分都很好,你错过了条件。所以,在你的浴室课上,声明:

一把锁:

private Lock lock = new ReentrantLock();

2 个条件或队列,附加到您的锁:

private Condition womenWaitingQueue = lock.newCondition();
private Condition menWaitingQueue = lock.newCondition();

2 个计数器知道有多少人在等待,2 个计数器知道有多少人正在使用:

private int womenWaitingN = 0;
private int menWaitingN = 0;
private int womenUsingN = 0;
private int menUsingN = 0;

当然还有资源的数量:

private final int BATHROOM_CAPACITY = 5;
private int free_resources = BATHROOM_CAPACITY;

所有 4 个功能都在这里,但由于作业标签而被删除

这里重要的是防止饥饿,如果有女性在等待,则不允许任何男性进入浴室,反之亦然。

所以,条件是如果一个男人想进入浴室,它必须检查浴室是否至少有 1 个空闲位置(使用免费资源)以及浴室是否有女性(使用 womenUsingN)。如果不满足这两个条件中的任何一个,则该人必须等待(使用 menWaitingQueue):

menWaitingQueue.await();

当一个男人离开浴室时,它必须检查是否有女性在等待(womenWaitingN),如果有,他们会收到通知:

womanWaitingQueue.signal();

因为menUsingN柜台,在浴室里没有男人之前,受此信号通知的女性将无法进入。如果没有女性在等待,则可以示意男性进入浴室。这可以防止饥饿,因为优先考虑异性(如果等待)。

最后一件事是每个函数都必须在每个进入/退出函数的开始/结束时锁定/解锁锁。

lock.lock();
lock.unlock();

我认为有了这些新信息,您将能够自己制作这些功能。祝你好运!

于 2012-06-21T13:23:26.733 回答
2

我认为您会为整个 mutex.acquire 和 mutex.release 语义而苦苦挣扎,尤其是在 mutex 实际应该保护的内容方面。让我试着稍微简化一下这个问题,给你一个关于如何解决这个问题的提示。

您被要求实现一个比简单信号量更复杂的并发对象,具有两个客户端类和饥饿预防。我不会为你这样做,但我将向你展示一个简单的信号量在 Java6 之前的日子里是什么样子的:

public class Resource {

    private int numClients = 0;
    private final int maxClients;

    public Resource(int maxClients) {
        this.maxClients = maxClients;
    }

    public synchronized void acquire() {
        while (!clientCanAcquire()) {
            try {
                wait();
            } catch (InterruptedException e) {
            }
        }
        ++numClients;
        printState();
    }

    public synchronized void release() {
        --numClients;
        printState();
        notify();
    }

    private boolean clientCanAcquire() {
        return numClients < maxClients;
    }

    private void printState() {
        System.out.println("Resource is currently acquired by " + numClients
                + " clients");
    }
}

客户端可以通过以下方式访问它:

import java.util.Random;

public class Client implements Runnable {

    private Resource resource;
    private Random rnd = new Random();

    public Client(Resource resource) {
        this.resource = resource;
    }

    public void run() {
        try {
            Thread.sleep(rnd.nextInt(1000));
            resource.acquire();
            Thread.sleep(rnd.nextInt(1000));
            resource.release();
        } catch (InterruptedException e) {
        }
    }
}

可以驱动整个事情的最简单的应用程序看起来像这样:

public class App {

    public static void main(String[] arg) {

        Resource r = new Resource(3);
        for (int i = 0; i < 10; i++) {
            Thread client = new Thread(new Client(r));
            client.start();
        }
    }
}

Resource 将确定客户端何时可以访问的信息存储在内部变量中。在多线程应用程序中,对这些变量的访问必须同步。此处显示的是执行此操作的最简单方法,但您也可以说

private Object mutex = new Object();

接着

synchronized (mutex) { }

或任何其他类型的互斥体。

您的问题比简单的普通信号量更复杂,但底层逻辑应该非常相似。

于 2012-06-21T14:24:05.527 回答
0

在http://se.inf.ethz.ch/courses/2013a_spring/ccc/有一个解决方案

您可以参考它以获得一些帮助。

于 2013-09-22T21:23:59.567 回答
0

@Th0rndike 好的,我按照你的提示写了这样的东西:

import java.util.concurrent.Semaphore;
import java.util.concurrent.locks.*;

public class Bathroom implements BathroomInterface {
    private Semaphore mutex = new Semaphore(1, false);

    private Lock lock = new ReentrantLock();
    private Condition womenWaitingQueue = lock.newCondition();
    private Condition menWaitingQueue = lock.newCondition();

    private int womenWaitingN = 0;
    private int menWaitingN = 0;
    private int womenUsingN = 0;
    private int menUsingN = 0;

    private int free_res = BATHROOM_SIZE;

    public void womanEnter() {
        lock.lock();
        if(free_res>0 && menUsingN==0) {
            womenUsingN++;
            free_res--;
            mutex.acquireUninterruptibly();
        }
        else
            try {
                womenWaitingQueue.await();
            }
        catch(Exception e) {
            System.out.println("E!");
        }
        lock.unlock();
    }

    public void womanExit() {
        lock.lock();
        womenUsingN--;
        free_res++;
        mutex.release();
        if(menWaitingN>0) {
            try {
                menWaitingQueue.signal();
            }
            catch(Exception e) {
                System.out.println("E!");
            }
        }
        lock.unlock();
    }

    public void manEnter() {
        lock.lock();
        menUsingN++;
        free_res--;
        if(free_res>0 && womenUsingN==0) {
            mutex.acquireUninterruptibly();
        }
        else
            try {
                menWaitingQueue.await();
            }
        catch(Exception e) {
            System.out.println("E!");
        }
        lock.unlock();    
    }

    public void manExit() {
        lock.lock();
        menUsingN--;
        free_res++;
        mutex.release();
        if(womenWaitingN>0) {
            try {
                womenWaitingQueue.signal();
            }
            catch(Exception e) {
                System.out.println("E!");
            }
        }
        lock.unlock();
    }
}

但是当我将它提交给自动程序检查器时,在 1man 和 1woman 测试中一切正常,但在其余部分中,它返回“实时超出”错误。如果我删除 lock.lock()/unlock(),“实时超出”错误将变为“错误答案”。

于 2012-06-21T23:54:18.673 回答