1

我有以下代码片段(代码是用 Java 编写的,但我试图尽可能减少混乱):

class State {

   public synchronized read() {
   }

   public synchronized write(ResourceManager rm) {
       rm.request();
   }

   public synchronized returnResource() {
   }
}

State st1 = new State();
State st2 = new State();
State st3 = new State();



class ResourceManager {
   public syncronized request() {
       st2 = findIdleState();
       return st2.returnResource();
   }
}


ResourceManager globalRM = new ResourceManager();


Thread1() 
{
    st1.write(globalRM);
}


Thread2() 
{
    st2.write(globalRM);

}

Thread3()
{
    st1.read();

}

此代码片段有可能通过以下调用序列进入死锁:

Thread1: st1.write()
Thread1: st1.write() invokes globalRM.request()
Thread2: st2.write()
Thread1: globalRM.request() tries to invoke st2.returnResource(), but gets blocked because Thread2 is holding a lock on st2.
Thread2: st2.write() tries to invoke globalRM.request(), but gets blocked because globalRM's lock is with Thread1

Thread3: st2.read(), gets blocked.

我该如何解决这样的死锁?我想了一会儿,发现有某种有序的锁方法可以用来获取锁,但我想不出这样的解决方案。问题是,资源管理器是全局的,而状态是特定于每个作业的(每个作业都有一个顺序的 ID,如果有某种方法可以使用顺序来获取锁,则可以用于排序)。

4

2 回答 2

1

有一些选项可以避免这种情况,每个选项都有其优点和缺点:

1.) 对所有实例使用一个锁对象。这种方法实现起来很简单,但将您限制在一个线程来获取锁。如果同步块很短并且可伸缩性不是大问题(例如桌面应用程序又名非服务器),这可能是合理的。其主要卖点是实施的简单性。

2.) 使用有序锁定 - 这意味着无论何时您必须获得两个或更多锁,请确保获得它们的顺序相同。这说起来容易做起来难,可能需要对代码库进行大量更改。

3.) 完全摆脱锁。使用 java.util.concurrent(.atomic) 类,您可以实现多线程数据结构而不会阻塞(通常使用 compareAndSet-flavor 方法)。这当然需要更改代码库并需要重新考虑结构。通常需要重写代码库的关键部分。

4.) 当你使用不可变类型和对象时,许多问题就会消失。与原子 (3.) 方法很好地结合以实现可变的超结构(通常实现为更改时复制)。

要给出任何建议,您需要了解更多有关您的锁所保护内容的详细信息。

- - 编辑 - -

我需要一个无锁 Set 实现,这个代码示例说明了它的优点和缺点。我确实将 iterator() 实现为快照,实现它以抛出 ConcurrentModificationException 并支持 remove() 会有点复杂,我不需要它。我没有发布的一些引用的实用程序类(我认为丢失的引用部分的作用完全显而易见)。

我希望它至少可以作为如何使用 AtomicReferences 的起点。

/**
 * Helper class that implements a set-like data structure
 * with atomic add/remove capability.
 * 
 * Iteration occurs always on a current snapshot, thus
 * the iterator will not support remove, but also never
 * throw ConcurrentModificationException.
 * 
 * Iteration and reading the set is cheap, altering the set
 * is expensive.
 */
public final class AtomicArraySet<T> extends AbstractSet<T> {

    protected final AtomicReference<Object[]> reference =
        new AtomicReference<Object[]>(Primitives.EMPTY_OBJECT_ARRAY);

    public AtomicArraySet() {
    }

    /**
     * Checks if the set contains the element.
     */
    @Override
    public boolean contains(final Object object) {
        final Object[] array = reference.get();
        for (final Object element : array) {
            if (element.equals(object))
                return true;
        }
        return false;
    }

