《Linux内核设计与实现》读书总结

2023-05-16

Linux内核设计与实现

进程管理

进程:处于执行器的程序,包含代码段,打开的文件,信号,内核内部数据,内存地址空间,多个线程,存放全局变量的数据段

线程:进程中活动的对象,内核调度的单位,包含独立程序计数器,进程栈,一组进程寄存器

Linux对进程与线程不做特殊的区分

进程描述符:task_struct的数据结构,位于内核双向循环链表的任务队列中;进程描述符包含:打开的文件,地址空间,信号,状态等

进程状态:创建,就绪,运行,阻塞,结束

进程上下文:一般程序在用户态运行,当执行系统调用或者中断,则陷入内核态,称内核“代表进行执行”,并处于进程上下文中。

进程家族树:进程有明显的继承关系,init为PID为1的进程,所有进程是它的后代。每个父进程与子进程都有相互指向的指针。父进程可以调用wait()等待子进程退出。

进程创建

  1. fork系统调用
    fork用来创建子进程,fork调用一次返回两次,有三种不同的返回值,在父进程中返回值为子进程的PID,子进程中返回值为0,如果出现错误fork返回一个负值,程序正是根据返回值的不同来判断当前是子进程还是父进程中,执行不同的代码。
    函数调用过程:操作系统会先创建一个进程描述块,然后把父进程的所有进程描述符的信息精确拷贝进来,和父进程一样(PID除外),代码段共享,数据段和堆栈段复制(复制采用copy_on_write技术),所有的寄存器全部精确拷贝,文件描述符精确拷贝,一旦子进程开始运行,则新旧进程的地址空间已经分开,两者独立运行,但是fork父、子进程执行顺序不确定。
    优点:子进程的执行独立于父进程,具有良好的并发性。缺点两者的通信需要有专门的通信机制,如pipe、fifo等。

  2. vfork系统调用
    vfork也是用来创建子进程,但是vfork创建的子进程完全运行在父进程的地址空间上,子进程对虚拟地址空间任何数据的修改都为父进程所见,没有独立空间,vfork子进程与父进程共享数据段。
    vfork创建子进程后,父进程会被阻塞,子进程先运行,父进程后运行,它调用exec或exit之后父进程才可能被调度运行,如果在调用这两个函数之前子进程依赖于父进程的进一步动作,则会导致死锁。
    优点:当创建子进程的目的仅仅是为了调用exec执行另一个程序时,子进程不会对父进程的地址空间有任何引用,因此,此时对地址空间的复制是多余的,通过vfork可以减少不必要的开销。

  3. exec函数族
    exec用被执行的程序替换调用它的程序,与fork相比,fork创建一个新的进程,产生一个新的PID,exec启动一个新的程序替换当前的进程PID不变。

线程创建:clone系统调用,clone可以有选择性的继承父进程的资源,可以向vfork一样和父进程共享一个虚存空间,从而使创造的是线程,也可以使创造出来的进程不是父子关系,而是兄弟关系。

进程终结:发生在exit()调用后,释放相关资源,释放进程描述符,置标志位,进入退出状态。若父进程退出子进程未退出,那么需要再寻找一个作为父进程

进程调度

进程调度:

  1. 进程调度主要负责决定将哪个进程投入运行,何时运行以及运行多长时间。
  2. 并发与并行:并发指一段时间内可同时处理多个任务,并行指可以同时运行多个任务。
  3. 抢占式与非强制式:抢占式为调度程序可以决定什么时候停止当前进程,开始运行下一个进程;非抢占式为进程只能自己主动停止运行。

Linux进程调度

  1. I/O消耗型与处理器消耗型:前者为磁盘,网络I/O等,后者为密集计算任务等。
  2. 两种优先级:nice值(范围-20到19)表示普通优先级,值越低优先级越高;实时优先级(范围0到99)代表实时任务的优先级,值越高优先级越高。
  3. 时间片:每个进程每次抢占狗能运行的时间。I/O消耗型尽量短,处理器消耗型尽量长。
  4. 调度要求:IO型尽量多运行,保证实时,但运行时间短;处理器型保证运行时间长即可。

Linux调度算法

  1. 调度器:选择优先级最高的调度器,然后由调度器选择进程进行调度。
  2. CFS公平调度算法:允许每个进程运行一段时间,循环轮转,选择运行最少的进程最为下一个运行进程。nice值不再直接计算时间片,而是计算所占时间的比例,可以确保给每个进程公平的处理器使用比。

