通常使用什么数据结构来实现帧表？

Question

我必须为操作系统项目实现一个帧表，以跟踪物理内存(而不是虚拟内存的页面)中的哪些帧正在使用或空闲。最重要的事情之一是决定用于帧表的数据结构。根据您的经验，帧表通常是如何实现的，就它们使用的数据结构而言？在我的例子中，条目必须保存指向物理内存中的帧的指针。您是否建议完全使用数组、列表、哈希表或其他方式？

Answer 1

Windows和Linux都使用结构数组，其中数组的每个元素都描述物理地址空间的一个页帧。因此，如果总共有128个页帧，则数组将包含128个结构。

在Windows上，此数组称为PFN数据库。每个结构描述帧的状态(无论是已分配的还是空闲的)，并且通常包括映射到它的那些页表项的一个或多个物理地址。为了使查找空闲帧比仅仅线性扫描数组更有效，每个元素都包含一个指向相同状态的下一个元素的指针。所以基本上有一个空闲帧的链表。

在Linux上，该数组称为mem_map，系统中的每个NUMA节点都有一个这样的数组。