读书笔记 十一月 4, 2016 chaossss No comments

《Linux内核设计与实现》笔记

进程管理

进程

进程:处于执行期的程序(目标码存放在某种存储介质上),但不仅仅局限于一段可执行的程序代码。通常还包含其他资源:

1. 打开的文件
2. 挂起的信号
3. 内核内部数据
4. 处理器状态
5. 一个或多个具有内存映射的内存地址空间及一个或多个执行线程
6. 用来存放全局变量的数据段等
7. ……

实际上进程就是正在执行的程序代码的实时结果。

执行线程

执行线程即线程,是在进程中活动的对象。每个线程拥有一个独立的程序计数器、进程栈和一组进程寄存器。内核的调度对象是线程,但Linux系统的线程实现很特别:它对线程和进程没有特别的区分,线程只不过是一种特别的进程。

进程描述符及任务结构

Linux内核将进程的列表存放在被称为任务队列的双向链表中,表项类型为task_struct,即进程描述符,该结构包含具体进程的所有信息。

分配进程描述符

Linux通过slab分配器分配task_struct结构,这样能达到对象服用和缓存着色的目的。

通过预先分配和重复使用task_struct,可以避免动态分配和释放所带来的资源消耗

slab分配器

slab分配器的基础是:在内核中,为有限的对象集分配大量内存,因为内核中普通对象进行初始化所需的时间超过了对其进行分配和释放所需的时间,因此,不应该将内存释放回一个全局的内存池,而是将内存保持为针对特定目的而初始化的状态。例如:内存被分配给一个互斥锁,那么只需在互斥锁首次分配内存时执行一次互斥锁初始化函数即可,后续的内存分配不需要执行这个初始化函数,因为上次释放和调用析构之后,它已经处于所需的状态中了。

上图是slab的高层组织结构,cache_chain是slab缓存的链接列表,可以用来查找最适合所需要的分配大小的缓存。每一块缓存kmem_cache包含一个slabs列表,这是一段连续的内存块(通常是页),列表中存在三种slab:

1. slabs_full – 完全分配
2. slabs_partial – 部分分配
3. slabs_empty – 空

其中slabs_empty是进行回收的主要备选对象,回收slab的内存返回给OS的其他用户使用。此外,slab也是一个连续的内存块(一个或多个连续页),它们被划分为一个个对象,这些对象就是从特定缓存中进行分配和释放的基本元素。

slab是slab分配器进行操作的最小分配单位,通常slab被分配为多个对象。

由于对象是在slab中进行分配和释放的,因此单个slab可以在slabs列表间移动。

优点:

1. slab缓存分配器通过对类似大小的对象进行缓存避免了常见的碎片问题
2. slab分配器支持通用对象的初始化,从而避免了为同一目的而对一个对象重复进行初始化
3. slab分配器支持硬件缓存对齐和着色,允许不同缓存中的对象占用相同的缓存行,从而提高缓存利用率

进程描述符的存放

内核通过唯一的进程标识值或PID标识进程,PID的最大值代表系统中允许同时存在的进程的最大数目。

进程状态

– TASK_RUNNING(运行)——进程是可执行的;它或者正在执行,或者在运行队列中等待执行。这是进程在用户空间中执行的唯一可能的状态
– TASK_INTERRUPTIBLE(可中断)——进程正在睡眠(阻塞),等待某些条件的达成。当条件被达成,内核就会将进程状态设为运行,处于此状态的进程也会因为接收到信号而提前被唤醒并随时准备投入执行
– TASK_UNINTERRUPTIBLE(不可中断)——除了就算是接收到信号也不会被唤醒或准备投入运行外,这个状态和可中断状态相同。这个状态通常在进程必须在等待时不受干扰或等待事件很快就会发生时出现。由于此状态的任务对信号不做响应,所以用的较少。
– TASK_TRACED——被其他进程跟踪的进程
– TASK_STOPPED(停止)——进程停止执行。进程没有投入运行也不能投入运行,通常这种状态发生在接收到SIGSTOP、SIGTSTP、SIGTTIN、SIGTTOU等信号的时候。此外,在调试期间接收到任何信号,都会使进程进入这种状态。

进程创建

Linux的进程创建分解到fork()和exec()两个函数中单独执行,fork()通过拷贝当前进程创建子进程,exec()读取可执行文件并将它载入地址空间开始运行。

写时拷贝

传统的fork()直接将所有资源复制给新创建的进程,这种实现过于简单且效率低,因为拷贝的数据也许是不共享的,此外,如果新进程打算立即执行一个新的映像,那么所有的拷贝都将前功尽弃。因此Linux使用了写时拷贝技术:这是一种可以推迟甚至免除拷贝数据的技术,因为内核先让父子进程共享同一个拷贝,只有在需要写入的时候数据才会被复制,使得各个进程拥有各自的拷贝。实际开销就是复制父进程的页表以及给子进程创建唯一的进程描述符。

Linux线程

Linux内核没有准备特别的调度算法或定义特别的数据结构来表征线程,相反,线程仅仅被视为一个与其他进程共享某些资源的进程。每个线程都拥有唯一隶属于自己的task_struct,但线程和其他进程共享某些资源,如地址空间。

在其他系统中,线程被抽象为耗费较少资源,运行迅速的执行单元。在Linux中,线程只是一种进程间共享资源的手段。

进程调度

多任务

多任务系统可分为:

– 非抢占式多任务
– 抢占式多任务(Linux)

抢占式多任务模式由调度程序来决定什么时候停止一个进程的运行,以便其他进程能够得到执行机会。该强制的挂起动作叫抢占。进程在被抢占之前能够运行的时间是预先设置好的,叫进程的时间片,即:分配给每个可运行进程的处理器时间段。

策略

策略决定调度程序在何时让什么进程运行,调度器的策略往往就决定系统的整体印象,并且,还要负责优化使用处理器时间。

I/O消耗型和处理器消耗型的进程