Linux调度算法实现

  1. 时间记账:记录每个进程运行时间。
  2. 虚拟实时(vruntime):每次选择vruntime最小的进程;内核中,进程的虚拟运行时间是自进程诞生以来进行累加的,一次调度间隔的虚拟运行时间=实际运行时间*(NICE_0_LOAD/权重)
  3. 进程选择:为了快速找到vruntime最小的进程,内核中用红黑树实现当前进程队列,每次选择最左叶子。
  4. 调度器入口:选择优先级最高的调度类,进行调度。
  5. 睡眠与唤醒:运行队列,等待队列之间的相互转换。
  6. 用户抢占:发生条件,从系统调用返回用户空间时,从中断处理程序返回用户空间时。
  7. 内核抢占:中断程序正在执行,内核代码再一次具有可抢占型,内核显式调用schedule(),内核任务阻塞。

实时任务策略

  1. SCHED_FIFO:先入先出算法,不使用时间片,可以一直执行。
  2. SCHED_RR:带有时间片的SCHED_FIFO算法。

系统调用

内核通信

  1. 除了异常和中断外,用户进程通过系统调用与内核通信。
  2. 系统调用的优点:1.为用户提供硬件抽象,无需知道磁盘以及文件系统类型;2.保证系统稳定安全;3.进程都运行在虚拟系统中,提供公共接口用以进程调用
  3. 调用关系:调用printf() -> c库中printf() -> c库中write() -> write()系统调用。
  4. 用户进程只需了解系统调用API功能,无需关心如何实现。

系统调用介绍

  1. 系统调用号:每个系统调用都需要一个系统调用号,通过指明调用号来执行系统调用。
  2. 应用程序通过软中断来通知内核执行系统调用:通过引发异常切换到内核态处理异常。
  3. 进入内核态后通过eax寄存器传递给内核调用号,通过其他寄存器传递参数。

系统调用实现

  1. 原则:接口简洁,参数少,越通用越好。
  2. 参数验证:检查用户指针是否有效,是否在合法用户区,是否可读可写。
  3. 权限验证:capable()检查是否可以对指定资源操作。
  4. 将系统调用函数添加到系统调用表,赋予系统调用号。
  5. 在c库中定义宏,完成设计寄存器并进入内核的操作。
  6. 用户态程序调用函数,从而产生系统调用。

中断与中断处理

中断概念

  1. 设备向内核发送信号,处理器便中断自己当前的工作转而处理中断
  2. 异常与中断不同,需要与处理器时钟同步,称之为同步中断;而硬件产生的为异步中断。

中断处理程序

  1. 在响应中断时,内核会执行特定函数,该函数为中断处理程序,是设备驱动的一部分。
  2. 中断可能随时发生,要求中断服务程序简短快速。
  3. 中断处理程序分为上下半部,上半部运行时间短,不允许被抢占。主要完成对中断的应答和复位操作;下半部分执行具体工作,可以被抢占,主要完成拷贝等耗时操作。

注册编写中断处理程序

  1. 通过request_irq()注册,通过free_irq()注销
  2. 每个中断服务程序需要占有一个中断线,可以共享也可以独占,同一个中断线的程序不能被抢占。

中断处理过程

  1. 产生中断->中断控制器->处理器->中断内核->do_IRQ()->是否有中断处理程序->运行中断服务程序->返回中断代码
  2. 中断服务程序过程:禁止中断->遍历中断线上的每一个程序,看是哪一个设备产生的中断->执行中断服务->返回

中断的下半部工作

中断的下半部概念

  1. 中断分为两个部分,一部分为上半部中断处理程序,一部分为下半部处理程序
  2. 中断处理程序不能阻塞,对时间要求高,因此有些中断操作不能全部在中断处理程序中运行,需要推迟到下半部执行

原始下半部解决方案

  1. BH接口:静态创建的链表,只包含32个节点,执行时全局同步
  2. 任务队列:设置多个队列,根据某些情况选择某个队列执行
  3. 新的解决方案:软中断与tasklet,工作队列

软中断

  1. 软中断是下半部运行时刻的机制,是一组静态定义的下半部接口,可以在所有处理器上同时执行,即使两个类型相同也可以。
  2. 一个软中断不会抢占另一个软中断,唯一可以抢占软中断的是中断处理程序
  3. 软中断最多有32个,编译时被确定,保留给对时间要求最严格的下半部使用,例如网络和SCSI.
  4. 软中断执行时,允许相应中断,但自己不能休眠,每个处理器可以执行相同程序,数据全局共享,因此需要锁保护。

