1. Linux 进程空间

（从上到下是从高地址到低地址）：

段名	描述
内核(kernel space)	…
栈 ↓	存放局部变量，函数参数和返回值
.mmap ↓	实现文件(设备)的映射，例如动态链接库
堆 ↑	存放动态分配的内存
.bss	未初始化的全局变量和（全局/局部）静态变量
.data	又分为.rdata（全局常量）和.wdata（已初始化的全局变量和已初始化的全局/局部静态变量）
.text	存放代码

.data段在编译时就已经分配好，在整个程序运行期间一直存在。

1.1. 为什么要分堆和栈？

栈上的变量的生命周期由进出栈自动管理，离开作用域时，自动析构、释放内存，但是不是所有的场景下都需要这种自动释放，当我们需要一块内存离开作用域函数后依然存在，则栈不能满足要求。

1.2. 静态变量放在哪里？

已经初始化的放在.wdata，未初始化的放在.bss

1.3. 局部常量放在哪里？

其实就是const修饰的局部变量，依然在栈端而非.rdata

1.4. 虚表放在哪里？

.rdata段即全局常量区
https://blog.csdn.net/chczy1/article/details/100521615

1.5. 内核栈？用户栈？

每个进程会有两个栈，一个用户栈，存在于用户空间，一个内核栈，存在于内核空间。当进程在用户空间运行时，cpu堆栈指针寄存器里面的内容是用户堆栈地址，使用用户栈；当进程在内核空间时，cpu堆栈指针寄存器里面的内容是内核栈空间地址，使用内核栈
https://blog.csdn.net/jasonLee_lijiaqi/article/details/80181501

1.6. 子线程的栈空间在父线程的什么位置？

【未证实的说法】在堆中开辟。此外，子线程的栈空间开辟后还会额外分配一定大小的区域，这个区域不可读不可写，访问即发生段错误，用来防止栈溢出。
http://www.360doc.com/content/16/0506/11/478627_556725732.shtml

2. MMAP

将一个文件（或设备）直接映射到进程的地址空间，进程可以通过指针操作此段内存，系统会自动将脏页写回，而不必手动调用read/write，当然也可以调用msync强制同步。mmap并不分配空间，只是单纯的地址映射，多个进程之间可以通过mmap同一个文件实现共享内存。
与传统的文件读取过程相比，mmap机制通过将用户进程空间直接映射到外存中的文件，从而略去了常规文件读取方式中，先把文件数据读取到内核的页缓存、而后再将数据从内核的页缓存拷贝到用户态进程空间的耗时操作，所以效率比常规的文件读取更高。
https://blog.51cto.com/u_15284125/2988714
https://blog.nowcoder.net/n/850befe7c86d446ab73c89c5f18d8dcb?from=nowcoder_improve

3. 内存管理

3.1. 虚拟内存机制

一种内存管理技术，逻辑上连续的内存是由许多物理内存上的并不连续的页组成，可以使得使得应用程序认为拥有连续的内存空间。
具有逻辑内存可以大于物理内存、安全（避免访问内核或者其他进程的内存）、可以共享内存等优点。

3.2. 段页式

段式内存管理将内存的进程空间按逻辑分为数个段（例如.data, .code），并对每个段建立到物理内存的映射关系。
页式内存管理无视逻辑段，将内存的按固定大小（一般是4KB）分为多个页，每个逻辑页与物理内存块进行映射。
段页式就是以上二者的结合，分段并在每个段内分页。

3.3. TLB

逻辑地址到物理地址的转换需要页表，页表在内存的内核空间中，每个进程的PCB包含了指向页表的指针。TLB(translation lookaside buffer)转译后备缓存，又称快表，是CPU中的一种缓存，缓存虚实地址映射，作为硬件缓存，查询速度比页表快很多；当TLB未命中，再查页表。

3.4. 缺页中断

内存进程空间中不是所有页都实际放在内存中。当访问到的逻辑页不在内存中时，需要进入缺页中断处理程序，操作系统根据页表中的外存地址找到对应页调入内存。

3.5. 页面置换算法

发生缺页中断时，若内存中没有闲置的物理页，必须选择一块调出内存进入外存。常见算法是FIFO（淘汰最早进入内存的页，现已很少用）和LRU（淘汰最久未被使用的页，常用，需要记录页的访问情况所以开销大，硬件实现比较复杂，而软件实现可以用双向链表+哈希，LC146）

