操作系统

概念

操作系统是管理和控制计算机硬件与软件资源的计算机程序。换句话说，操作系统是用户和计算机的接口，使得计算机系统所有资源最大限度发挥作用

分类：

批处理、分时、实时、嵌入式、个人计算机操作系统

结构：

驱动程序、内核、接口库、外围

I/O多路复用

一个进程处理多个请求事件，这就称为I/O多路复用

select/poll

将文件描述符集合拷贝到内核里，内核循环遍历已连接的Socket，当需要执行读写操作时会做标记，然后在复制在用户态执行遍历，处理读写事件，这里面需要拷贝两次。时间复杂度为O(n)

不同点：

• select：使用BitsMap保存固定长度的文件描述符，只能监听 0~1023 的文件描述符
• poll：使用动态数据保存文件描述符，突破了 select 的文件描述符个数限制，当然还会受到系统文件描述符限制。

epoll

9.2 I/O 多路复用：select/poll/epoll | 小林coding (xiaolincoding.com)

epoll_create维护一个epoll对象，epoll_ctl指令将待检测的socket加入到红黑树保存，红黑树的增删改查时间复杂度都是O(logn)，然后在循环中调用epoll_wait不断读取发生事件的socket个数，在就绪事件队列读取socket，然后程序会对接受到数据的socket拷贝到用户态进行处理，避免了一次性读取所有的socket的操作

1
2
3
4
5
6
7
8
9
10
11
12
13

int s = socket(AF_INET, SOCK_STREAM, 0);
bind(s, ...);
listen(s, ...)

int epfd = epoll_create(...);
epoll_ctl(epfd, ...); //将所有需要监听的socket添加到epfd中

while(1) {
    int n = epoll_wait(...);
    for(接收到数据的socket){
        //处理
    }
}

优势：

• 事件驱动，内核里维护了一个链表来记录就绪事件（发生的事件），当某个 socket 有事件发生时，通过回调函数内核会将其加入到这个就绪事件列表中
• 红黑树维护文件描述符，增删改查速率很快，并且只保存待检测的socket，而select/poll 每次操作时都传入整个 socket 集合给内核，减少数据拷贝和内存占用

事件：

• 边缘触发：当有可读事件触发，epoll_wait只会触发一次，保证一次性读取完内核缓冲去区的数据

当没数据可以读取的时候会发生阻塞，程序就没办法继续往下执行，所以边缘触发模式一般和非阻塞 I/O 搭配使用

• 水平触发：服务器端不断地从 epoll_wait 中苏醒，直到内核缓冲区数据被 read 函数读完才结束

TIP：多路复用 API 返回的事件并不一定可读写的，所以epoll需要结合非阻塞I/O使用

进程

PCB

进程控制块（process control block，PCB）

定义进程的关键信息，通过链表组织（按组织类别可分为：阻塞队列、就绪队列），各进程的切换是通过PCB的数据来恢复实现的

其具体保存了以下数据：（进程标识、状态、资源分配清单、CPU相关（寄存器值、状态））

进程描述信息：

• 进程标识符：标识各个进程，每个进程都有一个并且唯一的标识符；
• 用户标识符：进程归属的用户，用户标识符主要为共享和保护服务；

进程控制和管理信息：

• 进程当前状态，如 new、ready、running、waiting 或 blocked 等；
• 进程优先级：进程抢占 CPU 时的优先级；

资源分配清单：

• 有关内存地址空间或虚拟地址空间的信息，所打开文件的列表和所使用的 I/O 设备信息。

CPU 相关信息：

• CPU 中各个寄存器的值，当进程被切换时，CPU 的状态信息都会被保存在相应的 PCB 中，以便进程重新执行时，能从断点处继续执行。

状态

• 创建：进程创建
• 就绪：可运行，等待时间片
• 运行：占用CPU
• 阻塞：等待事件触发
• 结束：进程退出

