Java作业面试线程编程测试。他们想要什么答案？

Question

编辑:我添加了下面使用的实现，并且..。

...I看到了我做错了什么:虽然AtomicInteger balance对象是(我认为)线程安全的，但是涉及两个操作，即获取当前余额，然后更新它。因此，在得到它和更新它之间，平衡可能发生变化。

尽管如此，我仍然想知道什么是最好的解决方案，他们在寻找什么。

(此外，就可扩展性而言，例如转移余额的可能性，我故意没有提及。这似乎超出了任务的范围。如果不是我的错)

我刚刚收到了第二个负面的回答，我的家庭编程测试涉及线程由一个潜在的雇主。

我不知道我给出的解决方案是否一定是错的--可能不是他们想要的。不过在这一点上，我很困惑，也不知道那是什么。

这基本上就是您得到的Java问题：

public interface BalanceManagementSystem { //Edit: Changed name 
 /**
  * Deduct 'amountToWithdraw' of the given 'accountId' from account.
  * @param accountId The ID of the account to withdraw from
  * @param amountToWithdraw The quantity to withdraw
  * @return TODO: to be implemented
  */
 WithdrawalResult withdrawFromAccount(String accountId, int amountToWithdraw);

 /**
  * Add 'amountToDeposit' of the given accountId to inventory.
  * @param accountId The ID of the account to deposit to
  * @param amountToDeposit The quantity to deposit
  * @return TODO: to be implemented
  */
 DepositResult depositToAccount(String accountId, int amountToDeposit);
}

...so，您必须为上述两种方法实现具有线程安全方法的接口。我知道。

除了标准JDK包之外，不能使用任何外部依赖项。

其余的要求都有点模糊。最后，在没有数据库的情况下，我使用：

1. HashMap作为包含(我自己的)帐户对象的数据结构。
2. 用于将余额存储在帐户对象中的AtomicInteger，以加强线程安全。

显然这不是他们想要的答案。我很确定线程安全问题是哪里出了问题。

因此，对于给出和评估这样的线程测试的雇主或经理，或者是通过测试的员工，需要什么样的解决方案？

备注

用于存储的HashMap使用accountId作为密钥。

AtomicInteger不包含subtractAndGet()，所以我对它进行了子类化，创建了AtomicIntegerPlus。subtractAndGet()只是对本机addAndGet()的轻微修改。

class Account {
    private String accountId;

    private AtomicIntegerPlus balance; //Thread-safe object subclassed from AtomicInteger

    Account(String acctId, String loc, AtomicIntegerPlus amt) {
        this.accountId = acctId;
        this.balance = amt;
    }

    public void addToBalance(int amt) {
        balance.addAndGet(amt);
    }

    public void subtractFromBalance(int amt) {
        balance.subtractAndGet(amt);
    }
}

class BMS implements BalanceManagementSystem {
    private HashMap<String, Account> hashMap;
    -
    -

    /**
    * Deduct 'amountToWithdraw' of the given 'accountId' from account.
    * @param accountId The ID of the account to withdraw from
    * @param amountToWithdraw The quantity to withdraw
    * @return withdrawalResult
    */
    public WithdrawalResult withdrawFromAccount(String accountId, int amountToWithdraw) {

        if (hashMap.containsKey(accountId)) {           
            Account tmpAccount = (Account)hashMap.get(accountId);           
            int balance = tmpAccount.getBalance();

            if (balance >= amountToWithdraw) {              
                tmpAccount.subtractFromBalance(amountToWithdraw);
                hashMap.put(tmpAccount.getAccountId(), tmpAccount); //Updatebalance with new amount

                withdrawalResult.setMessage("Withdrawn. You now have " + tmpAccount.getBalance() + " left");

            } else {
                withdrawalResult.setMessage("Don't have the balance for your request. Only " + balance + " left");
            }

        } else {
            withdrawalResult.setMessage("Sorry: account id " + accountId + " does not exist");
        }

        return withdrawalResult;
    }

    /**
    * Add 'amountToDeposit' of the given accountId to inventory.
    * @param accountId The ID of the account to deposit to
    * @param amountToDeposit The quantity to deposit
    * @return depositResult
    */
    public DepositResult depositToAccount(String accountId, int amountToDeposit) {      

        if (hashMap.containsKey(accountId)) {           
            Account tmpAccount = (Account)hashMap.get(accountId);

            tmpAccount.addToBalance(amountToDeposit);       
            hashMap.put(tmpAccount.getAccountId(), tmpAccount);// Update Balance with new amount

            depositResult.setMessage("Deposited. You now have " + tmpAccount.getBalance() + " left");

        } else {
            depositResult.setMessage("Sorry: account id " + accountId + " does not exist");
        }

        return depositResult;
    }
}

Answer 1

您提供的解决方案显示了以下几个弱点：

( a)您似乎还没有完全理解引用类型(Java中的类)和值类型之间的区别。下面的代码说明了这一点：

Account tmpAccount = (Account)hashMap.get(accountId);
// ...
tmpAccount.subtractFromBalance(amountToWithdraw);
hashMap.put(tmpAccount.getAccountId(), tmpAccount);

