【教学课件】第9章Linux系统

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