Nachos实习——Lab4文件系统

ゞ浴缸里的玫瑰 2022-12-27 14:19 18阅读 0赞

# Nachos实习——Lab4 文件系统 #

### 文章目录 ###

*  Nachos实习——Lab4 文件系统
 *   *  内容一：总体概述
     *  内容二：任务完成情况
     *  内容三：具体完成Exercise情况
     *   *  一、文件系统的基本操作
         *   *  Exercise 1 源代码阅读
             *   *  1、code/filesys/filesys.h（cc）
                 *  2、code/filesys/filehdr.h(cc)
                 *  3、code/filesys/directory.h(cc)
                 *  4、code /filesys/openfile.h（cc）
                 *  5、code/userprog/bitmap.h（cc）
             *  Exercise 2 扩展文件属性
             *   *  1、基本思路
                 *  2、增加文件描述信息
                 *  3、突破文件名长度的限制
             *  Exercise 3 扩展文件长度
             *   *  1、基本思路
                 *  2、filehdr.h
                 *  3、filehdr.cc
                 *  4、测试说明
                 *  5、测试结果截图
             *  Exercise 4 实现多级目录
             *   *  1、基本思路
                 *  2、实现文件路径
                 *  3、实现多级目录
                 *  4、测试说明
                 *  5、测试结果截图
             *  Exercise 5 动态调整文件长度
             *   *  1、基本思路
                 *  2、开始前准备
                 *  3、实现ExpandFileSize函数
                 *  4、修改OpenFile :: WriteAt函数
                 *  5、测试结果
         *  二、文件访问的同步与互斥
         *   *  Exercise 6 源代码阅读
             *   *  a) 阅读Nachos源代码中与异步磁盘相关的代码，理解Nachos系统中异步访问模拟磁盘的工作原理。
                 *  b) 利用异步访问模拟磁盘的工作原理，在Class Console的基础上，实现Class SynchConsole。
             *  Exercise 7 实现文件系统的同步互斥访问机制，达到如下效果：
             *   *  1、a,b) 的解决方案
                 *  2、c)解决方案
         *  三、Challenges题目（至少选做1个）
         *   *  Challenge 1 性能优化
             *  Challenge 2 实现pipe机制
             *   *  1、基本思路
                 *  2、filesys.cc
                 *  3、测试程序
                 *  4、测试结果
     *  内容四：遇到的困难以及解决方法
     *  内容五：收获及感想
     *  内容六：对课程的意见和建议
     *  内容七：参考文献

## 内容一：总体概述 ##

本实习希望通过修改Nachos系统的底层源代码，达到“完善文件系统”的目标。

Nachos文件系统建立在模拟磁盘上，提供了基本的文件操作，如创建、删除、读取、写入等等。文件的逻辑结构与物理位置之间的映射关系由文件系统统一维护，用户只需通过文件名即可对文件进行操作。

然而，相比于实际文件系统，Nachos文件系统还存在很多不足之处：

*  文件长度的限制

Nachos文件系统采用直接索引方式，故文件长度不能超过4KB（更准确的说，是((128 – 2 \* 4) / 4) \* 128 = 3840 B）。同时，文件的长度必须在创建时予以指定，且不得更改。

*  文件数目的限制

Nachos文件系统只有一级目录，系统中所有的文件都存于根目录下，且数目不能多于10个。

*  粗粒度的同步互斥机制

Nachos文件系统每次只允许一个线程进行访问，不支持多个线程同时访问文件系统。

*  性能优化与容错

Nachos文件系统没有Cache机制，也没有容错机制，即当文件系统正在使用时，如果系统突然中断，文件内容的正确性无法保证。

## 内容二：任务完成情况 ##

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th align="center">Exercise 1</th> 
   <th align="center">Exercise 2</th> 
   <th align="center">Exercise 3</th> 
   <th align="center">Exercise 4</th> 
   <th align="center">Exercise 5</th> 
   <th align="center">Exercise 6</th> 
   <th align="center">Exercise 7</th> 
   <th align="center">Challenge</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><strong>完成情况</strong></td> 
   <td align="center"><strong>Y</strong></td> 
   <td align="center"><strong>Y</strong></td> 
   <td align="center"><strong>Y</strong></td> 
   <td align="center"><strong>Y</strong></td> 
   <td align="center"><strong>Y</strong></td> 
   <td align="center"><strong>Y</strong></td> 
   <td align="center"><strong>Y</strong></td> 
   <td align="center"><strong>Y</strong></td> 
  </tr> 
 </tbody> 
</table>

## 内容三：具体完成Exercise情况 ##

### 一、文件系统的基本操作 ###

#### 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

**Nachos 的文件系统是建立在 Nachos 的模拟物理磁盘上的，文件系统实现的结构如下图 所示：**

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ogNystap-1607692459509)(/Users/jaggerqian/Library/Application Support/typora-user-images/image-20201204160256504.png)\]][img-ogNystap-1607692459509_Users_jaggerqian_Library_Application Support_typora-user-images_image-20201204160256504.png]

##### 1、code/filesys/filesys.h（cc） #####

在 Nachos 中，实现了两套文件系统，它们对外接口是完全一样的：一套称作为 FILESYS\_STUB，它是建立在 UNIX 文件系统之上的，而不使用 Nachos 的模拟磁盘，它主要用于读者先实现了用户程序和虚拟内存， 然后再着手增强文件系统的功能；另一套是 Nachos 的文件系统，它是实现在 Nachos 的虚拟磁盘上的。当整个系统完成之后，只能使用第二套文件系统的实现。

class FileSystem {
      public:
        FileSystem(bool format);		
        bool Create(char *name, int initialSize);  	
        OpenFile* Open(char *name); 	// Open a file (UNIX open)
        bool Remove(char *name);  		// Delete a file (UNIX unlink)
        void List();			// List all the files in the file system
        void Print();			// List all the files and their contents
      private:
       OpenFile* freeMapFile;		// Bit map of free disk blocks,
       OpenFile* directoryFile;		// "Root" directory -- list of 
    					// file names, represented as a file
    };

如上述代码所示，这两文件中主要定了文件系统类，并实现了相关方法，如：

FileSystem(bool format);	//在同步磁盘的基础上建立一个文件系统。当 format 标志设置时，建立一个新的文件系 统；否则使用原来文件系统中的内容。	
    bool Create(char *name, int initialSize);//在当前的文件系统中创建一个固定大小的文件  	
    OpenFile* Open(char *name); 	//在当前的文件系统中打开一个已有的文件
    bool Remove(char *name);//在当前的文件系统中删除一个已有的文件

##### 2、code/filesys/filehdr.h(cc) #####

这俩文件定义了文件头。文件头的定义和实现如下所示，由于目前 Nachos 只支持直接索引，而且文件长度一旦固定， 就不能变动。所以文件头的实现比较简单

class FileHeader {
      public:
        bool Allocate(BitMap *bitMap, int fileSize);// 通过文件大小初始化文件头、根据文件大小申请磁盘空间
        void Deallocate(BitMap *bitMap);  		// 将一个文件占用的数据空间释放
        void FetchFrom(int sectorNumber); 	// 从磁盘扇区中取出文件头
        void WriteBack(int sectorNumber); 	// 将文件头写入磁盘扇区
        int ByteToSector(int offset);	// 文件逻辑地址向物理地址的转换
        int FileLength();			// 返回文件长度
        void Print();			// 打印文件头信息（调试用）
      private:
        int numBytes;			// 文件长度（字节数）
        int numSectors;			// 文件占用的扇区数
        int dataSectors[NumDirect];		//文件索引表
    };

在 Nachos 中，每个扇区的大小为 128 个字节。每个 inode 占用一个扇区，共有 30 个直接索 引。所以 Nachos 中最大的文件大小不能超过 3840 个字节。

##### 3、code/filesys/directory.h(cc) #####

定义目录文件。Nachos 中的目录结构非常简单，它只有一级目录，也就是只有根目录；而且根目录的大小 是固定的，整个文件系统中只能存放有限个文件。这样的实现比较简单，这里只介绍目录的接口：

