操作系统面试问题笔记

内核态和用户态

为什么要区分内核态和用户态？

用户不应当直接执行受限操作，如 I/O 请求。内核态只能由操作系统执行，可以执行特权操作。用户程序必须通过系统调用来执行这些特权操作，os 执行前会判断进程是否有权限执行相应的指令。

什么时候会陷入内核态？

系统调用 trap 、中断 interrupt 和异常 exception 的时候。系统调用（trap 又被称为软中断）是用户主动发起的，中断和异常是被动的。中断包括 I/O 中断、外部信号中断、各种定时器的时钟中断等，它不是某条指令的结果，也无法预测时机，独立于当前执行的程序，是异步事件，会执行对应的中断处理程序。异常是程序运算引起的各种错误如除0、缓冲区溢出、缺页等等，是同步事件，控制权会转移给对应的异常处理程序。中断和异常都是通过中断向量表来找到相应的处理程序进程处理。

信号

信号是什么？

信号是一种更高层的软件形式的异常，同样会中断进程的控制流，可以由进程进行处理。信号的作用是用来通知进程发生了某种系统事件。

trap、interrupt、exception 对用户进程是不可见的，而信号提供了一种机制通知用户发生了这些异常。例如，内核收到一个除0异常，内核就会给进程发一个 SIGFPE 信号；其他系统事件，例如按下 ctrl+c，内核就会给进程发一个 SIGINT 信号。

信号也可以作为进程间通信的方式，由一个进程发送给另一个进程。要发送一个信号，可以使用/bin/kill，kill函数向其他进程发送信号，或者使用 alarm 函数向自己发送信号。

每个进程有一个待处理信号的集合，任何时刻同一类型的待处理信号只能有一个，多余的丢弃（隐式阻塞）。

信号处理的时机有内核把进程从内核态切换为用户态时、内核使用控制转移强制处理信号时两种。如果进程的未被阻塞的待处理信号集合不为空，内核会选择集合中的某个信号并将控制权给到信号处理程序。这个信号处理程序是个用户层函数，由进程指定。

线程

进程、线程的定义？

进程是一个拥有资源和执行任务的单元体。进程所有的资源包括内存空间中的代码、数据等；IO资源；文件；处理机等。

线程是一个执行任务的单元体。线程只拥有处理机，线程之间共享进程的资源，如内存、IO等

	进程	线程
资源	进程是一个拥有资源和执行任务的单元体。	线程是一个执行任务的单元体，不拥有资源，线程之间共享地址空间
切换开销	开销很大	开销很小
通信	IPC	共享内存
健壮性	健壮，多个进程之间不会互相干扰	不健壮，一个线程出错会终止整个进程

为什么需要线程？

进程切换开销非常大，包括：

• 处理机的上下文切换，也就是保存和恢复寄存器的内容
• 与进程相关的数据结构更改：存储管理有关的记录信息（页表等）、文件管理有关数据（描述符等）、进程控制块中的各种阻塞队列就绪队列等

并且进程的处理机资源是和其他资源一起分配的，进程切换的时候会整体切换，开销很大。如果我们只切换必须的与处理机相关的信息，就可以有效减小开销。所以我们引入线程，把一个进程分成多个执行任务的实体，只为其分部处理机。

线程的上下文切换过程？

线程有自己的寄存器和栈，上下文切换的时候正在运行的线程会将寄存器的状态保存到 TCB（thread control block）里，（对应进程是PCB）然后恢复另一个线程的上下文。线程只需要切换处理机的上下文，不会改变地址空间，也就意味着不用重新加载页表，切换开销少；多个线程会共享地址空间。

线程的优缺点？

优点：可以提高效率，因为切换开销小；共享内存，通信方便。

缺点：一个线程出错 os 会结束整个进程，不够健壮；同一个进程中的多个线程共享内存可能会有并发问题。

线程的共享资源？

• 内存空间，也就是代码、全局变量、堆
• 文件描述符
• 信号处理器
• 进程ID、进程组ID等

线程的独占资源？

• 线程ID，在本进程中唯一
• 上下文，也就是寄存器的值
• 栈，因为每个线程的函数调用过程是独立的
• 错误返回码，系统调用或库函数报错时返回的全局 err 是独立的
• 信号屏蔽码，每个线程感兴趣的信号不同，所以屏蔽码不同，但每个线程共享本进程的信号处理器

