Home 面试题 操作系统

# 操作系统面试题

# 什么的操作系统

操作系统是负责管理协调计算机硬件和软件资源的一种系统软件。其屏蔽了底层硬件的异构性和复杂性，为上层应用程序提供统一易用的接口.

# 主机启动

BIOS ：I/O 处理系统，开机时可以自动检测各种外设
Bootloader ：加载 OS

# 中断和异常的处理过程

  • 外中断是指由 CPU 执行指令以外的时间引起的，如 IO 完成中断、时钟中断、控制台中断；

  • 内中断（异常）是由 CPU 执行指令内部事件引起的，如地址越界、除 0、算术溢出等.

  • 硬件

    1. 设置中断标记
    2. 操作系统根据这个标记（中断号）去找到对应的处理程序

  • 软件

    1. 保存现场：把当前执行程序的相关数据保存在寄存器中，然后入栈
    2. 开中断：以便于响应优先级更高的中断请求
    3. 中断服务程序处理
    4. 关中断：保证恢复现场时不被中断
    5. 恢复现场

# 系统调用

应用程序需要操作系统提供服务，而这些服务不能由应用程序直接执行。需要操作系统提供接 --- 系统调用

用户态 转化到 内核态

# 操作系统功能

  • 进程管理
  • 内存管理：负责管理内存的分配、回收。在进程创建时分配内存以及在进程结束时回收内存，协调内存资源
  • 设备管理
  • 文件管理
  • 提供用户接口

# CPU 内部结构

  • 计算逻辑单元 ALU
  • 寄存器
  • 控制器
  • 缓存
  • 内存管理单元 MMU

# 寄存器

  • 程序计数器 (prgram counter, PC) ：用于存放下一条运行指令的地址.
  • 指令寄存器 (Instraution Register, IR) ：用于存放当前正在执行的指令.
  • 程序状态字 (Program Status Word, PSW)
  • 累加寄存器 (Accumulator Register, AX) ：
  • 基地寄存器 (Base Register, BX)
  • 变址寄存器

# 进程与线程

进程是程序执行的一个过程，其实资源分配的基本单位，各个进程拥有自己独立的虚拟地址空间，执行互不干扰；同时父进程创建出的自进程之间也互不影响，子进程的崩溃或父进程的崩溃对互相并不影响。进程主要由程序段、数据段和程序控制块组成.

  1. 程序段：程序运行的代码
  2. 数据段：程序运行所产生的数据（全局变量、局部变量）
  3. 程序控制块：操作系统对该进程进行管理所涉及到的各种信息
    • PID ：进程标识符
    • 进程状态
    • 进程优先级
    • 程序计数器 PC
    • 内存指针
    • 上下文数据

在 Linux 中通过 fork 函数来创建一个子进程，子进程会拷贝父进程的；

同一个进程共享堆、全局变量、静态变量，但是线程独占栈、程序计数器

线程是进程内部的一个控制序列，其是 CPU 资源调度的基本单位，其是在进程内部运行，本质是在进程的地址空间运行，其可以和其他线程共享该进程的一些资源，比如全局变量、堆空间。但是每个线程也有自己独立的线程 ID，栈空间和程序计数器.

# 多线程与多进程

多进程的优点：

  • 各个进程拥有自己独立的虚拟地址空间，各个程序之间的执行互不干扰，而且子进程的崩溃不会影响父进程，反之父进程崩溃也不会影响子进程
  • 多个进程可以充分利用 CPU，并行执行程序，不用担心并行执行程序导致的问题

多线程的缺点：

  • 由于进程的独立性，不同进程之间数据交换需要进程通信
  • 创建一个子进程的开销比创建一个子线程的开销大
  • 线程的切换比进程的切换系统开销会更大【切换页表、切换内核栈和硬件上下文（进程切换之后，新程序的虚拟地址在 TLB 内失效，会导致频繁的访存）】

多线程的优点：

多线程的缺点：