进程可分为I/O消耗型和处理器消耗型,前者指进程的大部分时间用来提交/等待I/O请求,这样的进程经常处于可运行状态,但通常都是运行短短的一会儿,因为它总会因为等待I/O请求阻塞。后者时间大多用在执行代码上,除非被抢占,否则通常都一直在运行,因为它们没有太多的I/O需求。但由于不属于I/O驱动类型,所以从系统响应速度考虑,调度器不应该经常让它们运行。对于这类进程,调度策略往往是尽量降低它们的调度频率,而延长其运行时间。

调度策略通常要在进程响应迅速(响应时间短)和最大系统利用率(高吞吐量)间寻找平衡。

进程优先级

Linux采用了两种不同 的优先级范围:

1. nice值,范围是:-20~19,默认为0,值越小优先级越高。相对而言,低nice值的进程可以获得更多的处理器时间。Linux中,nice值代表分配给进程的时间片的比例;但Mac OS X中,代表分配给进程的时间片的绝对值
2. 实时优先级,越高的实时优先级数值意味着越高的优先级,范围:0~99。实时优先级和nice优先级处于互不相交的两个范畴

时间片

时间片是表明进程在被抢占前所能持续运行的时间的数值,调度策略必须规定一个默认的时间片。

Linux调度算法

传统Unix系统的进程调度存在的问题

1. nice单位值对应到处理器的绝对时间,导致进程切换无法最优化进行。同优先级的进程获得相同的时间片,但都要进行进程切换,切换进程上下文需要的时间甚至比进程完成任务需要的时间要多的多。
2. nice值相差很小的进程(例如相差1)得到的时间片在nice值较大的时候区别明显
3. 要将nice值与时间片建立映射,则代表我们需要分配一个绝对时间片,而且这个绝对时间片必须能在内核的测试范围内,也就意味着在大多数操作系统中,时间片必须是定时器节拍的整数倍。那么最小时间片也必然是定时器节拍的整数倍;不同nice值对应的时间片的差值也是定时器节拍的倍数;时间片还会随定时器节拍改变。

公平调度(CFS)

CFS基于一个简单的理念:进程调度的效果应如同系统具备一个理想中的完美多任务处理器。在这种系统中,每个进程将能获得1/n的处理器时间——n指可运行进程的数量。同时,我们可以调度给它们无限小的时间周期,所以在任何可测量周期内,我们给予n个进程中每个进程同样多的运行时间。

CFS允许每个进程运行一段时间、循环轮转、选择运行最少的进程作为下一个运行进程,而不再采用分配给每个进程时间片的做法,CFS在所有科运行进程总数基础上计算出一个进程应该运行多久,而不是依靠nice值来计算时间片。nice值在CFS中成为进程获得的处理器运行比的权重:nice值越高(优先级越低)的进程获得更低的处理器使用权重,这是相对于默认nice值进程的进程而言的。

每个进程都按其权重在全部可运行进程中所占比例的“时间片”来运行,为了计算准确的时间片,CFS为完美多任务中的无限小调度周期的近似值设立了一个目标(目标延迟),越小的调度周期将带来越好的交互性,同时也越接近完美的多任务。但你必须承受更高的切换代价和更差的系统总吞吐能力。

为了保证进程运行时间低到不能接收切换开销,CFS引入每个进程获得的时间片底线(最小粒度)。

CFS在进程数量特别多的情况下,并不是完美的公平调度,因为此时处理器时间再小也无法突破最小粒度。

所以,CFS让任何进程索获得的处理器时间是由它自己和其他所有可运行进程nice值的相对差值决定的。任何nice值对应当绝对时间是处理器的使用比。CFS称为公平调度器是因为它确保给每个进程公平的处理器使用比。CFS不是完美的公平,它只是近乎完美的多任务,但它确实在多进程环境下,降低了调度延迟带来的不公平性。

Linux调度的实现

Linux调度有四个部分组成

时间记账

所有的调度器都必须对进程运行时间作记账,多数Unix系统分配一个时间片给每一个进程,当系统时钟节拍发生时,时间片都会被减少一个节拍周期。当进程时间片减少到0,就会被另一个时间片未减到0的可运行进程抢占。

CFS不再有时间片的概念,但也必须维护每个进程运行的时间记账,因为它需要确保每个进程只在公平分配给它的处理器时间内运行,CFS用struct_sched_entity(调度器实体结构)来追踪进程运行记账,调度器实体作为成员变量嵌入在进程描述符的结构中。

调度器实体结构的vruntime变量存放进程的虚拟运行时间,该运行时间的计算是经过了所有可运行进程总数的标准化(或者说是被加权的),以ns为单位,和定时器节拍不再相关。虚拟运行时间可以帮助我们逼近CFS模型所追求的“理想多任务处理器”。vruntime被用于记录一个程序到底运行了多长时间以及它还应该运行多久。

进程选择

CFS试图用一个简单的规则均衡进程的虚拟运行时间:当CFS需要选择下一个运行进程时,它会挑一个具有最小vruntime的进程。CFS用红黑树组织可运行进程队列,利用它迅速找到最小vruntime值的进程。进程选择将分为三个步骤:

假设:有一个红黑树存储了系统中所有的可运行进程,其树节点的键值便是可运行进程的虚拟运行时间。

1. 挑选下一个任务:CFS调度器选取待运行的下一个进程,被选取进程为所有进程中vruntime值最小的那个,即红黑树中最左侧的叶子节点,因此CFS的进程选择算法也可以表达为:运行红黑树中最左边叶子节点代表的进程。
2. 向树中加入进程:当进程变为可运行状态(被唤醒)或通过fork()调用第一次创建,通过enqueue_entity()函数规划化进程的vrumtime值并更新min_vruntime值,然后更新当前任务的运行时统计数据以及运行时间等统计数据,最后通过_enqueue_entity()函数插入红黑树并更新缓存。
3. 从树中删除进程:当进程堵塞(变为不可运行态)或终止(结束运行),同样会先更新进程的vrumtime值及相关的运行时统计数据,然后删除节点,更新缓存。