class DirectoryEntry {  //目录项结构
      public:
        bool inUse;				//该目录项是否在使用标志
        int sector;				//对应文件的文件头位置
        char name[FileNameMaxLen + 1];	//对应文件的文件名
    };
    class Directory {
      public:
        Directory(int size); 		//初始化方法，size 规定了目录中可以放多少文件
        ~Directory();			//析构方法
        void FetchFrom(OpenFile *file);  	// 从目录文件中读入目录结构
        void WriteBack(OpenFile *file);	// 将该目录结构写回目录文件
        int Find(char *name);		// 在目录中寻找文件名，返回文件头的物理位置
        bool Add(char *name, int newSector);  //将一个文件加入到目录中
        bool Remove(char *name);		// 将一个文件从目录中删除
        void List();			// 列出目录中所有的文件
        void Print();			// 打印出目录中所有的文件和内容（调试用）
      private:
        int tableSize;			// 目录项数目
        DirectoryEntry *table;		// 目录项表
        int FindIndex(char *name);		//根据文件名找出该文件在目录项表中的表项序号
    };

##### 4、code /filesys/openfile.h（cc） #####

定义打开文件。该模块定义了一个打开文件控制结构。当用户打开了一个文件时，系统即为其产生一个打开 文件控制结构，以后用户对该文件的访问都可以通过该结构。打开文件控制结构中的对文件 操作的方法同 UNIX 操作系统中的系统调用。针对 FileSystem 结构中的两套实现，这里的打开文件控制结构同样有两套实现。这里分析建立在 Nachos 上的一套实现：

class OpenFile {
      public:
        OpenFile(int sector);		// 打开一个文件，该文件的文件头在 sector 扇区
        ~OpenFile();			// 关闭一个文件
        void Seek(int position); 		// 移动文件位置指针（从文件头开始）
        int Read(char *into, int numBytes); // 从文件中读出 numByte到into 缓冲，同时移动文件位置指针（通过ReadAt实现）
        int Write(char *from, int numBytes);//将from缓冲中写入numBytes个字节到文件中，同时移动文件位置指针（通过 WriteAt 实现）
        int ReadAt(char *into, int numBytes, int position);//将从 position 开始的 numBytes 读入 into 缓冲
        int WriteAt(char *from, int numBytes, int position);//将 from 缓冲中 numBytes 写入从 position 开始的区域
        int Length(); 			// 返回文件的长度
        
      private:
        FileHeader *hdr;			// 该文件对应的文件头（建立关系）
        int seekPosition;			// 当前文件位置指针
    };

##### 5、code/userprog/bitmap.h（cc） #####

定义位图模块。在 Nachos 的文件系统中，是通过位图来管理空闲块的。Nachos 的物理磁盘是以扇区为访问 单位的，将扇区从 0 开始编号。所谓位图管理，就是将这些编号填入一张表，表中为 0 的地方说明该扇区没有被占用，而非 0 位置说明该扇区已被占用。这部分内容是用 BitMap 类实 现的。BitMap 类的实现比较简单，这里只是介绍其接口。

class BitMap {
      public:
        BitMap(int nitems);		// 初始化方法，给出位图的大小，将所有位标明未用
        ~BitMap();			// 析构方法 
        void Mark(int which);   	// 标志第 which 位被占用
        void Clear(int which);  	// 清除第 which 位
        bool Test(int which);   	// 测试第 which 位是否被占用，若是，返回 TRUE
        int Find();            	// 找到第一个未被占用的位，标志其被占用,若没有找到，返回-1
        int NumClear();		// 返回多少位没有被占用
        void Print();		// 打印出整个位图（调试用）
        void FetchFrom(OpenFile *file); 	// 从一个文件中读出位图
        void WriteBack(OpenFile *file); 	// 将位图内容写入文件
      private:
      …………
       	//实现内部属性
    };

#### Exercise 2 扩展文件属性 ####

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

##### 1、基本思路 #####

因为目前nachos只有一个目录，所以在这个练习中我没有把路径添加在里面，相关属性我在第四个练习中实现。按照题目描述，需要实现两个需求，一个是增加文件描述信息，另一个是突破文件名长度的限制。所以我分成两步完成。

##### 2、增加文件描述信息 #####

根据nachos文件系统的结构，当我们需要修改文件相关属性的时候我们需要去修改code/filesys/filehdr.h文件。下图描述了文件头信息：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70]

如上图所示，文件头分为两个部分，磁盘和内存部分。原始的磁盘部分中只存在numBytes、numSectors、dataSectors\[NumDirect\]。所以原来的直接索引=（128-4-4）/4=30。但是目前增加了新的属性，所以相应的直接索引数量将会变化。

**（1）增加获取时间函和文件后缀函数**

为了获取到当前时间，需要先在filehdr.h(cc)中定义和实现两个函数。

//filehdr.cc
    char*
    getFileExtension(char *filename)//获取文件后缀
    {
        char *dot = strrchr(filename, '.');
        if(!dot || dot == filename) return "";
        return dot + 1;
    }
    char*
    getCurrentTime(void)//获取当前时间
    {
        time_t rawtime;
        time(&rawtime);
        struct tm* currentTime = localtime(&rawtime);
        return asctime(currentTime); 
      //该函数返回的时间是一个字符串，格式为：“Sat Dec  5 00:27:39 2020”所以需要占用一个25字节大小的空间（包括“\0”）
    }
    //filehdr.h
    extern char* getFileExtension(char *filename);
    extern char* getCurrentTime(void);

**（2）扩展头文件信息**

//filehdr.h
    #define NumOfIntHeaderInfo 2 //numBytes和numSectors
    #define NumOfTimeHeaderInfo 3 //三个时间字符串
    #define LengthOfTimeHeaderStr 26 // 时间长度
    #define MaxExtLength 5           // 文件类型长度
    #define LengthOfAllString MaxExtLength + NumOfTimeHeaderInfo*LengthOfTimeHeaderStr
    
    #define NumDirect   ((SectorSize - (NumOfIntHeaderInfo*sizeof(int) + LengthOfAllString*sizeof(char))) / sizeof(int))//直接索引个数，添加晚上上述信息之后，索引将由原来的30个变为9个
    class FileHeader {
      private:
        char fileType[MaxExtLength];
        char createdTime[LengthOfTimeHeaderStr];
        char modifiedTime[LengthOfTimeHeaderStr];
        char lastVisitedTime[LengthOfTimeHeaderStr];
        int dataSectors[NumDirect];                       
        int headerSector; 
      public:
        void HeaderCreateInit(char* ext); 
        void setFileType(char* ext) { strcmp(ext, "") ? strcpy(fileType, ext) : strcpy(fileType, "None"); }
        void setCreateTime(char* t) { strcpy(createdTime, t); }
        void setModifyTime(char* t) { strcpy(modifiedTime, t); }
        void setVisitTime(char* t) { strcpy(lastVisitedTime, t); }
        void setHeaderSector(int sector) { headerSector = sector; }
        int getHeaderSector() { return headerSector; }
    };

//filehdr.cc
    void
    FileHeader::HeaderCreateInit(char* ext)//初始化时间
    {
        setFileType(ext);
        char* currentTimeString = getCurrentTime();
        setCreateTime(currentTimeString);
        setModifyTime(currentTimeString);
        setVisitTime(currentTimeString);
    }

**（3）初始化和更新头部信息**