通信

管道

管道通信是单向的（FIFO），所谓的管道，就是内核里面的一串缓存。另外，管道传输的数据是无格式的流且大小受限

• 匿名管道：只适用于shell父进程fork子进程，前面的写作用于后面的读

1

ps auxf | grep mysql

• 命名管道：它可以在不相关的进程间也能相互通信，命令管道提前创建了一个类型为管道的设备文件，在进程里只要使用这个设备文件，就可以相互通信

1

int pipe(int fd[2])

消息队列

消息队列是保存在内核中的消息链表，消息的发送方和接收方要约定好消息体的数据类型，所以每个消息体都是固定大小的存储块，不像管道是无格式的字节流数据。不会随进程的结束而销毁

优势：

• 异步处理：进程不用相互等待
• 流量削峰、减藕

劣势：

• 消息不及时
• 大小限制
• 用户态和内核态的拷贝开销

共享内存

进程可以将同一段物理内存连接到他们自己的地址空间中，所有的进程都可以访问共享内存中的地址。

如果某个进程向共享内存写入数据，所做的改动将立即影响到可以访问同一段共享内存的任何其他进程。

不同进程的虚拟内存空间映射同一块物理内存空间，避免了消息队列用户态和内核态的拷贝开销，但是容易出现覆写问题

如何解决覆写？

通过信号量的P（-1）V（+1）操作，A进程操作共享内存时进行P操作，此时B进程发现该内存的信号量小于0，则阻塞；等至进程A执行完操作之后，执行V操作，这个时候B发现信号量不小于0则对共享内存进行操作

任务调度

单位

任务调度单位对比

• 协程：拥有自己的寄存器上下文和栈，并且由程序员自己调度和管理，上下文切换开销较小，因为它只涉及到用户态的内存切换
• 线程：线程是进程内的一个执行实体，线程的上下文切换开销较大，因为它涉及到内核态和用户态之间的切换。

进程

进程（Process）是操作系统中资源分配和调度的基本单位。每个进程有自己的内存空间和系统资源，是一个独立运行的程序实例。进程之间是相互隔离的，通常一个进程的崩溃不会影响到其他进程。

线程

线程（Thread）是进程中的一个执行路径。一个进程可以包含多个线程，它们共享进程的内存空间和资源，但每个线程有自己的栈和寄存器。线程是 CPU调度的基本单位，线程之间的切换比进程更轻量级。

协程

协程（Coroutine）是一种比线程更轻量级的存在。在许多编程语言中，协程是用户态的调度单位，它们可以在单线程中实现并发。协程通过程序员显式调用来切换，而不是由操作系统进行调度。协程主要用于处理异步任务，具有较高的效率。

使用场景

很适合高并发场景下的异步处理，这得益于协程的轻量、非阻塞特性（挂起yield而非阻塞blocking，减少资源浪费）

1. 单线程并发执行
2. IO密集型任务
3. 实时数据处理场景

进程调度详解

两种调度方式

主动配合式

每个进程主动调用进程切换API来释放CPU时间

强制式

时间片中断轮转

任务切换本质

CPU中存在有大量的寄存器，进程运行产生的临时数据都被保存在这些寄存器中，这些临时数据被称为进程的硬件上下文，当时间片消耗完的时候，进程会保存这些上下文，现阶段大家可以理解为保存到PCB中，当进程被二次调度时，进程会将曾经保存的硬件上下文进行恢复（将之前保存的硬件上下文覆盖到CPU的寄存器中）

步骤：

1. 上下文保存： 当操作系统决定要切换到另一个进程时，首先需要保存当前进程的上下文信息，包括程序计数器、寄存器内容、栈指针等。这些信息存储在进程的控制块（PCB）中。
2. 选择新进程： 在确定要切换到哪个新进程之前，操作系统会根据调度算法从就绪队列中选择一个合适的进程。这个选择可能基于进程的优先级、先到先服务（FIFO）、轮转法等。
3. 加载新进程的上下文： 一旦确定了新进程，操作系统就会从其对应的PCB中恢复该进程的上下文信息。这包括将新进程的程序计数器值加载到CPU中，以便执行新进程的代码。

