java - 如何处理Map 中对List的同步访问？

Question

更新：请注意。
我提出的问题得到了回答。对于我来说不幸的是，这个问题比标题中的问题要大得多。除了向地图添加新条目外，我还必须同时处理更新和删除。如果没有一个或另一个，我想到的方案似乎无法实现：
一种。僵局
b。复杂且耗时的检查和锁定
检查问题的底部是否有最终想法。

原始帖子：

你好

我有一个带地图的四季豆。

这是我要用于的用途：

很少有并发的JMS侦听器将接收带有动作的消息。每个动作由两个用户组成：长用户A和长用户B。消息将具有其自己的String ReplyTo队列，该队列将用于标识操作。
因为当一个用户参与另一个已执行的动作时，我不允许执行一个动作，所以我将使用此映射作为正在发生的事情的注册表，并控制动作的执行。
假设我收到了三个操作：
1. userA，userB
2. userB，userC
3. userC，userA

收到第一个动作时，地图为空，因此我将在其中记录有关该动作的信息并开始执行该动作。
收到第二个动作后，我可以看到userB忙于第一个动作，因此我只记录有关该动作的信息。
第三动作也一样。

地图将如下所示：
[userA：[action1，action3]，
userB：[action1，action2]，
userC：[action2，action3]

完成第一个操作后，我将从注册表中删除有关该信息的信息，并获取有关userA和userB的下一个操作[action3，action2]的信息。然后，我将尝试重新启动它们。

我想到现在，您已经可以对这张地图进行操作了。

因为要同时从多个线程访问map，所以我必须以某种方式处理同步。

我将有一些方法可以在操作完成后向地图添加新信息并从地图中删除信息。 remove方法将为刚刚为其完成操作的两个用户返回下一步操作（如果有）。

因为可能同时执行数百个动作，并且繁忙用户的动作百分比应该很小，所以我不想为每个添加/删除操作都阻止对地图的访问。

我考虑过仅对Map中的每个列表进行同步访问，以允许同时访问多个用户条目。但是...因为没有为该用户留下任何动作，所以我想从地图中删除该用户的条目。另外...当用户在地图中没有任何条目时，我将不得不创建一个。我有点担心那里可能存在冲突。

处理这种情况的最佳方法是什么？
使两种方法（添加和删除）同步（我认为是最坏的情况）是唯一正确的[安全]方法吗？

另外，我将有另一个映射，其中将包含操作ID作为键，而包含用户ID作为值，因此更容易识别/删除用户对。我相信我可以跳过这一步的同步，因为在任何情况下，一个动作都不会同时执行两次。

尽管代码是Groovy的，但我相信没有Java程序员会觉得很难阅读。它背后是Java。
请考虑将其作为伪代码，因为我只是在制作原型。

class UserRegistry {

    // ['actionA':[userA, userB]]
    // ['actionB':[userC, userA]]
    // ['actionC':[userB, userC]]
    private Map<String, List<Long>> messages = [:]
    /**
     * ['userA':['actionA', 'actionB'],
     * ['userB':['actionA', 'actionC'],
     * ['userC':['actionB', 'actionC']
     */
    private Map<long, List<String>> users = [:].asSynchronized()

    /**
     * Function will add entries for users and action to the registry.
     * @param userA
     * @param userB
     * @param action
     * @return true if a new entry was added, false if entries for at least one user already existed
     */
    public boolean add(long userA, long userB, String action) {
        boolean userABusy = users.containsKey(userA)
        boolean userBBusy = users.containsKey(userB)
        boolean retValue
        if (userABusy || userBBusy)  {
            if (userABusy) {
                users.get(userA).add(action)
            } else {
                users.put(userA, [action].asSynchronized())
            }
            if (userBBusy) {
                users.get(userB).add(action)
            } else {
                users.put(userB, [action].asSynchronized())
            }
            messages.put(action, [userA, userB])
            retValue = false
        } else {
            users.put(userA, [action].asSynchronized())
            users.put(userB, [action].asSynchronized())
            messages.put(action, [userA, userB])
            retValue = true
        }
        return retValue
    }

    public List remove(String action) {
        if(!messages.containsKey(action)) throw new Exception("we're screwed, I'll figure this out later")
        List nextActions = []
        long userA = messages.get(action).get(0)
        long userB = messages.get(action).get(1)
        if (users.get(userA).size() > 1) {
            users.get(userA).remove(0)
            nextActions.add(users.get(userA).get(0))
        } else {
            users.remove(userA)
        }
        if (users.get(userB).size() > 1) {
            users.get(userB).remove(0)
            nextActions.add(users.get(userB).get(0))
        } else {
            users.remove(userB)
        }
        messages.remove(action)
        return nextActions
    }
}

编辑
我昨晚想到了这个解决方案，看来消息map可能消失了，而用户Map可能是：

Map users<String, List<UserRegistryEntry>>

哪里
UserRegistryEntry：
字符串actionId
布尔等待

现在假设我执行了以下操作：

动作1：userA，userC
动作2：userA，userD
动作3：userB，userC
动作4：userB，userD

这意味着可以同时执行动作1和动作4，并且阻塞动作2和动作3。地图如下所示：

[
[userAId: [actionId: action1, waiting: false],[actionId: action2, waiting: true]],  
[userBId: [actionId: action3, waiting: true], [actionId: action4, waiting: false]],  
[userCId: [actionId: action1, waiting: false],[actionId: action3, waiting: true]],
[userDId: [actionId: action2, waiting: true], [actionId: action4, waiting: false]]
]

这样，完成动作执行后，我将使用以下方法从地图中删除条目：
userAId，userBId，actionId
并详细了解有关userA和userB的第一个非阻塞等待操作的信息（如果有的话），并将它们传递给执行。

现在，我将需要两种方法，即将数据写入Map并将其从Map中删除。

public boolean add(long userA, long userB, String action) {
    boolean userAEntryExists = users.containsKey(userA)
    boolean userBEntryExists = users.containsKey(userB)
    boolean actionWaiting = true
    UserRegistryEntry userAEntry = new UserRegistryEntry(actionId: action, waiting: false)
    UserRegistryEntry userBEntry = new UserRegistryEntry(actionId: action, waiting: false)
    if (userAEntryExists || userBEntryExists) {
        if (userAEntryExists) {
            for (entry in users.get(userA)) {
                if (!entry.waiting) {
                    userAEntry.waiting = true
                    userBEntry.waiting = true
                    actionWaiting = true
                    break;
                }
            }
        }

        if (!actionWaiting && userBEntryExists) {
            for (entry in users.get(userB)) {
                if (!entry.waiting) {
                    userAEntry.waiting = true
                    userBEntry.waiting = true
                    actionWaiting = true
                    break;
                }
            }
        }
    }

    if (userBEntryExists) {
        users.get(userA).add(userAEntry)
    } else {
        users.put(userA, [userAEntry])
    }

    if (userAEntryExists) {
        users.get(userB).add(userBEntry)
    } else {
        users.put(userB, [userBEntry])
    }

    return actionWaiting
}

对于删除：

public List remove(long userA, long userB, String action) {
        List<String> nextActions = []
        finishActionAndReturnNew(userA, action, nextActions)
        finishActionAndReturnNew(userB, action, nextActions)

        return nextActions;
    }

    private def finishActionAndReturnNew(long userA, String action, List<String> nextActions) {
        boolean userRemoved = false
        boolean actionFound = false
        Iterator itA = users.get(userA).iterator()
        while (itA.hasNext()) {
            UserRegistryEntry entry = itA.next()
            if (!userRemoved && entry.actionId == action) {
                itA.remove()
            } else {
                if (!actionFound && isUserFree(entry.otherUser)) {
                    nextActions.add(entry.actionId)
                }
            }
            if (userRemoved && actionFound) break
        }
    }

    public boolean isUserFree(long userId) {
        boolean userFree = true
        if (!users.containsKey(userId)) return true
        for (entry in users.get(userId)) {
            if (!entry.waiting) userFree = false
        }
        return userFree
    }

最后思考：
这种情况是致命的：
[ActionID，userA，userB]
[a，1,2]
[b，1,3]
[c，3,4]
[d，3,1]
动作a和c同时执行，b和d等待。
完成a和c后，将必须删除用户1、2、3、4的条目，因此一个线程将被锁定1和2，另一个线程将被锁定3和4。当这些用户被锁定时，必须检查每个用户的下一个动作。当代码确定用户1的下一个动作与用户3相关，而用户3的下一个动作与用户1相关时，乳清将尝试锁定它们。这是发生僵局的时候。我知道我可以对此进行编码，但是似乎要花很多时间才能执行，而且它会阻塞两个工作人员。
现在，我将问另一个关于SO的问题，更多关于我的问题，并尝试同时使用JMS解决方案原型。

Answer 1

您可能需要再次查看同步（集合）的工作方式：

这（作为一个非排他性的示例）不是线程安全的：

if (users.get(userA).size() > 1) {
    users.get(userA).remove(0)

请记住，只有单个“同步”方法才能保证是原子的，而没有更大的锁定范围。

快乐的编码。

编辑-每个用户的同步锁（已更新以进行评论）：

仅通过使用标准数据结构，您就可以通过使用 ConcurrentHashMap来实现每键锁定-尤其是通过使用'putIfAbsent'方法。 （这与仅使用“同步的HashMap”的get / put有很大的不同，请参见上文。）

以下是一些伪代码和注释：

public boolean add(long userA, long userB, String action) {
    // The put-if-absent ensures the *the same* object but may be violated when:
    //   -users is re-assigned
    //   -following approach is violated
    // A new list is created if needed and the current list is returned if
    // it already exists (as per the method name).
    // Since we have synchronized manually here, these lists
    // themselves do not need to be synchronized, provided:
    // Access should consistently be protected across the "higher"
    // structure (per user-entry in the map) when using this approach.
    List listA = users.putIfAbsent(userA, new List)
    List listB = users.putIfAbsent(userB, new List)
    // The locks must be ordered consistently so that
    // a A B/B A deadlock does not occur.
    Object lock1, lock2
    if (userA < userB) {
        lock1 = listA, lock2 = listB
    } else {
        lock1 = listB, lock2 = listA
    }
    synchronized (lock1) { synchronized (lock2) {{ // start locks

    // The rest of the code can be simplified, since the
    // list items are already *guaranteed* to exist there is no
    // need to alternate between add and creating a new list.
    bool eitherUserBusy = listA.length > 0 || listB.length > 0
    listA.add(action)
    listB.add(action)
    // make sure messages allows thread-safe access as well
    messages.put(action, [userA, userB])
    return !eitherUserBusy

    }} // end locks
}

我不知道在您的使用情况下，相对于单个公共锁对象如何公平。通常建议“简单”使用，除非这样做有明显的优势。

HTH和快乐编码。