//filesys.cc
    FileSystem::FileSystem(bool format)
    {
        if (format) {
            ...
            FileHeader *mapHdr = new FileHeader;
            mapHdr->HeaderCreateInit("BMap");//添加代码
            FileHeader *dirHdr = new FileHeader;
            dirHdr->HeaderCreateInit("DirH");//添加代码
        }
    }
    bool
    FileSystem::Create(char *name, int initialSize)
    {
                    ...
                else
                {
                    success = TRUE;
                    hdr->HeaderCreateInit(getFileExtension(name));//添加代码

之前在头文件中定义了内存部分的属性headerSector是因为打开文件时需要更新FileHeader。

//Openfile.cc
    OpenFile::OpenFile(int sector)
    {
        hdr = new FileHeader;
        hdr->FetchFrom(sector);
        hdr->setHeaderSector(sector);    
        seekPosition = 0;
    }
    
    OpenFile::~OpenFile()
    {
        hdr->WriteBack(hdr->getHeaderSector());//更新头信息
        delete hdr;
    }
    int
    OpenFile::ReadAt(char *into, int numBytes, int position)//读的时候更新时间
    {
        ...
        hdr->setVisitTime(getCurrentTime());
    }
    
    int
    OpenFile::WriteAt(char *from, int numBytes, int position)//写的时候更新时间
    {
        ...
        hdr->setVisitTime(getCurrentTime());
        hdr->setModifyTime(getCurrentTime());
    }

**（4）修改输出信息**

//filehdr.cc
    void
    FileHeader::Print()
    {
        int i, j, k;
        char *data = new char[SectorSize];
        printf("------------ %s -------------\n", "FileHeader contents");
        printf("\tFile type: %s\n", fileType);
        printf("\tCreated: %s", createdTime);
        printf("\tModified: %s", modifiedTime);
        printf("\tLast visited: %s", lastVisitedTime);
        // printf("\tPath: %s\n", filePath); // uncomment when we need it
        printf("File size: %d.  File blocks:\n", numBytes);
    ………………
    }

**（5）测试说明**

测我第一次测试的时候，直接在命令行输入测试命令，可能因为执行太快了，三个时间显示是一样的。所以我重新测试了一遍，写了个脚本，在脚本里添加了sleep 1。同时是测试结果更加的好看，我在main函数中添加了个-Q的参数，来控制关机的时候的输出信息。当时你也可以选择直接注释掉这些输出信息。

//main.cc
    bool VERBOSE = TRUE;
    for (argc--, argv++; argc > 0; argc -= argCount, argv += argCount) {
    	argCount = 1;
            if (!strcmp(*argv, "-z")) 
            …………
    				if (!strcmp(*argv, "-Q")) 
                VERBOSE = FALSE;
    //system.h
    extern bool VERBOSE;
    //Interrupt.cc
    void
    Interrupt::Idle()
    {
      …………
        if (VERBOSE) {
            printf("No threads ready or runnable, and no pending interrupts.\n");
            printf("Assuming the program completed.\n");
        }
    }
     void
    Interrupt::Halt()
    {
        if (VERBOSE) {
            printf("Machine halting!\n\n");
            stats->Print();
        }
    }

#测试脚本
    #在filesys目录下的test目录下写脚本t4_2_1.sh
    #!/bin/sh
    cd /opt/module/nachos_dianti/nachos-3.4/code/filesys
    echo "=== copies file \"small\" from UNIX to Nachos (and add extension) ==="
    ./nachos -Q -cp test/small small.txt
    sleep 1 # to observe the modification time change
    echo "=== print the content of file \"small\" ==="
    ./nachos -Q -p small.txt
    echo "=== prints the contents of the entire file system ==="
    ./nachos -Q -D

**（6）测试结果截图**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70 1]

##### 3、突破文件名长度的限制 #####

**（1）基本思路**

原始的文件名长度在/filesys/directory.h文件中被限制为9

#define FileNameMaxLen 		9
    class DirectoryEntry {
      public:
        ...
        char name[FileNameMaxLen + 1];
    };

按照上面直接索引计算的思路，我们只需减去其他项目所占空间，那么剩下来的部分我们则可以用来全部存放文件名。

观察在目录项中包含一个bool和一个int类型的变量，同时在filesys/filesys.cc文件中定定义了10个这样的目录项

#define NumDirEntries 		10
    #define DirectoryFileSize 	(sizeof(DirectoryEntry) * NumDirEntries)

综上所述，对FileNameMaxLen作如下修改

#define FileNameMaxLen (((SectorSize - (sizeof(bool) + sizeof(int)) * 10) / sizeof(char)) - 1)

**（2）测试说明**

我同样了写了一个脚本，对修改前和修改后进行了测试

#测试脚本
    #在filesys目录下的test目录下写脚本t4_2_2.sh
    #!/bin/sh
    cd /opt/module/nachos_dianti/nachos-3.4/code/filesys
    echo "=== copies file \"small\" from UNIX to Nachos (and add extension) ==="
    ./nachos -Q -cp test/small I_am_a_long_long_long_long_long_long_filename.txt
    sleep 1 # to observe the modification time change
    echo "=== prints the contents of the entire file system ==="
    ./nachos -Q -D

**（3）测试结果**

修改前：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70 2]

修改后：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70 3]

#### Exercise 3 扩展文件长度 ####

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

##### 1、基本思路 #####

准确来说，通过上面添加文件属性之后，文件长度已经只有9\*128=1152B字节了。因为目前Nachos文件系统只采用了直接索引，所以为了突破文件长度，我采用的机制是添加一个二级索引，一个三级索引。将原来的9个直接索引的最后两个分别改称二级和三级索引。这样以来，修改之后的最大文件长度可以达到：7\*128+32\*128+32\*32\*128=136064B约为132K。修改了文件长度限制之后，那么我们将需要重新修改allocate，deallocate，ByteToSector（偏移量计算）和print函数。因为这些函数都跟文件长度有关系。

##### 2、filehdr.h #####

#define NumDataSectors ((SectorSize - (NumOfIntHeaderInfo*sizeof(int) + LengthOfAllString*sizeof(char))) / sizeof(int))//存储数据区域的扇区数量，也就是原来的直接索引数量
    #define NumDirect (NumDataSectors - 2)//直接索引数量
    #define IndirectSectorIdx (NumDataSectors - 2)//二级索引的位置为一级索引的倒数第二个
    #define DoubleIndirectSectorIdx (NumDataSectors - 1)//三级索引的位置为一级索引的倒数第一个
    #define MaxFileSize (NumDirect * SectorSize) + \
                        ((SectorSize / sizeof(int)) * SectorSize) + \
                        ((SectorSize / sizeof(int)) * ((SectorSize / sizeof(int)) * SectorSize))//重新定义最大文件长度
    class FileHeader {
      private:
      	int dataSectors[NumDataSectors];//注意不是添加，是修改
    };
    char* printChar(char oriChar);

##### 3、filehdr.cc #####

主要是理解Allocate部分，理解了这部分，其他三个函数的修改相互对应。

