操作系统高频（七）虚拟地址与页表

操作系统高频（六）虚拟地址与页表

1.什么是文件系统？它的作用是什么？⭐

• 存储管理：文件系统负责管理计算机的存储设备，如硬盘、固态硬盘等。它将文件存储在这些设备上，并负责分配和回收存储空间。文件系统通过数据块的分配和索引机制，确保文件能够被快速定位和访问。
• 文件组织：文件系统定义了文件和目录的结构和组织方式。它通过层次化的目录结构或扁平化的文件结构，帮助用户对文件进行分类、分组和管理。文件系统提供了创建、删除、移动和重命名文件和目录的操作，便于用户组织和管理文件。
• 文件访问控制：文件系统提供了对文件的访问权限控制。它允许用户或程序对文件进行读取、写入和执行等操作，并根据用户角色和权限设置文件的访问级别。这样可以保护文件的机密性和完整性，限制未授权的访问和修改。
• 文件操作和管理：文件系统提供了一系列的接口和工具，允许用户对文件进行各种操作和管理。这包括文件的复制、移动、重命名、压缩和解压缩等操作，以及对文件属性的设置和查询，如文件大小、文件类型、创建时间等。
• 文件共享和备份：文件系统支持文件的共享，使多个用户能够同时访问和修改同一个文件。这促进了团队协作和信息共享。此外，文件系统还提供了备份和恢复的功能，确保用户的数据安全和可靠性。

2.说说进程调度算法有哪些？⭐⭐

1. 先来先服务（FCFS）：按照进程到达的先后顺序进行调度。先到达的进程先被执行，直到该进程完成或被阻塞。
2. 短作业优先（SJF）：根据进程的执行时间来进行调度，执行时间短的进程先被执行。该算法可以最小化平均等待时间，但可能导致长作业饥饿。
3. 最短剩余时间优先（SRTF）：在执行过程中，根据剩余执行时间来动态调度进程。如果一个新到达的进程的剩余执行时间比当前进程的剩余执行时间短，则进行切换。
4. 优先级调度：为每个进程分配一个优先级，并按照优先级来调度进程。具有较高优先级的进程先被执行，较低优先级的进程可能会被较高优先级的进程长时间抢占。
5. 时间片轮转调度（Round Robin）：将可用的CPU时间划分为固定大小的时间片（如10ms），每个进程在一个时间片内被执行，然后被放到就绪队列的末尾。这样可以保证每个进程都有机会执行，并提供一种均衡的调度。
6. 多级反馈队列调度：将就绪队列划分为多个队列，每个队列具有不同的时间片大小。新到达的进程首先进入第一个队列，如果在该队列执行完后还有剩余时间，则进入下一个队列，以此类推。这个算法可以根据进程的特性分配不同的优先级。

3.简述LRU算法及其实现方式。⭐⭐

LRU（Least Recently Used）算法是一种用于页面置换的算法，用于决定哪些页面应该被置换出内存。这个算法的基本思想是，当需要置换页面时，选择最近最少被使用的页面进行替换。

LRU 算法：

实现 LRU 算法的方式可以利用一个数据结构来记录页面的访问历史，可以使用链表或者队列来实现。下面是一种基于双向链表的 LRU 算法实现方式：

1. 维护一个双向链表。链表的头部表示最近使用的页面，尾部表示最久未使用的页面。
2. 当访问一个页面时，如果页面在链表中存在，将其从原位置删除，并插入到链表头部。
3. 当访问一个页面时，如果页面不在链表中，且缓存未满，则直接将该页面插入到链表头部。
4. 当访问一个页面时，如果页面不在链表中，且缓存已满，则删除链表尾部的页面，并将新页面插入到链表头部。

通过这种方式，最近访问的页面会被移到链表头部，而长时间未被访问的页面会逐渐移到链表尾部。当需要置换页面时，只需要淘汰链表尾部的页面即可。

LRU算法的优点是可以充分利用程序的局部性原理，将最近被访问的页面保留在内存中，从而提高缓存命中率和访问效率。但它也存在一些缺点，如实现复杂度较高和需要额外的数据结构来记录页面访问历史等。

代码实现：

