Publié il y a Mis à jour il y a Operating Systeman hour de lecture (Environ 11652 mots)0 visites

Nachos Lab04 文件系统

文件系统的基本操作

Exercise 1 源代码阅读

阅读Nachos源代码中与文件系统相关的代码，理解Nachos文件系统的工作原理。

code/filesys/filesys.h和code/filesys/filesys.cc

code/filesys/filehdr.h和code/filesys/filehdr.cc

code/filesys/directory.h和code/filesys/directory.cc

code/filesys/openfile.h和code/filesys/openfile.cc

code/userprog/bitmap.h和code/userprog/bitmap.cc

  • code/filesys/filesys.h和code/filesys/filesys.cc：这里是文件系统的实现，文件系统是存储在磁盘上的，按目录组织的一组文件，提供了根据文件名来创建、打开、删除操作。文件系统包含两个重要数据结构空闲空间位图以及目录。而对于文件系统上的每个文件均包含文件头、数据块数量和目录项。

    该文件系统存在两个实现版本“STUB”和“REAL”。“STUB”版本只是将文件系统定义为运行在Nachos中的对本机Unix文件系统的操作；“REAL”版本是在磁盘模拟器上构建的文件系统，其利用本机Unix文件系统来模拟磁盘（DISK）。

  • code/filesys/filehdr.h和code/filesys/filehdr.cc：这里是关于文件头结构的定义和实现。一个文件头部描述了如何在磁盘上获取文件数据，以及长度，所有者等等信息。

  • code/filesys/directory.h和code/filesys/directory.cc：这里是目录和目录项的定义和实现。目录是一个表用于记录<文件名，扇区号>数据对，提供目录中的文件名及其文件头所在磁盘位置的信息。

  • code/filesys/openfile.h和code/filesys/openfile.cc ：这里是文件结构的定义和实现。提供了打开，关闭，读写等文件操作方法。此处同样提供了两种实现版本“STUB”和“REAL”。

  • code/userprog/bitmap.h和code/userprog/bitmap.cc ：这两个文件用于实现一个位图结构。该位图支持对某个一个位进行设置（Mark）、清除（Clear）和测试是否设置（Test），以及从位图中查找一个Clear值（Find）和Clear所有的值（NumClear）。除此之外，还支持持久化存储，即将位图保存到文件（WriteBack）以及从文件还原位图数据（FetchFrom）。

Exercise 2 扩展文件属性

增加文件描述信息，如“类型”、“创建时间”、“上次访问时间”、“上次修改时间”、“路径”等等。尝试突破文件名长度的限制。

思路

这里需要注意的是，从文件系统的Create方法以及文件头的WriteBack方法中可以看到，初始的文件头仅用了一个磁盘块存储，也就是说文件头FileHeader的大小不能超过一个磁盘块大小（128 Bytes）。

文件磁盘块数量。在filehdr.h中设置了一个宏NumDirect用于记录一个文件头部能够存储的直接磁盘块数量。FileHeader仅放在一个磁盘块中，并且记录两个整数numBytes和numSectors，剩余空间均为该文件头可记录的磁盘块。如果修改了FileHeader的数据结构，如增加描述信息，则需要修改该宏避免数据溢出。对于目录文件也存在DirectoryEntry数据结构大小影响目录条目存储上限的问题，但由于预设数量仅为10（定义于code/filesys/filesys.cc文件中的#define NumDirEntries 10）。

1
#define NumDirect 	((SectorSize - 2 * sizeof(int)) / sizeof(int))

突破文件名长度。如果仍是采取文件名定长的方式，仅修改FileNameMaxLen该宏的大小，则不影响。但是如果换成了不定长的文件名，则需要对下列函数中的strncmp字符串比较函数（定长比较）修改为strcmp函数（不定长比较）。可能存在这一问题的还有Directory::Add中的strncpy函数（是否需要修改看不定长文件名的实现方式）。

不定长的文件名存在一个较为麻烦的问题：将变量（如目录）写回磁盘的时候，写回的是文件名的指针，而不是字符串。这也就意味着，当Nachos执行结束之后，再次执行，所有的文件名会失效。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int
Directory::FindIndex(char *name)
{
    for (int i = 0; i < tableSize; i++)
        if (table[i].inUse && !strncmp(table[i].name, name, FileNameMaxLen))
       return i;
    return -1;    // name not in directory
}

bool
Directory::Add(char *name, int newSector)
{ 
    if (FindIndex(name) != -1)
	return FALSE;

    for (int i = 0; i < tableSize; i++)
        if (!table[i].inUse) {
            table[i].inUse = TRUE;
            strncpy(table[i].name, name, FileNameMaxLen); 
            table[i].sector = newSector;
        return TRUE;
	}
    return FALSE;	// no space.  Fix when we have extensible files.
}

测试函数。由于此时还未实现动态文件大小，因此fstest中的测试函数中利用文件系统创建文件时，不能将初始大小设为0。否则会出现无法写入，或无法读取的情况。

1
2
3
4
5
6
7
8
9
10
static void 
FileWrite()
{
...
    if (!fileSystem->Create(FileName, 0)) {
      printf("Perf test: can't create %s\n", FileName);
      return;
    }
...
}

实现

结合Exercise 1中阅读的信息可以得知，文件的描述信息可以考虑在目录项或者文件头中记录。这里为了后续实现的方便，描述信息部分放在FileHeader文件头中，另一部分放在目录项中。

因此在filehdr.h文件中文件头FileHeader类中添加文件描述信息的私有成员crtTime、lastAccTime、lastModTime，以及相应的set和get方法。而路径则通过在文件中记录父文件夹文件头所处的磁盘块号（parDirHeaderSector）来进行反向查询。

而对于directory.h文件中的目录条目DirectoryEntry则新增文件类型和路径两个数据。文件类型目前仅分为普通文件（F_NORMAL）和目录文件（F_DIRECTORY）两种。

关于文件名长度限制。可以发现，仅在目录文件的目录项结构中出现了关于文件名的记录，并且使用了FileNameMaxLen常量来限制最大文件长度。因此可以通过将固定长度的字符数组修改为指针。

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/*
 * code/filesys/filehdr.h 
 */

class FileHeader {
  public:
...
    int getCrtTime() {return crtTime;}
    void setCrtTime(int ct) {crtTime = ct;}

    int getLastAccTime() {return lastAccTime;}
    void setLastAccTime(int lat) {lastAccTime = lat;}

    int getLastModTime() {return lastModTime;}
    void setLastModTime(int lmt) {lastModTime = lmt;}

    int getParDirHeaderSector() {return parDirHeaderSector;}
    void setParDirHeaderSector(int pds) {parDirHeaderSector = pds;}
  private:
...
    int crtTime;        // 创建时间
    int lastAccTime;    // 最后访问时间
    int lastModTime;    // 最后修改时间
    int parDirHeaderSector;  // 父文件夹文件头所处的磁盘块号
};

/*
 * code/filesys/directory.h
 */
enum FileType {
    F_NORMAL,    // 普通文件
    F_DIRECTORY    // 目录文件
};

class DirectoryEntry {
  public:
    bool inUse;				// Is this directory entry in use?
    int sector;				// Location on disk to find the 
					//   FileHeader for this file 
    
    char * name;
    FileType fileType;  // 文件类型
};

