使用Dekker算法进行同步

Question

我希望能够更改runTrain()方法以允许同步，从而避免两列火车同时通过。

公共类秘鲁扩展铁路{

public Peru() throws SetUpError {
    super("Peru",new Delay(0.1,0.3));
}

/**
 * Run the train on the railway.
 * This method currently does not provide any synchronisation to avoid two 
 * trains being in the pass at the same time.
 */
public void runTrain() throws RailwaySystemError {
    Clock clock = getRailwaySystem().getClock();
    Railway nextRailway = getRailwaySystem().getNextRailway(this);
    while (!clock.timeOut()) {
        choochoo();
        getBasket().putStone(this);
        while (nextRailway.getBasket().hasStone(this)) {
            getBasket().takeStone(this);
            siesta();
            getBasket().putStone(this);
        }
        crossPass();
        getBasket().takeStone(this);
    }
}

}

目前的问题是，我目前的方法不允许同步让两列火车同时通过。这两列火车分别是秘鲁和玻利维亚。

公共班级玻利维亚延长铁路{

public Bolivia() throws SetUpError {
    super("Bolivia",new Delay(0.1,0.3));
}

/**
 * Run the train on the railway.
 * This method currently does not provide any synchronisation to avoid two 
 * trains being in the pass at the same time.
 */
public void runTrain() throws RailwaySystemError {
    Clock clock = getRailwaySystem().getClock();
    Railway nextRailway = getRailwaySystem().getNextRailway(this);
    while (!clock.timeOut()) {
        choochoo();
        getBasket().putStone(this);
        while (nextRailway.getBasket().hasStone(this)) {
            getBasket().takeStone(this);
            siesta();
            getBasket().putStone(this);
        }
        crossPass();
        getBasket().takeStone(this);
    }
}

}

下面是抽象类，其中包含扩展线程时定义的所有方法。

