时空波居士 ☀️摩诃般若波罗蜜

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

2017-04-05

Linux内核简介

操作系统和内核

将操作系统和运行在它之上的应用程序看成一个系统,操作系统是指在整个系统中负责完成最基本功能和系统管理的那些部分,包括内核、设备驱动程序、启动引导程序、命令行Shell或其他用户界面、文件管理工具和系统工具。

内核是操作系统的核心,通常由以下部分组成:

  • 负责响应中断的中断服务程序
  • 负责管理多个进程从而分享处理器时间的调度程序
  • 负责管理进程地址空间的内核管理程序
  • 网络、进程间通信等系统服务

内核空间:内核独立于普通应用程序,拥有受保护的内存空间和访问硬件设备的所有权限。 用户空间:应用程序在用户空间执行,只能看到允许它们使用的部分系统资源,并且只使用某些特定的系统功能,不能直接访问硬件,也不能访问内核划给别人的内存空间。

当内核运行的时候,系统以内核态进入内核空间执行,而执行一个普通用户程序时,系统将以用户态进入用户空间执行。

系统调用:应用程序通过系统调用来与内核通信,通常调用库函数,再由库函数通过系统调用界面让内核代其完成各种不同任务(比如调用C库函数printf(),该库函数会格式化数据后调用内核的write()函数将数据写到控制台上)。在这种情况下,应用程序被称为通过系统调用在内核空间运行,而内核被称为运行于进程上下文中,这是应用程序完成其工作的基本行为方式。

中断:内核基于中断机制来管理系统的硬件设备,当硬件设备想要和系统通信的时候会首先发出一个异步的中断信号去打断处理器的执行,继而打断内核的执行。中断对应着一个中断号,内核通过这个中断号查找相应的中断服务程序。中断服务程序不在进程上下文中执行,而是在一个与所有进程都无关的、专门的中断上下文中运行,以此保证中断服务程序能够在第一时间响应和处理中断请求,然后快速地退出。

处理器在任何指定时间点上的活动必然属于以下三种情况之一:

  • 运行于用户空间,执行用户进程;
  • 运行于内核空间,处于进程上下文,代表某个特定的进程执行;(CPU空闲时,内核执行空进程)
  • 运行于内核空间,处于中断上下文,与任何进程无关,处理某个特定的中断;

单内核和微内核: 单内核将内核从整体上作为一个单独的大过程来实现,同时也运行在一个单独的地址空间上。这样的内核以单个静态二进制文件的形式存放于磁盘中,内核之间通信的开销微不足道,因为可以直接调用函数,大多数Unix系统都设计为单内核。 微内核的功能被划分为多个独立的过程,每个过程称为一个服务器,所有服务器都保持独立并运行在各自的地址空间上。因此不能像单内核那样直接调用函数,而是通过消息传递来处理内核通信(IPC),消息传递需要一定的周期,其开销大于函数调用。优点在于避免了因为一个服务的失效祸及另一个。Windows NT和Mach都是设计为微内核。 Linux是一个单内核,但是在具体设计上也汲取了微内核的精华,比如模块化设计、抢占式内核、支持内核线程以及动态装载内核模块的能力。

Linux与Unix的差异

  • Linux支持动态加载内核模块;(尽管Linux内核也是单内核)
  • Linux支持对称多处理机制(SMP);(每个处理器有相等的机会读/写存储器,也有相同的访问速度)
  • Linux内核可以抢占
  • Linux内核不区分线程和一般进程
  • Linux提供面向对象的设备模型、热插拔事件,以及用户空间的设备文件系统;
  • Linux忽略了一些设计拙劣的Unix特性,如STREAMS;

从内核出发

(获取内核源码、编译、安装等,略)

进程管理

进程是处于执行期的程序以及相关的资源的总称。 线程是在进程中活动的对象,每个线程都拥有一个独立的程序计数器、进程栈和一组进程寄存器。

Linux不特别区分进程和线程,线程被当做一种特殊的进程对待,内核调度的对象是线程而不是进程

进程描述符:内核把进程的列表存放在叫做任务队列的双向循环链表中,链表中的每一项都是类型为task_struct的,被称为进程描述符的结构,进程描述符中包含了一个具体进程的所有信息,比如其打开的文件、进程的地址空间、挂起的信号、进程的状态等。

分配进程描述符:Linux通过slab(一种内存分配机制)分配task_struct结构(task_struct分配在slab管理的缓存上),以此达到对象复用和缓存着色的目的。具体而言就是在进程的内核栈的栈顶(对于向上增长的栈来说)创建一个新的结构struct thread_info,而该结构中有一个指向task_struct的指针,x86系统中通过current宏(当前正在运行进程的进程描述符)从thread_info的task域中提取并返回task_struct的地址。

PID:内核通过一个唯一的进程标识值PID(int类型)来标识每个进程,内核将其放在各个进程的进程描述符中。PID的最大值默认为32768,可以通过修改/proc/sys/kernel/pid_max来提高(最高可达400万)。

进程状态:task_struct中的state域描述了进程的当前状态,有5种情况:

  • TASK_RUNNING:进程是可执行的,它或者正在执行,或者在运行队列中等待执行,这是进程在用户空间中执行的唯一可能的状态,也可以应用到内核空间中正在执行的进程。
  • TASK_INTERRUPTIBLE:进程是可中断的,进程被阻塞等待某些条件的达成,一旦这些条件达成,内核会把进程状态设置为可执行。
  • TASK_UNINTERRUPTIBLE:进程是不可中断的,处于此状态的进程对信号不做响应。
  • __TASK_TRACED:被其他进程跟踪的进程,例如正在被调试程序跟踪。
  • __TASK_STOPPED:进程停止执行,进程没有投入运行也不能投入运行,通常发生在接收到SIGSTOP、SIGTSTP、SIGTTIN、SIGTTOU等信号的时候,此外在调试期间接收到任何信号都会使进程进入这种状态。

设置当前进程状态: set_task_state(task,state); 或者: set_current_state(state);

进程上下文切换:可执行程序代码从一个可执行文件载入到进程的地址空间执行,将运行在用户空间。当程序执行了系统调用,或者触发了某个异常,它就陷入了内核空间,此时称内核代表进程执行,并处于进程上下文中。在此上下文中current宏是有效的。除非在此期间有更高优先级的进程需要执行,并由调度器做出了响应调整,否则在内核退出的时候,程序恢复在用户空间会继续执行。

进程家族树:进程之间存在继承关系,所有进程都是PID为1的init进程的后代,内核在系统启动的最后阶段启动该进程,该进程读取系统的初始化脚本并执行其他的相关程序,最终完成系统启动的整个过程。进程间的关系存放在进程描述符中,每个task_struct都包含一个指向其父进程task_struct的parent指针,以及一个名为children的子进程链表。

进程创建:Unix进程创建的过程被分解到两个函数中实现: 首先,fork()通过拷贝当前进程创建一个子进程,子进程与父进程的区别在于PID、PPID和某些资源统计量(如挂起的信号,这些没有必要被继承); exec()函数负责读取可执行文件并将其载入地址空间开始运行;

写时拷贝:传统的fork()系统调用直接把所有的资源复制给新创建的进程,这种实现效率低下,因为也许拷贝的数据并不共享。Linux的fork()使用写时拷贝,即不复制整个进程的地址空间,而是让父进程和子进程共享同一个拷贝,只有在需要写入的时候,数据才会被复制,在此之前只以只读方式共享。在页根本不会被写入的情况下,如fork()后立即exec(),它们就无须复制了。

