Outline for EECS 678 with Professor Kulkarni at KU 2
Outline for EECS 678 with Professor Kulkarni at KU 2
Popular in Course
Popular in Department
This 30 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at Kansas taught by a professor in Fall. Since its upload, it has received 15 views.
Reviews for Outline for EECS 678 with Professor Kulkarni at KU 2
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
5 Chapter 11 Outline FileSystem Structure FileSystem Implementation Directory Implementation FreeSpace Management Efficiency and Performance NFS EECS 678 Introduction to Operating Systems 7 Sp ng 2009 5 File Usage Patterns l Most files are small and most references are to small files 0 eg login c files I Large files use up most of the disk space 0 eg mp3 and avi files I Large files account for most of the bytes transferred between memory and disk I Bad new for le system designers EECS 678 Introduction to Operating Systems 7 Sp ng 2009 5 File System Design Constraints I Design problems for a file system 0 how should the file system look to the user gt file structure attributes directory structure access methods etc o devise algorithms and algorithms to map logical file system on physical storage medium I High performance 0 efficient access of small files gt many small files used frequently 0 efficient access of large files gt consume most disk space account for most data movement EECS 678 Introduction to Operating Systems 7 Sp ng 2009 if Layered File System I O control application programs 0 consists of device drivers interrupt handlers i 0 transfer information between disk and memory logical file system I Basic file system L 0 issues commands to readwrite speci c blocks fileorganization module 0 manages memory buffers and caches k l File organization module I baSIC file system 0 translate logicalphysical block addresses 0 manages free space manager for disk blocks Q lO control I Logical file system 0 holds the filecontrol block containing file L metadata ownership permissions location devices 0 manages the directory structure EECS 678 Introduction to Operating Systems 7 Spring 2009 5 File System Structures On Disk l Boot control block 0 information to boot an OS from that volume I Volume or partition control block 0 number of free blocks in partition block size freeblock count free block pointers free FCB count and pointers l Directory structure 0 organize files in this file system I File control block FCB O perfile structure file identifier file permissions file creationaccess write dates file owner group ACL file size data blocks 0 called inode in Unix EECS 678 Introduction to Operating Systems 7 Sp ng 2009 5 File System Structures In Memory l Mount table 0 information about each mounted volume I Directory structure cache 0 caches recently accessed directory information I Systemwide open filetable 0 copy of FCB of each open file in the system I Perprocess openfile table 0 pointer to FCB entry in systemwide table for each open file in process I Performance enhancing buffers 0 cache file system blocks as they are read EECS 678 Introduction to Operating Systems 7 Sp ng 2009 9 File Open File System Structures open file name directory structure P directory structu re filecontrol block user space kernel memory a secondary storage read index File Read index L r s per process openfile table systemwide openfile table i i data blocks file control block user space kernel memory b secondary storage EECS 678 Introduction to Operating Systems 7 Spiing 2009 of Disk Allocation Methods I An allocation method refers to how disk blocks are allocated for files 0 a file may require a variable number of blocks based on size 0 file size may change throughout its lifetime I Disk allocation policies 0 contiguous allocation I linked allocation 0 indexed allocation EECS 678 Introduction to Operating Systems 7 Sp ng 2009 5 Contiguous Allocation l Each file occupies a set of contiguous blocks on the disk I To allocate space for a new file of size n 0 search the disk for a hole larger than n 0 use firstfit bestfit worstfit strategies I Sequential access 0 file system remembers last block accessed 0 reads next block I Random access to blocki 0 immediately access block starting address I l Advantages 0 very efficient memory accesses 0 simple and lowoverhead allocation policy EECS 678 Introduction to Operating Systems 7 Sp ng 2009 Contiguous Allocation 2 A di recto ry count le start length 0B 1C 2I 3I count 0 2 f tr 14 4I 5I 5 7I mail 19 3 6 SD 9I10EI11EI St 28 4 tr f 6 2 1213l14ll15l 16El171819 mail 20D21E122D23D 24El252627 list mDmDmDmD V EECS 678 Introduction to Operating Systems 7 Spling 2009 5 Continuous Allocation 3 l Disadvantages 0 external fragmentation 0 need to know file size upfront gt what happens if size changes later I Dealing with difficulty of growing files 0 overestimate file size at creation time 0 copy file to larger hole if current hole proves too small 0 use a modified entent based continuous allocation policy I Extentbased continuous allocation 0 continuous chunk of disk space allocated during creation 0 another chunk of space called entem can be added later 0 FCB contains a linked list of of extents o eg Veritas file system EECS 678 Introduction to Operating Systems 7 Sp ng 2009 11 5 Linked Allocation l File is a linked list of disk blocks blocks may be scattered anywhere on the disk each block contains pointer to next block special maker indicates the end of file I Advantages simple FCB only stores starting block address no external fragmentation files can grow dynamically with incremental allocation of blocks directory file Jeep start 9 end 25 1213II1415I 1617II18I19I 20D212Z23j 242526D27E 28 EIZQEISODQA I V EECS 678 Introduction to Operating Systems 7 Spring 2009 12 15 Linked Allocation 2 l Disadvantages 0 random access is clumsy and inefficient 0 space overhead for linkedlist pointers 0 even locality for sequential access may suffer gt more movements of the disk head 0 unreliable gt a corrupted pointer can lead to loss of the remaining file EECS 678 Introduction to Operating Systems 7 Sp ng 2009 13 a FileAllocation Table FAT directory entry test I H 217 name start block 0 l Variation of linked allocation I Used in MS DOS and 082 217 I Start of each volume holds a special table 0 array indexed by block number 339 0 directory entry points to first file block 217 in Figure 618 O FAT entry points to next block in the chain FAT217 618 0 last file block marked l Random access is improved no of disk blocks 1 EECS 678 Introduction to Operating Systems 7 Spring 2009 6 18 339 FAT 14 5 Indexed Allocation I All disk block pointers together into a per file index block Q directory 0 directory entry holds the index file index block block block 19 in Figure oll 1 2l sll Jeep 19 o ith index block entry points to ith 4E 5B 713 data block I Advantages 0 fast lookups and direct access o no external fragmentation 6 D185 I Disadvantages 20El21ll2223ll 0 space overhead of index block 24El2526ll27ll 0 poor data block locality on disk 28D29D30D31D o indices for large file may not fit in one index block 15 EECS 678 Introduction to Operating Systems 7 Spring 2009 g Indexed Allocation 2 I How to store indices for large files that do not fit in a block I Linked scheme 0 link several index blocks together 0 last word in an index block points to next index block if required I Multilevel index 0 adopts multiple levels of index blocks 0 entries in firstlevel index block point to secondlevel index blocks 0 entries in secondlevel index block point to data blocks 0 Example with 4096byte blocks and 4byte address gt we can store 1024 pointers in firstlevel index block gt each of 1024 secondlevel blocks can point to 1024 data blocks gt therefore total storage 1024 1024 4096 1010 1010 1012 1032 4GB EECS 678 Introduction to Operating Systems 7 Sp ng 2009 16 s Twolevel Index Scheme directory entry 2 1024 1024 1024 rstlevel index block 1024 secondlevel index block EECS 678 Introduction to Operating Systems 7 Spiing 2009 file 17 a Indexed Allocation 3 I How to store indices for large files that do not fit in a block I Combined scheme 0 used in Unix File System U FS 0 15 index block pointers are maintained in the file inode FCB O 12 of these point to direct blocks 0 Last 3 point to indirect blocks gt one single indirect one double indirect one triple indirect EECS 678 Introduction to Operating Systems 7 Sp ng 2009 18 Combined Scheme UNIX 4K bytes per block mode owners 2 timestamps 3 gt data size block count gt data gt data direct blocks gt data gt data single indirect gt o 39 data gt data double Indirect gt data triple indirect gt data 39 gt data EECS 678 Introduction to Operating Systems 7 SpIing 2009 19 i Recovery l Prevent and recover from loss of data after a system crash I File system consistency 0 file system operations may change several structures on disk 0 eg creating a file changes directory structures allocates FCBs allocates data blocks changes the count of free F085 and data blocks 0 crash may cause some of these structures to be outofsync l Consistency checking 0 check and restore consistency of all file system data structures 0 check directory structure metadata with file data blocks 0 to prevent consistency check from happening on every system boot gt status bit set before every metadata change gt status bit reset after change is completed 0 not all errors can be rectified EECS 678 Introduction to Operating Systems 7 Sp ng 2009 20 5 Recovery 2 l Logstructured file systems used in V ndows NTFS Veritas FS UFS on Solaris l Procedure record each update to the file system as a transaction all transactions are written to a log a transaction is considered committed once it is written to the log gt the file system may not yet be updated transactions in the log are asynchronously written to the file system transaction is removed from the log after file system update if the file system crashes gt transactions remaining in the log are performed if system crashes before committing transaction gt revert any file system changes from partial transaction EECS 678 Introduction to Operating Systems 7 Sp ng 2009 21 a Network File System NFS l Both an implementation and a speci cation for accessing remote files across LANs or WANs l Implementation described in OS book is part of Sun39s Solaris operating systems 0 uses reliable TCP or unreliable UDP over IP protocol and Ethernet for communication between client and server I Server 0 machine that hosts the remote file system I Client 0 machine that attaches the remote file system in its local directory structure EECS 678 Introduction to Operating Systems 7 Sp ng 2009 22 s NFS Overview l NFS protocol allows file system sharing between independent machines across a network 0 a single machine may be a client and a server at the same time I A remote directory is mounted over a local file system directory 0 the mounted directory looks like an integral subtree of the local file system 0 the mount operation needs the host name of the remote directory 0 files in the remote directory can then be accessed as local file l iny accredited clients are given access to shared remote directories o accreditation and sharing are manual operations EECS 678 Introduction to Operating Systems 7 Sp ng 2009 23 a l File systems of three machines U 81 and S2 NFS Mounting Example U S 1 S2 USf LISI local shared dir1 EECS 678 Introduction to Operating Systems 7 Spring 2009 USI dir2 24 5 NFS Mounting Example 2 l a mount S1usrshared over Uusrloca l b cascading mount 82usrdir2 over Uusrocadir1 U U usr usr local local dir1 dir1 a b EECS 678 Introduction to Operating Systems 7 Spring 2009 25 s NFS Design Goals l NFS can operate in a heterogeneous environment 0 different machines operating systems and network architectures o NFS specifications is independent of these media I Achieving machine independence 0 Remote Procedure Call RPC mechanism for invoking operation on server 0 External Data Representation XDR used for formating messages passed over the network I NFS specification can be implemented on any system 0 varied file systems can be mounted both locally and remotely EECS 678 Introduction to Operating Systems 7 Sp ng 2009 26 5 NFS Services Mount Protocol l Specifies services to establish initial logical connection between server and client I Mount server on remote machine maintains 0 local file systems that can be exported 0 machine names that are permitted to mount them I Mount operation on local machine specifies 0 name of remote directory to be mounted 0 name of server machine storing it I Mount operation implementation 0 request mapped to corresponding RPC o forwarded to mount server running on server machine 0 check permissions for request validity 0 return file handle to the client to access file on the remote machine EECS 678 Introduction to Operating Systems 7 Sp ng 2009 27 JNFS Services for Remote File Access I NSF protocol provides following operations 0 searching for a file within a directory 0 reading a set of directory entries 0 manipulating links and directories o accessing file attributes 0 reading and writing files I NFS servers are stateless 0 each service request has to provide a full set of arguments 0 modified data must be committed to the server s disk before results are returned to the client gt lose advantages of caching o NFS V4 is just becoming available very different stateful l NFS does not provide concurrencycontrol mechanisms 0 write request interleaving possible been multiple clients of same file EECS 678 Introduction to Operating Systems 7 Sp ng 2009 28 9 NFS Architecture Major Layers l UNIX Windows etc filesystem interface 0 use normal open read write close calls and file descriptors l Virtual File System VFS layer 0 distinguishes local files from remote ones and local files are further distinguished according to their filesystem types 0 VFS activates filesystemspecific operations to handle local requests according to their filesystem types 0 calls the NFS protocol procedures for remote requests I NFS service layer 0 bottom layer of the architecture 0 handles XDR data conversion RPC call sendreceive o implements the NFS service protocol EECS 678 Introduction to Operating Systems 7 Sp ng 2009 29 JNFS Architecture Schematic View client server systemcalls interface t VFS interface gt VFS interface l v 1 v other types of UNIX file NFS NFS UNIX file file systems system client server system A RPCXDR RPCXDR A v network EECS 678 Introduction to Operating Systems 7 Spring 2009
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'