Silberschatz,Galvin,and Gagne?199911.1Applied Operating System Concepts
Module 11,File-System Interface（ 文件系统接口）
File Concept（ 文件概念）
Access Methods（存取方法）
Directory Structure （目录结构）
Protection（保护）
File-System Structure （文件系统结构）
Allocation Methods（分配方法）
Free-Space Management （自由空间管理）
Directory Implementation（目录实现）
Efficiency and Performance（效率和性能）
Recovery（恢复）
Silberschatz,Galvin,and Gagne?199911.2Applied Operating System Concepts
File Concept（ 文件概念）
Contiguous logical address space（相邻的逻辑地址空间）
Types,（ 类型）
– Data（ 数据）
Numeric（ 数字）
Character（ 字符）
Binary（ 二进制）
– Program（ 程序）
Silberschatz,Galvin,and Gagne?199911.3Applied Operating System Concepts
File Structure（ 文件结构）
None - sequence of words,bytes（ 顺序的字和字节）
Simple record structure（ 简单的记录结构 ）
– Lines （ 线性）
– Fixed length（ 固定长度）
– Variable length（ 可变长度）
Complex Structures（ 复杂结构）
– Formatted document（ 规格化的文档 ）
– Relocatable load file（ 可重定位文件 ）
Can simulate last two with first method by inserting
appropriate control characters.
（ 可以用第一个方法通过增加适当的控制字符来模拟后两种方法
）
Who decides（ 需要决定）
– Operating system（ 操作系统 ）
– Program（ 程序 ）
Silberschatz,Galvin,and Gagne?199911.4Applied Operating System Concepts
File Attributes（ 文件属性）
Name – only information kept in human-readable form.
（ 文件名,唯一的以人们可以理解的方式保存的信息 ）
Type – needed for systems that support different types.
（ 类型,需要可以支持多种类型的系统 ）
Location – pointer to file location on device.
（ 位置,指向文件在设备上的存储位置的指针 ）
Size – current file size,（ 大小,当前文件的大小）
Protection – controls who can do reading,writing,executing.
（ 保护：控制对文件的读取，改写和执行的权限 ）
Time,date,and user identification – data for protection，
security,and usage monitoring.（ 时间，日期和用户身份：保护和安全需要的数据 ）
Information about files are kept in the directory structure,which is
maintained on the disk.（ 文件的信息保存在磁盘上的目录结构中 ）
Silberschatz,Galvin,and Gagne?199911.5Applied Operating System Concepts
File Operations（ 文件操作）
Create（ 创建 ）
Write（ 改写 ）
Read（ 读取 ）
reposition within file – file seek（ 重定位文件,文件搜索 ）
Delete（ 删除 ）
Truncate（ 截去 ）
open（ Fi） – search the directory structure on disk for entry
Fi,and move the content of entry to memory.
（ 打开 （ Fi）,在磁盘上的目录结构中搜寻 Fi的表项,然后把表项的内容移动到内存中 ）
close （ Fi） – move the content of entry Fi in memory to
directory structure on disk.
（ 关闭 （ Fi）,把 Fi在内存中的表项内容移动到磁盘中 ）
Silberschatz,Galvin,and Gagne?199911.6Applied Operating System Concepts
File Types – name,extension
文件类型，名称，扩展名
Ex ec uta b le exe,com,bin o r
no n e
rea d y - to - r un m ach i ne -
la n gu a ge pr og r am
Obje ct ob j,o comp lied,mac hi n e
la n gu a ge,no t linked
So urce co de c,p,pa s,17 7,
asm,a
sou rce co de i n va rio us
la n gu a ge s
Ba tch ba t,sh comma n ds to the
comma n d in ter pre ter
T ex t tx t,do c tex tu al da t a d o cume nts
Word pro cess o r w p,t e x,rrf,etc,vari ou s w o rd - p roce ssor
formats
Li bra r y li b,a li bra r ie s of rou t in es
Prin t or vie w ps,dvi,gi f ASCII or b in ar y f il e
Archi ve arc,zip,t ar rel ate d file s gr ou p ed
in to one f il e,so metime s
comp ress ed,
F i l e T yp e U su a l e x t e n si o n F u n ct i o n
Silberschatz,Galvin,and Gagne?199911.7Applied Operating System Concepts
Access Methods（ 存取方法）
Sequential Access（ 顺序存取 ）
read next（ 读下一个 ）
write next （ 写下一个 ）
reset（ 复位 ）
no read after last write（ 未曾读取 ）
（ rewrite）
Direct Access（ 直接存取 ）
read n（ 读第 n项 ）
write n（ 写第 n项 ）
position to n（ 移动位置到第 n项 ）
read next（ 读下一个 ）
write next （ 写下一个 ）
rewrite n（ 重写第 n个 ）
n = relative block number（ n为相对块数 ）
Silberschatz,Galvin,and Gagne?199911.8Applied Operating System Concepts
Directory Structure（ 目录结构）
A collection of nodes containing information about all files.
（ 一个包含着所有文件信息的节点的集合 ）
F 1 F 2 F 3 F 4
F n
Directory
目录
Files
文件
Both the directory structure and the files reside on disk.（ 目录结构和文件都在磁盘上 ）
Backups of these two structures are kept on tapes.（ 备份放在磁带上 ）
Silberschatz,Galvin,and Gagne?199911.9Applied Operating System Concepts
Information in a Device Directory
设备目录中的信息
Name （ 名称 ）
Type（ 类型 ）
Address （ 地址 ）
Current length（ 当前长度 ）
Maximum length（ 最大长度 ）
Date last accessed （ for archival）（ 最后访问时间 ）
Date last updated （ for dump）（ 数据最后更新时间 ）
Owner ID （ who pays）（ 所有者 ID）
Protection information （ discuss later）（ 保护信息 ）
Silberschatz,Galvin,and Gagne?199911.10Applied Operating System Concepts
Operations Performed on Directory
操作系统的目录行为
Search for a file（ 寻找一个文件 ）
Create a file（ 建立一个文件 ）
Delete a file（ 删除一个文件 ）
List a directory（（ 列出目录的列表 ）
Rename a file（ 重命名文件 ）
Traverse the file system（ 整体操作文件系统）
Silberschatz,Galvin,and Gagne?199911.11Applied Operating System Concepts
Organize the Directory （ Logically） to Obtain
组织目录的逻辑结构
Efficiency – locating a file quickly.（ 效率,快速的定位一个文件 ）
Naming – convenient to users.（ 命名,方便用户 ）
– Two users can have same name for different files.
（ 两个用户可以有相同名字的不同文件 ）
– The same file can have several different names.
（ 相同的文件可以有不同的名字 ）
Grouping – logical grouping of files by properties,（ e.g.，
all Pascal programs,all games,… ）
（ 分组,从逻辑上对文件按属性进行分组,比如所有的 Pascal程序,游戏 ）
Silberschatz,Galvin,and Gagne?199911.12Applied Operating System Concepts
Single-Level Directory（ 单级目录）
A single directory for all users.（ 一个对所有用户的简单目录结构 ）
Naming problem（ 命名问题 ）
Grouping problem（ 分组 ）
Silberschatz,Galvin,and Gagne?199911.13Applied Operating System Concepts
Two-Level Directory（ 二级目录）
Separate directory for each user.（ 每个用户有单独的目录结构
）
Path name（ 路径名 ）
Can have the same file name for different user（ 不同的用户可以有相同
Efficient searching（ 有效率的搜索 ）
No grouping capability（ 无法分组 ）
Silberschatz,Galvin,and Gagne?199911.14Applied Operating System Concepts
Tree-Structured Directories（ 树型目录）
Silberschatz,Galvin,and Gagne?199911.15Applied Operating System Concepts
Tree-Structured Directories （ Cont.）
树型目录（续）
Efficient searching（ 有效的搜索 ）
Grouping Capability（ 分组的可能 ）
Current directory （ working directory）（ 当前目录 —工作目录
）
– cd /spell/mail/prog
– type list
Silberschatz,Galvin,and Gagne?199911.16Applied Operating System Concepts
Tree-Structured Directories （ Cont.）
Absolute or relative path name（ 绝对或相对路径名 ）
Creating a new file is done in current directory.
（ 建立新文件在当前路径下 ）
Delete a file（ 删除一个文件 ）
rm <file-name>
Creating a new subdirectory is done in current directory.（ 建立新子目录在当前路径下）
mkdir <dir-name>
Example,if in current directory /spell/mail
mkdir count
mail
prog copy prt exp count
Deleting,mail”? deleting the entire subtree rooted by,mail”.
Silberschatz,Galvin,and Gagne?199911.17Applied Operating System Concepts
Acyclic-Graph Directories（ 无环图结构目录）
Have shared subdirectories and files.（ 有共享的子目录和文件 ）
Silberschatz,Galvin,and Gagne?199911.18Applied Operating System Concepts
Acyclic-Graph Directories （ Cont.）
无环图结构目录（续）
Two different names （ aliasing）（ 别名,两个不同的名字 ）
If dict deletes list? dangling pointer.
Solutions：（ 解决方案 ）
– Backpointers,so we can delete all pointers.
（ 断点，我们可以删除所有的指针）
– Variable size records a problem.
（ 可变大小记录问题）
– Backpointers using a daisy chain organization.
（ 断点组织成菊花链的形式）
– Entry-hold-count solution.（ 表项保留计数的解决）
Silberschatz,Galvin,and Gagne?199911.19Applied Operating System Concepts
General Graph Directory（ 普通图结构目录）
Silberschatz,Galvin,and Gagne?199911.20Applied Operating System Concepts
General Graph Directory （ Cont.）
普通图结构目录（续）
How do we guarantee no cycles?（如何保证无环）
– Allow only links to file not subdirectories.
（只允许链接到文件而不允许链接到子目录）
– Garbage collection.（碎片收集）
– Every time a new link is added use a cycle detection
algorithm to determine whether it is OK.
（每次添加一个链接时都用一个检测算法判断是否不正确）
Silberschatz,Galvin,and Gagne?199911.21Applied Operating System Concepts
Protection（ 保护）
File owner/creator should be able to control
（文件所有者应当有权限控制：）
– what can be done（去做什么）
– by whom（由谁来做）
Types of access（存取的类型）
– Read（读）
– Write（写）
– Execute（执行）
– Append（添加）
– Delete（删除）
– List（列表）
Silberschatz,Galvin,and Gagne?199911.22Applied Operating System Concepts
Access Lists and Groups（ 访问列表或分组）
Mode of access,read,write,execute访问模式：读写执行）
Three classes of users（三种类型的用户）
RWX
a） owner access （所有者） 7? 1 1 1
RWX
b） groups access（组用户） 6? 1 1 0
RWX
c） public access（公共用户） 1? 0 0 1
Ask manager to create a group （ unique name）,say G,and
add some users to the group.（建立一个组，加入一些用户）
For a particular file （ say game） or subdirectory,define an
appropriate access.（对特定文件或目录，定义适当的访问）
owner group public
chmod 761 game
Attach a group to a file（加入组的信息到文件）
chgrp G game
Silberschatz,Galvin,and Gagne?199911.23Applied Operating System Concepts
File-System Structure（ 文件系统结构）
File structure（文件结构）
– Logical storage unit（逻辑存储单元）
– Collection of related information（相关信息的集合）
File system resides on secondary storage （ disks）,
（文件系统存在于辅助存储器中 —磁盘）
File system organized into layers.（文件系统按层组织）
File control block – storage structure consisting of
information about a file.
（文件控制块 FCB,由一个文件的相关信息组成的存储结构）
Silberschatz,Galvin,and Gagne?199911.24Applied Operating System Concepts
Contiguous Allocation（ 顺序分配）
Each file occupies a set of contiguous blocks on the disk.
（每一个文件占用一个连续的磁盘块的集合）
Simple – only starting location （ block #） and length （ number of
blocks） are required.（简单：只需要起始块号和长度）
Random access.（可以随机存取）
Wasteful of space （ dynamic storage-allocation problem）,
（浪费空间：动态存储分配问题）
Files cannot grow.（文件不能增长）
Mapping from logical to physical.（从逻辑地址映射到物理地址）
LA/512
Q
R
– Block to be accessed = ! + starting address
– Displacement into block = R
Silberschatz,Galvin,and Gagne?199911.25Applied Operating System Concepts
Linked Allocation（ 链接分配）
Each file is a linked list of disk blocks,blocks may be
scattered anywhere on the disk.
每个文件是一个的磁盘块的链接列表：块可以分散在磁盘各处。
pointerblock =
Silberschatz,Galvin,and Gagne?199911.26Applied Operating System Concepts
Allocate as needed,link together; e.g.,file starts at block 9
按所需分配磁盘块，链接在一起。文件起始于第九块
Silberschatz,Galvin,and Gagne?199911.27Applied Operating System Concepts
Linked Allocation （ Cont.）（ 链接分配，续）
Simple – need only starting address（ 简单：只需要起始地址）
Free-space management system – no waste of space
（ 自由空间管理系统：没有磁盘空间浪费）
No random access（ 无法随机存取）
Mapping（ 映射）
– Block to be accessed is the Qth block in the linked chain
of blocks representing the file.
– Displacement into block = R + 1
File-allocation table （ FAT） – disk-space allocation used by
MS-DOS and OS/2.（ 文件分配表：被 MS-DOS和 OS/2所采用）
LA/511
Q
R
Silberschatz,Galvin,and Gagne?199911.28Applied Operating System Concepts
Indexed Allocation（ 索引分配）
Brings all pointers together into the index block.
（ 把所有的指针都一起放在索引块里）
Logical view.（ 逻辑形式）
index table
索引表
Silberschatz,Galvin,and Gagne?199911.29Applied Operating System Concepts
Example of Indexed Allocation（ 索引分配的例子）
Silberschatz,Galvin,and Gagne?199911.30Applied Operating System Concepts
Indexed Allocation （ Cont.）（ 索引分配，续
）
Need index table（ 需要索引表）
Random access（ 随机存取）
Dynamic access without external fragmentation,but have
overhead of index block.（ 可以动态存取而没有外部碎片）
Mapping from logical to physical in a file of maximum size of
256K words and block size of 512 words,We need only 1
block for index table.（ 为了从逻辑映射到实际的文件系统，一个 256K字的文件，块为 512字，我们只需一个块作为索引表）
LA/512
Q
R
– Q = displacement into index table
– R = displacement into block
Silberschatz,Galvin,and Gagne?199911.31Applied Operating System Concepts
Indexed Allocation – Mapping （ Cont.）
索引分配 —映射（续）
Mapping from logical to physical in a file of unbounded
length （ block size of 512 words）,
（ 无限长度的文件从逻辑向物理的映射）
Linked scheme – Link blocks of index table （ no limit on
size）,（ 链接策略 —把索引块链接起来）（没有长度限制）
LA / （ 512 x 511）
Q1
R1
– Q1 = block of index table
– R1 is used as follows：
R1 / 512
Q2
R2
– Q2 = displacement into block of index table
– R2 displacement into block of file：
Silberschatz,Galvin,and Gagne?199911.32Applied Operating System Concepts
Indexed Allocation – Mapping （ Cont.）
索引分配 —映射（续）
Two-level index （ maximum file size is 5123）（ 两极索引）
LA / （ 512 x 512）
Q1
R1
– Q1 = displacement into outer-index
– R1 is used as follows：
R1 / 512
Q2
R2
– Q2 = displacement into block of index table
– R2 displacement into block of file：
Silberschatz,Galvin,and Gagne?199911.33Applied Operating System Concepts
Indexed Allocation – Mapping （ Cont.）
索引分配 —映射（续）
outer-index
外部索引 index
table
索引表
File
文件
Silberschatz,Galvin,and Gagne?199911.34Applied Operating System Concepts
Combined Scheme,UNIX （ 4K bytes per block）
联合策略,UNIX（ 4K字节每个块）
Silberschatz,Galvin,and Gagne?199911.35Applied Operating System Concepts
Free-Space Management（ 自由空间管理）
Bit vector （ n blocks）（ 位图）
…
0 1 2 n-1
bit[i] =
0? block[i] free
1? block[i] occupied
Block number calculation（ 块数计算）
（ number of bits per word） *
（ 每个字的 bit数）
（ number of 0-value words）
+
（ 值为 0的字的个数）
offset of first 1 bit
第一个 bit的偏移量
Silberschatz,Galvin,and Gagne?199911.36Applied Operating System Concepts
Free-Space Management （ Cont.）
自由空间管理（续）
Bit map requires extra space,Example（ 位图需要额外空间）
block size = 212 bytes
disk size = 230 bytes （ 1 gigabyte）
n = 230/212 = 218 bits （ or 32K bytes）
Easy to get contiguous files （ 比较容易得到连续的文件）
Linked list （ free list）（ 链接表 —自由空间表）
– Cannot get contiguous space easily（ 得到连续空间困难）
– No waste of space（ 没有浪费空间）
Grouping （ 分组）
Counting（ 计数）
Silberschatz,Galvin,and Gagne?199911.37Applied Operating System Concepts
Free-Space Management （ Cont.）
自由空间管理（续）
Need to protect：（ 需要保护）
– Pointer to free list（ 指向自由空间表的指针）
– Bit map（ 位图）
Must be kept on disk（ 必须保存在磁盘上）
Copy in memory and disk may differ.
（ 内存中的拷贝可能和磁盘上的不同）
Cannot allow for block[i] to have a situation where
bit[i] = 1 in memory and bit[i] = 0 on disk.
（ 磁盘上的值要和内存中的值相一致）
– Solution：（ 解决方案）
Set bit[i] = 1 in disk.（ 磁盘上设置为 1）
Allocate block[i]（ 分配空间）
Set bit[i] = 1 in memory（ 内存中设置为 1）
Silberschatz,Galvin,and Gagne?199911.38Applied Operating System Concepts
Directory Implementation（ 目录实现）
Linear list of file names with pointer to the data blocks.
（ 线性的文件名列表，包括指向数据块的指针）
– simple to program（ 容易编程）
– time-consuming to execute（ 耗 CPU的执行时间）
Hash Table – linear list with hash data structure.
（ 哈希表 —有着哈希数据结构的线性表）
– decreases directory search time（ 减少目录的搜索时间）
– collisions – situations where two file names hash to the
same location（ 碰撞：两个名字映射到同样的位置）
– fixed size（ 固定长度）
Silberschatz,Galvin,and Gagne?199911.39Applied Operating System Concepts
Efficiency and Performance（ 效率和性能）
Efficiency dependent on,（ 效率取决于）
– disk allocation and directory algorithms
（ 磁盘分配和目录算法）
– types of data kept in file’s directory entry
（ 保存在文件目录项中的数据结构）
Performance（ 性能）
– disk cache – separate section of main memory for
frequently sued blocks
（ 磁盘高速缓存 —主存中用于存放经常访问块的单独区域）
– free-behind and read-ahead – techniques to optimize
sequential access
（ free-behind&read-ahead,优化顺序存取的技术）
– improve PC performance by dedicating section of
memroy as virtual disk,or RAM disk.
（ 改进 PC性能可以靠用内存来模拟磁盘，即 RAM）
Silberschatz,Galvin,and Gagne?199911.40Applied Operating System Concepts
Various Disk-Caching Locations
可变的磁盘高速缓存分配
Silberschatz,Galvin,and Gagne?199911.41Applied Operating System Concepts
Recovery（ 恢复）
Consistency checker – compares data in directory structure
with data blocks on disk,and tries to fix inconsistencies.
（ 一致性检查：比较目录结构中的数据和磁盘块中的数据，尝试着去修正不一致）
Use system programs to back up data from disk to another
storage device （ floppy disk,magnetic tape）,
（ 应用系统程序来备份数据到其他的存储设备，软盘，磁带）
Recover lost file or disk by restoring data from backup.
（ 通过从备份重建来恢复丢失的文件或磁盘）
Module 11,File-System Interface（ 文件系统接口）
File Concept（ 文件概念）
Access Methods（存取方法）
Directory Structure （目录结构）
Protection（保护）
File-System Structure （文件系统结构）
Allocation Methods（分配方法）
Free-Space Management （自由空间管理）
Directory Implementation（目录实现）
Efficiency and Performance（效率和性能）
Recovery（恢复）
Silberschatz,Galvin,and Gagne?199911.2Applied Operating System Concepts
File Concept（ 文件概念）
Contiguous logical address space（相邻的逻辑地址空间）
Types,（ 类型）
– Data（ 数据）
Numeric（ 数字）
Character（ 字符）
Binary（ 二进制）
– Program（ 程序）
Silberschatz,Galvin,and Gagne?199911.3Applied Operating System Concepts
File Structure（ 文件结构）
None - sequence of words,bytes（ 顺序的字和字节）
Simple record structure（ 简单的记录结构 ）
– Lines （ 线性）
– Fixed length（ 固定长度）
– Variable length（ 可变长度）
Complex Structures（ 复杂结构）
– Formatted document（ 规格化的文档 ）
– Relocatable load file（ 可重定位文件 ）
Can simulate last two with first method by inserting
appropriate control characters.
（ 可以用第一个方法通过增加适当的控制字符来模拟后两种方法
）
Who decides（ 需要决定）
– Operating system（ 操作系统 ）
– Program（ 程序 ）
Silberschatz,Galvin,and Gagne?199911.4Applied Operating System Concepts
File Attributes（ 文件属性）
Name – only information kept in human-readable form.
（ 文件名,唯一的以人们可以理解的方式保存的信息 ）
Type – needed for systems that support different types.
（ 类型,需要可以支持多种类型的系统 ）
Location – pointer to file location on device.
（ 位置,指向文件在设备上的存储位置的指针 ）
Size – current file size,（ 大小,当前文件的大小）
Protection – controls who can do reading,writing,executing.
（ 保护：控制对文件的读取，改写和执行的权限 ）
Time,date,and user identification – data for protection，
security,and usage monitoring.（ 时间，日期和用户身份：保护和安全需要的数据 ）
Information about files are kept in the directory structure,which is
maintained on the disk.（ 文件的信息保存在磁盘上的目录结构中 ）
Silberschatz,Galvin,and Gagne?199911.5Applied Operating System Concepts
File Operations（ 文件操作）
Create（ 创建 ）
Write（ 改写 ）
Read（ 读取 ）
reposition within file – file seek（ 重定位文件,文件搜索 ）
Delete（ 删除 ）
Truncate（ 截去 ）
open（ Fi） – search the directory structure on disk for entry
Fi,and move the content of entry to memory.
（ 打开 （ Fi）,在磁盘上的目录结构中搜寻 Fi的表项,然后把表项的内容移动到内存中 ）
close （ Fi） – move the content of entry Fi in memory to
directory structure on disk.
（ 关闭 （ Fi）,把 Fi在内存中的表项内容移动到磁盘中 ）
Silberschatz,Galvin,and Gagne?199911.6Applied Operating System Concepts
File Types – name,extension
文件类型，名称，扩展名
Ex ec uta b le exe,com,bin o r
no n e
rea d y - to - r un m ach i ne -
la n gu a ge pr og r am
Obje ct ob j,o comp lied,mac hi n e
la n gu a ge,no t linked
So urce co de c,p,pa s,17 7,
asm,a
sou rce co de i n va rio us
la n gu a ge s
Ba tch ba t,sh comma n ds to the
comma n d in ter pre ter
T ex t tx t,do c tex tu al da t a d o cume nts
Word pro cess o r w p,t e x,rrf,etc,vari ou s w o rd - p roce ssor
formats
Li bra r y li b,a li bra r ie s of rou t in es
Prin t or vie w ps,dvi,gi f ASCII or b in ar y f il e
Archi ve arc,zip,t ar rel ate d file s gr ou p ed
in to one f il e,so metime s
comp ress ed,
F i l e T yp e U su a l e x t e n si o n F u n ct i o n
Silberschatz,Galvin,and Gagne?199911.7Applied Operating System Concepts
Access Methods（ 存取方法）
Sequential Access（ 顺序存取 ）
read next（ 读下一个 ）
write next （ 写下一个 ）
reset（ 复位 ）
no read after last write（ 未曾读取 ）
（ rewrite）
Direct Access（ 直接存取 ）
read n（ 读第 n项 ）
write n（ 写第 n项 ）
position to n（ 移动位置到第 n项 ）
read next（ 读下一个 ）
write next （ 写下一个 ）
rewrite n（ 重写第 n个 ）
n = relative block number（ n为相对块数 ）
Silberschatz,Galvin,and Gagne?199911.8Applied Operating System Concepts
Directory Structure（ 目录结构）
A collection of nodes containing information about all files.
（ 一个包含着所有文件信息的节点的集合 ）
F 1 F 2 F 3 F 4
F n
Directory
目录
Files
文件
Both the directory structure and the files reside on disk.（ 目录结构和文件都在磁盘上 ）
Backups of these two structures are kept on tapes.（ 备份放在磁带上 ）
Silberschatz,Galvin,and Gagne?199911.9Applied Operating System Concepts
Information in a Device Directory
设备目录中的信息
Name （ 名称 ）
Type（ 类型 ）
Address （ 地址 ）
Current length（ 当前长度 ）
Maximum length（ 最大长度 ）
Date last accessed （ for archival）（ 最后访问时间 ）
Date last updated （ for dump）（ 数据最后更新时间 ）
Owner ID （ who pays）（ 所有者 ID）
Protection information （ discuss later）（ 保护信息 ）
Silberschatz,Galvin,and Gagne?199911.10Applied Operating System Concepts
Operations Performed on Directory
操作系统的目录行为
Search for a file（ 寻找一个文件 ）
Create a file（ 建立一个文件 ）
Delete a file（ 删除一个文件 ）
List a directory（（ 列出目录的列表 ）
Rename a file（ 重命名文件 ）
Traverse the file system（ 整体操作文件系统）
Silberschatz,Galvin,and Gagne?199911.11Applied Operating System Concepts
Organize the Directory （ Logically） to Obtain
组织目录的逻辑结构
Efficiency – locating a file quickly.（ 效率,快速的定位一个文件 ）
Naming – convenient to users.（ 命名,方便用户 ）
– Two users can have same name for different files.
（ 两个用户可以有相同名字的不同文件 ）
– The same file can have several different names.
（ 相同的文件可以有不同的名字 ）
Grouping – logical grouping of files by properties,（ e.g.，
all Pascal programs,all games,… ）
（ 分组,从逻辑上对文件按属性进行分组,比如所有的 Pascal程序,游戏 ）
Silberschatz,Galvin,and Gagne?199911.12Applied Operating System Concepts
Single-Level Directory（ 单级目录）
A single directory for all users.（ 一个对所有用户的简单目录结构 ）
Naming problem（ 命名问题 ）
Grouping problem（ 分组 ）
Silberschatz,Galvin,and Gagne?199911.13Applied Operating System Concepts
Two-Level Directory（ 二级目录）
Separate directory for each user.（ 每个用户有单独的目录结构
）
Path name（ 路径名 ）
Can have the same file name for different user（ 不同的用户可以有相同
Efficient searching（ 有效率的搜索 ）
No grouping capability（ 无法分组 ）
Silberschatz,Galvin,and Gagne?199911.14Applied Operating System Concepts
Tree-Structured Directories（ 树型目录）
Silberschatz,Galvin,and Gagne?199911.15Applied Operating System Concepts
Tree-Structured Directories （ Cont.）
树型目录（续）
Efficient searching（ 有效的搜索 ）
Grouping Capability（ 分组的可能 ）
Current directory （ working directory）（ 当前目录 —工作目录
）
– cd /spell/mail/prog
– type list
Silberschatz,Galvin,and Gagne?199911.16Applied Operating System Concepts
Tree-Structured Directories （ Cont.）
Absolute or relative path name（ 绝对或相对路径名 ）
Creating a new file is done in current directory.
（ 建立新文件在当前路径下 ）
Delete a file（ 删除一个文件 ）
rm <file-name>
Creating a new subdirectory is done in current directory.（ 建立新子目录在当前路径下）
mkdir <dir-name>
Example,if in current directory /spell/mail
mkdir count
prog copy prt exp count
Deleting,mail”? deleting the entire subtree rooted by,mail”.
Silberschatz,Galvin,and Gagne?199911.17Applied Operating System Concepts
Acyclic-Graph Directories（ 无环图结构目录）
Have shared subdirectories and files.（ 有共享的子目录和文件 ）
Silberschatz,Galvin,and Gagne?199911.18Applied Operating System Concepts
Acyclic-Graph Directories （ Cont.）
无环图结构目录（续）
Two different names （ aliasing）（ 别名,两个不同的名字 ）
If dict deletes list? dangling pointer.
Solutions：（ 解决方案 ）
– Backpointers,so we can delete all pointers.
（ 断点，我们可以删除所有的指针）
– Variable size records a problem.
（ 可变大小记录问题）
– Backpointers using a daisy chain organization.
（ 断点组织成菊花链的形式）
– Entry-hold-count solution.（ 表项保留计数的解决）
Silberschatz,Galvin,and Gagne?199911.19Applied Operating System Concepts
General Graph Directory（ 普通图结构目录）
Silberschatz,Galvin,and Gagne?199911.20Applied Operating System Concepts
General Graph Directory （ Cont.）
普通图结构目录（续）
How do we guarantee no cycles?（如何保证无环）
– Allow only links to file not subdirectories.
（只允许链接到文件而不允许链接到子目录）
– Garbage collection.（碎片收集）
– Every time a new link is added use a cycle detection
algorithm to determine whether it is OK.
（每次添加一个链接时都用一个检测算法判断是否不正确）
Silberschatz,Galvin,and Gagne?199911.21Applied Operating System Concepts
Protection（ 保护）
File owner/creator should be able to control
（文件所有者应当有权限控制：）
– what can be done（去做什么）
– by whom（由谁来做）
Types of access（存取的类型）
– Read（读）
– Write（写）
– Execute（执行）
– Append（添加）
– Delete（删除）
– List（列表）
Silberschatz,Galvin,and Gagne?199911.22Applied Operating System Concepts
Access Lists and Groups（ 访问列表或分组）
Mode of access,read,write,execute访问模式：读写执行）
Three classes of users（三种类型的用户）
RWX
a） owner access （所有者） 7? 1 1 1
RWX
b） groups access（组用户） 6? 1 1 0
RWX
c） public access（公共用户） 1? 0 0 1
Ask manager to create a group （ unique name）,say G,and
add some users to the group.（建立一个组，加入一些用户）
For a particular file （ say game） or subdirectory,define an
appropriate access.（对特定文件或目录，定义适当的访问）
owner group public
chmod 761 game
Attach a group to a file（加入组的信息到文件）
chgrp G game
Silberschatz,Galvin,and Gagne?199911.23Applied Operating System Concepts
File-System Structure（ 文件系统结构）
File structure（文件结构）
– Logical storage unit（逻辑存储单元）
– Collection of related information（相关信息的集合）
File system resides on secondary storage （ disks）,
（文件系统存在于辅助存储器中 —磁盘）
File system organized into layers.（文件系统按层组织）
File control block – storage structure consisting of
information about a file.
（文件控制块 FCB,由一个文件的相关信息组成的存储结构）
Silberschatz,Galvin,and Gagne?199911.24Applied Operating System Concepts
Contiguous Allocation（ 顺序分配）
Each file occupies a set of contiguous blocks on the disk.
（每一个文件占用一个连续的磁盘块的集合）
Simple – only starting location （ block #） and length （ number of
blocks） are required.（简单：只需要起始块号和长度）
Random access.（可以随机存取）
Wasteful of space （ dynamic storage-allocation problem）,
（浪费空间：动态存储分配问题）
Files cannot grow.（文件不能增长）
Mapping from logical to physical.（从逻辑地址映射到物理地址）
LA/512
Q
R
– Block to be accessed = ! + starting address
– Displacement into block = R
Silberschatz,Galvin,and Gagne?199911.25Applied Operating System Concepts
Linked Allocation（ 链接分配）
Each file is a linked list of disk blocks,blocks may be
scattered anywhere on the disk.
每个文件是一个的磁盘块的链接列表：块可以分散在磁盘各处。
pointerblock =
Silberschatz,Galvin,and Gagne?199911.26Applied Operating System Concepts
Allocate as needed,link together; e.g.,file starts at block 9
按所需分配磁盘块，链接在一起。文件起始于第九块
Silberschatz,Galvin,and Gagne?199911.27Applied Operating System Concepts
Linked Allocation （ Cont.）（ 链接分配，续）
Simple – need only starting address（ 简单：只需要起始地址）
Free-space management system – no waste of space
（ 自由空间管理系统：没有磁盘空间浪费）
No random access（ 无法随机存取）
Mapping（ 映射）
– Block to be accessed is the Qth block in the linked chain
of blocks representing the file.
– Displacement into block = R + 1
File-allocation table （ FAT） – disk-space allocation used by
MS-DOS and OS/2.（ 文件分配表：被 MS-DOS和 OS/2所采用）
LA/511
Q
R
Silberschatz,Galvin,and Gagne?199911.28Applied Operating System Concepts
Indexed Allocation（ 索引分配）
Brings all pointers together into the index block.
（ 把所有的指针都一起放在索引块里）
Logical view.（ 逻辑形式）
index table
索引表
Silberschatz,Galvin,and Gagne?199911.29Applied Operating System Concepts
Example of Indexed Allocation（ 索引分配的例子）
Silberschatz,Galvin,and Gagne?199911.30Applied Operating System Concepts
Indexed Allocation （ Cont.）（ 索引分配，续
）
Need index table（ 需要索引表）
Random access（ 随机存取）
Dynamic access without external fragmentation,but have
overhead of index block.（ 可以动态存取而没有外部碎片）
Mapping from logical to physical in a file of maximum size of
256K words and block size of 512 words,We need only 1
block for index table.（ 为了从逻辑映射到实际的文件系统，一个 256K字的文件，块为 512字，我们只需一个块作为索引表）
LA/512
Q
R
– Q = displacement into index table
– R = displacement into block
Silberschatz,Galvin,and Gagne?199911.31Applied Operating System Concepts
Indexed Allocation – Mapping （ Cont.）
索引分配 —映射（续）
Mapping from logical to physical in a file of unbounded
length （ block size of 512 words）,
（ 无限长度的文件从逻辑向物理的映射）
Linked scheme – Link blocks of index table （ no limit on
size）,（ 链接策略 —把索引块链接起来）（没有长度限制）
LA / （ 512 x 511）
Q1
R1
– Q1 = block of index table
– R1 is used as follows：
R1 / 512
Q2
R2
– Q2 = displacement into block of index table
– R2 displacement into block of file：
Silberschatz,Galvin,and Gagne?199911.32Applied Operating System Concepts
Indexed Allocation – Mapping （ Cont.）
索引分配 —映射（续）
Two-level index （ maximum file size is 5123）（ 两极索引）
LA / （ 512 x 512）
Q1
R1
– Q1 = displacement into outer-index
– R1 is used as follows：
R1 / 512
Q2
R2
– Q2 = displacement into block of index table
– R2 displacement into block of file：
Silberschatz,Galvin,and Gagne?199911.33Applied Operating System Concepts
Indexed Allocation – Mapping （ Cont.）
索引分配 —映射（续）
outer-index
外部索引 index
table
索引表
File
文件
Silberschatz,Galvin,and Gagne?199911.34Applied Operating System Concepts
Combined Scheme,UNIX （ 4K bytes per block）
联合策略,UNIX（ 4K字节每个块）
Silberschatz,Galvin,and Gagne?199911.35Applied Operating System Concepts
Free-Space Management（ 自由空间管理）
Bit vector （ n blocks）（ 位图）
…
0 1 2 n-1
bit[i] =
0? block[i] free
1? block[i] occupied
Block number calculation（ 块数计算）
（ number of bits per word） *
（ 每个字的 bit数）
（ number of 0-value words）
+
（ 值为 0的字的个数）
offset of first 1 bit
第一个 bit的偏移量
Silberschatz,Galvin,and Gagne?199911.36Applied Operating System Concepts
Free-Space Management （ Cont.）
自由空间管理（续）
Bit map requires extra space,Example（ 位图需要额外空间）
block size = 212 bytes
disk size = 230 bytes （ 1 gigabyte）
n = 230/212 = 218 bits （ or 32K bytes）
Easy to get contiguous files （ 比较容易得到连续的文件）
Linked list （ free list）（ 链接表 —自由空间表）
– Cannot get contiguous space easily（ 得到连续空间困难）
– No waste of space（ 没有浪费空间）
Grouping （ 分组）
Counting（ 计数）
Silberschatz,Galvin,and Gagne?199911.37Applied Operating System Concepts
Free-Space Management （ Cont.）
自由空间管理（续）
Need to protect：（ 需要保护）
– Pointer to free list（ 指向自由空间表的指针）
– Bit map（ 位图）
Must be kept on disk（ 必须保存在磁盘上）
Copy in memory and disk may differ.
（ 内存中的拷贝可能和磁盘上的不同）
Cannot allow for block[i] to have a situation where
bit[i] = 1 in memory and bit[i] = 0 on disk.
（ 磁盘上的值要和内存中的值相一致）
– Solution：（ 解决方案）
Set bit[i] = 1 in disk.（ 磁盘上设置为 1）
Allocate block[i]（ 分配空间）
Set bit[i] = 1 in memory（ 内存中设置为 1）
Silberschatz,Galvin,and Gagne?199911.38Applied Operating System Concepts
Directory Implementation（ 目录实现）
Linear list of file names with pointer to the data blocks.
（ 线性的文件名列表，包括指向数据块的指针）
– simple to program（ 容易编程）
– time-consuming to execute（ 耗 CPU的执行时间）
Hash Table – linear list with hash data structure.
（ 哈希表 —有着哈希数据结构的线性表）
– decreases directory search time（ 减少目录的搜索时间）
– collisions – situations where two file names hash to the
same location（ 碰撞：两个名字映射到同样的位置）
– fixed size（ 固定长度）
Silberschatz,Galvin,and Gagne?199911.39Applied Operating System Concepts
Efficiency and Performance（ 效率和性能）
Efficiency dependent on,（ 效率取决于）
– disk allocation and directory algorithms
（ 磁盘分配和目录算法）
– types of data kept in file’s directory entry
（ 保存在文件目录项中的数据结构）
Performance（ 性能）
– disk cache – separate section of main memory for
frequently sued blocks
（ 磁盘高速缓存 —主存中用于存放经常访问块的单独区域）
– free-behind and read-ahead – techniques to optimize
sequential access
（ free-behind&read-ahead,优化顺序存取的技术）
– improve PC performance by dedicating section of
memroy as virtual disk,or RAM disk.
（ 改进 PC性能可以靠用内存来模拟磁盘，即 RAM）
Silberschatz,Galvin,and Gagne?199911.40Applied Operating System Concepts
Various Disk-Caching Locations
可变的磁盘高速缓存分配
Silberschatz,Galvin,and Gagne?199911.41Applied Operating System Concepts
Recovery（ 恢复）
Consistency checker – compares data in directory structure
with data blocks on disk,and tries to fix inconsistencies.
（ 一致性检查：比较目录结构中的数据和磁盘块中的数据，尝试着去修正不一致）
Use system programs to back up data from disk to another
storage device （ floppy disk,magnetic tape）,
（ 应用系统程序来备份数据到其他的存储设备，软盘，磁带）
Recover lost file or disk by restoring data from backup.
（ 通过从备份重建来恢复丢失的文件或磁盘）
