操作系统概述

系统调用/用户态和内核态

用户态：用户态可以直接读取用户程序的数据。
内核态：内核态运行的程序几乎可以访问计算机的任何资源，不受限制。

用户态无法直接访问硬件资源，而内核态可以；系统通过硬件保护机制防止用户态程序直接访问关键资源，确保系统稳定和安全。

什么是系统调用？

日常情况下我们的程序基本运行在用户态，当遇到与内核态级别有关的资源调用时，就需要进行系统调用，大致分为五类
- 设备管理：完成设备的请求或释放，以及设备的启动等。
- 文件管理：完成文件的增删改查。
- 进程管理：完成进程的创建、撤销、阻塞及唤醒等功能。
- 进程通信：完成进程间的消息传递或信号传递。
- 内存管理：完成内存的分配、回收以及获取作业占用内存的大小及地址等功能。

什么情况下发生系统调用？
1. 主动系统调用
  - 用户态主动请求切换到内核态，用户态进程通过系统调用申请使用操作系统提供的服务程序完成工作，比如read操作，比如fork()操作。系统调用的核心是OS为用户开了一个特别的中断来实现。
2. 异常
  - 当CPU在执行运行在用户态下的程序时，发生了某些事先不可知的异常，这时会触发由当前运行进程切换到处理此异常的内核相关程序中，也就转到了内核态，比如缺页异常。
3. 外围设备的中断
  - 当外围设备完成用户请求的操作后，会向CPU发出相应的中断信号，这时CPU会暂停执行下一条即将要执行的指令转而去执行与中断信号对应的处理程序，如果先前执行的指令是用户态下的程序，那么这个转换的过程自然也就发生了由用户态到内核态的切换。比如硬盘读写操作完成，系统会切换到硬盘读写的中断处理程序中执行后续操作等。如网卡接收到数据包、定时器中断等也会导致从用户态切入内核态，执行中断服务程序。

用户态程序无法直接访问硬件资源，为了在受限的权限下完成磁盘读写、网络通信、进程创建等操作，用户程序需要通过系统调用请求内核代为执行。以 Linux 为例，系统调用通过特殊的 syscall 指令触发软中断（软中断是调用方法，硬中断不可控，比如 IO完成通知、定时器、外设输入），由操作系统内核中的中断处理程序接管执行，完成如 read(), fork() 等功能后再返回用户态。

其他必会知识

并行与并发

并行(Parallelism)：多个任务在同一时刻被多个处理器或多个核心同时执行，是物理上的同时发生，常用于计算密集型任务。

并发(concurrency)：在一个时间段内多个任务被启动，并由单个处理器交替执行，依靠任务调度机制实现“看似同时”进行，适用于IO密集型任务或资源共享的场景。

并发更侧重于任务间的切换与调度控制，可在单核或多核系统中实现；而并行依赖于多核资源，更强调同时执行多个任务的能力。
//todo()
在Java中，synchronized 和 ReentrantLock 是并发控制工具；他们用来控制多个线程并发访问共享资源的行为，防止出现竞态，知识扩展到锁。
ForkJoinPool 和 parallelStream() 是实现并行计算的常用工具

同步和异步

同步（Synchronous）是指调用方发出请求后必须等待任务执行完成并返回结果才能继续执行下一步，期间调用线程会被阻塞。

异步（Asynchronous）是指调用方发出请求后不等待结果立即返回，任务通常由其他线程或事件回调处理，调用线程可继续执行后续逻辑，不被阻塞。

异步编程：线程池

进程管理

