https://github.com/0voice/linux_kernel_wiki/tree/main?tab=readme-ov-file#5

boot

进入实模式（直接访问物理内存），执行BIOS执行程序存储在ROM中。 BIOS -》 bootloader (协议为 GRUB 2 or ……) -》保护模式 -》操作系统

GDT（Global Descriptor Table，全局描述符表）（所有进程的目录） IDT（Interrupt Descriptor Table，中断描述符表）

打开A20，意味着CPU可以进行32位寻址（而非实模式20位）

linux内核正式启动 创建0号进程：包括内存、页表、必要数据结构、信号、调度器、硬件设备等的初始化 -》启动：kernel_init内核线程和kthreadd内核线程（管理调度其他的内核线程的守护线程） -》1号进程：运行一个用户进程，并从此开始形成用户态进程树（pstree）（Fork-Exec 模型，这个模型将“创建进程”和“加载程序”变成两个步骤） -》2号进程：kthreadd，即2号进程，用于内核态线程的管理，是一个守护线程 （如果有需要create的内核线程，则create，否则睡觉）（新create的kthread在创建完后调用schedule()让出CPU资源，而不是直接运行）

I/O

cpu和设备的设备控制器交流，设备控制器内有三种控制寄存器，数据，命令，状态。还有数据缓冲区。 cpu如何读写数据：两种：1.分配I/O端口，用特殊汇编指令；2.映射到内存中 i/o设备通知cpu：中断 dma：cpu下达指令（告诉它想读取多少数据，读完的数据放在内存的某个地方就可以了）=》dma把I/o设备控制器数据存入内存 =》dma中断cpu

设备驱动程序：中断处理程序，（初始化时注册中断处理程序到中断描述符表里）  I/O 调度算法：fifo，Deadline（截止时间调度，适用于对延迟敏感的应用）

 linux 应用程序与io设备交换：内核将输入事件写入 /dev/input/eventX； 内核通过 /dev/fb0（或其他编号）设备文件将显存映射到文件系统 ## I/O设备数据传输 从disk读到网卡 一般方式：

sendfile+DMA收集 只能用于文件描述符到 Socket 描述符的传输

splice splice() 更通用，允许在任意两个文件描述符之间移动数据，但它要求其中一个描述符必须是 Pipe（管道）。  数据页的所有权（页的指针）从 内核缓冲区A 转移到 Pipe 转移到 内核缓冲区B（两次splice）   应用：Kafka：生产者写入：利用 mmap() 实现高效日志追加（消息日志文件映射到用户进程内存空间），消费者读取：利用 sendfile() 实现高效网络传输（消息日志文件disk到socket response）

调度算法

进程调度算法

FCFS，最短优先，高响应比优先调度算法（）

多级反馈队列：多个队列（每次消费最高优先级的），每个进程运行完一个时间片降低一个优先级 linux现有: 完全公平调度器 (Completely Fair Scheduler, CFS): 尝试让每个进程获得相等的CPU使用份额，每次运行已运行事件最小的进程。可以提高并设置进程优先级（进程运行时调用c语言的sched_setscheduler() or 命令行工具 chrt 需要sudo）。Linux对普通进程调度，提供了 完全公平调度算法，每次都会调vruntime最小的进程调度。用分子pruntime来照顾 睡眠情况，用分母来照顾nice值

NICE值：反映进程优先级，nice越小优先级越高，cpu分配比例越高 sched_latency_ns 预期延迟时间

量化指标：周转时间（run+wait），带权周转时间（run/(run+wait)）

linux 进程/线程调度

5态：就绪，睡眠/等待（锁，I/O……），运行，僵死

协程：线程切换成本太大，用户调度器（而非内核）控制

高低级分类

特性	作业调度 (高级)	中级调度 (中级)	进程调度 (低级/CPU)
调度对象	作业	进程 (挂起态)	进程 (就绪态)
任务	磁盘 \(\rightarrow\) 内存	外存 \(\leftrightarrow\) 内存	内存 \(\rightarrow\) CPU
频率	低	中	高
状态变化	无 \(\rightarrow\) 就绪	挂起 \(\leftrightarrow\) 就绪	就绪 \(\rightarrow\) 运行
备注	创建进程	交换 (Swapping)	最核心、最基本的调度