然后在FileHeader的初始化函数Allocate中初始化文件的描述信息。其中文件创建时间crtTime设置为当前的系统时间，并且分别在FetchFrom中更新最近访问时间，和WriteBack中更新最近修改时间。而parDirHeaderSector的初始化则是由FileSystem类来负责，所以此处为了避免出错，在创建的时候让其具有初值-1。

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
/*
 * code/filesys/filehdr.cc
 */
bool
FileHeader::Allocate(BitMap *freeMap, int fileSize)
{ 
...
    crtTime = stats->totalTicks;
    lastModTime = crtTime;
    lastAccTime = crtTime;
    parDirHeaderSector = -1;
...
}

void
FileHeader::FetchFrom(int sector)
{
    synchDisk->ReadSector(sector, (char *)this);
    lastAccTime = stats->totalTicks;
}
void
FileHeader::WriteBack(int sector)
{
    synchDisk->WriteSector(sector, (char *)this);
    lastModTime = stats->totalTicks;
}

如果在Directory中对parDirHeaderSector初始化，则需要在Directory类的Add方法中从文件头所在的磁盘块中读取文件头信息，然后修改parDirHeaderSector值，再将其写回磁盘。由于经历了一次磁盘读写，这样做的效率会比较低。所以考虑在文件创建的时候，同时对路径信息初始化。

因此对FileSystem类中的Create方法进行修改，当文件创建成功且文件头还未写回磁盘时，向文件头设置父文件夹磁盘块号。此时还未实现多级目录，所以默认设为DirectorySector宏，该宏记录了根目录的文件头。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
 * code/filesys/filesys.cc
 */
bool
FileSystem::Create(char *name, int initialSize)
{
...
       else { 
          success = TRUE;      
          hdr->setParDirHeaderSector(DirectorySector);
      // everthing worked, flush all changes back to disk
              hdr->WriteBack(sector);       
              directory->WriteBack(directoryFile);
              freeMap->WriteBack(freeMapFile);
       }
...
}

目录条目DirectoryEntry中新增的信息也在Directory中对其初始化。重载Directory的Add方法，新增传入文件类型，用于对文件类型进行初始化。在Add中对于不定长的文件名的处理方式就是通过new来动态申请一个空间来存放文件名。因为文件名是动态的，因此在移除文件的时候，也需要在Remove中使用delete进行删除。

为了辅助路径功能的实现，添加了一个FindName方法，用于根据文件头的磁盘块号获取文件名。

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/*
 * code/filesys/directory.h
 */
class Directory {
...
    bool Add(char *name, int newSector, FileType fileType);
    char * FindName(int fSector);  // 根据磁盘块号获取文件名
...
}

/*
 * code/filesys/directory.cc
 */
bool
Directory::Add(char *name, int newSector, FileType fileType) {
    if (FindIndex(name) != -1)
        return FALSE;

    for (int i = 0; i < tableSize; i++)
        if (!table[i].inUse) {
            table[i].inUse = TRUE;
            
            int lens = strlen(name);
            table[i].name = new char [lens + 1];
            strncpy(table[i].name, name, lens);
            table[i].name[lens] = '\0';
            
            table[i].sector = newSector;
            table[i].fileType = fileType;
            return TRUE;
        }
    return FALSE;
}

bool
Directory::Remove(char *name)
{ 
    int i = FindIndex(name);

    if (i == -1)
	return FALSE; 		// name not in directory
    table[i].inUse = FALSE;
    delete table[i].name;
    return TRUE;	
}

char * Directory::FindName(int fSector) {
    for (int i = 0; i < tableSize; i++) {
        if (table[i].inUse && table[i].sector == fSector) {
            return table[i].name;
        }
    }
}

然后在code/filesys/filesys.h中新增一个PrintPath函数。通过提供当前的文件的文件名（name）以及其所属文件夹的文件头磁盘块号（parDirHeaderSector），来进行反向查询文件路径。

其反向查询的思路为，以当前文件的文件夹为起点，向上获取目录的父目录的信息，然后根据这个目录的父目录去获取当前目录的目录名。查询过程如上图所示。此处省略了路径字符串的反向处理，因此路径的显示与实际相反。即Unix下/usr/a，而Nachos下a/usr/。

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/*
 * code/filesys/filesys.h
 */
class FileSystem {
  public:
...
    void PrintPath(int parDirHeaderSector, char * name);
  private:
...
};

/*
 * code/filesys/filesys.cc
 */
void FileSystem::PrintPath(int sector, char * name) {
    FileHeader *hdr;
    OpenFile * dirFile;
    Directory * directory;
    int parSector;

    printf("%s/", name);
    do {
        if (sector == -1) sector = DirectorySector;
        hdr = new FileHeader;
        hdr->FetchFrom(sector);

        parSector = hdr->getParDirHeaderSector();

        if (parSector != -1) {
            dirFile = new OpenFile(parSector);  // hdr表示当前目录，其记录的是目录的父目录
            directory = new Directory(NumDirEntries);
            directory->FetchFrom(dirFile);
            name = directory->FindName(sector);

            printf("%s/", name);

            delete dirFile;
            delete directory;
        }

        sector = parSector;
        delete hdr;
    } while (sector != DirectorySector && sector != -1);
}

做完上述修改之后，为了避免出现问题，对源代码进行一定的修改。由于FileHeader新增了数据成员，大小发生了变化，因此修改code/filesys/filehdr.h文件中的NumDirect宏，重新计算新的值。

另外，由于将文件名换成了指针，变成了不定长，所以修改code/filesys/directory.cc文件中的FindIndex函数中调用的定长strncmp字符串比较函数替换为支持不定长比较的strcmp函数。以及将同文件中的Add函数中的strncpy修改为指针赋值（字符串常量存储在静态存储区，因此函数结束时空间不会被回收）。

测试

然后此时修改测试函数，将文件初始大小设为FileSize。

1
2
3
4
5
6
7
8
9
10
/*
 * code/filesys/fstest.cc
 */