线程，进程，协程的区别
- 进程是操作系统分配资源的基本单位，每个进程有独立的地址空间、文件描述符等资源。
- 线程是CPU调度的基本单位，是进程内的执行流，多个线程共享进程资源但独立调度。
- 协程是用户态轻量级线程，由程序自身控制切换，不需要内核参与，调度成本低，适合高并发IO场景。
进程vs线程
- 资源管理：进程拥有独立的资源，线程共享所属进程的资源
- 调度机制：线程是调度单位，切换成本低；线程切换仅需保存少量寄存器，不涉及页表/地址空间切换；而进程切换需要保存和恢复全部上下文，包括内存映射，开销更大。
- 系统开销：进程创建/销毁需要分配内存、句柄等系统资源，线程的系统开销更小。
- 通信机制：线程可以直接共享内存通信；进程需要使用IPC机制，如管道，socket，或共享内存。
PCB是什么？（Process Control Block）
- PCB主要包含以下几部分内容：
  - 进程的描述信息，比如进程的名称，标识符。
  - 处理机的状态信息。当程序中断时保留此时的信息，以便CPU返回时能从断点处执行。
  - 进程调度信息，比如阻塞原因，状态，优先级等。
  - 进程控制和资源占有，同步通信机制，链接指针。
- PCB的作用？
  - PCB是进程实体中的一部分，是操作系统中最重要的数据结构
  - 由于它的存在，可以使程序并发运行。
  - 系统通过PCB来感知进程的存在。
  - 进程的组成可以用这张图来表示，换句话说，PCB是程序的唯一标识符。
进程的五种状态
- 创建、就绪、运行、阻塞、结束
- 就绪和运行可以互相转化，当进程为就绪态时，若CPU为其分配时间篇，即可运行，状态变为运行。
- 运行状态结束后又变回就绪态。
- 阻塞状态是进程在运行状态中，需要等待某个资源，比如打印机资源，从而挂起的状态，等资源拿到后会回到就绪态，等待CPU时间片。
进程调度算法
- 先来先服务(FCFS)、短作业优先(SJF)、最短剩余时间有限(SRTN)、时间片轮转、优先级调度、多级反馈队列
进程同步的方式
1. 临界区
  - 多个进程对共享资源的访问代码区域称为临界区，系统通过加锁等机制确保任意时刻仅有一个进程执行临界区代码。
2. 同步和互斥
  - 同步：多个进程因为合作产生的直接制约关系，使得进程有一定的先后顺序。
  - 互斥：多个进程在同一时刻只有一个进程能进入临界区。
3. 信号量(Semaphore)
  - 信号量是一个整型计数器，用于控制进程间访问临界资源的个数。通过原子操作 P()（等待）和 V()（释放）实现：
  - P：如果信号量大于零，就对其进行减 1 操作；如果信号量等于 0，进程进入 waiting 状态，等待信号量大于零。
  - V：对信号量执行加 1 操作，并唤醒正在 waiting 的进程
    
    如果信号量只能取 0 或者 1，那么就变成了互斥量，其实也可以理解成加锁解锁操作，0 表示已经加锁，1 表示解锁。
  - 信号量是什么？是一种用于控制多进程或多线程并发访问共享资源的同步机制，汉堡店例子，有两种信号量：整型信号量和记录型信号量。记录型信号量执行P操作先–，然后判断当前值是否小于0，如果小于0，将其添加进阻塞队列；如果此时执行V操作让值大于等于0，说明在阻塞队列中存在进程已经预定了库存，分配给他。
4. 管程(Monitor)
  - 管程是高级语言层面的同步机制，封装了共享资源、临界区操作和条件变量。管程内部自动实现互斥，外部无法直接访问内部资源。Java 中 synchronized、wait/notify 就是典型的管程模型实现。
    
    Java中的ReentrantLock、Condition、Semaphore等都是对底层同步机制的封装。合理选用这些同步原语是高并发编程的核心。
进程间通信的方式(重要！)