线程的实现方式？

对 linux 内核线程来说，线程和进程并没有被区别对待，都有多个状态，运行、阻塞、就绪... 实际上线程和进程都是用 task_struct 结构体表示的，只不过线程的 mm （内存空间）和 files（打开的文件）结构体是进程共享的。

进程

进程有哪些状态？

进程的基本状态主要是就绪、执行和阻塞：

• 就绪：进程已获得除了处理机之外的资源。
• 执行：进程正在占有处理机资源执行。
• 阻塞：正在等待某种资源，得到之前无法执行。

除此之外可能还有挂起、睡眠等状态。

挂起指的是将暂不执行的进程转移到外存从而节省内存。挂起和阻塞都是进程暂停执行，但阻塞是要等待一个事件，挂起只需要载入内存就能继续执行。

linux 还把进程的阻塞进一步分为暂停、浅睡眠和深睡眠。区分的依据是，如果不需要等待资源就位暂停，否则为睡眠；如果睡眠能够被信号唤醒就是浅睡眠，否则就是深睡眠。

有哪些进程调度算法？

按 cpu 的分配方式可分为抢占和非抢占式；按系统的分时方式可以分为批处理系统、交互系统或实时系统下的调度。

• 批处理系统下的调度

  调度目标：提高吞吐量；降低周转时间；提高 cpu 利用率。

  • 先来先服务

    按请求 cpu 的顺序使用 cpu，非抢占

    优点是易于理解、便于实现，只需要一个就绪队列

    缺点是对短作业不公平；对 IO 密集型进程不利，因为会长时间等待设备；响应时间不确定。

  • 最短作业优先

    预知作业的运行时间，选择最短时间的优先运行

    优点是可以减少平均周转时间

    缺点是对长作业不公平；可能导致饥饿问题。

  • 最短剩余时间优先

    最短作业优先的抢占式版本，如果新作业比正在执行的作业剩余时间短，让它优先执行

    缺点是对长作业依然不公平；仍然可能导致饥饿问题。

  • 最高响应比算法

    响应比：作业等待时间/作业运行所需的时间

    哪个进程响应比大哪个进程优先。因此作业运行所需时间越小、等待时间越长越优先调度。

    优点：同时考虑了等待时间和执行时间，既考虑了短作业，也防止了长作业无限等待的饥饿。

• 交互系统（分时系统）的调度

  调度目标：要快速响应交互请求；cpu 时间分为若干个时间片，使每个用户都能共享主机资源。

  • 时间片轮转（round robin）

    将所有就绪进程排成一个队列，按时间片轮流调度，用完时间片的进程排到队列末尾，属于抢占式

    优点：不存在饥饿问题

    缺点：如果时间片小，进程切换频繁会影响吞吐；若时间片长，则响应时间长，实时性得不到保证

  • 优先级调度算法

    优先级高的进程先运行，同优先级的进程轮转。当高优先级队列中没有进程后，再调度下一级队列。

    缺点是可能导致低优先级的进程饿死。

  • 多级反馈队列

    为了避免低优先级进程饿死，引入动态优先级思想，高优进程运行一段时间后降低其优先级防止其一直占用 cpu 。多级反馈队列的思想是优先级越高，时间片越短。如果一个进程在当前队列规定的时间片内无法执行完毕，则移动到下个队列的队尾。

    缺点是也有可能出现饥饿问题，比如不断有更高优的进程加入。

  • 彩票法

    向进程提供一定数量（权重）的彩票，调度时随机抽取彩票，抽中的进程获得资源。重要的进程可以给更多彩票，协作进程可以交换彩票。

• 实时系统的调度算法

  调度算法的目标：满足任务的截止时间。

  最早截止时间优先算法：先把截止时间最早的任务完成。

僵尸进程、孤儿进程、守护进程是什么？