#define LevelMapNum (SectorSize / sizeof(int))
    bool
    FileHeader::Allocate(BitMap *freeMap, int fileSize)
    {
        …………
        if (numSectors < NumDirect) {//文件长度小于7*128时，直接索引就够
    		…………
        } else {
            if (numSectors < (NumDirect + LevelMapNum)) {//文件长度小于7*128+32*128时，使用直接索引+二级索引
                DEBUG('f', "Allocating using single indirect indexing\n");
                // 直接索引
                for (int i = 0; i < NumDirect; i++)
                    dataSectors[i] = freeMap->Find();
                // 二级索引
                dataSectors[IndirectSectorIdx] = freeMap->Find();
                int indirectIndex[LevelMapNum];
                for (int i = 0; i < numSectors - NumDirect; i++) {
                    indirectIndex[i] = freeMap->Find();
                }
                synchDisk->WriteSector(dataSectors[IndirectSectorIdx], (char*)indirectIndex);
            } else if (numSectors < (NumDirect + LevelMapNum + LevelMapNum*LevelMapNum)) {//文件长度小于7*128+32*128+32*32*128时，使用直接索引+二级索引+三级索引
                DEBUG('f',"Allocating using double indirect indexing\n");
                // 直接索引
                for (int i = 0; i < NumDirect; i++)
                    dataSectors[i] = freeMap->Find();
                dataSectors[IndirectSectorIdx] = freeMap->Find();
                // 二级索引
                int indirectIndex[LevelMapNum];
                for (int i = 0; i < LevelMapNum; i++) {
                    indirectIndex[i] = freeMap->Find();
                }
                synchDisk->WriteSector(dataSectors[IndirectSectorIdx], (char*)indirectIndex);
                // 三级索引
                dataSectors[DoubleIndirectSectorIdx] = freeMap->Find();
                const int sectorsLeft = numSectors - NumDirect - LevelMapNum;
                const int secondIndirectNum = divRoundUp(sectorsLeft, LevelMapNum);
                int doubleIndirectIndex[LevelMapNum];
                for (int j = 0; j < secondIndirectNum; j++) {
                    doubleIndirectIndex[j] = freeMap->Find();
                    int singleIndirectIndex[LevelMapNum];
                    for (int i = 0; (i < LevelMapNum) && (i + j * LevelMapNum < sectorsLeft); i++) {
                        singleIndirectIndex[i] = freeMap->Find();
                    }
                    synchDisk->WriteSector(doubleIndirectIndex[j], (char*)singleIndirectIndex);
                }
                synchDisk->WriteSector(dataSectors[DoubleIndirectSectorIdx], (char*)doubleIndirectIndex);
            } else {//超出文件最大长度，无法存储
                ASSERT(FALSE);
            }
        }
        return TRUE;
    }
    
    void
    FileHeader::Deallocate(BitMap *freeMap)
    {
        int i, ii, iii; // 分别对应直接索引、二级索引、三级索引
        DEBUG('f',"Deallocating direct indexing table\n");
        for (i = 0; (i < numSectors) && (i < NumDirect); i++) {
            ASSERT(freeMap->Test((int)dataSectors[i]));
            freeMap->Clear((int)dataSectors[i]);
        }
        if (numSectors > NumDirect) {
            DEBUG('f', "Deallocating single indirect indexing table\n");
            int singleIndirectIndex[LevelMapNum]; 
            synchDisk->ReadSector(dataSectors[IndirectSectorIdx], (char*)singleIndirectIndex);
            for (i = NumDirect, ii = 0; (i < numSectors) && (ii < LevelMapNum); i++, ii++) {//回收二级索引存储下的文件
                ASSERT(freeMap->Test((int)singleIndirectIndex[ii]));
                freeMap->Clear((int)singleIndirectIndex[ii]);
            }
            ASSERT(freeMap->Test((int)dataSectors[IndirectSectorIdx]));
            freeMap->Clear((int)dataSectors[IndirectSectorIdx]);
            if (numSectors > NumDirect + LevelMapNum) {//回收三级索引存储下的文件
                DEBUG('f',"Deallocating double indirect indexing table\n");
                int doubleIndirectIndex[LevelMapNum];
                synchDisk->ReadSector(dataSectors[DoubleIndirectSectorIdx], (char*)doubleIndirectIndex);
                for (i = NumDirect + LevelMapNum, ii = 0; (i < numSectors) && (ii < LevelMapNum); ii++) {
                    synchDisk->ReadSector(doubleIndirectIndex[ii], (char*)singleIndirectIndex);
                    for (iii = 0; (i < numSectors) && (iii < LevelMapNum); i++, iii++) {
                        ASSERT(freeMap->Test((int)singleIndirectIndex[iii])); 
                        freeMap->Clear((int)singleIndirectIndex[iii]);
                    }
                    ASSERT(freeMap->Test((int)doubleIndirectIndex[ii]));
                    freeMap->Clear((int)doubleIndirectIndex[ii]);
                }
                ASSERT(freeMap->Test((int)dataSectors[DoubleIndirectSectorIdx]));
                freeMap->Clear((int)dataSectors[DoubleIndirectSectorIdx]);
            }
        }
    }
    int
    FileHeader::ByteToSector(int offset)//当我们使用synchDisk->ReadSector和synchDisk->WriteSector的时候则会使用到该函数，如果计算错误则会报错“Assertion failed: line 121, file "../machine/disk.cc"”
    {
        const int directMapSize = NumDirect * SectorSize;
        const int singleIndirectMapSize = directMapSize + LevelMapNum * SectorSize;
        const int doubleIndirectMapSize = singleIndirectMapSize +  LevelMapNum * LevelMapNum * SectorSize;
        if (offset < directMapSize) {
            return (dataSectors[offset / SectorSize]);
        } else if (offset < singleIndirectMapSize) {
            const int sectorNum = (offset - directMapSize) / SectorSize;
            int singleIndirectIndex[LevelMapNum];
            synchDisk->ReadSector(dataSectors[IndirectSectorIdx], (char*)singleIndirectIndex);
            return singleIndirectIndex[sectorNum];
        } else {
            const int indexSectorNum = (offset - singleIndirectMapSize) / SectorSize / LevelMapNum;
            const int sectorNum = (offset - singleIndirectMapSize) / SectorSize % LevelMapNum;
            int doubleIndirectIndex[LevelMapNum]; 
            synchDisk->ReadSector(dataSectors[DoubleIndirectSectorIdx], (char*)doubleIndirectIndex);
            int singleIndirectIndex[LevelMapNum]; 
            synchDisk->ReadSector(doubleIndirectIndex[indexSectorNum], (char*)singleIndirectIndex);
            return singleIndirectIndex[sectorNum];
        }
    }
    void
    FileHeader::Print()
    {
        int i, j, k; //分别表示当前扇区，字节在扇区中的位置和字节在文件中的位置
        char *data = new char[SectorSize];
        printf("------------ %s -------------\n", "FileHeader contents");
        printf("File type: %s\n", fileType);
        printf("Created: %s", createdTime);
        printf("Modified: %s", modifiedTime);
        printf("Last visited: %s", lastVisitedTime);
        printf("File size: %d.  File blocks:\n", numBytes);
        int ii, iii; //与上面一样对应
        int singleIndirectIndex[LevelMapNum]; 
        int doubleIndirectIndex[LevelMapNum]; 
        printf("  Direct indexing:\n    ");
        for (i = 0; (i < numSectors) && (i < NumDirect); i++)
            printf("%d ", dataSectors[i]);
        if (numSectors > NumDirect) {
            printf("\n  Indirect indexing: (mapping table sector: %d)\n    ", dataSectors[IndirectSectorIdx]);
            synchDisk->ReadSector(dataSectors[IndirectSectorIdx], (char*)singleIndirectIndex);
            for (i = NumDirect, ii = 0; (i < numSectors) && (ii < LevelMapNum); i++, ii++)
                printf("%d ", singleIndirectIndex[ii]);
            if (numSectors > NumDirect + LevelMapNum) {
                printf("\n  Double indirect indexing: (mapping table sector: %d)", dataSectors[DoubleIndirectSectorIdx]);
                synchDisk->ReadSector(dataSectors[DoubleIndirectSectorIdx], (char*)doubleIndirectIndex);
                for (i = NumDirect + LevelMapNum, ii = 0; (i < numSectors) && (ii < LevelMapNum); ii++) {
                    printf("\n    single indirect indexing: (mapping table sector: %d)\n      ", doubleIndirectIndex[ii]);
                    synchDisk->ReadSector(doubleIndirectIndex[ii], (char*)singleIndirectIndex);
                    for (iii = 0;  (i < numSectors) && (iii < LevelMapNum); i++, iii++)
                        printf("%d ", singleIndirectIndex[iii]);
                }
            }
        }
        printf("\nFile contents:\n");
        for (i = k = 0; (i < numSectors) && (i < NumDirect); i++)
        {
            synchDisk->ReadSector(dataSectors[i], data);
            for (j = 0; (j < SectorSize) && (k < numBytes); j++, k++)
                printChar(data[j]);
            printf("\n");
        }
        if (numSectors > NumDirect) {
            synchDisk->ReadSector(dataSectors[IndirectSectorIdx], (char*)singleIndirectIndex);
            for (i = NumDirect, ii = 0; (i < numSectors) && (ii < LevelMapNum); i++, ii++) {
                synchDisk->ReadSector(singleIndirectIndex[ii], data);
                for (j = 0; (j < SectorSize) && (k < numBytes); j++, k++)
                    printChar(data[j]);
                printf("\n");
            }
            if (numSectors > NumDirect + LevelMapNum) {
                synchDisk->ReadSector(dataSectors[DoubleIndirectSectorIdx], (char*)doubleIndirectIndex);
                for (i = NumDirect + LevelMapNum, ii = 0; (i < numSectors) && (ii < LevelMapNum); ii++) {
                    synchDisk->ReadSector(doubleIndirectIndex[ii], (char*)singleIndirectIndex);
                    for (iii = 0; (i < numSectors) && (iii < LevelMapNum); i++, iii++) {
                        synchDisk->ReadSector(singleIndirectIndex[iii], data);
                        for (j = 0; (j < SectorSize) && (k < numBytes); j++, k++)
                            printChar(data[j]);
                        printf("\n");
                    }
                }
            }
        }
        printf("----------------------------------------------\n");
        delete[] data;
    }
    char*
    printChar(char oriChar)
    {
        if ('\040' <= oriChar && oriChar <= '\176') 
            printf("%c", oriChar); 
        else
            printf("\\%x", (unsigned char)oriChar); 
    }

##### 4、测试说明 #####

为了展示三个索引的功能，我分别创建了是三个文件PI1.TXT、PI3.TXT、PI112.TXT，文件大小分别为700B，3KB，112KB。分别写了三个测试脚本t4\_3\_1.sh、t4\_3\_2.sh、t4\_3\_3.sh

