操作系统第9章Linux系统课件

第9章Linux系统Linux系统Linux系统Linux系统概述Linux的特权级与中断处理Linux系统功能调用Linux系统的进程管理Linux系统的存储管理Linux系统的设备驱动Linux文件系统1Linux系统——主要内容Linux系统概述1Linux系统——主要内容

Linux系统概述Linux系统——Linux系统概述Linux系统——Linux系统概述1.Linux系统的定义Linux系统是一个类UNIX的操作系统，与UNIX完全兼容，在操作系统功能、使用方法等方面极为相似。(1)什么是Linux操作系统Linux是一个多用户、多任务操作系统(2)Linux与UNIX操作系统的不同点①源代码编写方式②

商业模式③

开发模式2Linux系统——Linux系统概述1.Linux系统的定义2Linux系统——Linux(4)Linux系统的特点①

单体结构内核②

可抢占式内核③

多线程应用程序的支持④

多处理机支持⑤

支持多种文件系统(3)Linux系统的组成

Linux操作系统包括Linux内核，还包括shell、带有多窗口管理器的X-Windows图形用户接口、文本编辑器、高级语言编译器等应用软件。

3Linux系统——Linux系统概述(4)Linux系统的特点(3)Linux系2.Linux系统的内核结构(1)Linux内核的组成

Linux内核包含最基础、最核心的概念，提供系统其他部分必须的服务支持。

组成进程调度程序、主存管理程序负责网络、进程间通信的服务程序中断处理程序和设备驱动等核心服务程序4Linux系统——Linux系统概述2.Linux系统的内核结构4Linux系统——Linu5(2)Linux系统的核心结构系统调用界面程序库进程通信进程调度存储管理文件子系统高速缓冲字符设备块设备设备驱动程序用户程序硬件控制硬件用户级核心级硬件层进程管理与存储管理网络管理网络协议网络驱动Linux系统的核心结构示意图Linux系统——Linux系统概述5(2)Linux系统的核心结构系统调用界面程

Linux系统的特权级与中断处理Linux系统——Linux系统的特权级与中断处理Linux系统——Linux系统的特权级与中断处理61.Linux系统的特权级Linux系统使用两个级别(处理机提供四个特权级)：特权级0——核态(内核模式)特权级3——用户态(用户模式)2.Linux系统中断处理的上半部和下半部(1)为什么要区分上半部和下半部Linux系统——Linux系统的特权级与中断处理为提高中断处理的效率，中断处理程序的执行必须快速、简洁。为此，Linux系统将中断处理程序分为两部分。将中断响应后必须立即处理的工作即刻执行，这就是中断处理程序的上半部(tophalf)。将更多的处理工作向后推迟执行，这就是中断处理程序序的下半部(bottomhalf)。61.Linux系统的特权级Linux系统——Linu7(2)中断处理程序的上半部上半部是中断处理中有严格时间限制的工作，是关键而紧迫的部分;上半部的工作是不可被打断的，即在屏蔽所有中断的情况下进行的。例：与硬件设备应答或使硬件复位的工作。(3)中断处理程序的下半部下半部处理那些可以稍后完成的工作；下半部的执行是可以打断的，即是在开中断的情况下执行。Linux系统——Linux系统的特权级与中断处理7(2)中断处理程序的上半部(3)中断处83.中断处理下半部的实现机制Linux系统中，用于实现实现将工作推后执行的内核机制称为“下半部机制”，下半部机制主要有tasklet和工作队列两种。(1)tasklet

①tasklet通过软中断实现

ⅰ一个软中断被标记后才能执行，称为触发软中断。

ⅱ待处理的软中断会在以下时机被检查和执行：从一个硬件中断返回时；在ksoftirqd内核线程中；在显示检查和执行待处理的软中断的代码中。Linux系统——Linux系统的特权级与中断处理83.中断处理下半部的实现机制Linux系统——Li9②Tasklet软中断ⅰtasklet的软中断表示是TASKLET_SOFTIRQ；ⅱTaskle由结构体tasklet_struct结构表示

structtasklet_struct{structtasklet_struct*next;/*链表中的下一个taskle*/unsignetlongstate;/*taskle的状态*/atomic_tcount;/*引用计数器*/void(*func)(unsignedlong);/*taskle的处理函数*/unsignedlongdata;/*给taskle处理函数的参数*/}tasklet由tasklet_schedule()函数调度Linux系统——Linux系统的特权级与中断处理9②Tasklet软中断structtaskle10(2)工作队列①

工作队列机制将中断处理程序的下半部交给一个内核线程去执行。②

下半部是在进程上下文(用户地址空间)执行，可以睡眠和被重新调度。注：这一点与上述的tasklet不同。如果下半部工作需要睡眠(如需要执行阻塞式I/O操作时，或要等待信号灯)时应选择工作队列机制；否则可选择tasklet机制。Linux系统——Linux系统的特权级与中断处理10(2)工作队列Linux系统——Linu11③

工作者线程

ⅰ该线程接收由各内核中断处理程序交给它的下半部。

ⅱ该线程内核线程实现的。执行的函数是work_thread()，对应的数据结构是工作队列链表。④工作队列链表ⅰ由若干个work_struct结构组成。ⅱwork_struct结构Linux系统——Linux系统的特权级与中断处理11③工作者线程Linux系统——Linux系统的特权级12

