linux进程管理

Linux进程管理,2020/5/3,西安交通大学计算机系,2,Linux操作系统,Linux是一个多用户、多任务的操作系统，这就意味着多个用户可以同时使用一个操作系统，而每个用户又可以同时运行多个命令。在这样的系统中，各种计算机资源（如文件、内存、CPU等）的分配和管理都以进程为单位。为了协调多个进程对这些共享资源的访问，操作系统要跟踪所有进程的活动，以及它们对系统资源的使用情况，实施对进程和资源的动态管理。,2020/5/3,西安交通大学计算机系,3,Linux的进程及其状态,在Linux系统中，进程(Process)和任务(Task)是同一个意思。所以，在内核的代码中，这两个名词常常混用。Linux进程状态在Linux系统中，进程有以下几个状态：运行态(TASK_RUNNING=0)此时，进程正在运行(即系统的当前进程)或者准备运行（即就绪态）等待态此时进程在等待一个事件的发生或某种系统资源。Linux系统分为两种等待进程：可中断的(TASK_INTERRUPTIBLE=1)和不可中断的(TASK_UNINTERRUPTIBLE=2)。可中断的等待进程可以被某一信号(Signal)中断；而不可中断的等待进程不受信号的打扰，将一直等待硬件状态的改变停止态(TASK_STOPPED=4)进程被停止，通常是通过接收一个信号。正在被调试的进程可能处于停止状态僵死态(TASK_ZOMBIE=3)由于某些原因被终止的进程，但是该进程的控制结构task_struct仍然保留着。,2020/5/3,西安交通大学计算机系,4,Linux进程状态转换,停止态TASK_STOPPED,正在运行态拥有cpu,就绪态Task_runing,僵死态TASK_ZOMBIE,不可中断等待态TASK_UNINTERRUPTIBLE,可中断等待态TASK_INTERRUPTIBLE,进程终止do_exit(),时间片到,进程调度schedule(),进程跟踪系统调用执行syscall_trace()sys_exit()schedule(),未申请到所需资源sleep_on()schedule()interruptible,未申请到所需资源sleep_on()schedule(),收到SIG_KILL或SIG_CONT后执行wake_up(),所需资源满足或收到信号wake_up_interruptible(),所需资源满足wake_up(),2020/5/3,西安交通大学计算机系,5,进程的模式和类型,在Linux系统中，进程的执行模式划分为用户模式和内核模式。如果当前运行的是用户程序、应用程序或者内核之外的系统程序，那么对应进程就在用户模式下运行；如果在用户程序执行过程中出现系统调用或者发生中断事件，就要运行操作系统（即核心）程序，进程模式就变成内核模式。在内核模式下运行的进程可以执行机器的特权指令；而且，此时该进程的运行不受用户的干预，即使是root用户也不能干预内核模式下进程的运行。按照进程的功能和运行的程序分类，进程可划分为两大类：一类是系统进程，只运行在内核模式，执行操作系统代码，完成一些管理性的工作，例如内存分配和进程切换；另外一类是用户进程，通常在用户模式中执行，并通过系统调用或在出现中断、异常时进入内核模式。,2020/5/3,西安交通大学计算机系,6,有关进程管理的命令,ps命令ps命令是查看进程状态的最常用的命令，它可以提供关于进程的许多信息。根据显示的信息可以确定哪个进程正在运行、哪个进程被挂起、遇到了哪些困难、进程已运行了多久、进程正在使用的资源、进程的相对优先级，以及进程的标识号（PID）。所有这些信息对用户都很有用，对于系统管理员来说更为重要。,2020/5/3,西安交通大学计算机系,7,Linux的ps命令格式,ps命令的一般格式是：ps选项以下是ps命令常用的选项及其含义：-a显示系统中与tty相关的所有进程的信息。-e显示所有进程的信息。-f显示进程的所有信息。-l以长格式显示进程信息。r只显示正在运行的进程。u显示面向用户的格式(包括用户名、CPU及内存使用情况等信息)。x显示所有非控制终端上的进程信息。-pid显示由进程ID指定的进程的信息。-tty显示指定终端上的进程的信息。,2020/5/3,西安交通大学计算机系,8,Linux的命令ps显示的信息项,UID进程属主的用户ID号PID进程ID号PPID父进程的ID号C进程最近使用CPU的估算。STIME进程开始时间,以“小时:分:秒”的形式给出TTY该进程建立时所对应的终端,“?”表示该进程不占用终端TIME报告进程累计使用的CPU时间。注意,尽管觉得有些命令(如sh)已经运转了很长时间,但是它们真正使用CPU的时间往往很短。所以,该字段的值往往是0:00CMD是command(命令)的缩写，往往表示进程所对应的命令名,2020/5/3,西安交通大学计算机系,9,Linux的命令ps显示的信息项,命令ps-auxUSER启动进程的用户%CPU运行该进程占用CPU的时间与该进程总的运行时间的比例%MEM该进程占用内存和总内存的比例VSZ虚拟内存的大小,以KB为单位RSS占用实际内存的大小,以KB为单位STAT表示进程的运行状态，包括以下几种代码:D不可中断的睡眠；R就绪（在可运行队列中）；S睡眠；T被跟踪或停止；Z终止（僵死）的进程。,2020/5/3,西安交通大学计算机系,10,Linux的kill命令,通常终止一个前台进程可以使用“Ctrl+C”组合键。但是,对于一个后台进程就须用kill命令来终止。kill命令是通过向进程发送指定的信号来结束相应进程。默认情况下,采用编号为15的TERM信号。TERM信号将终止所有不能捕获该信号的进程。对于那些可以捕获该信号的进程就要用编号为9的KILL信号,强行杀掉该进程。,2020/5/3,西安交通大学计算机系,11,Linuxkill命令的格式,kill-s信号|-p-a进程号.kill-l信号其中选项各选项的含义如下：-s指定需要发送的信号,既可以是信号名(如KILL),也可以是对应信号的号码(如9)。-p指定kill命令只是显示进程的pid(进程标识号),并不真正发出结束信号。-l显示信号名称列表,这也可以在/usr/include/linux/signal.h文件中找到。,2020/5/3,西安交通大学计算机系,12,使用kill命令时应注意,（1）kill命令可以带信号号码选项，也可以不带。如果没有信号号码，kill命令就会发出终止信号（TERM）。这个信号可以杀掉没有捕获到该信号的进程，也可以用kill向进程发送特定的信号。例如：kill-21234它的效果等同于在前台运行PID为1234的进程的时候，按下“Ctrl+C”。但是普通用户只能使用不带signal参数的kill命令，或者最多使用-9信号。（2）kill可以带有进程ID号作为参数。当用kill向这些进程发送信号时，必须是这些进程的主人。如果试图撤销一个没有权限撤销的进程，或者撤销一个不存在的进程，就会得到一个错误信息。,2020/5/3,西安交通大学计算机系,13,使用kill命令时应注意,（3）可以向多个进程发信号，或者终止它们。（4）当kill成功地发送了信号，Shell会在屏幕上显示出进程的终止信息。有时这个信息不会马上显示，只有当按下回车键使Shell的命令提示符再次出现时才会显示出来。（5）信号使进程强行终止常会带来一些副作用，比如数据丢失或终端无法恢复到正常状态。发送信号时必须小心，只有在万不得已时才用kill信号(9)，因为进程不能首先捕获它。要撤销所有的后台作业，可以键入“kill0”。因为有些在后台运行的命令会启动多个进程，跟踪并找到所有要杀掉的进程的PID是件很麻烦的事。这时,使用“kill0”来终止所有由当前Shell启动的进程是个有效的方法。,2020/5/3,西安交通大学计算机系,14,Linux的sleep命令,sleep命令的功能是使进程暂停执行一段时间。其一般格式是：sleep时间值其中，“时间值”参数以秒为单位,即使进程暂停由时间值所指定的秒数。此命令大多用于Shell程序设计中,使两条命令执行之间停顿指定的时间。,2020/5/3,西安交通大学计算机系,15,Linux进程的数据结构,在Linux中，进程用task_struct表示，所有进程被组织到以init_task为表头的双向链表中（见include/linux/sched.hSET_LINKS()宏），该链表是全系统唯一的。系统维护一个名为task的数组，task包含指向系统所有进程的task_struct结构的指针，task数组默认值为512,Linux从系统内存分配一个task_struct结构并将其加入task数组。当前运行进程的结构用current指针指示。,2020/5/3,西安交通大学计算机系,16,Linux内核0.11task_struct,进程控制块是task_struct结构，在include/linux/sched.h中定义task_struct结构体中各数据项含义,2020/5/3,西安交通大学计算机系,17,Linux内核0.11的task_struct,structtask_struct/*therearehardcodeddonttouch*/longstate;/*-1unrunnable,*runnable,0stoped*/longcounter;longpriority;longsignal;structsigactionsigaction32;longblocked;/*bitmapofmaskedsignals*/intexit_code;/*variousfields*/unsignedlongstart_code,end_code,end_data,brk,start_stack;longpid,father,pgrp,session,leader;unsignedshortuid,euid,suidunsignedshortgid,egid,sgid;longalarm;longutime,stime,cutime,cstime,start_time;unsignedshortused_math;,/*filesysteminfo*/inttty;/*-1ifnotty,soitmustbesigned*/unsignedshortumask;structm_inode*pwd;structm_inode*root;structm_inode*executable;unsignedlongclose_on_exec;structfile*filpNR_OPEN;/*ldtforthistask0zero1cs2-ds,2020/5/3,西安交通大学计算机系,18,Linuxtask_struct的信息分类,进程的状态信息进程调度信息进程标识信息进程通信信息进程的链接信息进程的时间和定时器信息有关文件系统的信息虚拟内存信息进程上下文信息其它信息,2020/5/3,西安交通大学计算机系,19,Linux的PCBtask_struct,stateLinux的进程状态主要分为三类：可运行的（TASK_RUNNING，相当于运行态和就绪态）；被挂起的（TASK_INTERRUPTIBLE、TASK_UNINTERRUPTIBLE和TASK_STOPPED）；不可运行的（TASK_ZOMBIE），调度器主要处理的是可运行和被挂起两种状态下的进程，其中TASK_STOPPED又专门用于SIGSTP等IPC信号的响应，而TASK_ZOMBIE指的是已退出而暂时没有被父进程收回资源的“僵尸”进程。need_resched布尔值，在调度器中用于表示该进程需要申请调度,2020/5/3,西安交通大学计算机系,20,Linux的PCBtask_struct,policy在Linux2.4中，进程的调度策略可以有三种选择：SCHED_FIFO（先进先出式调度，除非有更高优先级进程申请运行，否则该进程将保持运行至退出才让出CPU）、SCHED_RR（轮转式调度，该进程被调度下来后将被置于运行队列的末尾，以保证其他实时进程有机会运行）、SCHED_OTHER（常规的分时调度策略）。另外，policy中还包含了一个SCHED_YIELD位，置位时表示主动放弃CPU。rt_priority用于表征实时进程的优先级，从1-99取值，非实时进程该项应该为0。这一属性将用于调度时的权值计算（详见“就绪进程选择算法”）。counter该属性记录的是当前时间片内该进程还允许运行的时间（以CPU时钟tick值为单位，每个进程的counter初值与nice值有关，nice越小则counter越大，即优先级越高的进程所允许获得的CPU时间也相对越多），并参与就绪进程选择算法。在Linux2.4中，每个（非SCHED_FIFO实时）进程都不允许运行大于某一时间片的时间，一旦超时，调度器将强制选择另一进程运行（详见调度器工作流程）,2020/5/3,西安交通大学计算机系,21,Linux的PCBtask_struct,nice用户可支配的进程优先级，将参与“就绪进程选择算法”，同时该值也决定了该进程的时间片长度cpus_allowed以位向量的形式表示可用于该进程运行的CPU（见“调度器工作流程”）cpus_runnable以位向量的形式表示当前运行该进程的CPU（相应位为1）。如果不在任何CPU上运行，则为全1。这一属性和cpus_allowed属性结合，可以迅速判断该进程是否能调度到某一CPU上运行（位与）,2020/5/3,西安交通大学计算机系,22,Linux的PCBtask_struct,processor本进程当前（或最近）所在CPU编号thread用于保存进程执行环境（各个寄存器的值以及IO操作许可权映射表），内容与TSS相近。因为TSS以CPUid为索引，而Linux无法预测被替换下来的进程下一次将在哪个CPU上运行，所以这些信息不能保存在TSS中current核心经常需要获知当前在某CPU上运行的进程的task_struct，在Linux中用current指针指向这一描述符。current的实现采用了一个小技巧以获得高效的访问速度，这个小技巧与Linux进程task_struct的存储方式有关,2020/5/3,西安交通大学计算机系,23,Linux的PCBtask_struct,schedule_datatask_struct是用于描述进程的数据结构，其中包含了指向所运行CPU的属性。在Linux中，另有一个数据结构对应于CPU，可以利用它访问到某CPU上运行的进程，这个数据结构定义为schedule_data结构，包含两个属性：curr指针，指向当前运行于该CPU上的进程的task_struct，通常用cpu_curr(cpu)宏来访问；last_schedule时间戳，记录了上一次该CPU上进程切换的时间，通常用last_schedule(cpu)宏来访问。为了使该数据结构的访问能与CPU的Cacheline大小相一致，schedule_data被组织到以SMP_CACHE_BYTES为单位的aligned_data联合数组中，系统中每个CPU对应数组上的一个元素。,2020/5/3,西安交通大学计算机系,24,Linux就绪进程选择算法,Linuxschedule()函数将遍历就绪队列中的所有进程，调用goodness()函数计算每一个进程的权值weight，从中选择权值最大的进程投入运行。进程调度权值的计算分为实时进程和非实时进程两类，对于非实时进程（SCHED_OTHER），影响权值的因素主要有以下四个：进程当前时间片内所剩的tick数，即task_struct的counter值，相当于counter越大的进程获得CPU的机会也越大，因为counter的初值与（-nice）相关，因此这一因素一方面代表了进程的优先级，另一方面也代表了进程的欠运行程度；（weight=p-counter;）进程上次运行的CPU是否就是当前CPU，如果是，则权值增加一个常量，表示优先考虑不迁移CPU的调度，因为此时Cache信息还有效；（weight+=PROC_CHANGE_PENALTY;）此次切换是否需要切换内存，如果不需要（或者是同一进程的两个线程间的切换，或者是没有mm属性的核心线程），则权值加1，表示（稍微）优先考虑不切换内存的进程；(weight+=1;),2020/5/3,西安交通大学计算机系,25,Linux就绪进程选择算法,进程的用户可见的优先级nice，nice越小则权值越大。（Linux中的nice值在-20到+19之间选择，缺省值为0，nice()系统调用可以用来修改优先级。）(weight+=20-p-nice;)对于实时进程（SCHED_FIFO、SCHED_RR），权值大小仅由该进程的rt_priority值决定（weight=1000+p-rt_priority;），1000的基准量使得实时进程的权值比所有非实时进程都要大，因此只要就绪队列中存在实时进程，调度器都将优先满足它的运行需要。如果权值相同，则选择就绪队列中位于前列的进程投入运行。除了以上标准值以外，goodness()还可能返回-1，表示该进程设置了SCHED_YIELD位，此时，仅当不存在其他就绪进程时才会选择它。如果遍历所有就绪进程后，weight值为0，表示当前时间片已经结束了，此时将重新计算所有进程（不仅仅是就绪进程）的counter值，再重新进行就绪进程选择（详见调度器工作流程）。,2020/5/3,西安交通大学计算机系,26,Linux的调度器,Linux的调度器主要实现在schedule()函数中。调度器工作流程schedule()函数的基本流程可以概括为四步：1).清理当前运行中的进程2).选择下一个投入运行的进程3).设置新进程的运行环境4).执行进程上下文切换5).后期整理其中包含了一些锁操作：就绪队列锁runquque_lock，全局核心锁kernel_flag，全局中断锁global_irq_lock，进程列表锁tasklist_lock。,2020/5/3,西安交通大学计算机系,27,Linux内核0.11进程的创建,进程创建程序fork.cfork.c是sys_fork()（在kernel/system_call.s中）系统调用的辅助处理函数集sys_fork()其中给出了sys_fork()系统调用中使用的两个C语言函数find_empty_process()为新进程取得不重复的进程号copy_process()用于创建并复制进程的代码段和数据段以及环境还包括进程呢哦存区域验证和内存分配函数Verify_area(),2020/5/3,西安交通大学计算机系,28,fork.c的主要工作,为task_struct申请空闲内存页，并填入新进程标识号和其他内容调用find_empty_process()寻找空闲的进程槽（processstot）为kernel_task_page申请内存空闲页面复制父进程的LDP复制父进程的mmap建立文件系统有关信息，包括文件描述符和i节点等,2020/5/3,西安交通大学计算机系,29,Linux进程的撤销exit.c,2020/5/3,西安交通大学计算机系,30,设计Linux系统调用,用户接口添加系统调用添加源代码添加到内核文中的一个函数函数名前缀sys_作为系统调用的标志Asmlinkageintsys_yang(inti)intj;j=i*i;returnj;添加代码到文件/usr/src/linux/kernel/sys.c链接新的系统调用目的让内核其它部分知道它的存在打开/usr/src/linux/include/asm-i386/unistd.h该文件包含了系统调用的清单，用来给每个系统调用分配一个唯一的编号,2020/5/3,西安交通大学计算机系,31,Linux系统调用（续）,系统调用号的定义define_NR_nameNNN其中NNN为定义的号，name为新的系统调用名称新的定义添加到unist.h文件的最后在/usr/src/linux/arch/i386/kernel/entry.S的最后添加代码.longSYSMBOL_NAME(sys_yang)重新编译内核以root登录，进入/usr/src/linux目录，重建内核：makemenuconfig/配置新内核makedep/创建新内核makemodules_indtall/加入模块makeclean/清除多余创建的文件makebzImage/生成可执行内核引导文件makeinstall/安装新内核重新启动系统即可,2020/5/3,西安交通大学计算机系,32,Linux系统调用（续）,编程(test.c)调用自己的系统调用#include#include_syscall1(char*,yang,int,ret);main()intx,y;x=100;y=yang(x);printf(“Thisistheresultofnewkerneln”);printf(“%dn”,y);,2020/5/3,西安交通大学计算机系,33,Linux系统调用（续）,编译程序gccoI/usr/src/linux-2.4.20-8/includetesttest.c运行./test,2020/5/3,西安交通大学计算机系,34,设计动态模块,模块的组织#include/说明是个内核功能#include/说明是个模块/其他header信息intinit_module()/声明是一个模块./加载时,初始化模块的编码./期望实现的其它功能，如read()、ioctl()等函数voidcleanup_module()./卸载时,注销模块的编码,2020/5/3,西安交通大学计算机系,35,模块编程,模块的编译#gccO2gWallDMODULED_KERNEL_cfilename.c/filename.c为自己编写的模块程序源代码文件模块的加载insmod命令模块的卸载rmmod命令,2020/5/3,西安交通大学计算机系,36,模块编程,一个例子testmodule.c#defineMODULE#include#include#ifCONFIG_MODVERSION=1#defineMODVERSIONS#include#endifintinit_module()printk(Hello!Thisisatestingmodule!n);return0;voidcleanup_module()printk(Sorry!Thetestingmoduleisunloadingnow!n);,2020/5/3,西安交通大学计算机系,37,模块编程,模块的编译、加载与卸载编译#gccO2gWallDMODULED_KERNEL_ctestmodule.c/testmodule.c为自己编写的模块程序源代码文件加载#insmodftestmodule.o卸载#rmmodtestmodule,2020/5/3,西安交通大学计算机系,38,Ext文件系统minix文件系统结构文件名14个字符块设备最大容量64M(=8*(8*1024)*1024/(1024*1024),EXT2文件系统_minix文件系统,2020/5/3,西安交通大学计算机系,39,EXT2文件系统_磁盘布局,Ext文件系统Minix的第一次扩展文件名最大长度255个字符磁盘分区大小可达2GBExt2文件系统第二代扩展文件系统磁盘分区大小可达4TB磁盘布局采用了组块,2020/5/3,西安交通大学计算机系,40,EXT2文件系统_引导块和超级块,引导块BootBlock每个硬盘分区的开头1024字节，即0byte至1023byte是分区的启动扇区。存放由ROMBIOS自动读入的引导程序和数据，但这只对引导设备有效，而对于非引导设备，该引导块不含代码。这个块与ext2没有任何关系。超级块SuperBlock分区剩余的部分被分为若干个组。每个组里均由一个superblock块和一个GroupDescriptors（组描述符）块组成。Group0中的superblock被内核所用。定义了诸如文件系统的静态结构，包括块的大小，总块数，每组内inode数，空闲块，索引结点数等全局信息。其他Group中的SuperBlock则仅是Group0中的SuperBlock的一个拷贝。超级块的数据结构在ext2_fs.h定义为structext2_super_blockLinux启动时superblock0的内容读入内存，某个组损坏可用来恢复,2020/5/3,西安交通大学计算机系,41,EXT2文件系统_超级块,structext2_super_blockTypeField释意_u32s_inodes_count;索引结点的总数_u32s_blocks_count;文件系统块的总数_u32s_r_blocks_count;为超级用户保留的块数_u32s_free_blocks_count;空闲块总数_u32s_free_inodes_count;空闲索引节点总数_u32s_first_data_block;文件系统中第一个数据块_u32s_log_block_size;用于计算逻辑块的大小_s32s_log_frag_size;用于计算片的大小_u32s_blocks_per_group;每个组的块个数_u32s_frags_per_group;每个组的片个数_u32s_inodes_per_group;每个组的索引节点数_u32s_mtime;文件系统的安装时间_u32s_wtime;最后一次对超级块进行写的时间_u16s_mnt_count;安装计数_s16s_max_mnt_count;最大可安装计数,2020/5/3,西安交通大学计算机系,42,EXT2文件系统_超级块,_u16s_magic;用于确定文件系统版本的标志（ext20 xEF53）_u16s_state;文件系统状态_u16s_errors;当检测到错误时如何处理_u16s_minor_rev_level;次版本号_u32s_lastcheck;最后一次检测文件系统状态的时间_u32s_checkinterval;两次对文件系统状态进行检测的最大可能时间间隔_u32s_rev_level;版本号，以此识别是否支持某些功能_u16s_def_fesuid;保留块的默认用户标识UID_u16s_def_fesgid;保留块的默认用户组标识GID_u32s_first_ino;第一个非保留的索引节点号_u16s_inode_size;索引结点结构的大小_u16s_block_group_nr;本Superblock所在的块组号_u32s_reserved230;保留/*Paddingtotheendoftheblock*/注意文件系统的状态：没错：defineEXT2_valid_fs0 x0001有错：defineEXT2_ERROR_fs0 x0002,2020/5/3,西安交通大学计算机系,43,EXT2文件系统_组描述符,组描述符GroupDescriptors定义了块位图的块号，索引结点位图的块号、索引结点表的起始块号，本组空闲块的个数等组内信息。文件系统根据这些信息来查找数据块位图，索引结点位图，索引结点表的位置。数据结构在ext2_fs.h中定义：structext2_group_descTypeField释意_u32bg_block_bitmap;指向该组中块位图所在块的指针_u32bg_inode_bitmap;指向该组中块节点位图所在块的指针_u32bg_inode_table;指向该组中节点的首块的指针_u16bg_free_blocks_count;本组空闲块的个数_u16bg_free_inodes_count;本组空闲索引节点的个数_u16bg_used_dirs_count;本组分配给目录的节点数_u16bg_pad;填充_u32bg_reserved;保留;,2020/5/3,西安交通大学计算机系,44,EXT2文件系统_数据块及数据块位图,数据块位图DataBlockBitmap这是ext2管理存储空间的方法。即位图法。每个位对应一个数据块，位值为0表示空闲，1表示已经分配。数据块位图定义为一个块大小。于是，一个组中的数据块个数就决定了。假设块大小为b字节。可以区别的块数为b*8个数据块DataBlocks每个组的数据最大个数是在块大小定义后就确定了的。所以组容量也就确定了。假设块大小为b字节。那么组容量就确定为(b*8)*b字节若1块=4K，则组块大小=4K*8*4K=128M,2020/5/3,西安交通大学计算机系,45,EXT2文件系统_索引节点位图及索引节点,索引结点位图InodeBitmap与数据块位图相似，用来表示索引结点是否已经被使用。假设块大小为b字节，每个索引结点数据结构大小为128字节。最多可以有b*8个索引结点，索引结点表需要占用的存储空间大小为(b*8)*128字节。即(b*8)*128/b=8*128个块索引结点Inode索引结点表由若干个索引结点数据结构组成，需要占用若干个块。Ext2中的每个索引结点数据结构大小为128字节。每个索引结点即对应一个文件或是目录。是对其除文件名（目录名）以外的所有属性的描述。例如：文件类型，文件创建时间，访问时间，修改时间，文件所占数据块的个数，指向数据块的指针。其中，数据块指针是由15个元组的数据组成,2020/5/3,西安交通大学计算机系,46,EXT2文件系统_索引节点位图及索引节点,前12个元组，（0至11）直接指向数据块。第12号元组(12)是一个1级子索引。指向的不是数据块，而是存放数据块指针的块。类似的，第13号元组（13）是一个2级子索引。第14号元组（14）是一个3级子索引。这种结构可以适应大文件的存储。假设文件块大小为b。则当文件长度小于b*12时，只要用前12个元组来指向其数据块。当文件长度大于b*12时，则用多级索引机制来指向其数据块。这体现了Ext2的文件的物理结构，即索引文件。使用索引结点来指向文件的数据块，并且索引结点本身是聚集在一起的。,2020/5/3,西安交通大学计算机系,47,2020/5/3,西安交通大学计算机系,48,EXT2文件系统_索引节点定义,索引节点定义ext2_fs.h中的structext2_inodestructext2_inodeTypeField释意_u16i_mode;文件类型及访问权限_u16i_uid;文件拥有者的标识号UID_u32i_size;文件大小大小(字节)_u32i_atime;最后一次访问时间_u32i_ctime;创建时间_u32i_mtime;该文件内容最后修改时间_u32i_dtime;文件删除时间_u16i_gid;文件的用户组的组号_u16i_links_count;文件的链接计数_u32i_blocks;文件的数据块个数（以512字节计）_u32i_flags;打开文件的方式_u32i_blockEXT2_N_BLOCKS;指向数据块的指针数组_u32i_generation;文件的版本号(用于NFS)_u32i_file_acl;文件访问控制表(ACL已不再使用)_u32i_dir_acl;目录访问控制表(ACL已不再使用)_u8l_i_frag;每块中的片数_u8l_i_fsize;片的大小_u32l_i_reserved;保留;,2020/5/3,西安交通大学计算机系,49,EXT2文件系统_目录与文件,目录与文件不是所有的文件都需要数据块，有些文件只需要索引结点即可。Ext2中，目录是一种特殊的文件。其数据块中的内容即目录表：所包含的文件（当然也包括子目录）的文件名，指向文件的索引节点号，文件类型。ext2_fs.h中数据结构的定义：structext2_dir_entry_2_u32inode;索引节点号_u16rec_len;目录项长度_u8name_len;文件名长度_u8file_type;文件类型(1:普通文件，2:目录)charnameEXT2_NAME_LEN;文件名;其中MAX_NAME_LEN定义为255。即文件名最大长度为255个字符（字节）。同时，目录项取为4的整数。故，目录项的长度范围是12至264字节。,2020/5/3,西安交通大学计算机系,50,EXT2文件系统_目录与文件,目录文件的数据块实例其中，inode指向0的那一行，表示此文件已经被删除。同时，上一行的目录项长度扩展为两者之和(12+16)。,2020/5/3,西安交通大学计算机系,51,EXT2文件系统_文件的类型,文件类型Ext2中文件类型有以下几种：文件类型号描述0未知1普通文件2目录3字符设备4块设备5管道(Pipe)6套接字7符号指针,2020/5/3,西安交通大学计算机系,52,EXT2文件系统的操作,两个概念文件系统的设计目标在于：一方面，从用户的角度看，实现“按名取存”，文件系统的用户只要知道所需文件的文件名，就可存取文件中的信息，而无需知道这些文件究竟存放在什么地方。另一方面，从系统角度看，文件系统对文件存储器的存储空间进行组织、分配和回收，负责文件的存储、检索、共享和保护。用户角度的文件系统被称为VFS，虚拟文件系统。定义在这个层次上的操作，对于用户来说是文件系统所呈现所有属性。比如，列目录，建立目录，建立文件，打开文件，读写文件，重命名文件等。与每个操作相对应的是实际文件系统中的一系列底层操作。,2020/5/3,西安交通大学计算机系,53,EXT2文件系统的操作,索引结点操作,2020/5/3,西安交通大学计算机系,54,EXT2文件系统的操作,文件操作,2020/5/3,西安交通大学计算机系,55,EXT2硬盘空间管理,存储空间的分配回收需要考虑两个因素避免文件碎片时效Ext2中新建立的文件并不是马上就分配数据块，而是分配索引结点。当有数据存入时，再分配数据块。故存储空间的分配与回收也分成两个部分索引结点的创建与删除数据块的分配与回收,2020/5/3,西安交通大学计算机系,56,EXT2硬盘空间管理_创建索引结点,创建索引结点Ext2使用ext2_new_inode()来创建一个新的索引结点。创建成功则返回索引结点号，否则返回NULL。这个函数包括了以下几个步骤：get_empty_inode()返回一个空结点lock_super()互斥操作。即对superblock的P()操作如果索引结点是目录，则将其分配到空闲块最多的组中。如果索引结点不是目录，则从头开始“顺序查找”一个空结点分配给该文件。“顺序查找”的算法是：,2020/5/3,西安交通大学计算机系,57,EXT2硬盘空间管理_创建索引结点,load_inode_bitmap()载入选中的组的索引结点位图块。找到选择首个空闲索引结点，分配之，并将对应位图位填成1。将组描述符中的空闲索引结点个数减1。将SuperBlock中的空闲索引结点个数减1。填充刚刚分配的索引结点的数据结构。比如，文件属性，创建时间，访问时间等等。将新的索引结点插入索引结点hash表，加速查询。mark_indoe_dirty()将索引结点号填入superblock的dirtyinodelist中。unlock_super()互斥操作完毕，解锁。即，对superblock的V()操作。返回新分配的索引结点号。,2020/5/3,西安交通大学计算机系,58,EXT2硬盘空间管理_索引结点的删除,索引结点的删除Ext2使用ext2_free_inode()来删除一个索引结点。在此之前，内核必须已经事先完成了一系列的操作：删除文件占用的数据块，索引结点已经从hash表中删除，包含该索引结点的目录中索引结点号置0、前一个目录项长度重新计算等。此函数包含以下步骤：lock_super()互斥操作，对superblock加锁。根据索引结点号以及索引结点总数来计算该索引结点所在的组号。load_inode_bitmap()从所在的组中调入索引结点位图。将对应位置0。clear_inode()释放该索引结点所占用的cache空间。将组描述符中的空闲索引结点个数增1。将SuperBlock中的空闲索引结点个数增1。从SuperBlock的dirtyinodelist中清除该索引结点。uplock_super()互斥操作完毕。对superblock解锁。,2020/5/3,西安交通大学计算机系,59,EXT2硬盘空间管理_数据块寻址,数据块寻址ext2的单个文件所占有的数据块组织方式，在“硬盘数据结构”部分中已经分析过了。即15个元组长度的数据。前12个直接指向数据块，后3个分别采用1级，2级，3级索引方法。最大可支持的文件大小为2TB。块大小，文件大小上限与索引级数的关系如下图：,2020/5/3,西安交通大学计算机系,60,EXT2硬盘空间管理_分配数据块,分配数据块内核使用ext2_getblk()函数给需要数据空间的文件分配数据块。多个块与文件间的组织形式即前面所述的数据块寻址方式（多级索引）。为了在ext2分区中找到空闲的数据块，ext2使用ext2_alloc_block()函数。为了减少文件的碎片，Ext2文件系统尽量从已经分配给该文件的最后一个数据块开始寻找空闲块。Ext2采用了预先分配数据块的方法。文件不仅仅得到其所申请的数据块，还得被预先（额外）分配了最多达8个的连续数据块。Ext2_inode_info数据结构中，i_prealloc_count域保存了预先分配给文件而没有被使用的数据块。而I_prealloc_block域则保存着下一个将被预分配的块号。,2020/5/3,西安交通大学计算机系,61,EXT2硬盘空间管理_分配数据块,Ext2_alloc_block()及Ext2_getblk()的工作细节。Ext2_alloc_block()函数得到一个指向索引结点和goal的指针。Goal，是一个代表下一个将被分配的最优新块的逻辑块号。Ext2_getblk()根据以下规则来设置goal参数（即判断最优的原则）：如果已经被分配以及预先被分配给文件的块，是连续的块的话，goal即预先分配的数据块的逻辑块号加1。如果上述规则不满足，并且至少一个块已经被预先分配，则goal即这些预先分配的数据块中的某个块的逻辑块号。如果上述规则不满足，则goal即为文件的索引结点所在的组的第一个数据块的逻辑块号。Ext2_alloc_block()函数检查goal是否指向一个预先分配给该文件的一个块。是，则返回该块的逻辑块号。否则，忽略所有已经预分配的块，调用ext2_new_block()函数，查找新的空闲数据块。,2020/5/3,西安交通大学计算机系,62,EXT2硬盘空间管理_分配数据块,ext2_new_block()函数查找空闲块的策略如果传递给ext2_alloc_block()函数的预分配块（goal）空闲，则分配之否则，检查紧跟预分配块之后的64个块是否有空闲如果这64个块中没有空闲的块，则考虑所有的组。从包含goal的组开始过搜索对于每一个组：查找连续的8个空闲块。如果没有，则查找单个空闲块.一旦空闲块找到，搜索即停止。（firstmatch算法）结束分配之前，ext2_new_block()仍然试图预分配8个连接的空闲块。,2020/5/3,西安交通大学计算机系,63,EXT2硬盘空间管理_释放数据块,释放数据块当一个进程删除文件或是将文件长度置0的时候，所有分配给该文件的数据块将被回收。此时调用的函数是ext2_truncate()。该函数调用的参数是文件的索引结点地址。此函数将扫描索引结点中i_block数组，得到分配给该文件的数据块的块号信息。所有这些数据块，将由ext2_free_blocks()函数负责回收。Ext2_free_blocks()函数调用的参数有：文件的索引结点，要被释放的数据块的首地址（块号），要被连续释放的块数。此函数首先调用lock_super()给superblock上锁，然后进行如下操作：得到数据块位图。将要被释放的数据块所对应的位图中的位置0。将组描述符中的“空闲块数”域（bg_free_blocks_count）增1。将superblock中的“空闲块数”域（s_free_blocks_count）增1。最后，再调用uplock_super()给superblock解锁。,2020/5/3,西安交通大学计算机系,64,Ext2的普通文件读写实现,虚拟文件系统（VFS）上对文件的读写是通过系统调用read()或write()来实现的。从文件系统的层次看，这些系统调用对应着一系列的“底层”操作。下面分析Ext2文件系统的写操作过程。Ext2的写操作函数是ext2_file_write()。它有4个参数：fd文件描述符buf写入数据的缓冲区地址count写入的字节大小ppos指向保存文件地址指针上述写函数的工作过程如下步骤：剔除对该文件拥有特权的特权用户将写入地址移动到文件需要写入的地方。计算文件内的地址与文件系统中块的地址的对应关系写操作前准备：,2020/5/3,西安交通大学计算机系,65,Ext2的普通文件读写实现,写操作前准备：a.调用ext2_getblk()得到空闲数据块b.等待可能存在的读操作完成c.将写缓冲区的数据复制到数据块d.调用update_vm_cache()将cache中的数据同步更新文件索引结点中的i_size域设置索引结点中与时间相关域。比如，文件访问时间，修改时间。更新ppos指针返回已经写入文件的字节数。,2020/5/3,西安交通大学计算机系,66,类Ext2文件系统结构设计,Ext2文件系统是一个实际可用的文件系统，实在是太庞大了。为了进行简单的模拟，基于Ext2的思想和算法，设计一个类Ext2的文件系统，实现Ext2文件系统的一个功能子集。并且用现有操作系统上的文件来代替硬盘进行硬件模拟。设计文件系统应该考虑的几个层次介质的物理结构物理操作设备驱动程序完成文件系统的组织结构（逻辑组织结构）对组织结构其上的操作为用户使用文件系统提供的接口类ext2文件系统的数据结构块的定义为简单起见，逻辑块大小与物理块大小均定义为512字节。由于位图只占用