字节内推dd

10-07 18:30 字节跳动_算法工程师

发布于山东

关注

【C++八股-第18期】操作系统-进程调度与缺页

❤此贴满十朵花花，速更下一贴

alt

提纲：

👉 八股：

简单介绍一下常用的几种调度算法

概述一下LRU算法及其实现方式

页表是什么，操作系统为什么要引入这一概念？

一个32位系统，页大小是4KB，该操作系统的页表有多大？

虚拟地址到物理地址是如何映射的？

介绍一下缺页异常及缺页中断

调用 malloc 或 mmap 函数时，实际物理内存是何时分配的？介绍一下分配流程

介绍一下死锁的产生条件及其解决方案

👉 代码：

1. 简单介绍一下常用的几种调度算法

先来先服务调度算法 (FCFS)：

特点： 先来先得，即先到达队列的会被优先处理
缺点： 可能会导致“饥饿”现象，产生短作业的“回旋时间”较长的问题。

短作业优先调度算法 (SJF)：

特点： 优先调度估计执行时间最短的进程。
优点： 最小化平均等待时间。
缺点： 难以准确预测进程的执行时间，可能导致“饥饿”现象。

高优先级优先调度算法 (Priority Scheduling)：

特点： 根据每个进程的优先级进行调度，优先级高的进程先执行。
优点： 可以通过设置优先级来保证关键任务优先执行。
缺点： 低优先级进程可能会被长期搁置，导致“饥饿”现象。

时间片轮转法 (Round Robin, RR)：

特点： 每个进程分配一个固定长度的时间片，时间片用完后，进程会被置于队列末尾，等待下一个时间片。
优点： 简单公平，每个进程都能得到执行机会。
缺点： 时间片的长度对系统性能有较大影响，时间片过短会导致频繁切换，时间片过长则可能导致响应时间过长、系统整体吞吐量变低。

多级反馈队列调度算法 (Multilevel Feedback Queue, MLFQ)

特点： 系统设置多个队列，每个队列有不同的优先级和时间片长度，新进程首先进入最高优先级队列，如果没有完成则降级到下一个优先级队列。
优点：
- 响应性好： 高优先级队列中的短任务能快速得到处理，提高了系统对用户请求的响应速度。
- 公平性： 通过动态调整优先级，避免了饥饿现象，使得所有任务都有机会被执行。
- 适应性强： 能够适应不同性质的任务，短任务和长任务都能得到合理的处理。
- 良好的性能： 对于大多数实际应用，MLFQ往往能提供较好的整体性能，特别是在处理交互式任务时。
缺点：
- 实现复杂： 比起简单的调度算法，MLFQ的实现更为复杂，需要考虑队列的管理和进程优先级的动态调整。
- 参数调整困难： 选择适当的队列数量、时间片长度及降级策略可能需要根据具体应用进行调整，且不易找到最佳配置。
- 可能导致不公平： 如果设计不当，某些长任务可能会因为不断被降级而长时间无法执行，导致不公平的情况。
- 上下文切换开销： 虽然MLFQ减少了饥饿现象，但仍然可能由于频繁的上下文切换导致性能下降，尤其是在负载较高时。

2. 概述一下LRU算法及其实现方式

LRU （Least Recently Used，最近最少使用）算法

使用场景：

LRU（Least Recently Used） 算法是一种缓存淘汰策略，旨在保持缓存中最常使用的数据项。当缓存达到容量限制时，LRU会删除最近最少使用的对象，以便为新数据腾出空间。

实现方式：

通常结合 链表 和 哈希表（HashMap） 来实现。

数据结构：
- 双向链表： 用于维护缓存中数据项的访问顺序。链表的头部表示最近使用的项，尾部表示最近最少使用的项。
- 哈希表： 用于存储数据项及其在链表中的节点引用，实现O(1)的快速查找。
基本操作：
- 插入新数据项：
  - 如果新数据项已存在于缓存中（命中），则将其对应的节点移动到链表头部。
  - 如果新数据项不在缓存中： a. 创建一个新节点并将其放到链表头部。 b. 检查缓存是否满，如果满了，删除链表尾部节点，并从哈希表中移除该项。 c. 将新节点添加到哈希表中。
- 访问数据：
- 当访问某一数据项时，先在哈希表中查找：
  - 如果找到，则将对应的节点移到链表头部并返回该数据项。
  - 如果未找到，返回-1。

代码示例：（可忽略）

#include <iostream>
#include <unordered_map>
using namespace std;

class LRUCache {
public:
    LRUCache(int capacity) : capacity(capacity) {}

    int get(int key) {
        if (cache.find(key) == cache.end()) {
            return -1; // 数据项不在缓存中
        }
        // 将该节点移到链表头部
        list.splice(list.begin(), list, cache[key]);
        return cache[key]->second;
    }