调度器入口

调度器入口是schedule(),它是内核其他部分用于调用进程调度器的入口:选择哪个进程可以运行,何时将其投入运行。schedule()通常都需要和一个具体的调度类相关联,即:它会找到一个最高优先级的调度类——该调度类需要有自己的可运行队列,然后schedule()问调度类谁才是下一个该运行的进程。

睡眠和唤醒

休眠(被阻塞)的进程处于一个特殊的不可执行状态,这一点非常重要,因为如果没有这种特殊的状态,调度程序可能选出一个本不愿意被执行的进程。更糟糕的是,休眠就必须以轮询的方式实现了。

进程休眠的原因各不相同,但本质都是:等待某些事件的发生。事件可能是:

1. 一段时间从文件I/O读取更多数据
2. 某个硬件事件
3. 尝试获取一个已被占用的内核信号量
4. …

但无论哪种情况,内核对进程的操作都是一样的:进程把自己标记成休眠状态,然后从可执行红黑树中移出,并放入等待队列,调用schedule()选择和执行一个其他进程。

唤醒进程则相反:进程被设为可执行状态,然后从等待队列中移到可执行红黑树中。

休眠有两种相关的进程状态:

– TASK_INTERRUPTIBLE:如果接收到一个信号,会被提前唤醒并响应该信号。
– TASK_UNINTERRUPTIBLE:忽略信号。

两种状态的休眠进程位于同一个等待队列中等待事件发生,不能运行。

等待队列

休眠通过等待队列进行处理,等待队列是由等待某些事件发生的进程组成的简单链表。进程将自己放入等待队列并设置成不可执行状态,当与等待队列相关的事件发生时,队列上的进程会被唤醒。为了避免产生竞争条件,休眠和唤醒的实现不能有纰漏。

进程将自己假如等待队列的步骤:

1. 调用宏DEFINE_WAIT()创建一个等待队列的项
2. 调用add_wait_queue()将自己加入队列,队列会再进程等待的条件被满足时唤醒它。当事件发生,对等待队列执行wake_up()操作
3. 调用prepare_to_wait()方法将进程的状态变更为TASK_INTERRUPTIBLE或TASK_UNINTERRUPTIBLE,如有必要,函数会将进程加回等待队列
4. 若进程状态为TASK_INTERRUPTIBLE,则进程由信号唤醒(由于进程不是因为事件的发生被唤醒,因此称为伪唤醒),进程会检查并处理信号
5. 当进程被唤醒,会再次检查条件是否为真,若是,则退出循环;否则将再次调用schedule()并重复这步操作
6. 当条件被满足,进程状态将设为TASK_RUNNING并调用finish_wait()将自己移出等待队列

如果在进程休眠之前条件就已经达成了,那么循环会退出,进程不会存在错误地进入休眠的倾向。

注意:内核代码在循环体内常常需要完成一些其他的任务,如:在调用schedule()之前需要释放锁,调用后在重新获取锁、响应其他事件等……

唤醒

系统调用wake_up()函数唤醒指定的等待队列上的所有进程。该函数调用try_to_wake_up()将进程设置为TASK_RUNNING状态,并调用enqueue_task()将进程放入红黑树中,如果被唤醒进程的优先级高于当前执行进程的优先级,还需要设置need_resched标志。

注意:通常哪段代码促使等待条件达成,它就要负责随后调用wake_up()函数。

注意:进程存在虚假的唤醒。有时候进程被唤醒并不是因为它所等待的条件达成了才需要用一个循环处理来保证它等待的条件真正达成,详见下图。

抢占和上下文切换

上下文切换:从一个可执行进程切换到另一个可执行进程。

每当一个新进程被选出来准备投入运行时,schedule()就会调用context_switch()函数,它完成了两项基本工作:

– 调用switch_mm()函数将虚拟内存从上一个进程映射切换到新进程中
– 调用switch_to()将上一个进程的处理器状态切换到新进程的处理器状态(保存、恢复栈信息和寄存器信息,还有其他任何与体系结构相关的状态信息,都必须以每个进程为对象进行管理和保存)

内核提供了need_resched标志来表明是否需要重新执行一次调度,此标志对于内核来说是一个信息,它表示有其他进程应当被运行了,要尽快调用调度程序,相关用法见下表:

当某个进程应该被抢占时,scheduler_tick()就会设置这个标志;当一个优先级高的进程进入可执行状态时,try_to_wake_up()也会设置这个标志,内核检查该标志,确认其被设置,调用schedule()来切换到新进程。

在返回用户空间以及从中断返回时,内核也会检查need_resched标志,如果已被设置,内核会在继续执行之前调用调度程序。

用户抢占

内核即将返回用户空间时,如果need_resched标志被设置,会导致schedule()被调用,此时就会发生用户抢占。在内核返回用户空间时,它知道自己是安全的,因为它既然可以继续去执行当前进程,那么它当然可以再去选择一个新的进程去执行。所以内核无论是在中断处理程序还是在系统调用后返回,都会检查need_resched标志。如果它被设置了,那么内核会选择一个其他(更合适的)进程投入运行。从中断处理程序或系统调用返回的返回路径都是跟体系结构相关的。

简而言之,用户抢占在以下情况发生:

– 从系统调用返回用户空间时
– 从中断处理程序返回用户空间时

内核抢占

在不支持内核抢占的内核中,内核代码可以一直执行,直到它完成为止,即:调度程序没有办法在一个内核级的任务正在执行的时候重新调度——内核中的各任务是以协作方式调度的,不具备抢占性。内核代码一直要执行到完成(返回用户空间)或明显的阻塞为止。

但Linux完整地支持内核抢占,只要重新调度是安全的,内核就可以在任何时间抢占正在执行的任务。

