数据结构与算法|linux内核设计与实现操作系统|运维

一. linux内核简介 1. linux简介 1.1 unix的特点

unix很简洁，仅提供几百个系统调用，并有非常明确的设计目的
unix所有东西都当作文件对待，这种抽象使对数据和设备都通过一套相同的系统调用接口进行
内核用C语言编写，移植能力很强
进程创建迅速，独特的fork调用
提供了简洁但是稳定的进程间通讯原语

1.2 unix和linux

linux克隆unix，但不是unix
linux借鉴了unix很多的设计，并且实现了 unix的api
linux没有直接使用unix的源代码，但完整表达了unix的设计目标并保证编程接口一致

2. 操作系统和内核简介

内核一般包括：
- 中断服务程序：负责响应中断
- 调度程序：管理多进程，分配处理器时间
- 内存管理程序：管理内存空间
- 系统服务程序：包括网络，进程间通讯
应用程序通过系统调用和内核通讯来运行
应用程序通常调用库函数，库函数通过系统调用让内核带其完成各种任务
内核对硬件设备的管理：硬件想要通讯时，发送异步信号去打断内核，内核通过中断号查找处理程序
linux内核开发的特定
- 不能链接标准c函数库。c库太大了，会影响大小和效率。不过大部分常用的c函数在内核中都有实现
- 没有内存保护机制，要注意非法访问内存地址
- 不要轻易使用浮点数，要人工保存和恢复浮点寄存器
- 栈空间很小且固定。32为机器为8kb，64为16kb
- 内核很容易产生竞争条件，注意同步和并发
- 注意可移植性

二. 进程管理 1. 基本概念

unix系统的两大抽象对象：进程，文件。具体可参考另外三篇关于unix进程和文件的文章序列
进程是处于执行期的程序，linux通常也把进程叫做任务
进程包括：代码段，数据段，打开的文件，挂起的信号，地址空间，线程等
线程是进程中活动的执行对象
每个线程拥有独立的程序计数器，进程栈和一组进程寄存器
内核调度的对象是线程，而不是进程
linux的线程实现非常特别，并不特别区分线程和进程
进程提供两种虚拟机制：虚拟处理器和虚拟内存
同一个进程内的线程可以共享虚拟内存，但是有各自的虚拟处理器

2. 进程描述符及任务队列 2.1 基本概念

内核把进程存放在叫做任务队列的双向循环链表中
链表中每一项都是task_struct类型，称为进程描述符，包括一个进程的所有信息。路径：/include/linux/sched.h

2.2 进程描述符如何分配

linux通过slab分配其分配task_struct结构，这样能达到对象复用和缓存着色
通过预先分配和重复使用task_struct，避免动态分配和释放带来的性能损耗，这也是为什么创建进程快的原因
task_struct放在内核栈的尾端，为了让寄存器少的硬件体系只通过栈指针就能算出位置，避免使用额外寄存器存储
slab分配器在内核栈的尾部创建新的struct thread_info，内部的task指向实际的task_struct。thread_info位置：

2.3 进程描述符存放在哪

current宏可以查找当前正在运行进程的进程描述符
这个宏的具体实现根据各自硬件体系结构有所不同
x86体系，通过栈尾部的thread_info结构的task指针找到进程描述符
有的体系（IBM的RISC），分配一个专用的寄存器存放task_struct的地址

2.4 进程的状态

进程描述符的state字段描述了进程当前的状态，每个进程都处于五种状态的一种
- TASK_RUNNING：运行。进程是可执行的。
- TASK_INTERRUPTIBLE：可中断。进程被阻塞，等待被唤醒
- TASK_UNINTERRUPTIBLE：不可中断。收到信号不做任何响应。ps命令查看会显示D
- TASK_ZOMBIE：僵死。进程已经结束了，但是父进程还没有调用wait4系统调用
- TASK_STOPPED：停止。进程停止执行
状态变迁图
设置当前进程：set_task_state（task，state）或set_current_state

2.5 进程上下文

一般程序在用户空间执行，执行系统调用或触发异常时，进入内核空间，内核代表进程执行，并处于进程上下文中
系统调用和异常处理是内核明确定义的接口，对内核的所有访问也只能通过这些接口
linux进程有明显的继承关系，所有的进程都是pid为1的init进程的后代
系统中的每个进程必有一个父进程，每个进程可以拥有一个或多个子进程
进程间关系存放在进程描述符中。task_struct中的parent变量，指向一个task_struct，存放父进程地址。children变量是一个链表，指向所有的子进程

3. 进程创建 3.1 基本概念