两个进程都只能访问自己的那一片地址空间，如果一个进程可以随意访问另一个进程的地址空间，会修改另一个进程的数据，导致数据不安全。
1. 共享存储
- 操作系统在内存中划出一块共享存储区，数据的形式、存放位置都由通信进程控制，而不是操作系统。这种共享方式速度很快，是一种高级通信方式。但需要借助**同步机制（如信号量、互斥锁）**来防止竞态。
1. 管道
- 管道只能采用半双工通信，某一时间段只能实现单向的传输，如果要实现双向同时通信，则需要设置两个管道。
- 各进程互斥地访问管道
- 当管道被写满的时候，写进程应该被阻塞。
- 当管道空的时候，读进程应该被阻塞。
1. Socket和 MQ

死锁

讲讲死锁发生的条件是什么？
1. 资源分配是互斥的：资源要么处于被分配给一个进程的状态，要么就是可用状态。
2. 等待和占有条件：进程在请求资源得不到满足的时候，进入阻塞等待状态，且不释放已占有的资源。
3. 不剥夺条件：已经分配给一个进程的资源不能强制性地被抢占，只能等待占有他的进程释放。
4. 环路等待：有两个或者两个以上的进程组成一条环路，该环路中的每个进程都在等待下一个进程释放所占有的资源。
如何避免死锁的发生？
1. 预防策略：从形成死锁的四个条件入手，打破这四个条件的一个或多个
  - 破坏互斥条件：比如只读文件、磁盘等软硬件资源可采用这种办法处理。
  - 破坏占有和等待条件：在进程开始执行之前，就把其要申请的所有资源全部分配给他，直到所有资源都满足，才开始执行。
  - 破坏不剥夺条件：允许进程强行从资源占有者那里夺取某些资源
  - 破坏环路等待条件：给系统的所有资源编号，规定进程请求所需资源的顺序必须按照资源的编号依次执行。
2. 避免死锁
  - 银行家算法
3. 如果发生了死锁怎么办？
  - 先检测到死锁
  - 撤销进程法
    - 撤销陷于死锁的全部进程
    - 逐个撤销陷于死锁的进程，直到思索不存在
  - 资源剥夺法
    - 从陷于死锁的进程中逐个强迫放弃所占用的资源，直至死锁消失；
    - 从另外的进程那里强行剥夺足够数量的资源分配给死锁进程，以解除死锁状态。
你能举出一个死锁的例子吗？

假设生产者进程先加锁再检查缓冲区是否已满，而消费者进程先检查锁再访问缓冲区。当缓冲区满，生产者阻塞；消费者因锁被占用也阻塞，形成相互等待 —— 死锁。

死锁问题的本质是对有限资源的不当管理，在设计并发程序时应优先关注资源分配顺序和锁粒度控制。

内存管理

内存管理的几种机制
操作系统常见的内存管理机制包括分区管理、分页管理、分段管理和段页式管理。
1. 分区管理（固定/可变）
  - 最早的机制是将内存划分为若干固定大小或可变大小的区域（分区），每个进程占用一个区域。**缺点是会产生内部或外部碎片，且灵活性差，**因此被现代机制所取代。
2. 分页管理
  - 将逻辑地址空间划分为固定大小的页（Page），将物理内存划分为相同大小的页框（Frame），通过页表实现逻辑地址与物理地址的映射。分页提高了内存利用率，解决了外部碎片问题，但可能会增加访问开销。
3. 分段管理
  - 将程序按照逻辑结构划分为多个段（如代码段、数据段、堆栈段等），每段具有独立的基址和长度，通过段表映射到物理内存。分段体现了程序的逻辑结构，便于共享和保护，但可能产生外部碎片。
4. 段页式管理
  - 是分页与分段的结合。先将逻辑地址空间划分为段，再将每个段分页，结合段表和页表进行地址转换。该机制既保留了分段的逻辑性，又解决了分段带来的碎片问题，是现代操作系统广泛采用的方式。
分页和分段有什么区别呢？

