操作系统调度、浏览器历史——使用线性表实现

操作系统调度中的线性表实现

在操作系统（如Linux内核）中，进程调度通常涉及队列（Queue），例如就绪队列（Ready Queue）用于管理等待CPU的进程。这是一种线性表的形式，遵循FIFO原则（或优先级变体）。根据需求（如频繁的进程插入、删除和优先级调整），操作系统内核更倾向于使用**链表（Linked List）**实现队列，而不是数组：

• 原因：进程数量动态变化，插入/删除操作频繁（O(1)时间复杂度），链表避免了数组的元素移动开销和固定大小限制。数组在这种场景下容易导致碎片或溢出。
• 示例：在多级反馈队列调度（MLFQ）或圆robin调度中，就绪队列常用单链表或双向链表，每个节点代表一个进程控制块（PCB）。优先级队列可能用数组索引的链表数组（bucket queuing）。
• 实际应用：如在操作系统概念书中，Ready Queue常用链表来允许进程在队列间移动。 现代OS如Linux的CFS调度器也使用红黑树（树形结构，但基础队列部分仍借鉴链表动态性）。

如果进程数固定且少，数组实现（如循环队列）可能用于简单嵌入式系统，但主流桌面/服务器OS优先链表以优化性能和内存。

浏览器历史中的线性表实现

浏览器历史（Back/Forward功能）通常用两个栈（Stacks）实现：一个后退栈（存储已访问页面），一个前进栈（存储前进页面）。这也是线性表的特殊形式，遵循LIFO原则。
实现方式根据浏览器而异，但现代浏览器更常用**动态数组（Dynamic Array，如C++的std::vector或Java的ArrayList）**而不是纯链表：

• 原因：历史记录数量有限（通常数百条），动态数组支持高效的push/pop（摊销O(1)），且允许随机访问（如查看历史列表）。链表虽灵活，但缓存不友好，现代CPU更青睐数组的连续内存。内存开销也较低。
• 示例：在设计题中，常建议用双向链表（Doubly Linked List）模拟，因为它便于在历史中“跳转”（forward/back）。 但实际浏览器如Chrome或Firefox，使用自定义数组结构或deque（双端队列，常基于数组），以平衡性能和内存。
• 实际应用：当你后退时，从当前栈pop并push到前进栈；前进反之。数组实现简化了历史持久化（如保存到数据库）。

总体上，选择取决于具体需求：如果强调动态性和频繁操作，链表更好；

如果大小可控且需高效访问，数组优先。

在C语言实现中，可以根据场景灵活选择（如用malloc动态数组模拟vector）。