unix进程创建分为：fork和exec两步
fork通过拷贝当前进程创建子进程。子进程和父进程仅有很少差异：pid，ppid，某些资源和统计量
exec负责读取可执行文件并载入地址空间开始运行

3.2 写时拷贝（COW）

传统的fork直接拷贝资源效率低下，linux使用写时拷贝（copy on write）技术提高效率
COW并不会复制整个地址空间，而是让父子进程以只读方式共享内存，数据的复制只有在写入时才进行

3.3 fork函数

linux通过clone()系统调用实现fork(), 这个调用通过参数标识（很多种类型）指明需要共享的资源
clone内部调用do_fork完成主要工作(kernel/fork.c)
do_fork内部调用copy_process，然后让进程运行
copy_process调用过程：
- 调用dup_task_struct为新进程创建内核栈，thread_info结构和task_struct，这些值与当前进程相同，此时描述符完全相同
- 检查系统拥有的进程数是否超过限制
- 将很多成员重置
- 设置状态为TASK_UNINTERRUPTIBLE保证不会被运行
- 调用copy_flags以更新task_struct的flags成员
- 调用get_pid获取新的pid
- 根据参数标识，拷贝或共享打开的文件，文件系统信息，信号处理函数，进程地址空间，命名空间等。一般情况下，这些资源是线程共享的
- 父子进程平分时间片
- 扫尾工作，并返回指向子进程的指针
新创建的进程被唤醒并让其投入运行，一般优先子进程首先执行

3.4 vfork函数

和fork功能相同，除了补考吧父进程的页表项
通过向clone系统调用传递一个特殊标志进行的
该函数的设计并不是很优良的

4. 线程在linux中的实现 4.1 liunx线程概述

一组线程共享进程内的内存地址空间，打开的文件和其他资源
线程机制支持并发程序设计技术，多处理器上保证真正的并行处理
linux实现线程的机制非常独特，从内核角度看，没有线程的概念
linux把所有线程都当做进程来实现，内核没有特别的调度算法或数据结构来表征线程，被视为一个使用某些共享资源的进程
每个线程有自己的task_struct，就像一个普通的进程，这个进程和其他进程共享某些资源
与其他系统（windows，solaris）实现差异巨大，这些系统内核专门提供线程的支持

4.2 linux线程创建

线程的创建和普通进程创建类型，只不过调用clone时需要传递一些参数标志，指明需要共享的资源
参数标志说明：
- CLONE_VM：父子进程共享地址空间
- CLONE_SIGHAND：父子进程共享信号处理函数
- CLONE_THREAD：父子进程放入相同线程组
- CLONE_FS：父子进程共享文件系统信息
- CLONE_FILES：共享打开的文件 ...

4.3 内核线程

内核线程：独立运行在内核空间的标准进程
和普通进程的区别：没有独立的地址空间，只能在内核空间运行
创建只能由其他内核线程创建，函数为kernel_thread

4.4 进程终结
释放资源

进程终结时，内核必须释放它所占有的资源，并通知父进程
结束可以是正常，异常，还可以注册终止清理函数，详见另一篇文章：关于unix进程和文件的文章序列
最终结束会调用do_exit（kenel/exit.c），完成的工作包括：
- 将task_struct的标志成员设置为PF_EXITING
- 如果进程会计功能开启，会调用acct_process输出统计信息
- 调用_exit_mm函数放弃进程占用的mm_struct，如果没有被共享就彻底释放
- 调用sem_exit。如果排队等待IPC信号，则离开队列
- 调用__exit_files:递减文件描述符；__exit_fs:递减文件系统数据；exit_namespace：名字空间引用计数；exit_sighand：信号处理函数引用计数，如果某个降为0，则可释放
- task_struct的exit_code设置退出代码
- 调用exit_notify向进程发送信号，父进程修改为其他线程或init进程，进程状态设置为TASK_ZOMBLE（僵死，不被调度）
- 最后，调用schedule切换到其他进程
调用完do_exit，与进程相关的所有资源都被释放了，它所占有的资源只剩报错thread_info的内核栈和保存task_struct的那一小片slab，存在的唯一目的就是向父进程提供信息。

删除进程描述符

调用do_exit之后，线程僵死，但是还保留文件描述符
父进程获取到子进程的信息后，子进程的task_sturct结构才被释放
wait函数调用系统函数wait4实现，将挂起调用它的进程，直到其中一个子进程退出，函数返回子进程的pid
当最终需要释放进程描述符时，release_task会被调用，执行以下工作：
- 调用free_uid减少该进程拥有者的进程使用计数
- 调用unhash_process从pidhash上删除该进程，同时从task_list删除该进程
- 如果进程正在被ptrace跟踪，将跟踪父进程重置
- 最后，调用put_task_struct释放内核栈和thread_info结构所占的页，并释放task_struct所占的slab高速缓存
- 这时资源和描述符就全部被释放掉了

