# 操作系统手册
**Repository Path**: weafafafa/operating-system-manual
## Basic Information
- **Project Name**: 操作系统手册
- **Description**: 操作系统记录的笔记，待完善。
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No
## Statistics
- **Stars**: 1
- **Forks**: 0
- **Created**: 2024-09-22
- **Last Updated**: 2024-10-06
## Categories & Tags
**Categories**: Uncategorized
**Tags**: None
## README
# 操作系统篇
本人做的操作系统笔记
可配套于小林coding 操作系统章节综合学习，面试小伙伴们可以快速复习
[图解系统介绍 | 小林coding (xiaolincoding.com)](https://xiaolincoding.com/os/)
# 进程与线程
#### **1.进程的控制结构**
描述进程：进程控制块（process control block，PCB）
PCB包含：
1.进程**描述**信息：进程标识符、用户标识符
2.进程**控制和管理**信息：进程当前状态、进程优先级
3.**资源**分配清单：有关内存地址空间或虚拟地址空间的信息，打开文件的列表和和使用I/O设备信息
4.CPU相关信息：进程切换，CPU状态信息保存在PCB里，以便一下次重新执行从断点恢复
一般通过**链表**形式组织，相同状态的PCB在一起，组成队列：比如，就绪队列，阻塞队列。
#### **2.进程的状态**
Java中有六大状态：初始（New）、运行（RUNNABLE、包含就绪和运行中）、阻塞、等待、超时等待、终止
和操作系统底层是一样的，1.创建进程、2.终止进程、3.阻塞进程、4.唤醒进程
阻塞、唤醒本质上都是操作PCB控制块，修改其状态为阻塞、唤醒，并将其插入到对应的队列中
#### 3.**进程上下文切换**
进程上下文切换、线程上下文切换、中断上下文切换
进程的上下文不仅包含了虚拟内存、栈、全局变量等用户空间，还包含了内核堆栈、寄存器等内核资源
#### **4.进程与线程的比较**
根本区别：线程是调度的基本单位，进程是资源拥有的基本单位
两个线程属于同一个进程，因为虚拟内存共享，所以在切换时，虚拟内存这些资源就保持不动，只需要切换线程私有数据、寄存器等不共享数据
#### **5**.线程的实现方式
1.用户线程：在用户空间实现的线程，不由内核管理，由用户态线程库来管理
2.内核线程：在内核实现的线程，由内核管理
3.轻量级线程：在内核中支持用户线程
#### 6.用户线程和内核线程的优缺点
**1.用户线程**（多用户线程对一内核线程，多对一模型）：用户线程库维护
优点：TCB由用户线程库维护，可用于不支持线程技术操作系统；上下文切换快，无需内核态切换
缺点：线程阻塞导致其他线程阻塞，每个线程都无法打断其他线程（只有操作系统才有权限）；更少的时间片
**2.内核线程**（一用户线程对一内核线程，一对一模型）：操作系统维护
优点：一个线程被阻塞，不会影响其他内核线程的运行；更多的时间片
缺点：线程的创建、终止、切换都是内核态，系统开销大；需要内核维护PCB和TCB
**所以说轻量级线程采用（M：N模型）是一个折衷！**（M=1、N=1）退化成内核线程，(M！=1、N=1)退化成用户线程。
#### 7.进程、线程调度是什么？调度原则有哪些？
**调度**：操作系统选择某一个进程、线程执行时机的功能称为调度程序。
**5个调度原则**：CPU利用率、系统吞吐率、周转时间、等待时间、响应时间
CPU利用率：CPU始终是匆忙的
系统吞吐率：单位时间CPU完成进程数，短作业会提高吞吐率
周转时间：进程运行+阻塞时间+等待时间总和，越小越好
等待时间：在就绪队列中等待的时间，不是阻塞状态时间，越短越好
响应时间：用户请求到系统第一次响应时间，交互系统，越快越好
#### 8.调度算法（单核）
1.先去先来服务：适用于CPU繁忙作业，不适用于I/O繁忙作业系统
2.最短作业优先：长作业的周转时间很长
3.高响应比优先：等待时间/要求服务时间，等待时间越大，服务时间越小，优先级越高。理想算法，预期服务时间不能得到，不能实现。
4.时间片轮转算法：靠固定时间片来控制每个进程执行时间
5.最高优先级调度算法：可能导致低优先进程永远不会运行
6.多级反馈队列：综合了时间片轮转和最高优先级调度算法。核心是长作业优先级没执行完会满满降低，而每次执行分配的时间片更多。短作业优先级较高，在第一梯队，但是每次只分配较短时间片。
#### **9.进程间有哪些通信方式？**
6种：管道、消息队列、共享内存、信号量、信号、Socket
**管道**：匿名管道（只在亲缘关系进程通信），命名管道，通信数据是无格式的，单向
**消息队列**：与管道不同，通信数据是用户自定义数据类型，消息体，且不会随进程关闭而关闭
**共享内存**：开销小，多个进程虚拟内存对应同一块开辟的共享物理内存，从而可以直接访问修改
**信号量**：用来同步或者互斥，P、V操作。
**信号**：异步通信机制，用来进行异常通知，比如kill，进程三种相应方式：1.执行默认操作 2.捕捉信号处理 3.忽略信号
**Socket**：可以用于不同主机的进程通信，有UDP\TCP、以及本地进程间通信（绑定本地文件）三种方式
#### **10.经典同步互斥问题**
**1.生产者、消费者问题**：
①生产者生成数据，放在缓存中；②消费者从缓冲区取出数据处理；③只有一个生产者或消费者可以访问
解决方案：互斥+同步
**2.哲学家就餐问题（死锁）**：
①哲学家要左右两边叉子才能吃饭
解决方案：偶数编号的哲学家拿左边叉子，奇数编号的哲学家拿右边叉子（资源有序分配法，破坏头尾相连循环等待）；或者一个哲学家在左边两边一次性去尝试拿（破坏请求与保持条件）；一定时间没拿到就放弃自己的（破坏不可剥夺条件）
**3.读写者问题**：
①读-读允许 ②读-写互斥 ③写写互斥
解决方案：读者优先、写者优先、读写公平 ；互斥+同步or公平队列
#### **11.死锁产生条件、如何避免死锁？**
**死锁产生条件**：1.互斥 2.请求与保持 3.不可剥夺 4.头尾相连循环等待
**破坏死锁**：
针对请求与保持：一次申请所有的资源
针对不可剥夺：一定时间还是没加锁成功，释放锁
针对头尾相连循环等待：资源有序分配法，两个线程都先获得某一资源才能尝试下一个资源的获取
如果真产生了死锁，通过java 的**jstack**和调试工具进行**死锁检测**。
#### **12.什么是悲观锁、乐观锁？**
悲观锁：先尝试加锁，再执行（比如lock）
乐观锁：先尝试，如果发现没有冲突，达到预期，就提交（比如CAS操作、比如腾讯在线文档）
#### **13.线程崩溃了，进程也会崩溃吗？**
在JAVA中是不会的，C++会，因为JAVA有JVM
针对StackOverFlowError和NullPointException，JVM对这些崩溃信号做了自己的信号处理函数，因为这些错误太常见了，为了维护程序的健壮性，并且自定义一些处理逻辑，比如记录crash信息。
# 调度算法
### *进程调度*
#### 1.常见的进程调度算法？
①.先来先服务（First Come First Severd, FCFS）
每次从就绪队列选择最先进入队列进程，直到该进程执行完退出或者阻塞。
②.最短作业优先（Shortest Job First, SJF）
优先选择运行时间最短的进程运行
③.高响应比优先（Highest Response Ratio Next，HRRN）
理想算法。优先权=（等待时间/要求服务时间）+1
④.时间片轮转调度算法（Round Robin，RR）
每个进程分配一个时间段，称为时间片，允许进程在该时间段运行。
⑤.最高优先级（Highest Priority First，HPF）
需要确定优先级指标如何计算。
⑥.多级反馈队列（Multilevel Feedback Queue）
【时间片轮转算法】和【最高优先级算法】的综合发展
多级：多个队列，每个队列优先级从高到底，分配的时间片由低到高
反馈：新进程进入第一级队列末尾，按照先来先服务。如果高一级执行完时间片没有完成，则放入低一级队列。
长作业等待时间变长了，但是分配时间片大小也更大了，能够兼顾长短作业和响应时间。
### *内存页面置换*
#### **2.常见内存页面置换算法？**
当出现缺页异常，需要调度新页面而内存已满时，选择被置换的物理页。
需要尽可能减少页面换入换出的I/O操作。
①.最佳页面置换（OPT）
预测页面下一次访问前所需等待时间，过于理想，可以作为基线。
②.先进先出置换（FIFO）
驻留时间最长的页置换掉。
③.最近最久未使用置换（LRU）
选择历史最长时间没有被访问的页面进行置换
④.时钟页面置换（Lock）
与LRU近似，把所有页面保存在一个类似钟面的环形链表中，一个表针指着最老页面。
当发生缺页中断，顺时针寻找：
1.如果访问位为0，淘汰该页，置换
2.如果访问位为1，清除该访问位，并把表针前移一个位置，重复该过程直到找到访问位为0的并淘汰
⑤.最不常用算法
当发生缺页中断时，淘汰历史访问次数最少的页面。
### *磁盘调度*
#### **3.常见磁盘调度算法？**
①.先来先服务（FCFS）
先来请求，先服务。
②.最短寻道时间优先（Shortest Seek First，SSF）
优先选择离当前磁头位置最近的磁道。
出现**饥饿**现象：磁头在一小块区域反复来回移动
③.扫描算法（SCAN，又称电梯算法）
磁头在一个方向移动，访问所有未完成的请求，直到到达该方向最后的磁道，才调转方向。
④.循环扫描算法（CSCAN）
与扫描算法不同，磁道只响应一个方向上的请求，返回途中不处理任何请求。
⑤.LOOK和C-LOOK
不一定需要移动到某个方向的最后一个磁道，而是设定一个最远移动距离后返回。
LOOK：针对SCAN
C-LOOK:针对CSCAN
# 网络系统
### *文件传输*
#### 1.为什么要有DMA技术？
DMA可以代替CPU完成【将数据从磁盘控制器缓冲区搬运到内核空间】的工作，从而在这个过程中解放CPU，提高效率。
#### 2.零拷贝？如何使用零拷贝？
**零拷贝本质**：没有通过CPU来搬运数据，所有数据都是DMA来传输的。
1.mmap+write （4次上下文切换，3次数据拷贝）
mmap：内核和用户共享一个缓冲区
3次拷贝指的是**：读DMA拷贝** 磁盘控制器缓存->内核缓存，**CPU拷贝** 内核缓存区->内核socket缓冲区，**写DMA拷贝** 内核socket缓冲区->磁盘控制器缓存。
2.sendfile （2次上下文切换，3次数据拷贝）
减少了内核与用户态切换，2次上下切换，但是仍然是3次数据拷贝。
3.基于SG-DMA的sendfile技术
读DMA拷贝 磁盘控制器缓存->内核缓存，写DMA磁盘 内核缓存->磁盘控制器缓存
#### 3.PageCache有什么作用？
零拷贝技术基于PageCache，PageCache具有两大作用：
1.缓存功能，缓存数据供给读程序，此外，缓存尽可能多的I/O请求并合并后写，减少磁盘寻址操作
2.预读功能，更多读入一些预期数据
大文件不适合PageCache，小文件适合PageCache，因为大文件会把PageCache缓冲区占满。
所以，小文件采用**PageCache**+**零拷贝技术**，大文件采用**直接IO-异步IO**
### *Socket网络通信传输*
#### **4.TCP Socket的过程？**
服务端：Socket（）、bind（）、listen（）、accept（）、read（）
客户端：Socket（）、connet（）、write（）
Socket有两个，一个监听Socket，一个是已连接Socket（用来传输数据）
#### **5.服务器如何服务更多的用户（I/O多路复用）？**
**采用I/O多路复用：select/poll/epoll**
select/poll：本质没有区别，select是数组，poll是链表，连续结构存储在 **Socket文件描述符集合**中，有读可用内核态遍历集合标记对应Socket，然后把集合传给用户态，用户态仍遍历一遍，所以是2次遍历。
epoll：基于红黑树+链表
利用红黑树跟踪所有待检测的文字描述符，通过链表记录就绪事件。事件驱动传链表给用户态就可以了，效率更高。此外，epoll有**水平触发**（Socket事件没处理完不断触发提醒）和**边缘触发**（Socket事件没处理完只触发一次，所以尽可能一次读完），边缘触发更高效。
### 一致性哈希
#### 6.什么是一致性哈希，为什么需要它？
一致性哈希算法就很好地解决了分布式系统在**扩容或者缩容**时，发生过多的**数据迁移**的问题。
哈希算法是对节点数量取模，而一致性哈希是对2^32取模运算，取模对象固定值。
一致性哈希通过哈希环，尽可能让节点均匀分布在环上，然后对应的key对2^32取模后顺时针寻找对应所属的存储节点。
#### **7.如果节点分布不均匀会怎样，如何解决？**
**影响**：某节点突然宕机，可能导致其他节点迁移压力过大，导致崩溃，需要尽可能分布均匀。
**解决**：
核心：节点越多，相邻节点存储的key范围小。
如果节点不足，可以采用**虚拟节点扩充**，比如A 有 A-1,A-2,A-3.B 有 B-1,B-2,B-3.C有C-1,C-2,C-3。虚拟节点更多均匀分布密度更大，当B宕机仍然有6个，然后虚拟节点映射自己对应的节点即可。·
### 高性能网络模式：Reactor和Proactor
#### 8.Reactor是什么？实现方案有哪些？
**解释**：Reactor是一种用于处理服务请求并分发到对于处理器的模型。
该模式中场景包含三个对象：Reactor、Accept、Handler
Reactor：监听和分发事件
Accept：获取连接
Handler：处理业务
**实现方案**
：
1.单Reactor 单线程：无法利用到多核CPU
2.单Reactor 多线程：只有一个Reactor承担所有事件的监听（建立连接）和响应（处理请求），高并发事件场景下差
3.多Reactor 多线程：父Reactor只负责建立连接，不负责处理请求，交给了子Reactor处理
#### **9.Proactor是什么？和Reactor有什么区别？**
**解释**：Proactor是一种异步/IO实现的网络模型。感知的是已经完成的I/O通知。
**区别**：Reactor来了事件操作系统通知应用程序（通知后，I/O需要read），Proactor操作系统完成事件通知应用程序（操作系统已经帮忙完成内核到用户态拷贝了，只通知）。
# 内存管理
#### **1.虚拟内存，物理内存？**
操作系统提供一种机制，将不同进程的虚拟地址和不同内存的物理地址映射起来。
程序中所使用的内存地址叫 **虚拟内存地址**
硬件里的空间地址叫 **物理内存地址**
##### 衍生：**为什么需要虚拟内存？**
1.程序运行有局部性原理，对于程序不经常使用到的内存，可以swap置换到磁盘。
2.每个进程虚拟内存独立，解决了多进程之间地址冲突问题。
#### 2.操作系统如何管理虚拟内存和物理内存地址的关系？
①.内存分段
不同的段有不同属性，用分段形式把这些段分离出来。
通过**段号+段内偏移量**映射。
缺点：产生外部内存碎片（无内部内存碎片）、内存交换率低（物理内存和磁盘的swap）
②.内存分页
整个虚拟和物理内存空间切成一段段固定尺寸的大小，称为页。linux下每一个页的大小为4kB。
通过**页号+页内偏移量**映射。
优点：不会产生外部内存碎片（有内部内存碎片）、内存交换率高（物理内存和磁盘的swap）
③.段页式
通过**短号+页号+页内偏移量**映射。
内存分段+分页。使用不多，linux是段页式，但实际上段的基线都是0，所以本质上是内存分段式。
#### **3.如何解决分页下页表过大情况？**
多级页表。通过局部性原理，没有使用到的内存，导致后面级别的页表可能不会创建。
**新问题：**多级页表导致查询页表时间开销增大。**解决:**TLB,缓存最近常被访问的页表项。
#### **4.linux虚拟内存的划分？**
虚拟空间可以划分为**用户态+内核态**空间
用户态包括：代码段、全局变量（初始化的静态、全局变量）、BSS（未初始化的静态、全局变量）、堆（自底向上）、栈（自顶向下）、映射区
#### **5.malloc是如何分配内存的？**
malloc分配的是虚拟内存。
分配方式：
1.系统调用brk（），堆区分配内存。
2.系统调用mmap（），文件映射区分配内存。
malloc（1）会分配更大的空间作为内存池。
其中内存块的头信息记录了内存大小，所以free只需要输入一个参数。
#### **6.free释放内存，会归还给操作系统吗？**
malloc通过brk（）方式申请的内存，free释放后会缓存在malloc内存池，待下次使用
malloc通过mmap（）方式申请的内存，free释放后会彻底的释放。
一般，brk（）用于小于128KB的空间开辟，mmap（）用于大于128KB的空间开辟。
#### **7.物理内存满了，操作系统如何回收？**
如果空闲**物理内存**不够
**回收方式**：
1.后台内存回收：唤醒kswapd线程回收，不会阻塞进程执行
2.直接内存回收：后台内存回收跟不上内存申请速度，开始直接回收，阻塞进程执行
**可回收的内存类型**：
1.文件页回收：干净页直接释放，脏页换入磁盘，后释放
2.匿名页回收：开启swap机制后，swap机制会将不长访问的匿名页换出磁盘，下次需要换回来。
**回收方法：**
文件页回收和匿名页回收 都是基于LRU算法
如果后台回收和直接回收仍然不行，触发OOM机制：
通过内存占用情况和oom_score_adj的值进行打分，分越高越先杀死。