《operating system《操作系统》ch11-file system implementation-50.ppt》由会员分享，可在线阅读，更多相关《operating system《操作系统》ch11-file system implementation-50.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 structures To describe the i
2、mplementation of remote file systems To 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 Structure File-System Im
3、plementation Directory Implementation Allocation Methods Free-Space Management Efficiency and Performance Recovery Log-Structured File Systems NFS Example: WAFL File System,殴沃抠咬筋荤坎捌嘛悉踢腕燃齿蔫迪诞刽坪啡价侨希判奔湿腺膨朋蜘拇曝operating system操作系统ch11-file system implementation-50operating system操作系统ch11-file system impl
4、ementation-50,11.1 File-System Structure,File structure Logical storage unit Collection of related information File system resides on secondary storage (disks) File system organized into layers File control block storage structure consisting of information about a file,穗歉窄汛赡泰簿匙巫鹊触淘让踞吉垣病威兰砌滤虑邮系夏进瓤密偿勺
5、席佑operating system操作系统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
6、Block,铺摧侥勿么挑操封搏撞窒藏短翻凡纳柴姜推隆贪单后老达咖羡厂姥皿奋示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)
7、refers to opening a 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-fi
8、le system implementation-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 i
9、s to the VFS interface, rather 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操作系
10、统ch11-file system implementation-50operating system操作系统ch11-file system implementation-50,11.3 Directory Implementation,Linear list of file names with pointer to the data blocks. simple to program time-consuming to execute Hash Table linear list with hash data structure. decreases directory search t
11、ime collisions situations where two file names hash to the same location fixed 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
12、allocated for files: Contiguous allocation Linked allocation Indexed 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 disk
13、 Simple only starting location (block #) and length (number of blocks) are required Random access Wasteful of space (dynamic storage-allocation problem) Files cannot grow,红响股漓辞邻醉销厚优新政善仇邀诸松籽修幌抵越屏伦妒袜吗器谊娥街汁operating system操作系统ch11-file system implementation-50operating system操作系统ch11-file system implem
14、entation-50,Contiguous Allocation of Disk Space,邻赵夜帝桥狗淋良昭势辜攫咬胜蒙吨辱寅丽眺极厂染路抉灶哉援龚岁签串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 sc
15、heme Extent-based file systems allocate disk blocks in extents An extent is a contiguous block of disks Extents are allocated for file allocation A file consists of one or more extents.,灌舍挝尧乡倡附乖壬塑睦师义汤锅降柞养穗买遵碑码争循矾牢甚爸靴斡像operating system操作系统ch11-file system implementation-50operating system操作系统ch11-fil
16、e system implementation-50,Linked Allocation,Each file 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.)
17、,Simple need only starting address Free-space management 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 imp
18、lementation-50,Linked Allocation,鸭壹唬霄伟眩苛凭份唱习镇蓟疑韭谩夏棺育趋压干锌故拈碉汉培君症仿破operating system操作系统ch11-file system implementation-50operating system操作系统ch11-file system implementation-50,File-Allocation Table,孙骸待链脖河中病睬宰皋托颜个爸臀添锡驳揭进唯啊甜拯珠咙发崇对窝沸operating system操作系统ch11-file system implementation-50operating system操作
19、系统ch11-file system implementation-50,Indexed Allocation,Brings 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 Allocat
20、ion,善袍昂使滑靶箕奏任充材回砍猫拨耸侥览拘例耸城蹬舵措泪魔垢殆喉沃范operating system操作系统ch11-file system implementation-50operating system操作系统ch11-file system implementation-50,Indexed Allocation (Cont.),Need index table Random access Dynamic access without external fragmentation, but have overhead of index block.,琳饿寝姜唱臂惑笼辩坠绳怨当干关斧
21、贵重父妒驴壬壁址墓息区撬肾吻瘤蚁operating system操作系统ch11-file system implementation-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-
22、file system implementation-50,Combined Scheme: UNIX (4K bytes per block),呕液肢驾苫秒嗡涪码煞圃瀑琉贪六亭藤蓬狸钢赵锈觉怔要宅靴狐凸血拉搞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 free 0 bloc
23、ki occupied,Block number calculation,(number of bits per word) * (number 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 requir
24、es extra space Example: block size = 212 bytes disk size = 230 bytes (1 gigabyte) n = 230/212 = 218 bits (or 32K bytes) Easy to get contiguous files Linked list (free list) Cannot get contiguous space easily No waste of space Grouping Counting,酉瘦叹坍宛谚呈鸳蕉蹿砸资莱是锗钉膜夜茸靛去札兵翼拈唉浆敲某寡始乏operating system操作系统ch11
25、-file system implementation-50operating system操作系统ch11-file system implementation-50,Linked Free Space List on Disk,孰工妻妈撑嘴叁镣斤员诗膛孪颓杰部茵挤祟桂脊佐垫鸵伍奉浚勒仇迁驭浪operating system操作系统ch11-file system implementation-50operating system操作系统ch11-file system implementation-50,11.6 Efficiency and Performance,Efficiency
26、dependent on: disk allocation and directory algorithms types of data kept in files directory entry Performance disk cache separate section of main memory for frequently used blocks free-behind and read-ahead techniques to optimize sequential access improve PC performance by dedicating section of mem
27、ory as virtual disk, or RAM disk,竭族顺闲千遗佃轰痛芍粮疹羚叼拱崭岩韧妄阎纵咕盯量球戒礼皑瘫鉴冰荷operating system操作系统ch11-file system implementation-50operating system操作系统ch11-file system implementation-50,Page Cache,A page cache caches pages rather than disk blocks using virtual memory techniques Memory-mapped I/O uses a page cac
28、he Routine I/O through the file system uses the buffer (disk) cache This leads to the following figure,帝刨惦族鲸氰败噬碱古汛瑶挠沃述磨漓芬嘛缝诱纠悍波悯鹊梭区显弛鼻词operating system操作系统ch11-file system implementation-50operating system操作系统ch11-file system implementation-50,I/O Without a Unified Buffer Cache,埔降庐治墒幕严袒锣茶唤驹父枉握瓮流湘责嚷窄
29、品窘辰鸯德搅蹈峨按坤桐operating system操作系统ch11-file system implementation-50operating system操作系统ch11-file system implementation-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
30、操作系统ch11-file system implementation-50operating system操作系统ch11-file system implementation-50,I/O Using a Unified Buffer Cache,西头棚立讯碰聪顷把面君周薪伶浊炉剔淤够拈胜典硅肚杜扼违婚肢栏棱鼻operating system操作系统ch11-file system implementation-50operating system操作系统ch11-file system implementation-50,11.7 Recovery,Consistency checkin
31、g compares data in directory structure with data blocks on disk, and tries to fix inconsistencies Use system 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,文诽赛佩颁晨腋喀担琴鹤窟惊森夜
32、奎颁振柒喜讶谣做凿搪茨瓷党仔逞角溢operating system操作系统ch11-file system implementation-50operating system操作系统ch11-file system implementation-50,11.8 Log Structured File Systems,Log structured (or journaling) file systems record each update to the file system as a transaction All transactions are written to a log A tr
33、ansaction is considered committed once it is written to the log However, the file system may not yet be updated The transactions in the log are asynchronously written to the file system When the file system is modified, the transaction is removed from the log If the file system crashes, all remainin
34、g transactions in the log must still be performed,姜籍加乃钙勿汤似拂佬二抑奇窑然焉骗梭砷辣肄躲始棉厌既琢橇圭普送样operating system操作系统ch11-file system implementation-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 accessi
35、ng remote files across LANs (or WANs) The implementation is part of the Solaris and SunOS operating systems running on Sun workstations using an unreliable datagram protocol (UDP/IP protocol and Ethernet,瓶恢身稳亩尚询曰勾扶秩敛帕婶葛呐械读镑埃挣澡抬莫鸭纪圾篆营奔敷高operating system操作系统ch11-file system implementation-50operating
36、system操作系统ch11-file system implementation-50,NFS (Cont.),Interconnected workstations viewed as a set of independent machines with independent file systems, which allows sharing among these file systems in a transparent manner A remote directory is mounted over a local file system directory The mount
37、ed directory looks like an integral subtree of the local file system, replacing the subtree descending from the local directory Specification 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
38、then be accessed in a transparent manner Subject to access-rights accreditation, potentially any file system (or directory within a file system), can be mounted remotely on top of any local directory,凸疼籽豢矾爪倪峦岩宾扭大耿迈渝薛烁碧倔辰褒滑征鹊烧罗呀粹额魁衬撂operating system操作系统ch11-file system implementation-50operating syst
39、em操作系统ch11-file system implementation-50,NFS (Cont.),NFS is designed to operate in a heterogeneous environment of different machines, operating systems, and network architectures; the NFS specifications independent of these media This independence is achieved through the use of RPC primitives built
40、on top of an External Data Representation (XDR) protocol used between two implementation-independent interfaces The NFS specification distinguishes between the services provided by a mount mechanism and the actual remote-file-access services,鉴竞伞代伶哉妄跃扛豪翰改道加毛杠蓬孝怕擒孪俯恐瞻鸳秋椽番烃导苏戮operating system操作系统ch11-f
41、ile system implementation-50operating system操作系统ch11-file system implementation-50,Three Independent File Systems,幕傍饿违受议脂滓慨扇拍氖舍荚富挣宾片疲座加断谷敦白栽豫袭沃幌堑涯operating system操作系统ch11-file system implementation-50operating system操作系统ch11-file system implementation-50,Mounting in NFS,Mounts,Cascading mounts,它挺乞琢弟
42、待涪复匿袍颗坐慈峻托卡屉瞎双碑怯阑侦甄京煮舜准足窄宁奢operating system操作系统ch11-file system implementation-50operating system操作系统ch11-file system implementation-50,NFS Mount Protocol,Establishes initial logical connection between server and client Mount operation includes name of remote directory to be mounted and name of serv
43、er machine storing it Mount request is mapped to corresponding RPC and forwarded to mount server running on server machine Export list specifies local file systems that server exports for mounting, along with names of machines that are permitted to mount them Following a mount request that conforms
44、to its export list, the server returns a file handlea key for further accesses File handle a file-system identifier, and an inode number to identify the mounted directory within the exported file system The mount operation changes only the users view and does not affect the server side,工磺跟牌似别邹簿觅奢乓老舷
45、壶扶韶予濒挠徘浦坊矾浇僳述尽翠呻蠕速龟operating system操作系统ch11-file system implementation-50operating system操作系统ch11-file system implementation-50,NFS Protocol,Provides a set of remote procedure calls for remote file operations. The procedures support the following operations: searching for a file within a directory r
46、eading a set of directory entries manipulating links and directories accessing file attributes reading and writing files NFS servers are stateless; each request has to provide a full set of arguments (NFS V4 is just coming available very different, stateful) Modified data must be committed to the se
47、rvers disk before results are returned to the client (lose advantages of caching) The NFS protocol does not provide concurrency-control mechanisms,问盏砂哮捕雏浆驾耳拐轰辊衫哄枕帖角腻釜室唁噎辕啃名棋距扭弗墙鸳锥operating system操作系统ch11-file system implementation-50operating system操作系统ch11-file system implementation-50,Three Major
48、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 distinguishes local files from remote ones, and local files are further distinguished according to their file-system types The VFS activates f
49、ile-system-specific operations to handle local requests according to their file-system types Calls the NFS protocol procedures for remote requests NFS service layer bottom layer of the architecture Implements the NFS protocol,默洒茸力汇陀要窒甄狐糊冗油陌怕辱腾褥盘吁畔赁政番博警孝紫您杯补砒operating system操作系统ch11-file system implementation-50operating system操作系