操作系统

进程、线程、协程

一个应用程序一般对应一个进程，一个进程一般有一个主线程，还有若干个辅助线程，线程之间是平行运行的，在线程里面可以开启协程，让程序在特定的时间内运行。

• 进程：执行的程序、资源分配、由程序+数据集合+进程控制块组成，独立的堆栈、由操作系统调度（抢占式调度）、切换开销大(栈、寄存器、虚拟内存、文件句柄等)、稳定安全、进程间通信。
• 线程：多任务、调度和分派、独立的栈和共享的堆，由操作系统调度（抢占式调度）、共享进程资源、使用共享内存进行通信、上下文切换很快，资源开销较少、不够稳定容易丢失数据、多核并行高性能、适合IO密集型、通信不需要OS干预、用户线程（轻量级进程）由内核线程支持（一对一模型（真正的并发、独立、数量有限、调度开销大）、多对一模型（由用户态切换、阻塞）、多对多模型）。
• 协程：基于线程之上，比线程更加轻量级、存在用户态的轻量级线程、用户控制调度（对内核透明，内存占用小、单线程进程、无陷入和上下文切换、难以实现强制的 CPU 控制权切换，主动出让控制权）、适用于被阻塞大量并发的场景、不适用于大量计算的多线程。

Linux进程状态

• 可执行状态：正在 CPU 上执行的进程定义为 RUNNING 状态、而将可执行但是尚未被调度执行的进程定义为 READY 状态（获得了除了处理器之外的一切所需资源），linux 下统一为 TASK_RUNNING 状态。
• 可中断的睡眠状态：等待事件的发生（比如等待信号量、对应事件的等待队列中、事件发生进程被唤醒），而被挂起。
• 不可中断的睡眠状态：进程处于睡眠状态，进程是不可中断的（不响应异步信号，内核的某些处理流程是不能被打断的，比如IO操作与对应的物理设备进行交互）。
• 暂停状态或跟踪状态：收到SIGSTOP信号。
• 退出状态（EXIT_ZOMBIE）：僵尸进程、所有资源将被回收，除了 task_struct 结构（保存了进程的退出码，父进程逻辑判断）、内核通知父进程回收（父进程结束则被收养）。
• 退出状态（ EXIT_DEAD）：即将被销毁、彻底释放。
• 进程的初始状态：将调用进程（fork、clone、vfork）复制一份，得到子进程、独立。

进程通信

• 匿名管道：单工、FIFO、柱塞式、亲缘进程、本质为内核缓冲区（内存中）、约定格式。有名管道（磁盘文件、非亲缘）
• 信号：sigterm、sigkill、中断机制的一种模拟，异步通信方式（阻塞）、硬件来源、软件终止、三种处理方式
• 消息队列：内核中的消息链表、特定的格式、FIFO、随机查询。
• 共享内存：直接读写同一块内存空间、将其映射到进程的私有地址空间（内存逻辑地址）无拷贝、需要同步机制。
• 信号量：资源计数器、进程间同步、创建等待释放、等待队列、原子操作（P、V原语）、进程的线程间共享。
• 互斥量：临界区视为资源、原语加锁解锁、等待队列、管程（封装、wait、signal、synchronized方法）
• 套接字：IP+Port、远程、TCP/UDP。

线程通信

1，锁机制（互斥锁提供了以排他方式防止数据结构被并发修改的方法，条件变量可以以原子的方式阻塞进程，直到某个特定条件为真为止。对条件的测试是在互斥锁的保护下进行的。条件变量始终与互斥锁一起使用。 wait/notify 等待、Volatile 内存共享，CountDownLatch 并发工具）;信号量机制(Semaphore);信号机制(Signal)。

2，消息队列（rabbitMQ）:当不需要立即获得结果,异步处理：写入消息队列后立即返回客户端,无需等待；限流削峰：请求先入消息队列，而不是由业务处理系统直接处理，做了一次缓冲, 极大地减少了业务处理系统的压力；

点对点模式：点对点的Queue，即Producer发送消息到指定的Queue，接收方从Queue收取消息。

