chap6(49-50).ppt

复习：外存分配方式复习：外存分配方式p连续分配方式：文件分到连续分配方式：文件分到一组连续一组连续的盘块♥盘块组织方式：在目录中记录盘块组织方式：在目录中记录—文件名、起始文件名、起始盘块号、长度（总盘块数）盘块号、长度（总盘块数）♥特点：目录项中的特点：目录项中的起始盘块号起始盘块号+逻辑盘块号逻辑盘块号就是就是某逻辑地址数据所在的物理盘块号因此，读某逻辑地址数据所在的物理盘块号因此，读取某逻辑地址中的数据只需要取某逻辑地址中的数据只需要启动启动1次盘块次盘块♥优点：可优点：可实现随机访问实现随机访问♥缺点：需要缺点：需要的盘块的盘块——外存空间利用率低、文外存空间利用率低、文件扩充困难件扩充困难1复习：外存分配方式复习：外存分配方式p链接方式：文件分到一组链接方式：文件分到一组离散离散的盘块♥显式链接显式链接Ø盘块组织方式：盘块组织方式：•在目录中记录：文件名、起始盘块号、结束在目录中记录：文件名、起始盘块号、结束盘块号•其它盘块号存放在上一个盘块的地址域中其它盘块号存放在上一个盘块的地址域中Ø特点：只能从起始盘块开始特点：只能从起始盘块开始顺序访问顺序访问因此，读取某逻辑地址中的数据需要读取某逻辑地址中的数据需要多次启动磁盘多次启动磁盘。

Ø优点：不需要连续的内存空间优点：不需要连续的内存空间Ø缺点：读取数据需要多次启动磁盘缺点：读取数据需要多次启动磁盘2复习：外存分配方式复习：外存分配方式♥隐示链接隐示链接Ø盘块组织方式：盘块组织方式：•在目录中记录：文件名、起始盘块号在目录中记录：文件名、起始盘块号•其它盘块号存放于其它盘块号存放于FAT[上一个盘块号上一个盘块号]Ø特点：从目录及特点：从目录及FAT（在内存）中（在内存）中顺序查找顺序查找盘盘块号因此，读取某逻辑地址中的数据需要块号因此，读取某逻辑地址中的数据需要启启动动1次磁盘次磁盘Ø优点：不需要连续的内存空间优点：不需要连续的内存空间Ø缺点：顺序查找且安全性差缺点：顺序查找且安全性差3复习：外存分配方式复习：外存分配方式p索引方式：文件分到一组索引方式：文件分到一组离散离散的盘块♥单级索引单级索引Ø盘块组织方式：盘块组织方式：•在目录中记录：文件名、索引盘块号在目录中记录：文件名、索引盘块号•文件的盘块号按顺序存放在索引表中文件的盘块号按顺序存放在索引表中Ø特点：从目录中找到索引盘块，从索引盘块特点：从目录中找到索引盘块，从索引盘块中中直接找到直接找到某逻辑地址所在的盘块号。

因此，读某逻辑地址所在的盘块号因此，读取某逻辑地址中的数据需要启动取某逻辑地址中的数据需要启动2次磁盘Ø优点：既能实现离散存储，也能实现随机访问优点：既能实现离散存储，也能实现随机访问Ø缺点：能够处理的文件很小缺点：能够处理的文件很小4复习：外存分配方式复习：外存分配方式♥多级索引多级索引Ø盘块组织方式：盘块组织方式：•在目录中记录：文件名、外层索引盘块号在目录中记录：文件名、外层索引盘块号•外层索引表中按顺序存放内层索引表所在的外层索引表中按顺序存放内层索引表所在的盘块号•内层索引表中按顺序存放文件存放的盘块号内层索引表中按顺序存放文件存放的盘块号§假设某系统一个盘块大小为假设某系统一个盘块大小为1K，某个索引项需，某个索引项需要要4B，这逻辑地址，这逻辑地址A对应的对应的逻辑块号逻辑块号M=A/1K每个物理块中的索引项数每个物理块中的索引项数L=1K/4=2565复习：外存分配方式复习：外存分配方式Ø特点：特点：•从目录中找到外层索引盘块从目录中找到外层索引盘块•从从外层索引表外层索引表[M/L]读出内层索引表所在的物理读出内层索引表所在的物理块号块号•从从内层索引表内层索引表[M%L]读出数据所在的物理块号。