work_struct结构

每个work_struct结构描述如下

structwork_struct{unsignedlongpending;/*该工作正在等待处理？*/structlist_headentry;/*勾链字*/void(*func)(void*);/*该工作的处理函数*/void*data;/*传递该该处理函数的参数*/void*wq_data;/*内部使用*/structtimer_listtimer;/*延迟的工作队列所用的定时器*/}Linux系统——Linux系统的特权级与中断处理12work_struct结构Linux系统——L13⑤执行函数work_thread()ⅰ执行一个死循环；ⅱ若工作队列链表不空时，执行链表上的所有工作。工作被执行完毕，它就将相应的work_struct对象从链表上移走；ⅲ当链表为空时，它进入睡眠状态；ⅳ当有下半部插入到队列时，函数是work_thread()被唤醒，将继续处理新加入的下半部。Linux系统——Linux系统的特权级与中断处理13⑤执行函数work_thread()Linux系统——Linux系统的功能调用Linux系统——Linux系统功能调用Linux系统——Linux系统功能调用141.Linux系统功能调用的过程在Linux系统中，系统调用通过异常类型实现；当执行了int0x80指令而发生的软件中断；系统自动将用户态切换为核心态来处理该事件，执行自陷处理程序(系统调用处理程序)。Linux系统——Linux系统功能调用141.Linux系统功能调用的过程Linux系统——L15(1)系统功能调用过程abc();

abc();

{syscall;

}system_call:sys_abc

SYSEXITsysabc(){

}用户态核心态用户程序系统调用

在libc标准库中的封装例程系统调用处理程序系统调用服务例程Linux系统调用过程Linux系统——Linux系统功能调用15(1)系统功能调用过程abc();sy16(2)例：getuid系统调用过程intmain(){getuid();

}intgetuid(void)

{long_res;int$0x80;

}ENTRY(system_call)pushl%esxSAVE_ALLGET_CURRENT(%ebx)

callsys_getuid16