公共抽象类铁路扩展线程{私有字符串名称；//铁路私有静态篮子的名称sharedBasket =新篮子(“共享篮子”)；// a共享//通知篮子私有篮子；//私有篮子私有RailwaySystem railwaySystem；//该铁路构成私有延迟延迟的系统；//该铁路使用的延迟

private Position position; // the position of the train on this railway

public Railway(String name,Delay delay) {
    this.name = name;
    this.delay = delay;
    position = Position.END_PASS; // all trains start just after the
    basket = new Basket(name + "'s basket");
}

/**
 * Register this railway with a railway system
 * @param railwaySystem the railway system this railway must be registered with
 */
public void register(RailwaySystem railwaySystem) {
    this.railwaySystem = railwaySystem;
}

/**
 * Get the railway system this railway is registered with
 * @return the railway system this railway is registered with
 * @throws ProgrammingError if the railway is not registered
 */
public RailwaySystem getRailwaySystem() throws ProgrammingError {
    if (railwaySystem == null) {
        throw new ProgrammingError(name + " is not registered with a railway 
        system");
    }
    return railwaySystem;
}

/**
 * Get this railway's name
 * @return this railway's name
 */
public String name() {
    return name;
}

/**
 * Get this railway's private basket.
 * @return this railway's private basket
 */
public Basket getBasket() {
    return basket;
}

/**
 * Get the shared basket.
 * @return the basket shared between all railways.
 */
public static Basket getSharedBasket() {
    return sharedBasket;
}

/**
 * Use delay to generate a delay for this railway
 */
public void delay() {
    delay.delay();
}

// Fields keeping track of trains in the pass
private static int trainsInPass = 0; // how many trains are in the pass

/**
 * Defines parts of the railway system. These are specified as:
 * <ul>
 *     <li> START_PASS: just before entering the shared pass.</li>
 *     <li> IN_PASS: in the shared pass.</li>
 *     <li> END_PASS: at the end of the shared pass.</li>
 * </ul>
 * Trains start at the end of the pass, and must thereafter cycle through 
 * positions START_PASS, IN_PASS, END_PASS.
 */
public static enum Position {
    START_PASS, IN_PASS, END_PASS;
    
    public String toString() {
        switch (this) {
        case START_PASS: return "at the start of the pass";
        case IN_PASS: return "in the pass";
        case END_PASS: return "at the end of the pass";
        default: return "at an undefined position on the railway (ERROR)";
        }
    }
}
/**
 * Enter the pass.
 * This method does <i>not</i> check if it is safe to enter the pass. It is 
 * merely for
 * administration of the information about trains in the pass.
 * @throws ProgrammingError if this railway thinks it already has a train in 
 * the pass.
 */
private synchronized void enterPass() throws ProgrammingError {
    railwaySystem.trace(name + ": entering pass");
    if (position != Position.START_PASS) {
        throw new ProgrammingError(name + " cannot enter the pass, it is not " 
        + Position.START_PASS + ", it is " + position + ".");
    }
    position = Position.IN_PASS;
    trainsInPass++;
}

/**
 * Leave the pass.
 * This method is merely for administration of the information about trains in 
 * the pass.
 * @throws ProgrammingError if this railway thinks it does not have a train in 
 * the pass,
 *                          or if there is no record of any trains in the pass.
 */
private synchronized void leavePass() throws ProgrammingError {
    if (position != Position.IN_PASS) {
        throw new ProgrammingError(name + " cannot leave the pass, it is not " 
        + Position.IN_PASS + ", it is " + position + ".");
    }
    if (trainsInPass == 0) {
        throw new ProgrammingError("There is no train to leave the pass (even 
        though " + name + " thinks it is in the pass.");
    }
    position = Position.END_PASS;
    trainsInPass--;
    railwaySystem.trace(name + ": leaving pass");
}

/**
 * Travel round the safe part of the railway (outside the pass).
 * @throws ProgrammingError if the train is not currently at the end of the 
 * pass (and therefore at the start of the
 *         safe part of the railway).
 */
public void choochoo() throws ProgrammingError {
    if (position != Position.END_PASS) {
        throw new ProgrammingError(name + " cannot traverse safe section, it is 
        not " + Position.END_PASS + ", it is " + position + ".");
    }
    railwaySystem.trace (name + ": choo-choo");
    delay();
    position = Position.START_PASS;
}

/**
 * Have a siesta.
 */
public void siesta() {
    railwaySystem.trace(name + ": zzzzz");
    delay();
}

/**
 * Cross the pass.
 * @throws SafetyViolationError if there is/are already train(s) on the pass.
 */
public void crossPass() throws RailwaySystemError {
    enterPass();
    if (trainsInPass > 1) {
        throw new SafetyViolationError("There are now " + trainsInPass + " 
        trains in the pass!");
    }
    railwaySystem.trace(name + ": crossing pass");
    delay();
    leavePass();
}

// Error flag must be shared so that we can stop all railways if something goes 
// wrong    

private static boolean errorFlag = false;
protected static String errorMessage = "";

/**
 * Run the railway.
 */
public void run() {
    setErrorFlag(false);
    try {
        runTrain();
    } catch (RailwaySystemError error) {
        setErrorFlag(true);
        errorMessage = error.getMessage();
        System.out.println("!!! Something went wrong with the railway.\n\t" + 
        errorMessage);
    }
    if (errorOccurred()) {
        System.out.println("!!! " + name() + " shut down because of an 
        error.\n\t" + errorMessage);
    } else {
        System.out.println(name() + " shut down because time limit was 
        reached.");
    }
}

/**
 * Each railway should independently define how the trains are to be run, using 
 * the basket(s).
 * to maintain safety on the pass.
 * @throws RailwaySystemError if a safety violation occurs while the railway is 
 * being run.
 */
public abstract void runTrain() throws RailwaySystemError, RailwaySystemError;

/**
 * Set the shared error flag (if an error occurs).
 * @param errorFlag is true iff an error has occured.
 */
public static void setErrorFlag(boolean errorFlag) {
    Railway.errorFlag = errorFlag;
}

/**
 * Check the current error status.
 * @return true iff an error is currently active.
 */
public static boolean errorOccurred() {
    return errorFlag;
}

}

最后，我得到了包含main方法的类。

公共类RailwaySystem {

private Clock clock = null; // the clock used to time railways - must be initialised for 
// each run
private List<Railway> railways;

public RailwaySystem(List<Railway> railways,Clock clock) {
    this.clock = clock;
    this.railways = railways;
    clock.register(this);
    for (Railway railway: railways) {
        railway.register(this);
    }
}

/**
 * Start the railway system
 */
private void start() {
    clock.start();
    for (Railway railway: railways) {
        railway.start();
    }
}

/**
 * Wait for the system to stop
 */
private void stop() throws RailwaySystemError {
    try {
        clock.join();
        for (Railway railway: railways) {
            railway.join();
        }
    } catch (InterruptedException interrupt) {
        throw new RailwaySystemError("The railway system was interrupted: " + 
        interrupt.getMessage());
    }
}

/**
 * Given a railway, get the next one in the system's list
 * @param railway the given railway
 * @return the next railway in the list 
 * @throws ProgrammingError if railway is neither peru not bolivia
 */
public Railway getNextRailway(Railway railway) throws ProgrammingError {
    int index = railways.indexOf(railway);
    if (index == -1) { // railway is not in the list
        throw new ProgrammingError(railway.name() + " is not registered with this system");
    }
    return railways.get((index+1) % railways.size());
}

/**
 * Get this system's clock
 * @return the system's clock
 * @throws SetUpError if the clock is not initialised
 */
public Clock getClock() throws SetUpError {
    if (clock == null) {
        throw new SetUpError("Clock has not been intialised");
    }
    return clock;
}

/**
 * Provide a facility for switching tracing on/off.
 **/
private boolean tracingOn = false;

/**
 * Switch tracing on.
 **/
public void traceOn() {
    tracingOn = true;
}

/**
 * Switch tracing off.
 **/
public void traceOff() {
    tracingOn = false;
}

/**
 * Trace, if tracing is on
 * @param trace the trace to be output
 */
public synchronized void trace(String trace) {
    if (tracingOn) {
        System.out.println(trace);
    }
}

public static void main(String[] args) throws RailwaySystemError {
    List<Railway> railways = new ArrayList<Railway>();
    railways.add(new Peru());
    railways.add(new Bolivia());
    Clock clock = new Clock(1.0,20); // 20 ticks of 1 second
    RailwaySystem system = new RailwaySystem(railways,clock);
    system.traceOn();
    system.start();
    system.stop();
}

}

我需要在我的runTrain()方法中允许同步，这是我目前遇到的问题。非常感谢

Answer 1

你正在编写的代码有很多buggy。那是..。这不是一个好兆头，你的教授/书不懂线程，但他们却试图教你。

public void traceOff() {
    tracingOn = false;
}

public synchronized void trace(String trace) {
    if (tracingOn) {
        System.out.println(trace);
    }
}

每根线都有一枚邪恶的硬币。任何时候，任何线程访问任何变量(用于读取或写入)，该线程都会抛出这个硬币。头，它将使用自己的本地副本。即使只有一个字段，每个线程都有它的一个缓存副本，并且在头上，线程只更新/查看它的本地副本。尾部，并且它使用/更新实际字段而不是副本。

这枚硬币是邪恶的:它不是一枚“公平”的硬币，今天当你编写它并运行测试时，它很可能每次都会抛出尾巴。然后，当重要的客户进来，你演示你的应用程序时，硬币总是正面抛出。因为墨菲就是不喜欢你。

解决方案是要么阻止VM抛硬币，要么确保您的代码不关心结果。

确保VM不翻转它的唯一方法是在设置字段的行和读取字段的行之间建立所谓的“先来/后来”(CBCA)关系。

换句话说，上面的一对动作(traceOff和trace) 不会像预期的那样工作，并导致抛出那枚邪恶的硬币，除非建立了CBCA关系，使得tracingOn = false调用‘先于’if (tracingOn)调用。这意味着:假设线程A将跟踪设置为on，3小时后，线程B调用trace，则允许tracing作为on运行，这将是一个合法的VM。它还可以表现为tracing处于关闭状态，而且这也是合法的: JMM故意不做任何保证。显然，这是一个有缺陷的应用程序。显然，这里的重点应该是跟踪功能始终处于打开状态。不幸的是，这需要一个CBCA关系，而这段代码没有建立这种关系。那么，如何做到这一点呢？

synchronized是这样做的一种方法，但是这里没有正确地完成它。每当代码退出synchronized (x)块时，当其他代码随后进入synchronized (x)块时(由于已同步，这些事件不可能同时发生)，线程1执行的所有代码都“先于”来自线程2的代码。

这里没有发生这种情况：traceOff方法根本不是synchronized，因此不存在CBCA关系，因此这段代码是损坏的。

private static Basket sharedBasket = new Basket("shared basket");

这绝对应该是final。

目前的问题是，我目前的方法不允许同步让两列火车同时通过。

这看起来不太对。你的代码确实试图解决这个问题；这肯定是所有关于把石头放进篮子里的东西的目的：

getBasket().putStone(this)；while (nextRailway.getBasket().hasStone(this)) { getBasket().takeStone(this)；siesta()；getBasket().putStone(this)；}

这段代码没有任何意义--篮子里的一块石头表示通行证中还有另一列火车，所以当那里有一块石头时，你可以等待，但你可以拿到石头！那就意味着如果有第三列火车出现，哈伯姆。别碰那块石头。别管它了。

我假设这个篮子的代码是提供的(不是你写的)，并且是线程安全的，但是我们已经确定你的教授/这本书似乎不知道如何编写threadsafe代码，这是一个假设，正如wikipedians所说，获得了需要的引用。假设篮子代码是正确的，并且是threadsafe，那么，您已经拥有了所需的所有工具，但是您没有以正确的方式使用它们。

毫无疑问，要穿过山口，你必须在篮子里放一块石头，但前提是那里还没有石头，然后穿过山口，然后把石头拿出来，表示你的旅程已经结束。如果你不能把一块石头放进篮子里(因为里面已经有一块石头了)，那么等待一段时间，稍后再试一次。在你成功地将一块石头放入空篮子之前，不要进入通行证。

这里有两个重要的实现：

1. ‘检查石子是否在篮子里’和‘把石头放在篮子里’这两个任务是交织在一起的:你不能按顺序来做；如果两列火车都检查篮子，都看到篮子是空的，然后都把一块石头放进去，然后两个人都进入山口，然后两个火车都撞上并死于可怕的火热死亡，那该怎么办？“把石头放进去，但只有在还没有石头的情况下，才报告它是否成功”的概念是一个不能拆分的单一操作--这被称为原子operation.
2. No ，无论以什么方式，无论什么火车把石头放进篮子里，无论火车如何离开关口，都需要确保在完成时将石头移走。

货币篮子需要支撑，目前还不清楚是否会这样做。如果已经有一块石头在里面，putStone方法会失败吗？如果它成功了，它怎么会失败呢？它是返回一个布尔型false，还是抛出一些东西？

如果它没有失败(你可以把石头放在篮子里，即使里面已经有石头了)，这个方法几乎完全没有用--你需要在某个东西上使用synchronize来达到你的原子性要求。

如果它确实失败了，那么就使用它。您的算法需要更改为如下所示：

while (true) { // keep trying until we succeed.
    boolean actuallyPlacedStone = basket.putStoneIfBasketEmpty(this);
    if (!actuallyPlacedStone) {
       // the basket is filled, we can't go.
       siesta(); // sleep a while, and ...
       continue; // start from the top
    }

    // if we got here, we placed the stone!
    try {
        crossThePass();
    } finally {
        // no matter how we get out of that pass, be it on rails
        // or by tumbling down the mountain in a horrible accident...
        // the pass is now clear, so, take the stone with you.
        basket.takeStone(this);
    }
    break; // we're through, no need to repeat this process.
}

如果篮子没有任何线程保证，我想我们可以把它当做锁来使用。所有与篮子的交互现在必须在同步块中进行，以确保没有两个线程同时在篮子上操作，以及在周围建立，避免邪恶的硬币毁了我们的一天。我会创建助手方法：

public boolean placeStoneIfEmpty(Basket b) {
    synchronized (b) {
        if (b.hasStone()) return false;
        b.putStone(this);
        return true;
    }
}

public void removeStone(Basket b) {
    synchronized (b) {
        b.removeStone(this);
    }
}