1、Linux系统系统1Linux系统系统主要内容主要内容 Linux系统概述系统概述Linux系统系统 Linux系统概述系统概述 Linux系统是一个类系统是一个类UNIX的操作系统，与的操作系统，与UNIX完全兼容，完全兼容， 在操作系统功能、使用方法等方面极为相似。在操作系统功能、使用方法等方面极为相似。 Linux是一个多用户、多任务操作系统 源代码编写方式源代码编写方式 商业模式商业模式 开发模式开发模式 2Linux系统系统 Linux系统概述系统概述 单体结构内核单体结构内核 可抢占式内核可抢占式内核 多线程应用程序的支持多线程应用程序的支持 多处理机支持多处理机支持 支持多种文件
2、系统支持多种文件系统 Linux操作系统包括Linux内核，还包括shell、带有多窗口 管理器的 X-Windows图形用户接口、文本编辑器、高级语 言编译器等应用软件。 3Linux系统系统 Linux系统概述系统概述 Linux内核包含最基础、最核心的概念，提供系统其他部 分必须的服务支持。 组成组成进程调度程序、主存管理程序负责网络、进程间通信的服务程序中断处理程序和设备驱动等核心服务程序4Linux系统系统 Linux系统概述系统概述5系系 统统 调调 用用 界界 面面程程 序序 库库进程通信进程通信进程调度进程调度存储管理存储管理文件子系统文件子系统高速缓冲高速缓冲字符设备字符设备
3、 块设备块设备 设备驱动程序设备驱动程序用户程序用户程序 硬硬 件件 控控 制制 硬硬 件件 用户级用户级核心级核心级硬件层硬件层进程管理与存储管理进程管理与存储管理网络管理网络管理网络协议网络协议网络驱动网络驱动Linux系统的核心结构示意图Linux系统系统 Linux系统概述系统概述 Linux系统的特权级与中断处理系统的特权级与中断处理Linux系统系统 Linux系统的特权级与中断处理系统的特权级与中断处理6Linux系统使用两个级别 (处理机提供四个特权级) ：特权级0 核态 (内核模式)特权级3 用户态 (用户模式)Linux系统系统 Linux系统的特权级与中断处理系统的特权级
4、与中断处理为提高中断处理的效率，中断处理程序的执行必须快速、简洁。为此，Linux系统将中断处理程序分为两部分。将中断响应后必须立即处理的工作即刻执行，这就是中断处理程序的上半部 (tophalf)。将更多的处理工作向后推迟执行，这就是中断处理程序序的下半部(bottom half)。7上半部是中断处理中有严格时间限制的工作，是关键而 紧迫的部分;上半部的工作是不可被打断的，即在屏蔽所有中断的情 况下进行的。例：与硬件设备应答或使硬件复位的工作。下半部处理那些可以稍后完成的工作； 下半部的执行是可以打断的，即是在开中断的情况下执 行。Linux系统系统 Linux系统的特权级与中断处理系统的特
5、权级与中断处理8 Linux系统中，用于实现实现将工作推后执行的内核机制称为 “下半部机制”，下半部机制主要有tasklet和工作队列两种。 tasklet通过软中断实现通过软中断实现 一个软中断被标记后才能执行，称为触发软中断。 待处理的软中断会在以下时机被检查和执行：从一个硬件中断返回时；在ksoftirqd内核线程中；在显示检查和执行待处理的软中断的代码中。Linux系统系统 Linux系统的特权级与中断处理系统的特权级与中断处理9 Tasklet软中断软中断 tasklet的软中断表示是的软中断表示是TASKLET_SOFTIRQ； Taskle由结构体由结构体tasklet_stru
6、ct结构表示结构表示 struct tasklet_struct struct tasklet_struct *next; /* 链表中的下一个taskle */ unsignet long state; /* taskle的状态 */ atomic_t count; /* 引用计数器 */ void (*func) (unsigned long); /* taskle的处理函数 */ unsigned long data; /* 给taskle处理函数的参数 */ tasklet由由tasklet_schedule()函数调度函数调度 Linux系统系统 Linux系统的特权级与中断处理系统
7、的特权级与中断处理10 工作队列机制将中断处理程序的下半部交给一个内核线 程去执行。 下半部是在进程上下文 (用户地址空间)执行，可以睡眠和 被重新调度。 注：这一点与上述的tasklet不同。如果下半部工作需要睡 眠 (如需要执行阻塞式I/O操作时，或要等待信号灯)时应 选择工作队列机制；否则可选择tasklet机制。Linux系统系统 Linux系统的特权级与中断处理系统的特权级与中断处理11 工作者线程工作者线程 该线程接收由各内核中断处理程序交给它的下半部。 该线程内核线程实现的。执行的函数是 work_thread()， 对应的数据结构是工作队列链表。 工作队列链表工作队列链表 由若
8、干个work_struct结构组成。 work_struct结构Linux系统系统 Linux系统的特权级与中断处理系统的特权级与中断处理12 work_struct结构 每个work_struct结构描述如下 struct work_struct unsigned long pending; /* 该工作正在等待处理？*/ struct list_head entry; /* 勾链字 */ void (*func) (void *); /* 该工作的处理函数 */ void *data; /* 传递该该处理函数的参数 */ void *wq_data; /* 内部使用 */ struct t
9、imer_list timer; /* 延迟的工作队列所用的定时器 */ Linux系统系统 Linux系统的特权级与中断处理系统的特权级与中断处理13 执行函数执行函数work_threadwork_thread()() 执行一个死循环； 若工作队列链表不空时，执行链表上的所有工作。工 作被执行完毕，它就将相应的work_struct对象从链表 上移走； 当链表为空时，它进入睡眠状态； 当有下半部插入到队列时，函数是work_thread() 被唤醒，将继续处理新加入的下半部 。Linux系统系统 Linux系统的特权级与中断处理系统的特权级与中断处理Linux系统的系统的功能调用功能调用L
10、inux系统系统Linux系统功能调用系统功能调用14在Linux系统中，系统调用通过异常类型实现；当执行了int 0 x80指令而发生的软件中断；系统自动将用户态切换为核心态来处理该事件，执行自陷处理程序 (系统调用处理程序)。 Linux系统系统Linux系统功能调用系统功能调用15 abc(); abc(); syscall; system_call: sys_abc SYSEXITsysabc() 用户态用户态核心态核心态用户程序系统调用 在libc标准库中的封装例程系统调用处理程序系统调用服务例程Linux系统调用过程Linux系统系统Linux系统功能调用系统功能调用16int m
11、ain() getuid(); int getuid(void) long_res; int $0 x80; ENTRY(system_call) pushl % esx SAVE_ALL GET_CURRENT(%ebx) call sys_getuid16 RESTORE_ALLasmlinkage longsys_getuid16(void) return high2lowuid (current_uid);用户程序用户程序系统调用处理程序系统调用处理程序标准标准C库库内核例程内核例程getuid系统调用过程Linux系统系统Linux系统功能调用系统功能调用17 Linux系统的软中断
12、指令是系统的软中断指令是int 0 x80汇编语言指令汇编语言指令 该指令的执行会发生中断该指令的执行会发生中断 处理机的状态由用户态自陷到内核态处理机的状态由用户态自陷到内核态 从从system_call()开始执行系统调用处理程序。开始执行系统调用处理程序。 当系统调用处理完毕后，通过当系统调用处理完毕后，通过iret汇编语言指令返回到用汇编语言指令返回到用 户态。户态。Linux系统系统Linux系统功能调用系统功能调用18 linux中，每个系统调用被赋予一个唯一的系统调用号 系统调用号定义在include/asm-i386/unistd.h头文件中 系统调用号格式如下 #define
13、 _NR_restart_syscall 0 #define _NR_exit 1 #define _NR_fork 2 #define _NR_read 3 #define _NR_write 4 #define _NR_open 5 #define _NR_mq_getsetattr 282 Linux系统系统Linux系统功能调用系统功能调用19 系统调用表记录了内核中所有已注册过的系统调用， 它是系统调用的跳转表。 系统调用表是一个函数指针数组，表中依次保存所有 系统调用的函数指针 Linux系统调用表保存在arch/i386/kernel/下的entry.S中Linux系统系统Lin
14、ux系统功能调用系统功能调用20 系统调用表格式如下系统调用表格式如下 ENTRY(sys_call_table) .long sys_restart_syscall /* 0 */ .long sys_exit /* 1 */ .long sys_fork /* 2 */ .long sys_read /* 3 */ .long sys_write /* 4 */ .long sys_open /* 5 */ .long sys_mq_getsetattr /* 282 */ Linux系统系统Linux系统功能调用系统功能调用21系统调用处理程序是系统调用处理程序是system_call(
15、)，主要工作如下，主要工作如下宏SAVE_ALL保护现场； 正确性检查 ；依eax中所包含的系统调用号，调用其对应的服务例 程；系统服务例程结束时，通过宏RESTORE_ALL恢复寄 存器；最后通过iret指令返回。 Linux系统系统Linux系统功能调用系统功能调用22 在/usr/src/linux/kernel/sys.c文件中增加一个新的函数， 该函数的名字是sys_mysyscall 例：例：一个简单的系统调用，其功能是返回一个整型值 asmlinkage int sys_mycall(int number) return number; Linux系统系统Linux系统功能调用系
16、统功能调用23 在文件在文件include/asm-i386/unistd.hinclude/asm-i386/unistd.h中添加一项中添加一项 #define _NR_mysyscall XX XX XX为新增加的系统调用号，此数字选一未用值为新增加的系统调用号，此数字选一未用值。 例例 #define _NR_restart_syscall 0 #define _NR_exit1 #define _NR_mq_getsetattr 282 #define _NR_mysyscall 283 Linux系统系统Linux系统功能调用系统功能调用24 在文件/arch/i386/kerne
17、l/entry.S中的系统调用表sys_call_table中添加新增的系统调用sys_call_table数组包含指向内核中每个系统调用的指针 例例 ENTRY(sys_call_table) .long sys_restart_syscall /* 0 */ .long sys_exit /* 1 */ .long sys_mq_getsetattr /* 282 */ .long sys_mysyscall /*283*/Linux系统系统Linux系统功能调用系统功能调用25 为使新的系统调用生效，需要重建Linux的内核。 这需要以超级用户身份登录后重新编译内核。 在用户程序中，测试
18、新增加的系统调用是否能正确使用。Linux系统系统Linux系统功能调用系统功能调用Linux系统的系统的进程管理进程管理Linux系统系统Linux系统的进程管理系统的进程管理26 进程是程序在处理机上的一次执行过程。进程是处于执行 期的程序，它是分配系统资源和调度的实体。 进程包括可执行的程序代码、打开的文件、挂起的信号、 内核数据、地址空间、处理机状态、一个或多个可执行 的线程等。 Linux系统将线程看作是一种特殊的进程。线程被视为一 个与其他进程共享某些资源的进程。 Linux系统系统Linux系统的进程管理系统的进程管理27Linux内核使用进程描述符 (又称为进程控制块)来描述一
19、个 进程的完整信息。Linux系统系统Linux系统的进程管理系统的进程管理28指向进程基本控制块的指针进程状态state进程标识进程调度有关的字段进程亲属关系的字段指向当前目录的指针指向文件描述符的指针指向主存描述符的指针指向信号结构的指针指向tty结构的指针task_structthread_info当前目录文件描述符主存描述符所接收的信号与进程相关的tty指向进程队列priopidtgidpgrpsessinthread_inforun_listttyreal_parentparentchildrensiblingfsfilesmmsignal进程控制块的结构进程控制块的结构进程控制块结
20、构29 进程标识符进程标识符 进程标识符process ID 进程描述符中的标识符字段字段名字段名说明说明pid进程的PIDtgid线程组领头进程的PIDpgrp进程组领头的进程PIDsession会话领头进程的PIDLinux系统系统Linux系统的进程管理系统的进程管理30 进程状态进程状态 反映进程当前状态，包括以下几种可能的状态 可运行状态 TASK_RUNNING 可中断的等待状态 TASK_INTERRUPTIBLE 不可中断的等待状态 TASK_UNINTERRUPTIBLE 暂停状态 TASK_STOPPED 终止状态 TXIT_ZOMBIELinux系统系统Linux系统的进
21、程管理系统的进程管理31 进程基本信息进程基本信息 每个进程都有一个进程基本信息块。在进程描述符的thread_info字段中包含了指向该结构的指针 与进程调度有关的信息与进程调度有关的信息 可运行进程链表 (最多可有140个) 进程的亲属关系进程的亲属关系 进程描述符中的亲属关系字段字段名字段名说明说明real_parent指向创建p进程的父进程的描述符，若该父进程不再存在，就指向1#进程parent指向p进程的当前父进程，它的值通常与real_parent一致，偶尔也可不同children链表的头部，链表中的所有进程都是p进程创建的子进程sibling指向兄弟进程链表中的下一个或前一个元素
22、的指针Linux系统系统Linux系统的进程管理系统的进程管理32 其他字段其他字段 在进程描述符的thread_info字段中包含了指向各种结构的 指针。 fs 指向当前目录结构 fs_steuct files 指向文件描述符结构 files_struct mm 指向主存描述符结构 mm_struct signal 指向信号结构 signal_struct tty 指向进程相关的 tty_struct结构Linux系统系统Linux系统的进程管理系统的进程管理33 它或者正在执行，运行状态它或者正在执行，运行状态 或者在运行队列中等待执行，就绪状态或者在运行队列中等待执行，就绪状态 进程正在
23、等待某一事件的发生(如某一硬件中断或一个信 号)，它处于挂起或称睡眠状态。 除了不会因为接收到信号而被唤醒从而投入运行外，这个 状态与可中断等待状态相同。Linux系统系统Linux系统的进程管理系统的进程管理34 表示进程已经结束，但其父进程还没有调用wait4()系统 调用。子进程的进程描述符在此之前仍然被保留 表示进程停止执行，进程没有投入运行也不能投入运行。 通常这种状态发生在接收到SIGSTOP、SIGTSTP、 SIGTTIN、SIGTTOU等信号的时候。Linux系统系统Linux系统的进程管理系统的进程管理35 运行运行TASKUNNING进程调度等待某事件等待的事件发生 创建
24、创建新进程新进程 就绪就绪TASKUNNING 进程进程 终止终止 等待等待TASKINTERRUPTIBLETASKUNINTERRUPTIBLE被抢占创建进程完成Linux系统进程状态变迁图Linux系统系统Linux系统的进程管理系统的进程管理36 Linux系统用fork()系统调用创建一个进程。 写时拷贝写时拷贝 在创建新进程时内核不复制父进程的整个地址空间， 而是让父进程和子进程以读方式共享同一拷贝 只有当一方真正需要写入时，数据才被复制，这时， 父、子进程才拥有各自的拷贝 系统提供系统提供fork()和和clone()系统调用系统调用 fork()用来创建一般进程 clone()
25、用来创建轻量级进程 (线程) Linux系统系统Linux系统的进程管理系统的进程管理37 Linux系统提供exit()系统调用以终止某一个进程。其主要 功能由do_exec()函数完成。 进程终止后，此进程处于僵死状态，但系统还保留了它的 进程描述符。只有父进程发出了与被终止进程相关的 wait()系统调用后，子进程的task_struct结构才能释放。 Linux系统系统Linux系统的进程管理系统的进程管理38 两种等待状态两种等待状态 TASK_INTERRUPTIBLE 和 TASK_UNINTERRUPTIBLE 区别：处于TASK_UNINTERRUPTIBLE状态的进程如果接
26、收到一个信 号会被提前唤醒并响应该信号，而处于TASK_INTERRUPTIBLE状态 的进程会忽略信号。 进程等待的主要步骤进程等待的主要步骤 调用declare_waitqueue()创建一个等待队列的元素。 调用add_wait_queue()将该元素加入到等待队列。 进程的状态设置为TASK_INTERRUPTIBLE状态 TASK_UNINTERRUPTIBLE状态。 转进程调度程序schedule() 。 Linux系统系统Linux系统的进程管理系统的进程管理39 进程唤醒的主要步骤进程唤醒的主要步骤 当进程状态设置为TASK_INTERRUPTIBLE，则由信号唤醒进程， 这是
27、所谓的伪唤醒 (不是直接由所等待的事件唤醒)，因此需要检 查并处理信号。 若检查条件为真 (所等待的事件发生)，转；若条件不为真，转进 程调度schdule()。 当进程被唤醒时 (因事件发生)，检查条件是否为真，若为真转； 否则转进程调度schdule()。 当条件满足时，进程状态设置为 TASK_RUNNING，并将该进程 移出等待队列。 该函数将进程状态设置为TASK_RUNNING，再将此进程加入到 可执行队列。若被唤醒进程的优先级比当前正在运行的进程的优 先级高，设置need_resched标志。 Linux系统系统Linux系统的进程管理系统的进程管理Linux系统的系统的进程调度
28、进程调度Linux系统系统Linux系统的进程调度系统的进程调度40 进程调度程序是内核的组成部分，负责选择下一个要运 行的进程。进程调度可看作在可运行态进程之间分配有限的处理器 时间资源的内核子系统。进程调度程序是如Linux这样的多任务操作系统的基础。 基于动态优先级和可变时间的调度基于动态优先级和可变时间的调度 调度方式为可抢占式调度调度方式为可抢占式调度Linux系统系统Linux系统的进程调度系统的进程调度41 实现算法复杂度为实现算法复杂度为O(1)级的调度级的调度 进程调度算法保证在恒定的时间内完成 算法执行时间与系统中处于就绪 (可运行)状态的进程个 数无关 提高交互性能提高交
29、互性能提高交互性能，保证系统能快速响应 保证公平保证公平 在合理设定的时间范围内，没有进程会出现饥饿状态 也不会有进程获得大量的时间片 实现实现SMP可扩展性可扩展性Linux系统系统Linux系统的进程调度系统的进程调度42 I/O消耗型进程消耗型进程 大部分时间是使用外部设备，交互式进程具有此特征。 处理器消耗型进程处理器消耗型进程 大部分时间是使用CPU，计算进程具有此特征。 交互式的程序都是I/O消耗型的。 Linux为了保证交互式应用，优化了进程的响应，更倾向 于优先调度I/O消耗型进程，但并未忽略处理器消耗型程 序。Linux系统系统Linux系统的进程调度系统的进程调度43 Li
30、nux系统实现了基于进程过去行为的启发式算法；系统实现了基于进程过去行为的启发式算法； Linux系统选择优先级高的进程先运行，相同优先级的进系统选择优先级高的进程先运行，相同优先级的进 程按循环方式调度；程按循环方式调度； 动态优先级依进程占有动态优先级依进程占有CPU的情况、休眠时间的长短来的情况、休眠时间的长短来 增、减增、减 ； 系统根据进程优先级调整分配给它的时间片；系统根据进程优先级调整分配给它的时间片； 实施可抢占调度方式实施可抢占调度方式 Linux系统系统Linux系统的进程调度系统的进程调度44 优先级高的进程先运行，低的后运行，相同优先级的进程 按轮转方式进行调度。 静态
31、优先级的确定静态优先级的确定 在进程创建时，新创建的进程继承 父进程的静态优先级 静态优先级的取值范围静态优先级的取值范围 100 (最高优先级) 139 (最低 优先级)，取值越小，优先级越高; 静态优先级的改变静态优先级的改变 用户可以通过系统调用改变nice值， 从而改变自己拥有的静态优先级。Linux系统系统Linux系统的进程调度系统的进程调度45 每个进程有一个动态优先级每个进程有一个动态优先级 它是进程调度程序选择可运 行进程所使用的参数，其取值范围是100 (最高优先级) 139 (最低优先级) 动态优先级的计算动态优先级的计算 动态优先级动态优先级 = max(100，min
32、(静态优先级静态优先级 bonus + 5，139) bonus是范围 0 10的值， 值小于5表示降低动态优先级以示惩罚 值大于5表示增加动态优先级以示奖励 进程调度使用的是动态优先级，通过effective_prio( )函数 来计算一个进程的动态优先级。Linux系统系统Linux系统的进程调度系统的进程调度46 依据依据 进程睡眠时间的长短进程睡眠时间的长短 若进程睡眠时间长 若进程睡眠时间短 方法方法 Linux记录进程睡眠和执行时间 (存放在task_struct的 sleep_avg域中)，范围：0 MAX_SLEEP_AVG，默认值 为10ms 当当进程从开始休眠到要恢复执行这
33、一时间内sleep_avg 增加，直到达到MAX_SLEEP_AVG为止； 进程每执行一个时钟节拍， sleep_avg递减直到0为止。 Linux系统系统Linux系统的进程调度系统的进程调度47 进程休眠时间与进程休眠时间与bonus值的关系值的关系 平均休眠时间 bonus值 大于或等于0， 小于 100ms 0 大于或等于100，小于 200ms 1 大于或等于200，小于 300ms 2 大于或等于300，小于 400ms 3 大于或等于400，小于 500ms 4 大于或等于500，小于 600ms 5 大于或等于600，小于 700ms 6 大于或等于700，小于 800ms 7
34、 大于或等于800，小于 900ms 8 大于或等于900，小于 1000ms 9 大于1s 10 Linux系统系统Linux系统的进程调度系统的进程调度48 对交互式进程，系统提供较长的时间片对交互式进程，系统提供较长的时间片 调度程序根据进程的优先级动态调整分配给它的时间片调度程序根据进程的优先级动态调整分配给它的时间片Linux系统系统Linux系统的进程调度系统的进程调度 基本时间片基本时间片 静态优先级本质上决定了进程的基本时间片 (140 静态优先级) 20 若静态优先级 120 (140 静态优先级) 5 若静态优先级 120 静态优先级越高(值越小)，基本时间片越长。基本时间
35、片 =49表6.6 普通进程的静态优先级和基本时间片的典型值说明说明静态优先级静态优先级nice值值基本时间片基本时间片最高静态优先级100-20800ms高静态优先级110-10600ms缺省静态优先级1200100ms低静态优先级130+1050ms最低静态优先级139+195ms初始创建的进程父进程的值父进程的值父进程的一半Linux系统系统Linux系统的进程调度系统的进程调度更高的优先级更高的优先级更高的交互性更高的交互性更低的优先级更低的优先级更低的交互性更低的交互性最小最小5ms默认默认100ms最大最大800ms进程静态优先级与基本时间片的关系图50 创建新进程时的处理创建新进
36、程时的处理新创建的子进程和父进程均分父进程剩余的时间片 进程用完时间片时的处理进程用完时间片时的处理 当一个进程的时间片用完时，依任务的动态优先级重 新计算时间片； task_timeslice()函数为给定任务返回一个新的时间片。Linux系统系统Linux系统的进程调度系统的进程调度 可变时间片可变时间片当一个进程的时间片用完时，根据进程的动态优先级重新计算时间片。51 一个进程拥有的时间片可分多次使用，放弃一个进程拥有的时间片可分多次使用，放弃CPU时进时进 入活动队列入活动队列 当一个进程的时间片耗尽时，认为是过期进程，进入过当一个进程的时间片耗尽时，认为是过期进程，进入过 期队列期队
37、列Linux系统系统Linux系统的进程调度系统的进程调度52 每个处理器维护两个优先级数组 活动数组和过期数组 活动数组上的可执行队列中的进程都有剩余时间片活动数组上的可执行队列中的进程都有剩余时间片 过期数组上的可执行队列中的进程都已耗尽时间片过期数组上的可执行队列中的进程都已耗尽时间片 当一个进程的时间片耗尽时，被移至过期队列中； 当活动数组上的可执行队列中的所有进程都已耗尽时时间 片，这时，在活动数组和过期数组之间切换指针。Linux系统系统Linux系统的进程调度系统的进程调度53 可执行队列是给定处理机上的可执行进程链表runqueue结构 类型 名称 说明spinlock_t l
38、ock 保护进程链表的自旋锁 prio_array_t *active 指向活动进程链表的指针prio_array_t *expired 指向过期进程链表的指针prio_array_t2 arrays 活动进程和过期进程的两个集合 Linux系统系统Linux系统的进程调度系统的进程调度54 优先级数组是 prio_array 类型的结构体，该数组描述了可 运行进程的集合，包括 140个双向链表头个双向链表头 (每个链表对应一个优先级队列) 一个进程优先级位图一个进程优先级位图 该数组所包含的进程总数该数组所包含的进程总数 struct prio_array int nr_active; /*
39、 任务数目*/ unsigned bitmapBITMAP_SIZE; /* 优先级位图*/ struct list_head queueMAX_PRIO; /*优先级队列*/ Linux系统系统Linux系统的进程调度系统的进程调度55 优先级数组图示优先级数组图示 *active*expiredarrays0arrays1 task task优先级优先级0优先级优先级139 task task优先级优先级0优先级优先级139 过期进过期进程数组程数组活动进活动进程数组程数组runqueue结构中的两个进程数组Linux系统系统Linux系统的进程调度系统的进程调度56优先级位图的处理优先级
40、位图的处理 初始时，所有位被置为0； 当某个拥有一确定优先级的进程准备运行时 (状态为 TASK_RUNNING) ，位图中相应位置1； 调度时，查找系统中优线级最高的进程就转化为查找 位图中被置为1的第一个位。 由于优先级个数是定值，所以查找时间恒定，不受系统由于优先级个数是定值，所以查找时间恒定，不受系统 中可执行进程数目的影响，使中可执行进程数目的影响，使Linux系统的进程调度算系统的进程调度算 法具有法具有O(1) 的算法复杂度。的算法复杂度。 Linux系统系统Linux系统的进程调度系统的进程调度57 当进程要休眠时当进程要休眠时 当进程被抢占时当进程被抢占时 系统发生抢占时系统
41、发生抢占时 在活动优先级数组中找到第一个被设置的位；在活动优先级数组中找到第一个被设置的位； 选择该优先级链表里的第一个进程；选择该优先级链表里的第一个进程； 调上下文切换函数调上下文切换函数context_switch( )。Linux系统系统Linux系统的进程调度系统的进程调度58位位9进程链表进程链表 优先级位图优先级位图 0 1 0 1 9位位 6位位 9位位13 位位6进程链表进程链表位位130进程链表进程链表位位130LinuxO(1)级进程调度算法图解Linux系统系统Linux系统的进程调度系统的进程调度Linux系统的系统的存储管理存储管理Linux系统系统Linux系统的
42、存储管理系统的存储管理59Linux系统处在用户态时，使用用户代码段和用户数据 段来对指令和数据寻址在核态时，使用内核代码段和内核数据段来对指令和 数据寻址每个分段是一个连续的线性地址空间，从0开始直到 2321的寻址长度。 Linux系统系统Linux系统的存储管理系统的存储管理60 80 x86微处理器的分页单元处理4KB的页。一个32位的线 性地址分为3个域。 页目录页目录 页表页表 页内位移页内位移31 22 21 12 11 0 页目录页目录字段指向页目录项； 页表页表字段指向进程的一个页表项； 页内位移页内位移则是页内偏移量 80X86分页机构Linux系统系统Linux系统的存储
43、管理系统的存储管理61 第一级第一级 全局目录全局目录 (PGD) PGD中的表项指向页目录中的一个表项 二级页表二级页表 页目录页目录 (PMD) PMD中的表项指向页表PTE中的一个表项 三级三级 页表页表 该表项指向物理页 (页框) 的主存地址 Linux系统系统Linux系统的存储管理系统的存储管理62 地址转换过程地址转换过程 Linux系统通过三级页表完成线性地址到物理地址的转换页目录页目录 页表页表 页内位移页内位移31 22 21 12 11 0cr3+：+：页目录表页目录表页表页表物理页物理页+由线性地址转换为物理地址Linux系统系统Linux系统的存储管理系统的存储管理6
44、3 地址变换步骤地址变换步骤 由cr3指示的当前页目录的物理地址与分页结构中的页 目录字段的内容相加指向页目录表项； 由页目录表项内容得到当前使用的页表的始地址，通过 分页结构中的页表字段的内容找到该页表项； 由页表项指示的该页的物理页 (页框)的主存地址与分页 结构中的页内位移相加，得到最终的物理地址。Linux系统系统Linux系统的存储管理系统的存储管理64 Linux系统主存分配的基本单位是物理页 (又称为页框) 主存管理单元MMU以页为单位进行分配和处理 32位体系结构支持4KB的页，64位体系结构支持8KB的页 内核用struct page结构描述页框 struct page fl
45、ags; /* 页的状态页的状态 */ _count; /* 该页被引用的次数该页被引用的次数 */ *virtual; /* 页的虚拟地址，记录页在虚拟主存中的地址页的虚拟地址，记录页在虚拟主存中的地址 */ ; Linux系统系统Linux系统的存储管理系统的存储管理65 内核将系统中的所有页框划分为不同的区，具有相似特 征的页框归为同一个分区。 Linux系统共分为三种分区系统共分为三种分区 ZONE_DMA 这个分区包含的页只能用来执行DMA操作，大小为16MB； ZONE_NORMAL这个分区包含的页都是能正常映射的页，大小为16MB 896MB ZONE_HIGHMEM这个分区包含
46、的是“高端主存”，其中的物理页并不能永久地映射到内核地址空间，大小为896MB。 Linux系统系统Linux系统的存储管理系统的存储管理66 Linux内核通过页框和区对主存进行管理，实现了请求 主存的底层机制； 内核提供提供一组访问接口 (函数或宏) 可以直接的方 式获得动态主存，注意这种方式只能由内核使用。 Linux系统系统Linux系统的存储管理系统的存储管理67 分区页框分配器( Zoned page frame allocator)是一个内 核子系统，它负责对连续页框的主存分配。 分区页框分配器的组成如下图 分区页框分配器的组成Linux系统系统Linux系统的存储管理系统的存储
47、管理管理区分配器管理区分配器每CPU页框 高速缓存每CPU页框 高速缓存每CPU页框 高速缓存 伙伴系统 伙伴系统 伙伴系统 ZONE_DMA 主存管理区 ZONE_NORMAL 主存管理区 ZONE_HIGHMEM 主存管理区68 主存管理中的外碎片问题主存管理中的外碎片问题 当频繁地请求和释放不同大小的连续页框，就会导致在已分配页 框内产生许多小的、分散的空闲页框； Linux系统采用伙伴系统算法记录当前空闲的连续页框块的情况， 以尽量避免为满足小块的请求而分割大的空闲块。 伙伴系统算法中页框的组织伙伴系统算法中页框的组织 将所有的空闲页框分组为11个块链表； 每个块链表分别包含大小为1、
48、2、4、8、16、32、64、128、256、 512、1024个连续页框； 每个块的第一个页框的物理地址是该块大小的整数倍。 Linux系统系统Linux系统的存储管理系统的存储管理69 以分配以分配256个页框的块为例说明伙伴系统算法的页框的个页框的块为例说明伙伴系统算法的页框的 分配过程分配过程 首先在256个页框的链表中检查是否有空闲块满足需要； 若没有，则在512个页框的链表中找满足需要的空闲块 若存在这样的块，算法将这512的页框分为2半； 一半用来满足请求，另一半插入到256个页框的链表中； 若还没有，则在1024个页框的链表中找满足需要的空闲块； 若存在，则将256块用来满足要
49、求，其余部分分为256块 和512块分别插入到相应的链表中； 若不存在；算法放弃并给出不能满足分配的信息。 Linux系统系统Linux系统的存储管理系统的存储管理70 分配过程的逆过程就是页框的释放过程分配过程的逆过程就是页框的释放过程 内核试图将大小为b 的一对空闲伙伴块合并为一个大小为 2b的单独块。满足以下条件的两个块称为伙伴： 两个块的大小相同，记为b； 它们的物理地址是连续的； 第一块的第一个页框的物理地址是2b212的倍数。 算法是迭代的，如果它成功合并所释放的块，它会试图 合并2b的块，以再次试图形成跟更大的块。 Linux系统系统Linux系统的存储管理系统的存储管理71 L
50、inux内核提供用于页框分配和释放的函数 (或宏)。这些函数只能由内核直 接使用，用户进程请求主存时不能直接使用。 当用户进程请求动态主存时，内核采用推迟分配的方法，即用户并没有获 得请求的页框，而仅仅获得对一个新的线性地址区间的使用权。 这一线性地址区间成为进程地址空间的一部分，称为“线性区”。 进程的地址空间由每个进程的线性地址区组成，是一个独 立的连续区间。 描述进程地址空间的信息存放在主存描述符中。主存描述 符由mm_struct结构体表示，进程描述符的mm字段指向这 个结构。 Linux系统系统Linux系统的存储管理系统的存储管理72 进程的地址空间由若干个线性区组成； 线性区域