tasklet

  1. tasklet是利用软中断实现的一种机制,与软中断几乎相同,但是可以动态创建,不允许相同的tasklet同时运行
  2. 当前的软中断被触发即被运行,但是运行过程中再被触发的软中断,则由内核进程组ksoftirqd运行。

工作队列

  1. 工作队列可以完全被推迟,交给内核线程运行,并且允许睡眠或阻塞。
  2. 工作队列通过创建工作者线程(worker thread),来完成队列中的下半部任务;默认的工作者线程为events/n,可也动态创建,接受内核调度。

应该选择哪一种机制

  1. 选择软中断:需要速度最快,而且对共享数据不敏感,只用到单处理器变量
  2. 选择tasklet:需要速度,可以多处理器并发
  3. 选择任务队列:开销较大,需要阻塞

内核同步方法

同步介绍

  1. 多个进程访问和操作共享数据的代码段为临界区,有可能产生竞争
  2. 避免并发和防止竞争条件成为同步
  3. 加锁可以完成同步的任务

原子操作

  1. 原子操作是一组不可分割的指令
  2. 原子操作有针对整数的原子整数操作,64位原子操作,还有原子位操作

自旋锁

  1. 只能被一个线程持有,其他线程会不停得循环检查锁是否被释放。
  2. 自旋锁不可递归,可以使用在中断服务程序中,但是需要关中断,适合于短时间持有
  3. 读-写自旋锁:多个读者可以同时读,只有一个写者可以写

信号量

  1. 信号量是一种睡眠锁,当一个线程持有时,其他线程会被信号量放入等待队列睡眠,等信号量释放后才被唤醒
  2. 信号量只能在进程上下文中使用,适合于长时间持有,不能与自旋锁同时使用
  3. 计数信号量:初始可以指定使用者的数量,意味着多个线程可以同时持有。
  4. 读写信号量:与读些自旋锁相似,但是可以动态将写锁转换为读锁

互斥体

  1. 是一种可以睡眠的互斥锁,实际上是一种信号量,只能一个线程持有
  2. 上锁者必须解锁,不能递归,不能在中断中使用,可以调试,用以发现不遵守规范的锁使用者
  3. 只有在底层代码才使用信号量,其他尽量用互斥体

三者使用场景

需求建议加锁方法
低开销加锁优先自旋锁
短期锁定优先自旋锁
长期加锁优先互斥体
中断上下文加锁使用自旋锁
持有者需要睡眠使用互斥体

完成变量

  1. 一个任务完成可以唤醒等待的另一个任务
  2. 用以子进程结束通知父进程

BLK大内核锁

  1. 全局自旋锁,可睡眠,可递归
  2. 老版本使用

顺序锁

  1. 没有其他写者,写锁可以直接获得,并置位;读锁在读前后检测标志量是否被修改,未修改说明无写者,否则循环读取
  2. 适合写着少,读者多的情况

顺序与屏障

  1. 为了防止编译器对代码语句进行重排序优化,保证顺序执行。
  2. 读屏障:保证在读屏障之前的读操作不会再读屏障之后运行,写屏障同理。

定时器与时间管理

内核的时间概念

  1. 节拍:内核两次时钟中断的加个时间
  2. 墙上时间:内核通过时钟中断维护的实际时间
  3. 系统运行时间:自系统启动所经历的时间
  4. 系统定时器频率(HZ):每秒钟产生时钟中断的次数;低HZ(100):内核负载可能过重;高HZ(1000):内核运行效率更高,计时更精准
  5. jiffies:全局变量,用来记录字系统启动以来产生的节拍的总数,每次时钟中断都会改变该变量值

硬时钟与系统定时器

  1. 实时时钟(RTC)用来持久存放系统时间的设备,系统定时器(PIT)用来周期性触发中断机制
  2. 时钟中断处理程序:更新jiffies与墙上时间xtime,统计消耗的系统时间和用户时间,执行已经到期的动态定时器
  3. xtime为实际时间,存放自1970.1.1以来经历的时间,使用的是顺序锁。

定时器

  1. 在指定时间之后执行某些函数
  2. 内核保证不会提前运行定时器,但是可能延迟运行定时器,即到时间不一定会运行指定函数,而是等待调度
  3. 由时钟中断的下半部软中断触发定时器