内存页面调度算法（缓存）

当虚拟内存大于物理内存时，页面放在内存还是磁盘。LRU选择最长时间没有被访问的页面进行置换

磁盘调度算法

fifo，Deadline（截止时间调度，适用于对延迟敏感的应用），scan（每次消费磁头移动方向上最近的，磁头到最后的磁道才调转方向）

内存访问流程图 MMU

TLB：VPN (Virtual Page Number) PFN (Page Frame Number) ## 进程同步

定义： 协调多个进程或线程的执行顺序，确保它们按照预定的顺序或条件进行操作

互斥：锁

信号量

初始化，P操作（-，消费，阻塞如果为负）和V操作（+，释放）。|信号量| =信号量<0 ? 阻塞的线程数 : 能消费的资源数

跨进程：通过文件系统路径名（通常在 /dev/shm 下）进行标识和访问。用字符串（例如/myshm进行表示）

生产者和消费者模型

1 sem_t empty;

2 sem_t full;

3 sem_t mutex;

4

5 void *producer(void *arg) {

6 int i;

7 for (i = 0; i < loops; i++) {

8 sem_wait(&empty); // line p1

9 sem_wait(&mutex); // line p1.5 (MOVED MUTEX HERE...)

10 put(i); // line p2

11 sem_post(&mutex); // line p2.5 (... AND HERE)

12 sem_post(&full); // line p3

13 }

14 }

15

16 void *consumer(void *arg) {

17 int i;

18 for (i = 0; i < loops; i++) {

19 sem_wait(&full); // line c1

20 sem_wait(&mutex); // line c1.5 (MOVED MUTEX HERE...)

21 int tmp = get(); // line c2

22 sem_post(&mutex); // line c2.5 (... AND HERE)

23 sem_post(&empty); // line c3

24 printf("%d\n", tmp);

25 }

26 }

27

28 int main(int argc, char *argv[]) {

29 // ...

30 sem_init(&empty, 0, MAX); // MAX buffers are empty to begin with...

31 sem_init(&full, 0, 0); // ... and 0 are full

32 sem_init(&mutex, 0, 1); // mutex=1 because it is a lock

33 // ...

34 }

锁的实现原理

原子指令 Compare-and-Swap :CAS(address,expected_value,new_value)

if (*p == v1) *p = v2;

自旋锁

互斥锁和信号量：内部维护一个状态变量（表示锁是否被占用或可用资源数）和一个等待队列（Wait Queue）

条件变量

pthread_cond_wait，pthread_cond_signal（唤醒一个），pthread_cond_broadcast。

Lost Wakeup

在条件变量写法中，保护读条件->lock，要防止Lost Wakeup： wait时自动unlock绑定的锁，唤醒时lock。因为检查条件和进入阻塞必须是原子的，而这通过绑定 释放互斥锁 和 进入阻塞 来实现。

如果不是原子操作，想象一下以下场景：

1. Goroutine A 检查条件，发现不满足，决定等待。
2. Goroutine A 释放互斥锁。
3. （此时，另一个 Goroutine B 获得了锁，改变了状态，并发送了信号。）
4. Goroutine A 随后进入阻塞状态。

cond.L.Lock()
for check { // 一定用while
    cond.Wait()
}

生产者和消费者

full和empty不能用同一个变量，因为： 2个消费者 wait 1个生产者 run 唤醒一个消费者 消费者Arun 错误唤醒消费者B

rwlock

struct rwlock {
	int readers;
	sem_t write_lock; // 写锁。如果多个读者运行，则在第一个读者开始时lock此锁，在最后一个读者完成时unlock即可
	sem_t lock; // 保护上面两个的原子性
}

mmap

用户把一个文件描述符映射到一片虚拟内存中，对此内存进行读写会直接对 内核空间/其他用户内存 进行读写，然后操作系统对硬件进行读写。用于I/O优化->零拷贝，共享内存->IPC

IPC 进程通信

内核把 用户A内存 转到 内核 再转到 用户B内存 ### 管道 创建特殊的管道文件，对其正常read/write

int pipe(int fd[2]) // 返回两个文件描述符

一个很小的缓冲区（内核） 生产者消费者模型，一个生产一个消费

POSIX 消息队列

