操作系统学习课件

二.链接分配：链接文件

2.显式链接

所有链接指针统一存放在一张显式的链接表(fat表：文件分配表)中。每个FAT表项对应于磁盘数据区的一个盘块。引导块FAT1FAT2根目录区数据区FAT01234562345

数据区簇号…介质类型磁盘FAT表项其他

0EOF（-1）文件的最后一块盘块下一个盘块的块号

空闲盘块2.显式链接若文件f1占据了2，4，5，1四个盘块：012345物理块号FATEOF4512文件目录项f1MS-DOS的文件物理结构6EOF11105EOF0123456789FATFCBA4FCBB91011

A

B物理块号文件A占据了

4，6，11三个盘块。文件B占据了

9，10，5三个盘块。2.显式链接

FAT的大小表项数目——磁盘数据区盘块数；表项长度——保证能存放下最大的盘块号。为了方便检索，FAT表项长度扩充为半个字节的整数倍。如1.2MB的软盘，盘块大小为512B，则：

盘块数为：2.4K个

FAT表项长度为：12位（即1.5B）

FAT占3.6KB存储空间。显式链接分配的优缺点：去除了隐式链接结构的两个缺点；不支持高效的随机存取（如，大文件的随机存取）。FAT文件系统：

FAT12，FAT16，FAT32FAT12，每个FAT表项占12位：项数2^12=4K项，即每个卷最多4K簇；若每簇512B，则一个文件卷：2MB空间；一个物理磁盘可分为4个分区，所以物理盘最大为8MB。若每簇为8个扇区，则物理盘最大可达64MB。簇越大，则能支持更大的磁盘容量，但因簇内碎片而造成的浪费也随之增加。FAT16，每个FAT表项占16位：项数2^16=64K项，即每个卷最多64K簇；簇大小2KB到32KB；一个文件卷最大可达：216X32KB=2GB。FAT文件系统：

FAT12，FAT16，FAT32FAT32，每个FAT表项占32位：FAT表项的高4位保留不用，因此每个文件卷最多有268,435,445个簇；簇的大小最大为32K；每个文件卷必须包含至少65,527簇；FAT32文件系统最大支持32GB的文件卷。根目录文件夹位于数据区，根目录下子目录和文件的数量限制不复存在。FAT16，FAT32簇大小比较卷大小FAT16FAT32NTFS2G32KB2KB＜8G4KB4KB＜16G8KB4KB＜32G16KB4KB≥32G32KB4KBFAT32比FAT16支持更小的簇和更大的磁盘容量，减少了磁盘空间的浪费。引导区FAT1FAT2根目录区数据区FAT文件系统磁盘组织结构：FAT32引导区主要内容：每扇区字节数；通常512B

每簇扇区数；

FAT1的位置；磁盘分区大小（扇区数）；

FAT表大小（扇区数）；根目录位置；引导区备份扇区的位置；文件系统类型。Fat32数据区链接文件性能评价：1.存储空间利用率高；2.文件创建时用户不必指出文件的大小；3.文件动态扩充和修改容易。4.顺序存取效率较高，随机存取效率较低。1.什么是索引文件索引表：系统为每个文件建立的逻辑块号与物理块号的对照表；索引块：存放文件的索引表的物理块，其块号保存在文件FCB的物理地址中；物理文件由数据文件和索引表构成。这种物理文件称为索引文件。三.索引分配：索引文件

2.单级索引分配

三.索引分配：索引文件文件file1分配到4个磁盘块：14，15，30，40：

data14data15data30data40索引表403302151140物理块逻辑块文件A的FCB文件名物理地址file19…索引表超过1块时连续存放；隐式链接；多级索引等。-19索引块40301514

2.单级索引分配

三.索引分配：索引文件单级索引方式优缺点：采用离散分配，消除文件存储空间的外部碎片；随机存取效率高；索引表需占大量文件盘空间，尤其是常用的中小型文件，浪费严重。3.多级索引分配