//t4_3_1.sh 其他三个脚本只需要修改相应文件名即可
    #!/bin/sh
    cd /opt/module/nachos_dianti/nachos-3.4/code/filesys
    echo "=== format the DISK ==="
    ./nachos -Q -f
    echo "=== copies file \"largeFile\" from UNIX to Nachos ==="
    ./nachos -Q -cp test/PI1.TXT PI1
    echo "=== prints the contents of the entire file system ==="
    ./nachos -Q -D
    
    echo "=== remove the file \"largeFile\" from Nachos ==="
    ./nachos -Q -r PI1
    
    echo "=== prints the contents of the entire file system again ==="
    ./nachos -Q -D

##### 5、测试结果截图 #####

**t4\_3\_1.sh**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70 4]

**t4\_3\_2.sh**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70 5]

**t4\_3\_3.sh**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70 6]

#### Exercise 4 实现多级目录 ####

##### 1、基本思路 #####

在多级目录下用文件路径标识文件，所以我们需要实现文件路径功能，输入的文件路径是个字符串，所以我们需要实现相关函数去解析文件路径区分什么是目录，什么是文件名。这里直接调用libgen.h下的函数实现相关函数功能。Nachos系统本身没有实现创建文件目录，因此我们还需要实现针对文件目录的相关操作，即创建目录（mkdir），删除目录(rd)，查看目录(ld)等。针对文件的操作，因为目前的文件已经不是单纯的存在根目录下了，所以针对原来的创建、打开、删除文件我们也需要进行相应的改动。

##### 2、实现文件路径 #####

首先定义一个数据结构存储文件路径，然后实现相关函数对路径进行解析，区分出目录和文件名

//filehdr.h
    #include <libgen.h> 
    #define MAX_DIR_DEPTH 5
    typedef struct {
        char* dirArray[MAX_DIR_DEPTH];
        int dirDepth; // 定义目录深度，如果为0，则为根目录
        char* base;
    } FilePath;
    extern FilePath pathParser(char* path);//实现文件路径解析功能
    //filehdr.cc
    FilePath pathParser(char* path)
    {
        if (path[0] == '/')
            path = &path[1]; //去除根
        char* ts1 = strdup(path);//拷贝路径
        char* ts2 = strdup(path);
        FilePath filepath;
        char* currentDir = dirname(ts1);//去除不是目录名的部分，只留下目录
        filepath.base = strdup(basename(ts2)); //获取文件名部分
      //统计目录深度
      int depth;
        for (depth = 0; path[depth]; path[depth] == '/' ? depth++ : *path++);
        filepath.dirDepth = depth;
        ASSERT(depth <= MAX_DIR_DEPTH);
    		//前往当前目录
        while (strcmp(currentDir, ".")) { 
            filepath.dirArray[--depth] = strdup(basename(currentDir));
            currentDir = dirname(currentDir);
        }
        return filepath;
    }

##### 3、实现多级目录 #####

这里效仿Linux、unix系统，采用系统指令mkdir创建目录、rd（相当于rm -d）递归删除目录、ld列出目录。所以我需要在main函数中实现相关的指令。

//main.cc
    extern void MakeDir(char *dirname); //MakeDir函数我放在了fstest.cc文件下，所以这里需要声明一下
    #ifdef FILESYS
    ……………………
    		else if (!strcmp(*argv, "-mkdir")) { // make directory
            ASSERT(argc > 1);
            MakeDir(*(argv + 1));//需要实现的函数功能，定义在fstest.cc文件下
            argCount = 2;
        } else if (!strcmp(*argv, "-rd")) { // remove Nachos file or directory recursively (i.e. rm -r in UNIX)
            ASSERT(argc > 1);
            bool success = fileSystem->RemoveDir(*(argv + 1));//需要实现的函数功能，声明在FileSystem类中，删除目录
            argCount = 2;
        } else if (!strcmp(*argv, "-ld")) { // list Nachos directory
            ASSERT(argc > 1);
            fileSystem->ListDir(*(argv + 1));//需要实现的函数功能，声明在FileSystem类中，列出目录
            argCount = 2;
        }

在实现上述函数相关功能之前，我们首先需要解决个问题，就是我们如何根据文件路径去定位到我们的目标文件，并且返回目标文件的目录结构。因此我在FileSystem类中重新定义两个函数FindDirSector和FindDir分别实现上面功能：

//filesys.h
    class FileSystem{
    	public:
    		void* FindDir(char *filePath); //根据文件路径返回目标文件的目录结构
        int FindDirSector(char *filePath); //根据文件路径查找目标文件是否存在
    };
    //filesys.cc
    int FileSystem::FindDirSector(char *filePath)//根据文件路径查看目标文件是否存在，若存在返回扇区号，不存在返回-1
    {
        FilePath filepath = pathParser(filePath);
        int sector = DirectorySector; //从根目录所在扇区开始
        if(filepath.dirDepth != 0) { //不在根目录下
            OpenFile* dirFile;
            Directory* dirTemp;
            for(int i = 0; i < filepath.dirDepth; i++) {//根据目录深度查找目标文件扇区
                DEBUG('D', "Finding directory \"%s\" in sector \"%d\"\n", filepath.dirArray[i], sector);
                dirFile = new OpenFile(sector);
                dirTemp = new Directory(NumDirEntries);
                dirTemp->FetchFrom(dirFile);//从目标文件中读入目录结构
                sector = dirTemp->Find(filepath.dirArray[i]);//在目录下查找目标文件扇区，不存在返回-1
                if (sector == -1)
                    break; 
            }
            delete dirFile;
            delete dirTemp;
        }
        return sector;//返回目标文件所在扇区
    }
    void* FileSystem::FindDir(char *filePath)根据文件路径返回目标文件的目录结构
    {
        Directory* returnDir = new Directory(NumDirEntries);
        int sector = FindDirSector(filePath);//返回目标文件的扇区号
        if(sector == DirectorySector) { //目标文件在根目录下
            returnDir->FetchFrom(directoryFile);//返回根目录结构
        } else if (sector != -1) {//存在目标文件
            OpenFile* dirFile = new OpenFile(sector);
            returnDir->FetchFrom(dirFile);///读入目标文件的目录结构
            delete dirFile;
        } else {
            DEBUG('D', "No such directory. (might be deleted)\n");
        }
        return (void *)returnDir;//返回目标文件的目录结构
    }
    //FindDir的类型本来应该为Directory*，但是我在头文件中导入derectory.h时运行一直报错，很无解，所以这里使用void*，后续使用Directory*进行强制转换

通过上述函数已经可以在多级目录结构下定位到目标文件和返回目标文件的目录结构，因此我们可以针对多级目录进行相关操作了。即实现目录的相关函数 MakeDir、fileSystem->RemoveDir、fileSystem->ListDir和修改文件的相关函数fileSystem->Create，fileSystem->Open，fileSystem->Remove。