读出数据所在的物理块号•因此，二级索引读取某逻辑地址中的数据需要因此，二级索引读取某逻辑地址中的数据需要启动启动3次磁盘Ø优点：既能实现离散存储，也能实现随机访问优点：既能实现离散存储，也能实现随机访问Ø缺点：较小的文件需要多次启动磁盘缺点：较小的文件需要多次启动磁盘6复习：外存分配方式复习：外存分配方式♥混合索引：混合索引：UNIX系统使用的文件分配方式系统使用的文件分配方式Ø盘块组织方式：盘块组织方式：•在目录设置一个在目录设置一个13地址项的索引结点地址项的索引结点•0~9为直接文件，即为直接文件，即0—9中存放文件物理块号中存放文件物理块号•10为一级索引，即为一级索引，即10为索引盘块号为索引盘块号•11为二级索引，即为二级索引，即11中为外层索引盘块号中为外层索引盘块号•12为三级索引，即为三级索引，即12中为三级外层索引盘块号中为三级外层索引盘块号7i_addr[0]i_addr[1]……i_addr[9]i_addr[10]i_addr[11]i_addr[12]索引结点索引结点6.3 外存分配方式外存分配方式86.3 外存分配方式外存分配方式Ø引入目的：引入目的：•克服顺序方式的缺点克服顺序方式的缺点—需要连续盘块需要连续盘块•克服链接方式的缺点克服链接方式的缺点—无法实现随机存取无法实现随机存取•克服单级索引的缺点克服单级索引的缺点—对应文件较小对应文件较小•克服多级索引的缺点克服多级索引的缺点—较小的文件需要多次启较小的文件需要多次启动磁盘动磁盘96.3 外存分配方式外存分配方式v盘块大小为盘块大小为1KB，，记录盘块号需要记录盘块号需要4个字节个字节Ø混合索引能处理的最长文件的计算。

混合索引能处理的最长文件的计算Ø计算逻辑地址：计算逻辑地址：5000、、15000、、150000转换为转换为物理块号和块内位移物理块号和块内位移Ø简述读取上述逻辑地址对应数据所在的盘块的过简述读取上述逻辑地址对应数据所在的盘块的过程Ø若某文件的目录项已经在内存，采用混合索引方若某文件的目录项已经在内存，采用混合索引方式，读取文件的内容，最少需要启动几次盘块？式，读取文件的内容，最少需要启动几次盘块？最多需要启动几次盘块？最多需要启动几次盘块？106.4 目目 录录 管管 理理 q目录文件由若干目录项目录文件由若干目录项(FCB)组成，每个目录项组成，每个目录项记录一个文件的名字、属性、及其记录一个文件的名字、属性、及其存储位置存储位置等信等信息，供检索时使用息，供检索时使用q目录是文件系统实现按名存取的重要手段目录是文件系统实现按名存取的重要手段q对目录管理的要求如下：对目录管理的要求如下：Ø实现实现“按名存取按名存取”Ø提高对文件的检索速度提高对文件的检索速度Ø文件共享文件共享Ø允许文件重名允许文件重名11q文件控制块和索引结点文件控制块和索引结点v文件控制块文件控制块 (FCB)：：就是目录项，在文件控制块就是目录项，在文件控制块（目录项）中，通常含有以下三类信息：（目录项）中，通常含有以下三类信息：(1)基本信基本信息类息类;（（2）存取控制信息类；）存取控制信息类；(3)使用信息类。

