0

我知道在迭代期间无法在不抛出 ConcurrentModificationException 的情况下编辑 HashMap 或 LinkedHashMap 内容。但是，我有一种情况需要应用它。我正在使用 Second Chance 算法的时钟实现编写虚拟内存模拟。注意：RAM 是一个 LinkedHashMap，因此迭代顺序遵循插入顺序。这是我目前的方法（其中 tmp、hand 和 entry 是在主循环逻辑之外声明的变量：

PTE tmp; // A tmp PageTableEntry reference used for shuffling PTEs across RAM and the Page Table
Iterator<Entry<Integer, PTE>> hand; // Iterator that represents the clock hand
Map.Entry<Integer, PTE> entry = null; // A tmp Map Entry ref that is used to store the return of the hand Iterator


hand = RAM.entrySet().iterator(); // Set the Clock hand to the oldest PTE in RAM
entry = hand.next(); // Advance the iterator to the first RAM entry
tmp = entry.getValue(); // Get the PTE the Clock hand is pointing at

while (tmp.ref && hand.hasNext()) { // Advance the clock hand through RAM until finding an unreferenced PTE
    debugPrint(String.format("while:The hand is pointing at page # %d, ref == %b\n", tmp.baseAddr, tmp.ref), 1);
    tmp.ref = false; // Set the ref bit to false to give the PTE a second chance
    entry = hand.next(); // Select next PTE in RAM
    tmp = entry.getValue();

}

if (tmp.ref && !hand.hasNext()) { // Corner Case: The clock hand has found all PTEs in RAM to be referenced, must follow FIFO
    debugPrint(String.format("!HasNext:The hand is pointing at page # %d, ref == %b\n", tmp.baseAddr, tmp.ref), 1);

    tmp.ref = false; // Marked for eviction, must be set to unreferenced
    hand = RAM.entrySet().iterator(); // Reset the clock hand to point back to the first PTE inserted.
    entry = hand.next();
    tmp = entry.getValue();

}

这会产生几乎正确的输出，但我的问题是每次使用算法时都不应该重新创建迭代器。我需要一种方法来存储迭代器将指向的下一个元素，以便我可以从 LinkedHashMap 中删除 tmp 并用新的 PageTableEntry 替换它，以便下次迭代器运行时它从停止的地方恢复，而不是看到新添加的条目，直到它到达末尾并且必须循环回来。

4

1 回答 1

0

Iterator 接口没有用于向其添加元素并防止并发修改的 API 是其目标之一，因此恐怕优化非常困难，除非您编写自己的 LinkedHashMap 实现。

我看不到地图键的任何用法，所以如果可以更改 LinkedHashMap，那么您可以通过使用队列来避免这种复杂性，如果您总是想要顺序处理，或者如果您有优先级队列也可以使用一些查找

于 2020-04-09T19:57:21.890 回答