孤儿进程的处理

父进程如果在子进程之前退出，必须找到新的父亲，否则永远僵死
寻找父亲的函数在do_exit中调用的notify_present函数，内部调用forget_original_parent，该函数实现具体寻找过程
该函数设置父亲为线程组内的其他进程，没有就用init进程

三. 进程调度 1. 概述

调度程序是内核组成部分，它负责选择下一个要运行的进程
调度程序负责给可运行进程分配处理器时间资源
多任务系统可分为：抢占式任务（linux等现代操作系统的方式）和非抢占式任务
分配给每个进程的执行时间叫做时间片

2. 调度策略 2.1 cpu密集型和IO密集型

cpu密集型：大部分时间执行代码
IO密集型：大部分时间提交io和等待io，经常可运行，但运行时间极短
从系统响应速度考虑，linux调度策略更倾向于优先调度IO密集型进程

2.2 进程优先级

调度算法中最基本的一类：基于优先级调度，根据进程的价值和其对处理器时间的需求分级的思想
调度程序总是选择时间片未用完且优先级最高的进程运行
linux实现了一种基于动态优先级的调度算法。一开始设置基本优先级，然后根据需要动态加，减优先级：如果一个进程IO等待时间多余运行时间，它属于IO密集型，会提高优先级；相反，如果进程时间片一下就别耗尽，属于cpu密集型，会降低优先级
linux提供两组独立的优先级范围：
- nice值：-20～19，默认为0。标准优先级范围。值越大，优先级越低，时间片越短。task_struct的static_prio字段表示
- 实时优先级：0～99

2.3 时间片

表明进程在被抢占之前能持续运行的时间
调度策略必须规定默认时间片。如果过长，交互式的响应表现欠佳；如果过短，会明显增大进程切换带来的处理器耗时
很多系统默认时间片很短：20ms
linux提供动态调整优先级和时间片长度的机制，使得调度性能稳定且强健
进程不一定要一次用完时间片，可分多次使用，尽可能长时间保证可运行

2.4 进程抢占

当一个进程处于TASK_RUNNING状态，内核会检查它的优先级是否高于正在运行的进程，满足的话调度程序被唤醒重新选择进程运行
当一个进程的时间片为0，它会被抢占，调度程序可以选择新的进程执行

3. 调度算法 3.1 概述

linux调度程序定义与kernel/sched.c
2.5版本内核重写调度算法，和以前版本区别很大，实现以下目标
- 充分实现O（1）调度，不管多少进程或什么输入，每个算法能在恒定时间内完成
- 每个处理器拥有自己的锁和自己的可执行队列
- 尽量将同一组任务分配给同一个cpu连续执行，减少在cpu间移动进程
- 加强交互性能，即使系统负载，也保证系统响应
- 保证公平。消除饥饿线程，减少大量时间片进程

3.2 可执行队列

可执行队列数据结构为kernel/sched.c文件下的runqueue
表示给定处理器上的可执行进程链表，每个处理器一个
可执行队列是调度程序核心的数据结构，提供很多宏获取该指针
- cpu_rq（processor）：返回给定处理器可执行队列指针
- this_rq：当前处理器可执行队列指针
- task_rq：给定任务所在队列指针
对队列进行操作时，需要锁住队列，加锁函数
- task_rq_lock
- task_rq_unlock
- this_rq_lock
- this_rq_unlock
- double_rq_lock
- double_rq_unlock

3.3 优先级数组

每个可执行队列都有两个优先级数组，一个活跃的和一个过期的
数据结构为kernel/sched.c文件下的prio_array
能提供O(1)级算法复杂度的数据结构
优先级数组使可运行处理器的每一种优先级都包含一个相应的队列，该队列包含该优先级上可执行进程链表
优先级数组还拥有一个优先级位图，帮助高效查询最高优先级可执行进程
MAX_PRIO：系统拥有的优先级个数，默认140
BITMAP_SISE：优先级位图数组大小，unsigned long为32位，要表示140个优先级，需要5个长整形，总共160位
每个优先级数组都要包含一个位图成员。开始时，所有位图为0，当某个优先级进程开始执行，相应位图变为1，查找最高优先级就变为查找位图为1的第一个值，查找时间恒定。函数为sched_find_first_bit
要查找给定优先级任务，并轮询时，只需要遍历某个优先级链表即可
nr_active表示优先级数组内可执行进程数目

3.4 重新计算时间片