那么什么时候重新调度才是安全的?只要没有持有锁,内核就可以进行抢占。锁是非抢占区域的标志。由于内核是支持SMP的,所以,如果没有持有锁,正在执行的代码就是可重新导入的,也就是可以抢占的。

如果内核中的进程被阻塞了,或它显式地调用了schedule(),内核抢占也会显式地发生。内核抢占会发生在:

– 中断处理程序正在执行,且返回内核空间之前
– 内核代码再一次具有可抢占性的时候
– 如果内核中的任务显式地调用schedule()
– 如果内核中的任务阻塞(这会调用schedule())

实时调度策略

Linux提供了两种实时调度策略:

– SCHED_FIFO
– SCHED_RR

这两种实时算法实现的都是静态优先级,内核不会为实时进程计算动态优先级,这能保证给定优先级别的实时进程总能抢占优先级比它低的进程。

而SCHED_NORMAL则是普通的、非实时的调度策略。

SCHED_FIFO

SCHED_FIFO实现了一种简单的、先入先出的调度算法:它不使用时间片。处于可运行状态的SCHED_FIFO级的进程会比任何SCHED_NORMAL级的进程都先得到调度,一单一个SCHED_FIFO级进程处于可执行状态,就会一直执行,直到它自己受阻塞或显式地释放处理器为止。只有更高优先级的SCHED_FIFO或SCHED_RR任务才能抢占SCHED_FIFO任务。如果有两个相同优先级的SCHED_FIFO任务,他们会轮流执行,但依然只在它们愿意让出处理器时才会退出。只要有SCHED_FIFO级进程在执行,其他级别较低的进程就只能等待它变为不可运行态后才有机会执行。

SCHED_RR

SCHED_RR和SCHED_FIFO大体相同,只是SCHED_RR级的进程在好近事先分配给它的时间后就不能再继续执行了,也就是说,SCHED_RR是带有时间片的SCHED_FIFO——这是一种实时轮流调度算法。当SCHED_RR耗尽时间片,同优先级的其他实时进程被轮流调度,时间片指用来重新调度同一优先级的进程。对于SCHED_FIFO进程,高优先级总是立即抢占低优先级,但低优先级决不能抢占SCHED_RR任务,即使它的时间片耗尽。

Linux的实时调度算法提供了一种软实时工作方式,所谓软实时就是:内核调度进程,尽力使进程在它的限定时间到来前运行,但内核不保证总能满足这些进程的要求。相反,硬实时系统保证在一定条件下,可以满足任何调度的要求。

系统调用

与内核通信

系统调用在用户空间进程和硬件设备之间添加了一个中间层,该层的主要作用:

1. 为用户空间提供了一种硬件的抽象接口
2. 系统调用保证了系统的稳定和安全。作为硬件设备和应用程序之间的中间人,内核可以基于权限、用户类型和其他一些规则对需要进行的访问进行裁决
3. 每个进程都运行在虚拟系统中,而在用户空间和系统的其余部分提供这样一层公共接口,也是出于这种考虑。如果应用程序可以随意访问硬件而内核又对此一无所知的话,几乎就没法实现多任务和虚拟内存,当然也不可能实现良好的稳定性和安全性。在Linux中,系统调用是用户空间访问内核的唯一手段:除异常和陷入外,它们是内核唯一的合法入口。实际上,其他的像设备文件和/proc之类的方式,最终也还是要通过系统调用进行访问的。而有趣的是,Linux提供的系统调用却比大部分操作系统都少得多。

API、POSIX和C库

一般情况下,应用程序通过在用户空间实现的API而不是直接通过系统调用来编程。API定义了一组应用程序使用的编程接口,它们可以实现成一个系统调用,也可以通过多个系统调用来实现,也可以完全不使用任何系统调用。下图表示了POSIX、API、C库及系统调用之间的关系:

系统调用

访问系统调用通常通过C库中定义的函数调用来进行。

系统调用号

Linux中每个系统调用被赋予一个系统调用号,当用户空间的进程执行一个系统调用,系统调用号就可以指明要执行哪个系统调用(进程是不会提及系统调用名称的)。

注意:sys_ni_syscall()除了返回-ENOSYS外不做任何其他工作,这个错误号专门针对无效的系统调用而设。

系统调用的性能

Linux系统调用比其他操作系统执行要快的原因:

– 上下文切换的时间短
– 系统调用处理程序和每个系统调用本身非常简洁

系统调用处理程序

为了系统的安全性和稳定性,用户空间的程序无法直接执行内核代码,因为内核驻留在受保护的地址空间上。因此,应用程序要以某种方式通知系统(软中断——引发一个异常),告诉内核自己需要一个系统调用,希望系统切换到内核态,让内核代表应用程序在内核空间执行系统调用。

指定恰当的系统调用

切换到内核态还需要传入系统调用号才能得到准确的系统调用。

参数传递

将参数存放到寄存器中。

系统调用上下文

在进程上下文中,内核可以休眠并且可以被抢占,它们的意义在于:

– 能够休眠说明系统调用可以使用内核提供的绝大部分功能
– 在进程上下文中能够被抢占表明,像用户空间内的进程意义,当前的进程同样可以被其他进程抢占。因为新的进程可以使用相同的系统调用,所以必须小心,保证该系统调用是可重入的。

中断和中断处理

中断

中断本质上是一种电信号,由硬件设备发向处理器。处理器接收到中断后,会马上向操作系统反应此信号的到来,然后就由操作系统负责处理这些新到来的数据。硬件设备生成中断的时候并不考虑与处理器的时钟同步(随时可以发生中断)。

异常

异常与中断不同,异常产生时必须考虑与处理器时钟同步。实际上,异常也常常被称为同步中断。在处理器执行到由于编程失误而导致的错误指令时,或是在执行期间出现特殊情况,必须靠内核来处理时,处理器就会产生一个异常。

中断处理程序

