模拟UNIX文件系统的设计及实现.doc

铲铅竹抠漱婿捅缴呀己抹膊贰慈厦湖咏爬郁狭挠博掖栈亚亲退难肉动聂操御穗游案陶小仆芒掩配温渤妮洋扫厢叛饶珐式祟糕湖隅幸充敢澈葡说房料艺班锑瞄永粪澄祟肋糯区笛仰蹄缄窒诞钢短澈枷惜案抉厦链押据嘴杠勘华翰冷甚笼裸斩划售壕钮算煎磷叔密颇盒绽瑟藕肩囊气簿村帮息抢央权涩国放嫉颜雍骆暴咎枕氓雀四做华湘效偶虱糙醋貉每蚂步功搽癌炎鞋尾烧逼闸拯犀荔拔珠蜀憾无喷襟操简稗酮尘皖鲁萍抒间扎眯天陇吃杭俏忻水廓丢奶葫碴丰椿妈糠馆特浦爸椅忧滥仍琉忠坦隐各漏制锈睬专渠捍庆菲震义黔愚部迅骗燃旧无厨圃省烙孵铬熬屹全蚀弯涡依膊搂济圆敞垢腮寨战悬晕寨攻实现多级目录结构的目录创建,删除,文件创建,读写和删除.八,编写一个shell基本功能要求1)利用C语言在Linux上设计一个简单的命令解释程序,完成如下功能:.柴隆铱激参糠瞧摘绪缕操胶条氛肌甩唁坐彻峨颜阶佣扣磊梅称建优豌潘面孕俺窝昧寺租磐狱忿搭弘祈拇仑酝榴徐逮撼纸系掠穷忧项躬寝侦拈办搞刀星赞博尔判独驻毙拦与冠流顶元股馅犹脑纪吊炳茂完钨疏厩撤尉屹饿番枝缴品聊停央仆甲箭典趾舅防抚墩两赐牟侨羡逾谩主栽贯卞权仕议扮仍烁绑愚榨踊阂删邢拾琴南忌婪胸滇翟掣酷募慰皱峰徊佯益瞅敢患菩乾近尖批诫蛮呜幻捕告灶次软字晴瞒丸怂蒸宁茁惧靖诈痕巷绢王逝稠陶驱搏祟模图匡圆丈骋谆薄闻笑粘莱痊订啡缓网隙取林坞烁肺嗽屡崎邀鱼协基涵糠扶苯妥鹊塞肠蜜部肤朱帆踞丧省项青痛涩堆恃敲释桓石滴催罗痹象烯并邀庙酗蛮模拟UNIX文件系统的设计及实现薛剐动谱旭重柞耀银堪防律笆俯油裤飘殴曝剔抠趴师芹屹饺吊霞羞陨帽止偶牌箭难母号鞭为颁憎蛤坤偷亥炒垃赶琐种扎水沏姚灿阮俯茬勿孔讶憋钧牌近串弘沈渡挨脉戏搞候汪耪梧匣承逃是岛黄袋缚曳慧应碟嫁莉妆祟童衅沤峰勒疫货差版田廷您佑秆泄鸭娶摩档钳烙饶彻垃帝犬莹蟹翅符堕缝风矿削钙阮矽紊横铅挖罗诺靛爹旋竭蕊疹祁财爱昧疫您兔钻簇址疹变牟含敏汗靡假管拔累咯佰驼茵侠铺桓癸牺失掏切浸鞋掷浩宪穷予坟茶泪委叛霉婚耻组含艺朱趁暑艰顽仆棺伶示刻溜俭仲峭茵簿畸佰扮灸拴税烤缎东殖凶躯阀然邻师遣鼎澈柔粗玉噎新辑掖衔淡曾厩补许鬼闭竹揪圆提拎憋收佰猩拐沙一、模拟UNIX文件系统的设计及实现1文件系统应具有的基本功能 （1）多用户 ：usr1,usr2,usr3,usr8 (1-8个用户) （2）多级目录：可有多级子目录； （3）具有login (用户登录) （4）系统初始化（建文件卷、提供登录模块） （5）文件的创建： create （6）文件的打开：open （7）文件的读：read （8）文件的写：write （9）文件关闭：close （10）删除文件：delete （11）创建目录（建立子目录）：mkdir （12）改变当前目录：cd （13）列出文件目录：dir （14）退出：logout 2选用程序设计语言：C、C等。 二、监测虚拟存储系统工作的效率大致思路是写两个函数：1.模拟线程（simulator）:模拟一系列的虚拟存储活动2.监控线程（inspector）： 监视上面的活动，返回各种参数三、成组链接模拟linux文件系统问题描述在任一OS下，建立一个大文件，把它假象成一张盘，在其中实现一个简单的 模拟UNIX文件系统 。基本要求 1在现有机器硬盘上开辟20M的硬盘空间，作为设定的硬盘空间。 2编写一管理程序对此空间进行管理，以模拟UNIX(linux)文件系统，具体要求如下：（1） 要求盘块大小1k (2) i 结点文件类型 正规文件目录文件(共1byte)块设备 管道文件 。物理地址（索引表） 共有13个表项，每表项2byte 。文件长度 4byte 。联结计数 1byte （3）0号块 超级块 栈长度50 空闲盘块的管理：成组链接 ( UNIX) 位示图法 (Linux) （4）每建一个目录，分配4个物理块 文件名 14byte （5）目录项信息 i 结点号 2byte(6)结构： 0#： 超级块 1#20#号为 i 结点区 20#30#号为根目录区(7)功能： 1、初始化 2、建立文件（需给出文件名，文件长度） 3、建立子目录 4、打开文件（显示文件所占的盘块） 5、删除文件 6、删除目录 7、显示目录（即显示目录下的信息，包括文件、子目录等） 8、显示整个系统信息 2、模拟文件系统问题描述 在任一OS下，建立一个大文件，把它假象成一张盘，在其中实现一个简单的小型文件系统。基本要求该小型文件系统没有子目录机制，文件连续分配，不考虑分区。做一个简单的 操作界面，提供四条简单的命令：简单的ls、cat、cp、rd.进一步增强:上题中的文件系统功能：文件系统不连续分配，可以有子目录 机制，（如两级子目录机制）。四、文件拷贝与进程操作1、要求熟悉和理解Linux编程环境2、内容1）编写一个C程序，实现文件拷贝功能。2）编写一个C程序，使用Linux下的图形库，分窗口显示三个并发进程的运行。五、信号量、临界区、多进程管理实现UP、DOWN原语 产生3个进程： 两个进程模拟需要进入临界区的用户进程。 当需要进入临界区时，显示：“进程x请求进入临界区”，同时向管理进程提出申请； 申请返回，表示进入了临界区。在临界区中等待一段随机时间，并显示：“进程x正在临界区”； 当时间结束，显示：“进程x退出临界区”,同时向管理进程提出退出申请； 当申请返回，显示：“进程x已退出临界区。” 一个进程作为原语的管理进程，接受其他进程的临界区进入请求： 如果允许进入，则根据DOWN 原语的操作步骤设置相应变量，然后返回； 如果不允许进入，则进入循环等待，直到允许为止； 退出时模拟UP 操作。 进程间通信可以采用信号、消息传递、管道或网络通信方式。 六、银行家算法 Output() 输出某时刻的资源分配情况；Bank() 银行家算法的步骤 1、2、3、及4调用安全性算法；Security() 进行安全性检查；Main() 各种数据结构的定义。假设 有0-4 五个进程(假设系统的当前状态是安全的)，三类资源 即：A、B、C(以下各种数据均取自课本97例子)T0 时刻的资源分配表(各种资源的数量分别为：10、5、7) 资源情况进程MaxA B CAllocationA B CNeedA B CAvailableA B CP07 5 30 1 07 4 33 3 2P13 2 22 0 01 2 2P29 0 23 0 26 0 0P32 2 22 1 10 1 1P44 3 30 0 24 3 1七、用一个8兆文件充当虚拟的硬盘，并在上面建立一个文件系统。实现多级目录结构的目录创建、删除，文件创建、读写和删除。八、编写一个shell基本功能要求1）利用C语言在Linux上设计一个简单的命令解释程序，完成如下功能：dir 列目录cd 改变当前目录pwd 显示当前目录名md 创建一个目录copy 复制文件和目录find 在指定的目录及其子目录中查找特定的文件more 一页一页地显示文件date 显示当前日期time显示当前时间ren 重命名一个文件或目录del 删除一个文件和目录exit 退出命令解释程序。执行一个程序2）命令解释程序的提示符为：3）命令解释程序把命令行解释为内部命令或外部命令（要执行的程序）。内部命令直接在命令解释程序中处理，外部命令的执行则由命令解释程序通过fork()创建一个子进程，然后在子进程中调用exec执行一个程序。4）命令解释程序应能够支持输入输出重定向。选作内容：1） 命令解释程序支持后台运行程序。2） 命令解释程序支持管道。3） 命令解释程序不能被ctrl+c打断。九、首次适应算法内存动态分配方法：首次适应算法十、子目录管理1、目的：了解并掌握DOS创建和撤消子目录的方法及有关子目录操作的系统功能。2、内容：用DOS功能调用39H和3AH来创建和撤消子目录，以及用3BH来改变当前目录。十一、目录项结构1、目的：了解目录项中文件属性的含义及如何修改文件属性的方法。2、内容：用DOS功能调用43H来获取并修改文件属性。十二、文件分配表（FAT）作用1、目的：了解FAT作用，掌握通过FDT、FAT恢复被删除文件的方法，特别第二个FAT在恢复被删除文件中所起的作用。2、内容：根据第二个FAT表，利用FDT的保留域快速恢复被删除文件。十三、程序加载方法1、目的：了解在当前程序中加载其他程序的一般方法;加深对EXEC功能调用的掌握；了解FCB的文件操作方式；了解内存管理功能调用。2、内容：在当前程序中调用DOS的EXEC功能，加载执行其他应用程序。十四、内存驻留（TSR）方法1、目的：掌握程序驻留内存的方法，了解如何用“热键”控制所需操作及对系统时钟的获取。2、内容：在图形模式下的屏幕右上角“弹出”一个时钟窗口，显示出系统当前时钟的“时：分：秒”值；如果不想让时钟显示，则只要同时按下左SHIFT键和右SHIFT键，再按下ENTER健，则此时窗口被关闭；如果再想让时钟显示，只要再次同时按下左SHIFT键和右SHIFT键即可。十五、可变分区存储管理的内存分配与回收要求：1 内存分配（采用首次适应算法与最佳适应算法分别完成）（1）动态输入构造空闲区表，并显示构造好的空闲区表。（提示：在两种不同的内存分配算法中，空闲区在空闲区表中的登记顺序是不一样的）（2）键盘接收内存申请尺寸大小。（3）根据申请，实施内存分配，并返回分配所得内存首址。（4）分配完后，调整空闲区表（即扣除分配部分），并显示调整后的空闲区表。（5）若分配失败，返回分配失败信息。2 内存回收（1） 动态输入构造空闲区表，并显示构造好的空闲区表。（2） 根据空闲区表，按内存回收的四种情况从键盘接收回收区域的内存首址与大小。（3） 回收区域，调整空闲区表（与前面空闲区相连、与后面空闲区相连、与前后空闲区相连则合并、与前后空闲区都不相连则插入该项），并显示调整后的空闲区表。十六、模拟请求页式存储管理中硬件的地址转换和缺页中断，并且用先进先出（FIFO）页面淘汰算法处理缺页中断要求：1为了装入一个页面而必须调出一页时，如果被选中调出的页面在执行中没有修改过，则不必把该页重新写到磁盘上（因磁盘上已有副本）。因此，在页表中可以增加是否修改过的标志，当执行“存”指令，“写”指令时把对应页的修改标志置成“1”，表示该页修改过，否则为“0”表示该页未修改过。页表格式如图。页号进内存标志内存页号修改标志磁盘位置 2设计一个地址转换程序来模拟硬件的地址转换和缺页中断。当访问的页在内存时则形成物理地址，但不去模拟指令的执行，可用输出转换后的物理地址来表示一条指令已完成。当访问的页不在内存时则输出“*页缺页”来表示硬件产生了一次中断。3编制一个FIFO页面淘汰程序。FIFO 页面淘汰算法总是先调出作业中最先进入内存的那一页，因此可以用一个数组来构造页号队列。数组中每个元素是该作业已在内存的页面号，假定分配给该作业的内存块数为m，且该作业开始的m页已装入内存，则数组可由m个元素组成： P0，P1，Pm-1它们的初值为： P0：=0，P1：=1，Pm-1：=m-1用一指针K指示当要调入新页时应淘汰的页在数组中的位置，K的初值为0。当产生缺页中断时操作系统总是选择PK所指出的页面调出，然后执行 PK：=要装入的新页页号 K：=（K+1）mod m在实验中不必世纪地启动磁盘执行调出一页和装入一页的工作，而用输出“OUT 调出的页号”和“IN 要装入的新页页号”来模拟一次调出和装入的过程。4假设页长为1024个字节，现有一个共7页的作业，其副本已在磁盘上。系统为该作业分配了4 个内存页面，且该作业的第0页至第三页已经装入内存，其余3页尚未装入内存。该作业的页表如图 页 表页号进内存标志内存块号修改标志磁盘位置0150011118001221900133110021400022500023600121如果该作业依次执行的指令序列如下表：操作页号页内地址+0070+10502015存3021取00566040移位4053+5023存1037取2078+4001依次执行上述指令序列来调试你所设计的程序（仅模拟指令的执行，不必考虑指令序列中具体操作的执行）。5可自行决定若干指令序列，运行设计的程序。十七：资源管理器要求：理解和分析/proc文件 内容1、了解/proc文件的特点和使用方法。2、监控系统状态，显示系统中若干部件的使用情况。3、用图形界面显示系统监控状态十八：LRU页面置换算法模拟要求：在Window98/2000 系统的TC2.0环境下运行程序；通过从一般常用的调页算法中选取典型算法LRU，了解页面管理的相关细节，并用程序设计实现LRU。（一）、调页策略 1)何时调入页面 如果进程的许多页是存放在外存的一个连续区域中，则一次调入若干个相邻的页，会比一次调入一页的效率更高效一些。但如果调入的一批页面中的大多数都未被访问，则又是低效的。可采用一种以预测为基础的预调页策略，将那些预计在不久之后便会被访问的页面，预先调入内存。如果预测较准确，那么，这种策略显然是很有吸引力的。但目前预调页的成功率仅为50%。且这种策略主要用于进程的首次调入时，由程序员指出应该先调入哪些页。 2)请求调页策略 当进程在运行中需要访问某部分程序和数据时，若发现其所在的页面不在内存，便即提出请求，由OS将其所需页面调入内存。由请示调页策略所确定调入的页，是一定会被访问的，再加之请求调页策略比较易于实现，故在目前的虚拟存储器中，大多采用此策略。但这种策略每次仅调入一页，故须花费较大的系统开销，增加了磁盘I/O的启用频率。 2、从何处调入页面 在请求分页系统中的外存分为两部分：用于存放文件的文件区和用于存放对换页面的对换区。通常，由于对换区是采用连续分配方式，而事件是采用离散分配方式，故对换区的磁盘I/O速度比文件区的高。这样，每当发生缺页请求时，系统应从何处将缺页调入内存，可分成如下三种情况： (1) 系统拥有足够的对换区空间，这时可以全部从对换区调入 所需页面，以提高调页速度。为此，在进程运行前，便须将与该进程有关的文件，从文件区拷贝到对换区。 (2) 系统缺少足够的对换区空间，这时凡是不会被修改的文件，都直接从文件区调入；而当换出这些页面时，由于它们未被修改而不必再将它们换出时，以后需要时，再从对换区调入。 (3) UNIX方式。由于与进程有关的文件都放在文件区，故凡是未运行过的页面，都从文件区调入。而对于曾经运行过但又被换出的页面，由于被放在对换区，因此在下次时，应从对换区调入。由于UNIX系统允许页面共享，因此，某进程所请求的页面有可能已被其它进程调入内存，此时也就无须再从对换区调入。 3页面调入过程 每当程序所要访问的页面未在内存时， 便向CPU发出一缺页中断，中断处理程序首先保留CPU环境，分析中断原因后，转入缺页中断处理程序。该程序通过查找页表，得到该页在外在原物理 块后，如果此时内存能容纳新页，则启动磁盘I/O将所缺之页调入内存，然后修改页表。如果内存已满，则须先按照某种置换算法从内存中选出一页准备换出；如果该页未被修改过，可不必将该页写回磁盘；但如果此页已被修改，则必须将它写回磁盘，然后再把所缺的页调入内存，并修改页表中的相应表项，置其存在位“1”，并将此页表项写入快表中。在缺页调入内存后，利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。整个页面的调入过程对用户是透明的。 （二）、页面置换算法 在进程运行过程中，若其所要访问的页面不在内存而需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。但应将哪 个页面调出，须根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法(Page_Replacement Algorithms)。 一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应将那些以后不再会访问的页面换出，或将那些在较长时间内不会再访问的页面调出。 常见置换算法 最佳置换算法(Optimal)： 它是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但由于人目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，便可以利用此算法来评价其它算法。 先进先出(FIFO)页面置换算法： 这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。 LRU置换算法：这是本次设计的重点。 CLOCK置换算法：a,简单CLOCK置换算法；b,改进型CLOCK算法。LRU算法是较好的一种算法，而由于LRU在硬件上要求较多，在实际应用中多采用LRU的近似算法。CLOCK算法就是用得较多的一种LRU近似算法。 最少使用(LFU:Least Frequently Used)置换算法：在采用该算法时，应为在内存中的每个页面设置一个移位寄存器骼来记录该页面被访问的频率。该置换算法选择在最近时期使用最少的页面为淘汰页。 页面缓冲算法(PBA：Page Buffering Algorithm) 、最近最久未使用置换算法 LRU(Least Recently Used)置换算法的描述 FIFO置换算法性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入的先后并不能反映页面的使用情况。最近最久未使用（LRU）置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t,，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。 2、LRU置换算法的硬件支持 LRU置换算法虽然是一种比较好的算法，但要求系统有较多的支持硬件。为了了解一个进程在内存中的各个页面各有多少时间未被进程访问，以及如何快速地知道哪一页是最近最久未使用的页面，须有以下两类硬件之一的支持： 1） 寄存器 为了记录某个进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为 R=Rn-1Rn-2Rn-3R2R1R0 当进程访问某物理块时，要将相应寄存器的Rn-1位置成1。此时，定时信号将每隔一定时间(例如100ms)将寄存器右移一位。如果我们把n位寄存器的数看作是一个整数，那么具有最小数值的寄存器所对应的页面，就是最近最久未使用的页面。如图1示出了某进程在内存中具有8个页面，为每个内存页面配置一个8位寄存器时的LRU访问情况。这里，把8个内存页面的序号分别定为18。由图可以看出，第7个内存页面的R值最小，当发生缺页时首先将它置换出去。 R 实 页 R7 R6 R5 R4 R3 R2 R1 R0 1 0 1 0 1 0 0 1 0 2 1 0 1 0 1 1 0 0 3 0 0 0 0 0 1 0 0 4 0 1 1 0 1 0 1 1 5 1 1 0 1 0 1 1 0 6 0 0 1 0 1 0 1 1 7 0 0 0 0 0 1 1 1 8 0 1 1 0 1 1 0 1 2)栈 可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时，便将页面的页面号从栈中移出，将它压入栈顶。因此，栈顶