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

《操作系统第9章Linux系统课件.ppt》由会员分享，可在线阅读，更多相关《操作系统第9章Linux系统课件.ppt（132页珍藏版）》请在三一办公上搜索。

1、第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系统概述

2、,(4)Linux系统的特点 单体结构内核 可抢占式内核 多线程应用程序的支持 多处理机支持 支持多种文件系统,(3)Linux系统的组成 Linux操作系统包括Linux内核，还包括shell、带有多窗口 管理器的 X-Windows图形用户接口、文本编辑器、高级语 言编译器等应用软件。,3,Linux系统 Linux系统概述,2.Linux系统的内核结构(1)Linux内核的组成 Linux内核包含最基础、最核心的概念，提供系统其他部 分必须的服务支持。组成进程调度程序、主存管理程序负责网络、进程间通信的服务程序中断处理程序和设备驱动等核心服务程序,4,Linux系统 Linux系统概述,

3、5,(2)Linux系统的核心结构,Linux系统的核心结构示意图,Linux系统 Linux系统概述,Linux系统的特权级与中断处理,Linux系统 Linux系统的特权级与中断处理,6,1.Linux系统的特权级Linux系统使用两个级别(处理机提供四个特权级)：特权级0 核态(内核模式)特权级3 用户态(用户模式)2.Linux系统中断处理的上半部和下半部(1)为什么要区分上半部和下半部,Linux系统 Linux系统的特权级与中断处理,为提高中断处理的效率，中断处理程序的执行必须快速、简洁。为此，Linux系统将中断处理程序分为两部分。将中断响应后必须立即处理的工作即刻执行，这就是中

4、断处理程序的上半部(tophalf)。将更多的处理工作向后推迟执行，这就是中断处理程序序的下半部(bottom half)。,7,(2)中断处理程序的上半部上半部是中断处理中有严格时间限制的工作，是关键而 紧迫的部分;上半部的工作是不可被打断的，即在屏蔽所有中断的情 况下进行的。例：与硬件设备应答或使硬件复位的工作。,(3)中断处理程序的下半部下半部处理那些可以稍后完成的工作；下半部的执行是可以打断的，即是在开中断的情况下执 行。,Linux系统 Linux系统的特权级与中断处理,8,3.中断处理下半部的实现机制 Linux系统中，用于实现实现将工作推后执行的内核机制称为“下半部机制”，下半部

5、机制主要有tasklet和工作队列两种。(1)tasklet tasklet通过软中断实现 一个软中断被标记后才能执行，称为触发软中断。待处理的软中断会在以下时机被检查和执行：从一个硬件中断返回时；在ksoftirqd内核线程中；在显示检查和执行待处理的软中断的代码中。,Linux系统 Linux系统的特权级与中断处理,9,Tasklet软中断 tasklet的软中断表示是TASKLET_SOFTIRQ；Taskle由结构体tasklet_struct结构表示,struct tasklet_struct struct tasklet_struct*next;/*链表中的下一个taskle*/u