当所有线程时间片用完时，老版本linux采用循环遍历计算的方式重新计算时间片
新版本调度程序通过维护两个优先级数组：活动数组和过期数组，过期时间耗尽的线程放入过期数组，异步计算过期数组的时间片。最后只需要交换两个数组即可

3.5 计算优先级和时间片
动态计算优先级

静态优先级由用户指定后就不可更改，即前面介绍的nice值
动态优先级根据静态优先级和进程交互性函数关系计算而来
effective_prio函数返回一个进程的动态优先级：该函数以nice值为基数，再根据交互程度加上奖惩值（-5～5）
交换程度判断：计算进程执行时间和休眠时间。task_struct的sleep_avg变量，默认为10ms，休眠时增加该值（休眠时长），运行时减少该值

动态计算时间片

进程创建时，父子进程平分时间片。防止创建多个进程以抢占更多cpu时间
任务时间片用完时，根据任务的动态优先级计算时间片。函数为task_timeslice。时间值根据优先级值按比例缩放。最高200ms，最低10ms，默认为100ms
如果一个交互性很强的进程（TASK_INTER_ACTIVE宏），时间片用完后，会被再次放入活动数组而不是过期数组。避免出现需要交互却因为没有等到两个数组交换而执行不了。实现代码：scheduler_tick函数

3.6 睡眠和唤醒

处于休眠的线程进入等待队列，里面保存所有因等待某些事件发生的进程组成的简单链表
等待队列的数据结构为wake_queue_head_t
等待队列的创建：DECLEAR_WAITQUEUE或init_waitqueue_head
加入等待队列：add_wait_queue
与等待队列相关的事件发生时，队列的进程会被唤醒，使用wake_up函数

3.7 负载平衡程序

负载平衡程序针对多处理器系统中可执行程序负载不均衡的情况
函数为kernel/sched.c中的load_balance函数
调用时机：可执行队列为空时，定时调用（系统空闲时每隔1ms调用，其他情况每隔200ms调用）。单处理器不需要此函数。
负载平衡调用时需要锁定当前队列，并且屏蔽中断
load_balance操作步骤：
- 调用find_busiest_queue，找到最繁忙的队列。该队列进程数最多。如果没有超过当前队列25%的队列，直接结束返回
- 从繁忙队列中选择一个优先级数组用来抽取进程，最好是过期数组
- 寻址含有优先级最高（值最小）的链表，把高优先级的进程分散开
- 找到链表中没有在执行，且可移动，且不在高速缓存中的进程，靠用pull_task将进程抽取到当前队列
- 只要队列不平衡就执行以上步骤。最后释放锁。

4. 抢占和上下文切换 4.1 概述

上下文切换是从一个进程切换到另一个进程。
上下文切换定义在kernel/sched.c中的context_switch函数，该函数完成两项基本工作
- 调用定义在include/asm/menu_context.h中的switch_mm，负责把虚拟内存从上一个进程映射切换到新进程中
- 调用定义在include/asm/system.h中的switch_to，负责从上一个进程的处理器状态切换到新进程的处理器状态。包括保存，恢复栈信息和寄存器信息
内核提供need_resched标志表明是否需要重新调度。某个进程用尽时间片时，schedular_tick会设置该标志；当一个高优先级进程进入可执行状态时，try_to_wake_up也会设置该标志
每个进程都包含need_resched标志

4.2 用户抢占

用户抢占：内核返回用户空间时，如果need_reshed被设置，导致调用schedule，会选择一个更合适的进程执行的情况
用户抢占在以下情况时发生：
- 从系统调用返回用户空间
- 从中断处理程序返回用户空间

4.3 内核抢占

大部分Unix其他变体和大部分操作系统，不支持内核抢占，内核代码需要一直执行直到完成
2.6版本内核中，添加了内核抢占。只要重新调度是安全的，就可以内核抢占
只要没有持有锁，重新调度就是安全的，可以内核抢占
持有锁使用thread_info中的preempt_count计数器表示，使用锁时数值加一，释放锁时数值减一
内核抢占在以下情况时发生：
- 从中断处理程序返回内核空间时
- 当内核代码再一次具有可抢占性时
- 内核中的任务显示调用schedule
- 内核中的任务阻塞

5. 与调度相关的系统调用
【数据结构与算法|linux内核设计与实现】

sched_setscheduler：设置task_struct的policy和rt_priority值
sched_setaffinity：设置task_struct的cpus_allowed这个位掩码标志
sched_yield：将进程从活动队列移动到过期队列，以让出执行时间

四. 系统调用 1. 概述