一对多的Topic，即Producer发送消息到指定的Topic，任意多个在线的接收方均可从Topic获得一份完整的消息副本。当Producer想要发送消息的时候，它将消息发送给指定的Exchange，由Exchange将消息根据各种规则投递到一个或多个Queue（）路由。送消息时，使用rabbitTemplate.convertAndSend(exchange, routingKey, message)可以指定Exchange、Routing Key以及消息本身。接收消息时，需要在消息处理的类上标注@RabbitListener指明要监听的queue，通过多个@RabbitHandler标注的方法接收不同类型的消息。

内存分段、分页

逻辑地址（完整、连续、进程隔离、更大内存）；物理地址（非连续）；地址转换

• 段：内存块单元、逻辑完整（保护、共享）、代码、堆栈、段号+偏移量、大小可变、段表（段号-> 物理地址）、适合处理复杂系统的逻辑分区
• 分页：大小固定、物理连续、页表（进程不共享，页号-> 物理块号）、页号（块号）+偏移量、缓存（局部性原理）、多级页表（逻辑地址大页表太长、页表的页表、多级索引）、适合管理物理内存、利用率高。
• 段页：先分段再段内分页、段号+页号+偏移、段表（段号->页表地址）、页表（页号->块号）

内存调度

• 当 CPU 访问的页面不在物理内存时（逻辑地址），便会产生一个缺页中断，请求操作系统将所缺页调入到物理内存。「页面置换算法」选择一个物理页，如果该物理页有被修改过（脏页），则把它换出到磁盘，最后把正在访问的页面装入到这个物理页中。
• 最佳页面置换算法（OPT）：置换在「未来」最长时间不访问的页面。因为程序访问页面时是动态的，我们是无法预知每个页面在「下一次」访问前的等待时间，最佳页面置换算法作用是为了衡量你的算法的效率。
• 先进先出置换算法（FIFO）：选择在内存驻留时间很长的页面进行中置换。
• 最近最久未使用的置换算法（LRU）：选择最长时间没有被访问的页面进行置换， LRU 则是通过「历史」的使用情况来推测要淘汰的页面，近似最优置换算法。代价很高：为了完全实现 LRU，需要在内存中维护一个所有页面的链表。
• 时钟页面置换算法（Lock）：把所有的页面都保存在一个类似钟面的「环形链表」中，一个表针指向最老的页面。当发生缺页中断时，算法首先检查表针指向的页面：如果它的访问位位是 0 就淘汰该页面，并把新的页面插入这个位置，然后把表针前移一个位置；如果访问位是 1 就清除访问位改为0，并把表针前移一个位置，重复这个过程直到找到了一个访问位为 0 的页面为止；
• 最不常用置换算法（LFU）：当发生缺页中断时，选择「访问次数」最少的那个页面，并将其淘汰。成本高：要增加一个计数器来实现。记忆力太好：比如有些页面在过去时间里访问的频率很高，但是现在已经没有访问了，而当前频繁访问的页面由于没有这些页面访问的次数高，在发生缺页中断时，就会可能会误伤当前刚开始频繁访问，但访问次数还不高的页面。

磁盘调度

• 多层盘片，盘片中的每一层分为多个磁道，每个磁道分多个扇区。磁盘选择（电子）+磁道选择（机械）+扇区选择(转速)。通过优化磁盘的访问请求顺序来做到的提高磁盘的访问性能。
• 先来先服务算法：如果大量进程竞争使用磁盘，请求访问的磁道可能会很分散，那先来先服务算法在性能上就会显得很差，因为寻道时间过长。
• 最短寻道时间优先算法：优先选择从当前磁头位置所需寻道时间最短的请求，后续请求距离较小，导致某些请求的饥饿。
• 扫描算法算法：磁头在一个方向上移动，访问所有未完成的请求，直到磁头到达该方向上的最后的磁道，才调换方向。不会产生饥饿现象，但是中间部分相比其他部分响应的频率会比较多，每个磁道的响应频率存在差异。
• 循环扫描算法：只有磁头朝某个特定方向移动时，才处理磁道访问请求，而返回时直接快速移动至最靠边缘的磁道，也就是复位磁头，这个过程是很快的，并且返回中途不处理任何请求，该算法的特点，就是磁道只响应一个方向上的请求。响应频率相对比较平均
• LOOK ：磁头在每个方向上仅仅移动到最远的请求位置，然后立即反向移动，而不需要移动到磁盘的最始端或最末端，反向移动的途中会响应请求。
• C-LOOK：磁头在每个方向上仅仅移动到最远的请求位置，然后立即反向移动，而不需要移动到磁盘的最始端或最末端，反向移动的途中不会响应请求。