多个生产多个消费，有优先级而不是先进先出 /dev/mqueue/name

共享内存

tmpfs：内存中的文件系统 不同进程fd指向同一个tmpfs inode指向同一个内存（内核态） 用户用mmap把自己的内存映射到这个fd上

信号量

命名信号量用于进程间通信，存储在内核内存空间中 其实也是共享内存

Socket及后端底层原理

Socket ：传输层，tcp 本地地址（ip+端口），外部地址（可能没有），状态，pid 1. 创建socket（也是文件，返回fd）并bind到某个端口， 开始监听 listen() 2. accept() 阻塞直到有消息（有客户端请求连接），返回一个新的socket（连接socket） 3. 创建线程/协程，处理此连接

改进：每个连接创建一个线程开销太大 -> i/o多路复用 /
/
select -> epoll
一个go routine I/O阻塞 -> 挂起 -> 注册到epoll中（一两个专门的Net Poller线程用于等待和调度） -> epoll发现某个事件就绪 -> 唤醒对应的goroutine

OS复习

多道程序：（脱机）批处理系统，没有时间分片， 非抢断，多个程序在内存 分时。用dma防止主cpu参与I/O

信号量 P- V+

PCB

CAS

缓冲区=最小单位：同步：1/(一个资源在A的时间+一个资源在B的时间) >: 并行 min(效率A，效率B)

信号量实现XX 1. 定义共享变量 2. 信号量初值 3. 创建线程，cobegin P1();P2(); coend 4. 定义线程

kstack 每个进程的内核栈

哲学家进餐：圆桌拿两边筷子

银行家算法：动态预测，避免死锁，本质是预测未来会获取的最多的所有资源，如果未来想要获取的资源现在不够 -> 不安全 无环->树->有一个不依赖别人的->拓扑排序 if available > need : available += allocated

磁盘调度：SSTFShortest Seek Time First，SCAN电梯。注意0和MAX没有直接相通

状态变迁图中变迁2→5是否发生是指：有没有什么情况一个进程发生2变迁，然后另一个进程发生5变迁。

优先级与时间片轮转相结合的调度算法：如果高优先级就绪，抢占低优先级直接运行 or 与其他高优先级进行轮转。

分区放置策略（before 分页）： 首次匹配，最佳匹配（最小的），最坏匹配 空闲区队列：大小+下一个空闲块的地址（从前到后，从大到小，从小到大）

分级页表：顶级表项尽量小

答案不要用 2^x，用xxMB，十六进制表示

段页式：进程里面每个段一个页表（仅x86） > 在段页式系统中，逻辑地址由三部分组成： [ = ( S, P, W) ] >地址转换步骤： >1. 查段表：根据段号 \(S\) 找到对应的段表项。段表项中不再直接给出物理地址，而是给出该段的页表起始地址和页表长度。 >2. 查页表：根据页号 \(P\) 在该段的页表中找到对应的物理块号（页框号）。 >3. 拼接地址：将物理块号与页内偏移量 \(W\) 拼接，得到最终的物理地址。 > >linux是全分页。

页号为0x7，偏移为0x2ad，一页大小为1kb。可得物理地址为：0x1EAD

近似LRU置换算法（先移动替换指针）：一个固定环。命中就把引用位=1，指针不变。每次替换遍历环，发现1就置为0，发现0就替换，调入的新页面为1，把指针指向下一个块。

打开文件：文件描述符。打开文件对象。内存中的inode。文件描述符在文件描述表里面找到系统打开文件表。

空闲磁盘块的管理。每一组的最后一块作为索引表，用来登记下一组100块的物理块号和块数

inode块大小 != 磁盘块大小。但是间接索引是一个磁盘块

1k/128=8

剥夺式/抢占式：I/O结束（高优先进程）时是否即刻调度

带权周转时间

证明不会发生死锁：死锁条件：sum(alloc) = 资源数；进程无限等待（获取的资源没有达到最大）

LRU的队列顺序和请求队列顺序相同 ### TODO 银行家题目

在某采用页式地址管理的分时系统中，一个应用程序试图访问某虚地址，然而此虚地址

对应的内容并未调入内存（即系统尚未建立此虚地址到实地址的映射）。试描述系统处理应

用程序对该虚地址访问的过程。

ostep文件修改部分

408