• 僵尸进程

  当一个进程由于某种原因终止，内核并不会立即将它从系统清除，而是让其保持在“已终止”状态，直到其被父进程回收。僵尸进程指终止但还未被回收的进程，如果子进程退出而父进程没有调用 wait 或 waitpid 来回收，就会产生僵尸进程。僵尸进程的进程描述符仍然在操作系统的进程表保存，所以僵尸进程会占用进程号并占用一定内存。

  如何避免产生僵尸进程：

  • 父进程调用 wait 或者 waitpid 等待子进程结束
  • 子进程结束时内核会发送 SIGCHLD 信号给父进程，父进程可以注册一个信号处理函数，在其中调用 waitpid。也可以用 signal 忽略信号，由内核进行回收。
  • 杀死父进程，僵尸进程就会变成孤儿进程，由 init 进程接管并处理。

• 孤儿进程

  如果某个进程的父进程先结束了，其子进程就会成为孤儿进程。系统在进程结束时会扫描其子进程，如果有就会用 pid 为 1 的 init 进程将其接管。因此孤儿进程不会对系统造成危害。

• 守护进程

  daemon 守护进程是一种在后台执行的程序，用于维护某些程序的状态。

进程间通信

进程间的通信方式有哪些？

进程间可以通过信号、管道、命名管道、信号量、共享内存、消息队列、套接字等方式通信：

方式	传输的信息量	使用场景	关键词
信号	少量	任何	硬件来源、软件来源 / 信号队列
管道	大量	亲缘进程间	单向流动 / 内核缓冲区 / 循环队列 / 没有格式的字节流 / 操作系统负责同步
命名管道	大量	任何	磁盘文件 / 访问权限 / 无数据块 / 内核缓冲区 / 操作系统负责同步
信号量	N	任何	互斥同步 / 原子性 / P 减 V 增
共享内存	大量	多个进程	内存映射 / 简单快速 / 操作系统不保证同步
消息队列	比信号多，但有限制	任何	有格式 / 按消息类型过滤 / 操作系统负责同步
套接字	大量	不同主机的进程	读缓存区 / 写缓冲区 / 操作系统负责同步

进程间如何使用信号通信？

信号除了用来给操作系统作为硬件异常的包装发送给进程外，也可以作为进程间通信的方式。

如何发送信号：

• 使用操作系统提供的发送信号的系统调用
• 该系统调用会将信号放到目标进程的信号队列中
• 如果目标进程未处于执行状态，则该信号由内核保存，直到其恢复执行。如果信号被进程设为阻塞，则该信号的传输被延迟，直到阻塞被取消时才传递给进程。

如何接收信号：

• 每个进程都有个信号队列，用来存放等待处理的信号
• 进程在执行过程中的特定时刻（如从内核空间返回用户空间之前），检查并处理自己的信号队列。

对信号的处理包括：

• 处理信号。定义信号处理函数，信号发生时执行相应的处理函数
• 忽略信号，可以忽略信号不做任何处理
• 不处理也不忽略，即执行 linux 规定的默认操作
• 有些信号如 SIGSTOP、SIGKILL 等进程自己是无法处理和忽略的。

管道是什么？

管道是一种半双工的通信方式，数据只能单向流动。管道命令在 shell 中经常使用，可以用管道操作符 | 来表示两个命令间的数据通信。管道适合用来传输大量信息。其发送的内容是以字节为单位的、没有格式的字节流。

通过 pipe() 系统调用来创建打开一个管道，当最后一个使用它的进程关闭对其的引用时 pipe 将自动撤销。

通过 pipe() 创建的是匿名管道，只能用于父子或兄弟进场之间。

对于管道的实现，管道其实就是一个文件，是一种只存在于内存中的特殊的文件系统。linux 中的管道借助了文件系统的 file 结构实现，父进程使用 file 结构保存向管道写入数据的例程地址，子进程保存从管道读出数据的例程地址。因此，管道只能单向流动，并且只能用于具有亲缘关系的进程之间。

管道在内存里是一个由内核管理的缓冲区，实现是一个循环队列。

管道如何同步？

管道作为一个缓冲区，需要操作系统来保证读写进程的同步。下游进程或者上游进程需要等待另一方释放锁后才能操作管道。虽然读端和写端的 fd 不同，但管道就相当于一个文件，同一时刻就只能有一个进程访问。当管道为空时，下游进程读阻塞；反之管道满时上游进程写阻塞。这不会产生死锁，因为 pipe 文件内部存在访问控制机制，父进程把管道写满、子进程还没读取时，父进程不会再向管道中写入内容。这种访问控制机制会将管道中的读写顺序强制为先写再读。

命名管道是什么？

