操作系统复习总结

操作系统复习总结

CPU 32位和64的差别

1. 代表cpu能处理最长的字节，32位能处理4个字节，64位能处理8个字节。优势在于计算比较大的数字时，32位的计算机要拆开来计算，而64位的计算机不用。
2. 32位的CPU虚拟内存分配最多是3GB，不能超过3GB（2 ^ 32），因为在32位的计算机中cpu直接寻址是32为，也就是最多找4GB，但是有1GB的内存要分配给内核空间，但通常64为机器，会给一个进程分配4GB的内存

调度算法总结

进程调度（Cpu调度）

1. 什么时候会发成进程调度，当cpu空闲的时候，就会选择一个进程运行
   1. 运行态- > 就绪态
   2. 运行状态- >等待状态
   3. 等待状态 - > 就绪状态
   4. 运行态 -> 终止态

2. 算法
   1. 先来先服务，在队列中等的时间最长的进程会被调度。短作业饥饿
   2. 短作业有限，运行时间最短的会被调度。长作业饥饿
   3. 高响应比。响应比= （等待时间+要求服务时间）/ 要求服务时间。在要求服务时间相同是，等待时间越长响应比越高。在等待时间相同是，要求服务时间越短，响应比越高。
   4. 时间片：分配给每一个进程相同的时间片，时间片时间一到就切换下一个进程。
   5. 多级轮转：可以看出，短作业在刚进入时就被运行结束了，长作业运行没结束，进入到就绪队列2了.但是也获得了更高的运行时间。
   

页面置换算法

什么时候会发生缺页中断。采用了虚拟内存，那么页表中可能就不会有所有的页表项，一段用户要使用某一个不在页表项中的数据，且次数页表满了，就会发生缺页中断且页面置换。

1. 最佳页面置换算法：他的理论核心是，找到未来用户调度中，最不会使用的那个页面进行替换。但是这是做不到的，因为你无法预知用户未来的行为。
2. 先来先出，最早进的页面最早被置换出去
3. LRU，最久不用被置换算法：哪个页面最久没有被使用，哪个被替换出去（开销比较大
4. LFU，使用最少的被替换出去，一个计数器记录每一个页面的使用情况，使用最少的被替换（计数器对硬件需求比较大
5. 时钟轮转：当一个页面请求过来，会刷新每一个页面的访问位，遇到第一个访问位为0的就被淘汰

磁盘调度算法

1. 先来先服务，那个磁盘请求等待时间最长，服务哪个
2. 最短寻道优先，哪个请求磁头寻道时间最短先服务哪个（贪心
3. 扫描算法，电梯算法，磁头往一个方向运动，到边界再折返
4. 循环扫描：到边界不再折返，而是复位
5. LOOK和C-LOOK都是对扫描算法的优化。比如不在走到边界，直走到最远的那个不被访问的请求。C-LOOK是折返的时候不去处理请求。

内存管理

连续分配

连续分配的含义：给用户的进程分配到的是一个连续的内存空间

1. 单一分配

2. 固定分区分配：无外部碎片，有较多内部碎片，不灵活
   1. 分区大小相等
   2. 分区大小不相等

3. 不固定分区分配：有较多外部碎片
   1. 首次适应
   2. 最佳适应
   3. 最坏适应
   4. 临近适应算法

离散分配

1. 分页
   

1. 逻辑地址分为页号和业内地址。
2. 根据页号和页表寄存器找到页表，从而获得对应的物理块地址
3. 拼接自身的业内地址组成真正的物理地址
4. 整个过程读取了两次内存 

访问页表
访问真实的物理地址

5. 为了解决访问两次内存的问题，引入了快表。快表中存放的是页号和页号对应的物理块地址。这样只需要访问一次内存即可。（块表存放在cache中）
6. 为了解决页表过大的问题，可以采用多级页表

2. 分段
   1. 根据段号和段表寄存器找到对应的物理块
   2. 拼接地址访问。
   3. 区别
   分页是物理概念，且对程序员不可见。分段是逻辑概念，程序员主导
   分页地址空间是一维的，分段地址空间是二维的

3. 段页式：事实上，现在普遍用的是段页式
   1. 第一次访问获得页号
   2. 第二次访问获得真实地址
   3. 第三次访问访问真实地址

虚拟内存与虚拟存储器

虚拟内存详解