中断处理程序:内核用于响应特定中断的函数。每个能产生中断的设备都有一个相应的中断处理程序,它是设备驱动程序的一部分。

中断处理函数与其他内核函数的真正区别在于:中断处理程序时被内核调用来响应中断的,而它们运行于我们称之为中断上下文的特殊上下文中。

注意:中断上下文偶尔也被称作原子上下文,该上下文中的执行代码不可阻塞。

上半部与下半部的对比

中断处理程序能切分为两部分:

– 上半部:接收到中断就立即开始执行,但只做有严格时限的工作。
– 下半部:能够被允许稍后完成的工作。

注册中断处理程序

中断处理程序是管理硬件的驱动程序的组成部分,每一个设备都有相关的驱动程序。如果设备使用中断,那么驱动程序就会注册相应的中断处理程序。

中断上下文

当执行一个中断处理程序,内核处于中断上下文中。

注意:进程上下文是一种内核所处的操作模式,此时内核代表进程执行——例如,执行系统调用或运行内核线程。在进程上下文中,可以通过current宏关联当前进程。此外,因为进程是以进程上下文的形式连接到内核中的,因此,进程上下文可以睡眠,也可以调用调度程序。

但中断上下文和进程没有关联,与current宏也不相关(尽管它会指向被中断的进程)。因为没有后备进程,所以中断上下文不可以睡眠,否则又怎能再对它重新调度呢?因此,不能从中断上下文中调用某些函数。如果一个函数睡眠,就不能再中断处理程序中使用它——这是对什么样的函数可以在中断处理程序中使用的限制。

中断上下文具有较为严格的时间限制,因为它打断了其他代码。中断上下文中的代码应当迅速、简洁,尽量不要使用循环去处理繁重的工作。有一点非常重要,请永远牢记:中断处理程序打断了其他代码(甚至可能打断了在其他中断线上的另一中断处理程序)。正是因为这种异步执行的特性,所以所有的中断处理程序必须尽可能的迅速、简洁。尽量把工作从中断处理程序中分离出来,放在下半部来执行,因为下半部可以在更合适的时间运行。

中断处理程序栈是一个配置选项。曾经中断处理程序没有自己的栈,它们共享所中断进程的内核栈,内核栈的大小是两页,32位——8KB,64位——16KB。在这种设置中,中断处理程序共享别人的堆栈,所以在栈中获取时间时必须非常解约。当然,内核栈本来就很有限,因此,所有的内核代码都应该谨慎使用它。

中断处理机制的实现

/proc/interrupts

procfs是一个虚拟文件系统,只存在于内核内存,一般安装于/proc目录。在procfs中读写文件都要调用内核函数,这些函数模拟从真实文件中读或写。如/proc/interrupts文件,该文件存放系统中断与中断相关的统计信息。

中断控制

一般来说,控制终端系统的原因归根结底是需要提供同步。通过禁止中断,可以确保某个中断处理程序不会抢占当前的代码。此外,禁止中断还可以禁止内核抢占。但不管是禁止中断还是禁止内核抢占,都没有提供任何保护机制来防止来自其他处理器的并发访问。Linux支持多处理器,因此,内核代码一般都需要获取某种锁,防止来自其他处理器对共享数据的并发访问。获取这些锁的同时也伴随着禁止本地中断。锁提供保护机制,防止来自其他处理器的并发访问,而禁止中断提供保护机制,则是防止来自其他中断处理程序的并发访问。

下半部和延迟执行的工作

虽说中断处理程序在内核中必不可少,但也有其局限:

– 以异步方式执行,并且有可能打断其他重要代码的执行(甚至包括其他中断处理程序)
– 如果当前有一个中断处理程序正在执行,在最好的情况下,与该中断同级的其他中断会被屏蔽;在最坏情况下,当前处理器上所有中断都会被屏蔽
– 中断处理程序旺旺需要对硬件进行操作,所以通常有很高的时限要求
– 中断处理程序不在进程上下文中运行,因此不能阻塞

因此,中断处理流程还需要另一部分来提供其他那些时间要求宽松的任务的机制,也就是下半部。

下半部

下半部的任务:执行与中断处理密切相关但中断处理程序本身不执行的工作。在理想情况下,最好是中断处理程序将所有工作都交给下半部分执行。但往往会有部分对时间敏感的工作需要中断处理程序完成。

为什么要用下半部

当中断处理程序运行时,当前中断线在所有处理器上都会被屏蔽,若处理程序是IRQF_DISABLED类型,它执行时会禁止所有本地终端。因此缩短终端被屏蔽的时间对系统的响应能力和性能都至关重要。再加上中断处理程序要与其他程序异步执行,所以很明显我们需要缩短中断处理程序的执行时间。

下半部的环境

1. BH(bottom half)提供了一个静态创建、由32个bottom halves组成的链表。上半部通过一个32位整数中的一位来判断哪个bottom half可以执行。每个BH在全局范围进行同步,即使分属于不同的处理器,也不允许任何两个bottom half同事执行。
2. 任务队列
3. 软中断和tasklet
4. 工作队列

内核同步介绍

临界区和竞争条件

临界区:访问和操作共享数据的代码段。

竞争条件:两个执行线程处于同一个临界区中执行。

同步:避免并发和防止竞争条件。

注意:多个执行线程并发访问同一个资源通常是不安全的,为了避免在临界区中并发访问,开发者必须保证这些代码原子地执行。

加锁

锁机制:使用一个单独的锁保证一次只有一个对象占用临界资源,要使用临界资源就要先占有锁。

注意:锁的使用是自愿的、非强制的。

注意:各种锁机制之间的区别:当锁已经被其他线程持有,因而不可用时的行为表现不同。有些锁会简单地执行忙等待;而有些锁会使当前任务睡眠直到锁可用。

造成并发执行的原因

