（1）函数申明原型：int receive(char *sender,char *b) （2）功能：从接收线程的消息缓冲队列中取一个从sender发送过来消息并复制到b中。 （3）输入：
sender：发送线程的外部标识符；
b：接收线程内部的接收区，用来存放接收到的消息正文。 （4）输出：接收到的消息的长度 （5）函数实现的算法描述：
该函数要完成的主要工作是：首先检测指定的sender是否存在，如果不存在则直接返回；接着判断当前线程消息队列是否空闲，如果空闲，则调用remov()从消息队列取得sender发给它的消息；读取消息到b中；最后调用insert()将取完消息后的消息缓冲区插入到系统空闲消息缓冲队列中。具体代码请同学们自己完成。
另外，在设计receive()函数时，也可假设接收者能接收任一其他线程发送给它的消息，因此这时候就只需要指出接收区的起始地址信息，然后从自己的消息队列的队首取得一个消息缓冲区，将消息正文复制到接收区中，并释放相应的消息缓冲区即可。
在线程通信时，发送者和接收者都有可能在消息处理以前被撤消。其中，当一接收者等待一个来自某个已终止的线程的消息时，若不采取相应的动作，接收者将无限期阻塞下去。系统一旦发现这种情况，应结束接收动作，从而避免接收者被无限期阻塞。
注意，在示例代码中，在信号量的P、V操作中使用指向信号量的指针（而不是直接使用信号量本身）作为函数参数；另外，所有涉及到队列（包括线程控制块队列和消息缓冲队列）的插入和摘取操作的函数参数中，都没有直接使用队首指针来描述一个队列，而是用了指向队首指针本身的一个双重指针来描述一个队列。这都是因为C语言函数参数的传递是值传递，而不是地址传递的缘故。对队列操作，我们可稍加改进，在每个队列的队首加一个空成员，使队首指针始终指向该空成员，这样不管是插入还是摘取都不会改变队首指针本身，我们就可直接将队首指针作为函数的参数，以增加程序的可读性。同学们可根据这个思路去修改示例代码。
- 31 -
第三章 简单文件系统的实现
3.1 设计目的和内容要求
1. 设计目的
通过具体的文件存储空间的管理、文件的物理结构、目录结构和文件操作的实现，加深对文件系统内部数据结构、功能以及实现过程的理解。
2．内容要求
(1) 在内存中开辟一个虚拟磁盘空间作为文件存储分区，在其上实现一个简单的基于多级目录的单用户单任务系统中的文件系统。在退出该文件系统的使用时，应将该虚拟文件系统以一个Windows 文件的方式保存到磁盘上，以便下次可以再将它恢复到内存的虚拟磁盘空间中。
(2) 文件存储空间的分配可采用显式链接分配或其他的办法。
(3) 空闲磁盘空间的管理可选择位示图或其他的办法。如果采用位示图来管理文件存储空间，并采用显式链接分配方式，那么可以将位示图合并到FAT中。
(4) 文件目录结构采用多级目录结构。为了简单起见，可以不使用索引结点，其中的每个目录项应包含文件名、物理地址、长度等信息，还可以通过目录项实现对文件的读和写的保护。
(5) 要求提供以下操作命令：
? my_format：对文件存储器进行格式化，即按照文件系统的结构对虚拟磁盘空间进行布局，并在其上创建根目录以及用于管理文件存储空间等的数据结构。
? my_mkdir：用于创建子目录。 ? my_rmdir：用于删除子目录。 ? my_ls：用于显示目录中的内容。 ? my_cd：用于更改当前目录。 ? my_create：用于创建文件。 ? my_open：用于打开文件。 ? my_close：用于关闭文件。 ? my_write：用于写文件。 ? my_read：用于读文件。 ? my_rm：用于删除文件。
? my_exitsys：用于退出文件系统。
3．学时安排
授课2学时，上机9学时。 4． 开发平台 C或C++均可。 5．思考
- 32 -
(1) 我们的数据结构中的文件物理地址信息是使用C语言的指针类型、还是整型，为什么？
(2) 如果引入磁盘索引结点，上述实现过程需要作哪些修改？
(3) 如果设计的是一个单用户多任务文件系统，则系统需要进行哪些扩充（尤其要考虑读写指针问题）？如果设计的是一个多用户文件系统，则又要进行哪些扩充？
3.2 预备知识
3.2.1 FAT文件系统介绍
1．概述
FAT文件系统是微软公司在其早期的操作系统MS-DOS及Windows9x中采用的文件系统，它被设计用来管理小容量的磁盘空间。FAT文件系统是以他的文件组织方式——文件分配表（file allocation table，FAT）命名的，文件分配表的每个表项中存放某文件的下一个盘块号，而该文件的起始盘块号则保存在它的文件控制块FCB中。在文件分配表中，一般用FFFF来标识文件的结束；用0000来标识某个逻辑块未被分配，即是空闲块。为了提高文件系统的可靠性，在逻辑磁盘上通常设置两张文件分配表，它们互为备份。此外，文件分配表必须存放在逻辑磁盘上的固定位置，而根目录区通常位于FAT2之后，以便操作系统在启动时能够定位所需的文件，其磁盘布局如图3-1所示：
引导块FAT1FAT2根目录区数据区 图3-1 FAT文件系统磁盘布局
上述磁盘布局中，引导块中主要存放了用于描述分区的各种信息，包括逻辑块的大小、文件分配表的大小及位置、根目录的大小及位置等。除此之外，用于加载操作系统内核的引导程序也存储在引导块中。
FAT文件系统家族又分为FAT12、FAT16、FAT32三种类型，这里的数字表示文件分配表中每个表项（即簇号）所占的位数，即FAT12中每个表项占1.5个字节（12位），FAT16中每个表项占2个字节（16位），FAT32中每个表项占4个字节（32位）。由于FAT文件系统是以簇为单位为文件分配磁盘空间的（一个簇是一组连续的扇区，通常包含2n个扇区），因此，FAT32比FAT12和FAT16支持更多的簇数、更小的簇大小和更大的磁盘容量，从而大大提高磁盘空间的利用率。通常，FAT12适用于小容量磁盘，如软盘；FAT16是MS-DOS的文件系统；FAT32是Windows9x中的主要文件系统，开始支持大容量磁盘。
2．文件控制块FCB
为了正确、方便地操作文件，必须设置相应的数据结构用于存放文件的描述和控制信息，常用的数据结构有文件控制块（简称FCB）和索引节点（简称i节点）。在FAT文件系统中使用文件控制块。文件与文件控制块一一对应，而文件控制块的有序集合就称为文件目录，即一个文件控制块就是一个文件目录项。
虽然不同文件系统的文件控制块的内容和格式不完全相同，但通常都包括以下三类信息：基本信息、存取控制信息和使用信息。
（1）基本信息。包括文件名、用户名、文件类型、文件的物理地址、文件长度、文件的逻辑结构和物理结构等。
（2）存取控制信息。一般分别给出文件主、伙伴用户、一般用户的存取权限。
- 33 -
（3）使用信息。包括文件的建立日期及时间、上次存取文件的日期及时间、当前的使用信息等。
以MS-DOS（使用FAT16文件系统）为例，它的每个文件控制块包括32个字节，其字节分配情况如图3-2所示：
字节8B文件名3B1B10B保留2B2B2B4B扩展名属性时间日期首块号大小 图3-2 MS-DOS的文件控制块 其中属性字段占一个字节，它的每一位用来表示该文件是否具有某种属性，如果某一位的值为1，则表示该文件具有该属性。各位所表示的属性如表3-1所示：
表3-1 文件属性对照表
位 7 6 5 4 3 2 1 0 属性 保留 保留 存档 子目录 卷标 系统文件 隐藏 只读
3．根目录区
FAT12、FAT16的根目录区是固定区域、固定大小的，位于第二个FAT之后，如图3-1所示，且占据若干连续扇区，其中FAT12占14个扇区，一共224个根目录项；而FAT16占32个扇区，最多保存512个目录项，作为系统区的一部分。FAT32的根目录是作为文件处理的，采用与子目录文件相同的管理方式，其位置不是固定的，不过一般情况也是位于第二个FAT之后的，其大小可视需要增加，因此根目录下的文件数目不再受最多512个的限制。
3.2.2 几个C语言库函数介绍
由于我们的文件系统是建立在内存的虚拟磁盘上的，在退出文件系统的时候必须以一个文件的形式保存到磁盘上；而在启动文件系统的时候必须从磁盘上将该文件读入到内存的虚拟磁盘中。下面介绍几个可能会用到的C库函数，在使用这些库函数之前必须包含头文件“stdio.h”。
1．打开文件函数fopen()
（1）格式：FILE *fopen(const char *filename,const char *mode)
（2）功能：按照指定打开方式打开指定文件。 （3）输入参数说明：
filename：待打开的文件名，如果不存在就创建该文件。 mode： 文件打开方式，常用的有：
? \：为读而打开文本文件（不存在则出错）。
? \：为写而打开文本文件（若不存在则创建该文件；反之，则从文件起始位置写,原内容将被覆盖）。
? \：为在文件末尾添加数据而打开文本文件。（若不存在则创建该文件；反之,在原文件末尾追加）。
? \：为读和写而打开文本文件。（读时，从头开始；在写数据时,新数据只覆盖所占的空间，其后不变) 。
? \：首先建立一个新文件，进行写操作，随后可以从头开始读。(若文件存在，原内容将全部消失) 。
? \：功能与\相同；只是在文件末尾添加新的数据后，可以从头开始读。
- 34 -
另外，上述模式字符串中都可以加一个“b”字符，如rb、wb、ab、rb+、wb+、ab+等组合，字符“b”表示fopen() 函数打开的文件为二进制文件，而非纯文字文件。
（4）输出：一个指向FILE类型的指针。
2．关闭文件函数fclose()
（1）格式：int fclose(FILE * stream);
（2）功能：用来关闭先前fopen()打开的一个文件。此动作会让缓冲区内的数据写入文件中，并释放系统所提供的文件资源。
（3）输入参数说明：
stream：指向要关闭文件的指针，它是先前执行fopen()函数的返回值。 （4）输出：若关闭文件成功则返回0；有错误发生时则返回EOF并把错误代码存到errno。
3．读文件函数fread()
（1）格式：size_t fread( void *buffer, size_t size, size_t count, FILE *stream )； （2）功能：读二进制文件到内存。 （3）输入参数说明：
buffer：用于存放输入数据的缓冲区的首地址；
stream：使用fopen()打开的文件的指针，用于指示要读取的文件； size： 每个数据块的字节数； count： 要读入的数据块的个数； size*count：表示要求读取的字节数。 （4）输出：实际读取的数据块的个数。 4．写文件函数fwrite()
（1）格式：size_t fwite(const void *buffer,size_t size,size_t count,FILE *stream)； （2）功能：将数据写到二进制文件中。 （3）输入参数说明：
buffer：用于存放输出数据的缓冲区的首地址；
stream：使用fopen()打开的文件的指针，用于指示要写出的文件； size： 每个数据块的字节数； count： 要写出的数据块的个数； size*count：表示要求写出的字符数。 （4）输出：实际写出的数据块的个数。 5．判断文件结束函数feof ()
（1）格式：int feof(FILE * stream)
（2）功能：用来判断是否已读取到文件末尾。 （3）输入参数说明：
stream：使用fopen()打开的文件的指针，用于指示要判断的文件。 （4）输出：如果已读到文件尾则返回非零值，其他情况返回0。 6．定位文件函数fseek()
（1）格式：int fseek( FILE *stream, long offset, int origin )； （2）功能： 移动文件读写指针在文件中的位置。
- 35 -