链表是FIFO类页表置换算法模拟的首选，因其天然契合先进先出逻辑，插入尾部、删除头部均为O(1)；多级缓存场景下可用两级链表区分活跃与备用页，并通过预分配数组和空闲链表实现零动态内存分配。
页表置换算法模拟中，链表为何是管理页面驻留顺序的首选
在fifo类置换算法模拟里，链表天然匹配“先进先出”的逻辑。它不依赖索引或哈希计算，只靠节点插入和删除的位置关系就能准确反映页面进入内存的时间先后。比如用一个单向链表维护当前在内存中的页号，新页总插在尾部，淘汰时直接取头部节点——这种操作时间复杂度稳定为o(1)，比遍历数组找最老页更高效，也比维护时间戳再排序更轻量。
多级缓存页场景下，链表变量要区分“活跃”与“备用”两个队列
真实系统中常有L1/L2缓存分层，模拟时可对应设计两级链表：一级链表存最近被访问过的热页（类似LRU局部热点），二级链表存曾驻留但近期未用的冷页（类似FIFO后备池）。当一级满且发生缺页时，优先从二级链表头部淘汰；若二级为空，则按FIFO规则从一级链表头部淘汰。这样既保留了FIFO的简单性，又引入了访问热度的粗粒度区分。
- 一级链表节点带访问计数器，每次命中就+1，定期扫描将低频页移入二级链表
- 二级链表节点附加一个“上次移出时间”，避免刚移出就因新缺页又被拉回
- 两链表共用同一组页表项结构，仅通过指针域指向不同链表头尾
链表变量生命周期管理的关键细节
模拟程序运行中，链表节点不能随页面换入换出频繁malloc/free，否则易引发内存碎片或性能抖动。推荐做法是预分配固定大小的页表项数组（如total_vp个），每个元素既是页表项，也是链表节点。链表操作只改指针域（next、prev），不触碰数据域。初始化时用空闲链表串起所有未使用的节点，换入时从空闲链表取，换出时归还——这样整个模拟过程全程零动态内存申请。
特别注意：当某页被置换出去后，必须将其从原链表中彻底摘除，并清空其在页表中的物理块号和有效位，否则后续地址转换会误判为已在内存。
调试时容易忽略的链表陷阱
链表操作看似简单，但在页面并发访问模拟中极易出错。常见问题包括：
- 链表头/尾指针未初始化为NULL，导致野指针访问
- 页面重复加入同一链表（如缺页处理中未检查是否已在内存），造成环形链表
- 淘汰页面后忘记更新页表项的valid标志，下一次访问仍认为该页在内存
- 多线程模拟中未加锁，两个线程同时操作同一链表导致节点丢失
建议在关键链表操作前后加入断言（assert），例如插入前检查目标页号不在链表中，删除后验证链表长度减1——这些小习惯能快速定位90%以上的链表逻辑错误。