用户空间之所以需要同步,是因为用户程序会被调度程序抢占和重新调度。由于用户进程可能在任何时刻被抢占,而调度程序完全可能选择另一个高优先级的进程到处理器上执行,所以就会使得一个程序正处在临界区时,被非自愿地抢占了。如果新调度的进程随后也进入同一个临界区,前后两个进程就会产生竞争。另外,因为信号处理是异步发生的,所以,即使是单个线程的多个进程共享文件,或者在一个程序内部处理信号,也有可能产生竞争条件。

内核中可能造成并发执行的原因:

– 中断
– 软中断和tasklet
– 内核抢占
– 睡眠及与用户空间的同步
– 对称多处理

死锁

死锁的产生需要一定条件:要有一个或多个执行线程和一个或多个资源,每个线程都在等待其中的一个资源,但所有的资源都已经被占用了。所有线程都在相互等待,但它们永远不会释放已经占有的资源。于是任何线程都无法继续。

简单来说就是:占有且等待、互斥、不可抢占、环路等待。

避免死锁的简单规则:

– 按顺序加锁
– 防止发生饥饿
– 不要重复请求同一个锁
– 设计应力求简单

注意:尽管释放锁的顺序和死锁无关,但还是建议以获取锁的顺序释放锁。

争用和拓展性

锁的争用:当锁正在被占用时,有其他线程试图获得该锁。(锁处于高度争用状态指有多个其他线程正在等待获取该锁)

由于锁的作用是使程序以串行方式对资源进行访问,所以使用锁无疑会降低系统性能。被高度争用的锁会成为系统的瓶颈,严重降低系统性能。

拓展性是对系统可拓展程度的一个量度。

加锁粒度用来描述加锁保护的数据规模。

内存管理

尽管处理器的最小可寻址单位通常为字,但内存管理单元通常以页为单位进行处理。(虚拟内存中页就是最小单位)

由于硬件的限制,内核并不能对所有的页一视同仁。有些页位于内存中特定的物理地址上,所以不能将其用于一些特定的任务。由于存在这种限制,所以内核把页划分为不同的区。

Linux必须处理如下两种由于硬件存在缺陷而引起的内存寻址问题:

– 一些硬件只能用某些特定的内存地址来执行DMA
– 一些体系结构的内存的物理寻址范围比虚拟寻址范围大得多,意味着有一些内存不能永远地映射到内核空间上。

因此,Linux使用了四种区:

1. ZONE_DMA:执行DMA操作(<16MB)
2. ZONE_DMA32:与ZONE_DMA类似,但只能被32位设备访问
3. ZONE_NORMAL:能正常映射的页(16~896MB)
4. ZONE_HIGHEM:里面的页不能永久地映射到内核地址的空间(>896MB)

Linux把系统的页划分为区,从而形成不同的内存池,根据用途分配内存。

slab层

分配和释放数据结构是所有内核中最普遍的操作之一,为了便于数据的频繁分配和回收,通常会用空闲链表提供可用的、已经分配好的数据结构块。当需要新的数据结构实例,就从空闲链表中直接获取,而不用重新分配内存;用完以后就把它放回空闲链表。

在内核中,空闲链表面临的主要问题之一是不能全局控制。当可用内存变得紧缺,内核无法通知每个空闲链表,让其收缩缓存的大小以释放出一些内存来。实际上,内核根本就不知道存在任何空闲链表。因此出现了slab层来做通用数据结构缓存层。

slab分配器试图在几个基本原则间寻找平衡:

– 频繁使用的数据结构也会频繁分配和释放,因此需要缓存它们
– 频繁分配和回收必然导致内存碎片(难以找到大块连续可用内存)。为了避免这种情况,空闲链表的缓存会连续地存放。因为已释放的数据结构又会放回空闲链表,因此不会导致碎片
– 回收的对象可以立即投入下一次分配,因此,对于频繁地分配和释放,空闲链表可以提高其性能
– 如果分配器知道对象大小、页大小和总的高速缓存大小这样的概念,它会做出更明智的决策
– 如果让部分缓存专属于单个处理器(对系统上的每个处理器独立而唯一),那么,分配和释放就可以在不加SMP锁的情况下进行
– 如果分配器是与NUMA相关的,它就可以从相同的内存节点为请求者进行分配
– 对存放的对象进行着色,以防止多个对象映射到相同的高速缓存行

slab层的设计

slab层把不同的对象划分为所谓高速缓存组,其中每个高速缓存组都存放不同类型的对象,每种类型的对象对应一个高速缓存。然后高速缓存又被划分为slab,slab由一个或多个物理上连续的页组成。每个slab都包含一些对象成员(被缓存的数据结构)。每个slab处于三种状态:满、部分、空。

一个满的slab没有空闲的对象(所有对象均已分配);一个空的slab没有分配任何对象(所有对象都是空闲);一个部分满的slab有些对象已分配,有些空闲。

当内核某一部分需要一个新的对象时,若有部分满的slab,则先从部分满的slab中进行分配;否则就从空的slab中分配。如果没有空的slab,就要创建一个slab。

slab层只在给定的高速缓存部分中既没有满也没有空的slab时才会调用页分配函数。

slab层只在下列情况调用页释放函数:

– 当可用内存变得紧缺时,系统试图释放出更多内存以供使用
– 当高速缓存显式地被撤销

虚拟文件系统

文件系统抽象层

之所以可以使用通用文件系统接口对所有类型的文件系统进行操作,是因为内核在它的底层文件系统接口上建立了一个抽象层。该抽象层使Linux能够支持各种文件系统,即使是它们在功能和行为上存在很大差别。为了支持多文件系统,VFS提供了一个通用文件模型,该模型囊括了任何文件系统的常用功能集和行为。

Unix文件系统

Unix使用了四种和文件系统相关的传统抽象概念:

1. 文件
2. 目录项
3. 索引节点
4. 安装点