//1、首先实现 MakeDir创建目录功能，创建目录我直接调用系统实现的fileSystem->Create创建文件的功能，为了区分文件名和目录名一个比较简便的方法就是通过文件后缀来区分，因此我通过添加.DirF的后缀表示该文件为目录，同时才调用fileSystem->Create函数的时候，通过设置initialSize=-1来表示我要创建目录。
    //所以实现 MakeDir之前需要先修改fileSystem->Create函数，同时因为因为目前实现了多级目录，所以除了做上述功能修改之外还需要进行多级目录下的改动
    //filesys.cc
    #define DirFileExt "DirF"
    bool	FileSystem::Create(char *name, int initialSize)
    {
        ………………
       	int sector;
        bool success;
        bool isDir = FALSE;//通过isDir表示来判断需要创建目录还是文件
        if (initialSize == -1) {//创建目录
            isDir = TRUE;
            initialSize = DirectoryFileSize;
            DEBUG('f', "Creating directory %s, size %d\n", name, initialSize);
        } 
      	else
        	DEBUG('f', "Creating file %s, size %d\n", name, initialSize);//
        directory = new Directory(NumDirEntries);
      	//找到目录扇区并打开目录文件
        int dirSector = FindDirSector(name);
        ASSERT(dirSector != -1);
        OpenFile* dirFile = new OpenFile(dirSector);
        directory->FetchFrom(dirFile);
        FilePath filepath = pathParser(name);
        if (filepath.dirDepth > 0) {
            name = filepath.base;
        }
        if (directory->Find(name) != -1)//判断文件是否存在
          	success = FALSE;	
        else {	
            …………
        		if (sector == -1) //判断是否还有空闲扇区		
                success = FALSE;		
            else if (!directory->Add(name, sector))//判断该目录下是否还有位置
                success = FALSE;	
    				else {
        	    	……………………	
    	    			else {	
    	    					success = TRUE;
                		if (isDir)//如果创建目录，则添加后缀DirF
                        hdr->HeaderCreateInit(DirFileExt);
                		else
                    		hdr->HeaderCreateInit(getFileExtension(name));
        	    			hdr->WriteBack(sector); 		
                		if(isDir) {
                        Directory* dir = new Directory(NumDirEntries);//创建新的目录对象
                        OpenFile* subDirFile = new OpenFile(sector);//打开头文件
                        dir->WriteBack(subDirFile);//将目录对象写入该文件
                        delete dir;
                        delete subDirFile;
                    }
                    directory->WriteBack(dirFile);
                    delete dirFile;
        	    			freeMap->WriteBack(freeMapFile);
    	    			}
                ……………………
    }
    //现在可以实现创建MakeDir功能了
    //fstest.cc
    void MakeDir(char *dirname)
    {
        DEBUG('D',"Making directory: %s\n", dirname);
        fileSystem->Create(dirname, -1);
    }
    //2、实现fileSystem->RemoveDir，该函数的逻辑和fileSystem->Remove的逻辑是一样的，只不过增加了多层目录的相关功能
    //filesys.cc(别忘了去filesys.h中进行声明)
    bool FileSystem::RemoveDir(char *name)
    { 
        Directory *directory;
        BitMap *freeMap;
        FileHeader *fileHdr;
        int sector;
        directory = (Directory*)FindDir(name);
        FilePath filepath = pathParser(name);
        if (filepath.dirDepth > 0) {
            name = filepath.base;
        }
        sector = directory->Find(name);
        if (sector == -1) {
           delete directory;
           return FALSE;             
        }
        fileHdr = new FileHeader;
        fileHdr->FetchFrom(sector);
        freeMap = new BitMap(NumSectors);
        freeMap->FetchFrom(freeMapFile);
        fileHdr->Deallocate(freeMap);       //删除数据块
        freeMap->Clear(sector);         // 删除头
        directory->Remove(name);
        freeMap->WriteBack(freeMapFile);        
        directory->WriteBack(directoryFile);        
        delete fileHdr;
        delete directory;
        delete freeMap;
        return TRUE;
    }
    //3、实现fileSystem->ListDir，该函数的逻辑和fileSystem->List的逻辑是一样的
    //filesys.cc(别忘了去filesys.h中进行声明)     
    void FileSystem::ListDir(char* name)
    {
        printf("List Directory: %s\n", name);
        Directory *directory = (Directory*)FindDir(strcat(name, "/arbitrary"));
        directory->List();
        delete directory;
    }
    //4、修改fileSystem->Open和fileSystem->Remove。主要就是因为去要重新定位文件位置
    #define IsDirFile(fileHdr) (!strcmp(fileHdr->getFileType(), DirFileExt))//判断文件后缀是否是目录
    //getFileType()还未声明需要先声明
    class FileHeader {
      public:
      	char* getFileType() { return strdup(fileType); }
    };
    bool FileSystem::Remove(char *name)
    { 
        ………………
        int sector;
        directory = (Directory*)FindDir(name);
        FilePath filepath = pathParser(name);
        if (filepath.dirDepth > 0) {
            name = filepath.base;
        }
    		………………
        fileHdr->FetchFrom(sector);
        if(IsDirFile(fileHdr)) {
            DEBUG('D',"Reject the remove operation (attempt to delete a directory).\n");
            delete directory;
            delete fileHdr;
            return FALSE; // directory File
        }
    		……………………
    } 
    OpenFile * FileSystem::Open(char *name)
    { 
    		………………
        DEBUG('f', "Opening file %s\n", name);
        directory = (Directory*)FindDir(name);
        FilePath filepath = pathParser(name);
        if (filepath.dirDepth > 0) {
            name = filepath.base;
        }
        ……………………
    }

##### 4、测试说明 #####

我写了一个脚本去生成多级目录，目录结构如下：

*  /
    
     *  folder/ (directory)
        
         *  test/ (directory)
            
             *  small (file)
         *  dir/ (directory)
            
             *  third/ (directory)
         *  big (file)

#t4_4.sh
    #!/bin/sh
    cd /opt/module/nachos_dianti/nachos-3.4/code/filesys
    
    # use -Q to disable verbose machine messages
    echo "=== format the DISK ==="
    ./nachos -Q -f
    echo "=== create a directory called \"folder\""
    ./nachos -Q -d D -mkdir folder
    echo "=== create additional two directories called \"test\" \"dir\" in \"folder\""
    ./nachos -Q -d D -mkdir folder/test
    ./nachos -Q -d D -mkdir folder/dir
    echo "=== create another directory called \"third\" in \"dir/folder\""
    ./nachos -Q -d D -mkdir folder/dir/third
    
    echo "=== copies file \"big\" to \"folder\" ==="
    ./nachos -Q -cp test/big folder/big
    echo "=== copies file \"small\" to \"folder/test\" ==="
    ./nachos -Q -cp test/small folder/test/small
    
    echo "=== list each folder ==="
    ./nachos -Q -l
    ./nachos -Q -ld folder
    ./nachos -Q -ld folder/test
    ./nachos -Q -ld folder/dir
    ./nachos -Q -ld folder/dir/third
    echo "=== prints the contents of the entire file system ==="
    ./nachos -Q -D
    
    echo "=== test delete folder with \"-r\" which should fail"
    ./nachos -Q -d D -r folder
    echo "=== remove the file \"folder/test/small\" using recursive delete ==="
    ./nachos -Q -rd folder/test/small
    echo "=== remove the directory \"test\" (empty directory) ==="
    ./nachos -Q -rd folder/test
    echo "=== remove the directory \"folder\" recursively (non-empty directory) ==="
    ./nachos -Q -rd folder
    
    echo "=== list each folder again ==="
    ./nachos -Q -l
    ./nachos -Q -ld folder
    ./nachos -Q -ld folder/test
    ./nachos -Q -ld folder/dir
    ./nachos -Q -ld folder/dir/third

##### 5、测试结果截图 #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70 7]

#### Exercise 5 动态调整文件长度 ####

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

##### 1、基本思路 #####

修改filehdr.cc文件，添加ExpandFileSize函数，基本功能就是实现文件长度的增长。首先修改文件长度，获得增长前扇区数量，计算增长后扇区数量，如果增长前后扇区数量相同，那么不需要额外空间，否则检查剩余额外空间，如果剩余空间不能满足需求，那么返回错误，否则进行相关的空间分配。

##### 2、开始前准备 #####

在修改代码之前，我们先测试下不能动态调整文件长度下测试需要动态增长文件的情况。系统提供了-t参数调用在代码/filesys/fstest.cc中定义的PerformanceTest。此测试功能将继续写入内容（“ 1234567890”）5000次。然后阅读并最终将其删除。因为5000次太大了，所以我将次数设置为10次。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70 8]

可以看到他无法进行读写TestFile。

##### 3、实现ExpandFileSize函数 #####

在FileHeader中，定义了两个私有变量numBytes和numSectors，我们将使用这两个变量实现ExpandFileSize。

//filehdr.h
    class FileHeader {
      public:
      	bool ExpandFileSize(BitMap *freeMap, int additionalBytes);
    };
    //filehdr.cc
    bool FileHeader::ExpandFileSize(BitMap *freeMap, int additionalBytes)
    {
        ASSERT(additionalBytes > 0);
        numBytes += additionalBytes;
        int initSector = numSectors;//获得增长前扇区数量
        numSectors = divRoundUp(numBytes, SectorSize);//计算增长后扇区数量
        if (initSector == numSectors) {//相同则不需要额外空间
            return TRUE; 
        }
        int sectorsToExpand = numSectors - initSector;
        if (freeMap->NumClear() < sectorsToExpand) {//没有空间返回false
            return FALSE; 
        }
        DEBUG('f',"Expanding file size for %d sectors (%d bytes)\n", sectorsToExpand, additionalBytes);
        for (int i = initSector; i < numSectors; i++)//有空间则继续分配
            dataSectors[i] = freeMap->Find();
        return TRUE;
    }

##### 4、修改OpenFile :: WriteAt函数 #####

上述情况在“写”时发生。因此，我在代码/filesys/openfile.cc中修改了OpenFile :: WriteAt。当我们想用numBytes写入位置时，首先检查空间是否足够。如果不是，则调整文件头的大小并更新fileLength。

#define FreeMapSector       0
    int OpenFile::WriteAt(char *from, int numBytes, int position)
    {
        int fileLength = hdr->FileLength();
        ...
        if (position + numBytes > fileLength) {
            BitMap *freeMap = new BitMap(NumSectors);
            OpenFile* freeMapFile = new OpenFile(FreeMapSector);
            freeMap->FetchFrom(freeMapFile);
            hdr->ExpandFileSize(freeMap, position + numBytes - fileLength);
            hdr->WriteBack(hdr->getHeaderSector());
            freeMap->WriteBack(freeMapFile);
            delete freeMapFile;
            fileLength = hdr->FileLength();
        }
        ...
    }

##### 5、测试结果 #####

重新运行一下最开始的测试函数

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70 9]

