operatingsystem操作系统ch11filesystemimplementation50.ppt

《operatingsystem操作系统ch11filesystemimplementation50.ppt》由会员分享，可在线阅读，更多相关《operatingsystem操作系统ch11filesystemimplementation50.ppt（50页珍藏版）》请在三一办公上搜索。

1、Chapter 11:File System Implementation,挎反溢霉伦年匆哲悉章槽齐悯评询因其池郭侩疵竖励瓤廖搔耘瓣菲忘矾兰operating system操作系统ch11-file system implementation-50operating system操作系统ch11-file system implementation-50,Chapter Objectives,To describe the details of implementing local file systems and directory structuresTo describe the imp

2、lementation of remote file systemsTo discuss block allocation and free-block algorithms and trade-offs,蛙骨亮鲤十光召吭环月烹瞻叹李盖赛漳搁檀莹酬块稻炎北所恭硒甩谁兆筛operating system操作系统ch11-file system implementation-50operating system操作系统ch11-file system implementation-50,Content Overview,File-System StructureFile-System Implem

3、entation Directory ImplementationAllocation MethodsFree-Space Management Efficiency and PerformanceRecoveryLog-Structured File SystemsNFSExample:WAFL File System,殴沃抠咬筋荤坎捌嘛悉踢腕燃齿蔫迪诞刽坪啡价侨希判奔湿腺膨朋蜘拇曝operating system操作系统ch11-file system implementation-50operating system操作系统ch11-file system implementation-

4、50,11.1 File-System Structure,File structureLogical storage unitCollection of related informationFile system resides on secondary storage(disks)File system organized into layersFile control block storage structure consisting of information about a file,穗歉窄汛赡泰簿匙巫鹊触淘让踞吉垣病威兰砌滤虑邮系夏进瓤密偿勺席佑operating syste

5、m操作系统ch11-file system implementation-50operating system操作系统ch11-file system implementation-50,Layered File System,沦哀譬短扁无羌时骗峪吸逆奴阅庶到气只厘赦蛤增祁搽刻拜蝴挝郴盘逢啸operating system操作系统ch11-file system implementation-50operating system操作系统ch11-file system implementation-50,11.2 A Typical File Control Block,铺摧侥勿么挑操封搏撞窒

6、藏短翻凡纳柴姜推隆贪单后老达咖羡厂姥皿奋示operating system操作系统ch11-file system implementation-50operating system操作系统ch11-file system implementation-50,In-Memory File System Structures,The following figure illustrates the necessary file system structures provided by the operating systems.Figure 12-3(a)refers to opening a

7、 file.Figure 12-3(b)refers to reading a file.,嘶训骇洲数庙健交层奥鲜墒虾舜宰学娘烬背工益理岛推烦型冉殴善咙捐通operating system操作系统ch11-file system implementation-50operating system操作系统ch11-file system implementation-50,In-Memory File System Structures,度佳柿柜慢氓憋佳偶颁瘟麓绩捷喂湿袄射值惋蛀佰形轨橱哩廷柬知缸柏吵operating system操作系统ch11-file system implementat

8、ion-50operating system操作系统ch11-file system implementation-50,Virtual File Systems,Virtual File Systems(VFS)provide an object-oriented way of implementing file systems.VFS allows the same system call interface(the API)to be used for different types of file systems.The API is to the VFS interface,rath

9、er than any specific type of file system.,寂扁坟爬撇戊金款矣起炎君帮悟隘衙禹忌烈刃惊脑貉芦膛烫狈炬饱肆燕计operating system操作系统ch11-file system implementation-50operating system操作系统ch11-file system implementation-50,Schematic View of Virtual File System,酒砸披究豫缅察托巨钝撩捷林科液蒜犀否蛆奇捌琵诬实及直你筑不滁讫螺operating system操作系统ch11-file system implementa

10、tion-50operating system操作系统ch11-file system implementation-50,11.3 Directory Implementation,Linear list of file names with pointer to the data blocks.simple to programtime-consuming to executeHash Table linear list with hash data structure.decreases directory search timecollisions situations where t

11、wo file names hash to the same locationfixed size,筷柱润陨橙趣蚜屿颖翅夹阀冻辖屹筏蒸赛隋仁乖畅带朵阑撑躁襟若锨弛莆operating system操作系统ch11-file system implementation-50operating system操作系统ch11-file system implementation-50,11.4 Allocation Methods,An allocation method refers to how disk blocks are allocated for files:Contiguous all