1. 虚拟内存：
   1. 定义：虚拟内存会为每一个进程单独分配一个地址空间默认为4GB，逻辑上是连续，物理上是离散的，还有一部分是存在于存储器上的
   优点：
   1. 每一个进程都有自己独立的一套地址空间，彼此隔离。
   2. 缓解了物理内存不足的情况，把一部分使用率低的程序部分放置在外存，用到的时候在置换进来。
   3. 可以减少物理内存的损耗，因为本质上是通过映射，所以进程之间会有一些共享的内存空间。比如父子进程之间的代码段是共享的，采用的是写时拷贝的技术。

2. 虚拟内存的分布
   
   切记这个内核地址空间，上下文切换等，会用得到

3. 虚拟内存的内存管理技术
   1. 段式管理
   
   段选择因子与段表

段选择因子可以理解为段号，根据段号去段表中找到对应段的基地址
段表中会有最重要的就是，段基地址，段的上下界，特权级：比如内核态的段不允许用户端的内存请求。
分段，每一段的颗粒太大
1. 外部碎片问题，回收会有比较多的不连续的内存空间，比如两块128MB的内存空间空闲，是装不了一个200MB的段的
2. 解决方法是与SWAP交换，整理内存，而因为段的颗粒比较大，与SWAP进行交换的时候也会有比较大的性能开销。

2. 分页到请求分页 

开始的页式管理

把虚拟地址拆分成页号和业内偏移量
根据页表找到页的起始位置
访问
优势：
* 因为把内存分成了固定长度的块，没有外部碎片，但是有一定的内部碎片
* 因为粒度比较小，所以每次如果有一些页面不存在，交换的的只需要几页就可以了。

3. 多级页表：可以用于减少页表的开销。TLB：比如一次段式或者页式访问需要访问两次内存，段页式就要访问3次内存，因此就产生了TLB这种东西，TLB记录了最近访问的页和页其实地址，而TLB放在cache中，相当于减少了访问内存的速度。
4. 在分页的基础上，衍生出了请求分页。也就是在一开始，允许进程不把所有的程序段都加载进入内存，允许只加载一部门。但是会对所有的程序分页，并且标记好。 

新增的字段：外存地址
状态位：是否在内存中
修改位：是否被修改了
访问字段：决定后续的页面置换算法。
具体流程：见下文

5. 段页式管理（用的比较多）  

先把程序按照逻辑分成段，再按段分页。这样访问就需要3次访问内存了

6. SWAP分区：首先，这个SWAP分区是位于硬盘上的，存放了一个进程暂时用不到的一些程序，当需要用了，再将其置换进入内存。

发生缺页异常的时间点

掌握好一个原则：os对于物理内存能省则省

    https://zhuanlan.zhihu.com/p/480830378

1. 虚拟内存分页，当页不存在内存的时候会发生缺页异常
2. fork写时拷贝，当父进程和子进程随便哪一个发生写操作，因为写时拷贝，会发生缺页异常（因为此时子进程并没有获得自己的物理内存页）
3. 进程创建的时候，分配后的虚拟内存没有被访问的话，虚拟内存是不会映射到物理内存的，这样就不会占用物理内存了，只有第一次访问的时候才会被分配，这时候就缺页异常
4. malloc，分配后的虚拟内存没有被访问的话，虚拟内存是不会映射到物理内存的，这样就不会占用物理内存了，只有第一次访问的时候才会被分配，这时候就缺页异常

虚拟存储器详解

2. 虚拟存储器：
   1. 定义允许程序运行的时候不全部被装入内存，只有需要用到的那一部分进入内存。虚拟存储器很重要的是两个动作，请求和置换。
   2. 虚拟存储器得以存在主要因为局部性原理
   空间局部性
   时间局部性

3. 请求分页地址字段 

页号
物理块号
外存地址
修改位：是否呗修改了
访问字段：最近被访问的次数，根据算法而定
状态位：是否在内存中

4. 流程 

访问开始，查看页表是否在快表中，如果再直接拼接物理地址
不在快表中，访问页表，如果发生缺页，就发生缺页终端
请求调入缺失的页，如果内存已满出发置换算法置换一页
正常访问

5. 置换算法 

先进先出
LRU：最久没有被使用的页被置换
LFU：最少使用的页被置换出
最佳置换算法：预知后面会访问那几页，选择不会被访问的置换出去（不能实现）
时钟轮转算法

进程管理