#include <iostream>

#include <unordered_map>

using namespace std;

class LRUCache {

private:

    struct ListNode {

        int key;

        int value;

        ListNode* prev;

        ListNode* next;

        ListNode(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}

    };

    unordered_map<int, ListNode*> cache;

    ListNode* head;

    ListNode* tail;

    int capacity;

public:

    LRUCache(int capacity) {

        this->capacity = capacity;

        head = new ListNode(-1, -1);

        tail = new ListNode(-1, -1);

        head->next = tail;

        tail->prev = head;

    }

    void addToHead(ListNode* node) {

        node->next = head->next;

        node->prev = head;

        head->next->prev = node;

        head->next = node;

    }

    void deleteNode(ListNode* node) {

        node->prev->next = node->next;

        node->next->prev = node->prev;

    }

    int get(int key) {

        if (cache.count(key)) {

            ListNode* node = cache[key];

            deleteNode(node);

            addToHead(node);

            return node->value;

        }

        return -1;

    }

    void put(int key, int value) {

        if (cache.count(key)) {

            ListNode* node = cache[key];

            deleteNode(node);

            node->value = value;

            addToHead(node);

        } else {

            if (cache.size() == capacity) {

                ListNode* tailNode = tail->prev;

                deleteNode(tailNode);

                cache.erase(tailNode->key);

                delete tailNode;

            }

            ListNode* newNode = new ListNode(key, value);

            addToHead(newNode);

            cache[key] = newNode;

        }

    }

};

int main() {

    LRUCache lruCache(2);

    lruCache.put(1, 1);

    lruCache.put(2, 2);

    cout << lruCache.get(1) << endl; // 输出 1

    lruCache.put(3, 3);

    cout << lruCache.get(2) << endl; // 输出 -1，因为缓存中已经不存在 key 为 2 的元素

    lruCache.put(4, 4);

    cout << lruCache.get(1) << endl; // 输出 -1，因为缓存中已经不存在 key 为 1 的元素

    cout << lruCache.get(3) << endl; // 输出 3

    cout << lruCache.get(4) << endl; // 输出 4

    return 0;

}使用了一个结构体 ListNode 表示双向链表的节点，通过指针 prev 和 next 连接节点。缓存的数据通过哈希表 cache 来进行快速查找，键为键值，值为节点指针。LRU 缓存的容量由变量 capacity 控制。每次访问或插入新数据时，通过操作链表的头部指针和节点的连接关系来更新缓存的访问顺序，同时使用哈希表来查询快速访问指定键值的节点。

4.什么是页表，为什么要有？⭐⭐⭐

什么是页表？

答：页表（Page Table）是操作系统中的一种数据结构，用于管理虚拟内存和物理内存之间的映射关系。它记录了进程的页（Page）与物理页框（Page Frame）之间的对应关系。

页表的作用是什么？

页表的作用是实现虚拟内存与物理内存之间的映射关系，并提供对内存访问的控制和管理。具体作用包括：

1. 映射关系：通过页表，操作系统可以根据进程的虚拟地址将其转换为实际的物理地址。这样，进程就可以使用连续的虚拟地址空间而不需要关心物理内存的布局。
2. 内存管理：页表可以帮助操作系统有效地管理内存。它可以将进程的虚拟地址空间分割成小的固定大小的页，同时将物理内存分割成与页大小相同的块。这样，操作系统可以根据需要进行页面调度，将进程所需的虚拟页加载到物理内存中，并保持合理的内存利用率。
3. 内存保护：页表中可以记录访问权限和保护位等信息，用于控制进程对内存的访问权限。通过页表，操作系统可以实现内存的保护，确保进程只能访问到其所拥有的内存空间，防止越界访问和非法操作。
4. 虚拟化技术支持：在虚拟化环境下，页表可以实现虚拟机对物理内存的访问和管理。虚拟机监控程序（Hypervisor）会维护独立的页表，将虚拟机的虚拟地址转换为物理地址，隔离不同虚拟机之间的内存空间。

5.简述操作系统中的缺页中断。⭐⭐⭐

