UNIXLinux操作系统内核结构

UNIX_Linux操作系统内核结构电子科技大学信软学院教师介绍 刘玓教授 大型主机教学团队主任 大型主机与网络安全工程系主任 Email：liudi@uestc.edu.cn 主要研究方向：操作系统、大型主机、网络应用课程概述一．课程内容简介1、讲授范围具体的技术系统及其算法和实现流程，而不是操作系统基本原理；2、通用操作系统的现状和分类DOS类----结构简单、使用方便、效率低、安全性低UNIX类----运行高效、结构通用、安全可靠、适应能力强、系统较复杂MVS类----功能强大、处理能力巨大、系统复杂、较封闭大巨型机+z/OS小中型机+UNIX微型机+Windows功能强大简单易用3、根本特点分时多用户、开放性分时多用户：多个用户多个进程同时在一个系统中运行系统资源高度共享、有效协调开放性：标准化——结构上的一致性可移植性——应用软件的编码及系统应用接口可互操作性——可保持用户原来的使用习惯异种机之间的互操作4、教学难点多用户多进程——同步/互斥、数据一致性、访问安全性开放性——硬件依赖性、结构伸缩性、广泛适应性二、教学目的1、了解主流操作系统的发展方向低端操作系统VS高端操作系统2、掌握UNIX类操作系统的内部结构和主要算法文件、文件系统、进程、时钟、输入输出3、学习大型程序的和理念系统结构、功能流程、数据安全、思维模式4、奠定系统开发和应用开发的基础功能选择、层次划分、应用系统模式的确定三、教材《UNIX操作系统设计》（TheDesignoftheUNIXOperatingSystem）（美）MauriceJ.Bach著陈葆珏王旭柳纯录冯雪山译机械工业出版社2005年10月出版四、考核说明本课程为“考查”，请以选“考试”的同学进行更正。成绩构成：平时成绩+期末报告第一章系统概貌 1.1发展状况1、发展历史及版本v.01970年KenThompson和DennisRitchiePDP-7汇编语言UNICSv.11971年PDP-11汇编语言UNIXv.21972年增加管道功能v.51973年DennisRitchieBlanguage----Clanguage重写UNIX第一个高级语言OSv.61975年对外发表UNIX大学和科研单位应用v.71978年第一个商业版本我国开始深入研究应用的最早版本SystemIII1981年完全转向为社会提供的商品软件SystemV1983年系统功能稳定完善公布号:1.0、2.0、2.3、3.5、4.0、4.2、4.3现在最后版本为SystemVRelease4(SVR4)2、主要分支和兼容版本 BSD加州大学伯克利分校 XENIX/OpenServer Microsoft、SCO公司 HP-UXHP公司 AIXIBM SolarisSUN公司 IRIXSGI公司 UltrixDEC公司 Linux开放源代码3、基本功能特征交互式分时多用户 人机间实时交互数据 多个用户可同时使用一台机器 每个用户可同时执行多个任务软件复用 每个程序模块完成单一的功能 程序模块可按需任意组合 较高的系统和应用开发效率可移植性强 数千行汇编码,数十万行C语言代码配置灵活,适应性强 小内核,参数灵活可调 核外应用系统,任意裁减 限制规则很少界面方便高效 内部:系统调用丰富高效 外部:shell命令灵活方便可编程 应用:GUI清晰直观功能强大安全机制完善 口令、权限、加密等措施完善 抗病毒结构 误操作的局限和自动恢复功能多国语言支持 支持全世界现有的几十种主要语言网络和资源共享 内部:多进程结构易于资源共享 外部:支持多种网络 说明： 1、其它操作系统可能包含部分上述UNIX的特征，但非全部（如NT就有部分多用户系统特征） 2、这些特征有些是核心直接实现的，有些是由核心提供实现这种特征的方便性和可能性，而由使用者来实现的。 1.2系统结构硬件内核kernelshwhodatewcvigrepdatea.outlsapp_1app_2app_nUNIX操作系统的整体结构系统调用（systemcall）以函数形式提供给核外的命令和上层应用系统使用的一组程序，涵盖操作系统的所有功能。是应用程序请求操作系统服务的唯一通道。 内核（kernel） 系统调用的集合及实现系统调用的内部算法就形成操作系统核心 1.3用户看法进程和文件是UNIX操作系统中最基本的两个概念（抽象） 进程： 所有处在运行期间的程序实例都是进程 一个进程就是处在运行期间的一个程序实例 涵盖所有的动态概念 文件： 所有静态的无形数据和有形硬件设备 源程序、命令、图片、邮件、打印机、内存、磁盘等1.3.1文件系统/ binusretchometmpdev wholsbinlibrcttysstteachtty0hd02 adminhwconfliuwangchen aadir2save UNIX文件系统树示例UNIX文件系统的特征：1、树状层次结构树根、树枝、树叶、路径2、对文件数据的一致对待文件为有序无格式的字节流，逻辑意义由使用者解释3、文件管理建立、删除、修改、备份、移动、替换存储空间的分配和释放4、文件的访问和保护索引节点（inode）、文件描述符(fd)用户分组、权限划分5、设备文件管理统一各外部设备的访问模式charbuffer[2048];main(intargc,char*argv[]){ intfdold,fdnew; if(argc!=3) { printf(“need2argumentsforcopyprogram\n”); exit(1); } fdold=open(argv[1],O_RDONLY); if(fdold==-1) { printf(“cannotopenfile%s\n”,argv[1]); exit(1); } fdnew=creat(argv[2],0666); if(fdnew==-1) { printf(“cannotcreatefile%s\n”,argv[2]); exit(1); } copy(fdold,fdnew); exit(0);}copy(intold,intnew){ intcount; while((count=read(old,buffer,sizeof(buffer)))>0) write(new,buffer,count);}1.3.2处理环境程序：可执行的文件文件头包括：·文件的幻数（magicnumber）·编译器的版本号·机器类型·数据段、正文段、工作变量的段大小·程序入口点文件头正文段数据段工作变量段BSS（符号表、重定位信息等）进程：程序的一次执行实例一个程序可同时有多个实例；系统中可同时有多个进程父进程：调用系统调用fork的进程子进程：由系统调用fork产生的新进程执行程序：调用execl,用被执行程序的内容覆盖本进程地址空间abc执行abcxyz用xyz覆盖abc执行xyzxyz 例子： 执行可运行文件copy，其功能是拷贝文件，其运行格式为： copyoldfilenewfile 另一个名为cpfile的程序具体调用copy，其源程序如下： main(intargc,char*argv[]) { if(fork()==0) execl(“copy”,argv[1],argv[2]],0); wait((int*)0); printf(“copydone\n”); } 在用户环境下，程序的执行通常由命令解释器shell来完成，标准的命令格式为：cmd[-options][arguments] shell可识别的命令类型有： 1、简单命令 catfile1 2、多条命令 who;date;ps 3、复合命令 ps–e|grepstudent2 (ls;catfile3;pwd)>run_log 4、后台命令 ls–lR/home/teacher>tlist&1.3.3构件原语“软件复用”和“模块组装”理念 程序内部： 简单功能划分；纯代码设计 程序外部： 使用构件原语进行功能重叠和组装 UNIX包含两种构件原语： ①输入输出重定向 ②管道I/O重定向（I/Oredirect）：一个进程通常(default)打开三个文件： 标准输入文件（fd=0） 标准输出文件（fd=1） 标准错误输出文件（fd=2） 例如： grepabc grepabc<file1 grepabc<file1>file2 grepabc<file1>file22>file3管道（pipe）： A进程将标准输出重新定向到管道中去； B进程将标准输入重新定向从管道中来。 例如： ps-e|grepstudent3|wc-l 查看当前系统中与用户student3相关的进程有多少 A进程的输出B进程的输入 1.4操作系统服务UNIX操作系统提供五种主要的服务（也是UNIX核心的五个重要组成部分）：1．进程管理建立、终止、挂起、通信等2．时钟管理分时共享cpu，时间片，调度3．存储管理二级存贮器（内存和对换区），分配主存4．文件系统管理二级存贮结构。分配和收回存贮区和索引节点5．设备管理对I/O设备进行有控制的存取（多进程系统的特征）内核提供的服务的特点： 服务是透明的 ①文件类型透明： 用户可不关心是普通文件还是外部设备，但O.S自己要关心文件类型！ ②文件系统的透明： 文件系统类型、存放的物理位置。 ③存贮方式透明： 文件的存放位置、存放方式、存放格式 ④各用户进程能得到核心相同服务： 无论系统程序还是用户程序，平等对待，分时运行 1.5硬件假设（假设机器硬件只支持的运行状态）UNIX系统上进程的执行分成两种状态：用户态、核心态用户态：进程正在执行用户代码时的状态核心态：进程正在执行系统代码（系统调用）时的状态用户态和核心态的区别：①用户态：进程只能存取自己的地址空间核心态：进程可存取核心和用户地址空间②用户态：不能存取特权指令，只能存取自己的指令和数据核心态：除了能存取自己的指令和数据外，还可存取特权指令一个进程在运行时必须处在，而且只能处在或者核心态或者用户态下： 核心态的进程不是与用户进程平行运行的孤立的进程集合，而是每个用户进程的一部分。 “核心分配资源”: 一个在核心状态下执行的进程分配资源。 一个进程某时在“用户态”下运行，另一时刻又在“核心态”下运行，在其生命周期内可能在这两种状态间切换多次用户态核心态012345timeA|B|C|D|A|核心——处在核心态下的进程的相应部分的集合 硬件是按核心态和用户态来执行操作的，但对这两种状态下正在执行程序的多个用户是相同对待的。 readwriteopenA进程B进程C进程1.5.1中断与例外 中断（要保存上下文）： 来自进程之外的事件（外设、时钟等）引起的，发生在两条指令执行之间，中断服务完毕后从下一条指令继续执行。(中断服务是由核心中特殊的函数，而不是特殊的进程来执行的) 例外（不保存上下文）： 来自进程内部的非期望事件（地址越界，除数为0等），发生在一条指令执行过程中，例外事件处理完后重新执行该指令。1.5.2处理机执行级 用一组特权指令给处理机设置一个执行级，以屏蔽同级和低级的中断，最大限度地减少其它事件的干扰，使当前任务顺利执行并尽快完成；但开放更高级的中断，以响应更紧迫的请求。 中断事件 中断级别 硬件故障 高低 时钟 硬盘 网络 终端 软件中断1.5.3存储管理UNIX系统中的存储管理原则(或特点)：1．当前正在执行的进程（全部或部分）驻留在主存中；2．核心是永远驻留在主存中的（是永远活动的！）；3．编译程序产生的指令地址是虚地址（逻辑地址）；4．程序运行时核心与硬件（存储管理部件MMU）一起建立虚地址到物理地址的映射。 核心永远是活跃的 普通进程具有特定的生命周期（除非人为设定为无限循环）readwriteopenclose...核心代码段A进程B进程openreadreadwrite映射映射只是用户进程中的核心态下运行的代码段常驻内存，而非整个用户进程常驻内存。这些代码段是“可再入段”（或纯代码段、可共享代码段），被各用户进程段共享，为提高运行速度，避免频烦访问磁盘，故常驻内存，这些代码段的集合就是OS的内核。第二章核心导言 2.1UNIX操作系统的体系结构“文件”和“进程”是UNIX系统的两个最基本实体和中心概念，UNIX系统的所有操作都是以这两者为基础的。整个系统核心由以下五个部分组成：①文件系统：文件管理和存储空间管理（节点和空间管理）②I/O设备管理：核心→缓冲→块设备（随机存取设备）核心→原始设备（raw设备，字符设备，裸设备）③进程控制：进程的调度、同步和通讯④存贮管理：在主存与二级存储之间对程序进行搬迁⑤时钟管理：把cpu的时间分配给当前最高优先权的进程。硬件硬件控制字符设备块设备设备驱动程序高速缓冲文件子系统系统调用界面程序库进程控制子系统进程间通讯调度程序存储管理用户程序用户级核心级核心级硬件级陷入 2.2系统概念2.2.1文件系统概貌1．索引节点（indexnode——inode）inode特征： 文件的内部名称（或代号），方便机器操作； 每个文件都有一个且只有一个inode与之对应； inode存放文件的静态参数：存放地点、所有者、文件类型、存取权限、文件大小等； 每个文件都可以有多个名字，但都映射到同一个inode上； 各inode之间以inode号相区别；2．链结（link）——对应命令名ln文件i节点abcxyz文件名·一个文件可有多个名字，多个名字都对应同一个文件i节点，每个名字就是该文件节点的一个链结；.一个普通文件的名字个数，就是该文件的链结数；·每个链接名可以放在不同的目录下（同一个文件系统下）；·删除一个链接名时，文件链接数减一。如链接数不为零，则文件（节点）仍然存在。 使用文件链结的目的： ①方便用户的使用习惯，如“列目录”，可用ls、dir、list、lc等； ②误删文件时可补救，又不多占空间。abc和xyz具有相同的i结点号； ③减少移植应用程序时，因使用指定位置的文件，而拷贝该文件到指定位置去的麻烦。3．符号链结（symbollink）——对应命令名ln-s文件i节点abcxyz文件名 给文件的名字再取一个名字，而不是给文件节点再取一个名字。 链接的是“符号”而不是文件，因此“符号”可以是不存在的文件，即无意义的字符串。 abc和xyz具有不同的inode号，xyz的内容是它所指向的名字的字符串，大小是字符串长度为3字节。 “普通链结”中各名字必须在同一文件系统中，“符号链结”可在不同的文件系统中。4．活动i节点表（索引节点表）——inode表在内存中存放当前要使用的文件inode的表（或称为活动i节点表），表中的每一个表项对应一个当前正被使用的文件的状态信息。这样要使用（打开）同一个文件的进程不必再到盘上去寻找了，（共享！）5．用户打开文件表（或称用户文件描述符表）在系统中每一个进程都有一个描述该进程的数据结构user（类似于描述文件的i节点），在user中有一个数组，存放一组指针指向系统打开文件表中该进程打开的文件所对应的表项。structfile*u_ofile[NOFILE]NOFILE为每个进程最多可同时打开的文件数，这与系统中的进程数和内存大小以及交换区大小等有关系，一般为20~100。这个u_ofile数组就是该进程的用户打开文件表。6．系统打开文件表（file表）系统打开文件表主要存放被打开文件的读写指针。因为一个进程在一个时间片内可能读写不完所需内容，需要在下一个时间片继续从上一个时间片结束时的读写位置开始读写，故在进程生存期间应保持一读写指针。此外file表中还存放被打开文件的动态信息：如文件状态、引用计数（当前使用该文件的进程数）等。A进程B进程file表活动inode表用户打开文件表系统打开文件表活动i节点表为什么要单独设立一个file表来存放读写指针呢？ 由于可能有多个进程要共享一个被打开文件的inode，而每个进程的读写指针都不相同，故不能放在inode表中。 另一方面，要使不同进程的打开文件指针（文件描述符）或同一进程的不同打开文件指针能够共享一个打开文件指针（协同操作），就不能把读写指针放进某一个进程的用户打开文件表中。 因此只能在用户打开文件表和活动inode表之外再建立一个系统打开文件表（file表）来存放读写指针。UNIX操作系统中共享活动文件的方法：在内存中某个活动文件的副本只有一个，不同的进程采用不同的指针指向这文件的副本。由于任一时刻只有一个进程在运行（微观上看），故该文件也只要求内存中有一个副本即可，只是各个进程有自己的读写指针而已。这是在UNIX系统中共享文件（包括用户文件和系统文件）的主要方法。对其它资源的共享采用的是与之相似的另外几种方法。2.2.2进程 相关概念： 映像—— 程序以及与动态执行该程序有关的各种信息的集合(类似于历史档案)。它包括存储器映象、通用寄存器映像，地址映射空间、打开文件状态等。 进程—— 对映像的执行。对映像的执行也就是一个程序在虚拟机上动态执行的过程。 可执行文件的构成：进程是可执行文件的一次执行实例，高级语言程序经过编译或汇编语言程序经过汇编后所产生的、缺省名为a.out的可执行文件的结构包括图示四个部分：文件头正文段数据标识段其它信息段文件头——·文件的幻数（magicnumber）·编译器的版本号·机器类型·正文段、数据标识段、其它信息段的大小·程序入口点正文段——程序的功能代码数据标识段——标识未初始化的数据要占用的空间大小其它信息段——主要用于存放符号表 程序的执行 一个进程在执行系统调用exec时，把可执行文件装入本进程的三个区域中： 正文区：对应可执行文件的正文段 数据区：对应可执行文件的数据标识段 堆栈区：新建立的进程工作区 堆栈主要用于传递参数，保护现场，存放返回地址以及为局部动态变量提供存储区。 进程在核心态下运行时的工作区为核心栈，在用户态下运行时的工作区为用户栈。核心栈和用户栈不能交叉使用。堆栈使用举例。有如下程序，在主程序中调用函数，并进行参数传递：main(intargc,char*argv[]){charbuf[1024];intnumber;…readfile(buf,number);…}readfile(charbuffer[],intline){char*pointer;inttemp;…}空栈栈顶指针栈底指针低地址高地址用户栈进入主程序时的堆栈状况栈顶指针栈底指针低地址高地址调用main()时argc,argv本程序返回地址栈底指针暂存处buf,number栈顶指针栈底指针低地址高地址调用readfile时argc,argv本程序返回地址栈底指针暂存处buf,numberbuffer,linereadfile的返回地址栈底指针暂存处pointer,temp3.进程的标识进程由其进程标识号PID来识别。0#进程是由机器上电时“手工”创建的，调用fork创建了1#进程后，成为对换进程（swap）。1#进程init进程，由它来创建系统初始化过程中所需的其它所有的进程。父进程调用fork系统调用的进程子进程由系统调用fork产生的进程除0#进程外，其它所有进程都是另一个进程调用fork后产生的。 进程状态及状态转换 ①运行状态 此时进程正在占用处理机，进程的全部映像驻在内存中。 ②就绪状态 此时进程基本具备了运行条件，正在等待使用处理机。 ③睡眠状态 进程不具备运行条件，需等待某种事件的发生，无法继续执行下去。运行睡眠就绪调度调度睡眠唤醒中断5.在UNIX环境下，进程有如下特征： ①每个进程在核心进程表（proc数组）都占有一项，在其中保留相应的状态信息。 ②每个进程都有一个“每进程数据区（perprocessdataarea----ppda）”保留相应进程更多的信息和核心栈； ③处理机的全部工作就是在某个时候执行某个进程 ④一个进程可生成或消灭另一进程 ⑤一个进程中可申请并占有资源 ⑥一个进程只沿着一个特定的指令序列运行，不会跳转到另一个进程的指令序列中去，也不能访问别的进程的数据和堆栈。（抗病毒传播的重要原因之一）第三章数据缓冲区高速缓冲硬件缓存（cache）由一种高速寄存器（register）组成，主要解决CPU与RAM之间的速度差问。数据缓冲区高速缓冲（buffer）由软件实现的解决文件系统和物理硬盘之间的数据同步的一种方法。 数据缓冲区高速缓冲是UNIX特有的对数据并发访问的一种控制机制。问题的提出：1、磁盘机械运行速度大大低于处理机的运行速度；2、多进程并发运行，少量的磁盘（通道）I/O成为瓶颈；3、数据访问的随机性，磁盘忙闲不均解决办法：1、建立一个被称为数据缓冲区高速缓冲（简称高速缓冲）的内部数据缓冲区池（bufferpool）来存放要用的数据；2、写数据时把数据尽量多地尽量长时间地保存在缓冲池中延迟写出到磁盘上以备后续进程使用3、读数据时先在缓冲池中查找已有的数据如没有，再从磁盘读取，并保存在缓冲池中事先预读数据到缓冲池中3.1缓冲区及缓冲区首部缓冲区池由若干个缓冲区组成，每一个缓冲区又由两部分组成：一个实际存放数据的存储区和一个标识该缓冲区的缓冲区首部。存储区因为缓冲区首部与数据存储区之间有一一对应的关系，所以通常把两者统称为缓冲区。缓冲区是缓冲区池中数据存储的基本单位。缓冲区首部缓冲区首部的定义:structbuf{缓冲区标识缓冲区状态缓冲区链接指针向前向后串成链表空闲缓冲区链表指针联结空闲缓冲区设备号标识缓冲区块号union{缓冲区中的数据类型数据块超级块柱面块i节点块}b_un其它控制信息}3.2缓冲池的结构 1、最近最少使用（LRU）算法：LeastRecentlyUsed 程序设计采用模块化和层次化结构，尽量避免使用goto语句，程序跳转少，适应“流水线（pipeline）”体系结构的系统； 特定时间段内，程序在一个相对集中空间（代码段）内运行，涉及的数据（广义的：文件名、变量、指针和数组等）的个数相对较少； 当前使用过的数据，马上还要使用的可能性最大，较长时间未用过的数据，即将使用的可能性最小。2、缓冲池设计基本原则：存放有刚使用过的数据尽量长时间地保留在内存中，以便马上还要使用时能在内存中找到；需要腾出内存空间时，把很久都未使用过（即最近最少使用）的数据交换到磁盘上去。这些数据马上还要使用的可能性最小。3、空闲缓冲区链表核心维护了一个空闲缓冲区链表，它按照最近被使用的先后次序排列。空闲链表是一个以空闲缓冲区链表头开始的“双向循环链表”。链表的开始和结束都以链表头为标志。链表头空闲缓冲区1空闲缓冲区2空闲缓冲区3空闲缓冲区n4、空闲缓冲区链表操作 取用任意空闲缓冲区从空闲缓冲区链表的表头位置取下一个空闲缓冲区，后面的空闲缓冲区依次向前移动。 释放一个空闲缓冲区把这个装有数据的空闲缓冲区附加到空闲链表的链尾。只有当该空闲缓冲区所装数据出错时才挂到链头。 取用装有指定内容的空闲缓冲区从链表头开始查找，找到后取下使用，用完后放到链尾。当系统不断从链头取用空闲缓冲区，又把使用过的（装有数据的）缓冲区挂到链尾，一个装有有效数据的缓冲区就会逐渐向链表头移动。在链表头位置的就是“最近最少使用”的空闲缓冲区。5、空闲缓冲区分类系统中共设置了四个空闲缓冲区链表，根据缓冲区的不同用途而把它的放入不同的空闲缓冲区链表中。避免在取用空闲缓冲区时，逐个判断缓冲区中的内容。这四个空闲链表是：0#空闲缓冲区链表——存放文件系统超级块1#空闲缓冲区链表——存放通常使用的数据块2#空闲缓冲区链表——存放延迟写、无效数据或错误内容3#空闲缓冲区链表——存放没有对应存储空间的缓冲区首部如果某种类型的空闲缓冲区不够用时，核心也从其它空闲缓冲区链表中取用空闲缓冲区。6、缓冲区设置当核心需有一个空闲缓冲区时，它根据要装入的数据类型，从相应的空闲缓冲区链表的表头位置取下一个空闲缓冲区，装入一个磁盘数据块；根据该数据块所对应的设备号和块号数据对计算其hashno（散列、杂凑）值，根据其hashno的值放入到相应hash链表的链头。hashno=((diskno+blkno)/RND)%BUFHSZdiskno：设备号blkno：块号BUFHSZ：最大hash值，通常为63。RND：随机数，其值为：RND=MAXBSIZE/DEV_BSIZEMAXBSIZE：最大文件系统块的大小DEV_BSIZE：物理设备块大小hashno的取值范围：0~627、缓冲池的结构具有相同hashno的缓冲区链接在同一个hash链表中，因此系统中共有63个hash链表，分别链接hashno为0~62的缓冲区。每一个hash链表都是一个由链表头指向的双向循环链表，查找某一个指定hashno值的缓冲区时，也是从相应的hash链表的表头位置开始向表尾方向进行查找。这63个hash链表就构成了数据缓冲区高速缓冲的缓冲池，所有的缓冲区都存放在缓冲池中的某一个链表中。链表头缓冲区1缓冲区2缓冲区3缓冲区nhash链表的结构缓冲区缓冲区缓冲区缓冲区缓冲区缓冲区缓冲区缓冲区缓冲区空闲链表头Hash链表头hashno=0hashno=1hashno=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）； } elseif（缓冲区标记着延迟写） 为缓冲区做标记以放到空闲缓冲区链表头部；}3.3数据缓冲区高速缓冲的优缺点优点：提供了对磁盘块的统一的存取方法消除了用户对用户缓冲区中数据的特殊对齐需要减少了磁盘访问的次数，提高了系统的整体I/O效率有助于保持文件系统的完整性缺点：数据未及时写盘而带来的风险额外的数据拷贝过程，大量数据传输时影响性能第四章文件和文件系统的内部结构现代UNIX的文件系统通常可由三大模块组成： ①本地文件系统（UFS）——UserFileSystem ②网络文件系统（NFS）——NetworkFileSystem ③虚拟文件系统（VFS）——VirtualFileSystem本地文件系统（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表icommonicommonicommonicommonicommon 文件所有者标识（UID） 用户组标识（GID） 文件类型（FIFO、DIR、CHR、BLK、REG、LNK等） 文件保护模式（存取许可权）mode 文件存取时间（atime,mtime,ctime） 链接数目link 文件大小size 文件数据块索引表indextableicommon与inode的关系进程要读写一个文件时，先在内存的活动i节点表（即inode表）中申请一个空闲的活动i节点，并把磁盘上i节点（icommon）中的各项参数读入其中，当核心操作完成后，如果必要，就把在内存中的活动i节点写回到磁盘上去。内存活动i节点由数据结构inode来定义，它除了包含磁盘上对应的icommon中的各项参数外，还包含有其它的参数，如该活动i节点的状态、文件所在的逻辑设备号、i节点号、活动i节点链接指针，最近使用的i节点在目录中的位置等动态信息。structinode{活动i节点链接指针状态标志设备号i节点号最近访问的i节点在目录中的位置空闲i节点链接指针structincommon{文件模式和类型（FIFO、DIR、CHR、BLK、REG、LNK等）文件链接数文件所有者标识数（UID）文件所属用户组标识数（GID）文件大小文件最近存取时间（atime,mtime,ctime）数据块索引表其它信息}}2、数据块索引表数据块索引表用于检索本文件占用的数据块。它包含12项直接索引表目和3项间接索引表目。根据要读写的数据在文件中的位置可计算出该数据所在的逻辑块号，查索引表就可找到逻辑块所在的文件系统块号。系统根据计算出来的逻辑块号判断是否包含在直接索引表中，如果是，则取出直接索引表中的文件系统块号；如不是，则看是否包含在一次间接索引块中，否则再寻找二次和三次间接索引块。最长要存取三次间址索引块才能找到相应数据的文件系统块号（要取出数据则要读4次磁盘）。数据块索引表一级间址块二级间址块三级间址块数据块 直接0 直接1 直接2 直接11 一次间址 二次间址 三次间址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可得到0~63共64个hash值。具有相同hash值的活动i节点链接在同一个hash链表中，这样内存中就有64个hash链表，每个hash链表都是由hash链头开始的双向链表（与数据缓冲区链表不同的是此处的空闲和非空闲链表都是非循环的）。内存活动i节点表就是由这64个hash链表组成。如下图所示：inodeinodeinodeinodeinodeinodeinodeinodeinode空闲链表头Hash链表头hn=0hn=1hn=63NULL空闲链表尾活动inode表的结构4、文件系统的存储结构在UNIX系统中，一个物理磁盘通常被划分成一个或多个逻辑文件系统（简称文件系统或子文件系统），每个逻辑文件系统都被当作一个由逻辑设备号标识的逻辑设备。UNIX的普通文件和目录文件就保存在这样的文件系统中。逻辑文件系统的存储结构可分为两类型：一级存储结构型：常用于运行环境较小的文件系统中二级存储结构型：常用于运行环境较大（特别是硬盘空间较大）的文件系统中①、一级存储结构型这种类型的逻辑文件系统由超级块、索引节点表块和数据区组成，（如果是根文件系统，就还包括引导块）。整个存储结构是一维的。引导块：boot程序超级块：fs结构，存放文件系统的静态参数i节点表块：磁盘icommon表数据区：各数据块 引导块 超级块 i节点表块 数据区②、两级存储结构型这种存储结构的文件系统由两级组成：第一级由超级块和若干个柱面组块（cylindergroupblock）所组成（如果是根文件系统则还包括引导块）。第二级（即柱面组块）又是由超级块拷贝块、柱面组信息块，i节点表块和数据区所组成。文件系统的存储结构是二维的。目前大多数在大存储环境下运行的UNIX版本都采用这种存贮结构，其优点是能快速定位数据块。第一级存储结构第二级存储结构 引导块 超级块 1号柱面组块 2号柱面组块 …… n号柱面组块 超级块拷贝块 柱面组信息块 i节点表块 数据区超级块是由fs定义的数据结构，用于存放文件系统的静态参数：structfs{内存超级块链接指针超级块的磁盘地址柱面组块的位移量最近修改时间文件系统大小文件系统块大小柱面组数柱面组大小片大小文件系统标识数文件系统标志区最近访问的柱面组号确定分配算法的参数}超级块拷贝块：在每个柱面组块中存放有一个超级块拷贝块，其目的是使系统在超级块被意外破坏时，能从任何一个柱面组中进行恢复而不致使整个文件系统陷入瘫痪。每个柱面组中的超级块拷贝块的存放位置为安全起见不一定都装在柱面组中的最前面，而是可浮动地装在该柱面组中的任何位置。一般性的方法是：如果第n号柱面组中的超级块拷贝块开始于该柱面组中的第i磁道，则第n+1柱面组中的超级块拷贝块开始于该柱面组中的第i+1磁道。文件系统一旦建立后，它们的位置就是固定不变的。柱面组信息块（cg块）柱面组信息块中存放的是有关该柱面组的静态参数，它由数据结构cg来定义：structcg{内存中柱面组块的链接指针本柱面组块中i节点表大小本柱面组块中数据区大小最近一次所用块的位置最近一次所用片的位置最近一次所用i节点的位置本柱面组空闲数据块总数i节点位示图空闲块位示图}位示图：位示图为一张表，其中的每一个二进制位（bit）的值来表示某一个资源（例如数据块或i节点）的状态，这样每检测一个字节的值就可以知道八个资源的状态；每检测一个四字节的整数的值就可以知道32个资源的状态。系统只需要维护一张较小的表（位示图）就可以快速地检测指定资源的忙闲状态，或快速查找可用的空闲资源。5、文件系统的数据块在文件系统中，按存储单位来划分，由大到小可有下列层次：文件系统(filesystem)柱面组(cylindergroup)柱面(cylinder)磁道(track)扇区(sector)DEV_BSIZE512字节文件系统的逻辑块大小：DEV_BSIZE*2ⁿ即1k、2k、4k、8k、16k…目的：提高传输速度，减少overhead文件系统的逻辑片大小：DEV_BSIZE*2ⁿ即1k、2k、4k、8k、16k…目的：减少文件尾的碎片浪费。6．目录和目录项在UNIX文件系统中，目录的组织形式采用的是树形结构，一个逻辑文件系统就是一棵目录树。目录也被当作文件进行处理，一个目录文件的结构为表状结构，其中通常包含有若干表项，称为目录项，这些目录项既可以是普通文件的入口，也可以是子目录的入口。每一个目录项中通常包含两部分内容：文件的i节点号文件名目录/home/student/xiaolan的路径和目录结构//home/bin/home/log/home/student/home/student/xiaolan/home/student/xiaolan/src/home.student/xiaolan/bckup 2 。 2 。。 153 home 0 tst 85 bin 85 。 2 。。 153 。 2 。。 290 log 376 student 376 。 153 。。 584 xiaolan 584 。 376 。。 409 bckup 230 src 409 。 584 。。每个目录项由数据结构direct来定义：#defineMAXNAMLEN14structdirect{shortd_ino;/*目录项i节点号*/chard_name[MAXNAMELEN];/*目录项名字字符串*/}每个目录项的长度通常是确定的，为16个字节，其中前两个字节存放文件的i节点号d_ino，后面14个字节存放文件名d_name。这种定长目录项在算法实现方面比较简单，在使用灵活方面都有所不便，并且可能因许多目录项名字长度不足14字符面有空间浪费。在UNIX的每个文件系统中，有三个i节点号是有固定用途的：0号i节点：表示空目录项，当某个目录项被删除时，该目录项的i节点号被置为0。1号i节点：表示坏块文件，所有的磁盘坏块都划归到该节点上；2号i节点：固定表示该逻辑文件系统的根（root）目录；3号i节点：表示该文件系统中的lost+found目录。7、变长目录项的目录结构#defineMAXNAMLEN255structdirect{longd_ino;/*目录项i节点号*/shortd_reclen;/*目录项入口长度（占用长度）*/shortd_namelen；/*目录项名字长度*/chard_name[MAXNAMLEN+1]/*名字字符串，+1为串结束符\0*/}由于目录中各目录项的长度是变化的，因此必须在目录项中标明本目录项的长度。前一个目录项释放时，把该目录项的空间全部合并到前一个目录项中，形成前面一个目录项占用空间大于实际使用的空间。在增加新目录时，先查看目录中各目录项是否占用多余空间，如有，则进行压缩，把释放的空间分配给新目录项。变长目录结构增加了算法复杂性和工作量，通常用在硬件性能较高的大型系统中。8、文件名和文件名缓冲区核心在内存中建立了一个高速的名字缓冲区，用来存放最近使用过的文件名，核心认为“最近使用过的文件名马上还要使用的可能性最大”。名字缓冲区是由ncache定义的数据结构，只包含文件名和索引节点指针等重要信息：structncache{hash链表指针LRU链表指针文件i节点指针/*这里只需要节点指针，因内存中已有活动i节点表*/文件父目录节点指针文件名确认信息}链表头名字缓冲区1名字缓冲区2名字缓冲区3名字缓冲区n名字缓冲区（ncache）链表为定长双向循环链表为提高查找文件名的速度，还根据每个ncache的hash值，将其挂接到一个hash链表中。ncache的hash值用下列公式计算：hn=7&(*namep+*(namep-1+slen)+slen+(int)VP)namep：为指向名字字符串的指针slen：为名字长度VP：为父目录节点指针计算出相应的hash值（0~7）。共建立8个hash链，每个hash链是一个以链表头开始的双向循环链表，每个ncache任何时候都同时既在hash链上，又在LRU链上。ncachencachencachencachencachencachencachencachencacheLRU链表头Hash链表头hn=0hn=1hn=7名字缓冲区(ncache)池结构9、资源保护UNIX文件系统中的资源保护系统主要是对系统中的两类资源进行保护：①静态硬资源包括存贮空间和索引节点，对这类资源的保护主要是通过quota系统提供的限量机制实现的。②动态资源主要是指临界区资源或独享资源，对这类资源的保护主要是通过上锁机制来实现的。1）quota系统quota系统的主要功能就是检测和限制用户对文件系统资源的使用。在每个逻辑文件系统（包括根文件系统和各子文件系统）中都可以建立一个磁盘quota文件来限制用户对本文件系统资源的使用。每个quota文件是由多个dqblk数据结构所组成的表格，每个dqblk都针对一个用户，用于存放该文件系统对该用户的限制参数。如果一个用户的使用空间包含多个文件系统，则需在每个文件系统的硬盘quota文件中给该用户分配一个dqblk项。structdqblk{盘块数硬限制盘块数软限制已用盘块数节点数硬限制节点数软限制已用节点数盘块数时间限制节点数时间限制}系统在运行时，在内存中建立了一个活动dqblk链表（类似于活动i节点表），每个活动dqblk由其hash值而分别处在64链中的某个链表上，如果某个活动dqblk是空闲的，它同时又处在空闲活动dqblk链表中（与活动i节点表的结构完全一样）。quota限量系统构成quota资源限量系统对盘块数限制对节点数限制软限制(选择限制)硬限制(绝对限制)软限制(选择限制)硬限制(绝对限制)无时间限制有时间限制无时间限制有时间限制2）上锁机构为保持数据的一致性，能正常使用临界区资源，UNIX文件系统提供了一种对数据（文件或记录）的上锁机制，即劝告锁（advisorylock），用户既可给整个文件上锁，也可给部分记录上锁。劝告锁包含两种类型：共享锁（读操作锁）互斥锁（写操作锁）在同一个文件或同一个记录上同时只能有一个互斥锁（或写操作锁），但可以同时有多个共享锁（读操作锁）。共享锁的级别低于互斥锁，互斥锁可以覆盖共享锁。对一个文件上锁只是一种“自觉性”的保护措施——“劝告锁”，进程在读写该文件之前都必须先检查该文件是否已上锁，然后再进行相应的锁操作后才能对该文件进行读写。否则将使该文件上原有的所有劝告锁失效。4.1.2虚拟文件系统1．文件结