This is NACHOS#2

本文最后更新于：2022年7月7日 上午

目前Nachos实现的文件系统存在诸多限制，其中之一是文件大小不能扩展，即无法在已经存在的文件尾部追加数据

该实验的任务就是让你修改Nachos的文件系统，以满足：

  • 文件创建时，其大小可初始化为0
  • 当一个文件写入更多的数据时，其大小可随之增大
  • 要求能够从一个文件的任意位置开始写入数据，即能够正确处理命令行参数-ap -hap -nap

例如，如果一个文件的大小为100字节，当从其偏移量50（第一个字节的偏移量是0）开始写入100个字节后，该文件的大小应该为150字节，如下图所示

文件的扩展

Nachos的文件系统包括以下模块：

  • class Disk //see ../machine
  • class SynchDisk //see ../filesys
  • class BitMap //see ../userprog
  • class FileHeader //see ../filesys
  • class OpenFile //see ../filesys
  • class Directory //see ../filesys
  • class FileSystem //see ../filesys

Nachos文件系统结构

通过该实验，你需要

  • 理解文件系统中文件操作的实现方法，如文件打开、读、写、扩展、定位、关闭等
  • 理解如何管理硬盘空闲块
  • 理解创建文件时，如何为文件分配目录项及文件头（FCB）
  • 理解文件扩展时，如何为要扩展的数据查找并分配空闲块
  • 理解文件扩展后，文件大小是如何记录与保存的
  • 理解文件被删除后，如何回收为其分配的资源，如文件头、目录项、硬盘块等

问题分析

  • nachos [-d f] –ap Unix_filename Nachos_filename
    该命令的功能是将一个UNIX文件（unix_filename）附加到一个Nachos文件（nachos_filename）的后面，目的是用来测试当我们在一个Nachos的文件尾部追加数据后，文件大小是否会增加。
  • nachos [-d f] –hap Unix_filename Nachos_filename
    该命令的功能是从一个Nachos文件（nachos_filename）的中间（文件大小的1/2）位置开始，将一个UNIX文件（unix_filename）写入到该Nachos文件中。如果这个UNIX文件大于Nachos文件的一半，则该目录执行后，新的Nachos文件的大小将增加。
  • nachos [-d f] –nap Nachos_filename1 Nachos_filename1
    该命令的功能是将一个Nachos文件（nachos_filename1）附加到一个Nachos文件（nachos_filename2）的后面，目的是用来测试当我们在一个Nachos的文件尾部写入数据时，文件大小是否会增加。

执行上述命令时会出现如下错误

在./lab5/main.cc中查看对命令行参数-ap -hap -nap的处理过程

发现-ap -hap与函数Append(..)有关，-nap与函数 NAppend(..)有关

跳转阅读./lab5/fstest.cc中的这两个函数，找到报错行149

发现是由于写数据结果result和已读数据amountRead不一致导致的报错

找到result的产生位置，是OpenFile::Write(..)的返回结果

进入OpenFile::Write(..)函数内部查看，result实则是OpenFile::WirteAt(..)函数的返回结果，该函数试图从当前文件头对应的文件的指定位置position开始写入缓冲区from中numBytes大小的内容

分析该函数的实现：

  • 首先从当前文件的文件头中获取文件长度fileLength

  • 约束1：如果要写入的内容不存在numBytes<=0或是开始写入的位置为文件尾或超出了文件尾position>=fileLength，则直接退出

  • 约束2：如果要写入的内容过多超出了原文件的长度(position+numBytes)>fileLength，超出部分也不再写入

这两个if约束导致目前Nachos实现的文件系统不能对文件的大小进行扩展，所以需要对其进行修改：

  • 修改上面的两个约束，使Nachos文件大小可以扩展
  • 如果文件的最后一个扇区能够容纳扩展的数据，则要修改文件头中的文件长度，再将文件头写回硬盘
  • 如果文件的最后一个扇区不能够容纳扩展的数据，则要为这些数据分配新的扇区，那么就需要修改硬盘的位图和文件头中的文件长度、分配的扇区数、分配的扇区号，再将修改的内容写回硬盘

而在Append(..)与 NAppend(..)中将文件头写回硬盘的操作OpenFile::WriteBack()未被实现，需要我们补充

因此文件扩展操作需要涉及的内容有：

  • 修改OpenFile::WriteAt()，允许从文件尾部开始写数据，并可为要写入的数据分配新的扇区

  • 修改FileSystem类，添加空闲块位示图文件的硬盘读写操作

  • 修改OpenFile::OpenFile()及OpenFile::WriteBack()，实现文件头的硬盘读写

  • 修改FileHeader::Allocate()，为添加的数据分配硬盘块（扇区）

  • 修改Append()和NAppend()，使下次的写指针指向新写入数据的尾部，并在扩展操作结束后调用OpenFile::WriteBack()将修改后的文件头写入硬盘