进程调度

• 先来先服务调度算法：当一个长作业先运行了，那么后面的短作业等待的时间就会很长，不利于短作业。
• 最短作业优先调度算法：优先选择运行时间最短的进程来运行，这有助于提高系统的吞吐量。长作业饥饿。
• 高响应比优先调度算法：每次进行进程调度时，先计算「响应比优先级」，然后把「响应比优先级」最高的进程投入运行。优先级=(已等待事件+要求服务时间)/要求服务时间。这样短作业的进程容易被选中运行；对于长作业当其等待时间足够长时，其响应比便可以升到很高，从而获得运行的机会。
• 时间片轮转调度算法：每个进程被分配一个时间段，如果时间片用完，进程还在运行，那么将会把此进程从 CPU 释放出来，并把 CPU 分配另外一个进程；
• 最高优先级调度算法：从就绪队列中选择最高优先级的进程进行运行，
• 多级反馈队列调度算法：多个队列，每个队列优先级从高到低，同时优先级越高时间片越短，如果在第一级队列规定的时间片没运行完成，则将其转入到第二级队列的末尾，以此类推，直至完成。如果有新的进程加入优先级高的队列时，立刻停止当前正在运行的进程，转而去运行优先级高的队列；对于短作业可能可以在第一级队列很快被处理完。对于长作业，如果在第一级队列处理不完，可以移入下次队列等待被执行，虽然等待的时间变长了，但是运行时间也会更长了。
• O(1)、CFS。

进程切换

• 进程切换：必然陷入内核态需要切换内核态堆栈，PCB（用于描述控制进程的运行）的切换，切换页表（进程间虚拟内存独立），刷新TLB。
• 线程切换：线程共享资源，所以不需要切页表。一个线程执行至少需要寄存器和堆栈，线程切换本质就是堆栈的切换。
• 每个进程都有自己的虚拟地址空间，进程内的所有线程共享进程的虚拟地址空间，进程切换涉及虚拟地址空间的切换而线程不会。使用Cache（TLB）来缓存常用的地址映射，这样可以加速页表查找，由于每个进程都有自己的虚拟地址空间，那么显然每个进程都有自己的页表，那么当进程切换后页表也要进行切换，页表切换后TLB就失效了，cache失效导致命中率降低,表现出来的就是程序运行会变慢。

用户态、内核态

系统调用将 Linux 整个体系分为用户态和内核态；内核态：控制计算机的硬件资源、稳定安全；用户态：提供应用程序运行的空间、系统调用（os接口）、库函数对系统调用进行封装；给不同的操作给与不同的 “权限”、切换方式（系统调用、异常、外设中断）

调度

（饥饿、长短作业公平性、优先级）先来先服务、短作业优先、时间片轮转、多级队列（新进程优先级高、优先级高时间片越短、抢占式、级别降低）。

Linux调度

内核线程、调度基于线程，nice值越低优先级越高

• O(1)：常数时间、数组+链表、活动队列+过期队列、多级队列140优先级、高优先级长时间片、优先级调度、时间片用完加入过期队列（防止饿死）、活动队列空交换多动、过期队列、核心间队列独立、队列维护bitmap指示那些优先级还有任务（寻找最高优先级任务=寻找bitmap中最高位为1 的bit，cpu指令优化O(1),然后数组支持随机访问=>O(1)）、交互任务性能差
• CFS：红黑树（增删查log(N)）、不直接根据优先级分配时间、依据vruntime（nice因子大时间流逝快）决定优先级、vruntime插入红黑树、左下角vruntime最小（优先被调度）、定期将运行任务阿vruntime与左下角比较（抢占）、选择O(1)、插入O(log(N))

死锁

前提：互斥资源、请求新资源、不可抢占、等待关系闭环。