fork() Linux通过clone()系统调用实现fork(),clone()系统调用通过一系列的参数标志来指明父、子进程需要共享的资源,然后调用do_fork(),do_fork()完成了进程创建中的大部分工作,并调用copy_process()函数,然后让进程开始运行。copy_process()函数完成的工作如下:

  • 调用dup_task_struct()为新进程创建一个内核栈、thread_info结构和task_struct,这些值与当前进程的值相同,此时子进程和父进程的描述符是完全相同的;
  • 检查并确保新创建这个子进程后,当前用户所拥有的进程数目没有超出给它分配的资源的限制;
  • 子进程使自己与父进程区别开来,进程描述符内的许多成员都要被清0或被设为初始值;
  • 子进程的状态被设置为TASK_UNINTERRUPTIBLE,以保证它不会投入运行;
  • copy_process()调用copy_flags()以更新task_struct的flags成员,表明进程是否拥有超级用户权限的PF_SUPERPRIV标志被清0,表明进程还没有调用exec()函数的PF_FORKNOEXEC标志被设置;
  • 调用alloc_pid()为新进程分配一个有效的PID;
  • 根据传递给clone()的参数标志,copy_process()拷贝或共享打开的文件、文件系统信息、信号处理函数、进程地址空间和命名空间等;
  • 最后,copy_process()做扫尾工作,并返回一个指向子进程的指针;
  • 再回到do_fork(),如果copy_process()成功返回,新创建的子进程被唤醒并让其投入运行。

vfork() 除了不拷贝父进程的页表项外,vfork()系统调用和fork()的功能相同,如果Linux将来fork()有了写时拷贝页表项,那么vfork()就彻底没用了。理想情况下最好不要调用vfork(),内核也不用实现它。 fork()和vfork()最终实际都是通过调用clone()来创建新进程。

线程在Linux中的实现

从内核角度来说,Linux并没有线程这个概念,Linux把所有的线程都当做进程来实现,内核并没有准备特别的调度算法或是定义特别的数据结构来表征线程,线程仅仅被视为一个与其他进程共享某些资源的进程。每个线程都拥有自己的task_struct,所以在内核中它看起来就像是一个普通的进程,只是线程和其他一些进程共享某些资源(创建线程时指定),如地址空间。对于Linux来说,它只是一种进程间共享资源的手段。

创建线程

线程的创建与普通进程的创建类似,只不过在调用clone()的时候需要传递一些参数标志来指明需要共享的资源,如共享地址空间、文件系统资源、文件描述符: clone( CLONE_VM | CLONE_FS | CLONE_FILES, 0);

内核线程

内核通过内核线程实现在后台执行一些操作,内核线程即独立运行在内核空间的标准进程,与普通的进程的区别在于内核线程没有独立的地址空间(指向地址空间的mm指针被设为NULL),它们只能在内核空间运行,不能切换到用户空间去。可以被调度、可以被抢占。 运行ps -ef可以看到内核线程。

进程终结

当一个进程终结时,内核必须释放它所占有的资源,并通知其父进程。一般发生在进程自身调用exit()系统调用的时候,既可能是显式的,也可能是隐式的(C语言编译器会在main()函数的返回点后面放置调用exit()的代码)。此外,当进程接受到它既不能处理也不能忽略的信号或异常时,也可能被动终结。不管是如何终结的,该任务最重都要靠do_exit()来完成,该函数需要做很多繁琐的工作,主要包括:

  • 将task_struct中的标志成员设置为PF_EXITING;
  • 调用del_timer_sync()删除任一内核定时器,根据返回结果确保没有定时器在排队,也没有定时处理程序在运行;
  • 调用acct_update_integrals()输出记账信息;
  • 调用exit_mm()释放进程占用的mm_struct,如果没有别的进程使用它们,就彻底释放它们;
  • 调用sem__exit(),如果进程排队等待IPC信号,它则离开队列;
  • 调用exit_files()和exit_fs(),以分别递减文件描述符、文件系统数据的引用计数,如果其中某个引用计数的数值降为0,就可以释放;
  • 根据exit()提供的退出代码(或其他内核机制规定的退出动作)设置task_struct中的exit_code,供父进程随时检索;
  • 调用exit_notify()向父进程发送信号,给子进程重新找养父,养父为线程组中的其他线程或者init进程,并把进程状态(exit_code)设为EXIT_ZOMBIE;
  • do_exit()调用schedule()切换到新的进程,因为处于EXIT_ZOMBIE状态的进程不会再被调度,所以这是进程所执行的最后一段代码,do_exit()永不返回;
  • 处于EXIT_ZOMBIE退出状态的进程不可运行,它所占用的所有内存就是内核栈、thread_info、task_struct结构,此时进程存在的唯一目的就是向它的父进程提供信息(进程描述符还在),父进程检索到信息后,由进程所持有的剩余内存被释放,归还给系统使用。

删除进程描述符

在调用了do_exit()后,尽管线程已经僵死不能再运行,但是系统还保留了它的进程描述符这样使父进程有办法在子进程终结后仍然能够获得它的信息。在父进程获得已终结的子进程的信息后,或者通知内核它并不关注那些信息后,子进程的task_struct才可被释放,即调用release_task()函数:

  • 调用_exit_signal(),该函数调用_unhash_process(),后者又调用detach_pid()从pidhash上删除该进程,同时也要从任务列表中删除该进程;
  • _exit_signal()释放目前僵死进程所使用的所有剩余资源,并进行最终统计和记录;
  • 如果这个进程是线程组的最后一个进程,并且领头进程已经死掉,那么release_task()就要通知僵死的领头进程的父进程;
  • release_task()调用put_task_struct()释放进程内核栈和thread_info结构所占的页,并释放task_struct所占的slab高速缓存; 至此,进程描述符和所有进程独享的资源就全部被释放。

孤儿进程

如果父进程在子进程之前退出,必须有机制来保证子进程能够找到一个新的父进程,否则这些成为孤儿的进程就会在退出时永远处于僵死状态,白白耗费内存。对于这个问题解决方法是给子进程在当前线程组内找一个线程作为父亲,如果不行,就让init做其父进程。init进程会例行调用wait()来检查其子进程,清除所有与其相关的僵死进程。

进程调度

进程调度程序是多任务系统在可运行态进程之间分配有限的处理器时间资源的内核子系统。

调度器类

Linux调度器以模块方式提供,因此允许不同类型的进程可以有针对性地选择调度算法,这种模块化的结构被称为调度器类。每个调度器都有一个优先级,基础的调度器代码会按照优先级顺序遍历调度类,拥有一个可执行进程的最高优先级的调度器类胜出,去选择下面要执行的那一个程序。 CFS是一个针对普通进程的调度类。

完全公平调度算法(CFS)

Linux自2.6.23内核版本开始使用称为完全公平调度算法的进程调度算法,该算法不直接分配时间片到进程,而是将处理器的使用比划分给进程,因此进程所获得的处理器时间和系统的负载密切相关。nice值(-20到+19)不再像标准Unix系统那样用来表示优先级,而是作为权重来影响进程的处理器使用比例,具有高nice值的进程将被赋予低权重,从而丧失一小部分处理器使用比。 Linux系统是抢占式的,其抢占时机取决于新的可运行程序消耗了多少处理器使用比,如果消耗的使用比比当前进程小,则新进程立刻投入运行,抢占当前进程。否则将推迟其运行。

时间记账:CFS不再有时间片的概念,但是也必须维护每个进程运行时间的记账,以此确保每个进程只在公平分配给它的处理器时间内运行。CFS使用调度器实体结构struct sched_entity来跟踪进程运行并记账。sched_entity在task_struct中以一个名为se的成员变量被嵌入。在sched_entity中有一个名为vruntime的变量用来存放进程的虚拟运行时间,该运行时间称为虚拟实时,其值的计算是经过了所有可运行进程总数的标准化,即被加权的,单位为ns,因此和定时器的节拍不相关。CFS使用vruntime变量来记录一个程序到底运行了多长时间以及它还应该再运行多久。

进程选择:CFS试图利用一个简单规则去均衡进程的虚拟运行时间,当要选择下一个运行进程时,它会挑一个具有最小vruntime的进程,这也是CFS调度算法的核心。CFS使用红黑树(rbtree)来组织可运行的进程队列,并利用其找到最小vruntime值的进程。