static void 
FileWrite()
{
...
    if (!fileSystem->Create(FileName, FileSize)) {
...
}

为方便查看效果，在code/filesys/filehdr.h的FileHeader中新增PrintFileDesc方法，用于打印文件头内存储的信息，并在测试函数PerformanceTest（位于code/filesys/fstest.cc）中执行的读写操作成功时调用。

1
2
3
4
5
6
7
void FileHeader::PrintFileDesc(char * name) {
    printf("File stat contents in FileHeader. \n");
    printf("CreateTime %d, Last Access Time %d, Last Modify Time %d\n",
           crtTime, lastAccTime, lastModTime);
    fileSystem->PrintPath(parDirHeaderSector, name);
    printf("\n");
}

执行结果如下：

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
root@02487b68b87e:/nachos/nachos-3.4/code/filesys# ./nachos -t
Starting file system performance test:
Ticks: total 1130, idle 1000, system 130, user 0
Disk I/O: reads 2, writes 0
Console I/O: reads 0, writes 0
Paging: faults 0
Network I/O: packets received 0, sent 0
Sequential write of 50 byte file, in 10 byte chunks
Write numBytes -> 10
File stat contents in FileHeader. 
CreateTime 3150, Last Access Time 67210, Last Modify Time 3150
TestFile/
Write numBytes -> 10
File stat contents in FileHeader. 
CreateTime 3150, Last Access Time 67210, Last Modify Time 3150
TestFile/
Write numBytes -> 10
File stat contents in FileHeader. 
CreateTime 3150, Last Access Time 67210, Last Modify Time 3150
TestFile/
Write numBytes -> 10
File stat contents in FileHeader. 
CreateTime 3150, Last Access Time 67210, Last Modify Time 3150
TestFile/
Write numBytes -> 10
File stat contents in FileHeader. 
CreateTime 3150, Last Access Time 67210, Last Modify Time 3150
TestFile/
Sequential read of 50 byte file, in 10 byte chunks
Read numBytes -> 10
File stat contents in FileHeader. 
CreateTime 3150, Last Access Time 149770, Last Modify Time 3150
TestFile/
Read numBytes -> 10
File stat contents in FileHeader. 
CreateTime 3150, Last Access Time 149770, Last Modify Time 3150
TestFile/
Read numBytes -> 10
File stat contents in FileHeader. 
CreateTime 3150, Last Access Time 149770, Last Modify Time 3150
TestFile/
Read numBytes -> 10
File stat contents in FileHeader. 
CreateTime 3150, Last Access Time 149770, Last Modify Time 3150
TestFile/
Read numBytes -> 10
File stat contents in FileHeader. 
CreateTime 3150, Last Access Time 149770, Last Modify Time 3150
TestFile/
Ticks: total 194530, idle 191710, system 2820, user 0
Disk I/O: reads 37, writes 12
Console I/O: reads 0, writes 0
Paging: faults 0
Network I/O: packets received 0, sent 0
No threads ready or runnable, and no pending interrupts.
Assuming the program completed.
Machine halting!

Ticks: total 194540, idle 191720, system 2820, user 0
Disk I/O: reads 37, writes 12
Console I/O: reads 0, writes 0
Paging: faults 0
Network I/O: packets received 0, sent 0

Cleaning up...

Exercise 3 扩展文件长度

改直接索引为间接索引，以突破文件长度不能超过4KB的限制。

思路

将部分直接索引块替换成多级索引块，为方便实现可以仅考虑实现一级索引。一张索引表用一个磁盘块存储，因此需要有一个索引表结构处理该磁盘块上的数据。

然后分别对涉及文件大小的三个函数FileHeader::Allocate、FileHeader::Deallocate、FileHeader::ByteToSector进行处理以适应新的文件数据块索引方式。

实现

拓展文件长度的方式则是参照Unix文件系统的方式，在文件头中注册一定数量的直接索引，以及一部分的间接索引块。这次为了实现方便，仅使用一级索引和直接索引。

首先在code/filesys/filehdr.h中添加一些宏，添加宏的主要用途就是定义一级索引表的数量，然后修改直接索引宏的数量计算公式。此处分配了7个磁盘块指针用于存储一级索引表，剩余的20个指针则全部用于直接索引。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*
 * code/filesys/filehdr.h
 */
// 索引表条目数，其中扇区号用整数存储，此时的值为32
#define NumTableEntry (SectorSize / sizeof(int))  
// 一级索引表数量
#define NumTable_LV1 7 
// 一级索引表最大存储大小
#define MaxTableSize_LV1 (NumTable_LV1 * NumTableEntry * SectorSize) 
// 直接索引块数量，此时的值为20
#define NumDirect  ((SectorSize - 5 * sizeof(int)) / sizeof(int) - NumTable_LV1)  
#define MaxFileSize 	(NumDirect * SectorSize + MaxTableSize_LV1 * NumTable_LV1)

class FileHeader {
...
  private:
...
    int dataSectors[NumDirect];		// Disk sector numbers for each data 
					// block in the file
    int dataSectors_LV1[NumTable_LV1];
...
};

紧接着，为了方便处理间接索引表，创建了一个数据结构IndexTable。其进包含两个功能，即从磁盘块中读取索引表，以及将索引表写回磁盘块。而索引表的大小（即条目数）则是来自于上面定义的宏常量NumTableEntry。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class IndexTable {
public:
    void FetchFrom(int sectorNumber);  // Initialize file header from disk
    void WriteBack(int sectorNumber);  // Write modifications to file header
    //  back to disk

    int dataSectors[NumTableEntry];
};

void IndexTable::FetchFrom(int sectorNumber) {
    synchDisk->ReadSector(sector, (char *)this);
}

void IndexTable::WriteBack(int sectorNumber) {
    synchDisk->WriteSector(sector, (char *)this);
}

然后修改FileHeader的Allocate方法以处理多级索引的磁盘块分配方式。分配成功的前提是文件大小不超过可分配的最大大小（即小于MaxFileSize）。

其实现方式，则是先判断文件所需的空间是否超过直接索引的最大大小，如果没有，则按照原先的方式处理。如果超出了，则需要进一步判断，是否有空间去存储一级索引表。

当上述条件全部满足时：

  1. 先分配满全部的直接索引
  2. 超出部分则先分配一个磁盘空间给一级索引表，然后创建一级索引表结构indexTable，在索引表内填写数据之后写回磁盘
  3. 重复步骤2直至文件所需的大小
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/*
 * code/filesys/filehdr.cc
 */
bool
FileHeader::Allocate(BitMap *freeMap, int fileSize)
{ 
    // 超出文件最大大小
    if (fileSize > MaxFileSize)
        return FALSE;
  
    numBytes = fileSize;
    numSectors  = divRoundUp(fileSize, SectorSize);

   if (numSectors <= NumDirect) {
        if (freeMap->NumClear() < numSectors)
            return FALSE;     // not enough space

        for (int i = 0; i < numSectors; i++)
            dataSectors[i] = freeMap->Find();
   } else {
       int restNeed = numSectors - NumDirect;
       // 计算还需要多少个一级索引
       int numSectors_LV1 = divRoundUp(restNeed, NumTableEntry);
       // 一级索引表也需要占用磁盘块，因此还需要考虑索引表能否存储的下
       if (freeMap->NumClear() < numSectors + numSectors_LV1)
            return FALSE;


       // 直接索引分配
        for (int i = 0; i < NumDirect; i++)
            dataSectors[i] = freeMap->Find();
        // 一级索引分配
        for (int i = 0; i < numSectors_LV1; i++) {
            dataSectors_LV1[i] = freeMap->Find();

            IndexTable * indexTable = new IndexTable;

            // i * NumTableEntry + j代表已在一级索引表中记录的磁盘块总数
            for (int j = 0; j < NumTableEntry && (i * NumTableEntry + j) < restNeed; j++) {
                indexTable->dataSectors[j] = freeMap->Find();
            }
            // 将索引表写回磁盘
            indexTable->WriteBack(dataSectors_LV1[i]);
            delete indexTable;
        }

   }

    crtTime = stats->totalTicks;
    lastModTime = crtTime;
    lastAccTime = crtTime;
    parDirHeaderSector = -1;

    return TRUE;
}

相应的，空间回收函数Deallocate也要做相应的改动。其具体实现与Allocate相反，因此不做赘述。

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
29
30
31
32
33
34
35
36
37
38
/*
 * code/filesys/filehdr.cc
 */
void 
FileHeader::Deallocate(BitMap *freeMap)
{
    if (numSectors <= NumDirect) {
        for (int i = 0; i < numSectors; i++) {
            ASSERT(freeMap->Test((int) dataSectors[i]));  // ought to be marked!
            freeMap->Clear((int) dataSectors[i]);
        }
    } else {
        for (int i = 0; i < NumDirect; i++) {
            ASSERT(freeMap->Test((int) dataSectors[i]));  // ought to be marked!
            freeMap->Clear((int) dataSectors[i]);
        }

        int restNeed = numSectors - NumDirect;
        int numSectors_LV1 = divRoundUp(restNeed, NumTableEntry);

        for (int i = 0; i < numSectors_LV1; i++) {

            IndexTable * indexTable = new IndexTable;
            indexTable->FetchFrom(dataSectors_LV1[i]);

            // i * NumTableEntry + j代表已在一级索引表中记录的磁盘块总数
            for (int j = 0; j < NumTableEntry && (i * NumTableEntry + j) < restNeed; j++) {
                ASSERT(freeMap->Test((int) (indexTable->dataSectors[j])));  // ought to be marked!
                freeMap->Clear((int) (indexTable->dataSectors[j]));
            }
            delete indexTable;

            // 回收索引表的磁盘块
            ASSERT(freeMap->Test((int) dataSectors_LV1[i]));  // ought to be marked!
            freeMap->Clear((int) dataSectors_LV1[i]);
        }
    }
}

最后还有一处重要的改动，就是对文本内字节偏移量与所属的磁盘块之间的转换函数ByteToSector的修改。其实现思路在于，如果是直接索引块，则直接返回。如果位于一级索引中，则先判断属于哪一个一级索引表（结果存储在sector_LV1中），然后从磁盘中读取该索引表，并进一步判断属于该索引表的哪个磁盘块，最终结果存储在finSector中，并返回finSector。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*
 * code/filesys/filehdr.cc
 */
int
FileHeader::ByteToSector(int offset)
{
    if (offset < NumDirect * SectorSize) {
        return(dataSectors[offset / SectorSize]);
    } else {
        offset -= NumDirect * SectorSize;

        int sector_LV1 = offset / MaxTableSize_LV1;
        offset = offset % MaxTableSize_LV1;

        IndexTable * indexTable = new IndexTable;
        indexTable->FetchFrom(dataSectors_LV1[sector_LV1]);
        int finSector = indexTable->dataSectors[offset / SectorSize];
        delete indexTable;

        return finSector;
    }
}

测试

修改code/filesys/fstest.cc中的FileSize宏，将创建的文件大小设为超出直接块能存储的最大大小（$20 \times 128 = 2560 Bytes$），因此设为5000字节，其中ContentSize的值为10字节。

1
2
3
4
5
6
7
8
9
10
11
12
/*
 * code/filesys/fstest.cc
 */
#define FileSize 	((int)(ContentSize * 500))

static void 
FileWrite()
{
...
    if (!fileSystem->Create(FileName, FileSize)) {
...
}

部分测试结果如下，可以看到文件正常完成读写操作。

Exercise 4 实现多级目录

思路

考虑到文件系统创建文件是通过传入文件名的方式来创建文件的，也就是说默认创建在根目录中。又考虑到在Exercise 2中的路径实现，为了不大量修改之前路径的实现代码，考虑修改文件系统的实现。也就是说，在文件系统中传入的name代表的含义不再是单纯的文件名，而是文件的绝对路径（或相对路径）。

实现

由于计划将文件系统中的name变量定义为绝对路径（DirectoryEntry中的name仍仅代表文件名，而非绝对路径），因此需要实现一个路径解析函数PathParse。该函数对传入的绝对路径name进行解析，返回一个字符串数组以及数组长度nums。例如传入name:="/root/123"，则之行结束以后获得字符串数组{[0] => "root", [1] => "123"}，且nums为2。

可以注意到，这里的路径与之前Exercise 2执行结果中打印的路径有所差异。这是因为Exercise 2中路径检索是反向的，因此输出的需要倒序，但为了方便省略了倒序输出的步骤。所以真实路径为/root/123的文件123，将路径打印输出的结果为”123/root/“。

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/*
 * code/filesys/filesys.cc
 */
char ** FileSystem::PathParse(char *name, int *nums) {
    char ** paths = new char*[MaxDirDeeps];  // 为了使外部能访问
    *nums = 0;
    int lens = 0;
    int i = 0;

    // 如果不以'/'开头，则意味文件创建在根目录
    if (name[0] == '/') {
        while (name[i] != '\0') {
            if (name[i] == '/') {
                if (lens > 0) {
                    paths[*nums] = new char[lens + 1];
                    strncpy(paths[*nums], name + i - lens, lens);
                    paths[*nums][lens] = '\0';
                    lens = 0;
                    (*nums)++;
                    ASSERT((*nums) <= MaxDirDeeps);  // 不能超过最大深度
                }
            } else {
                lens++;
            }
            i++;
        }
    } else {
        lens = strlen(name);
        i = lens;
    }

    // 处理路径的最后部分，或处理直接根目录创建的文件
    if (lens > 0) {
        paths[*nums] = new char[lens + 1];
        strncpy(paths[*nums], name + i - lens, lens);
        paths[*nums][lens] = '\0';
        (*nums)++;
        ASSERT((*nums) <= MaxDirDeeps);  // 不能超过最大深度
    }

    return paths;

}

为了方便在子目录创建文件，将文件系统中的创建文件的部分抽离出来，作为函数*_create*，用于在指定的文件夹中创建指定类型的文件。该函数会返回被成功创建的文件的文件头所在的磁盘块号。然后对于目录文件，除了创建文件头之外，还需要额外的创建一个Directory对象，并将其写回磁盘，才完成了目录文件的初始化。

（注：此处使用的目录添加函数Directory::Add为重载过的版本，支持指定文件类型这一属性。）

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/*
 * code/filesys/filesys.cc
 */
//----------------------------------------------------------------------
// 在指定的文件夹创建文件
// 成功则返回创建好的文件头磁盘块，否则返回-1
//----------------------------------------------------------------------
int FileSystem::_create(BitMap *freeMap, Directory *directory, int dirSector, OpenFile * dirFile, char *name, FileType fileType, int initialSize) {
    bool success;
    FileHeader *hdr;
    int sector;

    sector = freeMap->Find();	// find a sector to hold the file header
    if (sector == -1)
        success = FALSE;		// no free block for file header
    else if (!directory->Add(name, sector, fileType))
        success = FALSE;	// no space in directory
    else {
        hdr = new FileHeader;
        if (!hdr->Allocate(freeMap, initialSize))
            success = FALSE;	// no space on disk for data
        else {
            success = TRUE;
            hdr->setParDirHeaderSector(dirSector);
            // everthing worked, flush all changes back to disk
            hdr->WriteBack(sector);
            directory->WriteBack(dirFile);
            freeMap->WriteBack(freeMapFile);

            if (fileType == F_DIRECTORY) {
                // 对于目录文件，需要额外的创建一个Directory对象并将其写回磁盘
                OpenFile *newDirFile = new OpenFile(sector);
                Directory *newDir = new Directory(NumDirEntries);
                newDir->WriteBack(newDirFile);

                delete newDirFile;
                delete newDir;
            }
        }
        delete hdr;
    }

    if (success)
        return sector;
    return -1;
}

由于出现了目录文件，因此在目录中新增一个函数CheckDir用于检查某一文件是否为目录文件。

1
2
3
4
5
6
7
8
9
10
/*
 * code/filesys/directory.cc
 */
bool Directory::CheckDir(char *name) {
    int i = FindIndex(name);

    if (i != -1)
        return table[i].fileType == F_DIRECTORY;
    return FALSE;
}

接着在文件系统中实现目标目录查找函数FileSystem::FindTargetDir，该函数用于从路径中检索出文件最终被放置的文件夹。例如，路径为”/root/123/aaa/A”，文件为”A”，则该函数会返回文件夹”aaa”的文件头所处的磁盘块号。同时该函数也支持创建不存在文件夹。如果crt的值为TRUE，且文件夹”123”不存在，则该函数会同时创建文件夹”123”和”aaa”，并最终返回”aaa”的文件头所处的磁盘块号。

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/*
 * code/filesys/filesys.cc
 */
int FileSystem::FindTargetDir(char **paths, int nums, bool crt) {
    ASSERT(nums > 0);

    if (nums == 1) {
        return DirectorySector;
    } else {
        int sector = DirectorySector;
        OpenFile * openFile;
        Directory * directory;
        BitMap * freeMap;

        freeMap = new BitMap(NumSectors);
        freeMap->FetchFrom(freeMapFile);

        // 最后一个变量是文件名，因此需要nums - 1
        for (int i = 0; i < nums - 1; i++) {
            if (sector == DirectorySector) {
                // 此时位于根目录
                openFile = directoryFile;
            } else {
                // 位于某个子目录
                openFile = new OpenFile(sector);
            }

            directory = new Directory(NumDirEntries);
            directory->FetchFrom(openFile);

            int nextSector = directory->Find(paths[i]);
            if (nextSector == -1) {  // 此时不存在
                if (crt) {
                    // 需要创建
                    nextSector = _create(freeMap, directory, sector, openFile, paths[i], F_DIRECTORY, DirectoryFileSize);
                    if (nextSector == -1) {
                        return -1;  // 创建失败
                    }

                } else {
                    // 不需要创建
                    return -1;
                }
            }
            ASSERT(directory->CheckDir(paths[i]));  // 确保这是一个文件夹
            sector = nextSector;

            if (openFile != directoryFile) {
                delete openFile;
            }
            delete directory;

        }
        delete freeMap;

        return sector;
    }
}

此时准备工作完成，开始修改文件系统中的文件操作代码，以适应绝对路径。

首先修改FileSystem::Create方法。该方法没有做特别多的变动，主要就是将原先直接在根目录上创建文件，修改为通过FindTargetDir先找到文件的父目录，然后在该目录内创建文件。然后FileSystem::Open和FileSystem::Remove也做类似的修改，即先找到最终的目录，然后在对文件做相应操作，具体实现这里就不再赘述。

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/*
 * code/filesys/filesys.cc
 */
bool
FileSystem::Create(char *name, int initialSize)
{
    OpenFile * openFile;
    Directory *directory;
    BitMap *freeMap;
    int sector;
    bool success;

    DEBUG('f', "Creating file %s, size %d\n", name, initialSize);

    // 解析绝对路径name
    int pathsNums = 0;
    char ** paths = PathParse(name, &pathsNums);
    // 获取最终的文件夹磁盘块号
    // 由于是创建，所以允许创建路径上的文件夹
    sector = FindTargetDir(paths, pathsNums, TRUE);
    if (sector == -1) {
        success = FALSE;
    } else {
        if (sector == DirectorySector) {
            openFile = directoryFile;
        } else {
            openFile = new OpenFile(sector);
        }
        directory = new Directory(NumDirEntries);
        directory->FetchFrom(openFile);

        if (directory->Find(paths[pathsNums - 1]) != -1)
            success = FALSE;			// file is already in directory
        else {
            freeMap = new BitMap(NumSectors);
            freeMap->FetchFrom(freeMapFile);

            if (_create(freeMap, directory, sector, openFile, paths[pathsNums - 1], F_NORMAL, initialSize) != -1) {
                success = TRUE;
            } else {
                success = FALSE;
            }

            delete freeMap;
        }
    }

    for (int i = 0; i < pathsNums; i++) {
        delete[] (paths[i]);
    }
    delete[] paths;
    if (openFile != directoryFile)
        delete openFile;
    delete directory;
    return success;
}

测试

修改测试函数PerformanceTest，分别对文件系统的进行文件的创建操作、对多级目录下的文件进行读写操作、和对这些文件的移除操作。

测试结果如下：其测试中分别创建了”/123”，”/usr/A”，”/usr/aaa/C”，”/usr/aaa/B”四个文件；然后对文件”/usr/aaa/B”进行读写操作测试；接着列出各个文件夹下的文件，其中首部的数字”0”代表普通文件、”1”代表目录文件；最后将这些文件进行移除。

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
29
30
31
32
root@02487b68b87e:/nachos/nachos-3.4/code/filesys# ./nachos -f -t
Starting file system performance test:
Perf test: create /123
Perf test: create /usr/A
Perf test: create /usr/aaa/C
Perf test: create /usr/aaa/B
Sequential write of 100 byte file, in 10 byte chunks
Sequential read of 100 byte file, in 10 byte chunks
List Directory => / 
0 123
 1 usr
 List Directory => /usr 
0 A
 1 aaa
 List Directory => /usr/aaa 
0 C
 0 B
 Perf test: remove /usr/aaa/B
Perf test: remove /123
Perf test: remove /usr/A
Perf test: remove /usr/aaa/C
No threads ready or runnable, and no pending interrupts.
Assuming the program completed.
Machine halting!

Ticks: total 775540, idle 764500, system 11040, user 0
Disk I/O: reads 138, writes 55
Console I/O: reads 0, writes 0
Paging: faults 0
Network I/O: packets received 0, sent 0

Cleaning up...

Exercise 5 动态调整文件长度

对文件的创建操作和写入操作进行适当修改，以使其符合实习要求。

思路

动态调整文件长度也就意味着，在对文件进行内容写入时，如果剩余空间不足，则动态申请新的磁盘块来存储写入的数据。

实现

首先为了满足要求，实现一个动态申请空间的函数Extend，该函数的实现方式与FileHeader::Allocate类似。但由于是申请额外的空间，需要做很多处理，如继续之前的情况分配直接索引块，或是继续分配一张一级索引表中未使用的空间。

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/*
 * code/filesys/filehdr.cc
 */
bool FileHeader::Extend(BitMap *freeMap, int Size) {
    if (numBytes + Size > MaxFileSize)
        return FALSE;

    // 计算还需多少个磁盘块
    int totalSectors = divRoundUp(Size + numBytes, SectorSize);

    // 先处理直接索引
    if (totalSectors <= NumDirect) {
        if (freeMap->NumClear() < totalSectors - numSectors)
            return FALSE;		// not enough space

        for (int i = numSectors; i < totalSectors; i++) {
            dataSectors[i] = freeMap->Find();
        }
    } else {
        int restNeed = totalSectors - NumDirect;
        // 计算共需要多少个一级索引
        int numSectors_LV1 = divRoundUp(restNeed, NumTableEntry);

        // 一级索引表也需要占用磁盘块，因此还需要考虑索引表能否存储的下
        int add_on = totalSectors - numSectors;
        if (numSectors > NumDirect) {
            add_on += numSectors_LV1 - divRoundUp(numSectors - NumDirect, NumTableEntry);
        }
        if (freeMap->NumClear() < add_on)
            return FALSE;

        // 直接索引分配，如果原先大小已经使用了一级索引，则该循环无法执行
        for (; numSectors < NumDirect; numSectors++)
            dataSectors[numSectors] = freeMap->Find();

        // 分别代表开始写入的一级索引表内部偏移，以及位于哪张索引表
        int innerOffset_LV1 = (numSectors - NumDirect) % NumTableEntry;
        int Offset_LV1 = (numSectors - NumDirect) / NumTableEntry;

        // 一级索引分配
        if (innerOffset_LV1 > 0) {
            IndexTable * indexTable = new IndexTable;
            // 内部偏移大于0，意味着最后一张一级索引表还未填写完
            indexTable->FetchFrom(dataSectors_LV1[Offset_LV1]);

            for (int j = innerOffset_LV1; j < NumTableEntry && (Offset_LV1 * NumTableEntry + j) < restNeed; j++) {
                indexTable->dataSectors[j] = freeMap->Find();
            }
            // 将索引表写回磁盘
            indexTable->WriteBack(dataSectors_LV1[Offset_LV1]);
            delete indexTable;
        }
        for (int i = Offset_LV1 + 1; i < numSectors_LV1; i++) {
            dataSectors_LV1[i] = freeMap->Find();

            IndexTable * indexTable = new IndexTable;

            // i * NumTableEntry + j代表已在一级索引表中记录的磁盘块总数
            for (int j = 0; j < NumTableEntry && (i * NumTableEntry + j) < restNeed; j++) {
                indexTable->dataSectors[j] = freeMap->Find();
            }
            // 将索引表写回磁盘
            indexTable->WriteBack(dataSectors_LV1[i]);
            delete indexTable;
        }
    }

    numBytes += Size;
    numSectors = totalSectors;
    return TRUE;
}

另外，由于申请空间需要调用freeMap，而该位图文件是文件系统的私有成员，因此还应当在FileSystem中实现一个拓展的封装。

由于考虑到该函数是被OpenFile调用，而OpenFile内部维护一个文件头指针FileHeader * hdr，考虑到需要使两者数据一致，因此OpenFile调用完该函数之后，需要重新将磁盘上的文件头读取到内存中。

因为仅传入一个磁盘块号，那么对该文件头的改动仅会影响磁盘上的数据，而已经读入内存的数据不会发生变化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*
 * code/filesys/filesys.cc
 */
bool FileSystem::FileExtend(int sector, int Size) {
    BitMap *freeMap;
    FileHeader *hdr;
    
    freeMap = new BitMap(NumSectors);
    freeMap->FetchFrom(freeMapFile);

    hdr = new FileHeader;
    hdr->FetchFrom(sector);
    hdr->Extend(freeMap, Size);
    hdr->WriteBack(sector);
  
  	freeMap->WriteBack(freeMapFile);

    delete freeMap;
    delete hdr;
}

因此为了方便文件头的重读取或者写回，在OpenFile中额外维护一个文件头磁盘块号hdrSector。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
 * code/filesys/openfile.h
 */
class OpenFile {
...    
  private:
...
    int hdrSector;  // Header所处的磁盘块
};

/*
 * code/filesys/openfile.cc
 */
OpenFile::OpenFile(int sector)
{ 
...
    hdrSector = sector;
}

文件创建操作可以不做修改，因为FileHeader::Allocate函数可以通过传入参数fileSize为0，而使得文件在创建时仅有FileHeader而不包含任何已分配的数据块。

再看文件写操作，有两个OpenFile::Write和OpenFile::WriteAt。查看代码可知OpenFile::Write是对OpenFile::WriteAt的一个封装，因此动态申请调用发生在OpenFile::WriteAt中。

这里主要做了两处改动：

  1. 由于支持了动态拓展，那么也就允许在文件末尾后一个字节开始写入，即允许position == fileLength
  2. 对于写入字节长度超出文件大小时，调用拓展函数申请新的空间。但如果申请失败，则按照原有规则处理。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*
 * code/filesys/openfile.cc
 */
int
OpenFile::WriteAt(char *from, int numBytes, int position)
{
...
    if ((numBytes <= 0) || (position > fileLength))
				return 0;				// check request
    if ((position + numBytes) > fileLength) {
        int need = position + numBytes - fileLength;
        if (fileSystem->FileExtend(hdrSector, need)) {
            // 额外空间申请成功，更新文件头
            hdr->FetchFrom(hdrSector);
            printf("Extend %d Bytes Success!\n", need);
        } else if (position == fileLength) {
            return 0;
        } else {
            numBytes = fileLength - position;
        }
    }
...
}

测试

由于实现了文件的动态拓展，因此在测试时将文件的初始大小设为0。

1
2
3
4
5
6
7
8
9
10
11
12
/*
 * code/filesys/fstest.cc
 */
#define FileSize 	((int)(ContentSize * 10))

static void 
FileWrite()
{
...
    if (!fileSystem->Create(FileName, 0)) {
...
}

测试结果如下：

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
29
30
31
32
33
34
35
root@02487b68b87e:/nachos/nachos-3.4/code/filesys# ./nachos -f -t
Starting file system performance test:
Ticks: total 82530, idle 82090, system 440, user 0
Disk I/O: reads 3, writes 5
Console I/O: reads 0, writes 0
Paging: faults 0
Network I/O: packets received 0, sent 0
Sequential write of 100 byte file, in 10 byte chunks
Extend 10 Bytes Success!
Extend 10 Bytes Success!
Extend 10 Bytes Success!
Extend 10 Bytes Success!
Extend 10 Bytes Success!
Extend 10 Bytes Success!
Extend 10 Bytes Success!
Extend 10 Bytes Success!
Extend 10 Bytes Success!
Extend 10 Bytes Success!
Sequential read of 100 byte file, in 10 byte chunks
Ticks: total 514530, idle 508340, system 6190, user 0
Disk I/O: reads 68, writes 42
Console I/O: reads 0, writes 0
Paging: faults 0
Network I/O: packets received 0, sent 0
No threads ready or runnable, and no pending interrupts.
Assuming the program completed.
Machine halting!

Ticks: total 514540, idle 508350, system 6190, user 0
Disk I/O: reads 68, writes 42
Console I/O: reads 0, writes 0
Paging: faults 0
Network I/O: packets received 0, sent 0

Cleaning up...

文件访问的同步与互斥

Exercise 6 源代码阅读

  1. 阅读Nachos源代码中与异步磁盘相关的代码，理解Nachos系统中异步访问模拟磁盘的工作原理。filesys/synchdisk.h和filesys/synchdisk.cc
  2. 利用异步访问模拟磁盘的工作原理，在Class Console的基础上，实现Class SynchConsole。

源码阅读

filesys/synchdisk.h和filesys/synchdisk.cc：同步磁盘的实现本身比较简单，即在Disk类的基础之上添加了同步机制。SynchDisk类中共利用了两种同步机制，锁和信号量。锁的作用主要是保护读写请求的原子性（即保证每次仅有一个线程在进行磁盘I/O）。而信号量则主要用在中断处理中，用于保证中断的同步（即确保磁盘一次仅处理一个操作）。

SynchConsole思路

首先简单分析一个Console的实现。Console是一个终端I/O的模拟类，它由读写文件类模拟输入和输出。它的操作也主要为PutChar、GetChar、WriteDone。因此参考SynchDisk的方式实现SynchConsole的思路就是读写部分操作的互斥以及中断的互斥。

SynchConsole实现

首先在*code/machine/*目录下创建两个文件，分别是synchconsole.h和synchconsole.cc

为了使创建的文件生效，需要修改code/Makefile.common文件，改动部分如下图所示。考虑到仅有用户程序需要用到Console，因此仅将其加入到USERPROG中。

class Synchconsole主要满足的策略是读和读的互斥，以及写与写的互斥。由于Console的读写分别对应的是不同的文件，因此重要的是保护模拟输入的文件的互斥，以及模拟输出的文件的互斥。

大致实现上与SynchDisk没有什么区别。重要的实现部分如下，需要注意的是对于读而言是先确保可读再进行读操作，因此先对进行P操作再执行Getchar。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*
 * code/machine/synchconsole.cc
 */
void SynchConsole::PutChar(char ch) {
    writeLock->Acquire();
    console->PutChar(ch);
    writeDone->P();
    writeLock->Release();
}

void SynchConsole::GetChar() {
    readLock->Acquire();
    readAvail->P();
    console->GetChar();
    readLock->Release();
}

Exercise 7 实现文件系统的同步互斥访问机制，达到如下效果

  1. 一个文件可以同时被多个线程访问。且每个线程独自打开文件，独自拥有一个当前文件访问位置，彼此间不会互相干扰。

  2. 所有对文件系统的操作必须是原子操作和序列化的。例如，当一个线程正在修改一个文件，而另一个线程正在读取该文件的内容时，读线程要么读出修改过的文件，要么读出原来的文件，不存在不可预计的中间状态。

  3. 当某一线程欲删除一个文件，而另外一些线程正在访问该文件时，需保证所有线程关闭了这个文件，该文件才被删除。也就是说，只要还有一个线程打开了这个文件，该文件就不能真正地被删除。

思路

  1. 这一点的实现可以通过不同线程各自创建一个OpenFile对象来处理。即每个线程都拥有基于同一磁盘块号创建的OpenFIie对象，那么它们各自内部都维护了互不干扰的访问位置。这一点由文件系统的Open操作来保证。
  2. 这一个要求的主要是为了避免，有线程正在对文件写时，另一个程序执行读，但是由于其不知道有程序正在写而导致读出来的数据可能是部分被修改的。因此要保证的就是要么读取修改结束后的，要么读取修改开始前的，而不是读取正在被修改的。
  3. 对文件实现一个全局的引用计数，每当有新的线程访问该文件，就对该文件的引用计数+1，而线程访问结束的时候就将该值-1。如果有线程尝试删除文件，则会根据引用计数的值是否为0来判断文件能否被立即删除。

实现

对于第1点，检查文件系统的Open操作的实现，可以发现，每次打开文件会先进行new OpenFile(sector)操作，再将新创建好的OpenFile对象返回。因此不需要做额外的改动。

对于第2点，为了保证某个磁盘块正在被写的时候不会被读，考虑在SynchDisk中，维护一个信号量数组sectorSemaphore，该数组用于确保每个磁盘块的读写互斥。并提供如下操作，允许对某个磁盘块进行P操作或者V操作。

1
2
3
4
5
6
7
8
9
10
/*
 * code/filesys/synchdisk.cc
 */
void SynchDisk::PSector(int sector) {
    sectorSemaphore[sector]->P();
}

void SynchDisk::VSevtor(int sector) {
    sectorSemaphore[sector]->V();
}

然后对文件的读写操作进行修改。在读或写之前先获取文件头磁盘块的访问权，然后更新文件头，操作结束之后，先将可能有改动的文件头写回，再释放该磁盘块的访问。之所以仅对文件头的磁盘块做互斥访问限制，主要是为了简便。这样只有先拿到文件头的访问权，才能对数据作修改。写操作可能会修改文件头数据索引，而读之前也要考虑是否要更新，文件头的更新操作是必要的。因此也就没必要再单独对读写访问的各个磁盘块上锁。

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
29
30
31
32
33
34
35
36
37
38
39
40
41
/*
 * code/filesys/openfile.cc
 */
int
OpenFile::ReadAt(char *into, int numBytes, int position)
{
    // 读之前先更新文件头
    synchDisk->PSector(hdrSector);
    hdr->FetchFrom(hdrSector);
...
    // 读完之后写回一次文件头
    hdr->WriteBack(hdrSector);
    synchDisk->VSector(hdrSector);
...
}

int
OpenFile::WriteAt(char *from, int numBytes, int position)
{
    // 写之前先更新文件头
    synchDisk->PSector(hdrSector);
    hdr->FetchFrom(hdrSector);
...
    if (!firstAligned) {
        synchDisk->VSector(hdrSector);
        ReadAt(buf, SectorSize, firstSector * SectorSize);
        synchDisk->PSector(hdrSector);
    }

    if (!lastAligned && ((firstSector != lastSector) || firstAligned)) {
        synchDisk->VSector(hdrSector);
        ReadAt(&buf[(lastSector - firstSector) * SectorSize],
               SectorSize, lastSector * SectorSize);
        synchDisk->PSector(hdrSector);
    }
...
    // 写完之后写回一次文件头
    hdr->WriteBack(hdrSector);
    synchDisk->VSector(hdrSector);
...
}

对于第3点，由于文件系统的Remove操作，最终会调用目录中的Remove方法，来实现文件的删除。因此文件引用计数则放置在目录项中，如果要对文件进行删除，则需要判断引用计数是否为0；如果引用计数不为0，则删除失败。

将引用计数放在目录项中，作为文件的一个属性。然后新增根据文件头的磁盘块号对文件计数+1以及计数-1的操作。同时目录类还支持检查文件的引用计数是否为0的CheckRefClear操作。

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/*
 * code/filesys/directory.h
 */
class DirectoryEntry {
  public:
...    
    int refCount;
};

/*
 * code/filesys/directory.cc
 */
bool
Directory::Add(char *name, int newSector, FileType fileType) {
...
            table[i].refCount = 0;
...
}

void Directory::PlusRef(int sector) {
    for (int i = 0; i < tableSize; i++) {
        if (table[i].inUse && table[i].sector == sector) {
            table[i].refCount++;
        }
    }
}

void Directory::NegaRef(int sector) {
    for (int i = 0; i < tableSize; i++) {
        if (table[i].inUse && table[i].sector == sector) {
            table[i].refCount--;
        }
    }
}

bool Directory::CheckRefClear(int sector) {
    for (int i = 0; i < tableSize; i++) {
        if (table[i].inUse && table[i].sector == sector) {
            return table[i].refCount == 0;
        }
    }
}

将引用计数的修改操作，在文件系统中做一个该接口的封装，方便OpenFile使用。

1
2
3
4
5
6
7
8
9
10
/*
 * code/filesys/directory.cc
 */
class FileSystem {
  public:
  ...
    void PlusRef(int sector, int parSector);
    void NegaRef(int sector, int parSector);
...
};

然后修改OpenFile类的构造函数以及析构函数，这样当文件被打开时，会增加引用计数，而当文件被关闭时会减少引用计数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
 * code/filesys/openfile.cc
 */
OpenFile::OpenFile(int sector)
{ 
...
    fileSystem->PlusRef(sector, hdr->getParDirHeaderSector());
...
}

OpenFile::~OpenFile()
{
    fileSystem->NegaRef(hdrSector, hdr->getParDirHeaderSector());
    delete hdr;
}

最后修改文件系统的Remove方法，当文件不存在或者引用计数不为0时，文件删除失败。

1
2
3
4
5
6
7
/*
 * code/filesys/filesys.cc
 */
if (sector == -1 || !directory->CheckRefClear(sector)) {
...
    return FALSE;
}

测试

为了方便测试，在OpenFile中新增一个getPos方法，来查看文件的seekPosition的值。

首先测试第1点，两个线程同时读文件，结果如下。可以看到两个线程同时读取同一个文件，各自维护了一个文件位置标志。

然后测试第2点，可以看到读写交替进行。

最后测试第3点，当文件正在写的时候，文件删除失败了；直到写结束的时候，再尝试删除，则成功。

Challenges题目

Challenge 1 性能优化

  1. 例如，为了优化寻道时间和旋转延迟时间，可以将同一文件的数据块放置在磁盘同一磁道上

  2. 使用cache机制减少磁盘访问次数，例如延迟写和预读取。

思路

实现

Challenge 2 实现pipe机制

重定向openfile的输入输出方式，使得前一进程从控制台读入数据并输出至管道，后一进程从管道读入数据并输出至控制台。

实现

在文件系统中新增两个宏，用于标示pipe文件的固定磁盘位置，以及其最大文件大小。并在文件系统的构造函数中对其初始化，pipe文件的初始值为0。仅维护pipe文件的文件头磁盘块，而具体文件则不在文件系统中维护。

1
2
#define PipeSector          2
#define PipeFileSize        0

然后在OpenFile类中新增一个功能ReadAll用于一次性读取文件的所有字节。

1
2
3
4
5
6
7
8
/*
 * code/filesys/openfile.cc
 */
int OpenFile::ReadAll(char *into) {
    int result = ReadAt(into, hdr->FileLength(), seekPosition);
    seekPosition += result;
    return result;
}

根据之前的设计，Pipe文件的大小会动态增涨。因此分别实现Pipe文件的读写操作函数。对于读操作，不仅会一次性读取Pipe中的所有字节，而且会清空Pipe，即读完之后Pipe的大小为0。对于写操作，由于支持动态增长，以及读写操作都会更新文件头，因此仅需要调用Write方法即可。

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
/*
 * code/filesys/filesys.cc
 */
int FileSystem::ReadPipe(char *data) {
    OpenFile* openFile = new OpenFile(PipeSector);
    int result = openFile->ReadAll(data);

    BitMap *freeMap = new BitMap(NumSectors);
    freeMap->FetchFrom(freeMapFile);

    FileHeader *pipeHdr = new FileHeader;
    pipeHdr->FetchFrom(PipeSector);
    pipeHdr->Deallocate(freeMap);
    pipeHdr->Allocate(freeMap, 0);
    pipeHdr->WriteBack(PipeSector);

    freeMap->WriteBack(freeMapFile);

    return result;
}

int FileSystem::WritePipe(char *data) {
    OpenFile* openFile = new OpenFile(PipeSector);
    int result = openFile->Write(data, strlen(data));

    return result;
}

测试

设计测试函数如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void PipeInTest() {
    printf("Thread 1 put data in pipe\n");
    char in[FileSize + 1];
    printf("Input: ");
    scanf("%s", in);
    fileSystem->WritePipe(in);
}

void PipeOutTest() {
    printf("Thread 2 get data from pipe\n");
    char out[FileSize + 1];

    fileSystem->ReadPipe(out);
    prinft("Output: %s", out);
}

分别调用执行，结果如下：

遇到的困难

困难1 测试文件系统出现Segment Fault

尽管未对文件系统做任何修改，但是不论怎么执行都会得到Segment Fault的错误。使用命令nachos -d查看调试信息得知，程序执行到创建交换空间（或虚拟内存）文件时出现的错误，可以得知正是该文件的存在引发的错误。进一步调查发现，在code/userprog/Makefile中启用了FILESYS_STUB宏，该宏定义的作用是将Nachos的文件系统实现为本地Unix文件系统的封装，也就是说在实现用户线程的时候调用的文件系统是基于本地Unix的。然而在文件系统的code/filesys/Makefile文件中，并未启用FILESYS_STUB宏，这也就意味着此处使用的Nachos内部实现的文件系统，存在一个与Unix文件系统差异的点使得错误的发生。

最后调查发现了真正的问题所在。根据code/threads/system.cc中的Initialize函数得知，machine初始化，在“REAL”文件系统fileSystem之前。

同时交换分区VirtualMemory是在Machine中初始化的，所以导致首次使用的时候，文件系统还是未格式化，却在Machine中尝试去创建文件了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*
 * code/machine/machine.cc
 */
Machine::Machine(bool debug)
{
...
#ifdef SWAPING
    swapBitMap = new BitMap(NumPhysPages * 2);

    fileSystem->Create("VirtualMemory", MemorySize * 2);
    swapFile = fileSystem->Open("VirtualMemory");
#endif
...
}

解决办法：修改交换分区VirtualMemory的初始化位置，将其放在文件系统中初始化。

为了避免大量修改代码，交换分区仍放在Machine类中，但是将其初始化的部分取出封装成一个函数

1
2
3
4
5
void Machine::CreateSwap() {
    swapBitMap = new BitMap(NumPhysPages * 2);
    fileSystem->Create("VirtualMemory", MemorySize * 2);
    swapFile = fileSystem->Open("VirtualMemory");
}

然后将其放在文件系统之后被初始化。

困难2 文件系统测试函数无法执行

传入nachos中与文件系统相关的参数，不会执行。尽管使用了-t参数去调用PerformanceTest测试函数，但是真正执行的却是ThreadTest测试函数。

经过阅读code/threads/main.cc可以发现如果定义了THREADS宏，则线程测试函数会先读走一个命令行参数，处理完线程测试函数之后，才会继续执行后续的用户线程、文件系统以及网络的测试。然后再进一步查看code/filesys/Makefile文件，可以发现文件系统启用了THREADS宏。

1
DEFINES = -DTHREADS -DUSER_PROGRAM -DVM -DFILESYS_NEEDED -DFILESYS

另外，经过对THREADS宏的作用进行调查，发现该宏定义与否不涉及线程功能的实现。大部分的宏的用于在Nachos中启用某个功能，如USER_PROGRAM、USE_TLB等；而THREADS则仅用于在main.cc文件中启用线程测试。

解决办法：将code/filesys/Makefile中的THREADS宏删去。因为对Makefile文件进行了改动，因此需要先删除之前编译好的object文件（.o文件）然后重新编译。

参考文献

[1] 百度文库. Nachos文件系统实习报告[EB/OL]. https://wenku.baidu.com/view/cb066179941ea76e59fa0485.html?re=view

[2] 百度文库. nachos Lab5实习报告[EB/OL]. https://wenku.baidu.com/view/04382358f6ec4afe04a1b0717fd5360cbb1a8d40.html?re=view

Nachos Lab04 文件系统

https://rlyown.github.io/2020/12/26/Nachos-Lab04-文件系统/

Author

Chaos Chen

Posted on

2020-12-26

Updated on

2023-06-30

Licensed under

#

Commentaires

×