RESTORE_ALLasmlinkagelongsys_getuid16(void){returnhigh2lowuid(current_uid);}用户程序系统调用处理程序标准C库内核例程getuid系统调用过程Linux系统——Linux系统功能调用16(2)例：getuid系统调用过程intmain(172.Linux系统功能调用的实现机制(1)Linux系统调用的进入 ①Linux系统的软中断指令是int0x80汇编语言指令②该指令的执行会发生中断③处理机的状态由用户态自陷到内核态④从system_call()开始执行系统调用处理程序。⑤当系统调用处理完毕后，通过iret汇编语言指令返回到用户态。Linux系统——Linux系统功能调用172.Linux系统功能调用的实现机制Linux系统—18(2)系统调用号 ①linux中，每个系统调用被赋予一个唯一的系统调用号

②系统调用号定义在include/asm-i386/unistd.h头文件中

③系统调用号格式如下

#define__NR_restart_syscall0#define__NR_exit 1#define__NR_fork 2#define__NR_read 3#define__NR_write 4#define__NR_open 5……………………#define__NR_mq_getsetattr282

Linux系统——Linux系统功能调用18(2)系统调用号 Linux系统——Lin19(3)系统调用表 ①

系统调用表记录了内核中所有已注册过的系统调用，它是系统调用的跳转表。

②

系统调用表是一个函数指针数组，表中依次保存所有系统调用的函数指针③

Linux系统调用表保存在arch/i386/kernel/下的entry.S中Linux系统——Linux系统功能调用19(3)系统调用表 Linux系统——Lin20④

系统调用表格式如下

ENTRY(sys_call_table) .longsys_restart_syscall/*0*/ .longsys_exit/*1*/ .longsys_fork /*2*/ .longsys_read /*3*/ .longsys_write /*4*/ .longsys_open /*5*/…………………… .longsys_mq_getsetattr/*282*/Linux系统——Linux系统功能调用20④系统调用表格式如下 Linux系统——Linux系21(4)系统调用处理程序

系统调用处理程序是system_call()，主要工作如下宏SAVE_ALL保护现场；正确性检查；依eax中所包含的系统调用号，调用其对应的服务例程；系统服务例程结束时，通过宏RESTORE_ALL恢复寄存器；最后通过iret指令返回。Linux系统——Linux系统功能调用21(4)系统调用处理程序Linux系统——Linux系223.增加一个新的系统功能调用的方法(1)添加新的服务例程

①

在/usr/src/linux/kernel/sys.c文件中增加一个新的函数，该函数的名字是sys_mysyscall②例：一个简单的系统调用，其功能是返回一个整型值asmlinkageintsys_mycall(intnumber){returnnumber;}Linux系统——Linux系统功能调用223.增加一个新的系统功能调用的方法Linux系统——23(2)增加新的系统功能调用号

①在文件include/asm-i386/unistd.h中添加一项#define__NR_mysyscallXX②XX为新增加的系统调用号，此数字选一未用值。③例#define__NR_restart_syscall0#define__NR_exit 1……………………#define__NR_mq_getsetattr282#define__NR_mysyscall283Linux系统——Linux系统功能调用23(2)增加新的系统功能调用号 Linux24(3)修改系统调用表

①

在文件/arch/i386/kernel/entry.S中的系统调用表sys_call_table中添加新增的系统调用sys_call_table数组包含指向内核中每个系统调用的指针②例

ENTRY(sys_call_table).longsys_restart_syscall/*0*/.longsys_exit/*1*/…………………….longsys_mq_getsetattr/*282*/.longsys_mysyscall/*283*/Linux系统——Linux系统功能调用24(3)修改系统调用表 Linux系统——25(4)重新编译内核并启动新内核

为使新的系统调用生效，需要重建Linux的内核。这需要以超级用户身份登录后重新编译内核。(5)在用户程序中访问新的系统调用

在用户程序中，测试新增加的系统调用是否能正确使用。Linux系统——Linux系统功能调用25(4)重新编译内核并启动新内核 (5)在Linux系统的进程管理Linux系统——Linux系统的进程管理Linux系统——Linux系统的进程管理261.Linux系统进程与线程(1)Linux系统中的进程

进程是程序在处理机上的一次执行过程。进程是处于执行期的程序，它是分配系统资源和调度的实体。进程包括可执行的程序代码、打开的文件、挂起的信号、内核数据、地址空间、处理机状态、一个或多个可执行的线程等。(2)Linux系统中的线程Linux系统将线程看作是一种特殊的进程。线程被视为一个与其他进程共享某些资源的进程。Linux系统——Linux系统的进程管理261.Linux系统进程与线程Linux系统——Lin272.Linux系统的进程描述符Linux内核使用进程描述符(又称为进程控制块)来描述一个进程的完整信息。(1)进程控制块的结构

Linux系统——Linux系统的进程管理272.Linux系统的进程描述符(1)进程控制块的结28指向进程基本控制块的指针进程状态state进程标识进程调度有关的字段进程亲属关系的字段指向当前目录的指针指向文件描述符的指针指向主存描述符的指针指向信号结构的指针指向tty结构的指针task_structthread_info当前目录文件描述符主存描述符所接收的信号与进程相关的tty指向进程队列priopidtgidpgrpsessinthread_inforun_listttyreal_parentparentchildrensiblingfsfilesmmsignal进程控制块的结构

进程控制块结构Linux系统——Linux系统的进程管理28指向进程基本控制块的指针进程状态state进程标识进程调29(2)进程控制块的主要内容

①进程标识符进程标识符processID进程描述符中的标识符字段字段名说明pid进程的PIDtgid线程组领头进程的PIDpgrp进程组领头的进程PIDsession会话领头进程的PIDLinux系统——Linux系统的进程管理29(2)进程控制块的主要内容①进程标识30②进程状态反映进程当前状态，包括以下几种可能的状态ⅰ可运行状态TASK_RUNNINGⅱ可中断的等待状态TASK_INTERRUPTIBLEⅲ不可中断的等待状态TASK_UNINTERRUPTIBLEⅳ暂停状态TASK_STOPPEDⅴ终止状态TXIT_ZOMBIELinux系统——Linux系统的进程管理30②进程状态ⅰ可运行状态TASK_RUNNINGLi31③进程基本信息每个进程都有一个进程基本信息块。在进程描述符的thread_info字段中包含了指向该结构的指针④与进程调度有关的信息可运行进程链表(最多可有140个)

⑤进程的亲属关系

进程描述符中的亲属关系字段字段名说明real_parent指向创建p进程的父进程的描述符，若该父进程不再存在，就指向1#进程parent指向p进程的当前父进程，它的值通常与real_parent一致，偶尔也可不同children链表的头部，链表中的所有进程都是p进程创建的子进程sibling指向兄弟进程链表中的下一个或前一个元素的指针Linux系统——Linux系统的进程管理31③进程基本信息④与进程调度有关的信息⑤进程的亲属关32⑥其他字段在进程描述符的thread_info字段中包含了指向各种结构的指针。ⅰfs——指向当前目录结构fs_steuctⅱfiles——指向文件描述符结构files_structⅲmm——指向主存描述符结构mm_structⅳsignal——指向信号结构signal_structⅴtty——指向进程相关的tty_struct结构Linux系统——Linux系统的进程管理32⑥其他字段ⅰfs——指向当前目录结构33(1)TASK_RUNNING(可运行状态)①它或者正在执行，运行状态②或者在运行队列中等待执行，就绪状态(2)TASK_INTERRUPTIBLE(可中断的等待状态)

进程正在等待某一事件的发生(如某一硬件中断或一个信号)，它处于挂起或称睡眠状态。(3)TASK_UNINTERRUPTIBLE(不可中断的等待状态)

除了不会因为接收到信号而被唤醒从而投入运行外，这个状态与可中断等待状态相同。3.Linux系统进程状态及变迁Linux系统——Linux系统的进程管理33(1)TASK_RUNNING(可运行状34(4)TASK_ZOMBIE(僵死状态)表示进程已经结束，但其父进程还没有调用wait4()系统调用。子进程的进程描述符在此之前仍然被保留(5)TASK_STOPPED(停止)表示进程停止执行，进程没有投入运行也不能投入运行。通常这种状态发生在接收到SIGSTOP、SIGTSTP、SIGTTIN、SIGTTOU等信号的时候。Linux系统——Linux系统的进程管理34(4)TASK_ZOMBIE(僵死状态)Linux系35(6)Linux系统进程状态的变迁运行TASK—UNNING进程调度等待某事件等待的事件发生创建新进程就绪TASK—UNNING进程终止等待TASK—INTERRUPTIBLETASK—UNINTERRUPTIBLE被抢占创建进程完成Linux系统进程状态变迁图Linux系统——Linux系统的进程管理35(6)Linux系统进程状态的变迁36(1)进程创建Linux系统用fork()系统调用创建一个进程。

①

写时拷贝ⅰ

在创建新进程时内核不复制父进程的整个地址空间，而是让父进程和子进程以读方式共享同一拷贝ⅱ只有当一方真正需要写入时，数据才被复制，这时，父、子进程才拥有各自的拷贝4.Linux系统进程创建与终止②系统提供fork()和clone()系统调用ⅰfork()用来创建一般进程ⅱclone()用来创建轻量级进程(线程)Linux系统——Linux系统的进程管理36(1)进程创建4.Linux系统进程创37(2)进程终止Linux系统提供exit()系统调用以终止某一个进程。其主要功能由do_exec()函数完成。

进程终止后，此进程处于僵死状态，但系统还保留了它的进程描述符。只有父进程发出了与被终止进程相关的wait()系统调用后，子进程的task_struct结构才能释放。Linux系统——Linux系统的进程管理37(2)进程终止Linux系统——Linux系统的进程管38(1)进程等待①

两种等待状态

TASK_INTERRUPTIBLE和TASK_UNINTERRUPTIBLE区别：处于TASK_UNINTERRUPTIBLE状态的进程如果接收到一个信号会被提前唤醒并响应该信号，而处于TASK_INTERRUPTIBLE状态的进程会忽略信号。5.Linux系统的进程等待与唤醒②

进程等待的主要步骤ⅰ调用declare_waitqueue()创建一个等待队列的元素。

ⅱ调用add_wait_queue()将该元素加入到等待队列。ⅲ进程的状态设置为TASK_INTERRUPTIBLE状态TASK_UNINTERRUPTIBLE状态。ⅳ转进程调度程序schedule()。Linux系统——Linux系统的进程管理38(1)进程等待5.Linux系统的进39(2)进程唤醒进程唤醒的主要步骤

①

当进程状态设置为TASK_INTERRUPTIBLE，则由信号唤醒进程，这是所谓的伪唤醒(不是直接由所等待的事件唤醒)，因此需要检查并处理信号。

②

若检查条件为真(所等待的事件发生)，转④；若条件不为真，转进程调度schdule()。

③

当进程被唤醒时(因事件发生)，检查条件是否为真，若为真转④；否则转进程调度schdule()。

④

当条件满足时，进程状态设置为TASK_RUNNING，并将该进程移出等待队列。

⑤

该函数将进程状态设置为TASK_RUNNING，再将此进程加入到可执行队列。若被唤醒进程的优先级比当前正在运行的进程的优先级高，设置need_resched标志。Linux系统——Linux系统的进程管理39(2)进程唤醒进程唤醒的主要步骤Linux系统——Linux系统的进程调度Linux系统——Linux系统的进程调度Linux系统——Linux系统的进程调度401.Linux进程调度目标和特点

进程调度程序是内核的组成部分，负责选择下一个要运行的进程。进程调度可看作在可运行态进程之间分配有限的处理器时间资源的内核子系统。进程调度程序是如Linux这样的多任务操作系统的基础。(1)Linux进程调度策略

①

基于动态优先级和可变时间的调度

②

调度方式为可抢占式调度Linux系统——Linux系统的进程调度401.Linux进程调度目标和特点进程41(2)调度目标①实现算法复杂度为O(1)级的调度ⅰ进程调度算法保证在恒定的时间内完成ⅱ算法执行时间与系统中处于就绪(可运行)状态的进程个数无关②提高交互性能提高交互性能，保证系统能快速响应③保证公平ⅰ在合理设定的时间范围内，没有进程会出现饥饿状态ⅱ也不会有进程获得大量的时间片④实现SMP可扩展性Linux系统——Linux系统的进程调度41(2)调度目标Linux系统——Linux42(3)I/O消耗型和处理器消耗型的进程①

I/O消耗型进程大部分时间是使用外部设备，交互式进程具有此特征。②

处理器消耗型进程大部分时间是使用CPU，计算进程具有此特征。

交互式的程序都是I/O消耗型的。Linux为了保证交互式应用，优化了进程的响应，更倾向于优先调度I/O消耗型进程，但并未忽略处理器消耗型程序。Linux系统——Linux系统的进程调度42(3)I/O消耗型和处理器消耗型的进程43(4)进程调度的特点①

Linux系统实现了基于进程过去行为的启发式算法；②

Linux系统选择优先级高的进程先运行，相同优先级的进程按循环方式调度；③

动态优先级依进程占有CPU的情况、休眠时间的长短来增、减；④

系统根据进程优先级调整分配给它的时间片；⑤

实施可抢占调度方式Linux系统——Linux系统的进程调度43(4)进程调度的特点Linux系统——Li442.可变优先级(1)基于优先级的调度

优先级高的进程先运行，低的后运行，相同优先级的进程按轮转方式进行调度。(2)静态优先级①

静态优先级的确定在进程创建时，新创建的进程继承父进程的静态优先级②

静态优先级的取值范围100(最高优先级)139(最低优先级)，取值越小，优先级越高;③

静态优先级的改变用户可以通过系统调用改变nice值，从而改变自己拥有的静态优先级。Linux系统——Linux系统的进程调度442.可变优先级(2)静态优先级Linu45(3)动态优先级①每个进程有一个动态优先级它是进程调度程序选择可运行进程所使用的参数，其取值范围是100(最高优先级)

139(最低优先级)

②

动态优先级的计算动态优先级=max(100，min(静态优先级－bonus+5，139))bonus是范围0～10的值，值小于5表示降低动态优先级以示惩罚值大于5表示增加动态优先级以示奖励进程调度使用的是动态优先级，通过effective_prio()函数来计算一个进程的动态优先级。Linux系统——Linux系统的进程调度45(3)动态优先级Linux系统——Linu46(4)确定I/O消耗型和处理器消耗型进程的方法①

依据——进程睡眠时间的长短若进程睡眠时间长——I/O消耗型若进程睡眠时间短——处理器消耗型②

方法Linux记录进程睡眠和执行时间(存放在task_struct的sleep_avg域中)，范围：0～

MAX_SLEEP_AVG，默认值为10msⅰ当进程从开始休眠到要恢复执行这一时间内sleep_avg增加，直到达到MAX_SLEEP_AVG为止；ⅱ进程每执行一个时钟节拍，sleep_avg递减直到0为止。Linux系统——Linux系统的进程调度46(4)确定I/O消耗型和处理器消耗型进程的47③进程休眠时间与bonus值的关系平均休眠时间bonus值大于或等于0，小于100ms0大于或等于100，小于200ms1大于或等于200，小于300ms2大于或等于300，小于400ms3大于或等于400，小于500ms4大于或等于500，小于600ms5大于或等于600，小于700ms6大于或等于700，小于800ms7大于或等于800，小于900ms8大于或等于900，小于1000ms9大于1s10Linux系统——Linux系统的进程调度47③进程休眠时间与bonus值的关系Linux系统——L483.可变时间片(1)Linux系统的进程调度的目标

①对交互式进程，系统提供较长的时间片②调度程序根据进程的优先级动态调整分配给它的时间片Linux系统——Linux系统的进程调度(2)时间片的计算①

基本时间片

静态优先级本质上决定了进程的基本时间片(140－静态优先级)×20若静态优先级＜120(140－静态优先级)×5若静态优先级≥

120

静态优先级越高(值越小)，基本时间片越长。基本时间片=483.可变时间片Linux系统——Linux系统的进程调49表6.6普通进程的静态优先级和基本时间片的典型值说明静态优先级nice值基本时间片最高静态优先级100-20800ms高静态优先级110-10600ms缺省静态优先级1200100ms低静态优先级130+1050ms最低静态优先级139+195ms初始创建的进程父进程的值父进程的值父进程的一半Linux系统——Linux系统的进程调度更高的优先级更高的交互性更低的优先级更低的交互性最小5ms默认100ms最大800ms进程静态优先级与基本时间片的关系图49表6.6普通进程的静态优先级和基本时间片的典型值说明50(3)时间片处理的时机①创建新进程时的处理新创建的子进程和父进程均分父进程剩余的时间片

②进程用完时间片时的处理ⅰ当一个进程的时间片用完时，依任务的动态优先级重新计算时间片；ⅱtask_timeslice()函数为给定任务返回一个新的时间片。Linux系统——Linux系统的进程调度②可变时间片当一个进程的时间片用完时，根据进程的动态优先级重新计算时间片。50(3)时间片处理的时机Linux系统——L51(4)时间片的使用①

一个进程拥有的时间片可分多次使用，放弃CPU时进入活动队列②

当一个进程的时间片耗尽时，认为是过期进程，进入过期队列Linux系统——Linux系统的进程调度51(4)时间片的使用Linux系统——Lin52(5)活动队列和过期队列每个处理器维护两个优先级数组——活动数组和过期数组①活动数组上的可执行队列中的进程都有剩余时间片②过期数组上的可执行队列中的进程都已耗尽时间片

当一个进程的时间片耗尽时，被移至过期队列中；当活动数组上的可执行队列中的所有进程都已耗尽时时间片，这时，在活动数组和过期数组之间切换指针。Linux系统——Linux系统的进程调度52(5)活动队列和过期队列Linux系统——534.Linux进程调度算法中使用的数据结构(1)可执行队列(runqueue结构)

可执行队列是给定处理机上的可执行进程链表runqueue结构

类型名称说明spinlock_tlock保护进程链表的自旋锁

prio_array_t*active指向活动进程链表的指针prio_array_t*expired指向过期进程链表的指针prio_array_t[2]arrays活动进程和过期进程的两个集合

Linux系统——Linux系统的进程调度534.Linux进程调度算法中使用的数据结构Linux54(2)优先级数组优先级数组是prio_array类型的结构体，该数组描述了可运行进程的集合，包括①

140个双向链表头(每个链表对应一个优先级队列)②

一个进程优先级位图③

该数组所包含的进程总数structprio_array{intnr_active;/*任务数目*/unsignedbitmap[BITMAP_SIZE];/*优先级位图*/structlist_headqueue[MAX_PRIO];/*优先级队列*/}Linux系统——Linux系统的进程调度54(2)优先级数组Linux系统——Linu55④优先级数组图示

*active*expiredarrays[0]arrays[1]

tasktask优先级0优先级139tasktask优先级0优先级139过期进程数组活动进程数组runqueue结构中的两个进程数组Linux系统——Linux系统的进程调度55④优先级数组图示task56

⑤优先级位图的处理ⅰ初始时，所有位被置为0；ⅱ当某个拥有一确定优先级的进程准备运行时(状态为TASK_RUNNING)，位图中相应位置1；ⅲ调度时，查找系统中优线级最高的进程就转化为查找位图中被置为1的第一个位。

由于优先级个数是定值，所以查找时间恒定，不受系统中可执行进程数目的影响，使Linux系统的进程调度算法具有O(1)的算法复杂度。

Linux系统——Linux系统的进程调度56⑤优先级位图的处理Linux系统——L575.Linux进程调度程序scheduler()(1)调度时机①当进程要休眠时②当进程被抢占时③系统发生抢占时(2)进程调度程序的主要工作①在活动优先级数组中找到第一个被设置的位；②选择该优先级链表里的第一个进程；③调上下文切换函数context_switch()。Linux系统——Linux系统的进程调度575.Linux进程调度程序scheduler()L58(3)LinuxO(1)级进程调度图解位9进程链表优先级位图

01

019位6位9位13

位6进程链表位130进程链表位130LinuxO(1)级进程调度算法图解Linux系统——Linux系统的进程调度58(3)LinuxO(1)级进程调度图解位9进Linux系统的存储管理Linux系统——Linux系统的存储管理Linux系统——Linux系统的存储管理591.Linux系统段页式地址变换(1)Linux系统的分段Linux系统处在用户态时，使用用户代码段和用户数据段来对指令和数据寻址在核态时，使用内核代码段和内核数据段来对指令和数据寻址每个分段是一个连续的线性地址空间，从0开始直到232−1的寻址长度。

Linux系统——Linux系统的存储管理591.Linux系统段页式地址变换Linux系统——L60(2)80x86分页结构80x86微处理器的分页单元处理4KB的页。一个32位的线性地址分为3个域。

页目录页表页内位移31222112110ⅰ页目录字段指向页目录项；ⅱ页表字段指向进程的一个页表项；ⅲ页内位移则是页内偏移量

80X86分页机构Linux系统——Linux系统的存储管理60(2)80x86分页结构页目录61(3)三级页表①

第一级——

全局目录(PGD)PGD中的表项指向页目录中的一个表项②

二级页表——页目录(PMD)PMD中的表项指向页表PTE中的一个表项③

三级——页表该表项指向物理页(页框)的主存地址Linux系统——Linux系统的存储管理61(3)三级页表Linux系统——Linu62(4)线性地址转换为物理地址①

地址转换过程Linux系统通过三级页表完成线性地址到物理地址的转换页目录页表页内位移31222112110cr3+：+：页目录表页表物理页+++由线性地址转换为物理地址Linux系统——Linux系统的存储管理62(4)线性地址转换为物理地址页目录63②地址变换步骤

ⅰ

由cr3指示的当前页目录的物理地址与分页结构中的页目录字段的内容相加指向页目录表项；

ⅱ由页目录表项内容得到当前使用的页表的始地址，通过分页结构中的页表字段的内容找到该页表项；

ⅲ由页表项指示的该页的物理页(页框)的主存地址与分页结构中的页内位移相加，得到最终的物理地址。Linux系统——Linux系统的存储管理63②地址变换步骤Linux系统——Linux系统的存储管642.Linux系统动态内核管理(1)物理页的描述①

Linux系统主存分配的基本单位是物理页(又称为页框)

②

主存管理单元MMU以页为单位进行分配和处理

③

32位体系结构支持4KB的页，64位体系结构支持8KB的页④

内核用structpage结构描述页框

structpage{flags;/*页的状态*/_count;/*该页被引用的次数*/

*virtual;/*页的虚拟地址，记录页在虚拟主存中的地址*/};

Linux系统——Linux系统的存储管理642.Linux系统动态内核管理Linux系统——Li65(2)物理主存分区内核将系统中的所有页框划分为不同的区，具有相似特征的页框归为同一个分区。Linux系统共分为三种分区①

ZONE_DMA

这个分区包含的页只能用来执行DMA操作，大小为16MB；

②ZONE_NORMAL这个分区包含的页都是能正常映射的页，大小为16MB896MB③ZONE_HIGHMEM这个分区包含的是“高端主存”，其中的物理页并不能永久地映射到内核地址空间，大小为896MB。Linux系统——Linux系统的存储管理65(2)物理主存分区Linux系统——Lin66(3)分区页框的分配①

Linux内核通过页框和区对主存进行管理，实现了请求主存的底层机制；②

内核提供提供一组访问接口(函数或宏)可以直接的方式获得动态主存，注意这种方式只能由内核使用。

Linux系统——Linux系统的存储管理66(3)分区页框的分配Linux系统——L67(4)分区页框分配器①

分区页框分配器(Zonedpageframeallocator)是一个内核子系统，它负责对连续页框的主存分配。②

分区页框分配器的组成如下图

分区页框分配器的组成Linux系统——Linux系统的存储管理管理区分配器每CPU页框高速缓存每CPU页框高速缓存每CPU页框高速缓存

伙伴系统

伙伴系统

伙伴系统

ZONE_DMA主存管理区

ZONE_NORMAL主存管理区

ZONE_HIGHMEM主存管理区67(4)分区页框分配器分区页框分配器的组成68(5)伙伴系统算法①主存管理中的外碎片问题ⅰ当频繁地请求和释放不同大小的连续页框，就会导致在已分配页框内产生许多小的、分散的空闲页框；

ⅱ

Linux系统采用伙伴系统算法记录当前空闲的连续页框块的情况，以尽量避免为满足小块的请求而分割大的空闲块。②伙伴系统算法中页框的组织ⅰ

将所有的空闲页框分组为11个块链表；ⅱ每个块链表分别包含大小为1、2、4、8、16、32、64、128、256、512、1024个连续页框；ⅲ每个块的第一个页框的物理地址是该块大小的整数倍。

Linux系统——Linux系统的存储管理68(5)伙伴系统算法②伙伴系统算法中页框69(6)页框的分配过程

以分配256个页框的块为例说明伙伴系统算法的页框的分配过程

①

首先在256个页框的链表中检查是否有空闲块满足需要；②

若没有，则在512个页框的链表中找满足需要的空闲块

ⅰ若存在这样的块，算法将这512的页框分为2半；

ⅱ

一半用来满足请求，另一半插入到256个页框的链表中；③

若还没有，则在1024个页框的链表中找满足需要的空闲块；

ⅰ若存在，则将256块用来满足要求，其余部分分为256块和512块分别插入到相应的链表中；

ⅱ若不存在；算法放弃并给出不能满足分配的信息。

Linux系统——Linux系统的存储管理69(6)页框的分配过程Linux系统——Linux系统的70(7)页框的释放过程

分配过程的逆过程就是页框的释放过程①

内核试图将大小为b的一对空闲伙伴块合并为一个大小为2b的单独块。满足以下条件的两个块称为伙伴：

ⅰ两个块的大小相同，记为b；

ⅱ它们的物理地址是连续的；

ⅲ

第一块的第一个页框的物理地址是2×b×212的倍数。②

算法是迭代的，如果它成功合并所释放的块，它会试图合并2b的块，以再次试图形成跟更大的块。Linux系统——Linux系统的存储管理70(7)页框的释放过程Linux系统——Linux系统的713.Linux系统的进程地址空间Linux内核提供用于页框分配和释放的函数(或宏)。这些函数只能由内核直接使用，用户进程请求主存时不能直接使用。当用户进程请求动态主存时，内核采用推迟分配的方法，即用户并没有获得请求的页框，而仅仅获得对一个新的线性地址区间的使用权。这一线性地址区间成为进程地址空间的一部分，称为“线性区”。(1)进程地址空间的描述①

进程的地址空间由每个进程的线性地址区组成，是一个独立的连续区间。②

描述进程地址空间的信息存放在主存描述符中。主存描述符由mm_struct结构体表示，进程描述符的mm字段指向这个结构。Linux系统——Linux系统的存储管理713.Linux系统的进程地址空间Linux系统——L72(2)进程线性区的描述①

进程的地址空间由若干个线性区组成；②

线性区域(又称为主存区域)用vm_area_struct结构体描述。

(3)主存描述符与主存区域描述符的关系①

进程地址空间可以由多个主存区域组成，描述这些主存区域的数据结构vm_area_struct组成一个链表；②

mm_struct中的mmap指向这个链表的头结构。Linux系统——Linux系统的存储管理72(2)进程线性区的描述Linux系统——L73③

主存描述符mm_struct和主存区域描述符vm_area_struct，这两类数据结构的关系如图所示。

主存描述符、线性区描述符与进程线性地址空间Linux系统——Linux系统的存储管理线性地址空间主存线性区域vm_area_struct结构主存描述符mm_struct结构

mmap

73③主存描述符mm_struct和主存区域描述符vm_aLinux系统的设备驱动Linux系统——Linux系统的设备驱动Linux系统——Linux系统的设备驱动741.Linux系统设备的分类(1)字符设备字符设备是能够像字符流的方式被有序访问的设备。这类设备以字节为单位进行数据处理。

(2)块设备块设备是能随机访问固定大小数据(又称为块)的设备。常见的块设备有硬盘、软盘驱动器、CD-ROM驱动器和闪存等。块设备以块为单位进行处理，大多数块设备采用缓冲技术。Linux系统——Linux系统的设备驱动741.Linux系统设备的分类Linux系统——Lin752.设备文件及标识(1)设备文件Linux系统将设备称为设备特殊文件，是文件类型的一种。(2)主、次设备号在Linux系统中描述文件的数据结构称为文件索引节点。设备特殊文件的索引节点包含硬件设备的一个标识符，该标识符对应字符设备或块设备。Linux系统——Linux系统的设备驱动752.设备文件及标识Linux系统——Linux系统的76①主设备号ⅰ

主设备号标识设备的类型。ⅱ

具有相同主设备号(即类型一样)的所有设备共享相同的文件操作集合。②

次设备号ⅰ次设备号标识主设备号相同的一组设备中的一个特定的设备。ⅱ如由相同的磁盘控制器管理的一组磁盘，具有相同的主设备号和不同的次设备号。Linux系统——Linux系统的设备驱动76①主设备号Linux系统——Linux系统的设备驱动77(3)VFS对设备文件的处理①

虚拟文件系统VFS(VirtualFilesystem)负责处理与UNIX标准文件系统相关的所有系统调用，为各种文件系统提供一个通用的接口。②

VFS在打开设备文件时改变缺省的文件操作。它将缺省的文件操作(f_op)字段改变为块设备(或字符设备)的文件操作表(def_bik_fops)的地址。③

对设备文件的每次系统调用都将转换成与设备相关的操作函数调用。④

当与设备相关的操作函数被调用后，就可以对硬件设备进行操作，以完成进程所请求的I/O传输。Linux系统——Linux系统的设备驱动77(3)VFS对设备文件的处理Linux系78缺省的块设备文件操作表def_bik_fops表方法用于块设备文件的函数openblkdev_open()releaseblkdev_close()llseekblkdev_llseek()readgeneric_file_read()writeblkdev_file_write()块设备文件操作表Linux系统——Linux系统的设备驱动78缺省的块设备文件操作表def_bik_fops表方法用793.Linux块设备的处理(1)块设备处理中内核组件之间的关系虚拟文件系统VFS磁盘高速缓存

文件系统映射层

通用块层

I/O调度程序

块设备驱动程序

块设备驱动程序磁盘磁盘块设备驱动程序涉及的内核组件Linux系统——Linux系统的设备驱动793.Linux块设备的处理虚80(2)以进程的read()系统调用为例，分析内核组件的调用过程①

在读操作之前，相应的设备文件已打开；②

VFS通过块设备文件操作表调用适当的VFS函数，传递的参数是：文件描述符、文件的偏移量；③

VFS相应的函数首先访问磁盘高速缓存，若所需数据在高缓存中，不必启动磁盘读操作；否则启动磁盘读操作。假定为后者；④

在磁盘文件系统映射层，计算请求数据的逻辑块号，根据该文件的索引节点中的索引结构确定该逻辑块号对应的磁盘物理块号。然后，对块设备发出读请求；Linux系统——Linux系统的设备驱动80(2)以进程的read()系统调用为例，分81⑤

通用块层接收到所需数据所在的磁盘块号、操作类型，给I/O调度程序发出启动磁盘读操作的命令；⑥

I/O调度程序根据预先定义好的I/O调度策略，将待处理的I/O数据传送请求进行归类。其目的是尽量将在磁盘上物理介质相邻的数据请求聚集在一起，以使I/O处理的效率最高；⑦

最后，块设备驱动程序向磁盘控制器的硬件接口发出设备启动命令，从而进行实际的数据传送。Linux系统——Linux系统的设备驱动81⑤通用块层接收到所需数据所在的磁盘块号、操作类型，给L824.用于块设备处理的数据结构设备驱动程序涉及的数据结构有设备请求队列和bio请求块。(1)bio结构①

bio是描述块设备I/O操作的描述符

ⅰ

包括一个磁盘存储区标识符(存储区的起始扇区号和扇区总数)；

ⅱ

一个或多个描述与I/O操作相关的主存区的段。②

bio结构以片段为单位的链表形式来组织块I/O操作

ⅰ一个片段是一小块连续的主存。当缓冲区分散在主存的多个位置时，bio结构体也能对内核保证I/O操作的执行。

ⅱ在bio结构体中有几个相关的域bi_io_vec、bi_vcnt和bi_idx。

Linux系统——Linux系统的设备驱动824.用于块设备处理的数据结构Linux系统——Lin83③

bi_io_vec、bi_vcnt和bi_idxⅰbi_io_vec域指向一个bio_vec数组该数组包含了提供特定I/O操作所需要使用到的所有片段。ⅱ

在指定的I/O操作中，bi_vcnt域用来描述bi_io_vec所指向的bio_vec数组中的向量数目。ⅲ

当块I/O操作执行完毕后，bi_idx域指向数组的当前索引。

Linux系统——Linux系统的设备驱动83③bi_io_vec、bi_vcnt和bi_idxLi84④bio结构、bio_vec结构数组和page结构之间的关系bio_vec结构数组总数为bi_vcntbio_idxbio_io_vecbio_vecbio_vecbio_vecbio_vec页面页面页面页面ⅰ

I/O操作的第一个片段由bio结构中的bio_io_vec字段所指向，其他的片段在其后依次存放，共有bi_vcnt个片段；ⅱ

当I/O操作开始执行时，使用着各个片段，这时，bi_idx域会不断地更新，它总是指向正在操作的当前片段。bio结构、bio_vec结构数组和page结构之间的关系Linux系统——Linux系统的设备驱动84④bio结构、bio_vec结构数组和page结构之间85(2)设备队列和请求描述符①

设备请求队列设备请求队列是一个双向链表，包含待处理的请求，由request_queue结构描述。②

请求描述符请求描述符request描述每个块设备待处理的请求。Linux系统——Linux系统的设备驱动85(2)设备队列和请求描述符Linux系统—86字段说明queue_head待处理请求的链表request_fn实现驱动程序的策略例程入口点的方法back_marge_fn检查是否可能将bio合并到请求队列的最后一个请求中的方法front_marge_fn检查是否可能将bio合并到请求队列的第一个请求中的方法marge_requests_fn合并请求队列中两个相邻请求的方法make_request_fn将一个