文件file2分配到1000个磁盘块：2，3，5，20，22，25，…1200，1511，若每个盘块号占4B，每个盘块1KB：

1601一级索引块256个盘块号256个盘块号16001610256个盘块号1620232个盘块号1000个数据块号存放在4个一级索引块中二级索引块16001601161016201700索引表15119991200998……523120物理块逻辑块data2data3data5data…data1200data15111000个磁盘块（数据块）文件A的FCB文件名物理地址file21700…4.混合索引分配Unix系统中，i节点中有13个物理地址项i_addr[13]:i_addr[0]～i_addr[9]:直接地址；i_addr[10]：一次间接地址；i_addr[11]:二次间接地址；i_addr[12]:三次间接地址。假设盘块大小为4KB，每个盘块号占4B，则:

一个磁盘块中能存放1K个磁盘块块号。a1034a10a1逻辑块号0191010331034……4.混合索引分配i节点逻辑文件…物理块号a0a9a1033………i_addr[12]i_addr[11]i_addr[10]i_addr[9]i_addr[8]…i_addr[1]i_addr[0]……:d:c0:b0:a9:a8:a1:a0…a1033a10b0…a2057a1034b1…a3081a2058b2…b1024b1c0…b2048b1025c1…c1024c1da2057a2058a3081………………直接地址一次间址块二次间址块三次间址块a1034a10a1逻辑块号0191010331034……4.混合索引分配i节点逻辑文件…物理块号a0a9a1033………i_addr[12]i_addr[11]i_addr[10]i_addr[9]i_addr[8]…i_addr[1]i_addr[0]……:d:c0:b0:a9:a8:a1:a0…a1033a10b0…a2057a1034b1…a3081a2058b2…b1024b1c0…b2048b1025c1…c1024c1da2057a2058a3081………………直接地址二次间接地址三次间接地址一次间接地址文件的前10个物理块号直接存放到文件i结点的前10个物理地址项i_addr[0]~i_addr[9]中，这10个物理地址项因此叫做直接地址；文件的其余全部物理块号（除前10个外）依次登记到若干个一级索引盘块中；首个一级索引盘块的物理块号登记在文件i结点的第10个物理地址i_addr[10]中，因此这个物理地址项被叫做一次间址项；其余的一级索引盘块的物理块号则依次登记到若干个二级索引盘块中；首个二级索引盘块的物理块号登记在文件i结点的第11个物理地址i_addr[11]中，因此这个物理地址项被叫做二次间址项；其余的二级索引盘块的物理块号则依次登记到1个三级索引盘块中而该三级索引盘块的物理块号则登记在文件i结点的第12个物理地址i_addr[12]中，因此这个物理地址项被叫做三次间址项。4.混合索引分配data…

10个数据块i节点…i_addr[0]i_addr[1]…i_addr[8]i_addr[9]i_addr[10]i_addr[11]i_addr[12]datadatadata假设某个文件总共需要n个磁盘块，则：(1)当n≤10时：所有数据盘块块号全部依次存放在i_addr[0]～i_addr[9]中：≤4.混合索引分配：(2)当10＜n≤10+1024时：前面10个数据盘块号全部存放在i_addr[0]～i_addr[9]中；i_addr[12]i_addr[11]i_addr[10]i_addr[9]i_addr[8]…i_addr[1]i_addr[0]…i节点…前10个…后1024个数据块≤4.混合索引分配：(2)10＜n≤1034：剩下的不超过1024个数据块号放在一个一级索引块（即一次间址块）中；并将该一次间址块块号存入i_addr[10]中：…后1024个数据块…一次间址块i_addr[12]i_addr[11]i_addr[10]i_addr[9]i_addr[8]…i_addr[1]i_addr[0]…i节点≤4.混合索引分配：(2)10＜n≤1034：总结i_addr[12]i_addr[11]i_addr[10]i_addr[9]i_addr[8]…i_addr[1]i_addr[0]…i节点…前10个…后1024个数据块…一次间址块≤4.混合索引分配：(3)当1034＜n≤10+1024+1M时：前面10个数据块号全部存放在i_addr[0]～i_addr[9]中；i_addr[12]i_addr[11]i_addr[10]i_addr[9]i_addr[8]…i_addr[1]i_addr[0]…i节点…前10个…≤1024+1M数据块4.混合索引分配：(3)1034＜n≤1034+1M：