缺页异常：malloc和mmap函数在分配内存时只是建立了进程虚拟地址空间，并没有分配虚拟内存对应的物理内存。当进程访问这些没有建立映射关系的虚拟内存时，处理器自动触发一个缺页异常，引发缺页中断。

缺页中断：缺页异常后将产生一个缺页中断，此时操作系统会根据页表中的外存地址在外存中找到所缺的一页，将其调入内存。

操作系统中的缺页中断（Page Fault）是指当程序访问的页不在物理内存中时发生的一种中断机制。当程序需要访问一个虚拟页，但该页当前不在物理内存中时，CPU会触发一个缺页中断，将控制权交给操作系统。

缺页中断的处理过程大致如下：（大致了解）

1. 当程序访问一个缺页时，CPU会暂停当前的指令执行，并产生一个异常或中断，即缺页中断。
2. 操作系统的内核捕获到缺页中断，并开始处理中断。
3. 操作系统首先会检查发生缺页中断的原因。如果该页是无效的或不可访问的，操作系统会终止该进程，因为这可能是非法访问。否则，如果该页是合法的但不在物理内存中，操作系统需要将该页加载到内存中。
4. 操作系统根据页表信息确定要替换的物理页框，并根据需要从磁盘中获取相应的页。
5. 如果物理内存中有空闲的页面，操作系统将被替换的页面清除并将新的页面加载到物理内存中。如果物理内存没有空间，则必须选择一个页面进行替换，通常会使用一些页面置换算法，如最近最少使用（LRU）或先进先出（FIFO）。
6. 操作系统更新页表，将新加载的页与对应的虚拟页建立映射关系，并标记该页为已加载到物理内存中。
7. 最后，操作系统恢复中断点，并将控制权返回给触发缺页中断的程序，让它继续执行。

缺页中断的目的是实现了虚拟内存的概念，允许程序使用比实际物理内存更大的地址空间，并将常用的页存放在物理内存中，而将不常用的页放在磁盘上。通过缺页中断处理，操作系统能够根据需求将所需的虚拟页从磁盘加载到内存中，实现了透明的内存管理和动态的页面调度。

6.简述一下虚拟内存和物理内存，为什么要用虚拟内存，好处是什么？⭐⭐⭐

虚拟内存是一种抽象的内存概念，它为每个进程提供了一个独立的地址空间，这个地址空间被称为虚拟地址空间。虚拟内存的大小可以超过物理内存的容量。

物理内存是计算机系统中实际存在的内存硬件，由RAM（Random Access Memory）组成。物理内存存储着正在运行的程序和数据。

为什么要使用虚拟内存？以下是虚拟内存的几个好处：

1. 扩展内存容量：虚拟内存允许进程访问超过物理内存容量的虚拟地址空间。当物理内存不足以容纳所有进程的数据时，操作系统可以将不常用的页面置换到磁盘上，从而释放物理内存空间给其他进程使用。
2. 内存隔离：每个进程都有独立的虚拟地址空间，使得不同进程之间的内存彼此隔离，互不干扰。这提高了系统的安全性和稳定性，一个进程的错误不会影响其他进程。
3. 简化程序设计：虚拟内存使得程序设计人员可以将内存视为连续的地址空间，而不需要关注物理内存的限制和分配。程序可以使用大量的虚拟内存，而不必担心物理内存的实际大小。
4. 提高性能：虚拟内存通过提供更大的地址空间和内存管理机制，可以提高系统的性能。它允许操作系统将常用的页面保留在物理内存中，减少了磁盘访问次数，提高了访问速度。

7.虚拟地址到物理地址怎么映射的？⭐⭐⭐

虚拟地址到物理地址的映射是通过页表（Page Table）来实现的。页表是一种数据结构，记录了虚拟页和物理页之间的映射关系。

虚拟地址到物理地址的映射是通过页表实现的。页表是一种数据结构，记录了虚拟页和物理页之间的对应关系。

当程序访问虚拟地址时，操作系统通过页表将其转换为物理地址。具体过程如下：