死锁检测：单资源单向有向图环检测（以每个节点为起点，深度优先、重复）。

死锁恢复：抢占恢复（用完归还）、杀死进程（选择副作用小的进程）。

死锁避免：安全前提（存在非死锁序列）下分配资源（银行家算法）。

死锁预防：非独占（假脱机打印）、非占有等待（一次请求全部资源）、破坏不可抢占（请求失败释放占有资源）。破坏等待（资源编号、请求资源序号升序、无环产生）

尾递归

传统递归在递归返回后好需要继续运算，保留栈帧；空间O(N);尾递归在递归返回后无后续运算，当前递归结果已被收集（二叉查找树的左右子节点为参数），无需保留栈帧，空间O(1)

CAS

乐观锁；根据地址v取值A=get(v)->B=f(A)->A==get(v)->成立则将B写入v,失败则不断重复至成功；重复读取get(v)，单变量原子性（封装），ABA问题（版本号比较）

阻塞非阻塞与同步异步

https://www.cnblogs.com/loveer/p/11479249.html

IO分两阶段1.数据准备阶段，2.内核空间复制数据到用户进程缓冲区（用户空间）阶段

• 阻塞和非阻塞关注的是程序在等待调用结果（消息，返回值）时的状态，对同一个线程来说的，阻塞IO和非阻塞IO的区别在于第一步发起IO请求是否会被阻塞。阻塞调用是指调用结果返回之前，主动挂起自己的操作，进程转变为“等待”的状态，调用线程只有在得到结果之后（同步：监测，异步：通知）才会返回。非阻塞调用指被调用后立即返回一个状态值，无需等I/O操作彻底完成，根据返回的状态，线程可以自行其它任务，（同步：轮询，异步：通知）。
• 同步和异步对应于调用者与被调用者，它们是线程之间的关系，关注的是消息通知的机制。同步IO和异步IO的区别就在于第二个步骤是否阻塞，如果不阻塞，发起I/O请求后仍需要继续执行，返回时不一定知道结果，当内核I/O操作完成后会通知用户线程，或者调用用户线程注册的回调函数，操作系统帮你做完IO操作再将结果返回给你，那么就是异步IO。同步IO即调用者需要等待被调用者返回结果，由处理消息者自己去等待消息是否被触发，之后才会进行下一步操作（需要等待或者轮询内核I/O操作完成后才能继续执行）。
• 阻塞与非阻塞与是否同步异步无关。
• 一个非阻塞I/O 系统调用 read() 操作立即返回的是任何可以立即拿到的数据，可以是完整的结果，也可以是不完整的结果，还可以是一个空值。而异步I/O系统调用 read（）结果必须是完整的， 但是这个操作完成的通知可以延迟到将来的一个时间点。

I/O多路复用

通过一种机制，可以监视多个文件描述符，一旦某个描述符就绪（一般是读就绪或者写就绪），能够通知程序进行相应的读写操作，没有就绪事件时，就会阻塞交出cpu。多路是指多个链接，复用指的是复用同一线程。但select，poll，epoll本质上都是同步I/O，因为他们都需要在读写事件就绪后自己负责进行读写，也就是说这个读写过程是阻塞的。

https://developer.aliyun.com/article/763247

https://juejin.cn/post/6931543528971436046

• select：时间复杂度O(n)，通过设置或者检查存放fd标志位的数据结构（fd数组为整型数组，用于保存文件描述符）来进行下一步处理，它仅仅知道有I/O事件发生了，却并不知道是哪那几个流，只能无差别轮询所有流，找出能读出数据，或者写入数据的流，效率较低。单个进程可监视的fd数量被限制，即能监听端口的大小有限。内核需要将消息传递到用户空间时需要内核拷贝动作，每次调用select，都需要把fd集合从用户态拷贝到内核态。

  1，用户线程调用select，将fd_set从用户空间拷贝到内核空间 2. 内核在内核空间对fd_set遍历一遍，检查是否有就绪的socket描述符，如果没有的话，就会进入休眠，直到有就绪的socket描述符 3. 内核返回select的结果给用户线程，即就绪的文件描述符数量 4. 用户拿到就绪文件描述符数量后，再次对fd_set进行遍历，找出就绪的文件描述符 5. 用户线程对就绪的文件描述符进行读写操作。

