algorithm - 在页面遍历算法方面需要一些帮助

Question

我正在编写自己的操作系统，我想验证是否设置了脏位。所以我想遍历某个虚拟地址范围说 R!到 R2 并浏览页面并检查其设置与否。我正在寻找一个好的算法来执行此操作。我可以将每个页表级别视为树的级别并遍历每个级别。所以我可以使用 DFS 或 BFS。这样做有更好的算法吗？

Answer 1

使用depth first search如果你想检查每个条目。 DFS 只需要一个堆栈，深度不超过树中的层数，页表也只有几层深。

BFS 较慢且 requires additional storage .当广度优先属性让您提前突破时，它通常最有用。