命名管道叫 FIFO，可用于没有亲缘关系的进程间。匿名管道 Pipe 和 FIFO 除了建立、打开、删除的方式不一样以外几乎一样。

通过 mknode() 或者 mkfifo() 系统调用都可以创建命名管道。一旦建立，任何有访问权限的进程都可以通过文件名将其打开和读写。命名管道建立时会在磁盘中创建一个索引节点 inode，管道名字就相当于索引的文件名，通过索引节点也可以设置进程的访问权限。命名管道实际上就是通过 inode 文件索引节点来实现通过内核缓冲区做数据传输。当不被使用时，命名管道在内存中释放，但是磁盘节点仍然存在。

信号量是什么？

信号量是一种特殊的变量，对它的操作都是原子的，包括 P（wait）和 V（signal）两种。V 操作会增加信号量的值，P 操作会减少它。

执行 V signal 操作时如果有其他进程因等待 S 而挂起，就让它恢复运行，否则 S+1；执行 P wait 操作时，如果 S 为0，则挂起进程，否则 S-1。

信号量可以是一个整数，也可以是一个二进制位 0 或 1。这样的信号量又叫 mutex 互斥锁。

信号量底层是通过硬件提供的原子指令，比如 test and set、compare and swap 等实现的。

共享内存是什么？

共享内存也是一种进程间通信的方式，允许多个进程共享同一段物理内存。不同进程可以将同一段共享内存映射到自己的地址空间，然后就可以像访问正常内存一样访问它。因此，不同进程可以通过向共享内存读写数据来交换信息。

在使用上，一个进程通过操作系统的系统调用来创建一块共享内存区，其他进程通过系统调用把这段内存映射到自己的用户地址空间里。之后各个进程向读写正常内存一样，读写共享内存。这个过程中共享内存区只会驻留在创建它的进程的地址空间里。

共享内存的优点是简单且高效，访问共享区域和访问自己的区域一样快，因为不需要系统调用，不用切换内核态用户态，也不需要做额外的复制。整个过程不需要内核的接入。

共享内存的缺点是存在并发问题，可能出现多个进程修改同一内存块的问题。因此共享内存常常和信号量一起使用。

linux 支持多种共享内存的方式，比如 mmap 系统调用、posix 共享内存、systemV 共享内存等。其中 mmap 系统调用的主要作用是将普通文件映射到进程的地址空间，然后可以像访问普通内存一样访问，而不必 read 或者 write。虽然 mmap 不是专门用来做共享内存的，但通过让多个进程 mmap 映射到同一个普通文件上，就可以实现这点。

消息队列是什么？

消息队列 message queue 是一个消息的链表，保存在内核中，每个消息是一个数据块，具有特定的格式。每个消息队列有一个唯一 key 作为消息队列标识符。

消息队列克服了信号传递信息少、管道只能传递无格式字节流以及缓冲区大小受限等缺点。消息队列提供了有格式的数据传递，但消息队列本身仍然有大小限制。

消息队列允许一个或多个进程同时或不同时向他写入和读取消息，换句话说它是异步的。由于是异步的，所以接收者必须轮询消息队列才能收到最近的消息。异步是消息队列最大的特点。

对于同步，操作系统会负责处理。如果消息队列已满，则写消息进程需排队等等；若取消息的进程没有找到需要的消息，则在等待队列中寻找。

套接字是什么？

通过 socket 既可以与同一台计算机的不同进程通信，又可以与不同计算机的进程通信。需要通信的进程之间各自创建一个 socket，内容包括主机地址与端口号，声明自己接收来自某端口地址的数据。

进程通过 socket 把消息发送到网络层中，网络层通过主机地址将其发到目的主机，目的主机通过端口号发给对应进程。

操作系统提供创建 socket、发送、接收的系统调用，为每个 socket 设置接收和发送缓冲区。

进程同步

有哪些常见的锁？

以 java 中常见的锁的概念来展开。