3.6. 动态内存分配算法

一般用链表的方式管理空闲内存块。常用的分配方法有首次适应、最佳适应、最坏适应

3.7. 内存抖动

主要有两种可能的原因：

在一个循环中大量创建临时对象
页面置换算法不合理

4. 进程和线程的区别？

区别项	进程	线程
最小单位？	资源分配的最小单位	CPU调度的最小单位
私有资源	设备（文件），代码段，数据段，堆（这些都由下属线程共享）	栈，寄存器，PC，pid
开销	创建、切换开销大	创建、切换开销小
相互影响	进程崩了互相无影响	一个线程segfault，默认情况下异常处理程序会终止同一进程的其他线程

4.1. 如何理解进程的创建/切换开销更大？

进程有独立的进程空间，而线程都是共用主线程的进程空间。在创建/切换进程时，需要进行进程空间的切换，此时需要修改页表（页表修改后自然TLB也失效），此步骤存在开销，并且切换后由于TLB失效，运行速度会变慢。而线程切换不需要修改页表与TLB

5. 线程模型与协程

5.1. 线程模型：用户态线程和内核态线程

运行于用户态的线程本身是不能被OS内核感知的；内核调度的对象被称作内核调度实体(kernel scheduling entity, KSE)，又被称为内核级线程（Kernel-Level Thread, KLT）。用户态线程（User-Level Thread, ULT）和内核态线程之间的对应关系被称为线程模型。
最经典的线程模型方案是一对一线程模型，即KLT，在大部分编程语言的线程库中（包括linux pthread, C++11 std::thread, Java::lang::thread），用户态线程和内核态线程都是一对一的关系，例如std::thread只是对KSE的一层封装。在一对一的线程模型下，线程的创建、销毁、调度完全借助OS内核提供的线程功能，实现简单。此模式下线程运行在用户态，而调度和管理在内核态。不过也正是因为这个原因，线程量很大的场景下对OS性能有较大影响。
协程则是一种典型的多对一线程模型，即ULT，多个用户态线程（即协程）对应一个内核态线程，协程之间的切换由语言的协程库自行调度。ULT的运行和管理调度都在用户态。由于OS不能感知协程的存在，故存在一个协程阻塞后导致一个进程下的所有协程都阻塞的缺点。
此外，存在一种混合型线程模型。这种模型综合了上述两者的优点，为一个进程创建多个内核态线程，用户态线程则可以在运行时与不同的内核态进程进行映射。当某个内核级线程由于其对应的某个用户态线程阻塞而被调度暂停运行时，语言的线程库可以修改其中未阻塞的用户态线程，将他们与其他的内核态线程重新建立映射关系。这种调度机制很复杂，一个典型例子是go语言的运行时调度器。
https://www.jianshu.com/p/dca73cbb87a6
https://cloud.tencent.com/developer/article/1793593

5.2. 协程？

轻量的用户态线程（不像进程/线程可能有内核态），不是由CPU调度而是由用户程序在一个线程内自行调度。一个线程内的多个协程分时运行，是并发(concurrency)而不是并行(parrallel)。切换开销更低。OS不能感知协程存在，一个协程阻塞则OS会认为该线程阻塞而导致调度。

6. 进程通信的方式（IPC）

方式	描述
信号Singal	需要注册信号捕获函数。例如ctrl+C的硬件中断SIGINT，调试时的SIGTRAP
信号量Semaphore	PV操作。P：-1，若>=0则继续；否则阻塞等待；V：+1，若<= 0则将一个阻塞等待的进程唤醒为就绪态
匿名管道Pipe	半双工，在内存中存在，只能在有亲缘关系的进程间通信
命名管道FIFO	半双工，以文件的方式在文件系统中存在，可以在任意进程间通信
共享内存Shared Memory	可以配合信号量/互斥锁，当做临界区来使用。
消息队列Message Queue	消息类型可以定义，不像管道那样只能读字节流；也是因为可以定义，可以选择性接受消息，而不是管道那样全读取。
Socket通信	可以用于不同主机上的进程通信。RPC属于这一类

7. 线程通信的方式

专有方式：全局变量！共用所属进程的.rdata段
信号量、互斥锁。

8. 同步和互斥的概念

同步：多个进/线程按照一定的顺序执行
互斥：同一时刻只允许一个访问者访问某一资源