    void put(int key, int value) {
        if (cache.find(key) != cache.end()) {
            // 更新节点值，并将该节点移到链表头部
            cache[key]->second = value;
            list.splice(list.begin(), list, cache[key]);
        } else {
            if (list.size() == capacity) {
                // 删除链表最后一个节点
                cache.erase(list.back().first);
                list.pop_back();
            }
            // 插入新节点到链表头部
            list.emplace_front(key, value);
            cache[key] = list.begin();
        }
    }

private:
    int capacity;
    list<pair<int, int>> list; // 链表，存储键值对，最近使用的在链表头部
    unordered_map<int, list<pair<int, int>>::iterator> cache; // 哈希表，存储键和链表节点的迭代器
};

int main() {
    LRUCache cache(2); // 创建一个容量为2的LRU缓存
    cache.put(1, 1);
    cache.put(2, 2);
    cout << cache.get(1) << endl; // 返回1
    cache.put(3, 3); // 淘汰键2
    cout << cache.get(2) << endl; // 返回-1（未找到）
    cache.put(4, 4); // 淘汰键1
    cout << cache.get(1) << endl; // 返回-1（未找到）
    cout << cache.get(3) << endl; // 返回3
    cout << cache.get(4) << endl; // 返回4
    return 0;
}

3. 页表是什么，操作系统为什么要引入这一概念？

页表是操作系统中用于管理虚拟内存和物理内存之间映射关系的一种数据结构，存储了虚拟内存页和物理内存页之间的对应关系。

alt

为什么要引入页表这一概念

1. 虚拟内存的抽象：

页表允许操作系统把虚拟地址空间与物理内存分离，使得每个进程可以拥有独立的虚拟地址空间，提高了内存管理的灵活性和安全性。

2. 有效利用内存：

通过分页机制，操作系统可以将物理内存分成固定大小的页（如4KB），而不是为每个字节都分配物理内存，这样可以有效减少内存碎片和浪费。

不可能每一个虚拟内存的 Byte 都对应到物理内存的地址，如果真是如此那么这张表将大得连真正的物理地址也放不下。

3. 内存保护：

页表可以实现对不同进程的内存隔离，防止一个进程访问另一个进程的内存区域，提高系统的稳定性和安全性。

4. 动态内存分配：

虚拟内存使得程序可以使用比实际物理内存更大的内存空间，操作系统能够根据需求在物理内存中动态加载和卸载页面，从而提高内存利用率。

5. 简化内存管理：

分页使得内存管理变得更加简单，操作系统只需管理页面，而不需要关注每个字节的分配情况。

4. 一个32位系统，页大小是4KB，该操作系统的页表有多大？

1. 计算虚拟地址空间

在32位系统中，虚拟地址空间的大小为 2^32 字节，即 4GB。

2. 计算页的数量

每个页的大小为4KB，即 2^12 字节。因此，虚拟地址空间中的页数为：

alt

这意味着该系统可以支持 2^20 个页。

3. 计算页表中每个条目的大小

在32位系统中，页表通常需要存储每个页的物理地址，通常是4字节（32位）。此外，还可能包含一些控制位（如有效位、权限位等），因此这里假设每个条目占用8字节。

4. 计算页表的总大小

alt

也就是 8MB。

结语：

如果采用一一映射，每个字节都需要单独映射，会导致页表的大小远超整个物理内存，极其不现实。然而，引入页表后，相比直接映射每个字节，所需空间从 4GB 大幅减少到仅 8MB，使得内存管理变得更加可行和高效。

5. 虚拟地址到物理地址是如何映射的？

分页（Paging）

操作系统将虚拟地址空间划分为固定大小的块，将其称之为页（Page）；同时将物理内存也划分为同样大小的页框（Frame），一般都是4KB。

操作系统通过页表（分页机制）维护虚拟页与物理页框之间的映射关系。

虚拟地址到物理地址的映射过程

1. 逻辑地址转线性地址

逻辑地址由段选择子（Segment Selector）和段内偏移量（Offset）组成。
操作系统首先使用段选择子找到相应的段描述符，该描述符包含该段的基地址。
线性地址 = 段基地址 + 段内偏移。

例子： 如果段基地址是 0x1000，段内偏移是 0x2000，则线性地址为 0x1000 + 0x2000 = 0x3000。

2. 线性地址转物理地址 线性地址被转换为物理地址的过程通过多级页表完成。

下面以 三级页表 为例子，在32位地址空间中，线性地址被分为三个部分：页目录索引 、页表索引 和页内偏移 。

页目录索引（10位）：用于在页目录中查找对应页表。
页表索引（10位）：用于在具体的页表中查找对应的页。
页内偏移（12位）：用于在页中定位具体的物理内存地址。
1. 从CR3寄存器获取页目录基地址：
  - 当一个进程被调度时，进程的页目录基地址被存入CR3寄存器，这个基地址指向当前进程的页目录表的起始地址。
2. 页目录查找：
  - 页目录基地址 + 页目录索引 = 页表的物理地址。
  - 使用线性地址的前10位作为页目录索引，从页目录中找到页表的地址。
3. 页表查找：
  - 页表的物理地址 + 页表索引 = 物理页的基地址。
  - 使用线性地址的中间10位作为页表索引，从页表中找到具体的物理页地址。
4. 页内偏移：
  - 物理页地址 + 页内偏移 = 最终的物理地址。
  - 线性地址的最后12位表示页内的偏移，用于在页中找到具体的数据。