# 进程调度算法

  • 先来先服务 FCFS(First Come First Serverd) ：按照请求的顺序进行调度（不利于短作业，不会导致饿死）
  • 短作业优先 SJF(Shortest Job First) ：按估计运行时间最短的顺序进行调度（不利于长作业，会导致饿死）
  • 最短剩余时间有优先
  • 时间片轮转
  • 优先级调度
  • 多级反馈队列：在一定程度上减少了频繁的进程切换的开销.

# 进程状态切换

# 进程间通信 IPC 方式

两个或多个进程之间产生的数据交互

  • 管道：半双工通信，数据只能单向流动.

    在内核中开辟一块缓冲区，进程 A 把数据从用户区拷贝到内核缓冲区，进程 B 再从内核缓冲区把数据读走.

    • 匿名管道：具有情缘关系的进程之间的通信方式（具有同一个祖先）

      #include <unistd.h>
      int pipe(int pipefd[2]);
      /*
        1. pipefd [0]: 读端 read (管道空时堵塞)
        2. pipefd [1]: 写端 write (管道满时堵塞)
      */

    • 有名管道：不相干的两个进程之间的通信方式

      #include <sys/types.h>
      #include <sys/stat.h>
      int mkfifo(const char *path, mode_t mode);
      /*
          path: 创建的命名管道的全路径名：
          mod: 为指定了文件的读写权限； 
      */

  • 共享内存 (Shared Memory Segment) ：由一个进程创建，多个进程都可以访问的一段内存空间。通过 shmat 可以将共享内存空间关联到指定的进程地址空间中

  • 消息队列

  • Socket 套接字：适用于不同主机之间的通信，也可以用于同一主机两个进程之间的通信

  • 信号 Signal

  • 信号量

# 进程同步

  • 互斥锁 + 条件变量
  • 信号量
  • 管程

# 多线程模型

  • 用户级线程

# 锁机制

  • 读写锁
  • 互斥锁
  • 条件变量
  • 自旋锁

# 死锁

死锁是两个或两个以上的线程在执行的过程中，去争夺同一个共享资源锁导致的互相等待的一个现象，在没有外部干预的情况下，这些线程会一直处于堵塞状态，无法往下去执行.

死锁产生的四个条件：

  1. 互传条件
  2. 请求与保持条件
  3. 不剥夺条件
  4. 循环等待条件

# 防止死锁的方法

  1. 在第一次执行的时候一次性申请所有的共享资源
  2. 占用部分资源的进程在进一步去申请其他共享资源的时候，如果申请不到，就主动释放它所占有的资源

# 银行家算法

# 连续内存分配

  • 单一连续分配

    内存中只有一道用户程序用户独占整个用户区空间，无外部碎片，有内部碎片；可以使用覆盖技术进行逻辑扩容，不需要采用内存保护

  • 固定分区分配（无外部碎片，会产生内部碎片）

    1. 分区大小相等（固定）：缺乏灵活性
    2. 分区大小不等（固定）

  • 动态内存分配：不会预先划分内存空间

    1. 首次适应算法：每次都从地地址开始查找，找到第一个能满足大小的空闲分区
    2. 最佳适应算法：选择尽可能小的内存分区分配给进程；空闲分区按照容量递增次序链接，每次分配内存时按顺序查找空闲分区链，找到第一个能满足要求的空闲分区
    3. 最坏适应算法：每次分配时使用最大的空闲内存区，为了过多的内存碎片；空闲分区安容量递减的次序链接，每次分配内存时按顺序查找空闲分区链，找到第一个能过满足要求的空闲分区
    4. 邻近适应算法： 首次适应算法 每次都要从链表头开始查找，这可能会导致低地址部分出现很多小的空闲分区，每次查找时需要进过这些分区，增加了查找开销。如果每次都从上次查找结束的位置开始检索，就能解决这个问题.

# 空闲内存的管理方式

  • 空闲链表
  • 位图：将内存划分为均等的分配单元，每个分配单元对应于位图中的一位，0 表示空闲，1 表示占用；分配单元的大小是一个值得考量的问题，分配单元太小会使得位图占用的空间过大，如果分配单元过大，内造成内部碎片。当需要分配一定大小空间的内存时，需要遍历真个位图，依次检查，时间复杂度较高.

# 内存紧缩与交换式碎片整理