可以发现成功实现了扩展。

### 二、文件访问的同步与互斥 ###

#### Exercise 6 源代码阅读 ####

##### a) 阅读Nachos源代码中与异步磁盘相关的代码，理解Nachos系统中异步访问模拟磁盘的工作原理。 #####

filesys/synchdisk.h和filesys/synchdisk.cc

Nachos 模拟的磁盘是异步设备。当发出访问磁盘的请求后立刻返回，当从磁盘读出或写入数据结束后，发出磁盘中断，说明一次磁盘访问真正结束。Nachos 是一个多线程的系统，如果多个线程同时对磁盘进行访问，会引起系统的混乱。所以必须作出这样的限制：

*  同时只能有一个线程访问磁盘
 *  当发出磁盘访问请求后，必须等待访问的真正结束。 这两个限制就是实现同步磁盘的目的。

SynchDisk 的类定义和实现如下所示：

class SynchDisk {
      public:
        SynchDisk(char* name); //生成一个同步磁盘 		
        ~SynchDisk();			//析构方法
        void ReadSector(int sectorNumber, char* data);//同步读写磁盘，只有当真正读写完毕后返回
        void WriteSector(int sectorNumber, char* data);
        void RequestDone();		//磁盘中断处理时调用
      private:
        Disk *disk;		//物理异步磁盘设备  		
        Semaphore *semaphore; //控制读写磁盘返回的信号量			
        Lock *lock;	//控制只有一个线程访问的锁	  		
    					
    };

以 ReadSector 为例来说明同步磁盘的工作机制：

void
    SynchDisk::ReadSector(int sectorNumber, char* data)
    {
        lock->Acquire();			// 加锁（一次只允许一个线程访问磁盘）
        disk->ReadRequest(sectorNumber, data);// 对磁盘进行读访问请求
        semaphore->P();			// 等待磁盘中断的到来
        lock->Release();	//解锁（访问结束）
    }

当线程向磁盘设备发出读访问请求后，等待磁盘中断的到来。一旦磁盘中断来到，中断处理 程序执行 semaphore->V()操作，ReadSector 得以继续运行。对磁盘同步写也基于同样的原理。

##### b) 利用异步访问模拟磁盘的工作原理，在Class Console的基础上，实现Class SynchConsole。 #####

**1、基本思路**

正如题目所描述的，我直接仿照Console实现SynchConsole，基本上只需要按照Console的相关操作去定义SynchConsole的操作即可。

**2、console.h**

首先在console.h中在Console基础上添加一个SynchConsole来，类里的方法和Console中一样，私有变量在Console的基础上进行定义。

#include "synch.h"
    class SynchConsole {
      public:
        SynchConsole(char *readFile, char *writeFile); //初始化硬件控制台设备
        ~SynchConsole(); //清理控制台                              
        void PutChar(char ch);//把字符串放到控制台显示，输出完毕后进行中断处理，中断处理函数是WriteDone
        char GetChar(); //轮询控制台输入。如果一个字符可用，则返回它。否则,返回EOF。每当有一个字符要获取时，就进行中断处理调用ReadAvail
        void WriteDone(); // 向I/O完成发送信号
        void ReadAvail();
    private:
        Console *console;//已经实现的console
        Lock *lock;//互斥锁
        Semaphore *semaphoreReadAvail;//同步信号量读
        Semaphore *semaphoreWriteDone;//同步信号量写
    };

**3、console.cc**

实现console.h中的相关方法，里面的所有方法都是仿照console实现的，功能也相似，如果有不能理解的地方可以直接看console的相关注释。

static void SynchConsoleReadAvail(int sc)
    { SynchConsole *console = (SynchConsole *)sc; console->ReadAvail(); }
    static void SynchConsoleWriteDone(int sc)
    { SynchConsole *console = (SynchConsole *)sc; console->WriteDone(); }
    SynchConsole::SynchConsole(char *readFile, char *writeFile)
    {
        lock = new Lock("synch console");
        semaphoreReadAvail = new Semaphore("synch console read avail", 0);
        semaphoreWriteDone = new Semaphore("synch console write done", 0);
        console = new Console(readFile, writeFile, SynchConsoleReadAvail, SynchConsoleWriteDone, (int)this);
    }
    SynchConsole::~SynchConsole()
    {
        delete console;
        delete lock;
        delete semaphoreReadAvail;
        delete semaphoreWriteDone;
    }
    void SynchConsole::PutChar(char ch)
    {
        lock->Acquire();
        console->PutChar(ch);
        semaphoreWriteDone->P();
        lock->Release();
    }
    char SynchConsole::GetChar()
    {
        lock->Acquire();
        semaphoreReadAvail->P();
        char ch = console->GetChar();
        lock->Release();
        return ch;
    }
    void SynchConsole::WriteDone()
    {
        semaphoreWriteDone->V();
    }
    void SynchConsole::ReadAvail()
    {
        semaphoreReadAvail->V();
    }

**4、userprog/progtest.cc**

仿照ConsoleTest在progtest.cc文件中实现SynchConsoleTest

static SynchConsole *synchConsole;
    void SynchConsoleTest (char *in, char *out)
    {
        char ch;
        synchConsole = new SynchConsole(in, out);
        for (;;) {
            ch = synchConsole->GetChar();
            synchConsole->PutChar(ch); 
            if (ch == 'q')//若输入的是q则退出
                return; 
        }
    }

**5、main.cc**

在main中定义了-c参数可以调用ConsoleTest，因此仿照其定义了-sc参数可以调用SynchConsoleTest。

extern void SynchConsoleTest(char *in, char *out); 
    int main(int argc, char **argv)
    {
    #ifdef USER_PROGRAM
        ...
            } else if (!strcmp(*argv, "-sc")) { 
                if (argc == 1) {
                    SynchConsoleTest(NULL, NULL);
                } else {
                    ASSERT(argc > 2);
                    SynchConsoleTest(*(argv + 1), *(argv + 2));
                    argCount = 3;
                }
                interrupt->Halt(); 
            }
    #endif // USER_PROGRAM

**6、测试结果**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70 10]

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

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

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

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

> 做这部分的时候我遇到很多我很不能理解的bug，但是我这不好写下来，如果你也遇到，可以私信我交流 ！

##### 1、a,b) 的解决方案 #####

当前open函数是每次打开就新建一个OpenFile对象，可以实现一个文件可以同时被多个线程访问。且每个线程独自打开文件，独自拥有一个当前文件访问位置，彼此间不会互相干扰。

**（1）synchdisk.h**

class SynchDisk {
      public:
        void PlusReader(int sector);//写者写时申请锁
        void MinusReader(int sector);//写者结束写时释放锁
        void BeginWrite(int sector);//读者开始读时申请锁
        void EndWrite(int sector);//读者结束读时释放锁
      private:
        Semaphore *mutex[NumSectors];//为每个文件分配锁
        int numReaders[NumSectors];//记录文件头
        Lock *readerLock;//读者锁
    };

**（2）synchdisk.cc**