• poll：时间复杂度O(n)，本质上和select没有区别，它将用户传入的数组拷贝到内核空间，然后查询每个fd对应的设备状态，如果设备就绪则在设备等待队列中加入一项并继续遍历，如果遍历完所有fd后没有发现就绪设备，则挂起当前进程，直到设备就绪或者主动超时，被唤醒后它又要再次遍历fd。但是它没有最大连接数的限制，原因是它是基于链表来存储fd的。每次调用poll，都需要把fd集合从用户态拷贝到内核态。

  1,用户线程调用poll系统调用，并将文件描述符链表拷贝到内核空间。2，内核对文件描述符遍历一遍，如果没有就绪的描述符，则内核开始休眠，直到有就绪的文件描述符。3，返回给用户线程就绪的文件描述符数量。4，用户线程再遍历一次文件描述符链表，找出就绪的文件描述符。5，用户线程对就绪的文件描述符进行读写操作。

• epoll：时间复杂度O(1)，epoll可以理解为event poll，给每个fd注册一个回调函数，当fd对应的设备发生IO事件时，就会调用这个回调函数，将该fd放到一个链表中，然后唤醒在epoll_wait中进入睡眠的进程，最后只要判断一下就绪链表是否为空就行了，非空就从该链表中取出一个fd，以此达到O（1）的时间复杂度。效率提升，不是轮询的方式；根据每个fd上的callback函数来实现的，只有活跃的socket才会主动调用callback，而跟连接总数无关，会随着fd数量上升而效率下降。使用内存映射(mmap)，不需要从用户空间频繁拷贝fd数据到内核空间。

  mmap，是将文件/设备映射到内存中，进程可以通过读写内存的方式，实现对被mmap文件的操作。进程通过mmap映射相同的文件，实现共享内存方式的通信。对于大量频繁读写的文件，mmap相对read/write的方式，避免了内核空间->用户空间的数据传输和切换（epoll）。

  具体实现：对应着有三个函数：

  epoll_create：epoll_create相当于在内核中创建一个存放fd的数据结构。在select和poll方法中，内核都没有为fd准备存放其的数据结构，只是简单粗暴地把数组或者链表复制进来；而epoll则不一样，epoll_create会在内核建立一颗专门用来存放fd结点的红黑树，储监控的文件描述符，后续如果有新增的fd结点，都会注册到这个epoll红黑树上。

  epoll_ctr：select和poll会一次性将监听的所有fd都复制到内核中，而epoll不一样，当需要添加一个新的fd时，会调用epoll_ctr，给这个fd注册一个回调函数，然后将该fd结点注册到内核中的红黑树中。当该fd对应的设备活跃时，会调用该fd上的回调函数，将该结点存放在一个就绪链表（存储就绪的文件描述符）中。这也解决了在内核空间和用户空间之间进行来回复制的问题。

  epoll_wait：epoll_wait的做法也很简单，其实直接就是从就绪链表中取结点，这也解决了轮询的问题，时间复杂度变成O(1)

  Level和Edge指的就是触发点，Level为只要处于水平，那么就一直触发，而Edge则为上升沿和下降沿的时候触发。当缓冲区有数据可取的时候，ET会触发一次事件，之后就不会再触发，而LT只要我们没有取完缓冲区的数据，就会一直触发。

NIO

https://tech.meituan.com/2016/11/04/nio.html

https://xie.infoq.cn/article/fb524c4992beea6bb4487af87

https://www.cnblogs.com/loveer/p/11479887.html

1，是一种同步非阻塞的 I/O 模型，在等待就绪阶段都是非阻塞的，真正的 I/O 操作是同步阻塞。是 I/O 多路复用的基础，成为解决高并发与大量连接、I/O 处理问题的有效方式。

2，服务器端同步阻塞 I/O 处理:socket.accept()、socket.read()、socket.write() 三个主要函数都是同步阻塞的，当一个连接在处理 I/O 的时候，系统是阻塞的，所以使用多线程时，就可以让 CPU 去处理更多的事情。低并发下结合线程池使得创建和回收成本相对较低，并且编程模型简单。创建和销毁都是重量级的系统函数，线程本身占用较大内存，线程的切换成本是很高的，无法应对百万级连接。