就绪队列与等待队列

等待队列休眠结束后可以发出中断让CPU响应执行

其余时间CPU可以放心只对就绪队列进行执行

优先级就绪队列的设计

维护BitMap快速定位存在且优先级最高的任务

为高优先级的进程分配更加多的时间片，尽可能保障高优先级的任务先执行

active与expired队列

如果高优先级的进程分多个时间片也没有执行完，其将导致低优先级的进程饥饿

通过active与expired队列可以避免：高优先级的进程执行完一轮时间片之后将任务转移到expired队列，这个时候active队列中低优先级的进程就可以拿到时间片了

其中active与expired队列转换过程中为了避免拷贝，其实拷贝仅仅就是改变了个指针

调度算法

衡量标准：

1. 平均周转时间
2. 平均等待时间

等待时间 = 周转时间 - 运行时间

周转时间 = 完成时间 - 到达时间

==饥饿是进程或者作业长期得不到服务而产生的一种状态==

先来先服务

先来先服务，类似于排队结账，不保证吞吐量，执行完一个完整的进程再周转

• 优点：实现简易
• 缺点：在长作业或长进程后面的短作业或短进程需要等待很长的时间，对长作业有利，对短作业不利

最短时间优先

对已到达的进程找到耗时最短的执行，执行完一个完整的进程再周转

• 优点：有较短的平均等待时间和平均周转时间；
• 缺点：不太公平，对短作业有利，对长作业不利，可能产生饥饿现象，此外，作业或者进程的运行时间是由用户提供的，并不一定真实，所以不一定能做到真正的短作业优先。

最高响应比

在每次调度的时候选择一个等待时间最长的作业或进程为其服务，但是没有考虑到作业的运行时间，因此导致了对短作业不友好的问题。

• 优点：较高响应比
• 缺点：对短作业不友好

.png)

时间片轮转

按照各个进程到达就绪队列的顺序，轮流让各个进程执行一个时间片，若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队。

排队规则：每一个新的进程加入到队尾，如果当前进程时间片结束但是并未执行完会继续放置到队尾，如果此时有新的进程加入，新进程在前，该线程扔然在队尾

• 优点：优点是公平，响应快，且适合于分时操作系统，不会造成进程饥饿
• 缺点：缺点是由于高频率的进程切换，因此有一定的系统开销，同时也不区分任务的紧急程度

优先级调度

根据任务的紧急程度来决定处理顺序

• 优点：用优先级区分紧急程度、重要程度，适用于实时操作系统，可灵活地调整对各种作业或进程的偏好程度
• 缺点：若源源不断地有高优先级进程到来，则可能导致饥饿

多级反馈队列

用户态与内核态

内核：作为应用连接硬件设备的桥梁，应用程序只需关心与内核交互，不用关心硬件的细节

内核具有很高的权限，可以控制 cpu、内存、硬盘等硬件，而应用程序具有的权限很小，因此大多数操作系统，把内存分成了两个区域：

• 内核空间，这个内存空间只有内核程序可以访问；

• 用户空间，这个内存空间专门给应用程序使用；

• 用户态：应用程序默认的执行模式，只能访问有限的系统资源，当用户态希望访问部分操作系统资源将会切换到内核态，执行完后切换回来

• 内核态：能够操作所有系统资源，负责管理硬件资源、内存、进程调度等；例如网络通信底层是用到了内核态

Linux设计

• MultiTask：多任务（任务可以并行并发执行）
• SMP：对称多处理，多个CPU访问同一个内存，其权限都是相同的
• ELF：可执行文件链接格式
• Monolithic Kernel：宏内核