请求分段存储管理LRU

### 请求分段存储管理中的LRU算法

#### LRU算法概述
最近最少使用（Least Recently Used, LRU）是一种常用的页面替换策略，在请求分段存储管理系统中用于决定当内存满时应该移除哪个段。该算法基于局部性原理，认为近期被频繁使用的数据在未来一段时间内仍然会被继续使用，而长时间未被访问的数据则很可能不再需要[^2]。

#### 数据结构设计
为了支持高效的LRU操作，通常会维护如下两种主要的数据结构：

- **双向链表**：记录所有已加载到物理内存中的段，并保持其顺序反映各段最后被访问的时间先后关系。最新访问过的位于头部，最久未访问的处于尾部。

- **哈希映射**：提供快速查找功能，键为虚拟地址空间里的段号，值是指向对应节点（即上述双向链表中的元素）的指针。

这种组合使得可以在常数时间内完成插入、删除和查询操作。

#### 地址转换过程
在进行正常的地址翻译过程中，如果遇到缺段异常，则意味着当前试图访问的目标段不在内存里。此时需触发相应的处理流程：
1. 如果存在空闲帧可用，则直接将所需段载入；
2. 否则依据LRU原则挑选出一个合适的牺牲品——即将被淘汰出去的那个段；
3. 执行实际的数据传输动作，包括但不限于从磁盘读取新段并写回旧段至外部存储设备；
4. 更新相关元数据信息，比如修改段表条目状态位等字段的内容；
5. 完成之后重新尝试引发此次缺失事件的那条指令。

struct SegmentNode {
    int segment_id;
    struct ListNode *prev, *next;

    // Constructor to initialize a new node with given id.
    SegmentNode(int sid):segment_id(sid), prev(nullptr), next(nullptr){}
};

// Hash table mapping from virtual address space segments IDs to their corresponding nodes in the doubly linked list.
unordered_map<int, SegmentNode*> hash_table;

// Doubly Linked List representing current order of usage among all loaded segments.
SegmentNode* head = nullptr;  // Points at most recently used element.
SegmentNode* tail = nullptr;  // Points at least recently used one.

void access_segment(int seg_id){
    auto it = hash_table.find(seg_id);
    
    if(it != end(hash_table)){
        move_to_head(it->second);  // Move accessed segment closer towards front indicating recent use.
    }else{
        load_new_segment(seg_id);  // Load newly referenced but not yet present segment into memory.
    }
}

void evict_least_recent(){
    remove_from_list(tail);       // Remove and possibly swap out oldest unused entry according to LRU policy.
}