在这里，您将通过引用从映射中获取一个Account类型的对象，并更改它的状态(使用substractFromBalance)。没有必要将它放回地图中--您已经更新了仍然存储在地图中的引用--而不是它的副本。

此错误与

( b) HashMap周围没有同步

如果帐户在生命周期内发生变化(对于银行系统来说这是非常正常的)，那么您将需要对hashMap的所有访问进行同步。你不能为此做任何事。您可能会认为，帐户是从程序一开始就修复的，并且永不更改--这将使您能够避免同步。但是，在您的代码示例中，您避免了这样的争论:通过调用hashMap.put(...)，您可以改变hashMap，这是非线程安全操作。

( c)在检查余额和更新余额之间，您的程序中有一个竞赛条件。如果其他线程也从中间的帐户中提取，您最终可能会出现负余额。如果您使用atomics，这里需要一个compareExchange循环。

( d)原子添加的实现可能不正确

我只能推测这一点，因为您没有提供AtomicIntegerPlus的源代码。我的第一个想法是:您不需要这个，因为普通的AtomicInteger已经具备了所需的一切。而且您的程序也不需要substractAndGet (您从不使用返回值)。那么问题是如何实现它:如果它像AtomicInteger.addAndGet(-value); return AtomicInteger.get();，那么它就错了，因为它不再是原子的了。无论如何，AtomicInteger.addAndGet(-value);已经足够了。

一个简单正确的解决方案只需在HashMap周围使用一个锁，甚至不需要atomics：

public WithdrawalResult withdrawFromAccount(String accountId, int amountToWithdraw) {
    WithdrawalResult withDrawalResult = new WithdrawalResult();

    synchronized(hashMap) {
        Account account = hashMap.get(accountId);    
        if (account != null) {                           
            int balance = account.getBalance();
            if (balance >= amountToWithdraw) {              
                account.setBalance(balance - amountToWithdraw);
                withdrawalResult.setMessage("Withdrawn. You now have " +   tmpAccount.getBalance() + " left");
            } else {
                withdrawalResult.setMessage("Don't have the balance for your request. Only " + balance + " left");
            }
        } else {
            withdrawalResult.setMessage("Sorry: account id " + accountId + " does not exist");
        }
    }

    return withdrawalResult;
}

Answer 2

假设您在特定帐户上有1000个帐户。900美元的两笔同时提款正在发生。您的基于AtomicInteger的解决方案是否确保您不会以负数结束？这是可以完成的(例如，通过循环中的compareAndSet )，但与同步相比可能有点过于复杂。

根据我的经验，实际问题(可能是对您的实现的后续)不仅仅是以线程安全的方式实现取款或存款，而是以线程安全的方式在两个帐户之间进行转移。您需要确保在并发事务情况下不会透支帐户，并且如果使用简单的同步方案并以交叉传输结束，则不会陷入死锁。基于AtomicInteger的解决方案使实现和推理变得非常困难(我仍然接受它，但您需要100%肯定地捍卫您的CAS逻辑)

Answer 3

HashMap作为包含(我自己的)帐户对象的数据结构。

第一个问题是，HashMap不是一个同步类，而且您似乎没有保护它不受同步访问的影响。如果两个线程同时尝试访问同一个HashMap，则可以得到数据损坏、无限循环等。

一个快速的解决方案是使用ConcurrentHashMap，它将阻止程序崩溃，但不能完全处理代码中的争用条件。您需要担心的是，如果两个线程同时对一个帐户执行第一次操作。如果您总是执行put(...)操作，那么第二个线程将覆盖第一个线程。您需要使用ConcurrentHashMap的putIfAbsent(...)方法。

Account account = concurrentMap.get(accountId);
if (account == null) {
   account = new Account();
   Account oldAccount = concurrentMap.putIfAbsent(accountId, account);
   if (oldAccount != null) {
      // some other thread beat us to it
      account = oldAccount;
   }
}

我看到的另一个问题是，您正在将Account重新放到地图中。这应该在上面的代码中只进行一次。它应该在您的两个方法共享的getAccount(accountId)方法中。

...I看到了我做错了什么:虽然AtomicInteger balance对象是(我认为)线程安全的，但是涉及两个操作，即获取当前余额，然后更新它。因此，在得到它和更新它之间，平衡可能发生变化。

这也是一个需要一些技巧来解决的问题。任何更新循环都需要类似于以下伪代码：

while (true) {
   int balance = account.getBalance();
   // test balance and print error here
   int newBalance = balance + adjustment;
   if (account.adjustBalance(balance, newBalance)) {
      break;
   }
}

然后在Account对象中执行如下操作：

 public boolean adjustBalance(int oldBalance, int newBalance) {
    // this returns true if balance is still oldBalance and only then it updates it to new
    return balance.compareAndSet(oldBalance, newBalance);
 }

每当您更新余额时，您都需要获取值，更改值，然后尝试将其存储回去，但只有当余额在此期间未被其他线程更新时，此操作才会成功。这个循环是一个非常典型的模式，用于JDK和其他地方的许多不同地方。

最后，我认为扩展AtomicInteger以添加subtractAndGet(...)是过分的做法。带有负数的AddAndGet(...)将是相当好的。