实现

修改OpenFile::WriteAt()

修改两个约束

1
2
3
4
5
6
7
8
9
10
if((numBytes <= 0) || (position > fileLength))
    return -1; 
if((position + numBytes) > fileLength){
    int incrementBytes = (position + numBytes) - fileLength;
    BitMap* freeBitMap = fileSystem->getBitMap(); // TODO 
    bool hdrRet = hdr->Allocate(freeBitMap, fileLength, incrementBytes); // TODO
    if(!hdrRet)
        return -1;
    fileSystem->setBitMap(freeBitMap); //TODO
}

对于约束1，如果要写入的内容不存在numBytes<=0或是开始写入的位置超出了文件尾position>fileLength，则直接返回错误参数-1。这里保留了开始写入的位置为文件尾position==fileLength，说明文件需要扩展。

对于约束2，保留超出部分的数据incrementBytes；获得当前硬盘的位图freeBitMap；检查是否有足够的空间分配给超出部分的数据，返回结果hdrRet；如果没有足够空间，则返回错误参数-1；如果有足够的空间，则将更新后的位图写回硬盘

修改FileSystem类

添加setBitMap()和getBitMap()

在类FileSystem的构造函数中，维护了一直处于打开状态的位图文件句柄OpenFile* freeMapFile，我们可以直接使用它们实现对DISK的位图文件的读写操作

1
2
3
4
5
6
7
8
9
BitMap* FileSystem::getBitMap(){
    BitMap* freeBitMap = new BitMap(NumSectors);
    freeBitMap->FetchFrom(freeMapFile);
    return freeBitMap;
}

void FileSystem::setBitMap(BitMap* freeMap){
    freeMap->WriteBack(freeMapFile);
}

getBitMap()调用了../userprog/bitmap.cc中BitMap类的FetchFrom(OpenFile *)

setBitMap()调用了BitMap类的WriteBack(OpenFile *)完成

修改OpenFile::OpenFile()及OpenFile::WriteBack()

分析OpenFile类的构造函数

维护了一个FileHeader类对象hdr，从硬盘的指定扇区sector中读取了该文件的文件头，并将读写指针seekPosition设置为开始位置0

考虑到类FileHeader中有函数WriteBack(int sector)

为了将文件头写回硬盘，我们可以调用这个函数，实现hdr->WriteBack(sector)

而该实现需要获得该文件头所在的扇区号，所以在OpenFile类中定义一个私有变量hdrSector并维护

1
2
3
4
5
6
7
OpenFile::OpenFile(int sector)
{ 
    hdr = new FileHeader;
    hdr->FetchFrom(sector);
    seekPosition = 0;
    hdrSector = sector; // ADD
}

那么，进而可以实现OpenFile::WriteBack()

1
2
3
void OpenFile::WriteBack(){
    hdr->WriteBack(hdrSector);
}

修改FileHeader::Allocate()

重载函数FileHeader::Allocate(BitMap* freeMap, int fileSize, int incrementBytes)，以根据要扩展的数据大小incrementBytes判断是否需要分配新的扇区块来返回结果，并更新文件头三元组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
bool FileHeader::Allocate(BitMap* freeMap, int fileSize, int incrementBytes){
    if(numSectors > NumDirect)
        return false;
    if((fileSize == 0) && (incrementBytes > 0)){
        if(freeMap->NumClear() < 1)
            return false;
        dataSectors[0] = freeMap->Find();
        numSectors = 1;
        numBytes = 0;
    }
    numBytes = fileSize;
    int offset = numBytes % SectorSize;
    int newSectorBytes = incrementBytes - (SectorSize - (offset + 1));
    if(newSectorBytes <= 0){
        numBytes += incrementBytes;
        return true;
    }
    int moreSectors = divRoundUp(newSectorBytes, SectorSize);
    if(numSectors + moreSectors > NumDirect)
        return false;
    if(freeMap->NumClear() < moreSectors)
        return false;
    for(int i=numSectors; i<numSectors+moreSectors; i++)
        dataSectors[i] = freeMap->Find();
    numBytes += incrementBytes;
    numSectors += moreSectors;
    return true;
}
  • 如果当前文件已分配的扇区数大于限制，则退出不予分配
  • 如果当前文件是空文件且要写入数据，那么首先要为该文件分配一个空闲扇区，并更新文件头信息
  • 如果当前文件最后一个扇区的剩余空间足以容纳要写入的incrementBytes个字节，就不需要为写入操作分配新的扇区，在最后一个扇区中写入数据即可。但要修改文件头中文件大小信息
  • 如果当前文件最后一个扇区的剩余空间无法容纳要写入的incrementBytes个字节，就需要为写入操作分配新的扇区，通过计算得出需要分配的扇区数moreSectors
    • 如果扩展后文件过大超出限制，则退出不予分配
    • 如果硬盘中没有足够的空闲扇区，则退出无法分配
    • 如果符合条件可以分配，则要更新文件头信息

