UNIXLinux操作系统内核结构.ppt

UNIX_Linux操作系统内核结构,电子科技大学信软学院,教 师 介 绍,刘玓 教授大型主机教学团队主任大型主机与网络安全工程系主任主要研究方向：操作系统、大型主机、网络应用,课 程 概 述一课程内容简介 1、讲授范围 具体的技术系统及其算法和实现流程，而不是操作系统基本原理；2、通用操作系统的现状和分类 DOS类-结构简单、使用方便、效率低、安全性低 UNIX类-运行高效、结构通用、安全可靠、适应能力强、系统较复杂 MVS类-功能强大、处理能力巨大、系统复杂、较封闭,大巨型机+z/OS,小中型机+UNIX,微型机+Windows,功能强大,简单易用,3、根本特点 分时多用户、开放性 分时多用户：多个用户多个进程同时在一个系统中运行 系统资源高度共享、有效协调 开放性：标准化 结构上的一致性 可移植性 应用软件的编码及系统应用接口 可互操作性 可保持用户原来的使用习惯 异种机之间的互操作 4、教学难点 多用户多进程同步/互斥、数据一致性、访问安全性 开放性硬件依赖性、结构伸缩性、广泛适应性,二、教学目的 1、了解主流操作系统的发展方向 低端操作系统 VS 高端操作系统 2、掌握UNIX类操作系统的内部结构和主要算法 文件、文件系统、进程、时钟、输入输出 3、学习大型程序设计的方法和理念 系统结构、功能流程、数据安全、思维模式 4、奠定系统开发和应用开发的基础 功能选择、层次划分、应用系统模式的确定,三、教材 UNIX操作系统设计（The Design of the UNIX Operating System）（美）Maurice J.Bach 著 陈葆珏 王旭 柳纯录 冯雪山 译 机械工业出版社 2005年10月出版四、考核说明 本课程为“考查”，请以选“考试”的同学进行更正。成绩构成：平时成绩+期末报告,第一章 系统概貌,1.1 发展状况1、发展历史及版本 v.0 1970年 Ken Thompson 和 Dennis Ritchie PDP-7 汇编语言 UNICS v.1 1971年 PDP-11 汇编语言 UNIX v.2 1972年 增加管道功能,v.5 1973年 Dennis Ritchie B language-C language 重写UNIX 第一个高级语言OS v.6 1975年 对外发表UNIX 大学和科研单位应用 v.7 1978年 第一个商业版本 我国开始深入研究应用的最早版本 System III 1981年 完全转向为社会提供的商品软件,System V 1983年 系统功能稳定完善 公布号:1.0、2.0、2.3、3.5、4.0、4.2、4.3 现在最后版本为 System V Release 4(SVR4),2、主要分支和兼容版本BSD 加州大学伯克利分校 XENIX/OpenServer Microsoft、SCO公司HP-UX HP公司AIX IBMSolaris SUN公司IRIX SGI公司Ultrix DEC公司Linux 开放源代码,3、基本功能特征 交互式分时多用户人机间实时交互数据多个用户可同时使用一台机器每个用户可同时执行多个任务软件复用每个程序模块完成单一的功能程序模块可按需任意组合较高的系统和应用开发效率可移植性强数千行汇编码,数十万行C语言代码,配置灵活,适应性强小内核,参数灵活可调核外应用系统,任意裁减限制规则很少界面方便高效内部:系统调用丰富高效外部:shell命令灵活方便可编程应用:GUI 清晰直观功能强大安全机制完善口令、权限、加密等措施完善抗病毒结构误操作的局限和自动恢复功能,多国语言支持支持全世界现有的几十种主要语言网络和资源共享内部:多进程结构易于资源共享外部:支持多种网络协议说明：1、其它操作系统可能包含部分上述UNIX的特征，但非全部（如NT就有部分多用户系统特征）2、这些特征有些是核心直接实现的，有些是由核心提供实现这种特征的方便性和可能性，而由使用者来实现的。,1.2 系统结构,内核,kernel,sh,who,date,wc,vi,grep,date,a.out,ls,app_1,app_2,app_n,UNIX操作系统的整体结构,系统调用（system call）以函数形式提供给核外的命令和上层应用系统使用的一组程序，涵盖操作系统的所有功能。是应用程序请求操作系统服务的唯一通道。内核（kernel）系统调用的集合及实现系统调用的内部算法就形成操作系统核心,1.3 用户看法 进程和文件是UNIX操作系统中最基本的两个概念（抽象）进程：所有处在运行期间的程序实例都是进程 一个进程就是处在运行期间的一个程序实例 涵盖所有的动态概念文件：所有静态的无形数据和有形硬件设备 源程序、命令、图片、邮件、打印机、内存、磁盘等,1.3.1 文件系统/bin usr etc home tmp dev who ls bin lib rc ttys st teach tty0 hd02 admin hwconf liu wang chen aa dir2 save UNIX文件系统树示例,UNIX文件系统的特征：1、树状层次结构 树根、树枝、树叶、路径2、对文件数据的一致对待 文件为有序无格式的字节流，逻辑意义由使用者解释3、文件管理 建立、删除、修改、备份、移动、替换 存储空间的分配和释放4、文件的访问和保护 索引节点（inode）、文件描述符(fd)用户分组、权限划分5、设备文件管理 统一各外部设备的访问模式,char buffer2048;main(int argc,char*argv)int fdold,fdnew;if(argc!=3)printf(“need 2 arguments for copy programn”);exit(1);fdold=open(argv1,O_RDONLY);if(fdold=-1)printf(“cannot open file%sn”,argv1);exit(1);fdnew=creat(argv2,0666);if(fdnew=-1)printf(“cannot create file%sn”,argv2);exit(1);copy(fdold,fdnew);exit(0);copy(int old,int new)int count;while(count=read(old,buffer,sizeof(buffer)0)write(new,buffer,count);,1.3.2 处理环境 程序：可执行的文件 文件头包括：文件的幻数（magic number）编译器的版本号 机器类型 数据段、正文段、工作变量的段大小 程序入口点,文件头,正文段,数据段,工作变量段BSS（符号表、重定位信息等）,进程：程序的一次执行实例 一个程序可同时有多个实例；系统中可同时有多个进程父进程：调用系统调用fork的进程子进程：由系统调用fork产生的新进程执行程序：调用execl,用被执行程序的内容覆盖本进程地址空间,abc,执行abc,xyz,用xyz覆盖abc,执行xyz,xyz,例子：执行可运行文件copy，其功能是拷贝文件，其运行格式为：copy oldfile newfile另一个名为cpfile的程序具体调用copy，其源程序如下：main(int argc,char*argv)if(fork()=0)execl(“copy”,argv1,argv2,0);wait(int*)0);printf(“copy donen”);,在用户环境下，程序的执行通常由命令解释器shell来完成，标准的命令格式为：cmd-options arguments shell可识别的命令类型有：1、简单命令 cat file1 2、多条命令 who;date;ps 3、复合命令 ps e|grep student2(ls;cat file3;pwd)run_log 4、后台命令 ls lR/home/teacher tlist&,1.3.3 构件原语“软件复用”和“模块组装”理念 程序内部：简单功能划分；纯代码设计 程序外部：使用构件原语进行功能重叠和组装 UNIX包含两种构件原语：输入输出重定向 管道,I/O重定向（I/O redirect）：一个进程通常(default)打开三个文件：标准输入文件（fd=0）标准输出文件（fd=1）标准错误输出文件（fd=2）例如：grep abc grep abc file2 grep abc file2 2 file3,管道（pipe）：A进程将标准输出重新定向到管道中去；B进程将标准输入重新定向从管道中来。例如：ps-e|grep student3|wc-l 查看当前系统中与用户student3相关的进程有多少,A进程的输出,B进程的输入,1.4 操作系统服务 UNIX操作系统提供五种主要的服务（也是UNIX核心的五个重要组成部分）：1进程管理 建立、终止、挂起、通信等 2时钟管理 分时共享cpu，时间片，调度 3存储管理 二级存贮器（内存和对换区），分配主存 4文件系统管理 二级存贮结构。分配和收回存贮区和索引节点 5设备管理 对I/O设备进行有控制的存取（多进程系统的特征）,内核提供的服务的特点：服务是透明的 文件类型透明：用户可不关心是普通文件还是外部设备，但O.S自己要关心文件类型！文件系统的透明：文件系统类型、存放的物理位置。存贮方式透明：文件的存放位置、存放方式、存放格式 各用户进程能得到核心相同服务：无论系统程序还是用户程序，平等对待，分时运行,1.5 硬件假设（假设机器硬件只支持的运行状态）UNIX系统上进程的执行分成两种状态：用户态、核心态 用户态：进程正在执行用户代码时的状态 核心态：进程正在执行系统代码（系统调用）时的状态用户态和核心态的区别：用户态：进程只能存取自己的地址空间 核心态：进程可存取核心和用户地址空间 用户态：不能存取特权指令，只能存取自己的指令和数据 核心态：除了能存取自己的指令和数据外，还可存取特权指令,一个进程在运行时必须处在，而且只能处在或者核心态或者用户态下：核心态的进程不是与用户进程平行运行的孤立的进程集合，而是每个用户进程的一部分。“核心分配资源”:一个在核心状态下执行的进程分配资源。一个进程某时在“用户态”下运行，另一时刻又在“核心态”下运行，在其生命周期内可能在这两种状态间切换多次,用户态,核心态,0 1 2 3 4 5 time,A|B|C|D|A|,核心处在核心态下的进程的相应部分的集合硬件是按核心态和用户态来执行操作的，但对这两种状态下正在执行程序的多个用户是相同对待的。,read,write,open,A 进程 B 进程 C 进程,1.5.1 中断与例外中断（要保存上下文）：来自进程之外的事件（外设、时钟等）引起的，发生在两条指令执行之间，中断服务完毕后从下一条指令继续执行。(中断服务是由核心中特殊的函数，而不是特殊的进程来执行的)例外（不保存上下文）：来自进程内部的非期望事件（地址越界，除数为0等），发生在一条指令执行过程中，例外事件处理完后重新执行该指令。,1.5.2 处理机执行级 用一组特权指令给处理机设置一个执行级，以屏蔽同级和低级的中断，最大限度地减少其它事件的干扰，使当前任务顺利执行并尽快完成；但开放更高级的中断，以响应更紧迫的请求。,1.5.3 存储管理 UNIX系统中的存储管理原则(或特点)：1当前正在执行的进程（全部或部分）驻留在主存中；2核心是永远驻留在主存中的（是永远活动的！）；3编译程序产生的指令地址是虚地址（逻辑地址）；4程序运行时核心与硬件（存储管理部件MMU）一起建立虚地址到物理地址的映射。核心永远是活跃的 普通进程具有特定的生命周期（除非人为设定为无限循环）,read,write,open,close,.,核心代码段,A进程,B进程,open,read,read,write,映射,映射,只是用户进程中的核心态下运行的代码段常驻内存，而非整个用户进程常驻内存。这些代码段是“可再入段”（或纯代码段、可共享代码段），被各用户进程段共享，为提高运行速度，避免频烦访问磁盘，故常驻内存，这些代码段的集合就是OS的内核。,第二章 核心导言,2.1 UNIX操作系统的体系结构“文件”和“进程”是UNIX系统的两个最基本实体和中心概念，UNIX系统的所有操作都是以这两者为基础的。整个系统核心由以下五个部分组成：文件系统：文件管理和存储空间管理（节点和空间管理）I/O设备管理：核心缓冲块设备（随机存取设备）核心原始设备（raw设备，字符设备，裸设备）进程控制：进程的调度、同步和通讯 存贮管理：在主存与二级存储之间对程序进行搬迁 时钟管理：把cpu的时间分配给当前最高优先权的进程。,硬 件,硬 件 控 制,字符设备 块设备设备驱动程序,高速缓冲,文件子系统,系 统 调 用 界 面,程 序 库,进程控制子系统,进程间通讯,调度程序,存储管理,用户程序,用户级,核心级,核心级,硬件级,陷入,2.2 系统概念2.2.1 文件系统概貌 1索引节点（index nodeinode）inode特征：文件的内部名称（或代号），方便机器操作；每个文件都有一个且只有一个inode与之对应；inode存放文件的静态参数：存放地点、所有者、文件类型、存取权限、文件大小等；每个文件都可以有多个名字，但都映射到同一个inode上；各inode之间以inode号相区别；,2链结（link）对应命令名 ln,文件i节点,abc,xyz,文件名,一个文件可有多个名字，多个名字都对应同一个文件i节点，每个名字就是该文件节点的一个链结；.一个普通文件的名字个数，就是该文件的链结数；每个链接名可以放在不同的目录下（同一个文件系统下）；删除一个链接名时，文件链接数减一。如链接数不为零，则文件（节点）仍然存在。,使用文件链结的目的：方便用户的使用习惯，如“列目录”，可用ls、dir、list、lc等；误删文件时可补救，又不多占空间。abc和xyz具有相同的i结点号；减少移植应用程序时，因使用指定位置的文件，而拷贝该文件到指定位置去的麻烦。,3符号链结（symbol link）对应命令名 ln-s,文件i节点,abc,xyz,文件名,给文件的名字再取一个名字，而不是给文件节点再取一个名字。链接的是“符号”而不是文件，因此“符号”可以是不存在的文件，即无意义的字符串。abc和xyz具有不同的inode号，xyz的内容是它所指向的名字的字符串，大小是字符串长度为3字节。“普通链结”中各名字必须在同一文件系统中，“符号链结”可在不同的文件系统中。,4活动i节点表（索引节点表）inode表 在内存中存放当前要使用的文件inode的表（或称为活动i节点表），表中的每一个表项对应一个当前正被使用的文件的状态信息。这样要使用（打开）同一个文件的进程不必再到盘上去寻找了，（共享！）,5用户打开文件表（或称用户文件描述符表）在系统中每一个进程都有一个描述该进程的数据结构user（类似于描述文件的i节点），在user中有一个数组，存放一组指针指向系统打开文件表中该进程打开的文件所对应的表项。struct file*u_ofileNOFILE NOFILE 为每个进程最多可同时打开的文件数，这与系统中的进程数和内存大小以及交换区大小等有关系，一般为20100。这个u_ofile数组就是该进程的用户打开文件表。,6系统打开文件表（file表）系统打开文件表主要存放被打开文件的读写指针。因为一个进程在一个时间片内可能读写不完所需内容，需要在下一个时间片继续从上一个时间片结束时的读写位置开始读写，故在进程生存期间应保持一读写指针。此外file表中还存放被打开文件的动态信息：如文件状态、引用计数（当前使用该文件的进程数）等。,A进程,B进程,file表,活动inode表,用户打开文件表,系统打开文件表,活动i节点表,为什么要单独设立一个file表来存放读写指针呢？由于可能有多个进程要共享一个被打开文件的inode，而每个进程的读写指针都不相同，故不能放在inode表中。另一方面，要使不同进程的打开文件指针（文件描述符）或同一进程的不同打开文件指针能够共享一个打开文件指针（协同操作），就不能把读写指针放进某一个进程的用户打开文件表中。因此只能在用户打开文件表和活动inode表之外再建立一个系统打开文件表（file表）来存放读写指针。,UNIX操作系统中共享活动文件的方法：在内存中某个活动文件的副本只有一个，不同的进程采用不同的指针指向这文件的副本。由于任一时刻只有一个进程在运行（微观上看），故该文件也只要求内存中有一个副本即可，只是各个进程有自己的读写指针而已。这是在UNIX系统中共享文件（包括用户文件和系统文件）的主要方法。对其它资源的共享采用的是与之相似的另外几种方法。,2.2.2 进程相关概念：映像 程序以及与动态执行该程序有关的各种信息的集合(类似于历史档案)。它包括存储器映象、通用寄存器映像，地址映射空间、打开文件状态等。进程 对映像的执行。对映像的执行也就是一个程序在虚拟机上动态执行的过程。,可执行文件的构成：进程是可执行文件的一次执行实例，高级语言程序经过编译或汇编语言程序经过汇编后所产生的、缺省名为a.out的可执行文件的结构包括图示四个部分：,文件头,正文段,数据标识段,其它信息段,文件头 文件的幻数（magic number）编译器的版本号 机器类型 正文段、数据标识段、其它信息段的大小 程序入口点正文段 程序的功能代码数据标识段 标识未初始化的数据要占用的空间大小其它信息段 主要用于存放符号表,程序的执行 一个进程在执行系统调用exec时，把可执行文件装入本进程的三个区域中：正文区：对应可执行文件的正文段 数据区：对应可执行文件的数据标识段 堆栈区：新建立的进程工作区 堆栈主要用于传递参数，保护现场，存放返回地址以及为局部动态变量提供存储区。进程在核心态下运行时的工作区为核心栈，在用户态下运行时的工作区为用户栈。核心栈和用户栈不能交叉使用。,堆栈使用举例。有如下程序，在主程序中调用函数，并进行参数传递：main(int argc,char*argv)char buf1024;int number;readfile(buf,number);readfile(char buffer,int line)char*pointer;int temp;,空栈,栈顶指针,栈底指针,低地址,高地址,用户栈,进入主程序时的堆栈状况,栈顶指针,栈底指针,低地址,高地址,调用main()时,argc,argv,本程序返回地址,栈底指针暂存处,buf,number,栈顶指针,栈底指针,低地址,高地址,调用readfile时,argc,argv,本程序返回地址,栈底指针暂存处,buf,number,buffer,line,readfile的返回地址,栈底指针暂存处,pointer,temp,3.进程的标识 进程由其进程标识号PID来识别。0#进程 是由机器上电时“手工”创建的，调用fork创建了1#进程后，成为对换进程（swap）。1#进程 init进程，由它来创建系统初始化过程中所需的其它所有的进程。父进程 调用fork系统调用的进程子进程 由系统调用fork产生的进程除0#进程外，其它所有进程都是另一个进程调用fork后产生的。,进程状态及状态转换运行状态 此时进程正在占用处理机，进程的全部映像驻在内存中。就绪状态 此时进程基本具备了运行条件，正在等待使用处理机。睡眠状态 进程不具备运行条件，需等待某种事件的发生，无法继续执行下去。,调度,调度,睡眠,唤醒,中断,5.在UNIX环境下，进程有如下特征：每个进程在核心进程表（proc数组）都占有一项，在其中保留相应的状态信息。每个进程都有一个“每进程数据区（per process data area-ppda）”保留相应进程更多的信息和核心栈；处理机的全部工作就是在某个时候执行某个进程 一个进程可生成或消灭另一进程 一个进程中可申请并占有资源 一个进程只沿着一个特定的指令序列运行，不会跳转到另一个进程的指令序列中去，也不能访问别的进程的数据和堆栈。（抗病毒传播的重要原因之一）,第三章 数据缓冲区高速缓冲,硬件缓存（cache）由一种高速寄存器（register）组成，主要解决CPU与RAM之间的速度差问题。数据缓冲区高速缓冲（buffer）由软件实现的解决文件系统和物理硬盘之间的数据同步的一种方法。数据缓冲区高速缓冲是UNIX特有的对数据并发访问的一种控制机制。,问题的提出：1、磁盘机械运行速度大大低于处理机的运行速度；2、多进程并发运行，少量的磁盘（通道）I/O成为瓶颈；3、数据访问的随机性，磁盘忙闲不均,解决办法：1、建立一个被称为数据缓冲区高速缓冲（简称高速缓冲）的内部数据缓冲区池（buffer pool）来存放要用的数据；2、写数据时 把数据尽量多地尽量长时间地保存在缓冲池中 延迟写出到磁盘上 以备后续进程使用3、读数据时 先在缓冲池中查找已有的数据 如没有，再从磁盘读取，并保存在缓冲池中 事先预读数据到缓冲池中,3.1 缓冲区及缓冲区首部 缓冲区池由若干个缓冲区组成，每一个缓冲区又由两部分组成：一个实际存放数据的存储区和一个标识该缓冲区的缓冲区首部。,存 储 区,因为缓冲区首部与数据存储区之间有一一对应的关系，所以通常把两者统称为缓冲区。缓冲区是缓冲区池中数据存储的基本单位。,缓冲区首部,缓冲区首部的定义:struct buf 缓冲区标志 标识缓冲区状态 缓冲区链接指针 向前向后串成链表 空闲缓冲区链表指针 联结空闲缓冲区 设备号 标识缓冲区 块号 union 缓冲区中的数据类型 数据块 超级块 柱面块 i节点块 b_un 其它控制信息,3.2 缓冲池的结构1、最近最少使用（LRU）算法：Least Recently Used 程序设计采用模块化和层次化结构，尽量避免使用goto语句，程序跳转少，适应“流水线（pipeline）”体系结构的系统；特定时间段内，程序在一个相对集中空间（代码段）内运行，涉及的数据（广义的：文件名、变量、指针和数组等）的个数相对较少；当前使用过的数据，马上还要使用的可能性最大，较长时间未用过的数据，即将使用的可能性最小。,2、缓冲池设计基本原则：存放有刚使用过的数据尽量长时间地保留在内存中，以便马上还要使用时能在内存中找到；需要腾出内存空间时，把很久都未使用过（即最近最少使用）的数据交换到磁盘上去。这些数据马上还要使用的可能性最小。,3、空闲缓冲区链表 核心维护了一个空闲缓冲区链表，它按照最近被使用的先后次序排列。空闲链表是一个以空闲缓冲区链表头开始的“双向循环链表”。链表的开始和结束都以链表头为标志。,链表头,空闲缓冲区1,空闲缓冲区2,空闲缓冲区3,空闲缓冲区n,4、空闲缓冲区链表操作 取用任意空闲缓冲区 从空闲缓冲区链表的表头位置取下一个空闲缓冲区，后面的空闲缓冲区依次向前移动。释放一个空闲缓冲区 把这个装有数据的空闲缓冲区附加到空闲链表的链尾。只有当该空闲缓冲区所装数据出错时才挂到链头。取用装有指定内容的空闲缓冲区 从链表头开始查找，找到后取下使用，用完后放到链尾。当系统不断从链头取用空闲缓冲区，又把使用过的（装有数据的）缓冲区挂到链尾，一个装有有效数据的缓冲区就会逐渐向链表头移动。在链表头位置的就是“最近最少使用”的空闲缓冲区。,5、空闲缓冲区分类 系统中共设置了四个空闲缓冲区链表，根据缓冲区的不同用途而把它的放入不同的空闲缓冲区链表中。避免在取用空闲缓冲区时，逐个判断缓冲区中的内容。这四个空闲链表是：0#空闲缓冲区链表存放文件系统超级块1#空闲缓冲区链表存放通常使用的数据块2#空闲缓冲区链表存放延迟写、无效数据或错误内容3#空闲缓冲区链表存放没有对应存储空间的缓冲区首部如果某种类型的空闲缓冲区不够用时，核心也从其它空闲缓冲区链表中取用空闲缓冲区。,6、缓冲区设置 当核心需有一个空闲缓冲区时，它根据要装入的数据类型，从相应的空闲缓冲区链表的表头位置取下一个空闲缓冲区，装入一个磁盘数据块；根据该数据块所对应的设备号和块号数据对计算其 hashno（散列、杂凑）值，根据其 hashno 的值放入到相应 hash 链表的链头。hashno=(diskno+blkno)/RND)%BUFHSZ diskno：设备号 blkno：块号 BUFHSZ：最大hash值，通常为63。RND：随机数，其值为：RND=MAXBSIZE/DEV_BSIZE MAXBSIZE：最大文件系统块的大小 DEV_BSIZE：物理设备块大小 hashno 的取值范围：0 62,7、缓冲池的结构 具有相同 hashno 的缓冲区链接在同一个hash链表中，因此系统中共有 63 个hash 链表，分别链接 hashno 为 0 62 的缓冲区。每一个 hash 链表都是一个由链表头指向的双向循环链表，查找某一个指定 hashno 值的缓冲区时，也是从相应的hash链表的表头位置开始向表尾方向进行查找。这 63 个 hash 链表就构成了数据缓冲区高速缓冲的缓冲池，所有的缓冲区都存放在缓冲池中的某一个链表中。,链表头,缓冲区1,缓冲区2,缓冲区3,缓冲区n,hash 链表的结构,缓冲区,缓冲区,缓冲区,缓冲区,缓冲区,缓冲区,缓冲区,缓冲区,缓冲区,空闲链表头,Hash链表头,hashno=0,hashno=1,hashno=62,缓冲池的结构,8、缓冲区的使用 如果要找特定缓冲区，根据hashno从相应的hash链表的表头处开始逐个向后查找；如果找到，则直接取用，并将其移动到hash链的链头；如果未找到，则从相应的空闲缓冲区链表的表头处取下一个空闲缓冲区，填入相应数据，重新计算其hashno，并放到新的hash链表的表头；释放缓冲区时，将该缓冲区仍保留在原hash队列中，同时挂接到空闲缓冲区链表的表尾。（同时在两个队列中）申请缓冲区的两个途径：要指定缓冲区 在hash链表中查找 要空闲缓冲区 在空闲链表中查找,9、进一步说明 一个缓冲区只有当它是空闲状态时，它才同时处在hash链表和空闲链表中。如果不空闲，则它只能处在某一个hash链表中。在空闲缓冲区链表中的缓冲区一定在某个hash链表中；在hash链表中的缓冲区不一定在空闲链中。不存在脱离hash链表的另一个空闲的缓冲区链表。缓冲池中的缓冲区个数是固定不变的，每个缓冲区在不同时刻存放着不同的磁盘数据块，具有不同的hash值，因此处在不同的hash链表中。缓冲区中的数据与某个磁盘数据块一一对应，这种对应有两个特点：一个磁盘数据块在缓冲池中最多只能有一个副本；缓冲区与数据块的对应是动态的，LRU数据块将被释放。,3.3 缓冲区的检索算法 在UNIX文件系统中的下层，即直接与逻辑存储设备联系的部分，包含如下基本算法：getblk 申请一个缓冲区 brelse 释放一个缓冲区 bread 读一个磁盘块 breada 读一个磁盘块，预读另一个磁盘块 bwrite 写磁盘块,1、申请一个缓冲区算法 getblk 根据缓冲池的结构，核心申请一个缓冲区分配个磁盘块时，可能出现的五种典型状况：该块已在hash队列中，并且缓冲区是空闲的；hash队列中找不到该块，需从空闲链表中分配一个缓冲区；hash队列中找不到该块，在从空闲链表中分配一个缓冲区时，发现该空闲缓冲区标记有“延迟写”，核心必须写出缓冲区内容到磁盘上，再重新分配一个空闲缓冲区；hash队列中找不到该块，并且空闲链表已空；该块已在hash队列中，但该缓冲区目前状态为“忙”。,2、释放一个缓冲区算法 brelse 唤醒等待缓冲区的所有进程 提高处理机的执行级别以封锁同级或低级的中断 将该缓冲区放到空闲队列的尾部（缓冲区有效）或头部（缓冲区无效）降低处理机的执行级别以开放中断,3、读一个磁盘块 bread 由 getblk 算法申请一个可用的缓冲区 如果缓冲区中的内容有效，则直接返回该缓冲区 如果缓冲区中的内容无效，则启动磁盘去读所需的数据块 等待磁盘操作完成后返回,算法 bread输入：文件系统号输出：含有数据的缓冲区得到该块的缓冲区（算法getblk）；if（缓冲区数据有效）return（缓冲区）；启动磁盘读；sleep（等待“读盘完成”事件）；return（缓冲区）；,4、读一个磁盘块并预读另一个磁盘块 breada 预读的前提：程序是在一个有限的空间内运行，程序对数据的访问是可预见的。预读的命中率：不一定达到100%，但良好的系统结构和算法可使命中率达到较高的水平。预读的结果：放在缓冲池内，以免需要的时候再去启动磁盘读数据块。,算法 breada输入：（1）立即读的文件系统块号（2）异步读的文件系统块号输出：含有立即读的数据的缓冲区if（第一块不在高速缓冲中）为第一块获得缓冲区（getblk）；if（缓冲区内容无效）启动磁盘读；if（第二块不在高速缓冲中）为第二块获得缓冲区（getblk）；if（缓冲区数据有效）释放缓冲区（brelse）；else启动磁盘读；if（第一块本来就在高速缓冲中）读第一块（bread）；return（缓冲区）；sleep（第一个缓冲区包含有效数据的事件）；return（缓冲区）；,5、写磁盘块 bwrite 启动磁盘驱动程序的写操作 如果是“同步写”，则本进程睡眠等待磁盘写操作的完成，磁盘写操作完成后，中断唤醒本进程，本进程释放该缓冲区并返回；如果是“异步写”，则无需等待磁盘写操作的完成，将缓冲区放到空闲链表的表头，以便随后某个进程申请空闲缓冲区时，将其写到磁盘上去。本进程不再关心该缓冲区实际被写出的时间和结果，而直接返回去作其它事情。事实上无论是同步写还是异步写，其根本区别在于本进程是否等待磁盘驱动程序完成操作后所发出的中断信号。,算法 bwrite输入：缓冲区输出：无启动磁盘读；if（I/O同步）sleep（等待“I/O完成”事件）；释放缓冲区（brelse）；else if（缓冲区标记着延迟写）为缓冲区做标记以放到空闲缓冲区链表头部；,3.3 数据缓冲区高速缓冲的优缺点优点：提供了对磁盘块的统一的存取方法 消除了用户对用户缓冲区中数据的特殊对齐需要 减少了磁盘访问的次数，提高了系统的整体I/O效率 有助于保持文件系统的完整性缺点：数据未及时写盘而带来的风险 额外的数据拷贝过程，大量数据传输时影响性能,第四章 文件和文件系统的内部结构,现代UNIX的文件系统通常可由三大模块组成：本地文件系统（UFS）User File System网络文件系统（NFS）Network File System虚拟文件系统（VFS）Virtual File System,本地文件系统（UFS）是UNIX系统中的基本文件系统，它通常固定存放在本地机器的存贮设备上，任何一种结构形式的文件系统都必然会直接或间接地与某个本地文件系统相联系。本地文件系统的构成 一个根文件系统+若干子文件系统所组成根文件系统 存放本操作系统的最主要和最基本的部分 可独立启动运行 系统起动后，根文件系统就不能卸下来子文件系统 主要存放应用程序和用户文件 一般不能独立启动 系统运行过程中可随时安装和卸下,网络文件系统（NFS）是本地机器上的文件系统和远地机器上的文件系统之间的介质，它管理和控制所有有关对远地文件的各种操作，给本地用户提供一个访问远地文件的使用方便的高层接口，避免用户直接涉及网络通讯方面的具体细节。,虚拟文件系统（VFS）VFS是整个操作系统的用户界面，它给用户提供一个统一的文件系统使用接口，避免用户涉及各个子文件系统的特征部分。用户感觉使用的是一个整体的，比本地机器上实际硬盘空间大得多的文件系统。虚构文件系统接受来自用户的操作请求，根据该操作所访问的文件是存放在本地机器上，还是存放在远地机器上而分别把操作交给本地文件系统或网络文件系统；本地文件系统或网络文件系统（实际上再传给远地机器上的本地文件系统）进行相应的操作后，将结果返回到虚拟文件系统中再传回给用户。,网 络,虚拟文件系统VFS,网络文件系统NFS,本地文件系统UFS,物理存储介质,虚拟文件系统VFS,网络文件系统NFS,本地文件系统UFS,物理存储介质,用户,用户,A机器,B机器,基于虚拟文件系统的体系结构,4.1 文件系统结构 4.1.1 本地文件系统1文件的存贮结构 UNIX的普通文件的逻辑结构是无格式的有序字节流，而它们的物理存贮结构是以索引方式来组织的。每个文件都是由一个索引节点i节点来表示的，每个i节点由其i节点号来标识。i节点通常以静态的形式存放在磁盘的i节点表中。每个磁盘i节点表项是由数据结构icommon定义的，描述对应文件的静态参数。,超级块,磁盘i节点表,数据存储区,磁盘icommon表,icommon,icommon,icommon,icommon,icommon,文件所有者标识（UID）用户组标识（GID）文件类型（FIFO、DIR、CHR、BLK、REG、LNK等）文件保护模式（存取许可权）mode文件存取时间（atime,mtime,ctime）链接数目 link文件大小 size文件数据块索引表 index table,icommon 与 inode 的关系 进程要读写一个文件时，先在内存的活动i节点表（即inode表）中申请一个空闲的活动i节点，并把磁盘上i节点（icommon）中的各项参数读入其中，当核心操作完成后，如果必要，就把在内存中的活动i节点写回到磁盘上去。内存活动i节点由数据结构inode来定义，它除了包含磁盘上对应的icommon中的各项参数外，还包含有其它的参数，如该活动i节点的状态、文件所在的逻辑设备号、i节点号、活动i节点链接指针，最近使用的i节点在目录中的位置等动态信息。,struct inode 活动i节点链接指针 状态标志 设备号 i节点号 最近访问的i节点在目录中的位置 空闲i节点链接指针 struct incommon 文件模式和类型（FIFO、DIR、CHR、BLK、REG、LNK等）文件链接数 文件所有者标识数（UID）文件所属用户组标识数（GID）文件大小 文件最近存取时间（atime,mtime,ctime）数据块索引表 其它信息,2、数据块索引表 数据块索引表用于检索本文件占用的数据块。它包含12项直接索引表目和3项间接索引表目。根据要读写的数据在文件中的位置可计算出该数据所在的逻辑块号，查索引表就可找到逻辑块所在的文件系统块号。系统根据计算出来的逻辑块号判断是否包含在直接索引表中，如果是，则取出直接索引表中的文件系统块号；如不是，则看是否包含在一次间接索引块中，否则再寻找二次和三次间接索引块。最长要存取三次间址索引块才能找到相应数据的文件系统块号（要取出数据则要读4次磁盘）。,数据块索引表,一级间址块,二级间址块,三级间址块,数据块,3、inode表的结构 在内存中，活动i节点表类似于数据缓冲区高速缓冲中的缓冲池结构。活动i节点表中的每一项就是一个活动i节点缓冲区，用来存放一个被打开文件的inode。（以下把活动i节点缓冲区简称为“活动i节点”）。空闲的活动i节点相互链接在一起构成“空闲活动i节点链表”，这是一个双向（非循环）链表，分别由链头指针和链尾指针指向空闲活动i节点链表的开始和结束。如下图所示：,链表头,空闲i节点1,空闲i节点2,空闲i节点3,空闲i节点n,空闲活动i节点链表为双向（非循环）链表，分别由链表头指针和链表尾指针指向空闲链表的首尾。,NULL,链表尾,活动i节点hash链表 当某个文件（即某个磁盘i节点）被打开时，根据该i节点所对应的设备号和i节点号计算其hash值：hn=(devno+inumber)%64可得到063共64个hash值。具有相同hash值的活动i节点链接在同一个hash链表中，这样内存中就有64个hash链表，每个hash链表都是由hash链头开始的双向链表（与数据缓冲区链表不同的是此处的空闲和非空闲链表都是非循环的）。内存活动i节点表就是由这64个hash链表组成。如下图所示：,inode,inode,inode,inode,inode,inode,inode,i