秋招面经笔记-操作系统&Linux串烧
进程、线程与协程
| 进程 | 线程 | 协程 | |
|---|---|---|---|
| 描述 | 资源分配的最小单位 | 操作系统调度的最小单位 | 用户态的轻量线程 |
| 切换对象 | 寄存器、内核栈、页表、文件描述符 | 寄存器，内核栈 | 寄存器，函数栈 |
| 切换者 | 操作系统 | 操作系统 | 用户 |
| 并发 | 单个CPU上通过切换实现并发，在不同的CPU上调度实现并行 | 单个进程内的线程并发执行 | 同时只能有一个协程运行 |
| 通信 | 依靠操作系统 | 读写进程数据段或堆栈 | 读写进程数据段或堆栈 |
- Linux线程：轻量级的进程，与进程同样以task_struct结构体的形式保存，线程栈的大小默认是8M，最大线程数一般受制于虚拟空间大小
- 线程回收：
- 等待线程结束（
pthread_join） - 直接结束线程（
pthread_exit），分离 - 让线程自己管理自己的资源（
pthread_detach）
- 等待线程结束（
- 进程的创建（
fork）：内部调用kernel_copy，简单来说是复制了当前的的任务结构体作为新的进程 - 进程的退出（
exit/_exit/exit_group）：_exit：立即进入内核，无条件终止进程exit：在_exit前会刷新所有流（清空缓冲），这也是为什么如果子进程（没有exec）调用了exit，父进程就无法使用文件，Linux中，_exit实际上是exit_group的封装
- 进程调度的简单过程：用户态 -> 中断 -> 内核态 -> 替换
task_struct-> 设置页表、文件描述符等资源 -> 切换栈 -> 中断 -> 用户态 - 进程调度算法：
- 先来先服务（FCFS）
- 短作业优先（SJF，不能实现）
- 最短剩余时间优先（SRTN，不能实现）
- 时间片轮转（RR）抢占式
- 优先级调度
- 多级反馈队列：按照不同的时间片（优先级，比如第一级8ms，第二级16ms，etc.）分组任务，如果任务在当前队列没有执行完成，就被移动到下一级队列，只有上一级队列没有人在排队，下一级才会被调度
- CFS：记录每个进程的运行时间（
vruntime），总是选择vruntime最小的进程运行，优先级越高，vruntime增长速度越慢 - O(1)调度：从优先级队列的最高优先级中找到进程调度（FIFO）
- 进程通信：
- 管道（
pipe）：半双工（可能考虑父子进程都使用rw文件，但是一般来说，我觉得是单工）- 无名管道（内存文件）：父子进程之间使用
- 有名管道（FIFO文件，借助文件系统）：允许在没有亲缘关系的进程间使用
- 共享内存：由一个进程创建，但多个进程都可以访问，最快的方式，要与信号量配合使用（通知内存变化）
- 消息队列：由操作系统维护的消息链表
- 信号：通知进程某事发生，比如
SIGABRT、SIGTERM等 - 信号量：计数器，控制多个进程对共享资源的访问
- 套接字：利用网络进行进程间通信
- 管道（
- 进程状态：
- NEW：新建
- READY：可以被调度
- RUNNING：正在或即将运行
- WAITING：等待加入调度（IO或者等待其他进程）
- EXIT：退出
- Linux特殊进程：
- 守护进程：后台运行的，没有和终端相连的进程，创建守护进程要创建子进程，并退出父进程，在子进程中新建会话，再创建孙进程，子进程退出时，这个孙进程就是不属于原终端的进程了（还需要改变文件权限掩码、重置根目录等）。
- 孤儿进程：父进程先退出，子进程会由
init收养 - 僵尸进程：子进程退出，父进程没有等待，子进程一直等待父进程
wait，无法真正退出
- C/C++程序的编译到运行
- 预处理
- 编译（to asm）
- 汇编（to obj）
- 链接（to elf64）
- 静态链接就是把预编译好的目标文件一同链接
- 动态链接已经生成的二进制文件，链接时会检查符号，并设置GOT和PLT的结构
- 运行时，装载器（
ld-linux.so）解析二进制文件（elf64）加载到内存空间，动态库以文件映射的方式加载进入内存空间，动态修改GOT表，将变量符号安排到正确的内存地址，当外部函数调用到来时，PLT表跳转到GOT表对应位置，调用装载器初始化正确的函数地址，然后跳转到该函数（可以加快载入时间，延迟初始化）
- 同步原语
- 测试并设置（
test_and_set）：获取旧数值并设置新数值 - 比较并交换（
compare_and_swap）：比较数值是否符合预期，是则更新值，返回旧数值 - 总线锁：多CPU下，总线锁阻止其它CPU访问数据
- 缓存锁：通过缓存一致性协议保证CPU缓存中的数值都是相同的
- 测试并设置（
- 同步机制：
- 临界区（开关中断）
- 信号量
- 互斥（同时只能有一个访问）与同步（按照一定的制约顺序执行）
- 管程（利用条件变量）
- 典型的锁：
- 读写锁：多个读者可以同时读，同时只能有一个写者（有写者时不能有读者），写者优先级高于读者
- 互斥锁：同时只能有一人访问资源
- 条件变量：根据某个条件判断是否解除互斥，是互斥锁的补全（同步）
- 自旋锁：如果无法取得，则原地自旋（
while），直到能够进入，利用进程切换，会导致时间片浪费，适用于上锁时间短的情况 - RCU（内核同步）：在读者完成了对资源的读取后，写者就可以安全地修改资源，因此要确定这个所有读者均完成读取的“宽限期”。RCU使用前禁止抢占，在临界区内禁止调度，因为禁止调度，如果发生了调度，说明在某个CPU上，对该对象的读取已经完成，所有CPU均调度完成时，旧对象则没有任何引用了，此时可以安全覆盖旧对象。
- POSIX同步机制：
- POSIX信号量：进程/线程同步
- POSIX互斥锁，条件变量：线程同步
- 线程终端退出：
tty退出时会发送SIGHUP给命令行，命令行会捕捉该命令并转发给子进程，如果不做处理，进程会退出
内存管理
内存：一块高速的易失性存储，程序和数据需要加载到内存中才能被CPU读取和执行，（我认为其目的是充当硬盘和CPU之间的一层缓冲，加速程序（程序执行流和数据访问）的执行。假设没有内存，CPU在执行每条指令，获取任何数据前都需要先访问硬盘获取指令或者数据，其中的时间消耗是无法忍受的）
虚拟内存（页表实现）：多级页表为每个进程引入了超大的虚拟空间，让每个进程都能够使用完整的地址范围（间接提升了进程的可移植性，因为不需要固定编址）。同时，页表是分页对内存进行管理、其中的虚拟内存物理上不必相连，甚至不一定在物理内存中，可以通过缺页机制，仅当我们需要该页面时才将内存加载进入物理内存，达到使用有限的内存运行大内存程序
快表加持的地址转换：CPU给出逻辑地址，
MMU先查TLB是否有对应页号，如果有则直接组合物理地址，否则爬多级页表进行转换，并记录在快表中内存覆盖：把用户空间分为固定区和覆盖区，将活跃的部分放入固定区，其他部分按照调用关系分段，将即将要访问的放在覆盖区，其他放在外存，在需要调用前，将其换入覆盖区，替换原有段
内存交换（换入换出）：
- 换出：将处于等待（暂时不会运行的进程）换出到辅存，把内存空间腾出来
- 换入：把准备好竞争的进程从辅存移入内存
换页算法：
- 最佳置换法（OPT）：每次淘汰的页面是最长时间内不再访问的页面（不可能实现）
- 先进先出（FIFO）：最早进入的页面最早淘汰
- 最近最久未使用（LRU）：记录页面的自上次被访问以来所经历的时间，淘汰时，选择页面中时间最大的
- 时钟置换算法（CLOCK）：将页面链接为链表，置访问位,当要淘汰页面时遍历该表，如果未访问则换出，若访问过则清空访问位，继续检查下一个，如果没找到则进行第二轮扫描
- 改进时钟置换：添加访问位和修改位：第一轮遇到(0,0)换出；第二轮找(0,1)，访问置0；第三轮找(0,0)；第四轮找(0,1)
内部碎片和外部碎片：
- 内部碎片：分配器只能分配固定大小的内存，由于需求内存的大小不一致而产生的空间浪费
- 外部碎片：内存的申请和释放导致内存中出现小空闲区，无法被利用
内存空间（从高到低）：
区域 内容 内核 控制程序执行的操作系统功能 栈 环境变量、argv、argc、main函数的局部变量，其他函数的局部变量（向下增长） 闲置 栈的增长空间 共享内存 动态链接库、用户映射等 闲置 堆的增长空间 堆 需要申请的大内存空间（向上增长） 数据段 初始化数据，未初始化数据 代码段 静态链接库函数、其他程序函数、main函数、启动例程（crt0.o） glibc内存池（
ptmalloc）：ptmalloc以chunk组织内存- 每个进程都有一个
main_arena和若干个non_main_arena，采用环形链表管理，main_arena能够使用brk和mmap，non_main_arena只能使用mmap（那次申请64MB，切块交给用户），申请内存时，如果线程当前拥有一个arena，会从中进行分配，如果失败（被占用）则在链表中循环，如果没有空闲arena，则创建新的 - 使用
mmap申请的内存用完后直接还给操作系统 - 主分配区上，判断申请大小是否超过
DEFAULT_MMAP_THRESHOLD决定是否使用mmap,一般是128KB，小于这个值则使用sbrk - 返还的内存被记录在名为
bins的结构中：bins：长128的数组，每个元素都是一个双向链表unsorted_bin（bins[1]）：维护free释放的chunksmall_bins（bins[2,63]）：维护小于512字节的内存块，chunk大小为index * 8large_bins（bins[64,127]）：维护大于512字节的内存块，index越大，chunk大小相差越大fast_bins：不大于max_fast(128B)的chunk释放后，会被放到fast_bins中，当需要小内存时，他们会被优先分配，某个特定时候，fast_bins会尝试合并，并放入unsorted_bin中- 申请内存会先查找
fast_bins，再尝试从unsorted_bin中查找，如果chunk不能满足需求，则将其放入合适的bin中，否则切块交给用户
- 当
bins无法满足需求时，会在top_chunk中分配内存（堆最上面的空间），剩余的部分形成新的top_chunk mmaped_chunk是由mmap分配的chunk,它们用完后直接还给操作系统
中断
- 硬件中断：外部硬件与CPU和内核交互
- 上半中断：中断服务函数
- 下半中断：
- 软中断：编译期分配好，不可更改，最多有32个软中断，目前只有网络和SCSI直接使用软中断
tasklet：使用两类软中断HI_SOFTIRQ和TASKLET_SOFTIRQ，可以动态增减，同类tasklet不能并发执行- 工作队列：利用内核线程执行，可以睡眠和阻塞
- 软件中断：异常、系统调用