1. 进程是CPU分配资源的单位，线程是CPU调度的单位。
2. 进程是如何申请资源的
3. 进程与线程的区别
   1. 进程
   进程是程序的一次运行。是CPU分配资源的最小单位
   进程和线程是一对多的关系
   进程拥有独立的地址空间，一般一个进程有4G的内存空间。同一个进程的线程共享进程的地址空间和资源，这些线程独有的是程序计数器、虚拟机栈、本地方法栈等。
   上下文切换的时候，进程的开销要比线程的开销要大。
   • 进程切换上下文的时候，操作系统主要在做，保存现场，会把寄存器等一些信息保存到pcb中去，pcb位于整个进程地址空间的内核态空间。然后恢复了下一个进程的运行空间，还切换了一下页表
   • 进程从运行态变成就绪态或者阻塞状态

2. 线程 

线程是CPU调度的最小单位
当一个线程出错，会致使一个进程被操作系统kill掉，而一个进程出错通常不会引发其他进程崩溃。（在java中，一个线程的崩溃不会导致进程的崩溃。因为线程访问了非法空间之后，操作系统通过信号机制去终止它所对应的进程，而在java中，jvm自定义了信号机制，使其不会崩溃）
线程不能独立存在，必须依赖进程存在。
现在对于线程的理解是：因为要并发的执行进程中的一些功能，所以产生了线程的概念。
线程切换的时候，分属于两个不同的进程，也就相当于进程调度了

4. 用户线程和内核线程
   1. 用户线程
   用户线程在用户空间创建使用，系统不直接操控用户进程。优点是比较快，不经过os，缺点是一个用户线程阻塞，会致使其他用户线程也阻塞

2. 内核线程 

由操作系统负责创建管理的线程，缺点开销比较大，优点是一个内核线程阻塞不会影响其他内核线程阻塞

5. PCB：PCB是进程很重要的一个部分。它唯一标识了一个进程，并且携带资源和CPU信息
   1. PID：标识进程的字段
   2. 进程的状态，优先级等等，目前的状态
   3. 处理机的状态：很多寄存器的值

6. 进程的状态
   1. 创建态：创建进程中
   2. 就绪态：
   拥有除了CPU的一切资源。
   运行态 to 就绪态 ：时间片结束

3. 运行态
4. 终止态：被Kill或者运行结束
5. 阻塞态：一旦进程发生IO操作就会陷入阻塞状态
6. 就绪挂起态：挂起的区别就是，挂起的进程被置换到了磁盘
7. 阻塞挂起态

7. 进程调度算法
   1. FCFS：先来先服务，对短作业不友好
   2. 短作业优先：对长作业不友好
   3. 高响应比优先：响应比 = （需要服务的时间 +等待时间） / 需要服务的时间
   4. 时间片轮转算法
   5. 多级反馈队列：多级代表有多个队列，反馈是指，当有新的进程进入，会立刻去执行新的作业。优先级越高的队列，所能获得时间片越短。

进程的通信方式

1. 匿名管道：
   对于匿名管道，他是一个存于内存中的文件，它返回给进程两个描述符，分别代表读取数据的接口和写入数据的接口。这就出现问题了，我是想跨进程通信，给我整这个有什么用。这个时候就可以通过Fokr()，我们知道Fork()是除了Pcb其他基本都复制的子进程，那么自然也复制了这个文件得到了文件描述符，就可以通过这个文件，父子进程进行通信 ，作用范围在父子进程之间。

2. 有名管道：有名管道是创建了一个真实的设备文件，不同进程通过这个设备文件进行跨进程通信。

3. 共享内存：因为消息都是存放在内核态的缓存之中，用户读取都要进入内核态，来回切换造成资源的浪费，因此就有了共享内存。共享内存是双方都拿出一块虚拟地址，映射到相同的物理空间，这样就可以感知数据的变化了。

4. 消息队列：发送方把数据放在消息队列中，接收方接受消息，在管道通信的基础上提升了效率。（不够及时）

5. 信号：和信号量完全不同的概念，一般用于处理异常的工作模式，比如kill 就是发送一个信号量杀死进程

6. 信号量：主要是控制进程的同步与互斥，通过P（减一）V（加上一个资源）操作，表达还剩多少资源，从而达到让线程同步。

7. Socket通信：可以跨主机，在两台主机的进程上通信

再别说之进程的用户态内核态切换过程

切记，进程的切换和进程从用户态切换至内核态是两件事请
进程切换的时候，os，主要保存了当前现场，比如一些寄存器的值进入pcb，而pcb处于用户虚拟空间的内核空间位置，并且恢复下一个进程的现场。