6、nsignet long state;/*taskle的状态*/atomic_t count;/*引用计数器*/void(*func)(unsigned long);/*taskle的处理函数*/unsigned long data;/*给taskle处理函数的参数*/tasklet由tasklet_schedule()函数调度,Linux系统 Linux系统的特权级与中断处理,10,(2)工作队列 工作队列机制将中断处理程序的下半部交给一个内核线 程去执行。下半部是在进程上下文(用户地址空间)执行，可以睡眠和 被重新调度。注：这一点与上述的tasklet不同。如果下半部工作需要睡 眠(如需要

7、执行阻塞式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;/*该工

8、作正在等待处理？*/struct list_head entry;/*勾链字*/void(*func)(void*);/*该工作的处理函数*/void*data;/*传递该该处理函数的参数*/void*wq_data;/*内部使用*/struct timer_list timer;/*延迟的工作队列所用的定时器*/,Linux系统 Linux系统的特权级与中断处理,13,执行函数work_thread()执行一个死循环；若工作队列链表不空时，执行链表上的所有工作。工 作被执行完毕，它就将相应的work_struct对象从链表 上移走；当链表为空时，它进入睡眠状态；当有下半部插入到队列时，函数是

9、work_thread()被唤醒，将继续处理新加入的下半部。,Linux系统 Linux系统的特权级与中断处理,Linux系统的功能调用,Linux系统Linux系统功能调用,14,1.Linux系统功能调用的过程在Linux系统中，系统调用通过异常类型实现；当执行了int 0 x80指令而发生的软件中断；系统自动将用户态切换为核心态来处理该事件，执行自陷处理程序(系统调用处理程序)。,Linux系统Linux系统功能调用,15,(1)系统功能调用过程,Linux系统调用过程,Linux系统Linux系统功能调用,16,(2)例：getuid系统调用过程,getuid系统调用过程,Linux系

10、统Linux系统功能调用,17,2.Linux系统功能调用的实现机制(1)Linux系统调用的进入 Linux系统的软中断指令是int 0 x80汇编语言指令 该指令的执行会发生中断 处理机的状态由用户态自陷到内核态 从system_call()开始执行系统调用处理程序。当系统调用处理完毕后，通过iret汇编语言指令返回到用 户态。,Linux系统Linux系统功能调用,18,(2)系统调用号 linux中，每个系统调用被赋予一个唯一的系统调用号 系统调用号定义在include/asm-i386/unistd.h头文件中 系统调用号格式如下#define _NR_restart_syscall

11、 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

12、(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中所包含的系统调用号，调用其对应的服务例 程；系统服务例程结束时，通过宏REST

13、ORE_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_my

14、syscall 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

15、_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系统中的进程

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

17、nux系统的进程管理,29,(2)进程控制块的主要内容,进程标识符 进程标识符process ID,进程描述符中的标识符字段,Linux系统Linux系统的进程管理,30,进程状态 反映进程当前状态，包括以下几种可能的状态,可运行状态 TASK_RUNNING 可中断的等待状态 TASK_INTERRUPTIBLE 不可中断的等待状态 TASK_UNINTERRUPTIBLE 暂停状态 TASK_STOPPED 终止状态 TXIT_ZOMBIE,Linux系统Linux系统的进程管理,31,进程基本信息 每个进程都有一个进程基本信息块。在进程描述符的thread_info字段中包含了指向该结构

18、的指针,与进程调度有关的信息 可运行进程链表(最多可有140个),进程的亲属关系,进程描述符中的亲属关系字段,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(可运行状态)它或者正在执行，运

19、行状态 或者在运行队列中等待执行，就绪状态(2)TASK_INTERRUPTIBLE(可中断的等待状态)进程正在等待某一事件的发生(如某一硬件中断或一个信 号)，它处于挂起或称睡眠状态。(3)TASK_UNINTERRUPTIBLE(不可中断的等待 状态)除了不会因为接收到信号而被唤醒从而投入运行外，这个 状态与可中断等待状态相同。,3.Linux系统进程状态及变迁,Linux系统Linux系统的进程管理,34,(4)TASK_ZOMBIE(僵死状态)表示进程已经结束，但其父进程还没有调用wait4()系统 调用。子进程的进程描述符在此之前仍然被保留(5)TASK_STOPPED(停止)表示进

20、程停止执行，进程没有投入运行也不能投入运行。通常这种状态发生在接收到SIGSTOP、SIGTSTP、SIGTTIN、SIGTTOU等信号的时候。,Linux系统Linux系统的进程管理,35,(6)Linux系统进程状态的变迁,Linux系统进程状态变迁图,Linux系统Linux系统的进程管理,36,(1)进程创建 Linux系统用fork()系统调用创建一个进程。写时拷贝 在创建新进程时内核不复制父进程的整个地址空间，而是让父进程和子进程以读方式共享同一拷贝 只有当一方真正需要写入时，数据才被复制，这时，父、子进程才拥有各自的拷贝,4.Linux系统进程创建与终止,系统提供fork()和c

21、lone()系统调用 fork()用来创建一般进程 clone()用来创建轻量级进程(线程),Linux系统Linux系统的进程管理,37,(2)进程终止 Linux系统提供exit()系统调用以终止某一个进程。其主要 功能由do_exec()函数完成。进程终止后，此进程处于僵死状态，但系统还保留了它的 进程描述符。只有父进程发出了与被终止进程相关的 wait()系统调用后，子进程的task_struct结构才能释放。,Linux系统Linux系统的进程管理,38,(1)进程等待 两种等待状态 TASK_INTERRUPTIBLE 和 TASK_UNINTERRUPTIBLE 区别：处于TAS

22、K_UNINTERRUPTIBLE状态的进程如果接收到一个信 号会被提前唤醒并响应该信号，而处于TASK_INTERRUPTIBLE状态 的进程会忽略信号。,5.Linux系统的进程等待与唤醒,进程等待的主要步骤 调用declare_waitqueue()创建一个等待队列的元素。调用add_wait_queue()将该元素加入到等待队列。进程的状态设置为TASK_INTERRUPTIBLE状态 TASK_UNINTERRUPTIBLE状态。转进程调度程序schedule()。,Linux系统Linux系统的进程管理,39,(2)进程唤醒,进程唤醒的主要步骤 当进程状态设置为TASK_INTER

23、RUPTIBLE，则由信号唤醒进程，这是所谓的伪唤醒(不是直接由所等待的事件唤醒)，因此需要检 查并处理信号。若检查条件为真(所等待的事件发生)，转；若条件不为真，转进 程调度schdule()。当进程被唤醒时(因事件发生)，检查条件是否为真，若为真转；否则转进程调度schdule()。当条件满足时，进程状态设置为 TASK_RUNNING，并将该进程 移出等待队列。该函数将进程状态设置为TASK_RUNNING，再将此进程加入到 可执行队列。若被唤醒进程的优先级比当前正在运行的进程的优 先级高，设置need_resched标志。,Linux系统Linux系统的进程管理,Linux系统的进程调

24、度,Linux系统Linux系统的进程调度,40,1.Linux进程调度目标和特点,进程调度程序是内核的组成部分，负责选择下一个要运 行的进程。进程调度可看作在可运行态进程之间分配有限的处理器 时间资源的内核子系统。进程调度程序是如Linux这样的多任务操作系统的基础。(1)Linux进程调度策略 基于动态优先级和可变时间的调度 调度方式为可抢占式调度,Linux系统Linux系统的进程调度,41,(2)调度目标 实现算法复杂度为O(1)级的调度 进程调度算法保证在恒定的时间内完成 算法执行时间与系统中处于就绪(可运行)状态的进程个 数无关 提高交互性能提高交互性能，保证系统能快速响应 保证公

25、平 在合理设定的时间范围内，没有进程会出现饥饿状态 也不会有进程获得大量的时间片 实现SMP可扩展性,Linux系统Linux系统的进程调度,42,(3)I/O消耗型和处理器消耗型的进程 I/O消耗型进程 大部分时间是使用外部设备，交互式进程具有此特征。处理器消耗型进程 大部分时间是使用CPU，计算进程具有此特征。,交互式的程序都是I/O消耗型的。Linux为了保证交互式应用，优化了进程的响应，更倾向 于优先调度I/O消耗型进程，但并未忽略处理器消耗型程 序。,Linux系统Linux系统的进程调度,43,(4)进程调度的特点 Linux系统实现了基于进程过去行为的启发式算法；Linux系统选

26、择优先级高的进程先运行，相同优先级的进 程按循环方式调度；动态优先级依进程占有CPU的情况、休眠时间的长短来 增、减；系统根据进程优先级调整分配给它的时间片；实施可抢占调度方式,Linux系统Linux系统的进程调度,44,2.可变优先级(1)基于优先级的调度 优先级高的进程先运行，低的后运行，相同优先级的进程 按轮转方式进行调度。,(2)静态优先级 静态优先级的确定 在进程创建时，新创建的进程继承 父进程的静态优先级 静态优先级的取值范围 100(最高优先级)139(最低 优先级)，取值越小，优先级越高;静态优先级的改变 用户可以通过系统调用改变nice值，从而改变自己拥有的静态优先级。,L

27、inux系统Linux系统的进程调度,45,(3)动态优先级 每个进程有一个动态优先级 它是进程调度程序选择可运 行进程所使用的参数，其取值范围是100(最高优先级)139(最低优先级)动态优先级的计算 动态优先级=max(100，min(静态优先级 bonus+5，139)bonus是范围 0 10的值，值小于5表示降低动态优先级以示惩罚 值大于5表示增加动态优先级以示奖励 进程调度使用的是动态优先级，通过effective_prio()函数 来计算一个进程的动态优先级。,Linux系统Linux系统的进程调度,46,(4)确定I/O消耗型和处理器消耗型进程的方法 依据 进程睡眠时间的长短

28、若进程睡眠时间长 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，小于 300m

29、s 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)时间片的计算 基本时间片 静态优先级本质上决定了进程的基本时间片

30、(140 静态优先级)20 若静态优先级 120(140 静态优先级)5 若静态优先级 120 静态优先级越高(值越小)，基本时间片越长。,49,表6.6 普通进程的静态优先级和基本时间片的典型值,Linux系统Linux系统的进程调度,进程静态优先级与基本时间片的关系图,50,(3)时间片处理的时机 创建新进程时的处理新创建的子进程和父进程均分父进程剩余的时间片 进程用完时间片时的处理 当一个进程的时间片用完时，依任务的动态优先级重 新计算时间片；task_timeslice()函数为给定任务返回一个新的时间片。,Linux系统Linux系统的进程调度,可变时间片当一个进程的时间片用完时，根

31、据进程的动态优先级重新计算时间片。,51,(4)时间片的使用 一个进程拥有的时间片可分多次使用，放弃CPU时进 入活动队列 当一个进程的时间片耗尽时，认为是过期进程，进入过 期队列,Linux系统Linux系统的进程调度,52,(5)活动队列和过期队列 每个处理器维护两个优先级数组 活动数组和过期数组 活动数组上的可执行队列中的进程都有剩余时间片 过期数组上的可执行队列中的进程都已耗尽时间片 当一个进程的时间片耗尽时，被移至过期队列中；当活动数组上的可执行队列中的所有进程都已耗尽时时间 片，这时，在活动数组和过期数组之间切换指针。,Linux系统Linux系统的进程调度,53,4.Linux进

32、程调度算法中使用的数据结构(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个双向链表头(每个链表对应一个优先级队列)一个

33、进程优先级位图 该数组所包含的进程总数 struct prio_array int nr_active;/*任务数目*/unsigned bitmapBITMAP_SIZE;/*优先级位图*/struct list_head queueMAX_PRIO;/*优先级队列*/,Linux系统Linux系统的进程调度,55,优先级数组图示,runqueue结构中的两个进程数组,Linux系统Linux系统的进程调度,56,优先级位图的处理 初始时，所有位被置为0；当某个拥有一确定优先级的进程准备运行时(状态为 TASK_RUNNING)，位图中相应位置1；调度时，查找系统中优线级最高的进程就转化为查

34、找 位图中被置为1的第一个位。由于优先级个数是定值，所以查找时间恒定，不受系统 中可执行进程数目的影响，使Linux系统的进程调度算 法具有O(1)的算法复杂度。,Linux系统Linux系统的进程调度,57,5.Linux进程调度程序scheduler()(1)调度时机 当进程要休眠时 当进程被抢占时 系统发生抢占时(2)进程调度程序的主要工作 在活动优先级数组中找到第一个被设置的位；选择该优先级链表里的第一个进程；调上下文切换函数context_switch()。,Linux系统Linux系统的进程调度,58,(3)Linux O(1)级进程调度图解,Linux系统Linux系统的进程调度

35、,Linux系统的存储管理,Linux系统Linux系统的存储管理,59,1.Linux系统段页式地址变换(1)Linux系统的分段Linux系统处在用户态时，使用用户代码段和用户数据 段来对指令和数据寻址在核态时，使用内核代码段和内核数据段来对指令和 数据寻址每个分段是一个连续的线性地址空间，从0开始直到 2321的寻址长度。,Linux系统Linux系统的存储管理,60,(2)80 x86分页结构 80 x86微处理器的分页单元处理4KB的页。一个32位的线 性地址分为3个域。,页目录字段指向页目录项；页表字段指向进程的一个页表项；页内位移则是页内偏移量,80X86分页机构,Linux系统

36、Linux系统的存储管理,61,(3)三级页表 第一级 全局目录(PGD)PGD中的表项指向页目录中的一个表项 二级页表 页目录(PMD)PMD中的表项指向页表PTE中的一个表项 三级 页表 该表项指向物理页(页框)的主存地址,Linux系统Linux系统的存储管理,62,(4)线性地址转换为物理地址 地址转换过程 Linux系统通过三级页表完成线性地址到物理地址的转换,由线性地址转换为物理地址,Linux系统Linux系统的存储管理,63,地址变换步骤 由cr3指示的当前页目录的物理地址与分页结构中的页 目录字段的内容相加指向页目录表项；由页目录表项内容得到当前使用的页表的始地址，通过 分页

37、结构中的页表字段的内容找到该页表项；由页表项指示的该页的物理页(页框)的主存地址与分页 结构中的页内位移相加，得到最终的物理地址。,Linux系统Linux系统的存储管理,64,2.Linux系统动态内核管理(1)物理页的描述 Linux系统主存分配的基本单位是物理页(又称为页框)主存管理单元MMU以页为单位进行分配和处理 32位体系结构支持4KB的页，64位体系结构支持8KB的页 内核用struct page结构描述页框 struct page flags;/*页的状态*/_count;/*该页被引用的次数*/*virtual;/*页的虚拟地址，记录页在虚拟主存中的地址*/;,Linux系统

38、Linux系统的存储管理,65,(2)物理主存分区 内核将系统中的所有页框划分为不同的区，具有相似特 征的页框归为同一个分区。Linux系统共分为三种分区 ZONE_DMA 这个分区包含的页只能用来执行DMA操作，大小为16MB；ZONE_NORMAL这个分区包含的页都是能正常映射的页，大小为16MB 896MB ZONE_HIGHMEM这个分区包含的是“高端主存”，其中的物理页并不能永久地映射到内核地址空间，大小为896MB。,Linux系统Linux系统的存储管理,66,(3)分区页框的分配 Linux内核通过页框和区对主存进行管理，实现了请求 主存的底层机制；内核提供提供一组访问接口(函

39、数或宏)可以直接的方 式获得动态主存，注意这种方式只能由内核使用。,Linux系统Linux系统的存储管理,67,(4)分区页框分配器 分区页框分配器(Zoned page frame allocator)是一个内 核子系统，它负责对连续页框的主存分配。分区页框分配器的组成如下图,分区页框分配器的组成,Linux系统Linux系统的存储管理,68,(5)伙伴系统算法 主存管理中的外碎片问题 当频繁地请求和释放不同大小的连续页框，就会导致在已分配页 框内产生许多小的、分散的空闲页框；Linux系统采用伙伴系统算法记录当前空闲的连续页框块的情况，以尽量避免为满足小块的请求而分割大的空闲块。,伙伴系

40、统算法中页框的组织 将所有的空闲页框分组为11个块链表；每个块链表分别包含大小为1、2、4、8、16、32、64、128、256、512、1024个连续页框；每个块的第一个页框的物理地址是该块大小的整数倍。,Linux系统Linux系统的存储管理,69,(6)页框的分配过程 以分配256个页框的块为例说明伙伴系统算法的页框的 分配过程 首先在256个页框的链表中检查是否有空闲块满足需要；若没有，则在512个页框的链表中找满足需要的空闲块 若存在这样的块，算法将这512的页框分为2半；一半用来满足请求，另一半插入到256个页框的链表中；若还没有，则在1024个页框的链表中找满足需要的空闲块；若存

41、在，则将256块用来满足要求，其余部分分为256块 和512块分别插入到相应的链表中；若不存在；算法放弃并给出不能满足分配的信息。,Linux系统Linux系统的存储管理,70,(7)页框的释放过程 分配过程的逆过程就是页框的释放过程 内核试图将大小为b 的一对空闲伙伴块合并为一个大小为 2b的单独块。满足以下条件的两个块称为伙伴：两个块的大小相同，记为b；它们的物理地址是连续的；第一块的第一个页框的物理地址是2b212的倍数。算法是迭代的，如果它成功合并所释放的块，它会试图 合并2b的块，以再次试图形成跟更大的块。,Linux系统Linux系统的存储管理,71,3.Linux系统的进程地址空

42、间 Linux内核提供用于页框分配和释放的函数(或宏)。这些函数只能由内核直 接使用，用户进程请求主存时不能直接使用。当用户进程请求动态主存时，内核采用推迟分配的方法，即用户并没有获 得请求的页框，而仅仅获得对一个新的线性地址区间的使用权。这一线性地址区间成为进程地址空间的一部分，称为“线性区”。(1)进程地址空间的描述 进程的地址空间由每个进程的线性地址区组成，是一个独 立的连续区间。描述进程地址空间的信息存放在主存描述符中。主存描述 符由mm_struct结构体表示，进程描述符的mm字段指向这 个结构。,Linux系统Linux系统的存储管理,72,(2)进程线性区的描述 进程的地址空间由

43、若干个线性区组成；线性区域(又称为主存区域)用vm_area_struct结构体描述。(3)主存描述符与主存区域描述符的关系 进程地址空间可以由多个主存区域组成，描述这些主存区 域的数据结构vm_area_struct组成一个链表；mm_struct中的mmap指向这个链表的头结构。,Linux系统Linux系统的存储管理,73,主存描述符mm_struct和主存区域描述符vm_area_struct，这 两类数据结构的关系如图所示。,主存描述符、线性区描述符与进程线性地址空间,Linux系统Linux系统的存储管理,Linux系统的设备驱动,Linux系统Linux系统的设备驱动,74,1.

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

45、x系统Linux系统的设备驱动,76,主设备号 主设备号标识设备的类型。具有相同主设备号(即类型一样)的所有设备共享相同的 文件操作集合。次设备号 次设备号标识主设备号相同的一组设备中的一个特定的 设备。如由相同的磁盘控制器管理的一组磁盘，具有相同的主 设备号和不同的次设备号。,Linux系统Linux系统的设备驱动,77,(3)VFS对设备文件的处理 虚拟文件系统VFS(Virtual Filesystem)负责处理与UNIX标 准文件系统相关的所有系统调用，为各种文件系统提供一 个通用的接口。VFS在打开设备文件时改变缺省的文件操作。它将缺省的 文件操作(f_op)字段改变为块设备(或字符

46、设备)的文件操 作表(def_bik_fops)的地址。对设备文件的每次系统调用都将转换成与设备相关的操作 函数调用。当与设备相关的操作函数被调用后，就可以对硬件设备进 行操作，以完成进程所请求的I/O传输。,Linux系统Linux系统的设备驱动,78,缺省的块设备文件操作表def_bik_fops表,块设备文件操作表,Linux系统Linux系统的设备驱动,79,3.Linux块设备的处理(1)块设备处理中内核组件之间的关系,块设备驱动程序涉及的内核组件,Linux系统Linux系统的设备驱动,80,(2)以进程的read()系统调用为例，分析内核组件的 调用过程 在读操作之前，相应的设备

47、文件已打开；VFS通过块设备文件操作表调用适当的VFS函数，传递的 参数是：文件描述符、文件的偏移量；VFS相应的函数首先访问磁盘高速缓存，若所需数据在高 缓存中，不必启动磁盘读操作；否则启动磁盘读操作。假 定为后者；在磁盘文件系统映射层，计算请求数据的逻辑块号，根据 该文件的索引节点中的索引结构确定该逻辑块号对应的磁 盘物理块号。然后，对块设备发出读请求；,Linux系统Linux系统的设备驱动,81,通用块层接收到所需数据所在的磁盘块号、操作类型，给 I/O调度程序发出启动磁盘读操作的命令；I/O调度程序根据预先定义好的I/O调度策略，将待处理的 I/O数据传送请求进行归类。其目的是尽量将

48、在磁盘上物 理介质相邻的数据请求聚集在一起，以使I/O处理的效率最 高；最后，块设备驱动程序向磁盘控制器的硬件接口发出设备 启动命令，从而进行实际的数据传送。,Linux系统Linux系统的设备驱动,82,4.用于块设备处理的数据结构 设备驱动程序涉及的数据结构有设备请求队列和bio请求块。(1)bio结构 bio是描述块设备I/O操作的描述符 包括一个磁盘存储区标识符(存储区的起始扇区号和扇区总数)；一个或多个描述与I/O操作相关的主存区的段。bio结构以片段为单位的链表形式来组织块I/O操作 一个片段是一小块连续的主存。当缓冲区分散在主存的多个位置 时，bio 结构体也能对内核保证 I/O

49、操作的执行。在bio结构体中有几个相关的域 bi_io_vec、bi_vcnt和bi_idx。,Linux系统Linux系统的设备驱动,83,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系统的设备驱动,84,bio结构、bio_vec结构数组和page结构之间的关系,I/O操作的第一个片段由bi

50、o结构中的bio_io_vec字段所指向，其他的 片段在其后依次存放，共有bi_vcnt个片段；当I/O操作开始执行时，使用着各个片段，这时，bi_idx域会不断地 更新，它总是指向正在操作的当前片段。,bio结构、bio_vec结构数组和page结构之间的关系,Linux系统Linux系统的设备驱动,85,(2)设备队列和请求描述符 设备请求队列 设备请求队列是一个双向链表，包含待处理的请求，由 request_queue结构描述。请求描述符 请求描述符request描述每个块设备待处理的请求。,Linux系统Linux系统的设备驱动,86,request_queue结构的字段,reques