睡眠和唤醒:睡眠即被阻塞,此时进程处于一个特殊的不可执行的状态,进程把自己标志成睡眠状态,从可执行红黑树中移除,放入等待队列,然后调用schedule()选择和执行一个其他进程。唤醒的过程则相反,进程被设置为可执行状态,然后再从等待队列中移到可执行二叉树中。

上下文切换

上下文切换,即从一个可执行进程切换到另一个可执行进程,由context_switch()函数负责处理。每当一个新的进程被选出来准备投入运行的时候,schedule()就会调用该函数,它完成两项基本的工作: 调用switch_mm(),把虚拟内存从上一个进程映射切换到新进程中;// 切换虚拟内存 调用switch_to(),从上一个进程的处理器状态切换到新进程的处理器状态,包括保存、恢复栈信息和寄存器信息,以及其他任何与体系结构相关的状态信息。 // 切换处理器

抢占时机 每个进程都包含一个need_resched标志,用来表明是否需要重新执行一次调度。当某个进程应该被抢占时,scheduler_tick()会设置这个标志;当一个优先级高的进程进入可执行状态时,try_to_wake_up()也会设置这个标志。内核会检查该标志(如返回用户空间以及从中断返回的时候),确认其被设置,然会调用schedule()来切换到一个新的进程。

用户抢占 在从系统调用或者中断处理程序返回用户空间时,如果need_resched标志被设置,会导致schedule()被调用,内核会选择一个其他(更合适的)进程投入运行,即发生用户抢占。即用户抢占发生在: 从系统调用返回用户空间时; 从中断处理程序返回用户空间时;

内核抢占 Linux支持内核抢占,前提是重新调度是安全的。只要进程没有持有锁,就是安全的。具体实现就是在每个进程的thread_info中引入preempt_count计数器,初试为0,每当使用锁的时候+1,释放锁的时候-1,当数值为0时,内核就可以抢占。从中断返回内核空间时,内核会检查need_resched和preempt_count的值,以决定是调用调度程序(内核抢占)还是返回执行进程。如果内核中的进程被阻塞了,或者它显式地调用了schedule(),内核抢占也会显式地发生。即内核抢占会发生在: 中断处理程序正在执行,且返回内核空间之前; 内核代码再一次具有可抢占性的时候; 内核中的任务显式调用schedule(); 内核中的任务阻塞(这同样也会导致调用schedule());

实时调度策略 Linux提供了两种实时调度策略:SCHED_FIFO、SCHED_RR。而普通的、非实时的调度策略是SCHED_NORMAL。 实时调度策略不使用CFS来管理,而是被一个特殊的实时调度器管理。 SCHED_FIFO实现了一种简单的先入先出的调度算法,不使用时间片,处于可运行态的SCHED_FIFO进程会比任何SCHED_NORMAL级的进程都先得到调度,一旦一个SCHED_FIFO级进程处于可执行状态,就会一直执行,直到它自己受阻或者显式地释放处理器。 SCHED_RR与SCHED_FIFO大体相同,区别在于SCHED_RR带有时间片,在执行完预先分配的时间后就不能再继续执行了。

与调度相关的系统调用

系统调用

在Linux中,系统调用是用户空间访问内核的唯一手段,除异常和陷入外,它们是内核唯一的合法入口。一般情况下,应用程序通过在用户空间实现的应用编程接口(API),而不是直接通过系统调用来编程。调用printf()函数时,应用程序、C库和内核之间的关系: image 用户程序通过包含标准头文件并和C库链接,就可以使用系统调用。

系统调用号

在Linux中,每个系统调用都被赋予一个系统调用号(一个操作系统应该提供哪些接口,由POSIX标准规定),用来指明到底是要执行哪个系统调用,进程不会提及系统调用的名称。内核中有一个名为sys_call_table的系统调用表,记录了所有已注册的系统调用,并为其指定唯一的系统调用号。

系统调用处理程序

触发系统调用 因为内核驻留在受保护的地址空间上,用户空间进程无法直接执行内核代码,因此需要一种通知内核进行系统调用的方式。通知内核的机制基于软中断实现:通过引发一个异常来促使系统切换到内核态去执行异常处理程序,此时的异常处理程序实际上就是系统调用处理程序。 在x86上预定义的软中断号是128,通过int $0x86指令(中断指令)触发该中断后,将执行第128号异常处理程序,而该程序正是系统调用处理程序system_call()。

指定系统调用

在x86上,系统调用号通过eax寄存器传递给内核:在陷入内核之前,用户空间就把相应系统调用所对应的系统调用号放入eax中,这样系统调用处理程序一旦运行,就可以从eax中得到数据。

参数传递

在x86系统上,ebx、ecx、edx、esi、edi按照顺序存放前5个参数,当需要6个及以上参数时,应该用一个单独的寄存器存放指向所有这些参数在用户空间地址的指针。

返回值

给用户空间返回值也通过寄存器传递,在x86系统上它存放在eax寄存器中。

系统调用的实现

(如何编写、添加一个系统调用(不提倡),略) 系统调用上下文 内核在执行系统调用的时候处于进程上下文,current指针指向当前任务,即引发系统调用的那个进程。在进程上下文中,内核可以休眠,并且可以被抢占。当系统调用返回时,控制权仍然在system_call()中,它最终会负责切换到用户空间,并让用户进程继续执行下去。

内核数据结构

Linux内核内建了常用的数据结构,包括链表、队列、关联数组、红黑树等。 (略)

中断和中断处理

中断机制:处理器的速度跟外围的硬件设备不在一个数量级上,因此提供一种机制让硬件在需要的时候向内核发出信号。中断本质上是一种特殊的电信号,由硬件设备生成,并直接送入中断控制器(简单的电子芯片)的输入引脚中,中断控制器采用复用技术将多路中断管线只通过一个和处理器相连接的管线与处理器通信。处理器一经检测到此信号,便中断自己的当前工作转而处理中断。硬件设备生成中断的时候并不考虑与处理器的时钟同步,即中断随时可以产生,因此内核随时可能因为新到来的中断而被打断。

中断请求线(IRQ):每个中断都通过一个唯一的数字标志,这样操作系统才能够给不同的中断提供对应的中断处理程序。这些中断值即中断请求线,例如IRQ 0是时钟中断、IRQ 1是键盘中断。对于连接在PCI总线上的设备而言,中断请求线是动态分配的。

中断与异常的区别:异常与中断不同,中断是由硬件引起的,异常则发生在编程失误而导致错误指令,或者在执行期间出现特殊情况必须要靠内核来处理的时候(比如缺页)。它在产生时必须考虑与处理器时钟同步,因此异常也称同步中断。

中断处理程序

产生中断的每个设备都有一个相应的中断处理程序,一个设备的中断处理程序是它设备驱动程序的一部分(设备驱动程序是用于对设备进行管理的内核代码),在响应一个特定中断的时候,内核会执行特定的中断处理程序(驱动程序事先通过request_irq()注册中断处理程序)。在Linux中中断处理程序就是C函数,这些C函数按照特定类型声明,以便内核能够按照标准的方式传递处理程序的信息,中断处理程序要负责通知硬件设备中断已经被接收

中断处理程序与其他内核函数的真正区别在于:中断处理程序是被内核调用来响应中断的,而它们运行于中断上下文中,中断上下文也称原子上下文,该上下文中执行的代码不可阻塞。

中断屏蔽 如果当前有一个中断处理程序正在执行,根据注册中断处理程序是设置的参数的不同,屏蔽情况也不同: 如果没有设置IRQF_DISABLED,与该中断同级的其他中断都会被屏蔽; 如果设置了IRQF_DISABLED,当前处理器上所有其他中断都会被屏蔽;