    /**
     * Adds an element to the set. Returns true if the element was added.
     * 
     * If element is NULL or already in the set, no change is made to the
     * set and false is returned.
     */
    @Override
    public boolean add(final T element) {
        if (element == null)
            return false;
        while (true) {
            final Object[] expect = reference.get();
            final int length = expect.length;
            // determine if element is already in set
            for (int i=length-1; i>=0; --i) {
                if (expect[i].equals(element))
                    return false;
            }
            final Object[] update = new Object[length + 1];
            System.arraycopy(expect, 0, update, 0, length);
            update[length] = element;
            if (reference.compareAndSet(expect, update))
                return true;
        }
    }

    /**
     * Adds all the given elements to the set.
     * Semantically this is the same a calling add() repeatedly,
     * but the whole operation is made atomic.
     */
    @Override
    public boolean addAll(final Collection<? extends T> collection) {
        if (collection == null || collection.isEmpty())
            return false;
        while (true) {
            boolean modified = false;
            final Object[] expect = reference.get();
            int length = expect.length;
            Object[] temp = new Object[collection.size() + length];
            System.arraycopy(expect, 0, temp, 0, length);
ELoop:      for (final Object element : collection) {
                if (element == null)
                    continue;
                for (int i=0; i<length; ++i) {
                    if (element.equals(temp[i])) {
                        modified |= temp[i] != element;
                        temp[i] = element;
                        continue ELoop;
                    }
                }
                temp[length++] = element;
                modified = true;
            }
            // check if content did not change
            if (!modified)
                return false;
            final Object[] update;
            if (temp.length == length) {
                update = temp;
            } else {
                update = new Object[length];
                System.arraycopy(temp, 0, update, 0, length);
            }
            if (reference.compareAndSet(expect, update))
                return true;
        }
    }


    /**
     * Removes an element from the set.  Returns true if the element was removed.
     * 
     * If element is NULL not in the set, no change is made to the set and
     * false is returned.
     */
    @Override
    public boolean remove(final Object element) {
        if (element == null)
            return false;
        while (true) {
            final Object[] expect = reference.get();
            final int length = expect.length;
            int i = length;
            while (--i >= 0) {
                if (expect[i].equals(element))
                    break;
            }
            if (i < 0)
                return false;
            final Object[] update;
            if (length == 1) {
                update = Primitives.EMPTY_OBJECT_ARRAY;
            } else {
                update = new Object[length - 1];
                System.arraycopy(expect, 0, update, 0, i);
                System.arraycopy(expect, i+1, update, i, length - i - 1);
            }
            if (reference.compareAndSet(expect, update))
                return true;
        }
    }

    /**
     * Removes all entries from the set.
     */
    @Override
    public void clear() {
        reference.set(Primitives.EMPTY_OBJECT_ARRAY);
    }

    /**
     * Gets an estimation how many elements are in the set.
     * (its an estimation as it only returns the current size
     * and that may change at any time).
     */
    @Override
    public int size() {
        return reference.get().length;
    }

    @Override
    public boolean isEmpty() {
        return reference.get().length <= 0;
    }

    @SuppressWarnings("unchecked")
    @Override
    public Iterator<T> iterator() {
        final Object[] array = reference.get();
        return (Iterator<T>) ArrayIterator.get(array);
    }

    @Override
    public Object[] toArray() {
        final Object[] array = reference.get();
        return Primitives.cloneArray(array);
    }

    @SuppressWarnings("unchecked")
    @Override
    public <U extends Object> U[] toArray(final U[] array) {
        final Object[] content = reference.get();
        final int length = content.length;
        if (array.length < length) {
            // Make a new array of a's runtime type, but my contents:
            return (U[]) Arrays.copyOf(content, length, array.getClass());
        }    
        System.arraycopy(content, 0, array, 0, length);
        if (array.length > length)
            array[length] = null;
        return array;
    }

}
于 2013-05-10T14:44:10.327 回答
0

任何死锁的答案都是以相同的顺序获取相同的锁。你只需要想办法做到这一点。

于 2013-05-10T12:42:16.710 回答