共同点的话：
- 首先都是离散分配的，单每个页和每个段的内存是连续的。
- 都是为了提高内存利用率，减少内存碎片。
不同点：
- 分页式管理的页面大小是固定的，由操作系统决定；分段式管理的页面是由用户程序所决定的。
- 分页是为了满足操作系统内存管理的需求，每一页是没有实际的意义的；而段是有逻辑意义的，在程序中可认为是代码段、数据段。
- 分页的内存利用率高，不会产生外部碎片；而分段如果单段长度过大，为其分配很大的连续空间不方便，会产生外部碎片。

讲讲分页管理的快表和多级页表（按照why how的方式来回答，即为什么出现快表，是如何解决痛点的）
why?

快表（TLB，Translation Lookaside Buffer）

为什么要有快表？（Why）
在分页管理中，每次内存访问前都要先查页表，再根据页表找到物理地址。这样一来，访问一个内存地址要两次内存访问（查页表 + 真正访问数据），开销非常大。为了优化访问速度，操作系统引入了快表（TLB），它是一个小型的、快速的硬件缓存，专门用来缓存页表项。
快表是如何工作的（How）
每次访问内存地址时，先用页号去查快表：

如果命中（也叫TLB Hit），就直接拿到对应的物理页框号，速度非常快；
如果不命中，就去查主存中的页表，查到后再把这个页表项加入快表；
如果快表满了，会使用替换策略（如LRU）淘汰掉旧的页表项。

快表的设计基于局部性原理：最近访问的页很可能会被再次访问，所以把它缓存在硬件里可以大幅提高访问速度。

多级页表（Multi-level Page Table）

为什么要有多级页表？（Why）
在32位系统中，假如虚拟地址空间是4GB，页大小是4KB，那就需要
4𝐺𝐵/4𝐾𝐵=1𝑀 个页表项。每个页表项4字节，总共页表大小就是4MB，光是页表就占了很多内存，对资源是一种浪费。于是提出多级页表，用树形结构按需加载页表项，节省内存空间。
多级页表是怎么工作的？（How）
以两级页表为例，虚拟地址被分成三部分：

一级页表索引
二级页表索引
页内偏移
访问地址时，先根据一级索引找到对应的二级页表地址，再用二级索引找到具体页表项，最后加上页内偏移得到物理地址。
多级页表的好处是：只有用到的页表项才会被加载到内存中，节省了大量内存空间，但代价是地址转换过程变长（可以通过快表优化）。

讲讲虚拟内存

一、为什么需要虚拟内存？（Why）

早期的程序运行时，必须整个程序全部装入内存才能执行。这个方式有几个问题：

程序太大时根本装不下；
多个程序同时运行，内存不够用；
程序之间容易互相干扰，缺乏隔离性。
而事实上，程序在某个时刻真正会用到的数据往往只是很小一部分，所以我们没必要一次性全部加载。这就引出了虚拟内存的概念。

二、虚拟内存是怎么实现的？（How）

虚拟内存的核心思想是：让程序以为它有一整块连续的内存空间，而操作系统背后悄悄地在做“地址映射”和“按需加载”。
具体来说：

每个进程有一个虚拟地址空间，和物理内存空间隔离；
程序执行时，只加载当前需要的页面，其余放在磁盘（也叫“后备存储”）；
如果程序访问了一个不在内存的页，会触发缺页中断；
操作系统此时从磁盘中把该页加载进内存；
如果内存满了，还会触发页面置换，将旧的页换出去，把新的页换进来。

这一整套机制依赖于硬件支持的地址映射（MMU），以及操作系统的分页管理、页面置换算法和缺页中断机制。

虚拟内存的三种实现技术？
1. 请求分页式存储管理
  - 程序运行时只加载当前需要的部分；
  - 没有加载的部分先留在磁盘中；
  - 一旦访问未加载的部分，就触发缺页（或缺段）中断，把需要的数据调入内存；
  - 若内存不足，还要进行页面或段的置换。
    
    核心目标都是：基于局部性原理，按需加载，提高内存利用率。