上半部与下半部 中断处理程序运行需要快速执行(因为不可阻塞),同时要能完成尽可能多的工作,这里存在矛盾。因此把中断处理切分为两个部分,上半部分(top half)接收到一个中断后立即执行,但是只做有严格时限的工作,例如对接收到的中断进行应答或复位硬件。能够被允许稍后完成的工作会推迟到下半部分(bottom half)去,此后在合适的时机下半部分会被中断执行,Linux提供了实现下半部分的各种机制。

编写中断处理程序 (略)

查看处理器中断统计信息

cat /proc/interrupts

下半部和推后执行的工作

划分工作为上半部或下半部的基本规则:

  • 如果一个任务对时间非常敏感,将其放在上半部;
  • 如果一个任务和硬件相关,将其放在上半部;(例如从网卡的缓存中拷贝数据)
  • 如果一个任务要保证不被其他中断(特别是相同的中断)打断,将其放在上半部;
  • 其他所有任务考虑放在下半部;

下半部的环境

下半部执行的关键在于当它们运行的时候,允许响应所有的中断。至于具体的执行时间并不确定,只是为了把一些任务推迟一点,让它们在系统不太繁忙并且中断恢复后执行就可以了。通常下半部在中断处理程序一返回就会马上运行。

和上半部只能通过中断处理程序实现不同,下半部可以通过多种机制实现: 最早的BH机制:提供一个静态创建、由32个bottom halves组成的链表,上半部通过一个32位整数中的一位来标识出哪个bottom half可以执行;这种机制简单但不够灵活,存在性能瓶颈; 任务队列:内核定义一组队列,其中每个队列都包含一个由等待调用的函数组成的链表,驱动程序可以把自己的下半部注册到合适的队列上去;这种机制无法替代整个BH接口,对于性能要求较高的子系统(比如网络)也不能胜任; 软中断和tasklet:这里的软中断指一组静态定义的下半部接口,共32个,可以在所有处理器上同时执行,软中断必须在编译期间就进行静态注册(最多只能注册32个,当前内核已使用9个)。tasklet是一种基于软中断实现的灵活性强、动态创建的下半部实现机制,其实是一种在性能和易用性之间寻求平衡的产物,对于大部分下半部处理来说,使用tasklet就足够了,对于网络这种性能要求较高的情况才需要使用软中断; 定时器:不同于其他实现方式,定时器可以把操作推迟到某个确定的时间段之后执行;

软中断的实现

软中断保留给系统中对时间要求最严格以及最重要的下半部使用,目前只有两个子系统(网络、SCSI)直接使用软中断。此外,tasklet和内核定时器都是建立在软中断上的。 软中断是在编译期间静态分配的,不像tasklet那样能够被动态地注册或注销。软中断由softirq_action结构表示。softirq_vec数组是一个包含32个该结构体的数组,每个被注册的软中断都占据该数组的一项,因此最多可能有32个软中断,在当前版本的内核中这32个项中只用到了9个。

当内核运行一个软中断处理程序的时候,会执行softirq_handler()函数,其唯一的参数是指向softirq_vec某个softirq_action结构体的指针。

一个注册的软中断必须在被标记后才会执行,中断处理程序在返回前会标记它的软中断。在下列场景待处理的软中断会被检查和执行: 从一个硬件中断代码处返回时; 在ksoftirqqd内核线程中; 在那些显式检查和执行待处理的软中断的代码中,比如网络子系统; 软中断最终在do_softirq()中执行,该函数很简单,如果有待处理的软中断,则循环遍历每一个,并调用它们的处理程序。

tasklet的实现

tasklet由两类软中断代表:HI_SOFTIRQ和TASKLET_SOFTIRQ,这两者之间唯一的实际区别在于HI_SOFTIRQ类型的软中断先执行。

tasklet由tasklet_struct结构表示,结构成员中有一个名为func的函数指针,代表tasklet的处理程序。state字段用来表明tasklet的状态,比如已调度、正在运行等。已调度的tasklet(等同于被触发的软中断)存放在两个单独处理器数据结构tasklet_vec(普通)和tasklet_hi_vec(高优先级)中,分别由tasklet_schedule()、tasklet_hi_schedule()这两个函数进行调度。

所有的tasklet都通过重复运用HI_SOFTIRQ和TASKLET_SOFTIRQ这两个软中断实现,当一个tasklet被调度时,内核就会唤起这两个软中断中的一个,随后该软中断会被特定的函数处理,执行所有已调度的tasklet,这个函数保证同一时间内只有一个给定类别的tasklet会被执行。

ksoftirqd线程

对于软中断,内核通常会选择在中断处理程序返回时进行处理,软中断的触发频率有时可能很高,而且处理函数有时还会自行重复触发(当一个软中断执行的时候,它可以重新触发自己以便再次得到执行),此时就会导致用户空间进程无法获得足够的处理器时间,因而处于饥饿状态。为解决该问题,当大量软中断出现的时候,内核会唤醒一组内核线程来处理这些负载,这些线程在最低优先级上运行(nice值为19),以保证它们不会和其他重要任务抢夺资源,但是最终肯定会被执行,这个线程名为ksoftirqd,每个处理器都有一个这样的线程。

工作队列的实现

工作队列可以把工作推后,交由一个内核线程去执行,因此可以运行在进程上下文中,允许重新调度甚至睡眠。因此,当需要用一个可以重新调度的实体来执行下半部处理的时候,比如需要获得大量内存、需要获取信号量、以及需要执行阻塞式的IO操作时,就应该选择工作队列。它是唯一能够在进程上下文中运行的下半部实现机制,也只有它才可以睡眠

工作队列子系统是一个用于创建内核线程的接口,通过它创建的进程负责执行由内核其他部分排到队列里的任务,它创建的这些内核线程称为工作者线程。驱动程序可以使用工作队列来创建一个专门的工作者线程来处理需要推后的工作。工作队列子系统提供了一个缺省的工作者线程events/n(n为CPU编号),以处理被推后的工作。除非一个驱动程序必须建立一个属于它自己的内核线程,否则最好使用缺省线程。

工作者线程用workqueue_struct表示,该结构内部维护了一个cpu_workqueue_struct的数组,数组的每一项对应系统中一个处理器。所有的工作者线程都是用普通的内核线程实现的,它们都要执行worker_thread()函数,在它初始化完成以后,这个函数执行一个死循环并开始休眠,当有操作被插入到队列里的时候,线程就被唤醒,并执行这些操作。工作用work_struct表示,每个处理器上的每种类型的队列(cpu_workqueue_struct的数组)都有一个该结构的链表,当一个工作者线程被唤醒时,它会执行它链表上的所有工作,执行完毕后就移除该工作,当链表上不再有对象时,它就会继续休眠。

内核同步介绍

临界区就是访问和操作共享数据的代码段,如果两个执行线程有可能处于同一个临界区中同时(交错地)执行,就称为竞争条件,避免和防止竞争条件称为同步

处理器提供了指令来原子地读变量、增加变量、写回变量,两个原子操作不可能交错执行。锁也是采用原子操作实现的,因此锁操作不存在竞争。

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

中断:中断几乎可以在任何时刻异步发生,也就可能随时打断当前正在执行的代码; 软中断和tasklet:内核能在任何时刻唤醒或者调度软中断和tasklet,打断当前正在执行的代码; 内核抢占:因为内核具有抢占性,所以内核中的任务可能会被另一个任务抢占; 睡眠及与用户空间的同步:在内核执行的进程可能会睡眠,这就会唤醒调度程序,从而导致另一个新的用户进程执行; 对称多处理:两个或者多个处理器可以同时执行代码;

用户空间之所以需要同步,是因为用户程序会被调度程序抢占和重新调度,造成一个程序正处于临界区时被非自愿地抢占了。而新的线程可能会访问同样的临界区。

用锁来保护共享资源并不困难,辨认出真正需要共享的数据和相应的临界区才是真正有挑战的地方。

死锁产生的条件:

要有一个或多个执行线程和一个或多个资源,每个线程都在等待其中的一个资源,但所有的资源都已经被占用了,所有线程都在相互等待,但它们永远不会释放已经占有的资源,于是任何线程都无法继续。最简单的死锁例子是自死锁。