# 非连续内存分配

  1. 连续内存空间分配，需要给程序分配连续空间，同时会产生外部碎片，内存利用率不高
  2. 非连续内存分配优点：
    • 程序的物理地址空间是非连续的，更好的利用内存空间
    • 允许共享代码与数据
    • 支持动态加载和动态链接
  3. 非连续内存分配缺点：建立虚拟地址空间到物理地址空间的转换

  • 分段

    1. 分段的寻址方式

  • 分页

    1. 逻辑页 page 和物理页 frame(帧) 的大小一致
    2. 不是所有的页都有对应的帧

  • 分段与分页的区别

    1. 分页对程序员是透明的，但是分段需要程序员显示的划分每个段
    2. 页的大小不可改变，段的大小可动态变化

# 页表

  • 标志位

    1. 访问位：表示当前页之前是否被访问过
    2. 修改位：表示当前页之前是否被修改过
    3. 保护位：表示是否允许对该页做任何类型的操作（读、写、可执行等)
    4. 驻留位：表示该页是在 内存 中还是在 外存 中

  • 帧号

  • 由于逻辑空间很大，导致程序对应的页表会很大，无法存储在 CPU 内，所以页表一般放置在内存中，如没有任何其他优化机制，使用分页存储访问一个内存空间需要 2 次访存.
  • 时间优化：TLB
  • 空间优化：多级页表、反向页表

# TLB

TLB(Translation Look-aside Buffer) ：在 CPU 内的 MMU 中，用于缓存近期访问的页帧转换表项；使用相关存储器实现，时间局部性原理；若 TLB 命中则只需要一次访存，若 TLB missing，则需要两次访存.

# 多级页表

# 反向页表

# 分段与分页对比

# 覆盖技术

需要程序员自己把挣个程序划分为若干个小的功能模块，并确定各个模块之间的覆盖关系，增加程序员的负担

# 交换技术

以程序作为交换单位，需要把进程的整个地址空间都换进换出，增加了处理器的开销

# 虚拟技术

虚拟技术是把一个物理实体转化为多个逻辑实体

  • 时空复用技术

    多进程与多线程：多个进程能在同一个处理器上并发执行使用了时空复用技术，当每个进程轮流占用 CPU

  • 空分复用技术

    虚拟内存：将物理内存抽象为逻辑地址空间，每个进程都有各自的地址空间.

# 虚拟内存

  1. 将物理空间扩充为更大的逻辑空间
  2. 在装入程序时，不必将其全部装入内存，而只需将当前需要执行的部分页面或段装入内存，就可以让程序开始执行
  3. 在程序执行过程中，如果执行的指令或访问的数据不在内存中（ 缺页 或 缺段 ），则由处理器通知操作系统将相应的页面或段调入内存，然后继续执行程序
  4. 另一方面，操作系统将内存中暂时不适用的页面或段调出保存到磁盘中，从而腾出更多的空闲空间存放将要装入的程序

# 缺页中断处理过程

# 页面置换算法

当缺页中断发生时，需要调入新的页面而内存已满时，选择内存当中那个物理页面进行替换（更可能减少换入换出的次数）

  1. 最优页面置换算法：将未来最久不会被访问的页面置换出去（理想情况）

  2. 先进先出算法

  3. 最近最久未使用 LRU,Least Recently Used

    1. 时钟页面置换算法 CLOCK ：最近未用算法

  4. 二次机会法

  5. 最不常用算法 LFU,Least Frequently Used

Belady 现象：分配的物理页面数增加，缺页率反而提高的异常现象（没有考虑进程访问的动态特征导致的， FIFO ）

# 虚拟地址转换位物理地址的过程

# malloc 申请内存时操作系统会怎么做？

malloc 会调用 brk 和 mmap 两个系统调用来实现.

# 磁盘调度算法

# 参考资料

  • [1] 王道计算机考研 操作系统_哔哩哔哩_bilibili
  • [2] 清华 操作系统原理_哔哩哔哩_bilibili
  • [3] 操作系统常见面试题
  • [4] 这 50 道操作系统面试题，真牛批！
Edited on Views times

Give me a cup of [coffee]~(￣▽￣)~*

Value WeChat Pay

WeChat Pay