剩下的不超过1024+1M个数据块号放在不超过1025个一次间址块一次间址块1024个…≤1024+1M个数据块…………1024个1024个不超过1025个4.混合索引分配：(3)1034＜n≤1034+1M：将第一个一次间址块块号存入i_addr[10]中；将剩下的不超过1024个一次间址块块号存入一个二级索引块（二次间址块）中；并将该二次间址块块号存入i_addr[11]中：二次间址块≤1024个i_addr[12]i_addr[11]i_addr[10]i_addr[9]i_addr[8]…i_addr[1]i_addr[0]…i节点一次间址块…不超过1025个4.混合索引分配：(3)1034＜n≤1034+1M：总结一次间址块1024个…前10个…≤1024+1M个数据块…………1024个1024个二次间址块≤1024个i_addr[12]i_addr[11]i_addr[10]i_addr[9]i_addr[8]…i_addr[1]i_addr[0]…i节点4.混合索引分配：(3)1034+1M＜n≤1034+1M+1G：前面10个数据块号全部存放在i_addr[0]～i_addr[9]中；i_addr[12]i_addr[11]i_addr[10]i_addr[9]i_addr[8]…i_addr[1]i_addr[0]…i节点…前10个…≤1024+1M+1G数据块4.混合索引分配：(3)1034+1M＜n≤1034+1M+1G：剩下的不超过1024+1M+1G个数据块号放在不超过1025+1M个一次间址块中；一次间址块1024个…≤1024+1M+1G个数据块…………1024个1024个4.混合索引分配：(3)1034+1M＜n≤1034+1M+1G：将第一个一次间址块块号存入i_addr[10]中；剩下的不超过1024+1M个一次间址块块号存入≤1025个二次间址块中；一次间址块…1024个1024个1024个…1024个二次间址块≤1025+1M个i_addr[12]i_addr[11]i_addr[10]i_addr[9]i_addr[8]…i_addr[1]i_addr[0]…i节点4.混合索引分配：(3)1034+1M＜n≤1034+1M+1G：再将第一个二次间址块存入i_addr[11]中；剩下的不超过1024个二次间址块号存入一个三次间址块中；最后将该三次间址块块号存入i_addr[12]中：…二次间址块≤1025个≤1024个三次间址块i_addr[12]i_addr[11]i_addr[10]i_addr[9]i_addr[8]…i_addr[1]i_addr[0]…i节点4.混合索引分配：…前10个…≤1024+1M+1G个数据块……………一次间址块1024个…1024个1024个1024个1024个1024个1024个1024个二次间址块1024个1024个…i_addr[12]i_addr[11]i_addr[10]i_addr[9]i_addr[8]…i_addr[1]i_addr[0]…i节点(3)1034+1M＜n≤1034+1M+1G：总结≤1024个三次间址块四.文件物理结构的比较顺序文件的优点是不需要额外的空间开销，只要在文件目录中指出文件的大小和首块的块号即可，对顺序的访问效率很高。适应于顺序存取且文件不经常修改的情况。缺点是动态地增长和缩小系统开销很大；文件创建时要求用户提供文件的大小；存储空间浪费较大。链接文件克服了连续文件的不足之处，但文件的随机访问系统开销较大。适应于顺序访问的文件。索引文件既适应于顺序存访问，也适应于随机访问，是一种比较好的文件物理结构，但要有用于索引表的空间开销和文件索引的时间开销。UNIX系统是使用索引结构成功的例子。西安电子科技大学2002多选题1.文件的物理结构一般有（）A连续文件B流式文件C记录式文件D串联文件E索引文件答案：ADE西安电子科技大学2002多选题2.连续结构的文件适合采用（）存取方法A顺序存取B直接存取C按键存取D分区存取E以上均不对答案：AB华中科技大学2000年 某文件系统采用单级索引文件结构，假定文件索引表的每个表项占3个字节，即用3个字节存放一个磁盘块的块号，每个磁盘块的大小为512B。试问：1）该文件系统能支持的最大文件大小是多少字节？能管理的最大磁盘空间是多大？2）若采用2级或3级索引，该文件系统能支持的最大文件大小是多少字节？能管理的最大磁盘空间是多大？分析1）由于索引表占用一个大小为512B的磁盘，所以该文件系统的索引表可以管理512/3=170个表项，而每一个表项对应一个物理块，因此该文件系统可以支持的最大文件为：