避免死锁的简单规则:

按顺序加锁:当有多个锁时,必须保证以相同的顺序获取锁,这样可以阻止致命的拥抱类型的死锁; 防止发生饥饿:这个代码的执行是否一定会结束?如果A不发生,B一定要等待下去吗? 不要重复请求同一个锁; 设计应力求简单,越复杂的加锁方案越有可能造成死锁;

内核同步方法

原子操作

原子操作是其他同步方法的基石,可以保证指令以原子的方式执行,即执行过程中不会被打断。因此不会引起竞争条件。内核提供了两组原子操作接口,一组针对整数进行操作,另一组针对单独的位进行操作。

原子整数操作

针对整数的原子操作只能对atomic_t类型的数据进行处理,之所以引入这样一个特殊的类型而不是直接使用C语言,主要有以下原因: 让原子函数只接受atomic_t类型的操作数,可以确保原子操作只与这种特殊类型的数据一起使用; 使用atomic_t类型确保编译器不对相应的值进行访问优化,使得原子操作最终接收到正确的内存地址,而不只是一个别名; 使用atomic_t可以屏蔽在不同体系结构上实现原子操作时的差异;

atomic_t在32位int类型的低8位嵌入了一个锁,因为对原子操作缺乏指令级的支持,所以只能用锁来避免对原子类型数据的并发访问,因此尽管Linux支持的所有机器上的int型数据都是32位的,但是使用atomic_t的代码只能将该类型的数据当做24位来用。

原子操作通常是内联函数,往往是通过内嵌汇编指令来实现的。原子整数操作列表如下:

在64位体系结构上需要使用atomic64_t类型(对long的封装,而不是int)。

原子位操作

原子位操作是对普通的内存地址进行操作,它的参数是一个指针和一个位号,第0位是给定地址的最低有效位。由于原子位操作是对普通的指针进行的操作,所以不像原子整型对应atomic_t,这里没有特殊的类型,只要指针指向任何数据,就可以对它进行操作。标准原子位操作列表如下:

内核还提供了一组与上述操作对应的非原子位函数,其操作与对应的原子位函数相同,但是不保证原子性(速度更快),且名字前缀多两个下划线,如test_bit()对应的非原子形式是__test_bit()。如果代码本身已经避免了竞争条件,就可以使用非原子位操作。

自旋锁

Linux内核中最常见的锁是自旋锁,自旋锁最多只能被一个可执行线程持有,如果一个执行线程试图获得一个已经被持有的自旋锁,那么改线程就会一直进行忙循环-旋转-等待锁重新可用。如果锁未被争用,请求锁的执行线程便能立刻得到它,继续执行。

自旋锁的初衷在于在短期内进行轻量级加锁。因为一个被争用的自旋锁使得请求它的线程在等待锁重新可用时自旋(特别浪费处理器时间),所以自旋锁不应该被长时间持有。还可以采取另外的方式来处理对锁的争用,比如让请求线程睡眠,直到锁重新可用时再唤醒它,这样处理器就不必循环等待,可以去执行其他代码,但这也会带来额外的开销(两次上下文切换)。

自旋锁的实现与体系结构密切相关,代码往往通过汇编实现,基本使用形式如下:

DEFINE_SPINLOCK(mr_lock);
spin_lock(&mr_lock);
/* 临界区 */
spin_unlock(&mr_lock);

自旋锁可以使用在中断处理程序中,在中断处理程序中使用自旋锁时,一定要在获取锁之前首先禁止本地中断(当前处理器上的中断请求),否则中断处理程序就会打断正持有锁的内核代码,有可能会视图去争用这个已经被持有的自旋锁,于是造成死锁。

信号量

Linux中的信号量是一种睡眠锁,如果有一个任务试图获得一个不可用(已经被占用)的信号量时,信号量会将其推进一个等待队列,然后让其睡眠。此时处理器就可以执行其他代码,当持有的信号量可用后,处于等待队列中的那个任务将被唤醒,并获得该信号量。

互斥信号量和计数信号量

不同于自旋锁,信号量可以同时允许任意数量的锁持有者,同时允许的持有者数量在声明信号量的时候指定,这个值称为使用者数量。使用者为1的信号量和自旋锁一样,在一个时刻仅允许一个锁持有者,这样的信号量称为二值信号量或者互斥信号量。初始化时使用者数量大于1的信号量被称为计数信号量

信号量支持两个原子操作P()和V(),P操作通过对信号量计数减1来获得一个信号量,如果结果是0或大于0,则获得信号量锁,任务就可以进入临界区,如果结果是负数,任务会被放入等待队列。当临界区执行完成后,V操作用来释放信号量,即将信号量计数加1。

信号量用struct semaphore表示:

/* 创建一个名为mr_sem的信号量 */
struct semaphore mr_sem;	
sema_init(&mr_sem,count);	

创建互斥信号量可以使用如下快捷方式: static DECLARE_MUTEX(mr_sem); 之后可以使用down_interruptible(&mr_sem)函数(即P操作)和up(&mr_sem)函数(即V操作)进行控制。

互斥体

互斥体在内核中对应数据结构mutex,其行为与使用计数为1的信号量类似,但操作接口更简单,实现也更高效,而且使用限制更强。引入互斥体的初衷是提供一个更简单的睡眠锁,即一个不需要管理任何使用计数的简化版的信号量。其使用上也有更多的限制: mutex的使用计数永远是1; 给mutex上锁者必须负责给其解锁,不能在一个上下文中锁定一个mutex,而在另一个上下文中给他解锁,因此mutex不适合内核同用户空间复杂的同步场景,最常使用的方式是在同一个上下文中上锁和解锁。 当持有一个mutex时,进程不可以退出; 不能在中断或者下半部中使用;

完成变量

完成变量提供了代替信号量的一个简单的解决方法,由结构completion表示。在一个指定的完成变量上,需要等待的任务调用wait_for_completion()来等待特定事件,当特定事件发生后,产生事件的任务调用complete()来发送信号唤醒正在等待的任务。例如当子进程执行或者退出时,vfork()系统调用使用完成变量唤醒父进程。

大内核锁(BKL)

BKL是一个全局自旋锁,使用它主要是为了方便实现从Linux最初的SMP过渡到细粒度枷锁机制,新代码中不再使用。(略)

顺序锁

简称seq锁,在2.6中引入的一种新型锁,提供了一种很简单的机制,用于读写共享数据,其实现主要依靠一个序列计数器。当有疑义的数据被写入时,会得到一个锁,并且序列值会增加,在读取数据之前和之后,序列号都被读取,如果读取的序列号值相同,说明在读操作进行的过程中没有被写操作打断过。如果读取的值是偶数,那边就表明写操作没有发生。

定时器和时间管理

内核中有大量的函数都是基于时间驱动的,其中有一些是周期执行的,比如对调度程序中的运行队列进行平衡调整、刷新屏幕、检测当前进程是否用尽了自己的时间片等。另一些则需要等待一个相对时间后才运行,比如要推后执行的IO操作等。除了这两种情况,内核还必须管理系统的运行时间以及当前时间。

周期性产生的事件都是由系统定时器驱动的,·系统定时器是一种可编程的硬件芯片,它能以固定频率产生中断·,该中断就是所谓的定时器中断,它所对应的中断处理程序负责更新系统时间,也负责执行需要周期性运行的任务。

内核必须在硬件(系统定时器)的帮助下才能计算和管理时间。系统定时器以某种频率自行触发,该频率可以通过编程预定,连续两次时钟中断的时间间隔就称为节拍(tick)。系统定时器的频率是通过静态预处理定义的,也称为HZ(赫兹),体系结构不同HZ值也不同。