延迟执行

  1. 忙等待:一直循环等待时钟节拍耗尽,或者在代码等待时调度其他任务,不能在中断中使用
  2. 短延时:要求延时的时间很精确,时间跨度很小,不使用jiffies,而是使用处理器频率
  3. schedule_timeout():让任务睡眠,等时间耗尽后被唤醒

内存管理

内存结构

  1. 页:32位一般为4K,struct_page代表系统的每个物理页
  2. 区:分为三种,包含ZONE_DMA:DMA使用的页;ZONE_NORMAL:正常寻址的页;ZONE_HIGHMEM:动态映射的页(超过896MB)

获得页

  1. 内核提供底层接口,获取空闲页
  2. alloc_pages获取页,free_pages释放页

kmalloc()

  1. kmalloc()与用户控件的malloc()类似,可以获得以字节为单位的内存,连续的物理地址
  2. gfp_mask标志包含三种修饰符,行为修饰符表示内核如何分配内存,区修饰符表示从哪个区分配内存,类型标志表示前两个修饰符的组合,简化操作
  3. 一般这几种修饰符类型最常用:DFP_ATOMIC:分配时不能睡眠,可在中断中使用;DFP_KERNEL:可以睡眠,在进程上下文运行;GFP_DMA:使用DMA内存

vmalloc()

  1. 分配连续的虚拟地址,映射之后的物理地址可能不连续
  2. vmalloc()在不得以才使用,为了获取大块的内存

slab层

  1. slab提供了空闲的链表保存以分配好的数据块,可以避免频繁请求内存
  2. 高速缓存组有若干个slab,每个slab保存着若干对象。
  3. 内核先从部分慢的slab中分配对象,若没有部分满的slab,则选择空的slab分配,若没有空的,则创建新的slab

栈上分配

  1. 进程栈与内核栈不共享,栈上保存局部变量以及函数调用信息
  2. 栈容量有限,因此采用动态分配比较合适

每个CPU数据分配

  1. 为每个cpu分配数据,可防止竞争的问题
  2. 只需要关闭内核抢占

如何选择分配函数

  1. 需要连续物理页,使用kmalloc()
  2. 对高位内存进行分配,使用alloc_pages()
  3. 需要大块虚拟内存页,使用vmalloc()
  4. 需要频繁创建与撤销大型数据结构,使用slab

虚拟文件系统

通用文件系统接口

  1. VFS提供了通用的文件系统的接口,无需考虑具体的文件系统以及实际物理介质。例如open(),write(),read()
  2. write()调用的过程:write()->sys_write()->文件系统的写方法->物理介质
  3. unix的四种文件系统抽象概念:文件,目录项,索引节点,安装点

VFS对象

  1. 包含四种主要对象:超级块对象,索引节点对象,目录项对象,文件对象。
  2. VFS将目录作为文件处理,且目录项不同于目录(此处存疑)

超级块对象

  1. 代表一个已安装的文件系统,存储文件系统的信息,存放于特定的磁盘扇区,在文件系统安装时,文件系统会读取超级快并填充到内存的超级块对象中
  2. 超级块操作函数执行文件系统和索引节点的底层操作

索引节点对象(inode)

  1. 代表一个具体文件,包含内个在操作文件或这目录时所需要的全部信息。
  2. 一个索引节点代表一个具体文件,但是只有在被访问时才会在内存被创建
  3. 操作函数包含create(),delete()等操作

目录项对象

  1. 代表一个目录项,是路径的一个组成部分,每个dentry代表路径中的一个特定部分
  2. 查找时需要进行字符串比对操作,耗时较多
  3. 目录项会缓存最近查询的目录,以便下次查询

文件对象

  1. 代表进程打开的文件,是已打开文件的内存表示,由open()创建,由close()撤销
  2. 具体的文件系统可对每一种操作做专门的实现,或者使用通用操作

其他数据结构

  1. 与文件系统相关的数据结构:描述特定文件系统类型,以及行为
  2. 与进程相关的数据结构:与进程当前打开的联系在一起

块I/O层

块设备

  1. 块设备是系统能够随机访问数据片的设备,例如磁盘
  2. 字符设备是只能按照字符流的方式被有序访问,例如键盘和串口
  3. 扇区是块设备中最小的寻址单元,常见512字节;块是文件系统的最小寻址单元,包含多个扇区
  4. 对一个块设备的操作,老版本有数据结构:缓冲区头,新版本有数据结构:bio结构体

缓冲区头

  1. 缓冲区头记录着内核处理设备块时的控制信息(比如块属于哪个设备,块对应哪个缓冲区)
  2. 缓冲区头的目的是为了表述磁盘块,和物理内存之间的映射关系。
  3. 缓冲区头很大且不易控制,仅能描述单个缓冲区,造成空间浪费