170*512B=87040B=85K

能管理的最大磁盘空间：224*512B2）若采用二级索引，则是：170*170*512B=7225KB3）若采用三级索引，则是：170*170*170*512B=2456500KB=2398.93M例：混合索引分配方式，FCB中13个地址项，第0～9个地址项为直接地址，第10个地址项为一次间接地址，第11个地址项为二次间接地址，第12个地址项为三次间接地址。盘块大小为512字节，盘块号需要3个字节来描述，每个盘块最多存放170个盘块地址。问：（1）该文件系统允许文件的最大长度是多少？（2）将文件的字节偏移量5000、15000、85000转换为物理块号和块内偏移量。（3）假设某个文件的FCB已在内存，但其他信息均在外存，为了访问文件中某个位置的内容，最少需要几次访问磁盘，最多需要几次访问磁盘？解答：(1)

通过直接地址可访问到10个数据块；通过一次间址还可再访问到170个数据块；通过二次间址还可再访问到1702

个数据块；通过三次间址还可再访问到1703

个数据块；所以文件的最大长度可达：

10＋170＋1702＋1703＝4942080块（2）

①

5000/512=9…392

字节偏移量5000的逻辑块号为9，块内偏移量为392B

由于9＜10，故:

可直接从FCB的第9个地址项处得到逻辑块9对应的物理盘块号，块内偏移量仍为392B。

（2）②15000/512=29…152

字节偏移量15000的逻辑块号为29，块内偏移量为152B

由于10≤29＜10＋170，而29－10＝19，故：可从FCB的第10个地址项，即一次间址项中得到一次间址块的地址，并将它读入内存；再从一次间址块的第19项（即该块的第57～59这三个字节）中获得逻辑块29对应的物理盘块号，块内偏移量仍为152B。（2）③150000/512=292…496

字节偏移量150000的逻辑块号为292，块内偏移为496B

由于10＋170≤292＜10＋170＋170×170292－(10＋170)＝112112/170=0…112

故需要：从FCB的第11个地址项中得到二次间址块的地址，并将该二次间址块读入内存；再从该二次间址块的第0项中获得一个一次间址块的地址，并把该一次间址块读入内存；再从该一次间址块的第112项中获得逻辑块292对应的物理盘块号，块内偏移量为496。（3）

由于文件的FCB已在内存，为了访问文件中某个位置的内容：最少需要1次访问磁盘即可从内存的FCB中直接获得一个直接地址，然后去访问对应的文件数据盘块。最多需要4次访问磁盘第1次是读三次间址块，第2次是读二次间址块，第3次是读一次间址块，第4次是访问文件的数据盘块6.4目录管理

对目录管理的要求如下：实现“按名存取”。(2)提高对目录的检索速度。(3)文件共享。(4)允许文件重名。←文件系统最基本的目标文件控制块（FCB）文件控制块是OS用来存放描述文件、管理文件的文件属性信息的数据结构。文件=FCB+文件内容文件与FCB一一对应FCB是文件存在的唯一标志一.文件控制块和索引结点

文件控制块（FCB）FCB中应包含的内容：基本信息类：①文件名；②文件物理地址和文件的长度：

顺序文件链接文件