自Linux问世以来,i386体系结构的时钟中断频率就设定为100HZ,但是在2.5开发版内核中,被提高到1000HZ。提高节拍率等同于提高中断解析度,比如HZ=100的时钟的执行粒度为10ms,即系统中的周期事件最快为10ms运行一次,而不能有更高的精度(因而存在时间误差),但是当HZ=1000时,解析度就为1ms。劣势在于,频率越高,系统的负担越重,因为处理器必须花时间来执行时钟中断处理程序,此外还会更频繁地打乱处理器高速缓存,并增加耗电。

Linux内核也支持无节拍操作,当编译内核的时候设置了CONFIG_HZ配置选项,系统就根据这个选项动态调度时钟中断(按需动态调度和重新设置),而不是每隔固定时间间隔触发时钟中断。最大的好处在于省电。

jiffies

全局变量jiffies用来记录自系统启动以来产生的节拍的总数。系统启动时内核将该变量初始化为0,此后每次时钟中断处理程序会增加该变量的值,一秒内增加的值即HZ,系统运行时间以秒为单位计算就等于jiffies/HZ。Jiffies定义在文件linux/jiffies.h中: extern unsigned long volatile jiffies;

常用的一些运算:

unsigned long time_stamp = jiffies;			/* 现在 */
unsigned long next_tick = jiffies+1;			/* 从现在开始的下一个节拍 */
unsigned long later = jiffies + 5*HZ;			/* 从现在开始后的5秒 */
unsigned long fraction = jiffies + HZ/10;			/* 从现在开始后的100ms */

因为jiffies使用unsigned long,所以在32位机器上,时钟频率为100HZ的情况下,497天后会溢出,如果频率为1000HZ,49.7天后就会溢出。溢出后其值会绕回到0。内核中提供了四个宏用来帮助比较节拍计数,它们能正确地处理节拍计数回绕的情况。

实时时钟(RTC)

除了系统定时器,体系结构还提供了另一种计时设备,即实时时钟。实时时钟是用来持久存放系统时间的设备,即便系统关闭后,它也可以靠主板上的微型电池提供的电力保持系统的计时。实时时钟最主要的作用是在系统启动时初始化xtime变量(墙上时间,象征真实的用户时间)。

时钟中断处理程序

时钟中断处理程序可以划分为两个部分:体系结构相关部分和体系结构无关部分。 与体系结构相关的部分作为系统定时器的中断处理程序注册到内核中,以便在产生时钟中断时运行,虽然不同体系结构的具体工作方式不同,但是最低限度也要执行如下工作:

  1. 获得xtime_lock锁,以便对访问jiffies和墙上时间xtime进行保护
  2. 需要时,应答或者重新设置系统时间;
  3. 周期性地使用墙上时间更新实时时钟;
  4. 调用体系结构无关的函数tick_periodic();

tick_periodic()函数主要执行体系结构无关部分的工作,主要包括:

  1. 给jiffies变量加1;
  2. 更新资源消耗的统计值,比如当前进程所消耗的系统时间和用户时间;
  3. 执行已经到期的动态定时器;
  4. 执行sheduler_tick()函数;
  5. 更新墙上时间xtime;
  6. 计算平均负载值;

实际时间

当前实际时间(墙上时间)定义为struct timespec xtime;结构体timespec中有一个long域tv_sec以秒为单位,存放着自1970年1月1日以来经过的时间。此外还有一个v_nsec域记录自上一秒开始经过的ns数。读取xtime变量需要使用xtime_lock锁,该锁不是普通自旋锁,而是一个seqlock锁

定时器

定时器也称动态定时器、内核定时器,是内核推后固定时间执行某些代码的基础(不同于下半部机制,下半部机制需要的仅仅是不在当前时间执行,而并没有指定推迟多长时间执行)。定时器由结构timer_list表示,其使用非常简单:执行一些初始化操作,设置一个超时时间,指定超时发生后执行的函数,然后激活定时器就可以了:

struct time_list my_timer;				/* 定义一个定时器 */
init_timer(&my_timer);					/* 初始化 */
my_timer.expires = jiffies + delay;		/* 设定超时节拍数 */
my_timer.data = 0;						/* 传入函数参数 */
my_timer.function = my_function;		/* 回调函数 */

内存管理

页(page)

内核把物理页做为内存管理的基本单元:内存管理单元(MMU,管理内存并把虚拟地址转换为物理地址的硬件)以页为单位来管理系统中的页表,从虚拟内存的角度来看,页就是最小单位。体系结构不同,支持的页大小也不尽相同,大多数32位体系结构支持4KB的页,因此在支持4KB页大小并有1GB物理内存的机器上,物理内存会被划分为262144个页。

内核中用struct page结构表示系统中的每个物理页,该数据结构用于描述物理内存本身,而不是描述包含在其中的数据。其中有一个flags域用来表示页的状态,比如页是不是脏的、是不是被锁定在内存中,等等。flags中的每一位单独表示一种状态,因此它至少可以同时表示出32种不同的状态。_count域用于表示页的引用计数,当计数变为-1时,就说明当前内核并没有引用这一页,于是可以用于新的内存分配。virtual域表示页的虚拟地址,即页在虚拟内存中的地址。

区(zone)

由于硬件存在如下引起内存寻址问题的缺陷,所以内核使用区从逻辑上对具有相似特性的页进行分组,主要是以下缺陷:

  1. 一些硬件只能用某些特定的内存地址来执行内存直接访问;
  2. 一些体系结构的内存物理寻址范围比虚拟寻址范围大得多,这样就有一些内存不能永久地映射到内核空间上;

Linux主要使用了4种区:

  1. ZONE_DMA:这个区包含的页能用来执行内存直接访问操作;
  2. ZONE_DMA32:和ZONE_DMA类似,主要区别在于这些页面只能被32位设备访问;
  3. ZONE_NORMAL:这个区包含的都是能正常映射的页;
  4. ZONE_HIGHEM:这个区包含“高端内存”,其中的页并不能永久地映射到内核地址空间。 区的实际使用和分布是与体系结构相关的。

区使用struct zone表示,lock域是一个自旋锁,用来防止该结构被并发访问。watermark数组持有该区的最小值、最高和最低水位值,内核使用水位为每个内存区设置合适的内存消耗基准,该水位值随空闲的内存的多少而变化。name是一个表示区名字的字符串,内核启动期间会初始化这个值。

获得页的接口

内核提供了一种请求内存的底层机制,以及对它进行访问的一组接口,所有这些接口都以页为单位分配内存,如:

  struct page * alloc_pages(…);		/* 分配连续的物理页 */
  void * page_address(struct page * pages);	/* 把给定的页转换成它的逻辑地址 */
	

(分配、释放函数,略)

slab层

空闲链表包含可供使用的、已经分配好的数据结构块,当代码需要一个新的数据结构实例时,就可以从空闲链表中抓取一个,而不需要先分配内存然后再把数据结构放进去。当不再需要这个数据结构的实例时,就把它放回空闲链表,而不是释放它。空闲链表相当于高速缓存

空闲链表的主要问题之一是不能全局控制,当可用内存变得紧缺时,内核无法通知每个空闲链表让其收缩缓存的大小以便释放一些内存出来,因为内核根本就不知道存在任何空闲链表。Linux内核提供slab层用来解决该缺陷。

slab层把不同的对象划分为高速缓存组,每个组存放不同类型的对象,如一个高速缓存组用于存放进程描述符,另一个用于存放索引节点对象(inode)。每个高速缓存由多个slab组成,一般情况下slab仅仅由一页组成。每个高速缓存都使用kmem_cache结构表示,该结构包含3个链表:slabs_full(满)、slabs_partial(部分满)、slabs_empty(空)。

内核栈

内核栈小而且固定。每个进程的内核栈大小既依赖体系结构,同时也与内核编译时的选项有关,通常为两页的大小。每个进程的整个调用链必须放在自己的内核栈中,不过中断处理程序也会使用它们所中断的进程的内核栈,这样中断处理程序也要放在内核栈中,这会使内核栈附加更严格的约束条件。为此在2.6的早期加入一个设置单页内核栈的选项,激活时,每个进程的内核栈只有一页,而中断处理程序将使用专门的中断栈。