而进程的用户态切入内核态，用户进入内核态也是要切换上下文的，把用户态的指令保存起来，进入内核态执行程序，再切换回用户态恢复现场，也执行了两次的上下文切换

用户从用户态进入内核态主要是。用户从用户态进入内核态主要通过trap陷入指令来完成

1. 主动发起系统调用，比如执行fork的时候就会陷入系统态
2. 发生异常
3. 外围设备的中断

再别说之用户上下文切换和线程的上下文切换

同进程的线程切换上下文，只需要保存自己的程序计数器，寄存器的值等私有变量，对于一些共享的资源就不用了切换了。这就是线程上下文切换比较简单原因。

在说一下用户态线程和内核态线程
用户态线程就是完全对操作空间不可见，完全由用户管理的线程，好处是管理的成本比较小。但是缺点是一个线程阻塞其余的线程跟着阻塞了，而且它无法到应用到多核的优势，IO交互的成本也比较打。

内核态线程由内核管理，就开销比较大。
映射关系
多个用户态对应一个内核态，一个线程阻塞其余线程都阻塞
一个用户态对应一个内核态，开销比较大
多个用户态对应多个内核态，两者结合

死锁

1. 死锁的条件
   1. 互斥
   2. 不剥夺
   3. 请求与保持
   4. 环路等待

操作系统中锁的概念

1. 互斥锁：竞争资源失败，会释放CPU资源给其他的进程

2. 自旋锁：竞争资源失败，不会释放CPU资源给其他进程

3. 读写锁：
   1. 读写锁必须作用于能明确区分出读锁和写锁的应用场景中
   2. 读写锁在读多写少的场景下比较有优势。因为读锁可以兼容

4. 乐观锁：通过版本控制等手段，本质上没有加锁，是无锁编程比如MVCC就是乐观锁的一种实现方式。适用于冲突比较少的场景

5. 悲观锁：是真正对数据加锁了

IO模型

IO模型之我真的悟了
首先了解一下

同步阻塞IO模型（BIO）：最大的特点是，在内核态处理数据的时候（把数据从磁盘读取到内核缓冲区），进程在阻塞自己。

同步非阻塞IO模型（NIO）：在数据从磁盘到操作系统内核缓冲区的这个过程中，也被称之为数据准备过程，进程是不阻塞自身，不断轮询

同步IO多路复用：在数据准备过程，不再自己轮询。在linux万物皆文件的指导思想下，一旦应用程序想要发起IO，就往一个集合中放入一个文件描述符。用一个线程统一管理这个集合，让操作系统判断，是否有数据准备成功，准备成功就通知来进行数据拷贝。这个数据拷贝是把数据从内核缓冲区拷贝至用户缓冲区
这就是区别所在，同步IO最后，都需要进程自己执行系统调用，将数据从内核缓冲区拷贝至用户缓冲区

异步IO模型：这就是异步IO的强大。最后不需要进程自己去参与数据从内核缓冲区拷贝至用户缓冲区。

IO模型

同步和异步的区别
把一个IO读写的过程分为两个步骤

1. 当线程发起IO请求的时候，Os需要把数据拷贝至内核缓冲区，数据准备过程
2. 线程真正发生读取的过程。
   同步的阻塞模型在第二步陷入阻塞，而异步模型在第二步不陷入阻塞。
   同步IO分为
   同步阻塞IO BIO：在第一个阶段，数据准备阶段，线程也会陷入阻塞状态。
   同步不阻塞IO NIO：在第一个数据准备阶段，线程会不断轮询，查看数据是否准备好

IO多路复用

IO多路复用就是一个很麻烦的点了。他的核心思想是，每当有线程去发起IO请求，都会在一个fd_set文件描述符集合中注册自己的事件，这个集合进入内核后，由os判断是否有数据准备好，并且通知对应的线程发生第二步。其中IO多路复用有 select poll epoll模式

1. select的工作流程：
   1. 先注册fd_set事件
   2. select将fd_set事件从用户态拷贝至内核空间，有os不断轮询
   3. 有时间就绪通知对应的线程搬运数据。
   缺点：1. 有长度限制1024 2. 拷贝的过程消耗资源 3. os 是 on的时间复杂度

2. poll的底层也是线性结构，和select的实现过程差不多，不过通过链表实现，避免了1024的长度限制