索引文件起始磁盘块号单级索引多级索引混合索引索引块块号最高级索引块块号直接地址+一次间址+二次间址等字节数或盘块数一.文件控制块和索引结点

文件控制块（FCB）FCB中应包含的内容：基本信息类：③文件逻辑结构；④文件主标识符和组标识符；⑤文件物理结构。一.文件控制块和索引结点

一.文件控制块和索引结点

文件控制块（FCB）(2)存取控制信息类文件主的权限；核准用户的权限；一般用户的权限。(3)使用信息类：

①文件建立日期及时间；②文件最近访问日期及时间；③文件最近修改日期及时间；④文件链接计数。FCB跟文件内容一样存放在文件存储器中；当文件打开时，FCB的内容被读入内存；FCB的实现方式：一个FCB就是一个目录项，目录项的有序集合形成文件目录（如MS-DOS）。将FCB拆分成文件名和索引结点两部分（如UNIX）一.文件控制块和索引结点

引导块FAT1FAT2根目录区数据区磁盘如：3.5寸双面双密度软盘

80磁道/面

18扇区/道

512字节/扇区1扇区/簇它的盘空间分配情况如下：

绝对扇区号长度（区）内容０１引导记录１９ＦＡＴ１１０９ＦＡＴ２１９１４根目录３３－２８７９２８４７用户文件区又如：360KB的软盘，根目录区为７个扇区，里面可存放112个目录项（FCB）举例（MS-DOS）：磁盘布局文件名首字节：

00h——从未用过的目录项；

E5h——已删除文件的目录项；

05H——实际该字节为的值为E5H；

2Eh——子目录标记项；其他——文件/子目录名的首字节。举例（MS-DOS）：文件控制块

DOS的FCB就是目录项，每个FCB占32B

文件名扩展名属性保留时间日期起始簇号文件长度8B4B2B2B2B10B1B3B一.文件控制块和索引结点

属性：文件名扩展名属性保留时间日期起始簇号文件长度8B4B2B2B2B10B1B3B位b7b6b5b4b3b2b1b0含义保留保留归档子目录卷标系统隐藏只读一.文件控制块和索引结点

举例（MS-DOS）：文件控制块文件名扩展名属性保留时间日期起始块号文件长度8B4B2B2B2B10B1B3B时间：最近修改时间位b15～b11b10～b5b4～b0含义小时分钟秒一.文件控制块和索引结点

举例（MS-DOS）：文件控制块文件名扩展名属性保留时间日期起始块号文件长度8B4B2B2B2B10B1B3B日期：最近修改日期位

b15～b9b8～b5b4～b0含义相对于1980年的年份偏移量月份日期一.文件控制块和索引结点

举例（MS-DOS）：文件控制块2.索引结点（i节点）（1）索引结点的引入

假设：某个目录中有640个目录项

64B/FCB1kB/磁盘块若采用一个FCB就是一个目录项的方式，则：

16个目录项/磁盘块上述目录文件需要40个磁盘块在该目录中检索一个文件平均需要启动磁盘20次。

引导块超级块索引结点区数据区对换区2.索引结点（i节点）（1）索引结点的引入

FCB内容

=

文件名

+

文件其他描述信息

i节点

目录项：

文件名（14B）i节点编号（2B）1#i结点2#i结点3#i结点UNIX文件卷布局上述640个目录项的目录文件可缩短到10个磁盘块，在该目录文件中检索一个文件平均需要启动磁盘5+1次。

64个目录项/块提高对目录的检索速度2.索引结点（i节点）（2）磁盘i结点内容文件类型；文件主标识符；组标识符；存取权限；文件物理地址（13个地址项）；文件长度（字节数）；文件链接计数；文件创建日期、时间；文件最近访问日期、时间；文件最近修改日期时间。rwx

rwx

rwx文件主同组用户其他用户2.索引结点（i节点）（3）内存i结点除了磁盘i结点中包含的内容外，还需要包含：磁盘i节点号；逻辑设备号；状态位：i节点是否上锁或被修改；访