虚拟文件系统

虚拟文件系统(VFS)作为内核子系统为用户空间程序提供了文件和文件系统相关的接口,通过虚拟文件系统,程序可以使用标准的Unix系统调用对不同的文件系统,甚至不同介质上的文件系统进行读写操作(即用户可以直接使用open()、read()、write()等系统调用,而无需考虑具体文件系统和实际物理介质)。之所以可以使用这种通用接口,是因为内核在它的底层文件系统接口上建立了一个抽象层,使Linux能够支持各种文件系统。

Linux在标准内核中已支持的文件系统超过60种(包括本地文件系统和网络文件系统),VFS层提供给这些不同文件系统一个统一的实现框架,而且也提供了能和标准系统调用交互工作的统一接口。

Unix文件系统

从本质上讲文件系统是特殊的数据分层存储结构,它包含文件、目录和相关的控制信息。Unix使用了4种和文件系统相关的传统抽象概念:文件、目录、索引节点、安装点(mount point)。

在Unix中目录属于普通文件,它列出包含在其中的所有文件,由于VFS把目录当做文件对待,所以可以对目录执行和文件相同的操作。

Unix系统将文件的相关信息和文件本身这两个概念加以区分,例如访问控制权限、大小、拥有者、创建时间等信息。文件相关信息,有时被称为文件的元数据,被存储在一个单独的数据结构中,该结构被称为索引节点(inode)。文件系统的控制信息存储在超级块中。

Unix文件系统在磁盘中的布局也按照上述概念实现,如在磁盘中,文件(包括目录)信息按照索引节点的形式存储在单独的块中;控制信息被集中存储在磁盘的超级块中。Linux的VFS的设计目标就是要保证能与支持和实现了这些概念的文件系统协同工作,比如支持像FAT、NTFS这样的非Unix风格的文件系统。

VFS对象

VFS使用一组数据结构来代表通用文件对象,这些结构体包含数据的同时也包含操作这些数据的函数指针,其中的操作函数由具体文件系统实现。一共有四个主要的VFS对象:

  1. 超级块对象,代表一个具体的已安装文件系统;
  2. 索引节点对象,代表一个具体文件;
  3. 目录项对象,代表一个目录项,是路径的一个组成部分;(不是目录对象,VFS中将目录作为文件来处理)
  4. 文件对象,代表由进程打开的文件;

超级块对象

各种文件系统都必须实现超级块对象,该对象用于存储特定文件系统的信息,通常对应于存放在磁盘特定扇区中的文件系统超级块或文件系统控制块。对于并非基于磁盘的文件系统,它们会在使用现场创建超级块,并将其保存到内存中。超级块对象用super_block结构体表示。在文件系统安装时,会调用alloc_super()函数以便从磁盘读取文件系统超级块,并且将其信息填充到内存中的超级块对象中。

索引节点对象

索引节点对象包含了内核在操作文件或目录时需要的全部信息(如用户、用户组、文件大小、最后访问时间、访问权限等等),这些信息可以从磁盘索引节点直接导入。由struct inode表示,索引节点仅当文件被访问时,才在内存中创建,一个索引节点代表文件系统中的一个文件,它也可以是设备或者管道这样的特殊文件。

目录项对象

VFS把目录当做文件对待,所以在路径/bin/vi中,bin和vi都属于文件,bin是特殊的目录文件,而vi是一个普通文件,路径中的每个组成部分都由一个索引节点对象表示。为了方便目录查找和路径解析等操作,VFS引入了目录项的概念,由detry结构体表示。每个detry代表路径中的一个特定部分,如/、bin和vi都属于目录项对象,前两个是目录,最后一个是普通文件。目录项对象没有对应的磁盘数据结构,VFS根据字符串形式的路径名现场创建它。为提高效率,目录项对象提供了缓存功能。detry结构体中的d_inode域指向目录项相关联的索引节点。

文件对象

文件对象表示进程已打开的文件,是已打开的文件在内存中的表示。由open()系统调用创建,由close()系统调用撤销。因为多个进程可以同时打开和操作一个文件,所以同一个文件也可能存在多个对应的文件对象。文件对象仅仅在进程观点上代表已打开的文件,它反过来指向目录项对象(的索引节点),只有目录项对象才表示已打开的实际文件。虽然一个文件对应的文件对象不是唯一的,但对应的索引节点及目录项对象则是唯一的。文件对象由file结构体表示,f_detry域指向对应的目录项。

和进程相关的数据结构

系统中的每一个进程都有自己的一组打开的文件,如根文件系统、当前工作目录、安装点等。如下结构将VFS层和系统的进程紧密联系在一起:

  1. file_struct:进程描述符中的files目录项指向该结构,所有与单个进程相关的信息,如打开的文件及文件描述符都包含在其中。
  2. fs_struct:进程描述符的fs域指向该结构,它包含文件系统和进程相关的信息,如当前进程的当前工作目录和根目录。
  3. namespace:进程描述符中的mmt_namespace域指向该结构,它使得每一个进程在系统中都看到唯一的安装文件系统,不仅是唯一的根目录,而且是唯一的文件系统层次结构。在大多数系统上只有一个命名空间,不过CLONE_NEWS标志可以使这一功能失效。

块I/O层

字符设备

字符设备按照字节流的方式被有序访问,比如串口、键盘等。

块设备

能够随机访问(数据顺序在设备上不一定要连续)访问固定大小数据片的硬件设备称为块设备,这些固定大小的数据片就称为块。块设备都是以安装文件系统的方式使用的。常见的块设备有硬盘、蓝光光驱、闪存等。 内核管理块设备比管理字符设备复杂得多,因为字符设备仅仅需要控制一个位置,即当前位置,而块设备访问的位置必须能够在介质的不同区间前后移动。事实上内核不必提供一个专门的子系统来管理字符设备,但是对块设备的管理却必须要有一个专门的提供服务的子系统。

扇区

块设备中最小的可寻址单元为扇区,块设备无法对比它还小的单元进行寻址和操作。扇区大小是设备的物理属性,一般为2的整数倍,通常为512字节。 块是文件系统的一种抽象,只能基于块来访问文件系统。虽然物理磁盘的寻址是按照扇区级进行的,但是内核执行的所有磁盘操作都是按照块进行的,块通常数倍于扇区大小,且不能超过一个页的长度。

缓冲区头

在读入后或等待写出时,一个块会被调入内存,并存储在一个缓冲区中,每个缓冲区与一个块对应,它相当于是磁盘块在内存中的表示。每个缓冲区都有一个对应的描述符,用buffer_head结构体表示,称作缓冲区头。缓冲区头的目的在于描述磁盘块和物理内存缓冲区之间的映射关系。

bio结构体

内核中块I/O操作的基本容器由bio结构体表示,该结构体代表了正在现场的(活动的)以片段链表形式组织的块I/O操作。一个片段是一小块连续的内存缓冲区。通过片段来描述缓冲区,即使一个缓冲区分散在内存的多个位置上,bio结构体也能对内核保证I/O操作的执行。每一个块I/O请求都通过一个bio结构体表示,每个请求包含一个或多个块,这些块被存储在bio结构体的bio_vec域中。

请求队列

块设备将它们挂起的I/O请求保存在请求队列中,该队列由request_queue结构体表示。内核中的高层代码,如文件系统将请求加入到队列中,只要队列不为空,队列对应的块设备驱动程序就会从队列头获取请求,然后将其送入对应的块设备上去。队列中的请求由结构体request表示,因为一个请求可能要操作多个连续的磁盘块,所以每个请求可以由多个bio结构体组成。

I/O调度程序