9. 进/线程同步的方式与其C++使用方式

原子变量：C++std::atomic 本博客上的介绍
互斥锁：C++std::mutex以及基于基础互斥锁开发的读写锁。
信号量：Linux / Windows API中的semaphore
条件变量：C++std::condition_variable，等待条件为真再被通知唤醒。
临界区：Windows Api中CRITICAL_SECTION，只能用于同一进程内的线程同步，是用户态的同步机制。

10. 生产者消费者模型

注意点：一个互斥锁用于控制缓冲区的写入和读出，两个信号量用于代表空闲缓冲区和待消费缓冲区的数量。

semaphore mutex=1; //临界区互斥信号量
semaphore empty=n;  //空闲缓冲区
semaphore full=0;  //缓冲区初始化为空
producer ()//生产者进程
{     
    while(1)
    {
        produce an item in nextp;  //生产数据
        P(empty);  //获取空缓冲区单元
        P(mutex);  //进入临界区.
        add nextp to buffer;  //将数据放入缓冲区
        V(mutex);  //离开临界区,释放互斥信号量
        V(full);  //满缓冲区数加1
    }
}
consumer () 
{  //消费者进程
    while(1)
    {
        P(full);  //获取满缓冲区单元
        P(mutex);  // 进入临界区
        remove an item from buffer;  //从缓冲区中取出数据
        V (mutex);  //离开临界区，释放互斥信号量
        V (empty) ;  //空缓冲区数加1
        consume the item;  //消费数据
    }
}

11. Linux PCB

11.1. 包含的内容

linux源码中结构体task_struct，其最重要的成员有：

进程号
进程状态：阻塞/运行等
资源清单：分配的文件（及设备）的fid
上下文数据：中断时将PC、寄存器、堆栈等数据存入此处，保护现场
页表指针

https://www.cnblogs.com/yungyu16/p/13024626.html

11.2. 存放的位置

内核空间

12. 进程的状态

运行、就绪、阻塞。

运行->就绪：分配的时间片用完
就绪->运行：CPU调度
运行->阻塞：等待资源分配
阻塞->就绪：得到分配的资源

13. 僵尸进程和孤儿进程

13.1. 定义

僵尸进程：子进程退出后，父进程未调用wait()或者waitpid()获取子进程信息，子进程的PCB未被释放，留在进程列表中占用进程号。
孤儿进程：父进程在子进程运行结束前就退出，会被init(pid=1)进程收养并在运行结束后释放资源。

13.2. 如何避免僵尸进程/孤儿进程

首先是尽可能不要忘记wait()和waitpid()。但是若未退出则wait()会阻塞，waitpid()则可以设置为立刻返回。
此外，可以使用一些技巧，例如二次fork：让子进程fork出孙进程，随后销毁子进程，这样孙进程变为孤儿进程，由init接管。
最后，还可以通过SIGCHILD通知内核对子进程的结束不关心，由内核回收。

14. 进程调度方式

先到先服务（First Come First Service, FCFS）：维护队列，队首执行
短作业优先（SJF）：选择预估运行时间最短的执行。容易导致长作业长期不被调度。
时间片轮转（RR）：维护队列，队首运行一个时间片后放入队尾。
优先级调度：从队列中选择优先级最高的执行。还有抢占式，更高优先级到来时直接终止当前时间片，执行该更高优先级的进程。

15. fork()

如果成功创建子进程，父进程返回子进程PID，子进程返回0；如果创建失败，返回-1。
fork()在创建子进程时，会使用写时复制(Copy On Write)策略。子进程在创建时需要复制父进程的.code、.data、堆栈和页表，但是这里并不是立刻复制物理页，而是暂时通过虚拟内存机制共享物理页。当其中一个进程对共享页进行写操作时，才会复制物理页，并且修改页表。

16. 死锁

16.1. 产生条件

死锁是两个或多个进程互相等待对方所持有的资源。发生条件是：1. 资源互斥，只能被一个访问者拥有；2. 占有且等待；3. 发生了循环等待；4. 不可抢占

16.2. 死锁判断

判断有向图中的环

16.3. 死锁处理

回退部分死锁进程；或抢占资源。

16.4. 避免方法

银行家算法，对进程分配资源前，检查两个方面：1. 剩余资源是否能够满足进程的需求；2.若分配，分配后的剩余资源是否可以使至少一个工作中的进程执行完毕。