• 可重入锁，意味着同一线程可以在已经持有该锁时再次获取同一个锁，而不会被自己所持有的锁紫塞。
• 互斥锁，Mutex，意味着同一时间只能有一个线程持有锁。java 里用 synchronized 实现。
• 读写锁，RWLock，允许同时多个读，但只能有一个写。读写不共存。这样比 mutex 的并发性更好。
• 自旋锁 SpinLock，自旋锁是一种锁定机制，不让线程休眠，而是会反复检查锁是否可用，适用于哪些期望锁被持有时间非常短的情况，避免了线程进入和退出休眠状态的开销。简单理解就是一个 while。往往在单核或者低并发时更有效，在高并发时容易导致 cpu 资源浪费。
• 乐观锁&悲观锁：一种概念或分类，乐观锁认为一个线程去拿数据的时候没有修改，所以不去加锁，而是采用版本号等其他方式去判断是否修改；悲观锁认为数据随时都会修改，所以整个数据处理部分都要加锁。
• 公平锁&非公平锁：一种策略或分类，公平锁会保证线程获取锁是按它们发出请求的顺序，防止线程饥饿；非公平锁在获取锁时不会检查队列情况，会直接试图获取锁，获取不到时才加入队列排队，这样性能更好。

各种锁的底层是如何实现的？

要实现锁，可能的方法有：

• 禁止中断：进入临界区前直接禁止中断，离开后恢复，保证 cpu 不会切换到其他线程，实现简单。但给用户禁止中断的权限很危险，而且禁止中断只能控制单 cpu，其他 cpu 仍然可以获取临界资源，且关中断可能造成某些中断信号丢失，效率也低。
• TSL 指令：可以锁住内存总线，使得一个进程使用进程时另一个进程不能用。缺点同上，只是弥补了多 cpu 的问题。
• 自旋锁：用一个 flag 表示锁是否被占用，使用 TAS 原子指令（Test And Set）去尝试获取锁。如果没获取到就持续执行、自旋，直到符合 test 要求并 set 成功。或者也可以使用 Fetch And Add 原子指令，每个线程往锁里加一个属于自己的 term ticket 排队，轮到自己的时候就获取锁，这样就不会出现饥饿的情况。
• 互斥锁：由操作系统提供系统调用管理，当一个线程访问其他线程持有的锁时，会被 os 调度为阻塞状态，直到锁被释放后再唤醒一个休眠的进程。互斥锁会引入重新调度和上下文切换的开销，适合持锁时间长的场景。
• 自适应锁：先使用自旋锁的操作，尝试多次不行就执行互斥锁的操作使线程进入睡眠。

死锁的条件？生产者消费者问题？

• 死锁的四个条件：互斥条件；不可剥夺条件；请求和保持条件；循环等待条件。
• 生产者消费者问题又叫有限缓冲问题，两种角色共享固定大小的缓冲区。问题在于判断是否要休眠（缓冲区空/满）和执行休眠不是原子操作。使用信号量解决，需要设计 empty、full 两个信号量，分别表示空槽数和满槽数；需要一个 mutex 控制缓冲区使用。在实现时注意要先尝试获取对应槽位的锁，再尝试获取对应的 mutex，否则可能死锁。

内存管理

不同内存分配技术及其优缺点

• 等长固定分区法：每个分区大小相同，在系统启动时分配好，每次给进程分配一整块。优点是需要维护的管理信息很少，内存分配算法简单；缺点是不同进程需要的空间不同，内碎片多浪费空间，且限制了并发执行的程序数量。
• 不等长固定分区法：每个分区大小不同，在系统启动时分配好，每次给进程分配一块。优缺点同上。
• 动态分区法：在运行中根据进程需要的空间分配分区，通过空闲分区链表进行组织。优点是并发执行的程序数量没有限制；缺点是管理空闲块的复杂度增加，分配算法的时间开销增加。
• 页式内存管理：把固定分区面积缩小，一个进程可使用多个分区；进程被切割成若干块，装入内存的几个分区中，逻辑上通过页表关联。优点是不存在任何外碎片。
• 段式内存管理：安装逻辑意义将程序分为若干段，每个段独立载入到内存的不同区间中。优点是按逻辑而非固定面积划分；缺点是每个段必须连续且全部加载到内存中。
• 段页式内存管理：把分段和分页两种方式结合，先把程序按照逻辑意义分成段，再按固定大小对每个段分页。

虚拟内存机制？

Linux 内存管理笔记 - tk_sky的博客 (mcyou.cc)

Malloc 实现？

一个很好的介绍：Memory Allocation (samwho.dev)

malloc/free 是一组用户态实现的内存分配函数，用来操作内存分配器给程序分配和回收内存。