SynchDisk::SynchDisk(char* name)
    {
    ………………
        readerLock = new Lock("ReaderLock");
        for(int i=0;i<NumSectors;i++)
        {
            numReaders[i]=0;
            mutex[i]=new Semaphore("Lock",1);
        }
    }
    void SynchDisk::PlusReader(int sector)
    {
        readerLock->Acquire();
        numReaders[sector]++;
        if(numReaders[sector]==1)
            mutex[sector]->P();
        printf("reader cnt: %d\n", numReaders[sector]);
        readerLock->Release();
    }
    void SynchDisk::MinusReader(int sector)
    {
        readerLock->Acquire();
        numReaders[sector]--;
        if(numReaders[sector]==0)
            mutex[sector]->V();
        printf("reader cnt: %d\n", numReaders[sector]);
        readerLock->Release();
    }
    void SynchDisk::BeginWrite(int sector)
    {
        mutex[sector]->P();
    }
    void SynchDisk::EndWrite(int sector)
    {
        mutex[sector]->V();
    }

**（3）测试程序**

//fstest.cc
    void write()
    {
        OpenFile *openFile;    
        int i, numBytes;
        if (!fileSystem->Create(FileName, 0)) {
          printf("Perf test: can't create %s\n", FileName);
          return;
        }
        openFile = fileSystem->Open(FileName);
        if (openFile == NULL) {
        printf("Perf test: unable to open %s\n", FileName);
        return;
        }
        printf("begin writing\n");
        numBytes=openFile->Write(Contents,ContentSize);
        printf("end writing\n");
        delete openFile;    // close file
    }
    void read(int which)
    {
        printf("%s start\n",currentThread->getName());
        OpenFile *openFile;
        char *buffer = new char[ContentSize+1];
        int i,numBytes;
        if((openFile=fileSystem->Open(FileName))==NULL){
            printf("Perf test: unable to Open file %s\n",FileName);
            delete [] buffer;
            return;
        }
        printf("begin reading\n");
        printf("%s's size is %d\n",FileName,openFile->Length());
        numBytes = openFile->Read(buffer,ContentSize);
        printf("read %d bytes\n",numBytes);
        buffer[ContentSize]='\0';
        printf("read Content: %s\n",buffer);
        printf("end reading\n");
        delete [] buffer;
        delete openFile;
    
        if (!fileSystem->Remove(FileName)) {
          printf("Perf test: unable to remove %s\n", FileName);
          return;
        }
    
    }
    void PerformanceTest1()
    {
        printf("Starting file system performance test:\n");
        Thread* thread1 = new Thread("reader1");
        thread1->Fork(read,7);
        write();
    }
    //main.cc
    //仿照-t添加-t1参数调用PerformanceTest1()

**（4）测试结果**

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-LjCRVngJ-1607692459518)(/Users/jaggerqian/Library/Application Support/typora-user-images/image-20201211202033296.png)\]][img-LjCRVngJ-1607692459518_Users_jaggerqian_Library_Application Support_typora-user-images_image-20201211202033296.png]

##### 2、c)解决方案 #####

因为我们想要当没有线程访问文件的时候才能删除文件，所以我们需要一个定义一个统计访问文件的线程数量的变量。然后在每次打开文件的时候让这变量+1

**（1）synchdisk.h**

class SynchDisk {
      public:
        int numVisitors[NumSectors];
    };

**（2）openfile.cc**

OpenFile::OpenFile(int sector)
    { 
        ………………
        synchDisk->numVisitors[hdr->getHeaderSector()]++;
    }
    OpenFile::~OpenFile()
    {
        ………………
        synchDisk->numVisitors[hdr->getHeaderSector()]++;
        delete hdr;
    }
    bool
    FileSystem::Remove(char *name)
    { 
        ………………
        if(synchDisk->numVisitors[sector])
        {
            printf("unable to remove thr file,there are still %d visitors\n",synchDisk->numVisitors[sector]);
            return FALSE;
        }
        else
        {
            freeMap = new BitMap(NumSectors);
            ………………
            return TRUE;
        }
    }

**（3）测试结果**

依然使用上一个测试程序  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70 11]

### 三、Challenges题目（至少选做1个） ###

#### Challenge 1 性能优化 ####

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

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

**TODO**

#### Challenge 2 实现pipe机制 ####

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

##### 1、基本思路 #####

使用管道文件模拟管道的实现，管道文件头定义在第二个扇区，然后定义两个函数分别用来向管道中写入数据和读出数据。

##### 2、filesys.cc #####

#define PipeSector 2
    FileSystem::FileSystem(bool format)
    { 
    		…………
         FileHeader *pipeHdr = new FileHeader;
         freeMap->Mark(PipeSector);
         pipeHdr->WriteBack(PipeSector);
    }
    //别忘了去类里声明
    int FileSystem::ReadPipe(char * data){//
        FileHeader *fileHdr;
        fileHdr = new FileHeader;
        fileHdr->FetchFrom(PipeSector);
        int length=fileHdr->getnumBytes();
        fileHdr->WriteBack(PipeSector);
        OpenFile *pipe_file=new OpenFile(PipeSector);
        pipe_file->Read(data,length);
        printf("reading data from the pipe\n");
        delete pipe_file;
        return length;
    }
    void FileSystem::WritePipe(char *data,int length)
    {
        OpenFile *pipe_file = new OpenFile(PipeSector);
        pipe_file->Write(data,length);
        printf("writing data into the pipe\n");
        delete pipe_file;
        FileHeader *fileHdr;
        fileHdr = new FileHeader;
        fileHdr->FetchFrom(PipeSector);
        fileHdr->setnumBytes(length);
        fileHdr->WriteBack(PipeSector);
    }

##### 3、测试程序 #####

写了测试程序PerformanceTest4()，PerformanceTest5()分别在main.cc里面使用-t4和-t5调用。PerformanceTest4()表示将数据写入管道，PerformanceTest5()表示将数据从管道读出并显示在控制台。

void PerformanceTest4()
    {
        printf("thread 1 wrte data to the pipe\n");
        char input_str[SectorSize+1];
        printf("input: ");
        scanf("%s",input_str);
        fileSystem->WritePipe(input_str,strlen(input_str));
    }
    void PerformanceTest5()
    {
        printf("thread 2 read data from the pipe\n");
        char data[SectorSize+1];
        int length=fileSystem->ReadPipe(data);
        data[length]='\0';
        printf("%s\n",data);
    }

##### 4、测试结果 #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70 12]

## 内容四：遇到的困难以及解决方法 ##

这个实验遇到的困难实在太多了，很多我在文档里面已经写的很清楚了就不做说明了！要是大家遇到我没说明的问题可以私信交流！

## 内容五：收获及感想 ##

这次实验太难了，难于上青天，花了我一个星期的时间！

## 内容六：对课程的意见和建议 ##

这是一门非常值得推荐的课。

## 内容七：参考文献 ##

*  \[1\] [Nachos中文教程][Nachos]
 *  \[2\] [文件系统实习报告][Link 1]
 *  \[3\] [文件系统实习报告][Link 2]

[img-ogNystap-1607692459509_Users_jaggerqian_Library_Application Support_typora-user-images_image-20201204160256504.png]: /images/20221120/0debf7d4223546ebb1fd61d3051e7d9f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70]: /images/20221120/dbc573f796d44fc7b1ca1e32520b6028.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70 1]: /images/20221120/ddf1caa0b6444ffd88ed8ab2149e1770.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70 2]: /images/20221120/4e0948dabefa44e3b9444102f28fec21.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70 3]: /images/20221120/1b5a4f58415e48c3b10e583417ea8919.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70 4]: /images/20221120/ba4899f88b784bab8712514722868f25.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70 5]: /images/20221120/1f463da8ece84f3597487ee6b8ac6258.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70 6]: /images/20221120/b9081596221b4e849337a79201028da5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70 7]: /images/20221120/eb57498cea624856bb3e0a3496e1e9fd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70 8]: /images/20221120/5c7eaf44680546a3af185bb303f8b846.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70 9]: /images/20221120/f2a54664226b405684c8312ae57fe625.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70 10]: https://img-blog.csdnimg.cn/20201211211915715.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4,size_16,color_FFFFFF,t_70
[img-LjCRVngJ-1607692459518_Users_jaggerqian_Library_Application Support_typora-user-images_image-20201211202033296.png]: https://img-blog.csdnimg.cn/20201214223039888.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70 11]: https://img-blog.csdnimg.cn/20201217221101117.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70 12]: https://img-blog.csdnimg.cn/20201211211951689.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4,size_16,color_FFFFFF,t_70
[Nachos]: https://wenku.baidu.com/view/400357de5022aaea998f0fb0.html
[Link 1]: https://icoty.github.io/2019/05/14/nachos-3-4-Lab3/
[Link 2]: https://github.com/daviddwlee84/OperatingSystem/