系统调用提供内核和应用程序交互的接口
系统调用内部，函数声明中要添加asmlinkage，通知编译期仅从栈中提取函数参数
系统调用在内核中均以sys_作为前缀
linux中每个系统调用都和一个独一无二的系统调用号关联
内核记录系统调用表所有已注册过的系统调用列表，存储在sys_call——table中，以体系结构有关
linux内核设计优化简洁，上下文切换时间极快，操作系统执行效率高

2. 系统调用处理程序

用户程序不能直接调用内核函数，以防止内核空间安全失控。而是通过中断通知内核，让内核代表程序去执行
触发软中断前，将调用号装入eax寄存器
参数传递：在x86系统上，ebx、ecx、edx、esi、edi按照顺序存放前五个参数。返回值通过eax寄存器返回
内核空间和用户空间数据拷贝函数：copy_to_user，copy_from_user

3. 系统调用上下文

current指针指向引发当前调用的进程
执行系统调用时处于进程上下文
进程上下文中，内核可以休眠（调用阻塞或schedule）并可以被抢占

4. 系统调用的实现

linux不提倡多用途的系统调用，每个系统调用都应该有明确的用途
接口应该尽量简洁，参数少。力求稳定不做改动
尽量为将来做考虑，尽量通用，不要做限制。“提供机制而不是策略”
编写完后要注册到内核，成为真正可用的系统调用
- 在系统调用最好加入一个表项。大部分位于entry.s文件中。所有支持系统调用的硬件体系都要做
- 定义系统调用号到include/asm/unist.h文件中
- 函数放入kernel文件下某个位置，使之编译进内核映像（不能被编译称模块）
用户空间如何访问注册的系统调用
- 通常情况下，用户通过包含标准头文件，并和底层系统调用具体的c实现链接，就可以使用系统调用
- 自定义系统调用在标志头文件中不存在，可以通过linux提供的宏来调用：_syscalln,n代表需要传递的参数。该宏有2+2n个参数，第一个代表返回值类型，第二个代表函数名称，后续的是n个参数类型和参数名称
- 比如：open函数的系统调用，系统调用号为_NR_open,定义在中，内部被_syscall3宏实现，调用open时，内部把宏直接放入应用程序代码中

五. 中断和中断处理程序 1. 中断

中断用于解决计算机处理器与硬件设备处理速度不匹配的问题，硬件处理好任务后主动发送信号给处理器
中断本质是电信号，由硬件设备产生，送入中断处理器的输入引脚上。再由中断控制器向处理器发送信号。处理器收到信号就中断工作去处理中断
每个中断都有唯一都数字标识，称为中断请求（IRQ）线。比如：IRQ0是时钟中断，IRQ1是键盘中断

2. 中断处理程序

响应特定中断时，会执行的函数为中断处理程序或中断服务例程
中断处理程序是设备驱动程序的一部分，设备驱动程序是用于对设备进行管理的内核代码
与内核函数的区别：中断处理程序是被内核调用来响应中断的，运行与中断上下文中
中断处理程序必须能快速执行，同时，我们要靠它完成大量的其他工作。这两个目的是矛盾的。
为了解决上述矛盾，将中断处理程序切分为两个半部
- 上半部：接收到请求就立即执行，但执行少部分工作。中断应答和硬件复位
- 下半部：中断处理程序返回时立即执行

3. 注册中断处理程序

irq：要分配的中断号
handler：实际中断处理程序。接受三个参数，返回irqreturn_t类型参数
irqflags：可以为0，或以下标识的位掩码
- SA_INTERRUPT：表明是快速中断程序。主要用于时钟中断程序
- SA_SAMPLE_RANDOM
- SA_SHIRQ：共享中断线
devname：中断相关设备的Ascii文本名称，如键盘中段为“keyboard”
dev_id：用于共享中断线
该函数可能会休眠，不能在中断上下文或不允许阻塞的代码中调用

4. 中断处理机制

设备产生中断，把电信号发送给中断控制器
中断控制器把信号发给处理器
处理器中断程序，跳到内存中预定义的位置执行。就是中断程序入口点
内核调用do_IRQ，对中断进行应答
相关函数位于arch/i386/kernel/entry.s，arch/i386/kernel/irq.c

5 中断控制

linux提供一组接口用于操作机器上的中断状态，提供能够禁止中断系统或屏蔽中断线的功能
相关代码在, 中
中断控制的根源是提供同步，通过禁止中断，确保中断程序不会抢占当前代码，也可以禁止内核抢占
禁止和激活当前处理器中断：local_irq_disable，local_irq_enable
禁止（屏蔽）指定中断线： disable_irq，disable_irq_nosync，enable_irq，synchronize_irq
获取中断系统状态：asm/system.h中的irqs_disable
判断是否处于中断上下文中：asm/hardirq.h中的in_interrupt