2. 请求分段式存储管理
3. 请求段页式存储管理（主流，先分段再分页）
讲讲页面置换算法？

一、为什么需要页面置换？（Why）

在请求分页的机制下，程序访问的页面不一定都在内存中，一旦访问了不在内存的页面，就会产生缺页中断。如果这时内存已经满了，就需要将某个当前在内存中的页面换出去，把新的页面换进来，这就需要用到页面置换算法。换句话说，页面置换就是一种淘汰策略，目的是在内存空间有限的前提下，尽量保留“有用的页面”，提高命中率。

二、常见的页面置换算法（How）

OPT（最优置换算法）

思想：总是淘汰未来最长时间不会用到的页面。
优点：命中率最高，是理想状态的上限。
缺点：无法实现，因为操作系统无法预知未来。

一般用于评估其他算法性能的理论上限。

FIFO（先进先出）

思想：按页面进入内存的先后顺序，最早进入的最先淘汰。
优点：实现简单，基于队列结构。
缺点：可能淘汰掉频繁使用的页面，存在Belady异常（页框变多反而缺页率升高）。

LRU（最近最久未使用）

思想：淘汰最长时间没被访问的页面，基于时间局部性原理。
实现方式有：
- 使用链表或栈，记录访问顺序；
- 用时间戳、计数器等辅助信息。
优点：性能较好，效果接近OPT。
缺点：实现复杂，开销大，需要硬件支持或软件模拟。

文件系统

文件系统主要做了什么？

文件系统主要负责管理和组织计算机存储设备上的文件和目录
1. 存储管理：将文件数据存储到物理存储介质中，并且管理空间分配，以确保每个文件都有足够多的空间存储。
2. 文件管理：文件的创建、删除、移动、重命名、压缩、加密、共享等。
3. 目录管理：目录的创建、删除、移动、重命名。
4. 文件访问控制：管理不同用户或进程对文件的访问权限，以确保用户只能访问其被授权的文件，保证文件的安全性和保密性。

硬链接和软链接有什么区别？
1. 硬链接
  - 在 Linux/类 Unix 文件系统中，每个文件和目录都有一个唯一的索引节点（inode）号，用来标识该文件或目录。硬链接通过 inode 节点号建立连接，硬链接和源文件的 inode 节点号相同，两者对文件系统来说是完全平等的（可以看作是互为硬链接，源头是同一份文件），删除其中任何一个对另外一个没有影响，可以通过给文件设置硬链接文件来防止重要文件被误删。
  - 只有删除了源文件和所有对应的硬链接文件，该文件才会被真正删除。
  - 硬链接具有一些限制，不能对目录以及不存在的文件创建硬链接，并且，硬链接也不能跨越文件系统。
  - ln命令用于创建硬链接。
2. 软链接（Symbolic Link 或 Symlink）
  - 软链接和源文件的 inode 节点号不同，而是指向一个文件路径。
  - 源文件删除后，软链接依然存在，但是指向的是一个无效的文件路径。
  - 软连接类似于 Windows 系统中的快捷方式。
  - 不同于硬链接，可以对目录或者不存在的文件创建软链接，并且，软链接可以跨越文件系统。
  - ln -s 命令用于创建软链接。
硬链接为什么不能跨文件系统？

硬链接是通过 inode 节点号建立连接的，而硬链接和源文件共享相同的 inode 节点号。然而，每个文件系统都有自己的独立 inode 表，且每个 inode 表只维护该文件系统内的 inode。如果在不同的文件系统之间创建硬链接，可能会导致 inode 节点号冲突的问题，即目标文件的 inode 节点号已经在该文件系统中被使用。

提高文件系统性能的方式有哪些？