3. epoll：
   1. 如果说select 和poll是轮询机制。那么epoll就是事件驱动机制，有事件就绪，会通过回调函数来进行通知，避免了轮询，这样随着FD剧增，性能影响不会太大。
   2. ET边缘：事件只会发送一次
   3. LT水平：只要有事件没处理完成，会一直发通知

零拷贝

1. 先介绍DMA
   在DMA出现之前，是CPU需要自身参与数据从磁盘到内核缓冲区的流程，在DMA出现之后由DMA来代劳
   
   零拷贝有两种模式
   mmp + write
   sendfile

原来的数据拷贝

1. 四次数据拷贝
2. 四次的上下文切换
3. 两次的系统调用

MMP + wirte

用mmp系统调用代替read系统调用

read()：是把内核缓冲区的内容拷贝到用户缓冲区。

现在使用mmap()：mmap()会把内核的空间映射到用户进程中区，这当当DMA把数据从磁盘读到操作系统缓冲区的时候，用户就不要读到用户缓冲区了。

再使用write，把内核缓冲区的的数据写到socket缓冲区，再写入网卡

三次的数据拷贝（cpu参与的只有一次）

两次的系统调用

四次的上下文切换

SendFile

SendFile需要网卡支持SG-DMA技术

SendFile指的是CPU不参与数据的搬运

SendFile的流程：进程发起一次的系统调用sendfile的系统调用，DMA把数据从磁盘读入内核缓冲区，再直接写入网卡缓冲区，不介入socket缓冲区。

数据拷贝两次（cpu并没有参与数据的拷贝）

系统调用一次

上下文切换两次

一致性哈希

负载均衡的算法有很多

1. 轮询：普通的轮询会有问题，有一些机器的性能较好，有些机器的性能较差，但是却把请求平均分配。
2. 加权轮询：加权轮询是针对性能较好的机器，提高权重，能获得更多的请求。但是加权轮询对于分布式系统不太友好。（比如数据切分，key统一放在机器A，value放在机器B）
3. 这个情况就可以使用一致性哈希来做加权轮询的算法。普通哈希算法不行。一致性哈希是%2^32，是一个固定值。key取模之后，往下遇到的第一个节点就是要寻找的节点。会有数据分部不均匀。
   

发现自己对于os的锁还是弄得不是很灵清在这里整理一下

乐观锁和悲观锁

1. 乐观锁：CAS、MVCC都是乐观锁的实现方式，本质上并没有给数据加锁。
2. 悲观锁：实际上给数据加锁了。比如Synchronized比如ReentrantLock都是物理意义上的给数据加锁了。
   乐观锁适用的场景为：冲突不多的场景用乐观锁可以提升并发量，比如git。因为乐观锁的本质是发生冲突再解决冲突，而悲观锁的本质是减少冲突的发生

自旋锁和互斥锁

自旋锁和互斥锁是所有锁的根基，是最重要的两种锁

1. 自旋锁：如果竞争资源失败进入自旋，不陷入阻塞，占据cpu资源。使用自旋锁，是认为被占据的锁资源很快会被释放出来，与其陷入阻塞切换上下文，不如自旋用一点cpu的资源来避免切换上下文切换带来的开销。所以乐观锁适用于锁资源很快被释放的场景。
2. 互斥锁：如果竞争资源失败会陷入阻塞，所谓的阻塞可以理解为Java中 Thread.sleep()。也就是不占用CPU资源陷入睡眠。但是互斥锁的使用需要切换上下文（这也是Synchronized重锁重的原因，开销就在这儿）
   自旋锁可以通过while(true) + CAS操作来实现
   互斥锁加锁的核心思路其实很简单，锁再怎么说破天，不过是内存空间的一块空间，各个线程抢着把这个空间设置为1，表示被自己占用了，所以其实本质上就由一些原语保证这个操作的原子性即可。

读锁和写锁

读锁和写锁还有一个别名，共享锁和独占锁。
读锁和读锁兼容，与写锁不兼容
写锁与写锁和读锁都不兼容
可以通过信号量来完成读写锁

可重入锁

公平锁

自适应锁

进程什么时候从用户态切换成系统态

1. 主动发起系统调用，比如执行fork的时候就会陷入系统态
2. 发生异常
3. 外围设备的中断

实现方式：中断、异常、陷入机制

中断的分类：
1. 缺页中断
2. 越界中断

大端小端：
小端，低位放低位地址，高位放高位地址
大端，低位放高位地址，高位放低位地址