六. 内核同步 1. 基本概念

临界区：访问和操作共享数据的代码段
竞争条件：多个执行线程处于同一个临界区
同步：避免并发和防止竞争条件
为什么需要同步：用户程序会被调度程序抢占和重新调度
造成并发的原因有：
- 中断
- 内核抢占
- 睡眠及用户空间的同步
- 多处理器
同步问题的解决：加锁
什么数据需要加锁
- 内核全局变量
- 共享数据
死锁；所有线程都在等待对方释放锁，任何线程都无法继续进行

2. 内核同步方法 2.1 原子操作

原子操作保证指令以原子方式执行
原子操作通常是内联函数，通过内嵌汇编指令完成
原子操作比其他同步方法给系统的开销小
linux内核提供对整数和单独对位进行的原子操作
整数原子操作相关函数为asm/atomic.h文件中
位原子操作相关函数为asm/bitops.h

2.2 自旋锁

自旋锁（spin lock）最多只能被一个可执行线程持有。如果锁未被占用，线程立刻可以得到。如果被占用，会一直循环等待锁可用。
自旋锁可用于防止多个线程同时进入临界区
自旋时特别浪费cpu，所以不应该被长时间持有
接口定义在,具体与体系结构相关的实现在
linux中自旋锁不可用递归
自旋锁的使用
spinlock_t mr_lock = SPIN_LOCK_UNLOCKED; //普通请求锁 spin_lock(&mr_lock); //禁止中断请求锁 spin_lock_irqsave(&mr_lock); //确保中断是激活的情况可用的方法 spin_lock_irq(&mr_lock) /**临界区**/ spin_unlock_irq(&mr_lock) spin_unlock_irqrestore(&mr_lock); spin_unlock(&mr_lock) 复制代码
自旋锁可以用在中断处理程序中（信号量不行，会导致休眠）,在使用锁之前，要禁止本地中断，否则会导致死锁

2.3 读写自旋锁

锁用途可以明确分为读锁和写锁。
一个或多个读任务可以并发的持有读者锁
用于写的锁只能被一个写任务持有，且此时不能并发读
读写锁使用
rwlock_t mr_rwlock = RW_LOCK_UNLOCKED; read_lock(&mr_rwlock); /**只读临界区**/ read_unlock(&mr_rwlock)write_lock(&mr_rwlock) /**读写临界区**/ write_unlock(&mr_rwlock) 复制代码
不能把读锁升级为写锁，会导致死锁

2.4 信号量

信号量是一种睡眠锁
同一时刻允许任意数量的锁持有者
信号量数量为1时，称为二值信号量或互斥信号量
如果一个任务试图获取被占用的信号量，信号量会将其推入等待队列，让其睡眠。当持有信号量的进程释放后，等待的任务被唤醒，获得信号量
信号量的特点
- 适合锁会被长时间持有的情况
- 锁被短时间持有，睡眠耗时可能比全部时间还长
- 会睡眠，不能在中断中调用
- 占有信号量时不能占用自旋锁。自旋锁不允许休眠
信号量支持两个原子操作P和V，荷兰语的探查和增加
信号量相关文件：
使用信号量
//声明信号量 static DECLARE_SEMAPHORE_GENERIC(name, count); //声明互斥量 static DECLARE_MUTET(name); //以指针方式初始化信号量 sema_init(sem, count); //以指针方式初始化互斥量 init_MUTET(sem); //试图获得信号量 down_interruptible(&name) //释放信号量 up(&name) 复制代码

2.5 读写信号量

与读写锁一样
相关文件：

2.6 完全变量

提供代替信号量的简单解决方法
相关文件：

2.7 Seq锁

提供一种简单的机制，用于读写共享数据
内部实现主要一个序列计数器
锁的初始化为0，写数据时，会得到锁，且序列值增加。读数据之前和之后，序列号被读取，如果相同则没有被打断，如果为偶数则没有写操作发生

2.8 屏障

屏障（barriers）可以确保指令顺序执行，禁止指令重排序
重排序是因为现代处理器为了优化其传送管道，打乱了分派和提交指令的顺序
rmb方法提供“读”内存屏障，rmb前面的载入操作不会排在rmb之后，反之亦然
wmb方法提供“写”内存屏障，wmb前面的存储操作不会排在wmb之后。
mb方法提供了“读写”屏障

七. 内存管理 1. 内核对内存的管理 1.1 页