17. IO模型和IO多路复用

17.1. Linux IO模型分类

IO模型	描述	适用场景
阻塞IO(Blocking IO)	调用`recvfrom`后阻塞，等待数据到达内核、并从内核拷贝到用户空间后返回	连接少且固定
非阻塞IO(Non-blocking IO)	调用`recvfrom`后，若内核未准备好数据，则立刻返回；若内核已准备好数据，则阻塞等待内核拷贝数据到用户空间
信号驱动IO	在用户态程序注册`SIGIO`信号处理函数，操作系统在数据到达内核缓冲区后以信号的方式通知用户，在信号处理函数中调用`recvfrom`将数据从内核拷贝到用户空间
IO多路复用(IO Multiplexing)	单个进程可以监听多个socket。分select, poll, epoll，机制有所不同，但是在内核拷贝数据到用户空间时都需要阻塞。	（NIO+IO多路复用）连接多且操作轻量级，例如聊天服务器。
异步IO(Asynchronous IO)	注册信号处理函数，完全不阻塞。操作系统完成到用户空间的数据拷贝后用信号方式通知进程处理。	连接多且操作重量级，例如相册服务器

17.2. IO多路复用

select
调用select后阻塞。select中包含一个文件描述符数组，最多1024个。select返回后还需要遍历这个数组判断哪些socket有数据，再调用recvfrom从内核拷贝数据到用户控件，此过程阻塞。
poll
解决了select的文件描述符数量上限问题，其他基本一致
epoll
epoll_create创建句柄，epoll_ctl向内核注册监听的端口，然后epoll_wait阻塞等待，返回后再recvfrom。epoll_wait只会返回就绪的文件描述符，故不需要遍历，效率更高

https://segmentfault.com/a/1190000003063859#articleHeader14
https://www.jianshu.com/p/5ab57182af89

18. 中断和异常

中断包括了异常。中断分为2类：

外中断
I/O完成中断，Ctrl+C硬件中断
异常
CPU运算时内部异常，例如越界、除0、缺页中断、调试时的特殊汇编代码INT3

19. 磁盘（移臂调度）调度算法

a. FCFS：按请求到达的顺序执行
b. 最短寻找时间优先：永远选择距离目前柱面最近的
c. 电梯调度算法：永远选择在当前移动方向上最近的，若当前方向上无新的请求，则反向。这种方法的响应性能可能不如最短寻找时间算法，但是其稳定性大大强于前者，很少出现“饿死”的现象
https://blog.csdn.net/juliefish/article/details/4766787

20. 文件系统极简描述

20.1. Ext2 / Ext3 文件系统

索引节点(index node, inode)存放文件类型、权限等元数据，并保存指向该文件的索引块或是物理磁盘块的指针。
对于很小的文件，不需要引入索引块，此时inode中直接存放磁盘块指针；而对于较大的文件，需要引入索引块。索引块里包含实际存放该文件的磁盘块指针，对于很大的文件则需要进行多级索引。
文件所占用的磁盘块是随机分布的，这样可以最大化利用文件删除后的碎片。

20.2. Ext4的重要改进

extents:
Ext2/3的索引机制在描述大文件时，需要引入多层索引，导致访问性能降低。Ext4引入了区块(extent)概念，是一个连续的物理块，可以一次性分配和寻址；且一个extent的大小可达128MB，显著高于磁盘块的4KB，故可以显著减少索引层数和个数。

https://zhuanlan.zhihu.com/p/183238194
https://zhuanlan.zhihu.com/p/44267768

21. 软硬链接

软链接: 相当于保存链接对象的绝对路径。软链接文件有自己的inode，故链接对象的inode引用计数不增加。
硬链接：与链接对象拥有同样的inode，此时该inode引用计数+1。

https://www.jianshu.com/p/dde6a01c4094

22. LINUX系统启动

开机硬件自检
加载BIOS
BIOS接管控制，确定启动设备，从中读取Boot Loader到主存
题外话：目前常用的BL GRUB2的全称是GRand Unified Bootloader,Version 2
Boot Loader接管控制，从磁盘读取内核到主存
内核接管控制，启动第一个用户进程init
https://cloud.tencent.com/developer/article/1114481

2022 年 10 月
一	二	三	四	五	六	日
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30
31