从本质上讲,文件系统是特殊的数据分层存储结构,它包含文件、目录和相关的控制信息。在Unix中,文件系统被安装到一个特定的安装点上,该安装点在全局层次结构中被称作命名空间,所有的已安装文件系统都作为根文件系统树的枝叶出现在系统中。

文件通过目录组织,目录和文件统称为目录项(目录也是一个普通的文件,VFS将目录看作文件处理)。

Unix将文件的相关信息和文件本身加以区分:文件的相关信息有时被称作文件的元数据(即文件的相关数据,如:访问控制权限、大小、拥有者、创建时间等信息),这些信息被存储在一个单独的数据结构——inode中。所有这些信息都和文件系统的控制信息密切相关,文件系统的控制信息存储在超级块中。

注意:超级块是一种包含文件系统信息的数据结构。

VFS对象及其数据结构

VFS中的主要对象类型:

– 超级块对象:代表一个具体的已安装文件系统
– 索引节点对象:代表一个具体文件
– 目录项对象:代表一个目录项,是路径的一个组成部分
– 文件对象:代表进程打开的文件

块I/O层

块设备:系统中能随机(不需要按顺序)访问固定大小数据片(块)的硬件设备。

字符设备:按照字符流的方式被有序访问的硬件设备。

剖析一个块设备

块设备中最小的可寻址单元是扇区,扇区的大小是设备的物理属性,扇区是所有块设备的基本单元——块设备无法对比扇区还小的单元进行寻址和操作。

块是文件系统的一种抽象——只能基于块来访问文件系统。虽然物理磁盘寻址是按照扇区级机型的,但内核执行的所有磁盘操作都是按照块进行的。

缓冲区和缓冲区头

当一个块被调入内存(读入后或等待写出),它要存储在一个缓冲区中。每个缓冲区与一个块对应,它相当于是磁盘块在内存中的表示。块包含一个或多个扇区,但大小不能超过一个页面,所以一个页可以容纳一个或多个内存中的块。由于内核在处理数据时需要一些相关的控制信息,因此每一个缓冲区都有一个对应的描述符。

缓冲区头用于描述磁盘块和物理内存缓冲区(在特定页上的字节序列)之间的映射关系。这个结构体在内核中只扮演一个描述符的角色,说明从缓冲区到块的映射关系。

bio结构体

目前内核中块I/O操作的基本容器由bio结构体表示,该结构体表示:正在现场的(活动的)以segment链表形式组织的块I/O操作。一个segment是一小块连续的内存缓冲区。这样的话,就不需要保证单个缓冲区一定要连续。通过segment来描述缓冲区,即使一个缓冲区分散在内存的多个位置上,bio结构体也能对内核保证I/O操作的执行。像这样的向量I/O就是所谓的聚散I/O。

下图表示了bio结构体与其他结构体之间的关系:

bio结构体和缓冲区头的区别

bio结构体代表的是块I/O操作,它可以包括内存中的一个或多个页;而缓冲区头结构体代表的是一个缓冲区,它仅仅是描述了磁盘中的一个块。

因为缓冲区头关联的是单独页中的单独磁盘块,所以它可能会引起不必要的分割,将请求按块为单位划分,只能靠以后才能再重新组合。而bio结构体是轻量级的,它描述的块可以不需要连续存储区,并且不需要分割I/O操作。

用bio结构体代替缓冲区头结构体还有其他好处:

– bio结构体很容易处理高端内存,因为它处理的是物理页面而不是直接指针
– bio结构体既可以代表普通页I/O,同时也可以代表直接I/O(不通过页高速缓存的I/O操作)
– bio结构体便于执行分散——集中(矢量化)块I/O操作,操作中的数据可以取自多个物理页面
– bio结构体相比于缓冲区头结构体属于轻量级结构体,它只需要包含块I/O操作所需的信息,而不用包含缓冲区本身相关的不必要信息

但还是需要缓冲区头结构体,毕竟它还负责描述磁盘块到页的映射。bio结构体不包含任何和缓冲区相关的状态信息——它仅仅是一个矢量数组,描述一个或多个单独块I/O操作的数据片段和相关信息。

I/O调度程序

磁盘寻址是计算机最慢的操作之一,每一次寻址(定位硬盘磁头刀特定块上的某个位置)需要花费不少时间,所以尽量缩短寻址时间无疑是提高系统性能的关键。

为了优化寻址操作,内核既不会简单地按请求接收次序,也不会立即将其提交给磁盘。相反,它会在提交前,先执行名为合并与排序的预操作,这种预操作可以极大地提高系统的整体性能。在内核中负责提交I/O请求的子系统成为I/O调度程序。

I/O调度程序将磁盘I/O资源分配给系统中所有挂起的块I/O请求。具体地说,这种资源分配是通过将请求队列中挂起的请求合并和排序来完成的。注意不要讲I/O调度程序和进程调度程序混淆。进程调度程序是将处理器资源分配给系统中的运行进程。但两者都是讲一个资源虚拟给多个对象,这种虚拟提供给用户的就是多任务和分时操作系统。

I/O调度程序的工作

I/O调度程序通过管理块设备的请求队列,减少磁盘寻址时间,从而提高全局吞吐量。

I/O调度程序通过两种方法减少磁盘寻址时间:

– 合并:将两个或多个请求结合成一个新请求。
– 排序:使整个请求队列按扇区增长方向有序排列,通过保持磁盘头以直线方向移动,缩短了所有请求的磁盘寻址时间,所以这种调度也被称作电梯调度。

Linus电梯

当请求加入到队列中,可能发生的四种操作:

1. 如果队列中已存在一个对相邻磁盘扇区操作的请求,那么新请求将和这个已存在的请求合并成一个请求
2. 如果队列中存在一个驻留时间过长的请求,那么新请求将被插入到队列尾部,以防止其他旧请求饥饿
3. 如果队列中以扇区方向为序存在合适的插入位置,那么新的请求将被插入到该位置,保证队列中的请求是以被访问磁盘物理位置为序进行排列的
4. 如果队列中不存在合适的请求插入位置,请求将被插入到队列尾部