3，所有的系统 I/O 都分为两个阶段：等待就绪和操作。举例来说，读函数，分为等待系统可读和真正的读；同理，写函数分为等待网卡可以写和真正的写。NIO 里用户最关心” 我可以读了”。NIO的读写函数可以立刻返回而不是柱塞，如果一个连接不能读写（socket.read()返回0或者socket.write()返回0），我们可以把这件事记下来，将用于传输的通道全部注册到选择器上，选择器监控通道，当某一通道就绪后连接继续进行读写，没有必要开启多线程。没有线程切换，只是拼命的读、写、选择事件。

4，Java NIO 实际读写时的核心在于：通道（Channel）和缓冲区（Buffer），选择器。通道表示打开到 IO 设备（文件流、套接字）的连接，对原 I/O 包中的流的模拟，负责传输；缓冲区用于容纳数据，负责存储，Channel的读写必须通过buffer对象，然后操作缓冲区，对数据进行处理。缓存区是双向的，既可以往缓冲区写入数据，也可以从缓冲区读取数据：缓冲区<->然后缓冲区通过通道进行传输<->从缓冲区取数据。选择器：把Channel通道注册到Selector中，通过Selecotr监听Channel中的事件状态，这样就不需要阻塞等待客户端的连接，从主动等待客户端的连接，变成了通过事件驱动，通过事件驱动实现单线程管理多个Channel的目的。

缓冲区根据数据类型的不同，可以进行划分ByteBuffer、CharBuffer等。根据工作方式分：直接缓冲区(磁盘->内核地址空间中->用户地址空间中->读取到应用程序)与非直接缓冲区(将缓冲区建立在物理内存之中,读写数据直接通过物理内存进行)，

上下文切换

• 就是先把前一个任务的 CPU 上下文（也就是 CPU 寄存器和程序计数器）保存起来，然后加载新任务的上下文到这些寄存器和程序计数器，最后再跳转到程序计数器所指的新位置，运行新任务。而这些保存下来的上下文，会存储在系统内核中，并在任务重新调度执行时再次加载进来。这样就能保证任务原来的状态不受影响，让任务看起来还是连续运行。

• 进程上下文切换 ：进程是由内核来管理和调度的，进程的切换只能发生在内核态，一次系统调用的过程，其实是发生了两次 CPU 上下文切换。（用户态-内核态-用户态）

• 线程上下文切换：当进程拥有多个线程时，这些线程会共享相同的虚拟内存和全局变量等资源。这些资源在上下文切换时是不需要修改的，线程也有自己的私有数据，比如栈和寄存器等，这些在上下文切换时也是需要保存的。

• 中断上下文切换：了快速响应硬件的事件，中断处理会打断进程的正常调度和执行，转而调用中断处理程序，响应设备事件。而在打断其他进程时，就需要将进程当前的状态保存下来，这样在中断结束后，进程仍然可以从原来的状态恢复运行。

  

进程内存布局

• 程序段(Text):程序代码在内存中的映射，存放函数体的二进制代码。
• 初始化过的数据(Data):在程序运行初已经对变量进行初始化的数据。
• 未初始化过的数据(BSS):在程序运行初未对变量进行初始化的数据。
• 栈(Stack):存储局部、临时变量，函数调用时，存储函数的返回指针，用于控制函数的调用和返回。调用一个方法或函数会将一个新的栈帧（stack frame）压入到栈中，这个栈帧会在函数返回时被清理掉。由于栈中数据严格的遵守FIFO的顺序，这个简单的设计意味着不必使用复杂的数据结构来追踪栈中的内容，只需要一个简单的指针指向栈的顶端即可。在程序块开始时自动分配内存,结束时自动释放内存，其操作方式类似于数据结构中的栈。
• 堆 (Heap):堆用于存储那些生存期与函数调用无关的数据，存储动态内存分配,需要程序员手工分配,手工释放，需要精细的算法来应付我们程序中杂乱的分配模式，优化速度和内存使用效率。分配方式类似于链表，会产生内存碎片。