使用信息类v目录文件占用盘块数的计算：目录文件占用盘块数的计算：在某文件系统中，每在某文件系统中，每个盘块为个盘块为512字节，文件控制块为字节，文件控制块为64个字节，该系个字节，该系统中共有统中共有256个文件，计算目录占用的盘块数？读个文件，计算目录占用的盘块数？读取一个取一个FCB平均启动磁盘的次数？平均启动磁盘的次数？6.4 目目 录录 管管 理理 12v索引结点索引结点Ø索引结点的引入：索引结点的引入：文件目录占用大量的盘块，检文件目录占用大量的盘块，检索时需要将盘块一一调入内存，速度慢其实检索时需要将盘块一一调入内存，速度慢其实检索时，只用到文件名，仅当找到一个目录项时，索时，只用到文件名，仅当找到一个目录项时，才需从该目录项中读出所需的信息才需从该目录项中读出所需的信息UNIX系统，系统，采用了把文件名与文件描述信息分开的办法采用了把文件名与文件描述信息分开的办法Ø将文件描述信息单独形成一个称为索引结点的数将文件描述信息单独形成一个称为索引结点的数据结构，简称为据结构，简称为i结点Ø在文件目录中的每一个目录项，仅由文件名和指在文件目录中的每一个目录项，仅由文件名和指向该文件所对应的向该文件所对应的i结点的指针所构成。

结点的指针所构成 6.4 目目 录录 管管 理理 13文件名文件名索引结点编号索引结点编号Fa 20 SQT 30文件目录文件目录索引结点编号索引结点编号文件类型、长度文件类型、长度文件存取权限文件存取权限文件物理地址文件物理地址：：：：索引结点索引结点6.4 目目 录录 管管 理理 14Ø引入索引结点后，查找一个目录项启动盘块的平引入索引结点后，查找一个目录项启动盘块的平均次数：均次数：每个盘块为每个盘块为512字节，其中文件名占字节，其中文件名占8个个字节如果索引结点编号占字节如果索引结点编号占2个字节，该系统共有个字节，该系统共有256个文件，为找到其中一个文件的个文件，为找到其中一个文件的FCB，，平均启平均启动磁盘的次数动磁盘的次数6.4 目目 录录 管管 理理 15q目录结构目录结构v单级目录结构：单级目录结构： 在整个系统中只建立一张目录表，在整个系统中只建立一张目录表，每个文件占一条记录每个文件占一条记录缺点缺点: (1) 查找速度慢查找速度慢 (2)不允许重名不允许重名文件名文件名 物理地址物理地址文件说明文件说明 状态位状态位F1ST6.4 目目 录录 管管 理理 16v两级目录：为了克服单级目录所存在的缺点，两级目录：为了克服单级目录所存在的缺点，可以为每一个用户建立一个单独的用户文件目可以为每一个用户建立一个单独的用户文件目录录UFD。

系统建立一个主目录系统建立一个主目录6.4 目目 录录 管管 理理 17用户名用户名 指向子目录指针指向子目录指针Wang ZhangWang 用户目录用户目录文件名文件名Fa. aa.文件名文件名dd.cc.Zhang用户目录用户目录主目录主目录6.4 目目 录录 管管 理理 cc. md.bb.Fa.18Ø优点：优点：(1)提高了检索目录的速度提高了检索目录的速度2)在不同的用户目录中，可以使用相同的文件名在不同的用户目录中，可以使用相同的文件名3)不同用户还可使用不同的文件名来访问系统中不同用户还可使用不同的文件名来访问系统中的同一个共享文件的同一个共享文件6.4 目目 录录 管管 理理 19Ø单级目录和二级目录比较次数的计算：单级目录和二级目录比较次数的计算：例如：某系统有例如：某系统有1000个用户，每个用户有个用户，每个用户有100个个文件，问：文件，问：（（1）单级目录结构最多需要比较多少次？）单级目录结构最多需要比较多少次？（（2）二级目录结构最多需要比较多少次？）二级目录结构最多需要比较多少次？6.4 目目 录录 管管 理理 20v多级目录结构多级目录结构Ø目录结构：多级目录结构又称为树型目录结构。