优化硬件：使用高速硬件设备（如 SSD、NVMe）替代传统的机械硬盘，使用 RAID（Redundant Array of Inexpensive Disks）等技术提高磁盘性能。
选择合适的文件系统选型：不同的文件系统具有不同的特性，对于不同的应用场景选择合适的文件系统可以提高系统性能。
运用缓存：访问磁盘的效率比较低，可以运用缓存来减少磁盘的访问次数。不过，需要注意缓存命中率，缓存命中率过低的话，效果太差。
避免磁盘过度使用：注意磁盘的使用率，避免将磁盘用满，尽量留一些剩余空间，以免对文件系统的性能产生负面影响。
对磁盘进行合理的分区：合理的磁盘分区方案，能够使文件系统在不同的区域存储文件，从而减少文件碎片，提高文件读写性能。

常见的磁盘调度算法
1. 先来先服务算法（First-Come First-Served，FCFS）：按照请求到达磁盘调度器的顺序进行处理，先到达的请求的先被服务。FCFS 算法实现起来比较简单，不存在算法开销。不过，由于没有考虑磁头移动的路径和方向，平均寻道时间较长。同时，该算法容易出现饥饿问题，即一些后到的磁盘请求可能需要等待很长时间才能得到服务。
2. 最短寻道时间优先算法（Shortest Seek Time First，SSTF）：也被称为最佳服务优先（Shortest Service Time First，SSTF）算法，优先选择距离当前磁头位置最近的请求进行服务。SSTF 算法能够最小化磁头的寻道时间，但容易出现饥饿问题，即磁头附近的请求不断被服务，远离磁头的请求长时间得不到响应。实际应用中，需要优化一下该算法的实现，避免出现饥饿问题。
3. 扫描算法（SCAN）：也被称为电梯（Elevator）算法，基本思想和电梯非常类似。磁头沿着一个方向扫描磁盘，如果经过的磁道有请求就处理，直到到达磁盘的边界（要到0），然后改变移动方向，依此往复。SCAN 算法能够保证所有的请求得到服务，解决了饥饿问题。但是，如果磁头从一个方向刚扫描完，请求才到的话。这个请求就需要等到磁头从相反方向过来之后才能得到处理。
4. 循环扫描算法（Circular Scan，C-SCAN）：SCAN 算法的变体，只在磁盘的一侧进行扫描，并且只按照一个方向扫描，直到到达磁盘边界（要到头），然后回到磁盘起点(0)，重新开始循环。
5. 边扫描边观察算法（LOOK）：SCAN 算法中磁头到了磁盘的边界才改变移动方向，这样可能会做很多无用功，因为磁头移动方向上可能已经没有请求需要处理了。LOOK 算法对 SCAN 算法进行了改进，如果磁头移动方向上已经没有别的请求，就可以立即改变磁头移动方向，依此往复。也就是边扫描边观察指定方向上还有无请求，因此叫 LOOK。
6. 均衡循环扫描算法（C-LOOK）：C-SCAN 只有到达磁盘边界时才能改变磁头移动方向，并且磁头返回时也需要返回到磁盘起点，这样可能会做很多无用功。C-LOOK 算法对 C-SCAN 算法进行了改进，如果磁头移动的方向上已经没有磁道访问请求了，就可以立即让磁头返回，并且磁头只需要返回到有磁道访问请求的位置即可。不下到0楼了，下到第一个有人的地方。
  
  LOOK和C-LOOK ：LOOK返回接人，CLOOK直接上到最两边有人的地方
谈谈inode?

Linux会为每个文件分配两个数据结构：索引节点（index node）以及目录项（directory entry），它们主要用来记录文件的元信息和目录层次结构。
- 索引节点：inode，用来记录文件的元信息，比如inode编号、文件大小、访问权限、创建时间、修改时间、数据在磁盘的位置；索引节点是文件的唯一标识符。
- 目录项：用来记录文件的名字，索引节点指针，以及与其他目录项的层级关联关系。多个目录项关联起来就会形成目录结构，目录项不存放在磁盘，而是缓存在内存
  
  目录项和索引节点的关系是一对多