最终期限I/O调度程序

最终期限I/O调度程序时为了解决Linus电梯所带来的饥饿问题而提出的。出于减少磁盘寻址时间的考虑,对某个磁盘区域的繁重操作,无疑会使得磁盘其他位置上的操作请求得不到运行的机会。实际上,一个对磁盘同一位置操作的请求流可以造成较远位置的其他请求永远得不到运行机会。

更糟糕的是,普通的请求饥饿还会带来“写——饥饿——读”这种特殊问题。写操作通常是在内核空闲时才将请求提交给磁盘,写操作完全和提交它的应用程序异步执行;读操作则相反,当应用程序提交读请求,应用程序会发生堵塞直到读请求被满足,也就是说,读操作是和应用程序异步执行的。所以虽然写请求时间对应用程序性能的影响不大,但读操作响应时间对系统性能影响很大。

此外,读请求往往会相互依赖。不管是读还是写,都需要读取类似索引节点这样的元数据。从磁盘进一步读取这些块会使I/O操作串行化。所以如果每一次请求都发生饥饿,全部延迟就会造成过长的等待时间。因此,读请求的响应时间直接影响系统性能。

注意:减少请求饥饿必须以降低全局吞吐量为代价。

在最后期限I/O调度程序中,每个请求都有一个超时时间,它首先将新请求以类似Linus电梯的方式执行请求的合并和插入,但会以请求类型将它们插入到额外队列(FIFO)中。如果在写队列头或在读FIFO队列头的请求超时,最后期限I/O程序会从FIFO队列中提取请求进行服务。如图:

注意:最后期限I/O调度并不难严格保证请求的响应时间,但通常可以在请求超时或超时前提交和执行,以防止饥饿。

预测I/O调度程序

预测I/O调度程序基于最后期限I/O程序增加了预测启发能力。

预测I/O调度试图减少在进行I/O操作期间,处理新到的读请求所带来的寻址数量。请求提交后并不直接返回处理其他请求,而是会有意空闲片刻,这个等待时间很短,但能让其他应用程序提交其他读请求(任何对相邻磁盘位置操作的请求都会立刻得到处理)。等待时间结束后,预测I/O调度程序就会重新返回原来的位置继续执行剩下的请求。

预测调度I/O程序能带来多大的优势主要取决于能否正确预测应用程序和文件系统的行为,这些预测依赖于一系列的启发和统计工作。

完全公正的排队I/O调度程序

此时,每一个提交I/O的进程都有自己队列,调度程序把进入的I/O请求放入特定的队列中,以时间片轮转调度队列,从每个队列中选取请求数,然后进行下一轮调度。

进程地址空间

地址空间

进程地址空间由进程可寻址的虚拟内存组成,而且更为重要的特点是内核允许进程使用这种虚拟内存中的地址。每个进程都有一个32位或64位的独立、连续的地址空间。

进程只能访问有效内存区域内的内存地址,每个内存区域也具有相关权限,如:对相关进程由可读、可写、可执行属性。

内存区域可以包含各种内存对象,如:

– 可执行文件代码的内存映射(代码段)
– 可执行文件的已初始化全局变量的内存映射(数据段)
– 包含未初始化全局变量,也就是bss段的零页的内存映射
– 进程用户空间栈的零页的内存映射
– C库或动态链接程序等共享库的代码段、数据段和bss
– 内存映射文件
– 共享内存段
– 匿名内存映射

进程地址空间中的任何有效地址都只能位于唯一的区域,这些内存区域不能相互覆盖。

内存描述符

内核用内存描述符mm_struct结构体表示进程的地址空间,该结构体包含了和进程地址空间有关的全部信息。

mm_struct与内核线程

内核线程没有进程地址空间,也没有相关的内存描述符,因此内核线程对应点进程描述符中mm域为空。这也正是内核线程的真正含义——没有用户上下文。

因为内核线程不需要访问任何用户空间的内存而且因为内核线程在用户空间中没有任何页,因此它们不需要有自己的内存描述符和页表。但内核线程还是需要使用一些数据以访问内存的(如页表)。为了避免内核线程为内核描述符和页表浪费内存,也为了当新内核线程运行时,避免浪费处理器周期向新地址空间进行切换,内核线程将直接使用前一个进程的内存描述符。

虚拟内存区域

内存区域由vm_area_struct结构体描述,该结构体描述了指定地址空间内连续区间上的一个独立内存范围。内核将每个内存区域作为一个单独的内存对象管理,每个内存区域都拥有一致的属性,另外,相应的操作也都一致。按照这样的方式,每一个VMA就可以代表不同类型的内存区域,这种管理方式类似于VFS。

页高速缓存和页回写

Linux内核通过页高速缓存实现磁盘缓存,页高速缓存主要用来减少对磁盘的I/O操作,具体地说,是通过把磁盘中的数据缓存到物理内存中,把对磁盘的访问变为对物理内存的访问。

磁盘高速缓存在操作系统中极其重要的原因:

1. 访问磁盘的速度要远远低于访问内存的速度——ms和ns的差距
2. 数据一旦被访问,就很有可能在短期内再次被访问到(局部性原理)

缓存手段

写缓存

写缓存常见的三种策略:

1. 当需要对缓存中的数据片进行写操作,直接写入到磁盘,同时使缓存中的数据失效。如果有后续的读操作,则重新从磁盘中读数据到缓存中
2. 写操作将自动更新内存缓存,同时也更新磁盘文件
3. Linux采用的回写,此时写操作直接写到内存中,同时标记页高速缓存中数据片被写入的页为“脏”,并将该页加入脏页链表中。然后由一个特定的进程(回写进程)周期地将脏页链表中的页写回到磁盘,最后清除页的脏标记。

设备与模块

设备类型

Linux将设备分为以下三种类型:

1. 块设备
2. 字符设备
3. 网络设备

发表评论