操作系统第6章文件管理(2)

1、Operating SystemOperating SystemPage 12022-3-1Operating SystemOperating SystemPage 22022-3-1q文件和文件系统文件和文件系统q文件的逻辑结构文件的逻辑结构q外存分配方式外存分配方式q目录管理目录管理q文件存储空间的管理文件存储空间的管理q文件共享与文件保护文件共享与文件保护q数据一致性控制数据一致性控制Operating SystemOperating SystemPage 32022-3-1q文件逻辑结构的类型文件逻辑结构的类型q顺序文件顺序文件q索引文件索引文件q索引顺序文件索引顺序文件q直接文件和哈

2、希文件直接文件和哈希文件Operating SystemOperating SystemPage 42022-3-1q文件组织的两种观点文件组织的两种观点v用户观点用户观点（逻辑结构）：研究的是用户思维中的（逻辑结构）：研究的是用户思维中的抽象文件，也叫逻辑文件。其目的是为用户提供抽象文件，也叫逻辑文件。其目的是为用户提供一种结构清晰、使用简便的逻辑组织。用户按此一种结构清晰、使用简便的逻辑组织。用户按此去存储、检索和加工处理有关文件信息。去存储、检索和加工处理有关文件信息。v实现观点实现观点（物理结构）：研究的是存储在物理设（物理结构）：研究的是存储在物理设备介质上的实际文件，即物理文件。其

3、目的是选备介质上的实际文件，即物理文件。其目的是选择一些性能良好、设备利用率高的物理结构。系择一些性能良好、设备利用率高的物理结构。系统按此和外部设备打交道，控制信息的传输。统按此和外部设备打交道，控制信息的传输。q对逻辑结构的要求对逻辑结构的要求v提高检索速度提高检索速度v便于修改便于修改v降低文件的存储费用降低文件的存储费用Operating SystemOperating SystemPage 52022-3-1q有结构文件有结构文件记录式文件记录式文件v按记录长度分按记录长度分定长记录定长记录变长记录变长记录v根据用户和系统管理需要分根据用户和系统管理需要分顺序文件顺序文件索引文件索引

4、文件索引顺序文件索引顺序文件q无结构文件无结构文件v流式文件流式文件 其长度以字节为单位其长度以字节为单位v采用读写指针来指出下一个要访问的字符采用读写指针来指出下一个要访问的字符v如如 源程序、源程序、 可执行文件、可执行文件、 库函数库函数等等Operating SystemOperating SystemPage 62022-3-16.1.2 文件类型和文件系统模型文件类型和文件系统模型 1. 文件类型文件类型 （1）。这是由若干个记录所构成的文件，故又这是由若干个记录所构成的文件，故又称为称为。根据记录的长度是定长的还是可改变的。根据记录的长度是定长的还是可改变的又可进一步分为定长记录

5、文件和可变长记录文件。又可进一步分为定长记录文件和可变长记录文件。（2）。直接由字符序列所构成的文件，故称为直接由字符序列所构成的文件，故称为。Operating SystemOperating SystemPage 72022-3-1Operating SystemOperating SystemPage 82022-3-16.2.1 文件逻辑结构的类型文件逻辑结构的类型 1. 有结构文件有结构文件：文件中所有记录的文件中所有记录的的，所有记录中的，所有记录中的各数据项，都处在相同的位置，具有相同的顺序和长度。的各数据项，都处在相同的位置，具有相同的顺序和长度。：指文件中各记录的指文件中各记

6、录的。：由一系列记录按某种顺序排列所形成的文件，其由一系列记录按某种顺序排列所形成的文件，其中的记录通常是中的记录通常是。：当记录为当记录为时，通常为之建立一张索引表，时，通常为之建立一张索引表，并为每个记录设置一张表项，以加快对记录的检索速度。并为每个记录设置一张表项，以加快对记录的检索速度。：是是 ，它为文件建立，它为文件建立一张索引表，为每一组记录中的第一个记录设置一个表项。一张索引表，为每一组记录中的第一个记录设置一个表项。Operating SystemOperating SystemPage 92022-3-1q文件逻辑结构的类型文件逻辑结构的类型q顺序文件顺序文件q索引文件索引文

7、件q索引顺序文件索引顺序文件q直接文件和哈希文件直接文件和哈希文件Operating SystemOperating SystemPage 102022-3-1q逻辑记录的排序逻辑记录的排序v串结构串结构各记录之间的顺序与关键字无关各记录之间的顺序与关键字无关通常由时间来决定通常由时间来决定存在问题存在问题v顺序结构顺序结构文件中的所有记录按关键字文件中的所有记录按关键字(词词)排列排列记录号记录号学号学号姓名姓名性别性别出生时间出生时间11赵赵23钱钱34孙孙45李李56周周620吴吴Operating SystemOperating SystemPage 112022-3-1q对对顺序文件

8、顺序文件(Sequential File)的读的读/写操作写操作R0R1R2R3RiLLLLLL2L3L4LL(i1)LRptr(a) 定定长长记记录录文文件件L0R0L1R1RiWptr(b)变变长长记记录录文文件件Li00L0L01L1L0L12Li (Lk1)i1k 0 (Lk1)ik 0记录长度记录长度记录记录起始地址起始地址Operating SystemOperating SystemPage 122022-3-1q顺序文件的优缺点顺序文件的优缺点v优点优点结构简单，容易实现结构简单，容易实现顺序文件的最佳应用场合，是在对诸记录进行顺序文件的最佳应用场合，是在对诸记录进行批量存取批