主目录结构：多级目录结构又称为树型目录结构主目录在这里又称为根目录，把数据文件称为树叶，目录在这里又称为根目录，把数据文件称为树叶，其它的目录（文件夹）均作为树的中间结点其它的目录（文件夹）均作为树的中间结点Ø目录项的分类：目录项的分类：ü若某个目录项指向的是文件，则称为若某个目录项指向的是文件，则称为文件的目文件的目录项录项ü若某个目录项指向的是下一级目录，则称为若某个目录项指向的是下一级目录，则称为目目录的目录项录的目录项6.4 目目 录录 管管 理理 21ABCD1D2 D3B1B2K1K2K322q目录查询技术：当用户要访问文件时，系统总是要目录查询技术：当用户要访问文件时，系统总是要对目录进行查询目前主要使用两种方法：对目录进行查询目前主要使用两种方法：v线性检索法：也叫顺序检索法利用用户提供的文线性检索法：也叫顺序检索法利用用户提供的文件名，在目录文件中顺序查找件名，在目录文件中顺序查找v举例：若系统为每个文件建立一个目录项（文件名举例：若系统为每个文件建立一个目录项（文件名和索引结点）和索引结点） ，用户给定的文件路径名是：，用户给定的文件路径名是： /usr/wang/fa6.4 目目 录录 管管 理理 23根目录根目录ID 文件名文件名1.2..6usri结点结点6ID=6132132块内容块内容ID 文件名文件名26 wangID=26496i结点结点26550块上块上的内容的内容ID 文件名文件名60fa496块上的内容块上的内容ID=60550i结点结点606.4 目目 录录 管管 理理 注：注：ID为索引结点编号为索引结点编号24vHash方法：方法：Ø系统建立了一张系统建立了一张Hash索引文件目录，利用索引文件目录，利用hash方方法进行查询，将用户提供的文件名变换为文件目录法进行查询，将用户提供的文件名变换为文件目录的索引值，再利用该索引值到目录中去查找，显著的索引值，再利用该索引值到目录中去查找，显著地提高检索速度。

地提高检索速度Ø文件名转换时要注意文件名转换时要注意“冲突冲突” 6.4 目目 录录 管管 理理 256.5 文件存储空间管理文件存储空间管理 v文件存储空间管理：文件存储空间管理：操作系统如何管理磁盘空间操作系统如何管理磁盘空间（分配及回收）分配及回收）Ø连续分配方式：空闲区表（链）连续分配方式：空闲区表（链）Ø离散分配方式（离散分配方式（※※）：位示图、成组链接法）：位示图、成组链接法v分配磁盘空间的单位：分配磁盘空间的单位：盘块（扇区）盘块（扇区）266.5 文件存储空间管理文件存储空间管理 v对磁盘空间进行管理：对磁盘空间进行管理：（（1）使用）使用数据结构数据结构记录系统中盘块的使用情况记录系统中盘块的使用情况2）提供）提供分配分配算法：根据数据结构，按照算法选算法：根据数据结构，按照算法选择空闲盘块，分配给文件择空闲盘块，分配给文件3）提供）提供回收回收算法：根据删除的文件名，找到分算法：根据删除的文件名，找到分给该文件的盘块号，并将它们作为空闲盘块记入给该文件的盘块号，并将它们作为空闲盘块记入数据结构中数据结构中27q连续分配方式：同内存管理中连续分配方式：同内存管理中动态分区分配动态分区分配v特点：给文件分配一组连续的空闲盘块，因此文件特点：给文件分配一组连续的空闲盘块，因此文件的物理结构为的物理结构为—连续文件。