修改Append()和NAppend()

Append()和NAppend()调用了修改后的OpenFile::WriteAt()，OpenFile::WriteAt()调用了重载的FileHeader::Allocate()，FileHeader::Allocate()根据每次写入的数据修改文件头三元组，但一直在内存中，尚未写回硬盘，因此在Append()和NAppend()的写操作结束后，应该调用OpenFile::WriteBack()将修改后的文件头写回到硬盘的相应的扇区中

1
openFile->WriteBack();

测试

  • 为容易识别硬盘DISK信息的改变，修改../file/test/下的文件内容

  • nachos –f 在硬盘DISK上初始化一个Nachos文件系统

    nachos –D

    考察Nachos在硬盘DISK上初始化的文件系统情况：

    • 空闲块位图的头文件（0号扇区）
    • 空闲块位图文件数据块（2号扇区）
    • 目录表头文件（1号扇区）
    • 目录表数据块（3、4号扇区)

  • nachos –cp test/small small复制test目录下的UNIX文件small到DISK中

    nachos –D

    查看硬盘DISK中的文件信息：

    • 空闲块位图的头文件（0号扇区）

    • 空闲块位图文件数据块（2号扇区）

    • 目录表头文件（1号扇区）

    • 目录表数据块（3、4号扇区）

    • 文件small的头文件（5号扇区）

    • 文件small的数据块（6号扇区）

  • nachos –ap test/small small 测试给一个已存在的文件追加数据

    nachos –D 查看硬盘DISK中的文件信息

    系统成功将small文件的内容扩展到small文件原扇区的剩余空间中

  • nachos –ap test/big small 测试为文件分配新扇区的功能

    nachos –D 以及 hexdump -C DISK查看硬盘DISK中的文件信息

    系统将samll文件原扇区的剩余空间写满后，为small分配新的扇区块，写入big的内容

  • nachos –ap test/medium medium，测试给一个空文件追加数据的功能

    nachos –D 查看硬盘DISK中的文件信息

    如果DISK中不存在文件，将会自动创建一个空的文件，然后将源文件内容追加到Nachos空文件中

  • nachos –ap test/big small 测试Nachos为small新分配的扇区块的位置

  • nachos –D查看硬盘DISK中的文件信息

    在执行它之前，由于small的数据块之后的扇区是medium文件的文件头及其数据块，因此，系统会在medium文件之后为small分配新的扇区10

    Nachos的文件系统采取索引分配文件数据块的方式，文件的数据块在硬盘上可以是非连续存放的，这使文件的扩展易于实现

  • nachos –hap test/medium small 测试从small的中间写入文件的功能

    nachos –D 查看硬盘DISK中的文件信息

    系统成功在small的中间写入文件test/medium的内容

  • nachos –nap medium small 测试将一个nachos文件附加到另一个nachos文件的功能

    nachos –D 查看硬盘DISK中的文件信息

    系统成功将nachos文件medium附加到nachos文件small的尾部

  • nachos –r small 测试文件删除功能

    nachos –D 及hexdump –C DISK查看硬盘DISK中的文件信息

    原来的small文件相关信息都消失不见，其他文件信息保持不变

    位示图数据块：值变为0x31f，即1100011111，表示5号、6号、7号扇区空闲，即为原small文件的文件头和数据部分占用的扇区

    目录表数据块：inUse值变为0，表示为原small文件分配的目录项空闲，而其他内容保持不变

    small的文件头以及small文件内容：均被保留

  • 测试nachos –l（列目录）命令

  • 测试nachos –p （显示文件内容）命令

  • 反复运行nachos –ap test/big small 测试nachos文件系统中对一个文件长度的限制

    nachos –D 查看硬盘DISK中的文件信息

    一个文件最多可分配30个扇区，每个扇区128字节，因此理论上文件最大限制为3840B

    但测试中small文件大小为3832B，因为写文件的过程中不是逐字节写入的，而是使用了一个10B大小的缓冲区。big文件大小为99B，所以在38次追加big文件后，small文件达到3762B，而在第39次追加big文件时，每10B写入small文件，当写入70B后达到3832B，这之后再想写入10B则会超过限额3840B，则不进行该次写入操作，最终small文件的大小即为3832B

  • 反复运行nachos –ap 在硬盘DISK上新建文件，测试nachos文件系统中最多可创建多少个文件

    报错之后共有10个文件，因为nachos采用一级目录，最多有10个目录项，因此最多可存储10个文件

  • 测试创建一个大小为0的文件

    将空文件test/empty复制到硬盘中，使用nachos -D查看DISK中的文件信息，发现empty文件的大小为0，没有为它分配数据块

SDU OperatingSystem

本文作者: 31
本文链接: http://uuunni.github.io/2022/03/30/This-is-NACHOS-2/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！