CareerCup

To prevent the deadlock, could we define an order for the account ID or the account itself, make sure it is transitive, means, Order(A)>Order(B), Order(B)>Order(C), ==> Order(A)>Order(C), and Order(A)==Order(B) ==> A==B. Then you can lock each Accounts following their orders.

Reference: Java Concurrency in Practice, pg: 209

The answer to the 3rd part of the question is...inducing a lock ordering to avoid deadlock.

int fromHash = System.identityHashCode(a1)
int toHash = System.identityHashCode(a2)

if(fromHash < toHash){
synchronized(a1){
synchronized(a2){
.... swap amounts
}
}
}

else if(fromHash > toHash){
synchronized(a2){
synchronized(a1){
.... swap amounts
}
}
}

else{
synchronized(tieLock){
synchronized(a1){
synchronized(a2){
.... swap amounts
}
}
}
}

Don't synchronize the entire method, just the critical block:

Public void TransferAccount(AccountID  id1, AccountID id2){
    Account a1 = id1.GetAccount();
    Account a2 = id2.GetAccount();
 
    //Swap amounts.
    synchronized (this) {
        // This section should execute very quickly and affect performance very little
        Temp = a1.Balance;
        a1.Balance = a2.Balance;
        a2.Balance = Temp;
    }
}

In a banking scenario, you often have these conditions:

1) Individual accounts have very little activity.
2) Accessing accounts has very high latency.

A small problem to avoid is the race where the same account is being incremented/decrement at the exact same millisecond. This can be handled with a simple mutex.

The bigger problem is that additions/subtractions to an account can't actually be committed until the remote account confirms the trade.

From a practical standpoint, the bank wants to err on the side of rejecting transactions prematurely. In other words, it wants to avoid ever promising funds from an account that has uncommitted credits, but it is also wants to avoid promising funds where provisional debits would lessen the balance upon commit.

So let's say Alice agrees to transfer $100 to Bob's account, and the transaction is initiated from a data center remote to both banks. The financial soundness of the transaction only hinges on Alice having sufficient funds in her account, so the remote data center notifies Alice's bank of the desired transfer. If Alice's provisional balance is too low, the transaction is immediately rejected. Otherwise, her available balance is immediately debited, and you make sure the transaction can be committed on Bob's end (i.e. his account is active, the network is available, etc.). At this point, the transaction is sound from a financial standpoint, but you can't commit it until Bob eventually gets the money in his bank. So, then you post the transfer to Bob's account, and if he confirms it, you then commit the transfer on Alice's end.

Remember that I said that individual accounts have very little activity, so for each account, you can inexpensively manage a data structure of all the uncommitted transfers. In some cases uncommitted transfers will be explicitly rolled back by the other party, but you also have to account for data failures, so you will have expiration logic. Here, you need to be very careful managing funds availability. Alice's bank can't release funds for her until it's certain that Bob hasn't been credited. On the other hand, Bob's bank can roll back his credit after a timeout.

Asking this problem in terms of Java is kind of contrived, because this is really more of a systems engineering question than a coding question. With a single data center, you would be more likely to using a locking model than a phased commit model, but bank transactions typically involve lots of latency between banks.

public void TransferAccount(AccountID  id1, AccountID id2)
{
	//The idea is not to use the exclusive lock simultaneously which can cause deadlock. 
	Account a1 = id1.GetAccount();
	Account a2 = id2.GetAccount();

	//Get an exclusive lock on id1 and not so exclusive(read on id2 - will make sure that id2 value doesnt change and lock can be held by multiple threads.) 
	id1.writeLock().lock();
	id2.readLock.lock();
	temp = a1.getBalance();
	a1.Balance = a2.Balance;
	id2.readLock.unlock();
	id1.writeLock().unlock();

	//Get exclusive lock on id2 to write to it. 
	id2.writeLock().lock();
	a2.Balance = temp;
	id2.writeLock().unlock();
}

public void TransferAccount(AccountID  id1, AccountID id2)
{
	//The idea is not to get the exclusve lock which can cause deadlock. 
	Account a1 = id1.GetAccount();
	Account a2 = id2.GetAccount();

	//Get an exclusive lock on id1 and not so exclusive(read on id2 - will make sure that id2 value doesnt change and lock can be held by multiple threads.) 
	id1.writeLock().lock();
	id2.readLock.lock();
	temp = a1.getBalance();
	a1.Balance = a2.Balance;
	id2.readLock.unlock();
	id1.writeLock().unlock();

	//Get exclusive lock on id2 to write to it. 
	id2.writeLock().lock();
	a2.Balance = temp;
	id2.writeLock().unlock();
}