动态内存分配的系统调用主要使用 brk/sbrk。这两个 linux 的系统调用分别用于返回堆顶地址和扩展堆大小。堆是向上生长的，使用 sbrk 后堆顶指针会向上移动。为了高效起见，我们引入 malloc/free 用户态内存分配，不让程序直接使用 brk 或 sbrk 来分配堆内存，而是预先扩展好堆，然后将这部分空间作为缓冲池，再经过管理池化地给进程提供。

一种 malloc 的实现方式是使用空闲链表管理所有内存块，然后整块分配。在每个内存块的首部记录当前块的大小、是否已被分配。接着使用首次适应法进行分配：遍历整个链表，找到第一个未被分配、大小合适的内存块；如果没有则向系统申请扩展内存。缺点是已分配和未分配都在同一个链表，每次都要从头到尾遍历；内存是整体分配的，容易产生内部碎片。

第二种实现方式是维护空闲列表+按需分配，只包含未分配的内存块，分配时找到第一个大于等于所需空间的空闲区块，然后从该块的尾部取出所需空间，剩余空间还是在链表里。如果剩余部分不够放首部信息，就直接从空闲列表摘除。优点是只有未分配的内存块，节省了遍历开销；只分配必须大小的空间，避免内碎片。缺点是会产生分割，导致很多小的外碎片，需要额外的清理和合并逻辑。

上面的实现方法分配时间都和空闲块的数量成线性关系，所以另一种实现的方式是分离存储，也就是维护多个空闲链表，每个链表的块大致相等或者相等。一种方法是分离适配方法，设计每个空闲链表中的块大致相等。分配的时候需要先选择适当的空闲链表，然后遍历，根据匹配算法（首次适应之类）找到一个块，可以选择是否将其分割。如果找不到合适的块，则查找下一个更大的空闲链表、以此类推。在释放时合并前后相邻的空闲块，并将结果放到相应的空闲列表中。这种方法的应用广泛，C标准库的 GNU malloc 包就是这周方法。这种方法快速，内存利用率也高。

另一种分离存储的方法是伙伴系统，其空闲链表只包含大小相等的块，并且大小都是 2 的幂。最开始时全局只有一个大小为 2^m 的空闲块，因为任何内存大小都可以分成 2 的幂的和，所以可以处理任何内存大小申请。如果没有对应大小的空闲，从下一级列表抽一个块分成两块。释放时将其与相邻空闲块合并得到更大的块。伙伴系统的优势是更块的搜索速度和合并速度。

初次之外，考虑到多线程的内存分配需求，谷歌实现了 tcmalloc，后面成为了 golang 的内存模型。tcmalloc 主要是池化的思想来管理，对每个线程维护有自己的缓存池，这样在线程内分配时不需要加锁，大大提高多线程下的分配效率。

大端法小端法？

对于对象的连续存储，是 以字节为单位的。对象的地址是所使用字节的最小地址。按照有效字节在内存中的存储顺序，可以分为大端法和小端法。

大端法和人的习惯相同，将高位存放在低地址，将低位存放在高地址；小端法则是将高位存放在高地址、低位存放在低地址。

x86 架构定义使用小端法，而网络字节顺序和常见的网络协议则使用大端法。因此直接按位修改网络报文时要做对应的大小端转换。

其他

缓冲区溢出是什么？

C 语言用运行时栈来存储过程信息，每个函数的信息都存在一个栈帧里，如寄存器、局部变量、参数、返回地址等。由于 C 对数组引用不进行任何边界检查，所以对越界的数组元素的写操作会破坏存储在栈中的状态信息，称为缓冲区溢出。防范缓冲区溢出攻击的机制有：随机化、栈保护和限制可执行代码区域。

随机化通过给栈增加一段随机大小的空间、随机安排地址空间布局等方法增加了攻击的难度，但不能保证安全。栈保护则是在每个函数的栈帧的局部变量和栈状态之间存储一个随机的金丝雀值，在恢复寄存器状态和函数返回之前检测这个值是否被改变了。另外一种办法就是在硬件上引入新的位，将读和执行分开，由硬件来检查页是否可执行，从而限制可执行代码区域。

IO模型有哪些？

Linux 网络收包与 IO 多路复用 - tk_sky的博客 (mcyou.cc)

---