1. 程序生成虚拟地址。
2. 虚拟地址由两部分组成：页表索引和页内偏移。页表索引用于在页表中查找对应的页表项。
3. 操作系统根据进程的页表找到对应的页表项。
4. 页表项中包含了物理页的地址信息。
5. 操作系统将虚拟页的高位替换为物理页的高位，形成物理地址的高位部分。
6. 将物理地址的高位部分与虚拟地址的低位部分（页内偏移）组合，得到最终的物理地址。

这样，通过页表的映射过程，程序可以通过虚拟地址来访问对应的物理内存。

三级页表转换方法：（两步）

（1）逻辑地址转线性地址：段起始地址+段内偏移地址=线性地址

（2）线性地址转物理地址：

每一个32位的线性地址被划分为三部分：页目录索引（10位）、页表索引（10位）、页内偏移（12位）

• 从cr3中取出进程的页目录地址（操作系统调用进程时，这个地址被装入寄存器中）
• 页目录地址 + 页目录索引 = 页表地址
• 页表地址 + 页表索引 = 页地址
• 页地址 + 页内偏移 = 物理地址

8.中断和异常的区别⭐⭐⭐⭐

当将中断和异常进行对比时，可以注意以下几个方面的区别：

1. 触发方式：

- 中断：由外部设备或其他特殊事件触发，如外部设备请求处理器的服务或时钟中断。

- 异常：由当前执行的指令引发，表示当前指令无法正常执行或发生了错误，如除零错误、越界访问、非法指令等。

2.异步性：

- 中断：是异步事件，与当前程序的执行无关，可以在任何时刻发生。

- 异常：是同步事件，由当前执行的指令引发，与当前程序的执行步骤相关。

3. 处理机制：

- 中断：发生中断时，处理器立即中断当前正在执行的程序，保存当前程序的上下文，并跳转到中断处理程序来处理中断事件。处理完中断后，处理器恢复之前被中断的程序的上下文，并继续执行。

- 异常：发生异常时，处理器立即中断当前指令的执行，保存当前程序的上下文，并跳转到异常处理程序来处理异常情况。处理完异常后，处理器根据异常处理程序的指示继续执行。

4. 类型：

- 中断：中断没有明确的类型，但可以根据中断源进行分类，如外部设备中断、时钟中断等。

- 异常：异常可以分为故障（Fault）、陷阱（Trap）和终止（Abort）三种类型。故障表示可以被修复的异常，陷阱用于实现系统调用和调试功能，终止表示无法恢复的异常。

5. 优先级：

- 中断：中断可以具有不同的优先级，处理器按照优先级处理中断事件，高优先级的中断会打断低优先级的中断处理。

- 异常：异常没有明确的优先级概念，处理器通常按照异常的严重程度来处理。

6. 外部设备：

- 中断：中断通常与外部设备的交互相关，用于处理外部设备的请求和数据传输。

- 异常：异常与外部设备无直接关联，主要用于处理指令执行过程中的错误或异常情况。

9. 请解释一下操作系统的文件访问方式，包括顺序访问、随机访问和直接访问。⭐⭐

操作系统的文件访问方式包括顺序访问、随机访问和直接访问。这些访问方式决定了如何在文件中读取和写入数据。

1. 顺序访问（Sequential Access）：

- 顺序访问是按照数据在文件中的顺序进行访问的方式。

- 读取数据时，必须从文件的开头开始，依次读取每个数据项，直到达到目标位置。

- 写入数据时，新的数据将追加到文件的末尾。

- 顺序访问适用于顺序处理数据的场景，如读取日志文件或批量处理数据。

2. 随机访问（Random Access）：

- 随机访问允许根据数据在文件中的位置进行直接访问。

- 读取数据时，可以通过指定数据在文件中的位置或偏移量来读取特定位置的数据。

- 写入数据时，可以将数据直接写入文件的指定位置。

- 随机访问适用于需要快速访问文件中特定位置的数据的场景，如数据库系统或索引文件。

3. 直接访问（Direct Access）：

- 直接访问允许通过记录的标识符（如文件中的记录号）直接访问文件中的数据。

- 读取数据时，可以通过记录的标识符来定位和读取特定记录的数据。

- 写入数据时，可以将数据直接写入文件中指定记录的位置。

- 直接访问适用于需要根据记录标识符快速访问文件中数据的场景，如数据库系统或索引文件。