内核把物理页作为内存管理的基本单元。
内存管理单元：MMU，管理内存，并把虚拟地址转换为物理地址的硬件
页大小跟体系结构不同而不同，大多数32为体系支持4KB的页，64位体系支持8KB的页
物理页的数据结构位于中的struct page。page与物理页相关，而不是虚拟页
sturct page{ unsigned longflags; // 页的状态，是否脏，是否被锁定。可表示32种状态。定义与 atomic_tcount; // 页的引用计数，被使用了多少次。为0时，新的分配就可以使用它 struct list_headlist; struct address_space*mapping; //指向与该页有关的address_space对象 unsigned longindex; struct list_headlru; union{ struct pte_chain *chain; pte_addr_tdirect; }pte; unsigned longprivate; void*virtual; //页虚拟地址，虚拟内存地址 } 复制代码

1.2 区

由于硬件限制，有些页位于内存中特定的物理地址上，不能用于特定的任务，所以把也划分为不同的区（zones）。
区对有相似特性的页进行分组。区的划分没有任何物理意义，仅仅是为了管理页采取的逻辑分组
linux使用三种区：
- ZONE_DMA：能执行DMA（直接内存访问）的区
- ZONE_NORMAL：能正常映射的区
- ZONE_HIGHEM：不能永久映射到内核地址空间的“高端内存”
区的数据结构位于的struct zone

2. 页相关接口

内核提供了一种请求内存的底层机制，提供了访问接口，接口都以页为端午分配内存，定义与中
// 分配2^order个连续的物理页，并返回指针 struct page* alloc_pages(unsigned int gfp_mask, unsigned int order) // 将页转换为逻辑地址,页是连续的，其他页紧随其后 unsigned long __get_free_pages(unsigned int gfp_mask, unsigned int order)// 只获取一页，高端地址分配需要使用此函数 struct page* alloc_page(unsigned int gfp_mask) unsigned long get_free_page(unsigned int gfp_mask)//获取填充内容为0的页 unsigned long get_zeroed_page(unsigned int gfp_mask)//释放页 void __free_pages(struct page *page, unsigned int order) void free_pages(unsigned long addr, unsigned int order) void free_page(unsigned int order)// 与用户空间的malloc函数类似，最通用的接口。提供用于获得以字节为单位的一块内核内存 // 定义与中 void *kmalloc(size_t siez, int flags) // kmalloc相反函数，释放空间 void kfree(const void *ptr)// 确保分配的页在物理地址上是连续的 // 定义与 void* vmalloc(unsigned long size) //释放空间 void vfree(void *addr) 复制代码
gfp_mask标志，在
中，分为三类：行为修饰符，区修饰符和类型
- 行为修饰符：内核如何分配所需的内存
- 区修饰符：从哪儿分配内存
- 类型：组合了行为修饰符和区修饰符

3. slab

slab提供通用数据结构缓存层的角色，slab会给每个处理器维持一个对象告诉缓存（空闲链表）
适用于需要创建和销毁很大的数据结构
slab层把不同的对象划分为所谓告诉缓存组，每个告诉缓存都存放不同类型的对象（每种对象类型对应一个高速缓存）
每个slab处于三种状态之一：慢，部分或空
多个salb组成一个高速缓存，各种数据结构：
- slab的：struct slab
- 高速缓存：kmem_cache_s
- 满链表：slabs_full
- 部分链表：slabs_partial
- 空链表：slabs_empty

4. 高端内存的映射

高端内存的页不能永久映射到内核地址空间中，所以某种标志获得的页不可能有逻辑地址
x86系统上，高端内存中的页被映射到3GB-4GB的逻辑地址
映射相关接口：
//映射一个给定的page结构到内核地址空间： void kmap(sturct page *page)//解除映射关系 void kunmap(struct page* page)//临时映射 void *kmap_atomic(sturct page *page, enum km_type type) 复制代码

八. 虚拟文件系统 1. 基本概念

虚拟文件系统：VFS，提供文件系统接口。通过VFS，可以利用标准的unix文件系统调用堆不同介质的不同文件进行操作
linux支持相当多的文件系统（超过50种）：
- 本地文件系统： ext2, ext3
- 网络文件系统：NFS，Coda
VFS中有四个主要的对象类型
- 超级快对象，代表一个已安装文件系统
- 索引节点对象，代表一个文件
- 目录项对象，代表一个目录项
- 文件对象，代表由进程打开的文件

2. 超级块对象

各种文件系统都必须实现超级块，该对象用于存储特定文件系统的信息，通常对应于存放在磁盘特定扇区中的文件系统控制块
超级块数据结构定义与中的super_block。
超级块中的s_op指向超级快的操作函数表，由super_operation结构体表示。文件系统对超级块操作时，会找到相应的操作方法
也就是不同的文件系统的信息，通过往super_operation中注册自己的针对文件系统操作的方法，提供给VFS使用
超级快相关代码位于中

3. 索引节点对象

索引节点对象包含了内核在操作文件或目录时需要的全部信息
索引节点对象数据结构位于中的struct inode
代表了文件系统中的一个文件（包括普通文件，管道等等）
索引节点中的inode_operations项也非常重要，定义了操作索引节点对象的所有方法

4. 目录项对象

目录项包括执行目录相关的操作，比如路径名查找等
目录项数据结构位于中的struct dentry
目录项状态包括：被使用，未被使用和负状态
目录项还包括目录项缓存，包括：
- 被使用的目录项链表
- 最近被使用的双向链表
- 哈希表和相应的哈希函数用来快速将给定路径解析为相关目录项对象
目录项操作定义在dentry_operation结构体中，位于

5. 文件对象

文件对象定义与中的struct file结构体
文件操作由file_operations结构体表示
具体的文件系统定义不同的实现

6. 其他数据结构

与文件系统相关的数据结构：struct file_system_type，描述特定文件系统类型，如ext3或XFS
安装文件系统的实例：vfsmount，
进程描述符的files指向的数据，包含进程相关的打开的文件及文件描述符的等信息：struct files_struct，
进程描述符的fs指向的数据，包含文件系统和进程信息：struct fs_struct,
进程描述符的namespace指向的数据，包含命名空间信息：struct namespace,

九. 块IO层 1. 基本概念

基本设备类型包括：块设备，字符设备。区别在于是否可以被随机访问
块设备中最小的可寻址单元是扇区，扇区大小一般是2的整数倍，最常见的大小是512字节
物理磁盘按扇区寻址，文件系统按块进行访问，块是较高层次的抽象
块包含一个或多个扇区，但大小不超过一页
块调入内存时，需要先加载到缓冲区，每个缓冲区与一个块对应
每个缓冲区有一个描述符，用buffer_head结构表示，称为缓冲区头。在文件中。包括缓冲区状态，使用计数，逻辑块号，物理页，块大小等信息

2. bio

目前内核中块IO操作基本容器由bio结构表示，位于

3. io调度程序十. 进程地址空间 1. 基本概念

每个进程都有唯一的地址空间，彼此之间互不干扰
进程只能访问有效范围内的内存地址
内存区域包含各种内存对象，包括：
- 代码段：可执行文件代码的内存映射
- 数据段：已初始化全局变量的内存映射
- BSS段：未初始化全局变量
- 其他

2. 内存描述符

内核使用内存描述符表示进程的地址空间
内存描述符数据结构位于中的mm_struct
内部的mmap和mm_rb两个数据结构表示的内容一样，此处做了冗余。前者为链表，便于高效遍历所有；后者为红黑树，便于高效搜索
锁都有的mm_struct都通过自身的mmlist链接在一个双向链表中，首元素的init进程，init_mm描述符。操作链表时，要用mmlist_lock加锁，锁位于
进程描述符中的mm字段存放内存描述符
分配内存描述符：copy_mm，内部调用allocate_mm宏从mm_cachep slab缓存分配
内核线程没有进程地址空间，mm字段为空

3. 内存区域

内存区域由vm_area_struct表示，定义在中，也称虚拟内存区域
vm_area_struct描述了指定地址空间内连续空间上的一个独立内存范围
vma包括很多标志位，标志了所含页面的行为和信息
- VM_READ：页面读权限
- VM_WRITE：页面写权限
- VM_EXEC：页面可执行权限
vm_area_struct结构体的vm_ops指向与指定内存区域相关的操作函数表，由vm_operations_struct表示

十一. 页高速缓存和页回写 1. 基本概念

页高速缓存是linux实现的一种磁盘缓存，主要用来减少对磁盘的io操作
通过把磁盘中的数据缓存到物理内存中，把对磁盘的访问变为对物理内存的访问
磁盘高速缓存的意义：
- 加快访问速度，内存速度大于磁盘
- 临时局部原理：数据一旦被访问，很有可能在短期内再次被访问
执行io操作前，内核会检查数据是否已经在页高速缓存中，如果在就可以立马返回

2. 页高速缓存数据结构

页高速缓存使用address_space结构体描述页高速缓存中的页面，定义与中
内部的a_ops指向地址空间对象中的操作函数表，由address_space_operations结构体表示
检查页是否在高速缓存中操作必须高效，每个address_struct提供的基树（radix tree），page_tree的二叉树，记录了文件偏移量。以达到快速检索的目的。基树代码在

3. 页回写