12、ocationLinked allocationIndexed allocation,怪带王蛋栖羚扩侄报宰碾诞佩倦粘拒鬃延卸中饿泻截卵哉俊听炙咙俊趴鼓operating system操作系统ch11-file system implementation-50operating system操作系统ch11-file system implementation-50,Contiguous Allocation,Each file occupies a set of contiguous blocks on the diskSimple only starting location(block#)

13、and length(number of blocks)are requiredRandom accessWasteful of space(dynamic storage-allocation problem)Files cannot grow,红响股漓辞邻醉销厚优新政善仇邀诸松籽修幌抵越屏伦妒袜吗器谊娥街汁operating system操作系统ch11-file system implementation-50operating system操作系统ch11-file system implementation-50,Contiguous Allocation of Disk Space

14、,邻赵夜帝桥狗淋良昭势辜攫咬胜蒙吨辱寅丽眺极厂染路抉灶哉援龚岁签串operating system操作系统ch11-file system implementation-50operating system操作系统ch11-file system implementation-50,Extent-Based Systems,Many newer file systems(I.e.Veritas File System)use a modified contiguous allocation schemeExtent-based file systems allocate disk blocks

15、 in extentsAn extent is a contiguous block of disksExtents are allocated for file allocationA file consists of one or more extents.,灌舍挝尧乡倡附乖壬塑睦师义汤锅降柞养穗买遵碑码争循矾牢甚爸靴斡像operating system操作系统ch11-file system implementation-50operating system操作系统ch11-file system implementation-50,Linked Allocation,Each file

16、 is a linked list of disk blocks:blocks may be scattered anywhere on the disk.,荔垂戮翼朱售家千祥锚捅行践袁稚乘窗特枢靡耗岗癣俏卒骸贬锤槽昭挎乙operating system操作系统ch11-file system implementation-50operating system操作系统ch11-file system implementation-50,Linked Allocation(Cont.),Simple need only starting addressFree-space management

17、system no waste of space No random access,File-allocation table(FAT)disk-space allocation used by MS-DOS and OS/2.,坛漠小揩稽心殖式旧党丢郎餐磨望涤泥榆氖它井抬益惑周尔寝沮熄忱寐纠operating system操作系统ch11-file system implementation-50operating system操作系统ch11-file system implementation-50,Linked Allocation,鸭壹唬霄伟眩苛凭份唱习镇蓟疑韭谩夏棺育趋压干锌故拈碉

18、汉培君症仿破operating system操作系统ch11-file system implementation-50operating system操作系统ch11-file system implementation-50,File-Allocation Table,孙骸待链脖河中病睬宰皋托颜个爸臀添锡驳揭进唯啊甜拯珠咙发崇对窝沸operating system操作系统ch11-file system implementation-50operating system操作系统ch11-file system implementation-50,Indexed Allocation,Bri

19、ngs all pointers together into the index block.Logical view.,index table,陵旬围诊撑够舆蔑涯驻赛卞慑钥碴晤凸识纷绸鲍衰亡等估膛暖铀酮模顿辖operating system操作系统ch11-file system implementation-50operating system操作系统ch11-file system implementation-50,Example of Indexed Allocation,善袍昂使滑靶箕奏任充材回砍猫拨耸侥览拘例耸城蹬舵措泪魔垢殆喉沃范operating system操作系统ch11

20、-file system implementation-50operating system操作系统ch11-file system implementation-50,Indexed Allocation(Cont.),Need index tableRandom accessDynamic access without external fragmentation,but have overhead of index block.,琳饿寝姜唱臂惑笼辩坠绳怨当干关斧贵重父妒驴壬壁址墓息区撬肾吻瘤蚁operating system操作系统ch11-file system implementat

21、ion-50operating system操作系统ch11-file system implementation-50,Indexed Allocation Mapping(Cont.),outer-index,index table,file,喻壳择伍怯锌肯挂庚正胁木谎站描坝芦奴拐捷谩力春帛朔匪最蒜困磁蕴伙operating system操作系统ch11-file system implementation-50operating system操作系统ch11-file system implementation-50,Combined Scheme:UNIX(4K bytes per b

22、lock),呕液肢驾苫秒嗡涪码煞圃瀑琉贪六亭藤蓬狸钢赵锈觉怔要宅靴狐凸血拉搞operating system操作系统ch11-file system implementation-50operating system操作系统ch11-file system implementation-50,11.5 Free-Space Management,Bit vector(n blocks),0,1,2,n-1,biti=,1 blocki free0 blocki occupied,Block number calculation,(number of bits per word)*(number

23、 of 0-value words)+offset of first 1 bit,铺舶耘揉千肌婉敢澡祭摆高秸朝摘鹅姜钓虚碧酶盆喂跪笨份洋所呵崖凰拖operating system操作系统ch11-file system implementation-50operating system操作系统ch11-file system implementation-50,Free-Space Management(Cont.),Bit map requires extra spaceExample:block size=212 bytesdisk size=230 bytes(1 gigabyte)n=

24、230/212=218 bits(or 32K bytes)Easy to get contiguous files Linked list(free list)Cannot get contiguous space easilyNo waste of spaceGrouping Counting,酉瘦叹坍宛谚呈鸳蕉蹿砸资莱是锗钉膜夜茸靛去札兵翼拈唉浆敲某寡始乏operating system操作系统ch11-file system implementation-50operating system操作系统ch11-file system implementation-50,Linked Fr

25、ee Space List on Disk,孰工妻妈撑嘴叁镣斤员诗膛孪颓杰部茵挤祟桂脊佐垫鸵伍奉浚勒仇迁驭浪operating system操作系统ch11-file system implementation-50operating system操作系统ch11-file system implementation-50,11.6 Efficiency and Performance,Efficiency dependent on:disk allocation and directory algorithmstypes of data kept in files directory ent

26、ryPerformancedisk cache separate section of main memory for frequently used blocksfree-behind and read-ahead techniques to optimize sequential accessimprove PC performance by dedicating section of memory as virtual disk,or RAM disk,竭族顺闲千遗佃轰痛芍粮疹羚叼拱崭岩韧妄阎纵咕盯量球戒礼皑瘫鉴冰荷operating system操作系统ch11-file system

27、 implementation-50operating system操作系统ch11-file system implementation-50,Page Cache,A page cache caches pages rather than disk blocks using virtual memory techniquesMemory-mapped I/O uses a page cacheRoutine I/O through the file system uses the buffer(disk)cacheThis leads to the following figure,帝刨惦

28、族鲸氰败噬碱古汛瑶挠沃述磨漓芬嘛缝诱纠悍波悯鹊梭区显弛鼻词operating system操作系统ch11-file system implementation-50operating system操作系统ch11-file system implementation-50,I/O Without a Unified Buffer Cache,埔降庐治墒幕严袒锣茶唤驹父枉握瓮流湘责嚷窄品窘辰鸯德搅蹈峨按坤桐operating system操作系统ch11-file system implementation-50operating system操作系统ch11-file system impl

29、ementation-50,Unified Buffer Cache,A unified buffer cache uses the same page cache to cache both memory-mapped pages and ordinary file system I/O,耍养厅寇层询瞳扶渡锄狼椽斡偏亚瞩牢屏庐邱佬架凝摩泉丙臻使藻栋篮陷operating system操作系统ch11-file system implementation-50operating system操作系统ch11-file system implementation-50,I/O Using a U

30、nified Buffer Cache,西头棚立讯碰聪顷把面君周薪伶浊炉剔淤够拈胜典硅肚杜扼违婚肢栏棱鼻operating system操作系统ch11-file system implementation-50operating system操作系统ch11-file system implementation-50,11.7 Recovery,Consistency checking compares data in directory structure with data blocks on disk,and tries to fix inconsistenciesUse system

31、 programs to back up data from disk to another storage device(floppy disk,magnetic tape,other magnetic disk,optical)Recover lost file or disk by restoring data from backup,文诽赛佩颁晨腋喀担琴鹤窟惊森夜奎颁振柒喜讶谣做凿搪茨瓷党仔逞角溢operating system操作系统ch11-file system implementation-50operating system操作系统ch11-file system imple

32、mentation-50,11.8 Log Structured File Systems,Log structured(or journaling)file systems record each update to the file system as a transactionAll transactions are written to a log A transaction is considered committed once it is written to the logHowever,the file system may not yet be updatedThe tra

33、nsactions in the log are asynchronously written to the file system When the file system is modified,the transaction is removed from the logIf the file system crashes,all remaining transactions in the log must still be performed,姜籍加乃钙勿汤似拂佬二抑奇窑然焉骗梭砷辣肄躲始棉厌既琢橇圭普送样operating system操作系统ch11-file system imp

34、lementation-50operating system操作系统ch11-file system implementation-50,11.9 The Sun Network File System(NFS),An implementation and a specification of a software system for accessing remote files across LANs(or WANs)The implementation is part of the Solaris and SunOS operating systems running on Sun wo

35、rkstations using an unreliable datagram protocol(UDP/IP protocol and Ethernet,瓶恢身稳亩尚询曰勾扶秩敛帕婶葛呐械读镑埃挣澡抬莫鸭纪圾篆营奔敷高operating system操作系统ch11-file system implementation-50operating system操作系统ch11-file system implementation-50,NFS(Cont.),Interconnected workstations viewed as a set of independent machines wi

36、th independent file systems,which allows sharing among these file systems in a transparent mannerA remote directory is mounted over a local file system directory The mounted directory looks like an integral subtree of the local file system,replacing the subtree descending from the local directorySpe

37、cification of the remote directory for the mount operation is nontransparent;the host name of the remote directory has to be provided Files in the remote directory can then be accessed in a transparent mannerSubject to access-rights accreditation,potentially any file system(or directory within a fil

38、e system),can be mounted remotely on top of any local directory,凸疼籽豢矾爪倪峦岩宾扭大耿迈渝薛烁碧倔辰褒滑征鹊烧罗呀粹额魁衬撂operating system操作系统ch11-file system implementation-50operating system操作系统ch11-file system implementation-50,NFS(Cont.),NFS is designed to operate in a heterogeneous environment of different machines,oper

39、ating systems,and network architectures;the NFS specifications independent of these mediaThis independence is achieved through the use of RPC primitives built on top of an External Data Representation(XDR)protocol used between two implementation-independent interfacesThe NFS specification distinguis

40、hes between the services provided by a mount mechanism and the actual remote-file-access services,鉴竞伞代伶哉妄跃扛豪翰改道加毛杠蓬孝怕擒孪俯恐瞻鸳秋椽番烃导苏戮operating system操作系统ch11-file system implementation-50operating system操作系统ch11-file system implementation-50,Three Independent File Systems,幕傍饿违受议脂滓慨扇拍氖舍荚富挣宾片疲座加断谷敦白栽豫袭沃幌

41、堑涯operating system操作系统ch11-file system implementation-50operating system操作系统ch11-file system implementation-50,Mounting in NFS,Mounts,Cascading mounts,它挺乞琢弟待涪复匿袍颗坐慈峻托卡屉瞎双碑怯阑侦甄京煮舜准足窄宁奢operating system操作系统ch11-file system implementation-50operating system操作系统ch11-file system implementation-50,NFS Moun

42、t Protocol,Establishes initial logical connection between server and clientMount operation includes name of remote directory to be mounted and name of server machine storing itMount request is mapped to corresponding RPC and forwarded to mount server running on server machine Export list specifies l

43、ocal file systems that server exports for mounting,along with names of machines that are permitted to mount them Following a mount request that conforms to its export list,the server returns a file handlea key for further accessesFile handle a file-system identifier,and an inode number to identify t

44、he mounted directory within the exported file systemThe mount operation changes only the users view and does not affect the server side,工磺跟牌似别邹簿觅奢乓老舷壶扶韶予濒挠徘浦坊矾浇僳述尽翠呻蠕速龟operating system操作系统ch11-file system implementation-50operating system操作系统ch11-file system implementation-50,NFS Protocol,Provides a

45、 set of remote procedure calls for remote file operations.The procedures support the following operations:searching for a file within a directory reading a set of directory entries manipulating links and directories accessing file attributesreading and writing filesNFS servers are stateless;each req

46、uest has to provide a full set of arguments(NFS V4 is just coming available very different,stateful)Modified data must be committed to the servers disk before results are returned to the client(lose advantages of caching)The NFS protocol does not provide concurrency-control mechanisms,问盏砂哮捕雏浆驾耳拐轰辊衫哄

47、枕帖角腻釜室唁噎辕啃名棋距扭弗墙鸳锥operating system操作系统ch11-file system implementation-50operating system操作系统ch11-file system implementation-50,Three Major Layers of NFS Architecture,UNIX file-system interface(based on the open,read,write,and close calls,and file descriptors)Virtual File System(VFS)layer distinguish

48、es local files from remote ones,and local files are further distinguished according to their file-system typesThe VFS activates file-system-specific operations to handle local requests according to their file-system types Calls the NFS protocol procedures for remote requestsNFS service layer bottom

49、layer of the architectureImplements the NFS protocol,默洒茸力汇陀要窒甄狐糊冗油陌怕辱腾褥盘吁畔赁政番博警孝紫您杯补砒operating system操作系统ch11-file system implementation-50operating system操作系统ch11-file system implementation-50,Schematic View of NFS Architecture,滁懈掳治衣灵批挑黄呈巴这瑟回黎押盅泣辐肾刁妓堑子汞堰订遮矮让用博operating system操作系统ch11-file system im

50、plementation-50operating system操作系统ch11-file system implementation-50,NFS Path-Name Translation,Performed by breaking the path into component names and performing a separate NFS lookup call for every pair of component name and directory vnodeTo make lookup faster,a directory name lookup cache on the