9、量存取时，即每次要读或写一大批记录时，即每次要读或写一大批记录只有顺序文件才能存储在磁带上，并能有效地只有顺序文件才能存储在磁带上，并能有效地工作工作v缺点缺点如果用户如果用户(程序程序)要求要求查找或修改查找或修改单个记录，单个记录， 顺顺序文件所表现出来的序文件所表现出来的性能就可能很差性能就可能很差如果想如果想增加或删除增加或删除一个记录，一个记录， 都比较困难都比较困难（需（需移动移动大量数据）大量数据）创建文件必须给出大小，不利于动态增长创建文件必须给出大小，不利于动态增长Operating SystemOperating SystemPage 132022-3-1q文件逻辑结构的类

10、型文件逻辑结构的类型q顺序文件顺序文件q索引文件索引文件q索引顺序文件索引顺序文件q直接文件和哈希文件直接文件和哈希文件Operating SystemOperating SystemPage 142022-3-1q对对定长记录定长记录文件，如果要查找第文件，如果要查找第i个记录，个记录， 可直可直接根据下式计算来获得第接根据下式计算来获得第i个记录相对于第一个记个记录相对于第一个记录首址的地址录首址的地址Ai = iLq对于对于可变长度记录可变长度记录的文件，要查找其第的文件，要查找其第i个记录时，个记录时，须首先计算出该记录的首地址，须首先计算出该记录的首地址，Li为第为第i个记录长个记录

11、长度度10iiiiiLAOperating SystemOperating SystemPage 152022-3-1索索引引号号0长长度度 m指指针针 ptrm01m1-imi-索索引引表表R0R1-Ri-逻逻辑辑文文件件索引文件的组织索引文件的组织 索引本身是一个定长记录的顺序文件，主文件中每个记录在索引本身是一个定长记录的顺序文件，主文件中每个记录在索引表中占一个表项，可采用快速查找算法，如字典索引表中占一个表项，可采用快速查找算法，如字典Operating SystemOperating SystemPage 172022-3-16.2.3 索引文件索引文件 2、索引文件的检索步骤：、

12、索引文件的检索步骤： （1）根据用户提供的关键字，利用折半查找法去检索索）根据用户提供的关键字，利用折半查找法去检索索引表，从中找到相应的表项；引表，从中找到相应的表项； （2）再利用该表项中给出的指向记录的指针值，去访问）再利用该表项中给出的指向记录的指针值，去访问所需记录。所需记录。 （3）要向索引文件中增加一个记录，便须对索引表进行）要向索引文件中增加一个记录，便须对索引表进行修改。修改。3、优点、优点 检索速度快，主要用于对信息处理的及时性要求较高检索速度快，主要用于对信息处理的及时性要求较高的场合。的场合。4、缺点、缺点 存储费用高，因为除了主文件外，还需配置一张索引存储费用高，因为

13、除了主文件外，还需配置一张索引表，且每个记录都有一个索引项。表，且每个记录都有一个索引项。Operating SystemOperating SystemPage 182022-3-1q文件逻辑结构的类型文件逻辑结构的类型q顺序文件顺序文件q索引文件索引文件q索引顺序文件索引顺序文件q直接文件和哈希文件直接文件和哈希文件Operating SystemOperating SystemPage 192022-3-1q索引顺序文件（索引顺序文件（Index Sequential File）是最是最常见的一种逻辑文件组织形式，是常见的一种逻辑文件组织形式，是顺序文件与索顺序文件与索引文件的结合引文件

14、的结合q克服了变长记录文件不便于直接存取的缺点，代克服了变长记录文件不便于直接存取的缺点，代价也不太大价也不太大q将顺序文件中的所有记录分为若干个将顺序文件中的所有记录分为若干个组组，为，为每组每组中的第一个记录中的第一个记录建立索引项，其中含有该记录的建立索引项，其中含有该记录的键值及指向该记录的指针键值及指向该记录的指针Operating SystemOperating SystemPage 202022-3-1键键An QiBao RongChen Lin逻逻辑辑地地址址姓姓 名名An QiAn Kang其其它它属属性性Bao Rong逻逻辑辑文文件件索引顺序文件索引顺序文件 Opera

15、ting SystemOperating SystemPage 212022-3-1Operating SystemOperating SystemPage 222022-3-1q对顺序文件检索对顺序文件检索v若记录数据为若记录数据为N，则检索一条记录时，最好的情况，则检索一条记录时，最好的情况是第一条记录即为所求；最坏的情况是最后一条是第一条记录即为所求；最坏的情况是最后一条记录为所求；平均检索记录为所求；平均检索N/2条记录条记录q对索引文件检索对索引文件检索v可采用折半查找等方法，平均查找可采用折半查找等方法，平均查找 条记录条记录q对索引顺序文件检索对索引顺序文件检索v索引文件与顺序文

16、件的结合索引文件与顺序文件的结合N键值键值150100252012.5Operating SystemOperating SystemPage 232022-3-16.2.4 索引顺序文件索引顺序文件 Operating SystemOperating SystemPage 242022-3-1q文件逻辑结构的类型文件逻辑结构的类型q顺序文件顺序文件q索引文件索引文件q索引顺序文件索引顺序文件q直接文件和哈希文件直接文件和哈希文件Operating SystemOperating SystemPage 252022-3-1q键值转换键值转换(Key to address transformation)v由记录键值到记录物理地址的转换由记录键值到记录物理地址的转换q直接文件直接文件 v根据给定的记录键值，直接获得指定记录的物根据给定的记录键值，直接获得指定记录的物理地址理地址q哈希哈希(Hash)文件文件 v利用哈希函数将记录键值转换为相应记录的地利用哈希函数将记录键值转换为相应记录的地址址Ope