连续文件v优点：文件的存取速度快，可实现随机存取优点：文件的存取速度快，可实现随机存取v缺点：文件扩充困难，产生较多的外存零头，外存缺点：文件扩充困难，产生较多的外存零头，外存利用率低利用率低v适用情况：适用情况：（（1）对换区空间的管理：对换区对速度要求高）对换区空间的管理：对换区对速度要求高（（2）较小文件的存储）较小文件的存储6.5 文件存储空间管理文件存储空间管理 28v空闲表法：空闲表法：Ø记录磁盘使用情况的数据结构：空闲表记录磁盘使用情况的数据结构：空闲表6.5 文件存储空间管理文件存储空间管理 序号序号 第一空闲盘块号第一空闲盘块号空闲盘块数空闲盘块数120424113603状态状态01129Ø存储空间的分配：采用首次适应、循环首次适应、存储空间的分配：采用首次适应、循环首次适应、最佳适应等算法从空闲表中选择一个合适的空闲区最佳适应等算法从空闲表中选择一个合适的空闲区域Ø存储空间的回收：删除文件会释放一些盘块，将释存储空间的回收：删除文件会释放一些盘块，将释放的盘块作为空闲区域记入空闲表中注意合并放的盘块作为空闲区域记入空闲表中注意合并Ø思考：思考：（（1）操作系统如何记载将一组连续盘块分配给某个）操作系统如何记载将一组连续盘块分配给某个文件？文件？（（2）删除时，如何知道删除文件占用了哪些盘块？）删除时，如何知道删除文件占用了哪些盘块？6.5 文件存储空间管理文件存储空间管理 30q离散分配方式：离散分配方式：v特点：不必给文件分配连续的空闲盘块，因此文件特点：不必给文件分配连续的空闲盘块，因此文件的物理结构通常为：索引文件、链接文件。

的物理结构通常为：索引文件、链接文件v优点：存储空间的利用率高，扩充容易优点：存储空间的利用率高，扩充容易v缺点：存取速度慢缺点：存取速度慢v适用情况：较大文件的存储适用情况：较大文件的存储v两种离散分配方式：两种离散分配方式：（（1）位示图法）位示图法（（2）成组链接法）成组链接法6.5 文件存储空间管理文件存储空间管理 31q位示图：位示图：v管理方式：管理方式：（（1）利用二进制的一位（）利用二进制的一位（bit））来表示磁盘中一个盘来表示磁盘中一个盘块的使用情况当其值为块的使用情况当其值为“0”时，表示对应的盘块时，表示对应的盘块空闲；为空闲；为“1”时表示该盘块已分配时表示该盘块已分配2）操作系统通常使用若干个）操作系统通常使用若干个计算机字计算机字（（1字＝字＝32位）位）来实现位示图因此，位示图可以看成一个来实现位示图因此，位示图可以看成一个n行行*32列的二维矩阵列的二维矩阵3）位示图的行、列编号：从）位示图的行、列编号：从0开始6.5 文件存储空间管理文件存储空间管理 32v关键问题：关键问题：（（1）盘块号是线性的（例如）盘块号是线性的（例如500个盘块，编号为个盘块，编号为0—499））（（2））位示图是二维的（行号、列号）位示图是二维的（行号、列号）（（3）某个盘块号在位示图中对应的行、列号）某个盘块号在位示图中对应的行、列号（（4）位示图的某行某列对应的盘块号。

位示图的某行某列对应的盘块号6.5 文件存储空间管理文件存储空间管理 33v举例：某系统的磁盘空间为举例：某系统的磁盘空间为600KB，，每个盘块的大每个盘块的大小为小为1KB，，系统使用一个计算机字（系统使用一个计算机字（32位）来代表位）来代表位示图的一行，请计算：位示图的一行，请计算： （位示图行、列号从（位示图行、列号从0开开始，盘块号从始，盘块号从0开始）开始）（（1）该位示图至少需要）该位示图至少需要 个计算机字个计算机字2）第）第208个盘块，对应位示图的个盘块，对应位示图的 字字 列3）位示图的第）位示图的第7字第字第28列对应的盘块号是列对应的盘块号是 6.5 文件存储空间管理文件存储空间管理 34。