bio结构体

  1. bio结构体表示一次I/O操作,一次操作可能包含多个磁盘块,但是包含一个连续的内存缓冲区,以链表的形式组织块io操作
  2. bio是轻量级的结构体

IO调度程序

  1. 块设备请求会被保存在请求队列中
  2. 关于请求的调度,包含电梯调度,最终期限io调度,预测io调度,完全公正的排队io调度,空操作io调度

电梯调度

  1. 合并扇区相邻的两个操作
  2. 对请求按照一个磁头运行的方向进行有序排序
  3. 可能会因为某个区域的密集操作,导致某个请求饥饿等待

最终期限IO调度程序

  1. 写操作应用程序不会等待,读操作应用程序会阻塞等待,因此要防止读操作请求进入饥饿状态
  2. 设置每个操作的超时时间,设置三个等待队列:排序队列与电梯调度相同,写请求队列与读请求队列在快要超时时运行,其余时间运行排队队列的请求
  3. 吞吐量会降低

预测io调度

  1. 在最终期限io调度的基础上改进
  2. 在每个请求完成后等待一段时间,在这段等待时间内多运行几个请求
  3. 工作负荷较大的情况下效果不好

完全公正io调度

  1. 每个进程都有自己的请求队列,并排序
  2. 每次固定选择每个进程的前n个请求运行
  3. 保证了每个进程的请求都能被公平运行

空操作io调度

  1. 只进行临近扇区请求的合并操作,不进行任何排序和其他操作
  2. 适用于真正可以随机访问的设备比如闪存

进程地址空间

地址空间

  1. 进程地址空间指用户空间的进程内存的管理,由虚拟内存构成,进程只能访问有效内存之内的地址。
  2. 可被合法访问的内存地址称为内存区域,包含代码段,数据段,用户栈等
  3. 进程具有唯一的地址空间,共享地址空间的进程叫做线程

内存描述符

  1. mm_struct为内存描述符,包含进程的地址空间以及相关的全部信息,所有结构体通过双向链表连接
  2. mmap与mm_rb均为存储内存区域的对象,mmap为链表,mm_rb为红黑树,存储的数据相同,在不同场合使用不同的查询
  3. 内核线程没有自己的进程地址空间和内存描述符,只需要共用前一个进程的内存描述符

虚拟内存区域

  1. vm_area_struct(VMA)为虚拟内存结构体,描述了一个连续区间的内存范围。
  2. 控制着内存的访问权限,包含读、写、执行
  3. 由mmap与mm_rb组织而成。可通过一些函数对内存进行操作,例如查询,创建,删除等

页表

  1. 虚拟内存地址需要解析为实际内存地址才可以执行相关操作
  2. linux使用三级页表进行地址转换
  3. 通过写时拷贝共享页表,当页表修改时才会被拷贝到应有的位置

页高速缓存与页回写

缓存方式

  1. 短时间内集中访问同一片数据称作局部性原理
  2. 页高速缓存是有内存中的物理页组成,对应磁盘中的物理块
  3. 缓存方式包含写缓存与缓存回收

写缓存方式

  1. 不缓存任何写操作,直接写入磁盘
  2. 写操作更新缓存,同时写入磁盘
  3. 回写:写操作只写入缓存,而后再周期性回写到磁盘

缓存回收

  1. 当内存空间不足时,需要回收部分页来腾出空间
  2. 最近最少使用(LRU),每次回收最长未被使用的页,通过LRU链表实现,但是在文件只被访问一次的情况下效果差。
  3. 双链策略:维护两个链表,活跃链表与非活跃链表,活跃链表保存使用次数多的页,每次只回收废活跃链表的页

Linux页高速缓存

  1. address_space:linux页包含多种类型,不仅仅是文件,因此该结构体表示对一个页的管理以及io操作
  2. 查找时采用堆与radix结合的优先搜索树,加快搜索缓存页的时间
  3. address_space包含常用操作例如读页到缓存或者更新缓存数据

flusher线程

  1. flusher线程负责将脏页写回到磁盘
  2. 三种情况下会被触发:空闲内存低于阈值,脏页存在时长过长,当用户调用sync()和fsync()时
  3. flusher线程周期执行,同时有多个线程负责执行操作,每个线程绑定一个设备
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

《Linux内核设计与实现》读书总结 的相关文章

随机推荐