在内核中负责提交I/O请求的子系统称为I/O调度程序,内核不会简单地以产生请求的次序直接将请求发向块设备,这样性能太差。为了优化寻址操作,内核在提交请求前会先执行合并、排序等预操作:将请求队列中挂起的请求合并、排序。I/O调度程序的工作就是管理块设备的请求队列,它决定队列中的请求排序顺序以及在什么时刻派发请求到块设备以此减少磁盘寻址时间,从而提高全局吞吐量。合并指将两个或多个请求结合成一个新请求,排序则是一种类似电梯调度的算法(实际的磁盘调度算法有多种,如Linus电梯、最终期限I/O、预测I/O调度等,略)。

进程地址空间

内核除了管理本身的内存外,还必须管理用户空间中进程的内存,这个内存即进程地址空间。 Linux采用虚拟内存技术,系统中的所有进程之间以虚拟方式共享内存,对一个进程而言它好像可以访问整个系统的所有物理内存。

地址空间

进程可寻址的虚拟内存组成了进程的地址空间,内核允许进程使用这种虚拟内存中的地址。

平坦地址空间

每个进程都有一个32位或者64位的平坦(flat)地址空间,具体大小取决于体系结构。平坦指地址空间范围是一个独立的连续空间,如0~4294967295(2^32)。因为每个内存都有唯一的平坦地址空间,所以一个进程的地址空间与另一个进程的地址空间即使有相同的内存地址,实际上也彼此互不相干。

内存区域

尽管一个进程可以寻址4GB的虚拟内存,但这并不代表它有权访问所有的虚拟地址。可被访问的合法地址空间称为内存区域(memory areas),通过内核,进程可以给自己的地址空间动态地添加或减少内存区域。进程只能访问有效内存区域内的内存地址,每个内存区域也具有相关权限属性(可读、可写、可执行)。如果一个进程访问了不在有效范围内的内存地址,或者以不正确的方式访问了有效地址,那么内核就会终止该进程,并返回段错误信息。

内存区域可以包含进程的各种内存对象

如:

  • 代码段:可执行文件代码的内存映射;
  • 数据段:可执行文件的已初始化全局变量的内存映射;
  • BSS段:未初始化全局变量的内存映射,页面中的信息全部为0;
  • 进程的用户空间栈(不同于进程内核栈);
  • 共享库(C库、动态链接库等)的代码段、数据段、bss段;
  • 任何内存映射文件;
  • 任何共享内存段;
  • 任何匿名的内存映射,比如通过malloc()分配的内存;

内存描述符

内存描述符用来表示进程的地址空间,用mm_struct表示,start_code、end_code分别表示代码段的起始、结束地址,start_data、end_data分别表示数据段的起始、结束地址,等等。mm_struct通过allocate_mm()宏从slab缓存中分配得到。

在进程描述符task_struct中,mm域存放该进程的内存描述符。fork()函数利用copy_mm()函数复制父进程的内存描述符给其子进程。如果父进程希望和子进程共享地址空间,可以在调用clone()时设置CLONE_VM标志,这种进程称为线程:是否共享地址空间几乎是进程和Linux中所谓线程本质上唯一的区别。

内核线程没有进程地址空间,也没有相关的内存描述符,所以内核线程对应的进程描述符中mm域为空。内核线程不需要访问任何用户空间的内存。

虚拟内存区域

内存区域由vm_area_struct结构体表示,描述了指定地址空间内连续区间上的一个独立内存范围。内核将每个内存区域作为一个单独的内存对象管理,每个内存区域都有一致的属性,比如访问权限等,相应的操作也都一致。vm_start、vm_end分别用来表示内存区域的首、尾地址,内存区域的位置就在[vm_start,vm_end]之间。vm_mm域指向对应的mm_struct,所以两个独立的进程将同一个文件映射到各自的地址空间,它们分别都会有一个vm_area_struct来标志自己的内存区域,而如果两个线程共享一个地址空间,那么它们也同时共享其中所有的vm_area_struct结构体。

VMA标志

VMA标志包含在vm_area_struct的vm_flags域内,是一种位标志,表示内存区域所包含的页面的行为和信息。反映了内核处理页面所需要遵守的行为准则,而不是硬件要求,如VM_READ、VM_WRITE、VM_EXEC分别标志了内存区域中页面的读、写和执行权限。当访问内存区域时,需要查看其访问权限,比如只读文件数据段的映射区域仅标志为VM_READ,而进程的代码映射区则会标志为VM_READ和VM_EXEC。

查看进程地址空间中的全部内存区域 cat /proc//maps 如:vi test 然后用ps -aux查看pid: ![image](/images/tech/linux_3.png)

用pid查看该进程的所有内存区域: image

操作内存区域

find_vma():找到一个给定的内存地址属于哪一个内存区域; do_mmap():创建一个新的线性地址区间,如果所创建的地址区间和一个已存在的地址区间相邻,并且它们具有相同的访问权限,则两个区间将合并为一个; do_mummap():从特定的进程地址空间中删除指定地址区间;

页表

当程序访问一个虚拟地址时,必须将其转化为物理地址,然后处理器才能解析地址并访问请求。地址的转换工作需要通过查询页表才能完成:将虚拟地址分段,使每段虚拟地址都作为一个索引指向页表,而页表项则指向下一级别的页表或指向最终的物理页面。Linux中使用三级页表完成地址转换: image

页高速缓存和页回写

页高速缓存是Linux内核实现的磁盘缓存,通过把磁盘中的数据缓存到物理内存中,以此减少对磁盘的I/O操作。页高速缓存由内存中的物理页组成,其内容对应磁盘上的物理块。页高速缓存大小能动态调整。Linux页高速缓存使用address_space结构体管理。

页回写则是将高速缓存中的变更数据刷新回磁盘的操作。程序执行写操作直接写到缓存中,后端存储(磁盘、块设备文件等等)不会立即直接更新,而是将页高速缓存中被写入的页面标记成“脏”,并且被加入到脏页链表中,然后由一个进程(回写进程)周期性地将脏页链表中的页写回到磁盘。

之所以要使用磁盘高速缓存,主要源自两个因素: 访问磁盘的速度要远远低于访问内存的速度:ms和ns的差距; 数据一旦被访问,就很可能在短期内再次被访问到:临时局部原理;

flusher线程

在2.6中由一群内核线程(flusher线程)负责将内存中累积的脏页写回磁盘。当以下情况发生时,脏页会被写回:

  • 当空闲内存低于一个特定的阈值时;
  • 当脏页在内存中驻留时间超过一个特定的阈值时;
  • 当用户进程调用sync()和fsync()系统调用时;

设备与模块

设备类型

在Linux中,设备被分为以下三种类型:

  • 块设备:可寻址,寻址以块为单位,块大小取决于设备。通常支持对数据的随机访问,如硬盘、蓝光光碟、闪存等。通过称为“块设备节点”的特殊文件来访问,通常被挂载为文件系统。
  • 字符设备:不可寻址,仅提供数据的流式访问,即一个个字符或一个个字节,如键盘、鼠标、打印机等。通过称为“字符设备节点”的特殊文件来访问,与块设备不同,应用程序通过直接访问设备节点与字符设备交互。
  • 网络设备:通过一个物理适配器和一种特定的网络协议提供了对网络的访问,打破了Unix所有东西都是文件的设计原则,不是通过设备节点来访问,而是通过套接字API这样的特殊接口来访问。

伪设备

并不是所有设备驱动都表示物理设备,有些设备驱动是虚拟的,仅提供访问内核功能而已,被称为“伪设备”,如内核随机数发生器(/dev/random)、空设备(/dev/null)、零设备(/dev/zero)等等。

模块

Linux内核是模块化组成的,允许在运行时动态地向其中插入或删除代码,这些代码被组合在一个单独的二进制镜像中,即所谓的可装载内核模块,简称模块。支持模块的好处是基本内核镜像可以尽可能地小,因为可选的功能和驱动程序可以利用模块形式再提供。

(编写自己的内核模块,略)

调试

(略)

可移植性

(略)

补丁、开发和社区

(略)


文章目录