Ok so you don’t want to lock around the entire method since AccountID.GetAccount() is external code and you have no idea what it is doing. You don’t want to lock on the Ids or the Accounts for the same reason they are coming from elsewhere and may or may not be the same instance every time the method is called. If they are not the same instance every time then your locking does not work and you get straight into the locked code twice if lock on them. We only want to lock around code we have complete control of.

If we keep a collection of accounts that we are currently working on then we can use that to make sure that we do not try the same account twice at the same time. We can also then do our checks for both accounts within one lock.

//make a hash set 
private HashSet<AccountID> m_CheckedOutAccounts = new HashSet<AccountID>();
// create lock object
private object m_Lock = new object();

public bool TryCheckoutAccounts(AccountID one, AccountID two)
{
// take lock
  lock(m_Lock)
  {
  // if m_CheckoutOutAccounts does not contain one and two
    bool accountsAvailable = !m_CheckedOutAccounts.Contains(one) && !m_CheckedOutAccounts.Contains(two);
    if(accountsAvailable )
    {
      // add one and two to m_CheckedOutAccounts
      m_CheckedOutAccounts.Add(one);
      m_CheckedOutAccounts.Add(two);
    // end if 
    }
    // return true if accounts were added otherwise false
    return accountsAvailable; 
  // end lock
  }
}


public void FreeAccounts(AccountID one, AccountID two)
{
  //take lock
  lock(m_Lock)
  {
    // remove one and tow from m_CheckedOutAccounts
    m_CheckedOutAccounts.Remove(one);
    m_CheckedOutAccounts.Remove(two);
  // end lock
  }
}
public void TransferAccount(AccountID  id1, AccountID id2)
{
  // while the accounts are not checked out
  while(!TryCheckoutAccounts(id1, id2))
  {
  // wait for monitor use a timeout just incase
  // this could just as easilly work without the monitor it is just a bit nicer on the cpu
    Monitor.Wait(this, 1000);
  // end while
  }

  Account a1 = id1.GetAccount();
  Account a2 = id2.GetAccount();
 
  //Swap amounts.
 
  Temp = a1.Balance;
  a1.Balance = a2.Balance;
  a2.Balance = Temp;

  // free accounts
  FreeAccounts(id1, id2);
  // pulse monitor
  Monitor.Pulse(this);
}

Thank you for posting this problem!! It pushed me to read about alternatives for using locks.

For situations where you need good scalability with respect to the number of threads and the 'size' of the critical section, using a lock is not the correct way to go.

Using wait-free and lock-free approach may help alleviate the problem here. Use Compare And Swap (CAS) or its variants. Since I am still learning about CAS and it use, here are some pointers to help you guys out. [ibm].com/developerworks/library/j-jtp11234/]
[http:][//audidude][.com/?p=363]

Java has a .util.concurrency.atomic package provides support for wait-free and lock-free approaches.
I will post out a solution as soon as I get a grip on the CAS idea and its likes.

class Account {

		private Lock balanceLock;
		private double balance;

		public Account()
		{
			balanceLock = new ReentrantLock();
		}


		public synchronized setAccount(double newBal)
		{
			balance = newBal;
		}

		public synchronized double getBalance()
		{
			return balance;
		}

	}

	/****************************   ANSWER *************************/

	public void TransferAccount(AccountID  id1, AccountID id2){
		Account a1 = id1.GetAccount();
		Account a2 = id2.GetAccount();
 
		//Swap amounts.
 
		double temp = a1.getBalance();
		a1.setBalance(a2.getBalance()); 
		/**  will get a2 balance until synchronization ends, then will run a1.setBalance() **/
		double temp2 = a2.getBalance(); // if a2.getBalance() as a parameter causes deadlock, but it shouldn't
		a2.setBalance(temp);
}

Are these questions asked during the interview for SDE internship or just SDE full-time job?

I think there are anyway two read and write operations in one atomic process, so it is obviously not CAS, and also can't be solved by the way ConcurrentHashMap and AtomicXXX did.
If those two accounts have the reference pointing to the same object like user, we may use user object for locking, otherwise I did not figure out a high efficient way to do it.

Homework? Multiple questions on threading/synchronization/deadlocks...