nachos考试复习.doc

1.在nachos中，一个扇区为128个字节。 2.一个磁盘（Disk）划分为：Bitmap、根目录，Fileheader，文件内容 3.在一个Fileheader(头文件)里包可以分为：文件大小（1个Int，即为4字节）、sectors的个数（1个Int，即为4字节），所以还剩128-2*4=120字节，120字节/4字节=30个索引号 NumDirect*SectorSize=30*128=38404KB，所以最大不超过4KB1、DISK前两个扇区：Bitmap和根目录2、存储块4K，怎么突破，增加二级索引改直接索引为间接索引，以突破文件长度不得超过4KB的限制。答：需修改filesys文件夹中的filehdr.h和filehdr.cc。由于原本文件索引dataSectors的大小最大只有NumDirect，即为30，并且是直接索引，所以文件大小被限制在4k。我们可以把dataSectors中的最后一位改为一个间接索引。此时文件大小最大为(NumDirect+NumIndirect-1)* SectorSize)。在filehdr.h中添加一个常量NumIndirect，值为(SectorSize / sizeof(int)，即为存放一个扇区索引的文件大小。并修改MaxFileSize为(NumDirect+NumIndirect-1)* SectorSize)。与此同时，还需要修改Allocate方法、Deallocate方法、ByteToSector方法和Print方法。Allocate方法：当numSectors小于等于NumDirect时，我们并不需要建立间接索引，可以直接建立直接索引。当numSectors大于NumDirect时，需要建立间接索引dataSectors2，等freeMap设置好后，将间接索引表写入sector中。Deallocate方法：和Allocate方法一样，当numSectors小于等于NumDirect时，只需要直接将freeMap中的dataSector值清0；当numSectors大于Numdirect时，需要先将间接索引从硬盘读入，再逐个的将直接索引表和间接索引表对应的freeMap中的值清0。表示将空间释放。ByteToSector方法：同样，需要对offset是在直接索引中，还是在间接索引中作出判断。Print方法：同Deallocate方法，只是并不是对freeMap中的值清0，而是通过所得的索引在硬盘中取值，然后打印出来。3、二级索引怎么使用：将磁盘块索引dataSectors中的最后一位改为一个间接索引4、添加文件属性在哪里添加，在fileheader里面5、线程五个状态 就绪、运行、阻塞、挂起、结束6、创建完成属于就绪状态-s，单步调试-l，list，相当于dir一般选项：-d:显示特定的调试信息-rs:使得线程可以随机切换-z:打印版权信息和用户进程有关的选项：-s:使用户进程进入单步调试模式-x:执行一个用户程序-c:测试终端输入输出和文件系统有关的选项：-f:格式化模拟磁盘-cp:将一个文件从宿主机拷贝到Nachos模拟磁盘上-p:将Nachos磁盘上的文件显示出来-r:将一个文件从Nachos模拟磁盘上删除-l:列出Nachos模拟磁盘上的文件-D:打印出Nachos文件系统的内容-t:测试Nachos文件系统的效率第五组：1.tlb缺页中断用的什么算法，思想是什么（第三次实习）：LRU算法TLB转换表是由硬件实现的,表的尺寸一般小于用户程序的页面数.因此在转换中会出现转换失败的情况,从而发生PageFaultException 异常此处更新策略采用FIFO。具体实现方式是在machine对象中添加队列指针stepOfTLB，用以循环利用TLB。至于LRU算法的采用，放在了pageTable缺页中断的试验中了TLB表中只存放一部分逻辑页到物理页的转换关系。这样就可能出现逻辑地址转换失败的现象，会发生PageFaultException异常。在该异常处理程序中，就需要借助用户进程空间的线性页面转换表来计算出物理页，同时TLB表中增加一项。如果TLB表已满，就需要对TLB表项做LRU替换。使用TLB页面转换表处理起来逻辑较线性表为复杂，但是速度要快得多。由于TLB转换页表是硬件实现的，所以指向TLB转换页表的指针应该是只读的，所以Machine类一旦实例化，TLB指针值不能改动。2.synDisk（同步磁盘）：信号量和锁有什么不同，实现上有什么不同信号量的私有属性有信号量的值，它是一个阀门。线程等待队列中存放所有等待该信号量的线程。信号量有两个操作：P操作和V操作，这两个操作都是原子操作。锁机制是线程进入临界区的工具。一个锁有两种状态，BUSY和FREE。当锁处于FREE态时，线程可以取得该锁后进入临界区，执行完临界区操作之后，释放锁；当锁处于BUSY态时，需要申请该锁的线程进入睡眠状态，等到锁为FREE态时，再取得该锁。3.文件系统之间的切换（linux自身的切换，自己增加的代码）第四组：2.怎么实现多级目录：修改filesys文件中的dirctory.h、dirctory.cc文件。用二叉树实现多级目录。首先，我们为每一个 DirectoryEntry 添加两个属性leftchild 和5rightchild，分别记录了左亲子节点和右亲子节点所在table数组中的下标号。这样，我们通过使用该节点的这两个属性，就可以找到该节点的左亲子节点和右亲子节点了。同时，文件应当分为两种类型，一种是文件类型，一种是文件夹类型。文件类型：DirectoryEntry 的Type 属性为F。DirectoryEntry 的Sector 属性中存放的是文件的FileHeader 所在的硬盘块号。DirectoryEntry 的leftchild 应当永远为-1。文件夹类型：DirectoryEntry 的Type 属性为W。DirectoryEntry 的Sector 属性应当永远为-1。既然涉及到多级目录，必然会涉及到文件的路径问题，路径中不同元素之间以符号分割（在C+的字符串中表示反斜杠需要用来表示）。这里规定一个根目录 root，默认存放在table0中，为整个目录树的根节点。路径分析函数设计：int AnalyzePath(char *path);该函数算法的设计思路很简单，将路径字符串以符号进行分割，按分割后的路径元素从root 依次进行树的层次遍历查找，找到则返回该文件在table数组中的下标号，未找到则返回错误。转换到二叉树上，就是从 root 节点开始，按序访问root 以及它的右亲子节点，比较其文件名和当前路径分割元素，如果相同则在它的左亲子节点以及左亲子节点的所有右亲子节点中查找下一个元素。为了添加节点，我们只需要通过AnalyzePath 函数找到该文件要被添加至的文件夹，而后查看它的leftchild 节点是否为-1，如果是则将它的leftchild 赋值给数组下标值。否则，查找它的左亲子节点的右亲子节点，直到找到一个右亲子节点为-1 的节点，并将数组下标赋值给该节点的rightchild 即可。文件目录的删除算法：bool Add(char *name, int newSector, char *path, char type);首先我们要对文件的类型进行判断，如果是普通文件则直接删除。而如果是目录文件，则需要采用一定算法遍历并删除以它为根节点的整棵子树。采用后根遍历的算法来进行遍历删除。该算法首先将根节点进栈。之后进行如下循环：1. 判断栈是否为空，是则退出。2. 出栈一个节点并使其成为当前节点，判断当前节点是否是叶子节点（左右节点是否都为空）3. 如果是，则删除该节点，并回到步骤 2。否则继续向下执行。4. 按照当前节点-当前节点的右亲子节点-当前节点的左亲子节点的顺序依次进栈（当然要判断节点非空才进栈）。5. 回到步骤 2。3.虚拟内存实现的机制 Nachos基本的地址转换机制： 单用户程序：虚拟地址=物理地址 相关函数：translate.cc中Machine:Translate (int virtAddr, int* physAddr, int size, bool writing)4.文件系统的结构nachos的文件系统是单目录结构，通过接口FileSystem提供。有两个函数： OpenFile open(String name, boolean create)和 boolean remove(String name)open接受文件名（name）和新建标记（create），如果文件顺利打开，返回一个OpenFile，否则，返回nullremove接受文件名（name）,如果返回true，代表文件顺利删除OpenFile是一个抽象类，它可以代表一个在磁盘上的文件或一个控制台的读写。OpenFile+-SynchConsole.File+-OpenFileWithPosition +-StubOpenFile +-ArrayFileOpenFile: 类似于一个接口，什么都做不成SynchConsole.File: 控制台的抽象文件OpenFileWithPosition: 可以随机读写的文件StubOpenFile: 见下ArrayFile: 把一个byte数组包装成文件，用于Lib.cloneFile。接口FileSystem目前只有一个实现StubFileSystem。StubFileSystem通过在真实的OS上创建文件来模拟。5.系统调用的执行过程用户程序陷入系统调用的时候会抛出一个(异常)中断NOFFMachine.run()的过程简介1 设置执行状态为用户态2 循环执行每条指令 2.1 从内存中读取指令 2.2 译码 执行该指令 2.3 是否有中断发生：在userprog文件夹下的exception.cc中修改。在ExceptionHandler函数中加入两个switch语句，首先判断which是否是SyscallException类型的，再通过type来判断中断类型。Create系统调用：首先通过r4中的值，将文件名读入内存中。再调用fileSystem的Create方法，直接创建该文件。最后维护前后PCReg的值，每个系统调用的最后都需要加上这步，之后不再赘述。Open系统调用：依然通过r4，将文件名读入内存中。调用fileSystem的Open函数将文件名问为filename的文件打开。并设置point。Close系统调用：r4中存储的是文件打开控制，直接将其删除。Write系统调用：从指定位置(r6)读取指定个字节(r5)，放到指定缓冲区(r4)。这些指定由用户程序决定。r6 可以是文件，或者是控制台(r6=1时)。再通过machine的ReadMem方法由内存向buffer中写入数据，即为将内存中的数据写入buffer中，每次读一个，循环size次。最后将buffer中的数据写入文件中。Read系统调用：从指定位置(r6)读取指定个字节(r5)，放到指定缓冲区(r4)。先将从文件中读出size大小的数据，存入缓冲区buffer中。再通过machine的WriteMem方法往内存中写入buf中的数据，即为将文件读入内存中，每次读一个，循环size次。1.ThreadRoot的入口地址#define InitialPCs0 2.oneTick什么时候会被调用OneTick的功能就是时钟前进一个单位开中断的时候调用OneTick啊3.线程优先级怎么实现的，二级目录在thread.h中，增加线程的优先级unsigned priority(越小优先级越高)。并public其析取方法。修改scheduler.cc的ReadyToRun函数：不是将thread直接Append到就绪队列，而是用了List类的SortedInsert方法插入，这样可以得到按线程priority增序排列的列表。在scheduler.cc中，增加ShouldISwitch(Thread * oldThread, Thread * newThread)函数，其功能为比较oldThread和newThread的priority，只要旧的priority小于新的priority就返回false不换（即，旧的优先级高于新的才不换，等于或者小于都