%!PS-Adobe-2.0 %%Title: techrep.mss %%DocumentFonts: (atend) %%Creator: Alessandro Forin and Scribe 7(1700) %%CreationDate: 7 February 1994 13:42 %%Pages: (atend) %%EndComments % PostScript Prelude for Scribe. /BS {/SV save def 0.0 792.0 translate .01 -.01 scale} bind def /ES {showpage SV restore} bind def /SC {setrgbcolor} bind def /FMTX matrix def /RDF {WFT SLT 0.0 eq {SSZ 0.0 0.0 SSZ neg 0.0 0.0 FMTX astore} {SSZ 0.0 SLT neg sin SLT cos div SSZ mul SSZ neg 0.0 0.0 FMTX astore} ifelse makefont setfont} bind def /SLT 0.0 def /SI { /SLT exch cvr def RDF} bind def /WFT /Courier findfont def /SF { /WFT exch findfont def RDF} bind def /SSZ 1000.0 def /SS { /SSZ exch 100.0 mul def RDF} bind def /AF { /WFT exch findfont def /SSZ exch 100.0 mul def RDF} bind def /MT /moveto load def /XM {currentpoint exch pop moveto} bind def /UL {gsave newpath moveto dup 2.0 div 0.0 exch rmoveto setlinewidth 0.0 rlineto stroke grestore} bind def /LH {gsave newpath moveto setlinewidth 0.0 rlineto gsave stroke grestore} bind def /LV {gsave newpath moveto setlinewidth 0.0 exch rlineto gsave stroke grestore} bind def /BX {gsave newpath moveto setlinewidth exch dup 0.0 rlineto exch 0.0 exch neg rlineto neg 0.0 rlineto closepath gsave stroke grestore} bind def /BX1 {grestore} bind def /BX2 {setlinewidth 1 setgray stroke grestore} bind def /PB {/PV save def newpath translate 100.0 -100.0 scale pop /showpage {} def} bind def /PE {PV restore} bind def /GB {/PV save def newpath translate rotate div dup scale 100.0 -100.0 scale /showpage {} def /letter {} def /lettersmall {} def /note {} def } bind def /GE {PV restore} bind def /FB {dict dup /FontMapDict exch def begin} bind def /FM {cvn exch cvn exch def} bind def /FE {end /original-findfont /findfont load def /findfont {dup FontMapDict exch known{FontMapDict exch get} if original-findfont} def} bind def /BC {gsave moveto dup 0 exch rlineto exch 0 rlineto neg 0 exch rlineto closepath clip} bind def /EC /grestore load def /SH /show load def /MX {exch show 0.0 rmoveto} bind def /W {0 32 4 -1 roll widthshow} bind def /WX {0 32 5 -1 roll widthshow 0.0 rmoveto} bind def /RC {100.0 -100.0 scale 612.0 0.0 translate -90.0 rotate .01 -.01 scale} bind def /URC {100.0 -100.0 scale 90.0 rotate -612.0 0.0 translate .01 -.01 scale} bind def /RCC {100.0 -100.0 scale 0.0 -792.0 translate 90.0 rotate .01 -.01 scale} bind def /URCC {100.0 -100.0 scale -90.0 rotate 0.0 792.0 translate .01 -.01 scale} bind def %%EndProlog %%Page: 0 1 BS 0 SI 15 /Times-Bold AF 20492 19005 MT (An MS-DOS File System for UNIX)SH 12 /Times-Italic AF 27462 21742 MT (Alessandro Forin)SH 27596 23354 MT (Gerald R. Malan)SH /Times-Roman SF 27763 24966 MT (September 1993)SH 27480 26578 MT (CMU-CS-93-196)SH 10 SS 25944 31617 MT (School of Computer Science)SH 26069 32994 MT (Carnegie Mellon University)SH 25332 34371 MT (Pittsburgh, Pennsylvania 15213)SH /Times-Italic SF 21110 37125 MT (A shorter version of this document will appear in the)SH 21042 38502 MT (Proceedings of the 1994 Winter USENIX Conference)SH 23458 39879 MT (January 17-21, 1994 San Francisco, CA.)SH /Times-Roman SF 8280 61886 MT (This research was sponsored by the Advanced Research Projects Agency) 379 W( \050DOD\051, under contract number)378 W 8280 63172 MT (DABT63-93-C-0054. The) 258 W( views and conclusions contained in this document are those of the authors and should not)5 W 8280 64458 MT (be interpreted as representing the official policies, either expressed) 75 W( or implied, of the Defense Advanced Research)74 W 8280 65744 MT (Projects Agency or the US Government.})SH ES %%Page: 1 2 BS 0 SI 10 /Times-Roman AF 54580 4286 MT (1)SH 13 /Times-Bold AF 29261 8071 MT (Abstract)SH 10 /Times-Roman AF 8280 10444 MT (We have written DosFs, a new file system for UNIX that uses MS-DOS data structures for permanent) 157 W( storage.)158 W 8280 11730 MT (DosFs can) 1 W( be used anywhere a traditional UNIX file system can be used, and it can mount disks written by MS-DOS)SH 8280 13016 MT (as regular UNIX partitions. DosFs can be used as the root partition, and) 1 W( exported by an NFS server. Our motivation)2 W 8280 14302 MT (for this work was efficient disk) 67 W( space utilization; DosFs provides from 10% to 13% better disk utilization than the)66 W 8280 15588 MT (4.3 BSD Fast File System \050FFS\051. In addition, we) 38 W( found that the disk block allocation algorithm used by DosFs lets)39 W 8280 16874 MT (us exploit large contiguous disk) 86 W( operations, providing a five-fold improvement over FFS for uncached operations.)85 W 8280 18160 MT (To the best of our knowledge, this is the first file system) 55 W( implementation that allows the user to specify the logical)56 W 8280 19446 MT (block size) 24 W( at mount time. A user can mount the same file system with a larger block size when file accesses tend to)23 W 8280 20732 MT (be sequential and a smaller one when they tend to be scattered. The MS-DOS structures) 174 W( were designed for a)175 W 8280 22018 MT (single-user system and do not) 169 W( support access control. We solved this problem with simple extensions that are)168 W 8280 23304 MT (backward-compatible with MS-DOS.)SH ES %%Page: 2 3 BS 0 SI 10 /Times-Roman AF 6120 4286 MT (2)SH /Times-Bold SF 7120 62577 MT (Keywords)SH /Times-Roman SF (: Operating Systems, File Systems, Disk Storage, Unix, MS-DOS, Mach, DosFs)SH ES %%Page: 3 4 BS 0 SI 10 /Times-Roman AF 54580 4286 MT (3)SH 14 /Times-Bold AF 8280 8138 MT (1. Introduction)SH 10 /Times-Roman AF 9280 9515 MT (Today's micro-kernel architectures make it possible to) 550 W( run multiple operating system environments)551 W 8280 10892 MT (simultaneously. For) 380 W( example, a) 65 W( notebook computer running Mach 3.0) 64 W( [2]) SH( can have both UNIX and MS-DOS disk)64 W 8280 12269 MT (partitions. In) 396 W( fact, an MS-DOS emulator) 73 W( [12]) SH( can) 73 W( be started from within the UNIX environment so that Windows)74 W 8280 13646 MT (applications can run in parallel with UNIX applications.) 51 W( Unfortunately,) 351 W( UNIX cannot access files on the MS-DOS)50 W 8280 15023 MT (partition while the) 27 W( MS-DOS emulator can access all UNIX files. The perception from UNIX is that part of the disk)28 W 8280 16400 MT (is missing, causing inconvenience both in resource utilization and in the sharing of data) 87 W( between applications that)86 W 8280 17777 MT (belong to the two different worlds.) 81 W( Other) 413 W( commercial MS-DOS emulators have similar limitations. A number of)82 W 8280 19154 MT (toolsets do exist to) 149 W( let UNIX users access MS-DOS floppies and disks, but they only transfer data between the)148 W 8280 20531 MT (UNIX and) 15 W( MS-DOS file systems. The best solution is an integrated file system that empowers all existing tools and)16 W 8280 21908 MT (applications.)SH 9280 24387 MT (We had both technical) 39 W( and practical motivations for this work. On the technical side, we wanted to examine and)38 W 8280 25764 MT (compare the permanent data structures used by MS-DOS and) 194 W( FFS, check whether it was possible to extend a)195 W 8280 27141 MT (single-user file system like the MS-DOS) 117 W( one into a multi-user safe, networked file system, and understand some)116 W 8280 28518 MT (initial performance figures) 1 W( for uncached disk accesses. On the practical side, we wanted to extend our UNIX system)2 W 8280 29895 MT (to support more disk formats, including) 8 W( MS-DOS and the ISO 9660) 7 W( [5]) SH( disk formats. Some of our users expressed a)7 W 8280 31272 MT (desire to have the UNIX backup and restore utilities work on their MS-DOS data.) 15 W( Finally,) 282 W( a UNIX local file system)16 W 8280 32649 MT (should be usable as the root file system for a multi-user UNIX system.)SH 9280 35128 MT (There are very few file systems for UNIX that handle permanent) 98 W( storage, the latest BSD 4.4 release has added)97 W 8280 36505 MT (LFS to the only one that was previously provided. There) 63 W( are a few other file systems outside of the BSD sources,)64 W 8280 37882 MT (but they all use permanent) 52 W( data structures similar to the original UFS ones. The permanent data structures used by)51 W 8280 39259 MT (MS-DOS are) 228 W( different enough from the standard UNIX ones to make it interesting to explore the effects on)229 W 8280 40636 MT (functionality and performance. For example, there are no inodes in MS-DOS.)SH 9280 43115 MT (The MS-DOS file system was designed for a single-user environment, on a personal computer. UNIX) 45 W( is used in)44 W 8280 44492 MT (multi-user, possibly security-sensitive environments. On security grounds, the single-user file) 63 W( system model is not)64 W 8280 45869 MT (acceptable on UNIX. For instance,) 9 W( MS-DOS has no provisions for storing user ids or access control information, but)8 W 8280 47246 MT (it is not acceptable to make files and directories readable and writeable by all users. The models of) 12 W( the expected file)13 W 8280 48623 MT (system usage might instead be closer. On) 34 W( UNIX, it is common to assume a time-sharing model, such as was traced)33 W 8280 50000 MT (by John Ousterhout) 39 W( [10]) SH( in his investigations of the 4.2 BSD file system. But even the most powerful workstations)40 W 8280 51377 MT (today are typically used by a single user at a time,) 198 W( and the file systems themselves use sophisticated caching)197 W 8280 52754 MT (strategies. It) 250 W( might well be that the MS-DOS model is quite appropriate for most UNIX users after all.)SH 9280 55233 MT (In our initial tests) 63 W( we found that native MS-DOS 5.0 was up to five times faster than our emulated UNIX \050BSD)64 W 8280 56610 MT (4.3 on top of Mach 3.0\051 for large uncached reads, and four times faster than the monolithic Mach 2.5.) 8 W( We) 264 W( traced the)7 W 8280 57987 MT (disk operations with a SCSI bus analyzer to) 30 W( find an explanation. We found that the MS-DOS file was contiguously)31 W 8280 59364 MT (allocated and) 17 W( was being accessed with four times larger block sizes \050e.g. 16 KB at a time\051 just like our user program)16 W 8280 60741 MT (was requesting. The FFS file was allocated in an interleaved fashion to cope with) 111 W( rotational delays) 112 W( [8],) SH( and was)112 W 8280 62118 MT (being accessed at the file system block size, 4 KB. The extra seek times accounted for the remaining discrepancies.)SH 9280 64597 MT (Assuming we were able) 96 W( to reach the same optimal disk allocation for files as in MS-DOS, we realized that we)95 W 8280 65974 MT (could provide new functionality to our users, namely the ability to specify the disk access size \050logical block) 71 W( size\051)72 W 8280 67351 MT (dynamically, at mount time. Depending on prevailing) 84 W( use, with DosFs we can either use a small or a large block)83 W 8280 68728 MT (size, whichever gets the best performance, without any need for rebuilding the file system.) 51 W( A) 354 W( smaller block size is)52 W 8280 70105 MT (preferable in case buffer-cache misses are non-sequential and dispersed across the file) 7 W( system. A larger block size is)6 W 8280 71482 MT (best in the more common case that accesses tend to be sequential and clustered around a few files at a time.)SH ES %%Page: 4 5 BS 0 SI 10 /Times-Roman AF 6120 4286 MT (4)SH 7120 7886 MT (Finally, we wanted to support the ISO file system organization \050and the RockRidge) 468 W( extensions for)469 W 6120 9263 MT (POSIX/UNIX [13]\051) SH( that is standard in CD-ROM disks. We started the project with some code) 144 W( written by Pace)143 W 6120 10640 MT (Willisson at) 157 W( Berkeley, which provided a read-only ISO file system implementation. The code was missing the)158 W 6120 12017 MT (RockRidge \050RR\051 extensions and the file handle operations for use with NFS. Both were easy to) 71 W( add. Support for)70 W 6120 13394 MT (the MS-DOS file system looked, at first,) 179 W( like another simple addition because the ISO file system has various)180 W 6120 14771 MT (similarities with the MS-DOS file system. We just had to add the write-part--- which turned out to) 89 W( be more than)88 W 6120 16148 MT (twice the initial code.)SH 7120 18627 MT (The remainder of the paper is structured as follows. Section 2 describes) 114 W( the organization of the MS-DOS file)115 W 6120 20004 MT (system and permanent) 163 W( disk data. We assume the reader has some knowledge of the BSD FFS data structures,)162 W 6120 21381 MT (descriptions can be found in) 145 W( [8, 7].) SH( Section) 540 W( 3 details the main design and) 145 W( implementation problems. Section 4)146 W 6120 22758 MT (illustrates the programs we) 300 W( wrote for file system maintainance. In Section 5 we look at the performance)299 W 6120 24135 MT (optimizations from the following viewpoint. We use native, uncached MS-DOS as the) 163 W( base for each test. Each)164 W 6120 25512 MT (optimization is described and its individual effect quantified relative to either the) 155 W( base or the final performance)154 W 6120 26889 MT (figure. In) 280 W( many cases we can use run-time flags to toggle a specific optimization on or) 15 W( off to help us understand the)16 W 6120 28266 MT (measurements. Section) 272 W( 6 reports on the first evaluation criteria we used, namely the disk) 11 W( utilization profiles for FFS)10 W 6120 29643 MT (and MS-DOS.) 229 W( Section) 710 W( 7 describes the testing setup and the results of various performance tests. The tests)230 W 6120 31020 MT (themselves were taken from those commonly used in the file system literature and were) 118 W( selected to illustrate the)117 W 6120 32397 MT (effects of one or more performance optimizations. In Section 8) 83 W( we point out similar and related work and finally)84 W 6120 33774 MT (draw a few conclusions from our experience and illustrate the status and availability of the code.)SH 14 /Times-Bold AF 6120 37592 MT (2. The MS-DOS File System Structure)SH 10 /Times-Roman AF 7120 38969 MT (Starting from the first sector of a disk, the) 45 W( MS-DOS file system layout is as follows; further details can be found)44 W 6120 40346 MT (in [1]. The initial section of the disk contains the primary \0501 sector\051 and the secondary bootstraps) SH( \050a variable number)1 W 6120 41723 MT (of sectors\051. This is followed by one or) 80 W( more copies of the File Allocation Table \050FAT\051, which is followed by the)79 W 6120 43100 MT (root directory entries. The rest of) 149 W( the disk is divided into dynamically allocated)150 W /Times-Italic SF 40349 XM (clusters)SH /Times-Roman SF (. Figure) 550 W( 1 graphically)150 W 6120 44477 MT (depicts this layout.)SH 7120 46956 MT (The first sector of the disk contains the primary bootstrap) 56 W( code, intermixed with geometry information about the)55 W 6120 48333 MT (disk and possibly) 97 W( partitioning information. It also records the location, size and number of FATs, the size of the)98 W 6120 49710 MT (root directory, and the size of physical sectors and clusters.) 107 W( The) 463 W( primary bootstrap code uses this information to)106 W 6120 51087 MT (load the secondary bootstrap code into memory and transfer control to it.)SH 7120 53566 MT (The FAT is a) 27 W( fixed size table that describes the allocation status of the disk's clusters. Entries are either 12 or 16)28 W 6120 54943 MT (bits wide, depending on the total number of clusters in the disk partition. A floppy) 35 W( has a 12 bit FAT, a fixed disk a)34 W 6120 56320 MT (16 bit FAT.) 90 W( The) 431 W( first two FAT entries are reserved. MS-DOS uses a single FAT copy on floppy disks, and two)91 W 6120 57697 MT (copies on fixed disks to protect against disk corruption. DosFs accepts and keeps coherent any number of) 28 W( copies of)27 W 6120 59074 MT (the FAT.)SH 7120 61553 MT (To determine which disk blocks are allocated) 39 W( to a file \050or directory\051 we must start from the file's directory entry.)40 W 6120 62930 MT (The entry contains the file's starting cluster number, e.g. the first block of the file.) 61 W( To) 371 W( find the next block, we use)60 W 6120 64307 MT (the cluster number as an index in) 19 W( the FAT. The value at that entry is the cluster number of the second block, and so)20 W 6120 65684 MT (on. The) 308 W( last block of the file has a FAT entry value of -1. If a cluster is not allocated, its FAT entry) 29 W( is zero. Other)28 W 6120 67061 MT (distinguished values are used to indicate reserved clusters \050bad blocks, for instance\051.)SH ES %%Page: 5 6 BS 0 SI 10 /Times-Roman AF 54580 4286 MT (5)SH 1 1 0 -5720 67200 GB %%BeginDocument: dospict.ps %!PS-Adobe-2.0 EPSF-1.2 %%DocumentFonts: Helvetica-Bold Helvetica %%%Pages: 1 %%BoundingBox: 140 244 393 600 %%EndComments 50 dict begin /arrowHeight 8 def /arrowWidth 4 def /none null def /numGraphicParameters 17 def /stringLimit 65535 def /Begin { save numGraphicParameters dict begin } def /End { end restore } def /SetB { dup type /nulltype eq { pop false /brushRightArrow idef false /brushLeftArrow idef true /brushNone idef } { /brushDashOffset idef /brushDashArray idef 0 ne /brushRightArrow idef 0 ne /brushLeftArrow idef /brushWidth idef false /brushNone idef } ifelse } def /SetCFg { /fgblue idef /fggreen idef /fgred idef } def /SetCBg { /bgblue idef /bggreen idef /bgred idef } def /SetF { /printSize idef /printFont idef } def /SetP { dup type /nulltype eq { pop true /patternNone idef } { /patternGrayLevel idef patternGrayLevel -1 eq { /patternString idef } if false /patternNone idef } ifelse } def /BSpl { 0 begin storexyn newpath n 1 gt { 0 0 0 0 0 0 1 1 true subspline n 2 gt { 0 0 0 0 1 1 2 2 false subspline 1 1 n 3 sub { /i exch def i 1 sub dup i dup i 1 add dup i 2 add dup false subspline } for n 3 sub dup n 2 sub dup n 1 sub dup 2 copy false subspline } if n 2 sub dup n 1 sub dup 2 copy 2 copy false subspline patternNone not brushLeftArrow not brushRightArrow not and and { ifill } if brushNone not { istroke } if 0 0 1 1 leftarrow n 2 sub dup n 1 sub dup rightarrow } if end } dup 0 4 dict put def /Circ { newpath 0 360 arc patternNone not { ifill } if brushNone not { istroke } if } def /CBSpl { 0 begin dup 2 gt { storexyn newpath n 1 sub dup 0 0 1 1 2 2 true subspline 1 1 n 3 sub { /i exch def i 1 sub dup i dup i 1 add dup i 2 add dup false subspline } for n 3 sub dup n 2 sub dup n 1 sub dup 0 0 false subspline n 2 sub dup n 1 sub dup 0 0 1 1 false subspline patternNone not { ifill } if brushNone not { istroke } if } { Poly } ifelse end } dup 0 4 dict put def /Elli { 0 begin newpath 4 2 roll translate scale 0 0 1 0 360 arc patternNone not { ifill } if brushNone not { istroke } if end } dup 0 1 dict put def /Line { 0 begin 2 storexyn newpath x 0 get y 0 get moveto x 1 get y 1 get lineto brushNone not { istroke } if 0 0 1 1 leftarrow 0 0 1 1 rightarrow end } dup 0 4 dict put def /MLine { 0 begin storexyn newpath n 1 gt { x 0 get y 0 get moveto 1 1 n 1 sub { /i exch def x i get y i get lineto } for patternNone not brushLeftArrow not brushRightArrow not and and { ifill } if brushNone not { istroke } if 0 0 1 1 leftarrow n 2 sub dup n 1 sub dup rightarrow } if end } dup 0 4 dict put def /Poly { 3 1 roll newpath moveto -1 add { lineto } repeat closepath patternNone not { ifill } if brushNone not { istroke } if } def /Rect { 0 begin /t exch def /r exch def /b exch def /l exch def newpath l b moveto l t lineto r t lineto r b lineto closepath patternNone not { ifill } if brushNone not { istroke } if end } dup 0 4 dict put def /Text { ishow } def /idef { dup where { pop pop pop } { exch def } ifelse } def /ifill { 0 begin gsave patternGrayLevel -1 ne { fgred bgred fgred sub patternGrayLevel mul add fggreen bggreen fggreen sub patternGrayLevel mul add fgblue bgblue fgblue sub patternGrayLevel mul add setrgbcolor eofill } { eoclip originalCTM setmatrix pathbbox /t exch def /r exch def /b exch def /l exch def /w r l sub ceiling cvi def /h t b sub ceiling cvi def /imageByteWidth w 8 div ceiling cvi def /imageHeight h def bgred bggreen bgblue setrgbcolor eofill fgred fggreen fgblue setrgbcolor w 0 gt h 0 gt and { l b translate w h scale w h true [w 0 0 h neg 0 h] { patternproc } imagemask } if } ifelse grestore end } dup 0 8 dict put def /istroke { gsave brushDashOffset -1 eq { [] 0 setdash 1 setgray } { brushDashArray brushDashOffset setdash fgred fggreen fgblue setrgbcolor } ifelse brushWidth setlinewidth originalCTM setmatrix stroke grestore } def /ishow { 0 begin gsave fgred fggreen fgblue setrgbcolor /fontDict printFont findfont printSize scalefont dup setfont def /descender fontDict begin 0 [FontBBox] 1 get FontMatrix end transform exch pop def /vertoffset 0 descender sub printSize sub printFont /Courier ne printFont /Courier-Bold ne and { 1 add } if def { 0 vertoffset moveto show /vertoffset vertoffset printSize sub def } forall grestore end } dup 0 3 dict put def /patternproc { 0 begin /patternByteLength patternString length def /patternHeight patternByteLength 8 mul sqrt cvi def /patternWidth patternHeight def /patternByteWidth patternWidth 8 idiv def /imageByteMaxLength imageByteWidth imageHeight mul stringLimit patternByteWidth sub min def /imageMaxHeight imageByteMaxLength imageByteWidth idiv patternHeight idiv patternHeight mul patternHeight max def /imageHeight imageHeight imageMaxHeight sub store /imageString imageByteWidth imageMaxHeight mul patternByteWidth add string def 0 1 imageMaxHeight 1 sub { /y exch def /patternRow y patternByteWidth mul patternByteLength mod def /patternRowString patternString patternRow patternByteWidth getinterval def /imageRow y imageByteWidth mul def 0 patternByteWidth imageByteWidth 1 sub { /x exch def imageString imageRow x add patternRowString putinterval } for } for imageString end } dup 0 12 dict put def /min { dup 3 2 roll dup 4 3 roll lt { exch } if pop } def /max { dup 3 2 roll dup 4 3 roll gt { exch } if pop } def /arrowhead { 0 begin transform originalCTM itransform /taily exch def /tailx exch def transform originalCTM itransform /tipy exch def /tipx exch def /dy tipy taily sub def /dx tipx tailx sub def /angle dx 0 ne dy 0 ne or { dy dx atan } { 90 } ifelse def gsave originalCTM setmatrix tipx tipy translate angle rotate newpath 0 0 moveto arrowHeight neg arrowWidth 2 div lineto arrowHeight neg arrowWidth 2 div neg lineto closepath patternNone not { originalCTM setmatrix /padtip arrowHeight 2 exp 0.25 arrowWidth 2 exp mul add sqrt brushWidth mul arrowWidth div def /padtail brushWidth 2 div def tipx tipy translate angle rotate padtip 0 translate arrowHeight padtip add padtail add arrowHeight div dup scale arrowheadpath ifill } if brushNone not { originalCTM setmatrix tipx tipy translate angle rotate arrowheadpath istroke } if grestore end } dup 0 9 dict put def /arrowheadpath { newpath 0 0 moveto arrowHeight neg arrowWidth 2 div lineto arrowHeight neg arrowWidth 2 div neg lineto closepath } def /leftarrow { 0 begin y exch get /taily exch def x exch get /tailx exch def y exch get /tipy exch def x exch get /tipx exch def brushLeftArrow { tipx tipy tailx taily arrowhead } if end } dup 0 4 dict put def /rightarrow { 0 begin y exch get /tipy exch def x exch get /tipx exch def y exch get /taily exch def x exch get /tailx exch def brushRightArrow { tipx tipy tailx taily arrowhead } if end } dup 0 4 dict put def /midpoint { 0 begin /y1 exch def /x1 exch def /y0 exch def /x0 exch def x0 x1 add 2 div y0 y1 add 2 div end } dup 0 4 dict put def /thirdpoint { 0 begin /y1 exch def /x1 exch def /y0 exch def /x0 exch def x0 2 mul x1 add 3 div y0 2 mul y1 add 3 div end } dup 0 4 dict put def /subspline { 0 begin /movetoNeeded exch def y exch get /y3 exch def x exch get /x3 exch def y exch get /y2 exch def x exch get /x2 exch def y exch get /y1 exch def x exch get /x1 exch def y exch get /y0 exch def x exch get /x0 exch def x1 y1 x2 y2 thirdpoint /p1y exch def /p1x exch def x2 y2 x1 y1 thirdpoint /p2y exch def /p2x exch def x1 y1 x0 y0 thirdpoint p1x p1y midpoint /p0y exch def /p0x exch def x2 y2 x3 y3 thirdpoint p2x p2y midpoint /p3y exch def /p3x exch def movetoNeeded { p0x p0y moveto } if p1x p1y p2x p2y p3x p3y curveto end } dup 0 17 dict put def /storexyn { /n exch def /y n array def /x n array def n 1 sub -1 0 { /i exch def y i 3 2 roll put x i 3 2 roll put } for } def %%EndProlog %I Idraw 7 Grid 8 %%%Page: 1 1 Begin %I b u %I cfg u %I cbg u %I f u %I p u %I t [ 0.8 0 0 0.8 0 0 ] concat /originalCTM matrix currentmatrix def Begin %I Poly %I b 65535 2 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 148 197 ] concat %I 4 121 112 121 550 340 550 340 112 4 Poly End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-bold-r-*-140-* /Helvetica-Bold 14 SetF %I t [ 1 0 0 1 306 708 ] concat %I [ (File Allocation Table) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-bold-r-*-140-* /Helvetica-Bold 14 SetF %I t [ 1 0 0 1 329.5 566 ] concat %I [ (Root Directory) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-bold-r-*-140-* /Helvetica-Bold 14 SetF %I t [ 1 0 0 1 334 471 ] concat %I [ (File Clusters) ] Text End Begin %I Line %I b 65535 2 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 149 423 ] concat %I 120 294 339 294 Line End Begin %I Line %I b 65535 2 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 149 194 ] concat %I 120 294 339 294 Line End Begin %I Line %I b 65535 2 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 149 284 ] concat %I 120 294 339 294 Line End Begin %I BSpl %I b 65535 1 0 1 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 148 227 ] concat %I 4 141 301 81 351 101 421 171 440 4 BSpl End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-medium-r-*-120-* /Helvetica 12 SetF %I t [ 1 0 0 1 290 448 ] concat %I [ (Cluster #) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-medium-r-*-120-* /Helvetica 12 SetF %I t [ 1 0 0 1 309 427 ] concat %I [ (22) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-medium-r-*-120-* /Helvetica 12 SetF %I t [ 1 0 0 1 309 389 ] concat %I [ (34) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-medium-r-*-120-* /Helvetica 12 SetF %I t [ 1 0 0 1 309 349 ] concat %I [ (56) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-bold-r-*-140-* /Helvetica-Bold 14 SetF %I t [ 1 0 0 1 179 737 ] concat %I [ (Beginning) (of Disk) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-bold-r-*-140-* /Helvetica-Bold 14 SetF %I t [ 1 0 0 1 179 329 ] concat %I [ (End of Disk) ] Text End Begin %I Poly %I b 65535 1 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 148 217 ] concat %I 4 141 291 141 331 320 331 320 291 4 Poly End Begin %I Pict %I b u %I cfg u %I cbg u %I f u %I p u %I t [ 1 0 0 1 226 211 ] concat Begin %I Line %I b 65535 2 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 168 217 ] concat %I 48 183 51 182 Line End Begin %I Line %I b 65535 2 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 178 217 ] concat %I 48 183 51 182 Line End Begin %I Line %I b 65535 2 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 188 217 ] concat %I 48 183 51 182 Line End End %I eop Begin %I Pict %I b u %I cfg u %I cbg u %I f u %I p u %I t [ 1 0 0 1 70 272 ] concat Begin %I Line %I b 65535 2 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 168 217 ] concat %I 48 183 51 182 Line End Begin %I Line %I b 65535 2 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 178 217 ] concat %I 48 183 51 182 Line End Begin %I Line %I b 65535 2 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 188 217 ] concat %I 48 183 51 182 Line End End %I eop Begin %I Pict %I b u %I cfg u %I cbg u %I f u %I p u %I t [ 1 0 0 1 0 9 ] concat Begin %I Line %I b 65535 1 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 148 147 ] concat %I 131 441 330 441 Line End Begin %I Line %I b 65535 1 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 148 207 ] concat %I 131 441 330 441 Line End Begin %I Line %I b 65535 1 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 148 177 ] concat %I 131 441 330 441 Line End Begin %I Line %I b 65535 1 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 149 237 ] concat %I 131 441 330 441 Line End Begin %I Pict %I b u %I cfg u %I cbg u %I f u %I p u %I t [ 1 0 0 1 10 0 ] concat Begin %I Pict %I b u %I cfg u %I cbg u %I f u %I p u %I t [ 1 0 0 1 -13 -4 ] concat Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-medium-r-*-120-* /Helvetica 12 SetF %I t [ 1 0 0 1 329 677 ] concat %I [ (Index 22) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-medium-r-*-120-* /Helvetica 12 SetF %I t [ 1 0 0 1 329 665 ] concat %I [ (Value 34) ] Text End End %I eop Begin %I Line %I b 65535 1 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 138 197 ] concat %I 171 480 171 451 Line End Begin %I Line %I b 65535 1 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 198 197 ] concat %I 171 480 171 451 Line End End %I eop Begin %I Pict %I b u %I cfg u %I cbg u %I f u %I p u %I t u Begin %I Pict %I b u %I cfg u %I cbg u %I f u %I p u %I t [ 1 0 0 1 83 4 ] concat Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-medium-r-*-120-* /Helvetica 12 SetF %I t [ 1 0 0 1 329 638 ] concat %I [ (Index 34) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-medium-r-*-120-* /Helvetica 12 SetF %I t [ 1 0 0 1 329 626 ] concat %I [ (Value 56) ] Text End End %I eop Begin %I Line %I b 65535 1 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 148 197 ] concat %I 260 451 260 421 Line End Begin %I Line %I b 65535 1 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 148 197 ] concat %I 320 451 320 421 Line End End %I eop Begin %I Pict %I b u %I cfg u %I cbg u %I f u %I p u %I t u Begin %I Pict %I b u %I cfg u %I cbg u %I f u %I p u %I t [ 1 0 0 1 14 12 ] concat Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-medium-r-*-120-* /Helvetica 12 SetF %I t [ 1 0 0 1 329 601 ] concat %I [ (Index 56) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-medium-r-*-120-* /Helvetica 12 SetF %I t [ 1 0 0 1 330 589 ] concat %I [ (Value -1) ] Text End End %I eop Begin %I Line %I b 65535 1 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 148 197 ] concat %I 251 421 251 391 Line End Begin %I Line %I b 65535 1 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 148 197 ] concat %I 191 391 191 421 Line End End %I eop End %I eop Begin %I Pict %I b u %I cfg u %I cbg u %I f u %I p u %I t [ 1 0 0 1 0 19 ] concat Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-medium-r-*-120-* /Helvetica 12 SetF %I t [ 1 0 0 1 369 408 ] concat %I [ (File data block 1) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-medium-r-*-120-* /Helvetica 12 SetF %I t [ 1 0 0 1 369 369 ] concat %I [ (File data block 2) ] Text End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-medium-r-*-120-* /Helvetica 12 SetF %I t [ 1 0 0 1 369 329 ] concat %I [ (File data block 3) ] Text End Begin %I Rect %I b 65535 1 0 1 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 148 197 ] concat %I 211 192 320 221 Rect End Begin %I Rect %I b 65535 1 0 1 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 148 197 ] concat %I 211 152 320 182 Rect End Begin %I Rect %I b 65535 1 0 1 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 148 197 ] concat %I 211 112 320 142 Rect End End %I eop Begin %I Line %I b 65535 1 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 148 197 ] concat %I 131 490 131 401 Line End Begin %I Line %I b 65535 1 0 0 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 148 197 ] concat %I 330 490 330 401 Line End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-medium-r-*-120-* /Helvetica 12 SetF %I t [ 1 0 0 1 290 538 ] concat %I [ (An example directory entry has) (a file starting at cluster 22.) ] Text End Begin %I BSpl %I b 65535 1 0 1 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 148 197 ] concat %I 3 290 431 287 412 251 411 3 BSpl End Begin %I BSpl %I b 65535 1 0 1 [] 0 SetB %I cfg Black 0 0 0 SetCFg %I cbg White 1 1 1 SetCBg none SetP %I p n %I t [ 1 0 0 1 148 197 ] concat %I 3 231 480 290 480 290 461 3 BSpl End Begin %I Text %I cfg Black 0 0 0 SetCFg %I f *-helvetica-bold-r-*-140-* /Helvetica-Bold 14 SetF %I t [ 1 0 0 1 340 737 ] concat %I [ (Boot Sectors) ] Text End End %I eop showpage %%Trailer end %%EndDocument GE /Times-Bold SF 20792 45515 MT (Figure 1:)SH /Times-Roman SF 25208 XM (Organization Of The MS-DOS File System)SH 9280 49099 MT (Directory entries are fixed in size, 32 bytes) 42 W( each. Every entry contains the name and extension, an attribute byte)43 W 8280 50476 MT (that indicates, among other things, if this is a directory or) 199 W( a file, a timestamp, the size of the entry \050zero for)198 W 8280 51853 MT (directories\051, and the starting cluster number. There is room for 10 more bytes that are defined as reserved by) 21 W( the file)22 W 8280 53230 MT (system specifications. The upper two bits of the attribute byte are also) 18 W( reserved/undefined. In the initial versions of)17 W 8280 54607 MT (MS-DOS, the root directory was the only directory and it) 23 W( could not grow. Later versions of MS-DOS are backward)24 W 8280 55984 MT (compatible and also have a) 67 W( fixed, contiguously preallocated root directory. The root directory is therefore special,)66 W 8280 57361 MT (fixed both in size and disk location at file system creation time. Other directories can be grown/shrunk as necessary.)6 W 8280 58738 MT (Some directory entries are special, and identified as such by) 158 W( the attribute byte. The MS-DOS image itself, for)157 W 8280 60115 MT (instance, is marked invisible and read-only.)104 W /Times-Bold SF 26922 XM (Label)SH /Times-Roman SF 29722 XM (entries contain information about the creation time of the file)105 W 8280 61492 MT (system, and the volume name. There is only supposed to be one such label entry, in the root directory.)SH 9280 63971 MT (Clusters are logical blocks, e.g. multiples of the physical sectors. Their size is typically 512 bytes on small)165 W 8280 65348 MT (floppies and 2048 bytes on) 220 W( fixed disks. Just as in FFS, any cluster can contain either file data or directory)221 W 8280 66725 MT (information. Unlike) 376 W( FFS, no other type of information \050metadata\051 is recorded in the clusters. The cluster size) 63 W( can)62 W 8280 68102 MT (actually be set to any power of two multiple of the physical sector size, similarly to) 54 W( the fragment size in the UNIX)55 W 8280 69479 MT (BSD file system. Unlike BSD, the cluster size can be up to a 16 bit multiple of the sector size. In practice, the)103 W 8280 70856 MT (upper limit supported by MS-DOS is 64 KB.)SH ES %%Page: 6 7 BS 0 SI 10 /Times-Roman AF 6120 4286 MT (6)SH 14 /Times-Bold AF 6120 8138 MT (3. Design Issues)SH 10 /Times-Roman AF 7120 9515 MT (The MS-DOS file system evolved from its CP/M predecessor, it) 95 W( is aimed exclusively at a single-user machine,)96 W 6120 10892 MT (with no protection between users of the) 27 W( file storage. It strives to minimize resource utilization, both in memory and)26 W 6120 12269 MT (on disk. But it lacks features present in UNIX file systems, such as file links.)SH 7120 14748 MT (DosFs is implemented as a) 48 W( layer of code below the virtual file system \050Vnode\051 layer) 49 W( [6].) SH( The) 348 W( Vnode layer has a)49 W 6120 16125 MT (well defined interface, which must) 138 W( be fully implemented to cover all aspects of UNIX file system functionality.)137 W 6120 17502 MT (This presented us with various design) 34 W( issues, which we will describe in the rest of the section. Table 1 summarizes)35 W 6120 18879 MT (these issues, and indicates how they are solved in the various file systems.)SH 46800 50 6120 20184 UL 8 /Times-Italic AF 6120 21298 MT (Problem)SH 15480 XM (FFS)SH 24840 XM (IsoFs)SH 34200 XM (MS-DOS)SH 43560 XM (DosFs)SH 2755 50 6120 21498 UL 1378 50 15480 21498 UL 1777 50 24840 21498 UL 2888 50 34200 21498 UL 2089 50 43560 21498 UL /Times-Bold SF 6120 22684 MT (Access Control)SH 15480 XM (inodes)SH 24840 XM (extended attributes)SH 34200 XM (none)SH 43560 XM (directory ext. or)SH 43560 23388 MT (mount option)SH 6120 24774 MT (Filename size)SH 15480 XM (255)SH 24840 XM (30 or)SH 34200 XM (11)SH 43560 XM (11)SH 24840 25478 MT (RR unlimited)SH 6120 26864 MT (Filename chars)SH 15480 XM (ASCII)SH 24840 XM (Upcase+)SH 34200 XM (Upcase++)SH 43560 XM (mount option)SH 6120 28250 MT (Inode numbering)SH 15480 XM (Inode Table)SH 24840 XM (Extent num)SH 34200 XM (N/A)SH 43560 XM (Cluster num)SH 6120 29636 MT (Links)SH 15480 XM (hard+soft)SH 24840 XM (hard+soft with)SH 34200 XM (none)SH 43560 XM (soft)SH 24840 30340 MT (RR extensions)SH 6120 31726 MT (NFS access)SH 15480 XM (inode num)SH 24840 XM (inode + dir)SH 34200 XM (N/A)SH 43560 XM (inode + dir)SH 6120 33112 MT (Special devices)SH 15480 XM (standard)SH 24840 XM (RR ext.)SH 34200 XM (no)SH 43560 XM (directory ext.)SH 6120 34498 MT (Setuid files)SH 15480 XM (standard)SH 24840 XM (RR ext.)SH 34200 XM (no)SH 43560 XM (directory ext.)SH 46800 50 6120 36084 UL 10 SS 15646 37422 MT (Table 1:)SH /Times-Roman SF 19674 XM (Permanent Data Structures And UNIX Functionality Issues)SH 12 /Times-Bold AF 6120 41106 MT (3.1. Protection)SH 10 /Times-Roman AF 7120 42483 MT (In FFS, a directory entry contains only the name of the file and the inode number. A separate table, the inode)94 W 6120 43860 MT (table, contains a 128 byte record) 24 W( for each inode with various information, including the user-id, group-id and access)25 W 6120 45237 MT (permissions of the inode, its type and \050a portion of\051 the list of blocks owned by the inode. There) 6 W( are no inodes in the)5 W 6120 46614 MT (MS-DOS file system, and a) 37 W( directory entry does not have the user-id, group-id, or access mode information \050except)38 W 6120 47991 MT (for read-only files\051. There are two approaches for adding access protection to DosFs.) 16 W( We) 280 W( could use the 10 reserved)15 W 6120 49368 MT (bytes to store the extra information or we could dynamically calculate the access permission for each file.)SH 7120 51847 MT (The first approach is acceptable) 272 W( if MS-DOS applications ignore those 10 bytes \050they do\051 or if backward)273 W 6120 53224 MT (compatibility and interoperability) 27 W( are not concerns. It is our goal to interact as smoothly as possible with MS-DOS,)26 W 6120 54601 MT (including potential applications that might themselves store) 178 W( information in those reserved bytes. Therefore we)179 W 6120 55978 MT (provide the extended information option only if DosFs is mounted as) 25 W( the root partition, or if explicitly requested via)24 W 6120 57355 MT (mount options. In practice, we have not yet found an MS-DOS application that would look at) 184 W( the content of)185 W 6120 58732 MT (reserved bits and bytes, nor does MS-DOS itself complain or reset these bytes.) 49 W( A) 346 W( disk utility \050such as our)48 W /Times-Italic SF 49643 XM (dosfsck)SH /Times-Roman SF (\051)SH 6120 60109 MT (can simply) 225 W( reset the extra protection information, to guarantee 100% compatibility with MS-DOS. We have)226 W 6120 61486 MT (designed our extensions so that no data is lost if the access information is destroyed.)SH 7120 63965 MT (For the second approach there are several possibilities:)SH 8120 65304 MT (1.)SH 9120 XM ([root,wheel] owns all files; write permissions depend on mount mode \050read-only prevents all) 92 W( writes\051)91 W 9120 66409 MT (and on the read-only bit in the attribute byte; all users have equal access rights;)SH 8120 68167 MT (2.)SH 9120 XM (same as above, but the user who issued the mount command) 133 W( is substituted for [root,wheel]; access)134 W 9120 69272 MT (modes are taken from the umask and propagated to all files;) 67 W( other users have access rights as per the)66 W 9120 70377 MT (umask;)SH ES %%Page: 7 8 BS 0 SI 10 /Times-Roman AF 54580 4286 MT (7)SH 10280 7886 MT (3.)SH 11280 XM (allow the user to) 48 W( specify an arbitrary user-id, group-id, and access mode mask; otherwise, same as #2)49 W 11280 8991 MT (above;)SH 9280 11470 MT (All three options) 24 W( essentially give the same ownership to all files, they just specify this ownership differently. We)23 W 8280 12847 MT (selected option #2 as) 122 W( default because it allows a user to mount his/her volumes and access them safely via NFS)123 W 8280 14224 MT (without any special options. Privileged users or operators can use option #3.)SH 9280 16703 MT (Regardless of the mount options, if a file on disk has the special) 238 W( extension marker we use the protection)237 W 8280 18080 MT (information stored on disk; only the mode mask is used to mask off specific bits. An) 208 W( interesting use of the)209 W 8280 19457 MT (user-specified mode mask is to disable setuid programs or execute permissions, regardless of their value on disk.)106 W 8280 20834 MT (This could be used by a cautious operator when mounting suspicious floppy disks on a general-purpose machine,) 31 W( to)32 W 8280 22211 MT (get rid of Viruses.)SH 9280 24690 MT (A possible alternative was to make use of the special)121 W /Times-Italic SF 31874 XM (label)SH /Times-Roman SF 34244 XM (directory entries. MS-DOS specifies that they are)120 W 8280 26067 MT (optional and they would only appear in the root directory.) 21 W( We) 294 W( could put a label entry on each directory, to store the)22 W 8280 27444 MT (protection information. This idea is similar to the AFS Access Control Lists, which are) 66 W( set on a per-directory, not)65 W 8280 28821 MT (per-file basis [14]. We were told by Microsoft that it is not a good idea to misuse label entries.)SH 9280 31300 MT (The ISO file system defines)79 W /Times-Italic SF 21090 XM (extended attributes)79 W /Times-Roman SF 29136 XM (that provide protection) 79 W( information, including owner and group)80 W 8280 32677 MT (identifiers, and permissions. These are stored along with the file data in the first block of the file,) 78 W( separated from)77 W 8280 34054 MT (any directory entry information. ISO leaves open the mapping of this information onto the) 170 W( receiving system's)171 W 8280 35431 MT (administrative database.)SH 12 /Times-Bold AF 8280 39115 MT (3.2. File Naming)SH 10 /Times-Roman AF 9280 40492 MT (MS-DOS file names are limited to 12 characters, 8 bytes) 30 W( of name proper, an implied dot character to separate the)29 W 8280 41869 MT (file extension, and three characters of extension \050suffix\051.) 64 W( The) 380 W( ASCII space character must be used to pad both the)65 W 8280 43246 MT (name and the extension fields. The MS-DOS specifications only dictate 8-bit ASCII characters but) 87 W( some internal)86 W 8280 44623 MT (MS-DOS functions converts all characters to uppercase. Therefore) 163 W( in practice all file names in MS-DOS have)164 W 8280 46000 MT (uppercase only ASCII) 122 W( characters, and digits. Special punctuation symbols are discouraged; some might produce)121 W 8280 47377 MT (peculiar effects.)SH 9280 49856 MT (The ISO file system sets a total) 6 W( limit of 30 characters on a file name, not counting the dot separator between name)7 W 8280 51233 MT (and extension and the trailing version information) 254 W( \050a semicolon followed by a digit\051. The only permissible)253 W 8280 52610 MT (characters are) 116 W( digits, uppercase letters, and underscore. The RockRidge \050POSIX\051 extensions use only the ASCII)117 W 8280 53987 MT (codes for letters and digits, period, underscore and hyphen. Extra information is added to a directory) 170 W( entry to)169 W 8280 55364 MT (express a file name in this POSIX format and) 55 W( bypass the ISO restrictions. This file name encoding scheme has no)56 W 8280 56741 MT (maximum length.)SH 9280 59220 MT (UNIX BSD file names have a) 62 W( set limit of 255 characters, and no restrictions on their content except for the first)61 W 8280 60597 MT (seven bits) 23 W( of the ASCII code. In principle, raising the 255 limit would be just a matter of modifying one define and)24 W 8280 61974 MT (recompile. There) 250 W( is only one function that imposes the seven bit restriction in our 4.3 BSD file system code.)SH 9280 64453 MT (To cope with this jungle of rules and) 4 W( exceptions we wrote separate file name comparison and translation functions)3 W 8280 65830 MT (for the) 34 W( FFS, DosFs and the ISO file systems. In the case of the ISO file system, these handle the RR extension and)35 W 8280 67207 MT (recover the original UNIX names, bypassing the ISO limitations. The file name length limitation for) 36 W( MS-DOS was)35 W 8280 68584 MT (found to be the most irritating to our users. We resolved the) 45 W( problem using one of the reserved bits in the attribute)46 W 8280 69961 MT (byte to signify the entry contains a long name. The immediately following directory) 31 W( entry has an attribute byte that)30 W 8280 71338 MT (qualifies it as a label entry, but contains instead 31 more bytes of the file name. Under DOS the) 127 W( name appears)128 W ES %%Page: 8 9 BS 0 SI 10 /Times-Roman AF 6120 4286 MT (8)SH 6120 7886 MT (truncated.)SH 7120 10365 MT (We also removed the uppercase-only limitation: at mount time it is possible to specify) 108 W( one of three translation)107 W 6120 11742 MT (options. File) 348 W( names can be untranslated \050except for the) 49 W( implied dot between name and extension\051 and look exactly)50 W 6120 13119 MT (as they would under MS-DOS. Or we can map letters to lowercase and clean up the extra spaces,) 130 W( to make file)129 W 6120 14496 MT (names look more UNIX-like. This is the default option. When used as a root file system we use a) 12 W( third scheme that)13 W 6120 15873 MT (treats name and extension as a single) 108 W( string, without any implied "dot" and without case conversions. This third)107 W 6120 17250 MT (option provides the most "proper" feeling for UNIX users, but it might make the) 81 W( file name unacceptable to native)82 W 6120 18627 MT (MS-DOS.)SH 12 /Times-Bold AF 6120 22311 MT (3.3. Inode Numbering)SH 10 /Times-Roman AF 7120 23688 MT (FFS maintains permanent inode tables on disk, and there is a direct mapping) 45 W( from inode number to disk address.)44 W 6120 25065 MT (Since ISO file systems do not have inode tables we used the first block number) 9 W( of directories and files \050the)10 W /Times-Italic SF 49244 XM (extent)SH /Times-Roman SF (, in)10 W 6120 26442 MT (ISO parlance\051 as the inode number. We maintained this scheme for the DosFs file system, the only modification) 41 W( is)40 W 6120 27819 MT (that our)23 W /Times-Italic SF 9499 XM (dosfs_ialloc\050\051)SH /Times-Roman SF 15272 XM (function must procure a cluster each time we create a new "inode". For) 23 W( directories this is not)24 W 6120 29196 MT (a problem since a directory by definition must contain) 35 W( at least the dot and dot-dot entries \050this is true of both UNIX)34 W 6120 30573 MT (and MS-DOS\051 and therefore can never be totally empty. For files this) 33 W( means that zero-length files still own at least)34 W 6120 31950 MT (one cluster. Special devices are the only inodes for which we might safely and) 53 W( quickly optimize away this cluster,)52 W 6120 33327 MT (by dynamically generating impossible cluster) 144 W( numbers and modifying the file system utilities to recognize these)145 W 6120 34704 MT (directory entries.)SH 7120 37183 MT (This simple scheme no longer worked) 118 W( when we added the RockRidge extensions to the ISO file system. The)117 W 6120 38560 MT (problem is with symbolic links. In ISO a symbolic) 76 W( link is entirely defined in the directory entry, it does not have)77 W 6120 39937 MT (any associated disk space.) 211 W( We) 671 W( could have used extension-specific knowledge, such as looking into the extra)210 W 6120 41314 MT (information provided by the RR records that include an inode number. Instead, we took an approach that should still)SH 6120 42691 MT (work with some other future extensions to the ISO standard. The high bits of) 48 W( the inode number are the extent, and)47 W 6120 44068 MT (for regular files) 109 W( and directories, the low bits are zero. For symlinks, the high bits are the extent of the directory)110 W 6120 45445 MT (where the symlink lives, the low bits are a function of the directory entry \050e.g. the offset) 39 W( in the extent\051. Any given)38 W 6120 46822 MT (ISO extension need only tell if this is a symlink or not, the existing code will build the inode number appropriately.)SH 12 /Times-Bold AF 6120 50506 MT (3.4. Hard/Symbolic Links)SH 10 /Times-Roman AF 7120 51883 MT (MS-DOS has neither symbolic links nor hard links. Implementing symbolic links) 41 W( was simple. We just took one)42 W 6120 53260 MT (unused bit in the attribute byte of) 163 W( the directory entries to mark the entry as having our special extensions, and)162 W 6120 54637 MT (another bit in the extension bytes to indicate a symbolic link.) 32 W( We) 315 W( store in the link's cluster the file name the link is)33 W 6120 56014 MT (pointing at, just like FFS. For MS-DOS the file is a regular file of length equal to the link name, and the content) 30 W( of)29 W 6120 57391 MT (the file is the link name itself.)SH 7120 59870 MT (Short FFS symlinks can be optimized by using the direct) 51 W( block fields of the inode to store the file name this is a)52 W 6120 61247 MT (link to, avoiding one disk access while doing expansion of symbolic links. DosFs) 21 W( has no inodes and cannot use this)20 W 6120 62624 MT (optimization. Notice,) 336 W( however, that in terms of disk accesses DosFs is always at par with the optimized case. FFS)43 W 6120 64001 MT (must access the directory entry, the inode, and \050possibly\051 the link name.) 37 W( DosFs) 323 W( must access the directory entry and)36 W 6120 65378 MT (\050always\051 the link name.)SH 7120 67857 MT (Hard links are more difficult. One approach is to just build another entry that points to the same starting) 43 W( cluster.)44 W 6120 69234 MT (This creates two problems: uniqueness of inode numbers is lost, and there is no obvious way to keep) 14 W( \050on permanent)13 W 6120 70611 MT (storage\051 a reference count of the number of entries) 151 W( that point to the same inode. The first problem means, for)152 W 6120 71988 MT (instance, that size and other attributes that are stored in a directory entry are not) 38 W( kept coherent, unless the entry that)37 W ES %%Page: 9 10 BS 0 SI 10 /Times-Roman AF 54580 4286 MT (9)SH 8280 7886 MT (is a hard link actually points back to the original entry it is a link to. Since a cluster can hold a number of directory)30 W 8280 9263 MT (entries this variation can still perform well, for the higher probability of finding the pointed-to entry in) 3 W( memory. But)2 W 8280 10640 MT (more importantly, the second problem) 52 W( means that there is no way to know when an inode can actually be released.)53 W 8280 12017 MT (One solution to this problem is to use more of those 10 reserved bytes to hold a hard link count.)SH 9280 14496 MT (Note that these issues do not arise on ISO CD-ROM file) 124 W( systems for the simple reason that the file system is)123 W 8280 15873 MT (immutable. The) 726 W( RockRidge extensions do support symbolic links, and they also provide reference counting.)238 W 8280 17250 MT (Implementing hard links and making a mutable ISO file system is therefore feasible.)SH 9280 19729 MT (For expediency, we chose to implement symlinks but) 21 W( not hard links. We needed symbolic links to handle the file)20 W 8280 21106 MT (system structure with more flexibility, especially when DosFs is the root. We did not find any mandatory) 32 W( reason to)33 W 8280 22483 MT (have hard links, so we left the issue open for future extensions.)SH 12 /Times-Bold AF 8280 26167 MT (3.5. NFS Access)SH 10 /Times-Roman AF 9280 27544 MT (Exporting a \050local\051 file system via NFS) 157 W( is not difficult. The NFS layer gives to client machines a)156 W /Times-Italic SF 50952 XM (handle)SH /Times-Roman SF 54080 XM (on)SH 8280 28921 MT (Vnodes, the local file system provides functions to build such a handle and map it back to a Vnode. FFS handles)74 W 8280 30298 MT (contain just the inode number and a generation number for coherency purposes.) 129 W( Neither ISO nor MS-DOS have)128 W 8280 31675 MT (inode tables separate from directory information, we could not use just the inode number as is done in) 58 W( FFS. If the)59 W 8280 33052 MT (inode is not in the cache we need to refer back to some directory entry to recover size,) 56 W( modes and timestamps of a)55 W 8280 34429 MT (DosFs or ISO inode. This is also true with the RockRidge extensions to ISO.)SH 9280 36908 MT (The handle that is exported to remote nodes in NFS has a predefined size, but) 165 W( fortunately it is opaque. No)166 W 8280 38285 MT (application appears to make special use of the content of an FFS handle. We added two more fields to the) 38 W( FFS file)37 W 8280 39662 MT (handle scheme, the cluster number of the directory that contains an entry for the given inode, and the offset) 57 W( of this)58 W 8280 41039 MT (entry. If) 280 W( the) 15 W( inode is not in core it can be reconstructed by recovering the original directory, checking its coherency,)14 W 8280 42416 MT (and looking up the directory entry. Note that protection issues are no different when access is via NFS than when)64 W 8280 43793 MT (access is local.)SH 12 /Times-Bold AF 8280 47477 MT (3.6. Other extensions)SH 10 /Times-Roman AF 9280 48854 MT (When we first tried to use DosFs as) 6 W( a root file system on a DEC Alpha workstation we discovered a small number)5 W 8280 50231 MT (of other problems. To begin with, we had) 130 W( to modify both the boot programs and the Mach default pager) 131 W( [3]) SH( to)131 W 8280 51608 MT (understand the MS-DOS file) 87 W( system structures. The first must be able to find, read in, and transfer control to the)86 W 8280 52985 MT (boot image. The second) 27 W( has similar needs with respect to the UNIX server image. In addition, it might have to use)28 W 8280 54362 MT (a DosFs file system for paging purposes.)SH 9280 56841 MT (We then) 173 W( found a number of instances in file system-independent UNIX code where FFS data structures and)172 W 8280 58218 MT (semantics were assumed. For instance, mounting of the root file system itself was special cased) 67 W( for FFS and NFS)68 W 8280 59595 MT (and so was the checking of special device close operations against mounted file systems. Even) 31 W( the shutdown of the)30 W 8280 60972 MT (system assumed the root was) 90 W( an FFS file system. We also saw no reason why the root file system should not be)91 W 8280 62349 MT (un-mounted, e.g. on clean shutdowns of the system.)SH 9280 64828 MT (Two more extensions were necessary to get the system up in multiuser mode. The) 123 W( first and most obvious, in)122 W 8280 66205 MT (hindsight, was the need for special devices.) 108 W( We) 467 W( used the)109 W /Times-Italic SF 32495 XM (mode)SH /Times-Roman SF 35020 XM (extension field to mark a file as a UNIX special)109 W 8280 67582 MT (device and stored the major/minor information in the reserved) 71 W( bytes. Special devices are the directory entries that)70 W 8280 68959 MT (make the most use of the reserved bytes in MS-DOS directory entries; all 10 bytes are used up.)SH 9280 71438 MT (The second, slightly less) 13 W( obvious, was the need for setuid programs. CMU UNIX runs the single user shell not as)14 W ES %%Page: 10 11 BS 0 SI 10 /Times-Roman AF 6120 4286 MT (10)SH /Times-Italic SF 6120 7886 MT (root)SH /Times-Roman SF 8037 XM (but as the less privileged user)SH /Times-Italic SF 20091 XM (opr)SH /Times-Roman SF (, therefore we just could not do much without encountering a protection block.)SH 6120 9263 MT (Once again, we used the)77 W /Times-Italic SF 16502 XM (mode)SH /Times-Roman SF 18995 XM (field for this information, making it almost identical to the FFS)78 W /Times-Italic SF 45354 XM (i_mode)SH /Times-Roman SF 48626 XM (field. The)406 W 6120 10640 MT (only difference is that DosFs does not support the special mode value used by)119 W /Times-Italic SF 39171 XM (badsect\0501\051)SH /Times-Roman SF 43761 XM (for creating bad) 119 W( block)118 W 6120 12017 MT (files. There) 250 W( is no need for this, the FAT defines special entry values to mark unusable clusters.)SH 14 /Times-Bold AF 6120 15835 MT (4. Tools)SH 10 /Times-Roman AF 7120 17212 MT (While developing DosFs we found) 206 W( the need for tools to accomplish a variety of tasks, such as file system)207 W 6120 18589 MT (construction, check and repair, bad block handling, analysis, and tuning. We patterned a) 37 W( small set of tools after the)36 W 6120 19966 MT (well known UNIX ones:)112 W /Times-Italic SF 16623 XM (dosmkfs)SH /Times-Roman SF (,)SH /Times-Italic SF 20458 XM (dosfsck)SH /Times-Roman SF (,)SH /Times-Italic SF 24015 XM (dosbadsect)SH /Times-Roman SF (,)SH /Times-Italic SF 29072 XM (dosdumpfs)SH /Times-Roman SF (. All) 476 W( of the tools are considerably simpler and)113 W 6120 21343 MT (smaller than their FFS counterparts. The)188 W /Times-Italic SF 24101 XM (dostunefs)SH /Times-Roman SF 28316 XM (program is actually just a compaction tool that reallocates)187 W 6120 22720 MT (clusters on disk to keep file/directory data contiguous for best performance. We hardly ever) 38 W( use it. A similar effect)39 W 6120 24097 MT (can be obtained simply with) 220 W( a dump/dosmkfs/restore, but with tunefs there is no need for a separate tape or)219 W 6120 25474 MT (temporary disk partition.)SH 7120 27953 MT (Once we started to use) 33 W( DosFs as root partition we decided to actually integrate dosfsck back into fsck, which can)34 W 6120 29330 MT (now handle either type of file system, including support for the so-called "preen) 168 W( mode". This is the way fsck)167 W 6120 30707 MT (operates non-interactively, e.g. during automatic reboots.) 85 W( There) 421 W( are only two very embarrassing cases where fsck)86 W 6120 32084 MT (will not automatically repair the disk:) 116 W( when) 480 W( an allocation chain in the FAT has a loop and when two allocation)115 W 6120 33461 MT (chains merge. FFS and fsck have many more mutual) 235 W( understandings of accidents that "should not happen".)236 W 6120 34838 MT (Another strange property) 51 W( of the DosFs fsck is that it is CPU-intensive, not I/O intensive. Most of the time is spent)50 W 6120 36215 MT (verifying the FAT allocation chains in memory, I/O operations to read directory entries take little time.)SH 14 /Times-Bold AF 6120 40033 MT (5. Optimizations)SH 10 /Times-Roman AF 7120 41410 MT (A number of optimizations came to us for free, by using the UNIX) 154 W( buffer cache for I/O. These include the)155 W 6120 42787 MT (caching of I/O buffers, read-ahead for sequential file accesses, and delayed-writes. Other optimizations were trivial)32 W 6120 44164 MT (to add, such as caching of name lookups. Handling of) 60 W( the FAT table was simplified by its modest size. Based on)61 W 6120 45541 MT (our SCSI traces, and on McVoy's work on extent-based performance [9], we implemented large I/O operations.)SH 7120 48020 MT (The effects) 35 W( of I/O buffer caching are illustrated in Section 7, by comparing native MS-DOS and DosFs small file)34 W 6120 49397 MT (accesses. On) 334 W( a well-tuned) 42 W( UNIX system, cached read and write operations should perform almost at memory copy)43 W 6120 50774 MT (speed. For) 708 W( illustration purposes, we have intentionally avoided the use of any) 229 W( of the many native MS-DOS)228 W 6120 52151 MT (extensions that would perform) 40 W( file caching. For instance, Microsoft provides the SmartDrive optional driver which)41 W 6120 53528 MT (Windows 3.1 installs by default. With this proviso, read and) 46 W( write operations that hit in the cache are from 3 to 15)45 W 6120 54905 MT (times faster in DosFs than native MS-DOS.)SH 7120 57384 MT (The benefit of delayed writes is) 55 W( illustrated by the)56 W /Times-Bold SF 27477 XM (crtdel)SH /Times-Roman SF 30282 XM (test, where a relatively small file is created, written and)56 W 6120 58761 MT (deleted a number of times. The performance gain over the uncached case is up to a factor of 40.) 114 W( If) 476 W( we disable)113 W 6120 60138 MT (read-aheads, the elapsed) 16 W( time for the sequential, uncached read of a 5 MB DosFs file in 2 KB blocks increases 30%.)17 W 6120 61515 MT (The effective bandwidth drops from 480 KB/sec to 340 KB/sec.)SH 7120 63994 MT (The)SH /Times-Bold SF 8943 XM (crtdel)SH /Times-Roman SF 11710 XM (test reveals) 18 W( the effects of one interesting difference between FFS and DosFs. In FFS, directory entries)17 W 6120 65371 MT (and the inode table must be kept coherent in spite of potential power failures. When creating a new) 39 W( directory entry)40 W 6120 66748 MT (FFS incurs a cost of three writes. The first one is to the inode table, the second) 74 W( to the directory entry, and the last)73 W 6120 68125 MT (again to the inode table to set) 83 W( the reference count properly. Hard links require a proper handling of the reference)84 W 6120 69502 MT (count field. In DosFs we) 13 W( only need two writes, one to the directory entry and one to the FAT. This is still true even)12 W 6120 70879 MT (if we implemented) 2 W( hard links, because the reference count would have to be part of the directory entry itself, not of a)3 W ES %%Page: 11 12 BS 0 SI 10 /Times-Roman AF 54080 4286 MT (11)SH 8280 7886 MT (separate inode table.)SH 9280 10365 MT (Another optimization) 66 W( is caching of name lookups, which also came to us for free since the name cache operates)65 W 8280 11742 MT (on Vnodes and is therefore file system-independent. The effects of this optimization can be partially) 67 W( quantified in)68 W 8280 13119 MT (the)SH /Times-Bold SF 9840 XM (open)SH /Times-Roman SF 12234 XM (tests, where a file is repeatedly opened and) 88 W( immediately closed. FFS and DosFs get better times on the)87 W 8280 14496 MT (longer pathnames) 75 W( than MS-DOS, but the times show that MS-DOS is also doing name caching. If we disable the)76 W 8280 15873 MT (name cache DosFs incurs) 76 W( a 15% higher cost per component. Note that in this test the read operation necessary to)75 W 8280 17250 MT (reconstruct the inode will always) 46 W( hit in the buffer cache. If the system is loaded the read might miss, and the price)47 W 8280 18627 MT (will be much higher.)SH 9280 21106 MT (We decided to keep the FAT entirely in memory, to speed) 27 W( up many file access operations. The maximum size of)26 W 8280 22483 MT (a FAT is 128 KB, which would describe a 512 MB) 61 W( partition at a cluster size of 8 KB. In practice, most MS-DOS)62 W 8280 23860 MT (disk partitions are much smaller than) 31 W( this, for instance on a floppy the FAT is approximately 4 KB and on a 60 MB)30 W 8280 25237 MT (disk partition of) 4 W( 2 KB clusters the FAT is 60 KB. In terms of main memory consumption the FFS inode cache alone)5 W 8280 26614 MT (is much more expensive \050in our system\051 than the DosFs FAT table. In the) 196 W( Mach 3.0 system this memory is)195 W 8280 27991 MT (pageable. If) 456 W( we find that keeping the FAT in memory creates problems we can take advantage of the) 103 W( I/O buffer)104 W 8280 29368 MT (cache and reduce this) 26 W( memory cost to a user-specified number of I/O buffers per mounted file system. If frequently)25 W 8280 30745 MT (accessed, the FAT blocks will be) 55 W( found in the buffer cache. It is difficult to isolate the performance effects of this)56 W 8280 32122 MT (optimization, because the occasional I/O operations to recover the FAT would be unpredictably) 17 W( intertwined with the)16 W 8280 33499 MT (other I/O operations.)SH 9280 35978 MT (We applied other minor optimizations in the FAT handling code.) 35 W( For) 321 W( instance, every DosFs Vnode has a lookup)36 W 8280 37355 MT (hint that is used when mapping) 21 W( file offsets to disk clusters. We do not have to scan the entire allocation chain when)20 W 8280 38732 MT (doing sequential reads. We also optimized the rewriting) 134 W( of the FATs since they tended to be a noticeable cost,)135 W 8280 40109 MT (especially on the slow floppies. On each sync\0502\051 call we rewrite \050if modified\051) 59 W( only the primary FAT, the alternate)58 W 8280 41486 MT (FATs are rewritten only when the disk is unmounted. If we) 40 W( encounter a power failure the status of the disk will be)41 W 8280 42863 MT (as of the last sync\0502\051 call, and dosfsck takes care of rewriting the alternate FATs.)SH 9280 45342 MT (Our disk block allocation algorithm is extremely simple and) 154 W( similar to the one used by MS-DOS) 153 W( [1].) SH( When)556 W 8280 46719 MT (extending a file we scan forward in the FAT starting from the last block of the file. If we do not find a free) 49 W( block,)50 W 8280 48096 MT (then we) 125 W( scan backward from the last block of the file. When creating a new file or directory we start from \050an)124 W 8280 49473 MT (estimate of\051 the lowest) 144 W( numbered free block in the FAT. The first two rules tends to enforce sequentiality and)145 W 8280 50850 MT (clustering, the third tends to accumulate in-use blocks at the) 19 W( beginning of the disk, reducing seeking. The algorithm)18 W 8280 52227 MT (is extremely simple, and extremely effective if executed sequentially. It is not executed concurrently) 66 W( in MS-DOS,)67 W 8280 53604 MT (or for the most part, in our UNIX workstations.)SH 9280 56083 MT (The optimization that had the single most visible payoff was to perform I/O in) 50 W( sizes larger than the file system's)49 W 8280 57460 MT (cluster size. This is possible) 200 W( because the block allocation algorithm is very effective in keeping a file's data)201 W 8280 58837 MT (contiguous. We) 256 W( can essentially chose any size for I/O and use) 3 W( it as the equivalent of the FFS logical block size. The)2 W 8280 60214 MT (DosFs logical block size is specified by the user) 3 W( at mount time. The default value of 16 KB was chosen because it is)4 W 8280 61591 MT (the knee in the performance curve across several disks, and across) 135 W( three types of workstations, but we make no)134 W 8280 62968 MT (claims as to its generality and) 46 W( applicability. The implementation is simple, we use a special version of)47 W /Times-Italic SF 50395 XM (bmap\050\051)SH /Times-Roman SF 53580 XM (that)SH 8280 64345 MT (returns the start and size of the contiguous chunk of disk that contains a given cluster.)SH 9280 66824 MT (One last) 112 W( optimization we adopted from MS-DOS: we do not force the users to discover optimizations on their)111 W 8280 68201 MT (own, unless they are really obvious. This is in sharp contrast with the FFS philosophy. In) 29 W( [8]) SH( it was advocated that)29 W 8280 69578 MT (users would know the characteristics of all disks and even) 103 W( the speed of their processors relative to the disks they)102 W 8280 70955 MT (used. Users) 400 W( would otherwise perform experiments to define the) 75 W( correct values for the file system parameters, and)76 W ES %%Page: 12 13 BS 0 SI 10 /Times-Roman AF 6120 4286 MT (12)SH 6120 7886 MT (use tunefs\0501\051 to optimize them. There is only one tuning parameter in) 56 W( DosFs, the logical block size for large I/Os.)55 W 6120 9263 MT (This is optionally decided at mount time, has an appropriate default, and the meaning is more intuitive than most)94 W 6120 10640 MT (FFS parameters \050and/or combinations thereof\051.)SH 14 /Times-Bold AF 6120 14458 MT (6. Disk Utilization)SH 10 /Times-Roman AF 7120 15835 MT (In this section we analyze the overheads and the costs for metadata in DosFs, and we) 88 W( compare them with FFS.)87 W 6120 17212 MT (We have performed a simple experiment involving the storing of a set of files on a floppy disk, and we have) 12 W( derived)13 W 6120 18589 MT (the formulas that characterize the space requirements of the two file systems.)SH 46800 50 6120 19894 UL 8 /Times-Italic AF 6120 21008 MT (Allocation Size)SH 15480 XM (Waste)SH 24840 XM (FFS free)SH 34200 XM (DosFs free)SH 43560 XM (Difference)SH 3332 50 6120 21208 UL 1288 50 9652 21208 UL 1954 50 15480 21208 UL 1378 50 24840 21208 UL 1243 50 26418 21208 UL 2089 50 34200 21208 UL 1243 50 36489 21208 UL 3375 50 43560 21208 UL /Times-Bold SF 6120 22394 MT (512)SH 15480 XM (50 KB)SH 24840 XM (326 KB)SH 34200 XM (422 KB)SH 43560 XM (+29%)SH 6120 23780 MT (1024)SH 15480 XM (105 KB)SH 24840 XM (273 KB)SH 34200 XM (368 KB)SH 43560 XM (+34%)SH 6120 25166 MT (2048)SH 15480 XM (220 KB)SH 24840 XM (138 KB)SH 34200 XM (260 KB)SH 43560 XM (+88%)SH 6120 26552 MT (4096)SH 15480 XM (475 KB)SH 24840 XM (-86 KB)SH 34200 XM (4 KB)SH 43560 XM (n/a)SH 46800 50 6120 28138 UL 10 SS 15658 29476 MT (Table 2:)SH /Times-Roman SF 19686 XM (A Simple Utilization Test: Moving Data To A Floppy Disk)SH 7120 31955 MT (The data set included two software packages in sources,) 27 W( objects, documentation files and man pages for a total of)26 W 6120 33332 MT (978,634 bytes in 194 files and 7 directories. The floppy media has a formatted capacity of) 209 W( 2880 sectors, or)210 W 6120 34709 MT (1,474,560 bytes. Table 2 illustrates the results) 52 W( of unpacking the data from a)51 W /Times-Italic SF 37476 XM (tar\0501\051)SH /Times-Roman SF 40110 XM (file onto the floppy file system.)51 W 6120 36086 MT (Four cases each for FFS and DosFs are presented, with fragment/cluster sizes ranging from 512) 32 W( to 4096 bytes. The)33 W 6120 37463 MT (FFS block size was) 58 W( kept constant, 4096 bytes. We report the amount of free space after the unpacking \050a negative)57 W 6120 38840 MT (value indicates the amount of data that did not fit\051, as reported by df\0501\051. The FFS entry at 4096 bytes is) 34 W( misleading)35 W 6120 40217 MT (since not all of the) 66 W( data fit on disk. DosFs leaves from 30% to 80% more free blocks than FFS, depending on the)65 W 6120 41594 MT (allocation size. If we compute the overhead in disk bytes used versus bytes in the data set) 73 W( we find that FFS costs)74 W 6120 42971 MT (between 16% and 36%, while DosFs costs between 6% and 23%.)SH 7120 45450 MT (The first column reports the number of) 73 W( bytes wasted due to fragmentation. Suppose we put a one-byte file in a)72 W 6120 46827 MT (single directory on the floppy. We will need one disk block for the directory, and one) 9 W( for the file. Most of the bytes)10 W 6120 48204 MT (in the two blocks are wasted, in DosFs we really needed 33 bytes) 94 W( and we used instead 1024 bytes, or more. We)93 W 6120 49581 MT (computed the) 81 W( fragmentation by looking at each file and directory and evaluating the extra bytes on disk that were)82 W 6120 50958 MT (allocated and unused because data did not fill a block. The space wasted is approximately) 52 W( the same in the two file)51 W 6120 52335 MT (systems and originates for the most) 105 W( part from files. This measure is important in two respects. It shows that an)106 W 6120 53712 MT (improper allocation block size can easily cost 40% of the available space on disk.) 34 W( It) 317 W( demonstrate that Extent Based)33 W 6120 55089 MT (allocation, which is equivalent to even larger allocation sizes, is an expensive proposition for typical UNIX files.)SH 7120 57568 MT (Let us now) 65 W( look more closely at the overheads incurred for meta-data in the two file systems, by comparing the)66 W 6120 58945 MT (total per-file disk costs for a file of length)9 W /Times-Bold SF 23115 XM (F)SH /Times-Roman SF 23985 XM (in a file system) 9 W( of fragment/cluster size)8 W /Times-Bold SF 40069 XM (A)SH /Times-Roman SF (. In) 266 W( the formulas,)8 W /Times-Bold SF 48191 XM (ceil)SH /Times-Roman SF (\050X,Y\051 is)8 W 6120 60322 MT (the function that rounds up X to the nearest Y multiple. DosFs will use)SH /Courier-Bold SF 10920 62127 MT (DosFsCost = D + \050B * Ceil\050 F/A, 1 \051\051 + Ceil\050 F, A \051)SH 10920 64389 MT (D = Ceil\050 Nd * 32 , A \051 / Nd)SH /Times-Roman SF 7120 66868 MT (bytes on disk, where)61 W /Times-Bold SF 15835 XM (Nd)SH /Times-Roman SF 17424 XM (is the number of files) 61 W( in the same directory and)62 W /Times-Bold SF 37148 XM (B)SH /Times-Roman SF 38127 XM (is the number of bytes per cluster in)62 W 6120 68245 MT (the FAT, e.g. 2 for a disk and 1.5 for a floppy. The three terms of the sum represent the cost)99 W /Times-Bold SF 45541 XM (D)SH /Times-Roman SF 46612 XM (in the directory)99 W 6120 69622 MT (entry, the FAT, and the file itself. The FAT cost is paid once at file system creation time, and) 24 W( with the exception of)25 W 6120 70999 MT (the root directory all other costs are dynamic allocations.) 16 W( The) 280 W( fixed, upfront cost for DosFs in the \050best\051 floppy case)15 W ES %%Page: 13 14 BS 0 SI 10 /Times-Roman AF 54080 4286 MT (13)SH 8280 7886 MT (is 2 KB, in a 60 MB disk partition this is 64 KB.)SH 75 100 0 5280 28191 GB %%BeginDocument: util2.ps %!PS-Adobe-2.0 %%DocumentFonts: (atend) %%Creator: PLOT X1.1c %%%Pages: 1 %%BoundingBox: 40 40 328 256 %%EndComments /MT {moveto} bind def /LT {lineto} bind def /sethsbcolor {setgray pop pop} bind def /x2sqrt3 2 sqrt 3 mul def % % () x y o DoLText % % Left justified text. /DoLText { gsave 3 1 roll translate rotate newpath 0 0 moveto show grestore } def % % () x y o DoRText % % Right justified text. /DoRText { gsave 3 1 roll translate rotate dup stringwidth pop neg 0 translate newpath 0 0 moveto show grestore } def % % () x y o DoCText % % Center justified text. /DoCText { gsave 3 1 roll translate rotate dup stringwidth pop 2 div neg 0 translate newpath 0 0 moveto show grestore } def % % Symbol Definitions % % /SymbolStart { gsave [] 0 setdash 3 1 roll translate dup dup scale 1 exch div setlinewidth newpath } def /SBox { SymbolStart -3 -3 moveto 3 -3 lineto 3 3 lineto -3 3 lineto closepath stroke grestore } def /SBullet { SymbolStart 0 0 3 0 360 arc fill grestore } def /SCircle { SymbolStart 0 0 3 0 360 arc stroke grestore } def /SCross { SymbolStart -3 -3 moveto 3 3 lineto stroke -3 3 moveto 3 -3 lineto stroke grestore } def /SCustom { pop pop pop } def /SDel { SymbolStart x2sqrt3 2 moveto x2sqrt3 neg 2 lineto 0 -4 lineto closepath stroke grestore } def /SPlus { SymbolStart -3 0 moveto 3 0 lineto stroke 0 -3 moveto 0 3 lineto stroke grestore } def /SDiamond { SymbolStart 45 rotate -3 -3 moveto 3 -3 lineto 3 3 lineto -3 3 lineto closepath stroke grestore } def /SEllipse { SymbolStart 2 1 scale 0 0 3 0 360 arc closepath stroke grestore } def /SNone { pop pop pop } def /SNumber { SymbolStart grestore } def /SSolidBox { SymbolStart -3 -3 moveto 3 -3 lineto 3 3 lineto -3 3 lineto closepath fill grestore } def /StarSide 6 36 cos div dup 36 sin mul sub 36 sin mul 36 cos div def /SStar { SymbolStart 0 3 translate -108 rotate 0 0 moveto 5 { StarSide 0 translate 0 0 lineto -72 rotate StarSide 0 translate 0 0 lineto 144 rotate } repeat closepath stroke grestore } def /STriangle { SymbolStart x2sqrt3 -2 moveto x2sqrt3 neg -2 lineto 0 4 lineto closepath stroke grestore } def % % ci w h o x y bar % /bar { gsave translate rotate % exch 2 div exch % ci w/2 h % newpath 2 copy pop 0 moveto 2 copy lineto 2 copy exch neg exch lineto 2 copy pop neg 0 lineto closepath stroke % ci w/2 h % 3 -1 roll dup 0 ne { % w/2 h ci 3 copy pop moveto % w/2 h ci 3 copy add lineto 3 copy add exch neg exch lineto 3 copy pop exch neg exch lineto stroke 3 copy pop moveto % w/2 h ci 3 copy sub lineto 3 copy sub exch neg exch lineto 3 copy pop exch neg exch lineto stroke currentlinewidth 2 mul setlinewidth pop 2 copy moveto exch neg exch lineto stroke } {pop pop pop } ifelse % grestore } def % % a linesfill % /linesfill { gsave clip initmatrix MFactor MFactor scale 0.5 setlinewidth rotate 1 dict begin /ksp 1000 MFactor div def ksp neg 5 ksp { % v newpath dup ksp exch moveto ksp neg exch lineto stroke } for end grestore newpath } def % % a lines2fill % /lines2fill { gsave clip initmatrix MFactor MFactor scale 0.5 setlinewidth rotate 1 dict begin /ksp 1000 MFactor div def ksp neg 8 ksp { % v newpath dup ksp exch moveto dup ksp neg exch lineto stroke 2 add dup ksp exch moveto ksp neg exch lineto stroke } for end grestore newpath } def % % a lineswfill % /lineswfill { gsave clip initmatrix MFactor MFactor scale 0.5 setlinewidth rotate 1 dict begin /ksp 1000 MFactor div def ksp neg 10 ksp { % v newpath dup ksp exch moveto ksp neg exch lineto stroke } for end grestore newpath } def /crosshatch { dup gsave linesfill grestore 90 add linesfill } def % % ci w h o x y {pg2} {pg1} linefillbar % /fillbar { 2 dict begin /pg1 exch def /pg2 exch def 6 copy % save bar parameters gsave translate rotate % exch 2 div exch % ci w/2 h 3 -1 roll % w/2 h ci % newpath % 3 copy pop pop neg 0 moveto 3 copy sub exch neg exch lineto 3 copy sub lineto 3 copy pop pop 0 lineto closepath pg1 % 3 copy sub exch neg exch moveto 3 copy add exch neg exch lineto 3 copy add lineto 3 copy sub lineto closepath pg2 % grestore pop pop pop bar end } def save %%EndProlog %%%Page: 1 1 save 40 40 translate 0.0 0.0 translate 1.000000 1.000000 scale /MFactor 1.000000 def 1.000000 setlinewidth [] 0 setdash newpath 54.3 209.6 MT 54.6 182.9 LT 55.3 144.8 LT 56.0 121.9 LT 56.8 106.6 LT 57.5 95.7 LT 58.2 87.5 LT 58.9 81.1 LT 59.6 76.0 LT 60.3 71.8 LT 61.0 68.3 LT 61.8 65.4 LT 62.5 62.8 LT 63.2 60.6 LT 63.9 58.7 LT 64.6 57.0 LT 65.3 55.5 LT 66.0 54.2 LT 66.8 52.9 LT 67.5 51.8 LT 68.2 50.8 LT 68.9 49.9 LT 69.6 49.1 LT 70.3 48.3 LT 71.1 47.6 LT 71.8 47.0 LT 72.5 46.4 LT 73.2 45.8 LT 73.9 45.2 LT 88.2 39.1 LT 102.5 36.4 LT 116.8 35.0 LT 131.1 34.0 LT 145.4 33.4 LT 159.7 32.9 LT 174.0 32.6 LT 188.3 32.3 LT 202.6 32.0 LT 216.9 31.9 LT 231.2 31.7 LT 245.5 31.6 LT 259.8 31.4 LT 274.1 31.3 LT stroke 1.000000 setlinewidth [] 0 setdash 54.6 182.9 1.0000 SNone 55.3 144.8 1.0000 SNone 56.0 121.9 1.0000 SNone 56.8 106.6 1.0000 SNone 57.5 95.7 1.0000 SNone 58.2 87.5 1.0000 SNone 58.9 81.1 1.0000 SNone 59.6 76.0 1.0000 SNone 60.3 71.8 1.0000 SNone 61.0 68.3 1.0000 SNone 61.8 65.4 1.0000 SNone 62.5 62.8 1.0000 SNone 63.2 60.6 1.0000 SNone 63.9 58.7 1.0000 SNone 64.6 57.0 1.0000 SNone 65.3 55.5 1.0000 SNone 66.0 54.2 1.0000 SNone 66.8 52.9 1.0000 SNone 67.5 51.8 1.0000 SNone 68.2 50.8 1.0000 SNone 68.9 49.9 1.0000 SNone 69.6 49.1 1.0000 SNone 70.3 48.3 1.0000 SNone 71.1 47.6 1.0000 SNone 71.8 47.0 1.0000 SNone 72.5 46.4 1.0000 SNone 73.2 45.8 1.0000 SNone 73.9 45.2 1.0000 SNone 88.2 39.1 1.0000 SNone 102.5 36.4 1.0000 SNone 116.8 35.0 1.0000 SNone 131.1 34.0 1.0000 SNone 145.4 33.4 1.0000 SNone 159.7 32.9 1.0000 SNone 174.0 32.6 1.0000 SNone 188.3 32.3 1.0000 SNone 202.6 32.0 1.0000 SNone 216.9 31.9 1.0000 SNone 231.2 31.7 1.0000 SNone 245.5 31.6 1.0000 SNone 259.8 31.4 1.0000 SNone 274.1 31.3 1.0000 SNone 1.000000 setlinewidth [2 3] 0 setdash 54.3 209.6 MT 54.6 181.9 LT 55.3 143.8 LT 56.0 120.9 LT 56.8 105.6 LT 57.5 94.7 LT 58.2 86.4 LT 58.9 80.1 LT 59.6 74.9 LT 60.3 70.8 LT 61.0 67.3 LT 61.8 64.3 LT 62.5 61.8 LT 63.2 59.6 LT 63.9 57.7 LT 64.6 56.0 LT 65.3 54.5 LT 66.0 53.1 LT 66.8 51.9 LT 67.5 50.8 LT 68.2 49.8 LT 68.9 48.9 LT 69.6 48.1 LT 70.3 47.3 LT 71.1 46.6 LT 71.8 45.9 LT 72.5 45.3 LT 73.2 44.7 LT 73.9 44.2 LT 88.2 38.1 LT 102.5 35.4 LT 116.8 34.0 LT 131.1 33.0 LT 145.4 32.4 LT 159.7 31.9 LT 174.0 31.5 LT 188.3 31.2 LT 202.6 31.0 LT 216.9 30.8 LT 231.2 30.7 LT 245.5 30.5 LT 259.8 30.4 LT 274.1 30.3 LT stroke 1.000000 setlinewidth [] 0 setdash 54.6 181.9 1.0000 SNone 55.3 143.8 1.0000 SNone 56.0 120.9 1.0000 SNone 56.8 105.6 1.0000 SNone 57.5 94.7 1.0000 SNone 58.2 86.4 1.0000 SNone 58.9 80.1 1.0000 SNone 59.6 74.9 1.0000 SNone 60.3 70.8 1.0000 SNone 61.0 67.3 1.0000 SNone 61.8 64.3 1.0000 SNone 62.5 61.8 1.0000 SNone 63.2 59.6 1.0000 SNone 63.9 57.7 1.0000 SNone 64.6 56.0 1.0000 SNone 65.3 54.5 1.0000 SNone 66.0 53.1 1.0000 SNone 66.8 51.9 1.0000 SNone 67.5 50.8 1.0000 SNone 68.2 49.8 1.0000 SNone 68.9 48.9 1.0000 SNone 69.6 48.1 1.0000 SNone 70.3 47.3 1.0000 SNone 71.1 46.6 1.0000 SNone 71.8 45.9 1.0000 SNone 72.5 45.3 1.0000 SNone 73.2 44.7 1.0000 SNone 73.9 44.2 1.0000 SNone 88.2 38.1 1.0000 SNone 102.5 35.4 1.0000 SNone 116.8 34.0 1.0000 SNone 131.1 33.0 1.0000 SNone 145.4 32.4 1.0000 SNone 159.7 31.9 1.0000 SNone 174.0 31.5 1.0000 SNone 188.3 31.2 1.0000 SNone 202.6 31.0 1.0000 SNone 216.9 30.8 1.0000 SNone 231.2 30.7 1.0000 SNone 245.5 30.5 1.0000 SNone 259.8 30.4 1.0000 SNone 274.1 30.3 1.0000 SNone 1.000000 setlinewidth [7 5 19 5] 0 setdash 55.5 209.6 MT 56.0 194.8 LT 56.8 179.5 LT 57.5 168.5 LT 58.2 160.3 LT 58.9 153.9 LT 59.6 148.8 LT 60.3 144.6 LT 61.0 141.1 LT 61.8 138.2 LT 62.5 135.7 LT 63.2 133.5 LT 63.9 131.5 LT 64.6 129.9 LT 65.3 128.3 LT 66.0 127.0 LT 66.8 125.8 LT 67.5 124.7 LT 68.2 123.7 LT 68.9 122.8 LT 69.6 121.9 LT 70.3 121.2 LT 71.1 120.4 LT 71.8 119.8 LT 72.5 119.2 LT 73.2 118.6 LT 73.9 118.1 LT 88.2 111.9 LT 102.5 109.3 LT 116.8 107.8 LT 131.1 106.9 LT 145.4 106.2 LT 159.7 105.8 LT 174.0 105.4 LT 188.3 105.1 LT 202.6 104.9 LT 216.9 104.7 LT 231.2 104.5 LT 245.5 104.4 LT 259.8 104.3 LT 274.1 104.2 LT stroke 1.000000 setlinewidth [] 0 setdash 56.0 194.8 1.0000 SNone 56.8 179.5 1.0000 SNone 57.5 168.5 1.0000 SNone 58.2 160.3 1.0000 SNone 58.9 153.9 1.0000 SNone 59.6 148.8 1.0000 SNone 60.3 144.6 1.0000 SNone 61.0 141.1 1.0000 SNone 61.8 138.2 1.0000 SNone 62.5 135.7 1.0000 SNone 63.2 133.5 1.0000 SNone 63.9 131.5 1.0000 SNone 64.6 129.9 1.0000 SNone 65.3 128.3 1.0000 SNone 66.0 127.0 1.0000 SNone 66.8 125.8 1.0000 SNone 67.5 124.7 1.0000 SNone 68.2 123.7 1.0000 SNone 68.9 122.8 1.0000 SNone 69.6 121.9 1.0000 SNone 70.3 121.2 1.0000 SNone 71.1 120.4 1.0000 SNone 71.8 119.8 1.0000 SNone 72.5 119.2 1.0000 SNone 73.2 118.6 1.0000 SNone 73.9 118.1 1.0000 SNone 88.2 111.9 1.0000 SNone 102.5 109.3 1.0000 SNone 116.8 107.8 1.0000 SNone 131.1 106.9 1.0000 SNone 145.4 106.2 1.0000 SNone 159.7 105.8 1.0000 SNone 174.0 105.4 1.0000 SNone 188.3 105.1 1.0000 SNone 202.6 104.9 1.0000 SNone 216.9 104.7 1.0000 SNone 231.2 104.5 1.0000 SNone 245.5 104.4 1.0000 SNone 259.8 104.3 1.0000 SNone 274.1 104.2 1.0000 SNone 1.000000 setlinewidth [5 4] 0 setdash 54.8 209.6 MT 55.3 185.3 LT 56.0 162.3 LT 56.8 147.1 LT 57.5 136.1 LT 58.2 127.9 LT 58.9 121.5 LT 59.6 116.4 LT 60.3 112.2 LT 61.0 108.7 LT 61.8 105.8 LT 62.5 103.2 LT 63.2 101.0 LT 63.9 99.1 LT 64.6 97.4 LT 65.3 95.9 LT 66.0 94.6 LT 66.8 93.4 LT 67.5 92.3 LT 68.2 91.3 LT 68.9 90.4 LT 69.6 89.5 LT 70.3 88.7 LT 71.1 88.0 LT 71.8 87.4 LT 72.5 86.8 LT 73.2 86.2 LT 73.9 85.7 LT 88.2 79.5 LT 102.5 76.9 LT 116.8 75.4 LT 131.1 74.5 LT 145.4 73.8 LT 159.7 73.4 LT 174.0 73.0 LT 188.3 72.7 LT 202.6 72.5 LT 216.9 72.3 LT 231.2 72.1 LT 245.5 72.0 LT 259.8 71.9 LT 274.1 71.8 LT stroke 1.000000 setlinewidth [] 0 setdash 55.3 185.3 1.0000 SNone 56.0 162.3 1.0000 SNone 56.8 147.1 1.0000 SNone 57.5 136.1 1.0000 SNone 58.2 127.9 1.0000 SNone 58.9 121.5 1.0000 SNone 59.6 116.4 1.0000 SNone 60.3 112.2 1.0000 SNone 61.0 108.7 1.0000 SNone 61.8 105.8 1.0000 SNone 62.5 103.2 1.0000 SNone 63.2 101.0 1.0000 SNone 63.9 99.1 1.0000 SNone 64.6 97.4 1.0000 SNone 65.3 95.9 1.0000 SNone 66.0 94.6 1.0000 SNone 66.8 93.4 1.0000 SNone 67.5 92.3 1.0000 SNone 68.2 91.3 1.0000 SNone 68.9 90.4 1.0000 SNone 69.6 89.5 1.0000 SNone 70.3 88.7 1.0000 SNone 71.1 88.0 1.0000 SNone 71.8 87.4 1.0000 SNone 72.5 86.8 1.0000 SNone 73.2 86.2 1.0000 SNone 73.9 85.7 1.0000 SNone 88.2 79.5 1.0000 SNone 102.5 76.9 1.0000 SNone 116.8 75.4 1.0000 SNone 131.1 74.5 1.0000 SNone 145.4 73.8 1.0000 SNone 159.7 73.4 1.0000 SNone 174.0 73.0 1.0000 SNone 188.3 72.7 1.0000 SNone 202.6 72.5 1.0000 SNone 216.9 72.3 1.0000 SNone 231.2 72.1 1.0000 SNone 245.5 72.0 1.0000 SNone 259.8 71.9 1.0000 SNone 274.1 71.8 1.0000 SNone 1.000000 setlinewidth [2 3 10 3] 0 setdash 55.7 209.6 MT 56.0 202.8 LT 56.8 187.5 LT 57.5 176.5 LT 58.2 168.3 LT 58.9 161.9 LT 59.6 156.8 LT 60.3 152.6 LT 61.0 149.1 LT 61.8 146.2 LT 62.5 143.7 LT 63.2 141.5 LT 63.9 139.6 LT 64.6 137.9 LT 65.3 136.3 LT 66.0 135.0 LT 66.8 133.8 LT 67.5 132.7 LT 68.2 131.7 LT 68.9 130.8 LT 69.6 129.9 LT 70.3 129.2 LT 71.1 128.5 LT 71.8 127.8 LT 72.5 127.2 LT 73.2 126.6 LT 73.9 126.1 LT 88.2 119.9 LT 102.5 117.3 LT 116.8 115.8 LT 131.1 114.9 LT 145.4 114.3 LT 159.7 113.8 LT 174.0 113.4 LT 188.3 113.1 LT 202.6 112.9 LT 216.9 112.7 LT 231.2 112.5 LT 245.5 112.4 LT 259.8 112.3 LT 274.1 112.2 LT stroke 1.000000 setlinewidth [] 0 setdash 56.0 202.8 1.0000 SNone 56.8 187.5 1.0000 SNone 57.5 176.5 1.0000 SNone 58.2 168.3 1.0000 SNone 58.9 161.9 1.0000 SNone 59.6 156.8 1.0000 SNone 60.3 152.6 1.0000 SNone 61.0 149.1 1.0000 SNone 61.8 146.2 1.0000 SNone 62.5 143.7 1.0000 SNone 63.2 141.5 1.0000 SNone 63.9 139.6 1.0000 SNone 64.6 137.9 1.0000 SNone 65.3 136.3 1.0000 SNone 66.0 135.0 1.0000 SNone 66.8 133.8 1.0000 SNone 67.5 132.7 1.0000 SNone 68.2 131.7 1.0000 SNone 68.9 130.8 1.0000 SNone 69.6 129.9 1.0000 SNone 70.3 129.2 1.0000 SNone 71.1 128.5 1.0000 SNone 71.8 127.8 1.0000 SNone 72.5 127.2 1.0000 SNone 73.2 126.6 1.0000 SNone 73.9 126.1 1.0000 SNone 88.2 119.9 1.0000 SNone 102.5 117.3 1.0000 SNone 116.8 115.8 1.0000 SNone 131.1 114.9 1.0000 SNone 145.4 114.3 1.0000 SNone 159.7 113.8 1.0000 SNone 174.0 113.4 1.0000 SNone 188.3 113.1 1.0000 SNone 202.6 112.9 1.0000 SNone 216.9 112.7 1.0000 SNone 231.2 112.5 1.0000 SNone 245.5 112.4 1.0000 SNone 259.8 112.3 1.0000 SNone 274.1 112.2 1.0000 SNone 52.5 27.6 MT 281.3 27.6 LT stroke 81.1 27.6 MT 81.1 31.2 LT stroke 109.7 27.6 MT 109.7 31.2 LT stroke 138.3 27.6 MT 138.3 31.2 LT stroke 166.9 27.6 MT 166.9 31.2 LT stroke 195.5 27.6 MT 195.5 31.2 LT stroke 224.1 27.6 MT 224.1 31.2 LT stroke 252.7 27.6 MT 252.7 31.2 LT stroke 281.3 27.6 MT 281.3 31.2 LT stroke /Helvetica findfont 12 scalefont setfont (Number of files in thousands \(Nf\)) 106.2 0.0 0 DoLText (2) 77.8 12.0 0 DoLText (4) 106.4 12.0 0 DoLText (6) 135.0 12.0 0 DoLText (8) 163.6 12.0 0 DoLText (10) 188.9 12.0 0 DoLText (12) 217.5 12.0 0 DoLText (14) 246.1 12.0 0 DoLText (16) 274.7 12.0 0 DoLText 52.5 27.6 MT 52.5 209.6 LT stroke 52.5 45.8 MT 56.1 45.8 LT stroke 52.5 64.0 MT 56.1 64.0 LT stroke 52.5 82.2 MT 56.1 82.2 LT stroke 52.5 100.4 MT 56.1 100.4 LT stroke 52.5 118.6 MT 56.1 118.6 LT stroke 52.5 136.8 MT 56.1 136.8 LT stroke 52.5 155.0 MT 56.1 155.0 LT stroke 52.5 173.2 MT 56.1 173.2 LT stroke 52.5 191.4 MT 56.1 191.4 LT stroke 52.5 209.6 MT 56.1 209.6 LT stroke (FFS - DOSFS Overhead \(in bytes\)) 12.0 26.5 90 DoLText (1000) 22.3 39.8 0 DoLText (2000) 22.3 58.0 0 DoLText (3000) 22.3 76.2 0 DoLText (4000) 22.3 94.4 0 DoLText (5000) 22.3 112.6 0 DoLText (6000) 22.3 130.8 0 DoLText (7000) 22.3 149.0 0 DoLText (8000) 22.3 167.2 0 DoLText (9000) 22.3 185.4 0 DoLText (10000) 15.6 203.6 0 DoLText (0) 42.3 12.0 0 DoLText /Helvetica findfont 10 scalefont setfont [] 0 setdash 1.000000 setlinewidth 151.8 190.4 MT 178.8 190.4 LT stroke 151.8 190.4 0.6500 SNone 178.8 190.4 0.6500 SNone (F = 1, Nd = 1) 192.3 187.4 0 DoLText [2 3] 0 setdash 1.000000 setlinewidth 151.8 177.4 MT 178.8 177.4 LT stroke 151.8 177.4 0.6500 SNone 178.8 177.4 0.6500 SNone (F = 50k, Nd = 1) 192.3 174.4 0 DoLText [7 5 19 5] 0 setdash 1.000000 setlinewidth 151.8 164.4 MT 178.8 164.4 LT stroke 151.8 164.4 0.6500 SNone 178.8 164.4 0.6500 SNone (F = 100k, Nd = 1) 192.3 161.4 0 DoLText [5 4] 0 setdash 1.000000 setlinewidth 151.8 151.4 MT 178.8 151.4 LT stroke 151.8 151.4 0.6500 SNone 178.8 151.4 0.6500 SNone (F = 500k, Nd = 1) 192.3 148.4 0 DoLText [2 3 10 3] 0 setdash 1.000000 setlinewidth 151.8 138.4 MT 178.8 138.4 LT stroke 151.8 138.4 0.6500 SNone 178.8 138.4 0.6500 SNone (F = 1M, Nd = 1) 192.3 135.4 0 DoLText [] 0 setdash 1.000000 setlinewidth 138.3 128.3 MT 138.3 200.5 LT 270.2 200.5 LT 270.2 128.3 LT 138.3 128.3 LT stroke showpage restore %%Trailer restore %%DocumentFonts: Helvetica %%EndDocument GE /Times-Bold SF 22749 26801 MT (Figure 2:)SH /Times-Roman SF 27165 XM (Metadata Costs: FFS Over DosFs)SH 9280 30385 MT (For FFS, we arrive at the following expressions)SH /Courier-Bold SF 13080 32190 MT (FFSCost = D + 128 + Ceil\050 F/\0508 * A\051, 1 \051 + C / Nf + Ceil\050 F, A \051)SH 13080 34452 MT (D = Ceil\050Sum\050Max\050 12, 8 + namelen\050i\051\051\051, A\051 / Nd)SH /Times-Roman SF 9280 36931 MT (Where)SH /Times-Bold SF 12445 XM (Nf)SH /Times-Roman SF 14000 XM (is the total number of files on disk, and)250 W /Times-Bold SF 32138 XM (C)SH /Times-Roman SF 33360 XM (is the fixed cost in cylinder groups and) 250 W( replicated)251 W 8280 38308 MT (superblocks. For) 328 W( a floppy this cost is at minimum 104) 39 W( KB in three cylinder groups, for a 60 MB disk partition it is)38 W 8280 39685 MT (1.4 MB. The five terms of the sum are the amortized directory entry cost)78 W /Times-Bold SF 39028 XM (D)SH /Times-Roman SF (, the inode, the allocation) 78 W( bitmap, the)79 W 8280 41062 MT (amortized fixed cost, and the file itself. For FFS all but the directory entry and) 143 W( file data costs are paid at disk)142 W 8280 42439 MT (creation time. The formula above is only valid for \050relatively\051 small) 34 W( files, for large files we must also add the costs)35 W 8280 43816 MT (in double and triple indirect blocks.)SH 9280 46295 MT (Figure 2 shows what happens as we add more files to) 65 W( the file system. The curves assume a given file length)64 W /Times-Bold SF 54219 XM (F)SH /Times-Roman SF (,)SH 8280 47672 MT (and a fixed number of files per directory. Note that up to a file length of 64) 23 W( KB FFS does not use indirect blocks to)24 W 8280 49049 MT (indicate the blocks that belong to files, it uses the direct block list in the inode which is a pre-paid cost.) 29 W( This) 307 W( fact is)28 W 8280 50426 MT (illustrated in more detail in Figure 3, where we vary the size of the average file in a file system with 6,000) 29 W( files and)30 W 8280 51803 MT (an average of 20 files per directory. In both Figures the fragment size) 3 W( is 512 bytes and the logical block size is 4 KB,)2 W 8280 53180 MT (in a 60 MB partition. The ramps are the points at which FFS must allocate) 31 W( a new block for the \050indirect\051 block list.)32 W 8280 54557 MT (Once that cost is paid) 8 W( DosFs has a lesser advantage, but the DosFs costs still grow at half the speed of the FFS costs.)7 W 8280 55934 MT (This is because FAT entries are 16 bits while FFS disk block numbers are 32 bits.)SH 75 100 0 5280 70839 GB %%BeginDocument: util3.ps %!PS-Adobe-2.0 %%DocumentFonts: (atend) %%Creator: PLOT X1.1c %%%Pages: 1 %%BoundingBox: 40 40 328 184 %%EndComments /MT {moveto} bind def /LT {lineto} bind def /sethsbcolor {setgray pop pop} bind def /x2sqrt3 2 sqrt 3 mul def % % () x y o DoLText % % Left justified text. /DoLText { gsave 3 1 roll translate rotate newpath 0 0 moveto show grestore } def % % () x y o DoRText % % Right justified text. /DoRText { gsave 3 1 roll translate rotate dup stringwidth pop neg 0 translate newpath 0 0 moveto show grestore } def % % () x y o DoCText % % Center justified text. /DoCText { gsave 3 1 roll translate rotate dup stringwidth pop 2 div neg 0 translate newpath 0 0 moveto show grestore } def % % Symbol Definitions % % /SymbolStart { gsave [] 0 setdash 3 1 roll translate dup dup scale 1 exch div setlinewidth newpath } def /SBox { SymbolStart -3 -3 moveto 3 -3 lineto 3 3 lineto -3 3 lineto closepath stroke grestore } def /SBullet { SymbolStart 0 0 3 0 360 arc fill grestore } def /SCircle { SymbolStart 0 0 3 0 360 arc stroke grestore } def /SCross { SymbolStart -3 -3 moveto 3 3 lineto stroke -3 3 moveto 3 -3 lineto stroke grestore } def /SCustom { pop pop pop } def /SDel { SymbolStart x2sqrt3 2 moveto x2sqrt3 neg 2 lineto 0 -4 lineto closepath stroke grestore } def /SPlus { SymbolStart -3 0 moveto 3 0 lineto stroke 0 -3 moveto 0 3 lineto stroke grestore } def /SDiamond { SymbolStart 45 rotate -3 -3 moveto 3 -3 lineto 3 3 lineto -3 3 lineto closepath stroke grestore } def /SEllipse { SymbolStart 2 1 scale 0 0 3 0 360 arc closepath stroke grestore } def /SNone { pop pop pop } def /SNumber { SymbolStart grestore } def /SSolidBox { SymbolStart -3 -3 moveto 3 -3 lineto 3 3 lineto -3 3 lineto closepath fill grestore } def /StarSide 6 36 cos div dup 36 sin mul sub 36 sin mul 36 cos div def /SStar { SymbolStart 0 3 translate -108 rotate 0 0 moveto 5 { StarSide 0 translate 0 0 lineto -72 rotate StarSide 0 translate 0 0 lineto 144 rotate } repeat closepath stroke grestore } def /STriangle { SymbolStart x2sqrt3 -2 moveto x2sqrt3 neg -2 lineto 0 4 lineto closepath stroke grestore } def % % ci w h o x y bar % /bar { gsave translate rotate % exch 2 div exch % ci w/2 h % newpath 2 copy pop 0 moveto 2 copy lineto 2 copy exch neg exch lineto 2 copy pop neg 0 lineto closepath stroke % ci w/2 h % 3 -1 roll dup 0 ne { % w/2 h ci 3 copy pop moveto % w/2 h ci 3 copy add lineto 3 copy add exch neg exch lineto 3 copy pop exch neg exch lineto stroke 3 copy pop moveto % w/2 h ci 3 copy sub lineto 3 copy sub exch neg exch lineto 3 copy pop exch neg exch lineto stroke currentlinewidth 2 mul setlinewidth pop 2 copy moveto exch neg exch lineto stroke } {pop pop pop } ifelse % grestore } def % % a linesfill % /linesfill { gsave clip initmatrix MFactor MFactor scale 0.5 setlinewidth rotate 1 dict begin /ksp 1000 MFactor div def ksp neg 5 ksp { % v newpath dup ksp exch moveto ksp neg exch lineto stroke } for end grestore newpath } def % % a lines2fill % /lines2fill { gsave clip initmatrix MFactor MFactor scale 0.5 setlinewidth rotate 1 dict begin /ksp 1000 MFactor div def ksp neg 8 ksp { % v newpath dup ksp exch moveto dup ksp neg exch lineto stroke 2 add dup ksp exch moveto ksp neg exch lineto stroke } for end grestore newpath } def % % a lineswfill % /lineswfill { gsave clip initmatrix MFactor MFactor scale 0.5 setlinewidth rotate 1 dict begin /ksp 1000 MFactor div def ksp neg 10 ksp { % v newpath dup ksp exch moveto ksp neg exch lineto stroke } for end grestore newpath } def /crosshatch { dup gsave linesfill grestore 90 add linesfill } def % % ci w h o x y {pg2} {pg1} linefillbar % /fillbar { 2 dict begin /pg1 exch def /pg2 exch def 6 copy % save bar parameters gsave translate rotate % exch 2 div exch % ci w/2 h 3 -1 roll % w/2 h ci % newpath % 3 copy pop pop neg 0 moveto 3 copy sub exch neg exch lineto 3 copy sub lineto 3 copy pop pop 0 lineto closepath pg1 % 3 copy sub exch neg exch moveto 3 copy add exch neg exch lineto 3 copy add lineto 3 copy sub lineto closepath pg2 % grestore pop pop pop bar end } def save %%EndProlog %%%Page: 1 1 save 40 40 translate 0.0 0.0 translate 1.000000 1.000000 scale /MFactor 1.000000 def 1.000000 setlinewidth [] 0 setdash newpath 52.6 30.4 MT 55.2 67.2 LT 58.0 66.4 LT 60.8 65.5 LT 63.6 64.7 LT 66.3 63.8 LT 69.1 62.9 LT 71.9 62.1 LT 74.7 61.2 LT 77.4 60.3 LT 80.2 59.5 LT 83.0 58.6 LT 85.8 57.8 LT 88.5 56.9 LT 91.3 56.0 LT 94.1 55.2 LT 96.9 54.3 LT 99.6 53.4 LT 102.4 52.6 LT 105.2 51.7 LT 108.0 50.9 LT 110.7 87.7 LT 113.5 86.8 LT 116.3 85.9 LT 119.1 85.1 LT 121.8 84.2 LT 124.6 83.4 LT 127.4 82.5 LT 130.2 81.6 LT 132.9 80.8 LT 135.7 79.9 LT 138.5 79.0 LT 141.3 78.2 LT 144.0 77.3 LT 146.8 76.5 LT 149.6 75.6 LT 152.4 74.7 LT 155.1 73.9 LT 157.9 73.0 LT 160.7 72.1 LT 163.5 71.3 LT 166.2 108.1 LT 169.0 107.2 LT 171.8 106.4 LT 174.6 105.5 LT 177.3 104.7 LT 180.1 103.8 LT 182.9 102.9 LT 185.7 102.1 LT 188.4 101.2 LT 191.2 100.3 LT 194.0 99.5 LT stroke 194.0 99.5 MT 196.8 98.6 LT 199.5 97.8 LT 202.3 96.9 LT 205.1 96.0 LT 207.9 95.2 LT 210.6 94.3 LT 213.4 93.4 LT 216.2 92.6 LT 219.0 91.7 LT 221.7 128.5 LT 224.5 127.7 LT 227.3 126.8 LT 230.1 126.0 LT 232.8 125.1 LT 235.6 124.2 LT 238.4 123.4 LT 241.2 122.5 LT 243.9 121.6 LT 246.7 120.8 LT 249.5 119.9 LT 252.3 119.1 LT 255.0 118.2 LT 257.8 117.3 LT 260.6 116.5 LT 263.4 115.6 LT 266.1 114.7 LT 268.9 113.9 LT 271.7 113.0 LT 274.5 112.2 LT stroke 1.000000 setlinewidth [] 0 setdash 52.6 30.4 1.0000 SNone 55.2 67.2 1.0000 SNone 58.0 66.4 1.0000 SNone 60.8 65.5 1.0000 SNone 63.6 64.7 1.0000 SNone 66.3 63.8 1.0000 SNone 69.1 62.9 1.0000 SNone 71.9 62.1 1.0000 SNone 74.7 61.2 1.0000 SNone 77.4 60.3 1.0000 SNone 80.2 59.5 1.0000 SNone 83.0 58.6 1.0000 SNone 85.8 57.8 1.0000 SNone 88.5 56.9 1.0000 SNone 91.3 56.0 1.0000 SNone 94.1 55.2 1.0000 SNone 96.9 54.3 1.0000 SNone 99.6 53.4 1.0000 SNone 102.4 52.6 1.0000 SNone 105.2 51.7 1.0000 SNone 108.0 50.9 1.0000 SNone 110.7 87.7 1.0000 SNone 113.5 86.8 1.0000 SNone 116.3 85.9 1.0000 SNone 119.1 85.1 1.0000 SNone 121.8 84.2 1.0000 SNone 124.6 83.4 1.0000 SNone 127.4 82.5 1.0000 SNone 130.2 81.6 1.0000 SNone 132.9 80.8 1.0000 SNone 135.7 79.9 1.0000 SNone 138.5 79.0 1.0000 SNone 141.3 78.2 1.0000 SNone 144.0 77.3 1.0000 SNone 146.8 76.5 1.0000 SNone 149.6 75.6 1.0000 SNone 152.4 74.7 1.0000 SNone 155.1 73.9 1.0000 SNone 157.9 73.0 1.0000 SNone 160.7 72.1 1.0000 SNone 163.5 71.3 1.0000 SNone 166.2 108.1 1.0000 SNone 169.0 107.2 1.0000 SNone 171.8 106.4 1.0000 SNone 174.6 105.5 1.0000 SNone 177.3 104.7 1.0000 SNone 180.1 103.8 1.0000 SNone 182.9 102.9 1.0000 SNone 185.7 102.1 1.0000 SNone 188.4 101.2 1.0000 SNone 191.2 100.3 1.0000 SNone 194.0 99.5 1.0000 SNone 196.8 98.6 1.0000 SNone 199.5 97.8 1.0000 SNone 202.3 96.9 1.0000 SNone 205.1 96.0 1.0000 SNone 207.9 95.2 1.0000 SNone 210.6 94.3 1.0000 SNone 213.4 93.4 1.0000 SNone 216.2 92.6 1.0000 SNone 219.0 91.7 1.0000 SNone 221.7 128.5 1.0000 SNone 224.5 127.7 1.0000 SNone 227.3 126.8 1.0000 SNone 230.1 126.0 1.0000 SNone 232.8 125.1 1.0000 SNone 235.6 124.2 1.0000 SNone 238.4 123.4 1.0000 SNone 241.2 122.5 1.0000 SNone 243.9 121.6 1.0000 SNone 246.7 120.8 1.0000 SNone 249.5 119.9 1.0000 SNone 252.3 119.1 1.0000 SNone 255.0 118.2 1.0000 SNone 257.8 117.3 1.0000 SNone 260.6 116.5 1.0000 SNone 263.4 115.6 1.0000 SNone 266.1 114.7 1.0000 SNone 268.9 113.9 1.0000 SNone 271.7 113.0 1.0000 SNone 274.5 112.2 1.0000 SNone 52.5 27.6 MT 274.5 27.6 LT stroke 108.0 27.6 MT 108.0 31.2 LT stroke 163.5 27.6 MT 163.5 31.2 LT stroke 219.0 27.6 MT 219.0 31.2 LT stroke 274.5 27.6 MT 274.5 31.2 LT stroke /Helvetica findfont 12 scalefont setfont (File size in KB \(F\)) 180.0 0.0 0 DoLText (500) 98.1 12.0 0 DoLText (1000) 150.2 12.0 0 DoLText (1500) 205.7 12.0 0 DoLText (2000) 261.2 12.0 0 DoLText 52.5 27.6 MT 52.5 138.0 LT stroke 52.5 55.2 MT 56.1 55.2 LT stroke 52.5 82.8 MT 56.1 82.8 LT stroke 52.5 110.4 MT 56.1 110.4 LT stroke 52.5 138.0 MT 56.1 138.0 LT stroke (FFS - DOSFS Overhead) 12.0 7.5 90 DoLText (3000) 22.3 49.2 0 DoLText (6000) 22.3 76.8 0 DoLText (9000) 22.3 104.4 0 DoLText (12000) 15.6 132.0 0 DoLText (0) 42.3 12.0 0 DoLText /Helvetica findfont 10 scalefont setfont [] 0 setdash 1.000000 setlinewidth 222066.0 477.5 MT 222093.0 477.5 LT stroke 222066.0 477.5 0.6500 SNone 222093.0 477.5 0.6500 SNone [] 0 setdash 1.000000 setlinewidth 222052.5 467.4 MT 222052.5 487.6 LT 222196.6 487.6 LT 222196.6 467.4 LT 222052.5 467.4 LT stroke showpage restore %%Trailer restore %%DocumentFonts: Helvetica %%EndDocument GE /Times-Bold SF 16584 69449 MT (Figure 3:)SH /Times-Roman SF 21000 XM (File System Overhead In Bytes, As A Function Of The File Size)SH ES %%Page: 14 15 BS 0 SI 10 /Times-Roman AF 6120 4286 MT (14)SH 7120 7886 MT (If we look at directory entries alone, FFS would score better than it does overall. DosFs uses a fixed 32 bytes per)19 W 6120 9263 MT (entry, including information that FFS stores in the inode table. FFS instead uses a minimum of 8) 29 W( bytes plus the file)28 W 6120 10640 MT (name, and will typically be able to fit more directory entries) 21 W( per block. In Figure 4 we plot the directory entry costs)22 W /Times-Bold SF 6120 12017 MT (D)SH /Times-Roman SF 7214 XM (for the two file systems, and their difference. By growing the number of files per) 122 W( directory the initial cost is)121 W 6120 13394 MT (amortized and the remaining cost is dominated by the file name length \050we have assumed file names of length 12\051.)SH 75 100 0 3120 39099 GB %%BeginDocument: util1.ps %!PS-Adobe-2.0 %%DocumentFonts: (atend) %%Creator: PLOT X1.1c %%%Pages: 1 %%BoundingBox: 40 40 400 328 %%EndComments /MT {moveto} bind def /LT {lineto} bind def /sethsbcolor {setgray pop pop} bind def /x2sqrt3 2 sqrt 3 mul def % % () x y o DoLText % % Left justified text. /DoLText { gsave 3 1 roll translate rotate newpath 0 0 moveto show grestore } def % % () x y o DoRText % % Right justified text. /DoRText { gsave 3 1 roll translate rotate dup stringwidth pop neg 0 translate newpath 0 0 moveto show grestore } def % % () x y o DoCText % % Center justified text. /DoCText { gsave 3 1 roll translate rotate dup stringwidth pop 2 div neg 0 translate newpath 0 0 moveto show grestore } def % % Symbol Definitions % % /SymbolStart { gsave [] 0 setdash 3 1 roll translate dup dup scale 1 exch div setlinewidth newpath } def /SBox { SymbolStart -3 -3 moveto 3 -3 lineto 3 3 lineto -3 3 lineto closepath stroke grestore } def /SBullet { SymbolStart 0 0 3 0 360 arc fill grestore } def /SCircle { SymbolStart 0 0 3 0 360 arc stroke grestore } def /SCross { SymbolStart -3 -3 moveto 3 3 lineto stroke -3 3 moveto 3 -3 lineto stroke grestore } def /SCustom { pop pop pop } def /SDel { SymbolStart x2sqrt3 2 moveto x2sqrt3 neg 2 lineto 0 -4 lineto closepath stroke grestore } def /SPlus { SymbolStart -3 0 moveto 3 0 lineto stroke 0 -3 moveto 0 3 lineto stroke grestore } def /SDiamond { SymbolStart 45 rotate -3 -3 moveto 3 -3 lineto 3 3 lineto -3 3 lineto closepath stroke grestore } def /SEllipse { SymbolStart 2 1 scale 0 0 3 0 360 arc closepath stroke grestore } def /SNone { pop pop pop } def /SNumber { SymbolStart grestore } def /SSolidBox { SymbolStart -3 -3 moveto 3 -3 lineto 3 3 lineto -3 3 lineto closepath fill grestore } def /StarSide 6 36 cos div dup 36 sin mul sub 36 sin mul 36 cos div def /SStar { SymbolStart 0 3 translate -108 rotate 0 0 moveto 5 { StarSide 0 translate 0 0 lineto -72 rotate StarSide 0 translate 0 0 lineto 144 rotate } repeat closepath stroke grestore } def /STriangle { SymbolStart x2sqrt3 -2 moveto x2sqrt3 neg -2 lineto 0 4 lineto closepath stroke grestore } def % % ci w h o x y bar % /bar { gsave translate rotate % exch 2 div exch % ci w/2 h % newpath 2 copy pop 0 moveto 2 copy lineto 2 copy exch neg exch lineto 2 copy pop neg 0 lineto closepath stroke % ci w/2 h % 3 -1 roll dup 0 ne { % w/2 h ci 3 copy pop moveto % w/2 h ci 3 copy add lineto 3 copy add exch neg exch lineto 3 copy pop exch neg exch lineto stroke 3 copy pop moveto % w/2 h ci 3 copy sub lineto 3 copy sub exch neg exch lineto 3 copy pop exch neg exch lineto stroke currentlinewidth 2 mul setlinewidth pop 2 copy moveto exch neg exch lineto stroke } {pop pop pop } ifelse % grestore } def % % a linesfill % /linesfill { gsave clip initmatrix MFactor MFactor scale 0.5 setlinewidth rotate 1 dict begin /ksp 1000 MFactor div def ksp neg 5 ksp { % v newpath dup ksp exch moveto ksp neg exch lineto stroke } for end grestore newpath } def % % a lines2fill % /lines2fill { gsave clip initmatrix MFactor MFactor scale 0.5 setlinewidth rotate 1 dict begin /ksp 1000 MFactor div def ksp neg 8 ksp { % v newpath dup ksp exch moveto dup ksp neg exch lineto stroke 2 add dup ksp exch moveto ksp neg exch lineto stroke } for end grestore newpath } def % % a lineswfill % /lineswfill { gsave clip initmatrix MFactor MFactor scale 0.5 setlinewidth rotate 1 dict begin /ksp 1000 MFactor div def ksp neg 10 ksp { % v newpath dup ksp exch moveto ksp neg exch lineto stroke } for end grestore newpath } def /crosshatch { dup gsave linesfill grestore 90 add linesfill } def % % ci w h o x y {pg2} {pg1} linefillbar % /fillbar { 2 dict begin /pg1 exch def /pg2 exch def 6 copy % save bar parameters gsave translate rotate % exch 2 div exch % ci w/2 h 3 -1 roll % w/2 h ci % newpath % 3 copy pop pop neg 0 moveto 3 copy sub exch neg exch lineto 3 copy sub lineto 3 copy pop pop 0 lineto closepath pg1 % 3 copy sub exch neg exch moveto 3 copy add exch neg exch lineto 3 copy add lineto 3 copy sub lineto closepath pg2 % grestore pop pop pop bar end } def save %%EndProlog %%%Page: 1 1 save 40 40 translate 0.0 0.0 translate 1.000000 1.000000 scale /MFactor 1.000000 def 1.000000 setlinewidth [] 0 setdash newpath 42.9 281.6 MT 43.7 243.5 LT 44.5 213.0 LT 45.3 190.1 LT 46.0 169.8 LT 46.8 157.1 LT 47.6 144.4 LT 48.4 134.2 LT 49.1 126.6 LT 49.9 119.0 LT 50.7 113.9 LT 51.5 190.1 LT 52.2 180.0 LT 53.0 169.8 LT 53.8 162.2 LT 54.6 157.1 LT 55.3 149.5 LT 56.1 144.4 LT 56.9 139.3 LT 57.7 134.2 LT 58.5 129.2 LT 59.2 126.6 LT 60.0 121.5 LT 60.8 119.0 LT 61.6 116.5 LT 62.3 113.9 LT 63.1 111.4 LT 63.9 149.5 LT 64.7 144.4 LT 65.4 141.9 LT 66.2 136.8 LT 67.0 134.2 LT 67.8 131.7 LT 68.5 129.2 LT 69.3 126.6 LT 70.1 124.1 LT 70.9 121.5 LT 71.6 119.0 LT 72.4 116.5 LT 73.2 113.9 LT 74.0 113.9 LT 74.7 111.4 LT 75.5 108.8 LT 76.3 134.2 LT 77.1 131.7 LT 77.9 129.2 LT 78.6 129.2 LT 79.4 126.6 LT 80.2 124.1 LT 81.0 121.5 LT 81.7 121.5 LT 82.5 119.0 LT stroke 82.5 119.0 MT 83.3 116.5 LT 84.1 116.5 LT 84.8 113.9 LT 85.6 113.9 LT 86.4 111.4 LT 87.2 111.4 LT 87.9 108.8 LT 88.7 129.2 LT 89.5 126.6 LT 90.3 124.1 LT 91.0 124.1 LT 91.8 121.5 LT 92.6 121.5 LT 93.4 119.0 LT 94.1 119.0 LT 94.9 116.5 LT 95.7 116.5 LT 96.5 113.9 LT 97.3 113.9 LT 98.0 111.4 LT 98.8 111.4 LT 99.6 108.8 LT 100.4 108.8 LT 101.1 124.1 LT 101.9 121.5 LT 102.7 121.5 LT 103.5 121.5 LT 104.2 119.0 LT 105.0 119.0 LT 105.8 116.5 LT 106.6 116.5 LT 107.3 113.9 LT 108.1 113.9 LT 108.9 113.9 LT 109.7 111.4 LT 110.4 111.4 LT 111.2 111.4 LT 112.0 108.8 LT 112.8 108.8 LT 113.5 121.5 LT 114.3 119.0 LT 115.1 119.0 LT 115.9 119.0 LT 116.7 116.5 LT 117.4 116.5 LT 118.2 116.5 LT 119.0 113.9 LT 119.8 113.9 LT 120.5 113.9 LT 121.3 111.4 LT 122.1 111.4 LT stroke 122.1 111.4 MT 122.9 111.4 LT 123.6 108.8 LT 124.4 108.8 LT 125.2 108.8 LT 126.0 119.0 LT 126.7 119.0 LT 127.5 116.5 LT 128.3 116.5 LT 129.1 116.5 LT 129.8 116.5 LT 130.6 113.9 LT 131.4 113.9 LT 132.2 113.9 LT 132.9 111.4 LT 133.7 111.4 LT 134.5 111.4 LT 135.3 111.4 LT 136.1 108.8 LT 136.8 108.8 LT 137.6 108.8 LT 138.4 119.0 LT 139.2 116.5 LT 139.9 116.5 LT 140.7 116.5 LT 141.5 113.9 LT 142.3 113.9 LT 143.0 113.9 LT 143.8 113.9 LT 144.6 111.4 LT 145.4 111.4 LT 146.1 111.4 LT 146.9 111.4 LT 147.7 108.8 LT 148.5 108.8 LT 149.2 108.8 LT 150.0 108.8 LT 150.8 116.5 LT 151.6 116.5 LT 152.3 116.5 LT 153.1 113.9 LT 153.9 113.9 LT 154.7 113.9 LT 155.5 113.9 LT 156.2 111.4 LT 157.0 111.4 LT 157.8 111.4 LT 158.6 111.4 LT 159.3 111.4 LT 160.1 108.8 LT 160.9 108.8 LT 161.7 108.8 LT stroke 161.7 108.8 MT 162.4 108.8 LT 163.2 116.5 LT 164.0 113.9 LT 164.8 113.9 LT 165.5 113.9 LT 166.3 113.9 LT 167.1 113.9 LT 167.9 111.4 LT 168.6 111.4 LT 169.4 111.4 LT 170.2 111.4 LT 171.0 111.4 LT 171.7 108.8 LT 172.5 108.8 LT 173.3 108.8 LT 174.1 108.8 LT 174.9 108.8 LT 175.6 113.9 LT 176.4 113.9 LT 177.2 113.9 LT 178.0 113.9 LT 178.7 113.9 LT 179.5 111.4 LT 180.3 111.4 LT 181.1 111.4 LT 181.8 111.4 LT 182.6 111.4 LT 183.4 111.4 LT 184.2 108.8 LT 184.9 108.8 LT 185.7 108.8 LT 186.5 108.8 LT 187.3 108.8 LT 188.0 113.9 LT 188.8 113.9 LT 189.6 113.9 LT 190.4 113.9 LT 191.1 111.4 LT 191.9 111.4 LT 192.7 111.4 LT 193.5 111.4 LT 194.3 111.4 LT 195.0 111.4 LT 195.8 108.8 LT 196.6 108.8 LT 197.4 108.8 LT 198.1 108.8 LT 198.9 108.8 LT 199.7 108.8 LT 200.5 113.9 LT 201.2 113.9 LT stroke 201.2 113.9 MT 202.0 113.9 LT 202.8 111.4 LT 203.6 111.4 LT 204.3 111.4 LT 205.1 111.4 LT 205.9 111.4 LT 206.7 111.4 LT 207.4 111.4 LT 208.2 108.8 LT 209.0 108.8 LT 209.8 108.8 LT 210.5 108.8 LT 211.3 108.8 LT 212.1 108.8 LT 212.9 113.9 LT 213.7 113.9 LT 214.4 111.4 LT 215.2 111.4 LT 216.0 111.4 LT 216.8 111.4 LT 217.5 111.4 LT 218.3 111.4 LT 219.1 111.4 LT 219.9 108.8 LT 220.6 108.8 LT 221.4 108.8 LT 222.2 108.8 LT 223.0 108.8 LT 223.7 108.8 LT 224.5 108.8 LT 225.3 113.9 LT 226.1 111.4 LT 226.8 111.4 LT 227.6 111.4 LT 228.4 111.4 LT 229.2 111.4 LT 229.9 111.4 LT 230.7 111.4 LT 231.5 111.4 LT 232.3 108.8 LT 233.1 108.8 LT 233.8 108.8 LT 234.6 108.8 LT 235.4 108.8 LT 236.2 108.8 LT 236.9 108.8 LT 237.7 113.9 LT 238.5 111.4 LT 239.3 111.4 LT 240.0 111.4 LT 240.8 111.4 LT stroke 240.8 111.4 MT 241.6 111.4 LT 242.4 111.4 LT 243.1 111.4 LT 243.9 108.8 LT 244.7 108.8 LT 245.5 108.8 LT 246.2 108.8 LT 247.0 108.8 LT 247.8 108.8 LT 248.6 108.8 LT 249.3 108.8 LT 250.1 111.4 LT 250.9 111.4 LT 251.7 111.4 LT 252.5 111.4 LT 253.2 111.4 LT 254.0 111.4 LT 254.8 111.4 LT 255.6 111.4 LT 256.3 108.8 LT 257.1 108.8 LT 257.9 108.8 LT 258.7 108.8 LT 259.4 108.8 LT 260.2 108.8 LT 261.0 108.8 LT 261.8 108.8 LT 262.5 111.4 LT 263.3 111.4 LT 264.1 111.4 LT 264.9 111.4 LT 265.6 111.4 LT 266.4 111.4 LT 267.2 111.4 LT 268.0 108.8 LT 268.7 108.8 LT 269.5 108.8 LT 270.3 108.8 LT 271.1 108.8 LT 271.9 108.8 LT 272.6 108.8 LT 273.4 108.8 LT 274.2 108.8 LT 275.0 111.4 LT 275.7 111.4 LT 276.5 111.4 LT 277.3 111.4 LT 278.1 111.4 LT 278.8 111.4 LT 279.6 111.4 LT 280.4 108.8 LT stroke 280.4 108.8 MT 281.2 108.8 LT 281.9 108.8 LT 282.7 108.8 LT 283.5 108.8 LT 284.3 108.8 LT 285.0 108.8 LT 285.8 108.8 LT 286.6 108.8 LT 287.4 111.4 LT 288.1 111.4 LT 288.9 111.4 LT 289.7 111.4 LT 290.5 111.4 LT 291.3 111.4 LT 292.0 108.8 LT 292.8 108.8 LT 293.6 108.8 LT 294.4 108.8 LT 295.1 108.8 LT 295.9 108.8 LT 296.7 108.8 LT 297.5 108.8 LT 298.2 108.8 LT 299.0 108.8 LT 299.8 111.4 LT 300.6 111.4 LT 301.3 111.4 LT 302.1 111.4 LT 302.9 111.4 LT 303.7 111.4 LT 304.4 108.8 LT 305.2 108.8 LT 306.0 108.8 LT 306.8 108.8 LT 307.5 108.8 LT 308.3 108.8 LT 309.1 108.8 LT 309.9 108.8 LT 310.7 108.8 LT 311.4 108.8 LT 312.2 111.4 LT 313.0 111.4 LT 313.8 111.4 LT 314.5 111.4 LT 315.3 111.4 LT 316.1 108.8 LT 316.9 108.8 LT 317.6 108.8 LT 318.4 108.8 LT 319.2 108.8 LT 320.0 108.8 LT stroke 320.0 108.8 MT 320.7 108.8 LT 321.5 108.8 LT 322.3 108.8 LT 323.1 108.8 LT 323.8 108.8 LT 324.6 111.4 LT 325.4 111.4 LT 326.2 111.4 LT 326.9 111.4 LT 327.7 111.4 LT 328.5 108.8 LT 329.3 108.8 LT 330.1 108.8 LT 330.8 108.8 LT 331.6 108.8 LT 332.4 108.8 LT 333.2 108.8 LT 333.9 108.8 LT 334.7 108.8 LT 335.5 108.8 LT 336.3 108.8 LT 337.0 111.4 LT 337.8 111.4 LT 338.6 111.4 LT 339.4 111.4 LT 340.1 108.8 LT 340.9 108.8 LT 341.7 108.8 LT 342.5 108.8 LT 343.2 108.8 LT 344.0 108.8 LT 344.8 108.8 LT 345.6 108.8 LT 346.3 108.8 LT 347.1 108.8 LT 347.9 108.8 LT 348.7 108.8 LT 349.5 111.4 LT 350.2 111.4 LT stroke 1.000000 setlinewidth [] 0 setdash 43.7 243.5 1.0000 SNone 44.5 213.0 1.0000 SNone 45.3 190.1 1.0000 SNone 46.0 169.8 1.0000 SNone 46.8 157.1 1.0000 SNone 47.6 144.4 1.0000 SNone 48.4 134.2 1.0000 SNone 49.1 126.6 1.0000 SNone 49.9 119.0 1.0000 SNone 50.7 113.9 1.0000 SNone 51.5 190.1 1.0000 SNone 52.2 180.0 1.0000 SNone 53.0 169.8 1.0000 SNone 53.8 162.2 1.0000 SNone 54.6 157.1 1.0000 SNone 55.3 149.5 1.0000 SNone 56.1 144.4 1.0000 SNone 56.9 139.3 1.0000 SNone 57.7 134.2 1.0000 SNone 58.5 129.2 1.0000 SNone 59.2 126.6 1.0000 SNone 60.0 121.5 1.0000 SNone 60.8 119.0 1.0000 SNone 61.6 116.5 1.0000 SNone 62.3 113.9 1.0000 SNone 63.1 111.4 1.0000 SNone 63.9 149.5 1.0000 SNone 64.7 144.4 1.0000 SNone 65.4 141.9 1.0000 SNone 66.2 136.8 1.0000 SNone 67.0 134.2 1.0000 SNone 67.8 131.7 1.0000 SNone 68.5 129.2 1.0000 SNone 69.3 126.6 1.0000 SNone 70.1 124.1 1.0000 SNone 70.9 121.5 1.0000 SNone 71.6 119.0 1.0000 SNone 72.4 116.5 1.0000 SNone 73.2 113.9 1.0000 SNone 74.0 113.9 1.0000 SNone 74.7 111.4 1.0000 SNone 75.5 108.8 1.0000 SNone 76.3 134.2 1.0000 SNone 77.1 131.7 1.0000 SNone 77.9 129.2 1.0000 SNone 78.6 129.2 1.0000 SNone 79.4 126.6 1.0000 SNone 80.2 124.1 1.0000 SNone 81.0 121.5 1.0000 SNone 81.7 121.5 1.0000 SNone 82.5 119.0 1.0000 SNone 83.3 116.5 1.0000 SNone 84.1 116.5 1.0000 SNone 84.8 113.9 1.0000 SNone 85.6 113.9 1.0000 SNone 86.4 111.4 1.0000 SNone 87.2 111.4 1.0000 SNone 87.9 108.8 1.0000 SNone 88.7 129.2 1.0000 SNone 89.5 126.6 1.0000 SNone 90.3 124.1 1.0000 SNone 91.0 124.1 1.0000 SNone 91.8 121.5 1.0000 SNone 92.6 121.5 1.0000 SNone 93.4 119.0 1.0000 SNone 94.1 119.0 1.0000 SNone 94.9 116.5 1.0000 SNone 95.7 116.5 1.0000 SNone 96.5 113.9 1.0000 SNone 97.3 113.9 1.0000 SNone 98.0 111.4 1.0000 SNone 98.8 111.4 1.0000 SNone 99.6 108.8 1.0000 SNone 100.4 108.8 1.0000 SNone 101.1 124.1 1.0000 SNone 101.9 121.5 1.0000 SNone 102.7 121.5 1.0000 SNone 103.5 121.5 1.0000 SNone 104.2 119.0 1.0000 SNone 105.0 119.0 1.0000 SNone 105.8 116.5 1.0000 SNone 106.6 116.5 1.0000 SNone 107.3 113.9 1.0000 SNone 108.1 113.9 1.0000 SNone 108.9 113.9 1.0000 SNone 109.7 111.4 1.0000 SNone 110.4 111.4 1.0000 SNone 111.2 111.4 1.0000 SNone 112.0 108.8 1.0000 SNone 112.8 108.8 1.0000 SNone 113.5 121.5 1.0000 SNone 114.3 119.0 1.0000 SNone 115.1 119.0 1.0000 SNone 115.9 119.0 1.0000 SNone 116.7 116.5 1.0000 SNone 117.4 116.5 1.0000 SNone 118.2 116.5 1.0000 SNone 119.0 113.9 1.0000 SNone 119.8 113.9 1.0000 SNone 120.5 113.9 1.0000 SNone 121.3 111.4 1.0000 SNone 122.1 111.4 1.0000 SNone 122.9 111.4 1.0000 SNone 123.6 108.8 1.0000 SNone 124.4 108.8 1.0000 SNone 125.2 108.8 1.0000 SNone 126.0 119.0 1.0000 SNone 126.7 119.0 1.0000 SNone 127.5 116.5 1.0000 SNone 128.3 116.5 1.0000 SNone 129.1 116.5 1.0000 SNone 129.8 116.5 1.0000 SNone 130.6 113.9 1.0000 SNone 131.4 113.9 1.0000 SNone 132.2 113.9 1.0000 SNone 132.9 111.4 1.0000 SNone 133.7 111.4 1.0000 SNone 134.5 111.4 1.0000 SNone 135.3 111.4 1.0000 SNone 136.1 108.8 1.0000 SNone 136.8 108.8 1.0000 SNone 137.6 108.8 1.0000 SNone 138.4 119.0 1.0000 SNone 139.2 116.5 1.0000 SNone 139.9 116.5 1.0000 SNone 140.7 116.5 1.0000 SNone 141.5 113.9 1.0000 SNone 142.3 113.9 1.0000 SNone 143.0 113.9 1.0000 SNone 143.8 113.9 1.0000 SNone 144.6 111.4 1.0000 SNone 145.4 111.4 1.0000 SNone 146.1 111.4 1.0000 SNone 146.9 111.4 1.0000 SNone 147.7 108.8 1.0000 SNone 148.5 108.8 1.0000 SNone 149.2 108.8 1.0000 SNone 150.0 108.8 1.0000 SNone 150.8 116.5 1.0000 SNone 151.6 116.5 1.0000 SNone 152.3 116.5 1.0000 SNone 153.1 113.9 1.0000 SNone 153.9 113.9 1.0000 SNone 154.7 113.9 1.0000 SNone 155.5 113.9 1.0000 SNone 156.2 111.4 1.0000 SNone 157.0 111.4 1.0000 SNone 157.8 111.4 1.0000 SNone 158.6 111.4 1.0000 SNone 159.3 111.4 1.0000 SNone 160.1 108.8 1.0000 SNone 160.9 108.8 1.0000 SNone 161.7 108.8 1.0000 SNone 162.4 108.8 1.0000 SNone 163.2 116.5 1.0000 SNone 164.0 113.9 1.0000 SNone 164.8 113.9 1.0000 SNone 165.5 113.9 1.0000 SNone 166.3 113.9 1.0000 SNone 167.1 113.9 1.0000 SNone 167.9 111.4 1.0000 SNone 168.6 111.4 1.0000 SNone 169.4 111.4 1.0000 SNone 170.2 111.4 1.0000 SNone 171.0 111.4 1.0000 SNone 171.7 108.8 1.0000 SNone 172.5 108.8 1.0000 SNone 173.3 108.8 1.0000 SNone 174.1 108.8 1.0000 SNone 174.9 108.8 1.0000 SNone 175.6 113.9 1.0000 SNone 176.4 113.9 1.0000 SNone 177.2 113.9 1.0000 SNone 178.0 113.9 1.0000 SNone 178.7 113.9 1.0000 SNone 179.5 111.4 1.0000 SNone 180.3 111.4 1.0000 SNone 181.1 111.4 1.0000 SNone 181.8 111.4 1.0000 SNone 182.6 111.4 1.0000 SNone 183.4 111.4 1.0000 SNone 184.2 108.8 1.0000 SNone 184.9 108.8 1.0000 SNone 185.7 108.8 1.0000 SNone 186.5 108.8 1.0000 SNone 187.3 108.8 1.0000 SNone 188.0 113.9 1.0000 SNone 188.8 113.9 1.0000 SNone 189.6 113.9 1.0000 SNone 190.4 113.9 1.0000 SNone 191.1 111.4 1.0000 SNone 191.9 111.4 1.0000 SNone 192.7 111.4 1.0000 SNone 193.5 111.4 1.0000 SNone 194.3 111.4 1.0000 SNone 195.0 111.4 1.0000 SNone 195.8 108.8 1.0000 SNone 196.6 108.8 1.0000 SNone 197.4 108.8 1.0000 SNone 198.1 108.8 1.0000 SNone 198.9 108.8 1.0000 SNone 199.7 108.8 1.0000 SNone 200.5 113.9 1.0000 SNone 201.2 113.9 1.0000 SNone 202.0 113.9 1.0000 SNone 202.8 111.4 1.0000 SNone 203.6 111.4 1.0000 SNone 204.3 111.4 1.0000 SNone 205.1 111.4 1.0000 SNone 205.9 111.4 1.0000 SNone 206.7 111.4 1.0000 SNone 207.4 111.4 1.0000 SNone 208.2 108.8 1.0000 SNone 209.0 108.8 1.0000 SNone 209.8 108.8 1.0000 SNone 210.5 108.8 1.0000 SNone 211.3 108.8 1.0000 SNone 212.1 108.8 1.0000 SNone 212.9 113.9 1.0000 SNone 213.7 113.9 1.0000 SNone 214.4 111.4 1.0000 SNone 215.2 111.4 1.0000 SNone 216.0 111.4 1.0000 SNone 216.8 111.4 1.0000 SNone 217.5 111.4 1.0000 SNone 218.3 111.4 1.0000 SNone 219.1 111.4 1.0000 SNone 219.9 108.8 1.0000 SNone 220.6 108.8 1.0000 SNone 221.4 108.8 1.0000 SNone 222.2 108.8 1.0000 SNone 223.0 108.8 1.0000 SNone 223.7 108.8 1.0000 SNone 224.5 108.8 1.0000 SNone 225.3 113.9 1.0000 SNone 226.1 111.4 1.0000 SNone 226.8 111.4 1.0000 SNone 227.6 111.4 1.0000 SNone 228.4 111.4 1.0000 SNone 229.2 111.4 1.0000 SNone 229.9 111.4 1.0000 SNone 230.7 111.4 1.0000 SNone 231.5 111.4 1.0000 SNone 232.3 108.8 1.0000 SNone 233.1 108.8 1.0000 SNone 233.8 108.8 1.0000 SNone 234.6 108.8 1.0000 SNone 235.4 108.8 1.0000 SNone 236.2 108.8 1.0000 SNone 236.9 108.8 1.0000 SNone 237.7 113.9 1.0000 SNone 238.5 111.4 1.0000 SNone 239.3 111.4 1.0000 SNone 240.0 111.4 1.0000 SNone 240.8 111.4 1.0000 SNone 241.6 111.4 1.0000 SNone 242.4 111.4 1.0000 SNone 243.1 111.4 1.0000 SNone 243.9 108.8 1.0000 SNone 244.7 108.8 1.0000 SNone 245.5 108.8 1.0000 SNone 246.2 108.8 1.0000 SNone 247.0 108.8 1.0000 SNone 247.8 108.8 1.0000 SNone 248.6 108.8 1.0000 SNone 249.3 108.8 1.0000 SNone 250.1 111.4 1.0000 SNone 250.9 111.4 1.0000 SNone 251.7 111.4 1.0000 SNone 252.5 111.4 1.0000 SNone 253.2 111.4 1.0000 SNone 254.0 111.4 1.0000 SNone 254.8 111.4 1.0000 SNone 255.6 111.4 1.0000 SNone 256.3 108.8 1.0000 SNone 257.1 108.8 1.0000 SNone 257.9 108.8 1.0000 SNone 258.7 108.8 1.0000 SNone 259.4 108.8 1.0000 SNone 260.2 108.8 1.0000 SNone 261.0 108.8 1.0000 SNone 261.8 108.8 1.0000 SNone 262.5 111.4 1.0000 SNone 263.3 111.4 1.0000 SNone 264.1 111.4 1.0000 SNone 264.9 111.4 1.0000 SNone 265.6 111.4 1.0000 SNone 266.4 111.4 1.0000 SNone 267.2 111.4 1.0000 SNone 268.0 108.8 1.0000 SNone 268.7 108.8 1.0000 SNone 269.5 108.8 1.0000 SNone 270.3 108.8 1.0000 SNone 271.1 108.8 1.0000 SNone 271.9 108.8 1.0000 SNone 272.6 108.8 1.0000 SNone 273.4 108.8 1.0000 SNone 274.2 108.8 1.0000 SNone 275.0 111.4 1.0000 SNone 275.7 111.4 1.0000 SNone 276.5 111.4 1.0000 SNone 277.3 111.4 1.0000 SNone 278.1 111.4 1.0000 SNone 278.8 111.4 1.0000 SNone 279.6 111.4 1.0000 SNone 280.4 108.8 1.0000 SNone 281.2 108.8 1.0000 SNone 281.9 108.8 1.0000 SNone 282.7 108.8 1.0000 SNone 283.5 108.8 1.0000 SNone 284.3 108.8 1.0000 SNone 285.0 108.8 1.0000 SNone 285.8 108.8 1.0000 SNone 286.6 108.8 1.0000 SNone 287.4 111.4 1.0000 SNone 288.1 111.4 1.0000 SNone 288.9 111.4 1.0000 SNone 289.7 111.4 1.0000 SNone 290.5 111.4 1.0000 SNone 291.3 111.4 1.0000 SNone 292.0 108.8 1.0000 SNone 292.8 108.8 1.0000 SNone 293.6 108.8 1.0000 SNone 294.4 108.8 1.0000 SNone 295.1 108.8 1.0000 SNone 295.9 108.8 1.0000 SNone 296.7 108.8 1.0000 SNone 297.5 108.8 1.0000 SNone 298.2 108.8 1.0000 SNone 299.0 108.8 1.0000 SNone 299.8 111.4 1.0000 SNone 300.6 111.4 1.0000 SNone 301.3 111.4 1.0000 SNone 302.1 111.4 1.0000 SNone 302.9 111.4 1.0000 SNone 303.7 111.4 1.0000 SNone 304.4 108.8 1.0000 SNone 305.2 108.8 1.0000 SNone 306.0 108.8 1.0000 SNone 306.8 108.8 1.0000 SNone 307.5 108.8 1.0000 SNone 308.3 108.8 1.0000 SNone 309.1 108.8 1.0000 SNone 309.9 108.8 1.0000 SNone 310.7 108.8 1.0000 SNone 311.4 108.8 1.0000 SNone 312.2 111.4 1.0000 SNone 313.0 111.4 1.0000 SNone 313.8 111.4 1.0000 SNone 314.5 111.4 1.0000 SNone 315.3 111.4 1.0000 SNone 316.1 108.8 1.0000 SNone 316.9 108.8 1.0000 SNone 317.6 108.8 1.0000 SNone 318.4 108.8 1.0000 SNone 319.2 108.8 1.0000 SNone 320.0 108.8 1.0000 SNone 320.7 108.8 1.0000 SNone 321.5 108.8 1.0000 SNone 322.3 108.8 1.0000 SNone 323.1 108.8 1.0000 SNone 323.8 108.8 1.0000 SNone 324.6 111.4 1.0000 SNone 325.4 111.4 1.0000 SNone 326.2 111.4 1.0000 SNone 326.9 111.4 1.0000 SNone 327.7 111.4 1.0000 SNone 328.5 108.8 1.0000 SNone 329.3 108.8 1.0000 SNone 330.1 108.8 1.0000 SNone 330.8 108.8 1.0000 SNone 331.6 108.8 1.0000 SNone 332.4 108.8 1.0000 SNone 333.2 108.8 1.0000 SNone 333.9 108.8 1.0000 SNone 334.7 108.8 1.0000 SNone 335.5 108.8 1.0000 SNone 336.3 108.8 1.0000 SNone 337.0 111.4 1.0000 SNone 337.8 111.4 1.0000 SNone 338.6 111.4 1.0000 SNone 339.4 111.4 1.0000 SNone 340.1 108.8 1.0000 SNone 340.9 108.8 1.0000 SNone 341.7 108.8 1.0000 SNone 342.5 108.8 1.0000 SNone 343.2 108.8 1.0000 SNone 344.0 108.8 1.0000 SNone 344.8 108.8 1.0000 SNone 345.6 108.8 1.0000 SNone 346.3 108.8 1.0000 SNone 347.1 108.8 1.0000 SNone 347.9 108.8 1.0000 SNone 348.7 108.8 1.0000 SNone 349.5 111.4 1.0000 SNone 350.2 111.4 1.0000 SNone 1.000000 setlinewidth [5 4] 0 setdash 42.9 281.6 MT 43.7 243.5 LT 44.5 213.0 LT 45.3 190.1 LT 46.0 169.8 LT 46.8 157.1 LT 47.6 144.4 LT 48.4 134.2 LT 49.1 126.6 LT 49.9 119.0 LT 50.7 113.9 LT 51.5 108.8 LT 52.2 103.8 LT 53.0 98.7 LT 53.8 93.6 LT 54.6 91.1 LT 55.3 88.5 LT 56.1 86.0 LT 56.9 83.4 LT 57.7 80.9 LT 58.5 78.4 LT 59.2 126.6 LT 60.0 121.5 LT 60.8 119.0 LT 61.6 116.5 LT 62.3 113.9 LT 63.1 111.4 LT 63.9 108.8 LT 64.7 106.3 LT 65.4 103.8 LT 66.2 101.2 LT 67.0 98.7 LT 67.8 96.1 LT 68.5 93.6 LT 69.3 93.6 LT 70.1 91.1 LT 70.9 88.5 LT 71.6 88.5 LT 72.4 86.0 LT 73.2 86.0 LT 74.0 83.4 LT 74.7 83.4 LT 75.5 80.9 LT 76.3 80.9 LT 77.1 78.4 LT 77.9 78.4 LT 78.6 78.4 LT 79.4 101.2 LT 80.2 98.7 LT 81.0 98.7 LT 81.7 96.1 LT stroke 81.7 96.1 MT 82.5 96.1 LT 83.3 93.6 LT 84.1 93.6 LT 84.8 93.6 LT 85.6 91.1 LT 86.4 91.1 LT 87.2 88.5 LT 87.9 88.5 LT 88.7 88.5 LT 89.5 86.0 LT 90.3 86.0 LT 91.0 83.4 LT 91.8 83.4 LT 92.6 83.4 LT 93.4 80.9 LT 94.1 80.9 LT 94.9 80.9 LT 95.7 80.9 LT 96.5 78.4 LT 97.3 78.4 LT 98.0 78.4 LT 98.8 93.6 LT 99.6 93.6 LT 100.4 91.1 LT 101.1 91.1 LT 101.9 91.1 LT 102.7 88.5 LT 103.5 88.5 LT 104.2 88.5 LT 105.0 88.5 LT 105.8 86.0 LT 106.6 86.0 LT 107.3 86.0 LT 108.1 86.0 LT 108.9 83.4 LT 109.7 83.4 LT 110.4 83.4 LT 111.2 83.4 LT 112.0 80.9 LT 112.8 80.9 LT 113.5 80.9 LT 114.3 80.9 LT 115.1 78.4 LT 115.9 78.4 LT 116.7 78.4 LT 117.4 78.4 LT 118.2 78.4 LT 119.0 88.5 LT 119.8 88.5 LT 120.5 88.5 LT 121.3 88.5 LT stroke 121.3 88.5 MT 122.1 86.0 LT 122.9 86.0 LT 123.6 86.0 LT 124.4 86.0 LT 125.2 86.0 LT 126.0 83.4 LT 126.7 83.4 LT 127.5 83.4 LT 128.3 83.4 LT 129.1 83.4 LT 129.8 80.9 LT 130.6 80.9 LT 131.4 80.9 LT 132.2 80.9 LT 132.9 80.9 LT 133.7 78.4 LT 134.5 78.4 LT 135.3 78.4 LT 136.1 78.4 LT 136.8 78.4 LT 137.6 78.4 LT 138.4 88.5 LT 139.2 86.0 LT 139.9 86.0 LT 140.7 86.0 LT 141.5 86.0 LT 142.3 86.0 LT 143.0 83.4 LT 143.8 83.4 LT 144.6 83.4 LT 145.4 83.4 LT 146.1 83.4 LT 146.9 83.4 LT 147.7 80.9 LT 148.5 80.9 LT 149.2 80.9 LT 150.0 80.9 LT 150.8 80.9 LT 151.6 80.9 LT 152.3 80.9 LT 153.1 78.4 LT 153.9 78.4 LT 154.7 78.4 LT 155.5 78.4 LT 156.2 78.4 LT 157.0 78.4 LT 157.8 78.4 LT 158.6 86.0 LT 159.3 86.0 LT 160.1 83.4 LT 160.9 83.4 LT stroke 160.9 83.4 MT 161.7 83.4 LT 162.4 83.4 LT 163.2 83.4 LT 164.0 83.4 LT 164.8 83.4 LT 165.5 80.9 LT 166.3 80.9 LT 167.1 80.9 LT 167.9 80.9 LT 168.6 80.9 LT 169.4 80.9 LT 170.2 80.9 LT 171.0 80.9 LT 171.7 78.4 LT 172.5 78.4 LT 173.3 78.4 LT 174.1 78.4 LT 174.9 78.4 LT 175.6 78.4 LT 176.4 78.4 LT 177.2 78.4 LT 178.0 78.4 LT 178.7 83.4 LT 179.5 83.4 LT 180.3 83.4 LT 181.1 83.4 LT 181.8 83.4 LT 182.6 83.4 LT 183.4 83.4 LT 184.2 80.9 LT 184.9 80.9 LT 185.7 80.9 LT 186.5 80.9 LT 187.3 80.9 LT 188.0 80.9 LT 188.8 80.9 LT 189.6 80.9 LT 190.4 80.9 LT 191.1 78.4 LT 191.9 78.4 LT 192.7 78.4 LT 193.5 78.4 LT 194.3 78.4 LT 195.0 78.4 LT 195.8 78.4 LT 196.6 78.4 LT 197.4 78.4 LT 198.1 83.4 LT 198.9 83.4 LT 199.7 83.4 LT 200.5 83.4 LT stroke 200.5 83.4 MT 201.2 83.4 LT 202.0 80.9 LT 202.8 80.9 LT 203.6 80.9 LT 204.3 80.9 LT 205.1 80.9 LT 205.9 80.9 LT 206.7 80.9 LT 207.4 80.9 LT 208.2 80.9 LT 209.0 80.9 LT 209.8 78.4 LT 210.5 78.4 LT 211.3 78.4 LT 212.1 78.4 LT 212.9 78.4 LT 213.7 78.4 LT 214.4 78.4 LT 215.2 78.4 LT 216.0 78.4 LT 216.8 78.4 LT 217.5 78.4 LT 218.3 83.4 LT 219.1 83.4 LT 219.9 80.9 LT 220.6 80.9 LT 221.4 80.9 LT 222.2 80.9 LT 223.0 80.9 LT 223.7 80.9 LT 224.5 80.9 LT 225.3 80.9 LT 226.1 80.9 LT 226.8 80.9 LT 227.6 80.9 LT 228.4 78.4 LT 229.2 78.4 LT 229.9 78.4 LT 230.7 78.4 LT 231.5 78.4 LT 232.3 78.4 LT 233.1 78.4 LT 233.8 78.4 LT 234.6 78.4 LT 235.4 78.4 LT 236.2 78.4 LT 236.9 78.4 LT 237.7 83.4 LT 238.5 80.9 LT 239.3 80.9 LT 240.0 80.9 LT stroke 240.0 80.9 MT 240.8 80.9 LT 241.6 80.9 LT 242.4 80.9 LT 243.1 80.9 LT 243.9 80.9 LT 244.7 80.9 LT 245.5 80.9 LT 246.2 80.9 LT 247.0 80.9 LT 247.8 78.4 LT 248.6 78.4 LT 249.3 78.4 LT 250.1 78.4 LT 250.9 78.4 LT 251.7 78.4 LT 252.5 78.4 LT 253.2 78.4 LT 254.0 78.4 LT 254.8 78.4 LT 255.6 78.4 LT 256.3 78.4 LT 257.1 78.4 LT 257.9 80.9 LT 258.7 80.9 LT 259.4 80.9 LT 260.2 80.9 LT 261.0 80.9 LT 261.8 80.9 LT 262.5 80.9 LT 263.3 80.9 LT 264.1 80.9 LT 264.9 80.9 LT 265.6 80.9 LT 266.4 78.4 LT 267.2 78.4 LT 268.0 78.4 LT 268.7 78.4 LT 269.5 78.4 LT 270.3 78.4 LT 271.1 78.4 LT 271.9 78.4 LT 272.6 78.4 LT 273.4 78.4 LT 274.2 78.4 LT 275.0 78.4 LT 275.7 78.4 LT 276.5 78.4 LT 277.3 78.4 LT 278.1 80.9 LT 278.8 80.9 LT 279.6 80.9 LT stroke 279.6 80.9 MT 280.4 80.9 LT 281.2 80.9 LT 281.9 80.9 LT 282.7 80.9 LT 283.5 80.9 LT 284.3 80.9 LT 285.0 78.4 LT 285.8 78.4 LT 286.6 78.4 LT 287.4 78.4 LT 288.1 78.4 LT 288.9 78.4 LT 289.7 78.4 LT 290.5 78.4 LT 291.3 78.4 LT 292.0 78.4 LT 292.8 78.4 LT 293.6 78.4 LT 294.4 78.4 LT 295.1 78.4 LT 295.9 78.4 LT 296.7 78.4 LT 297.5 80.9 LT 298.2 80.9 LT 299.0 80.9 LT 299.8 80.9 LT 300.6 80.9 LT 301.3 80.9 LT 302.1 80.9 LT 302.9 80.9 LT 303.7 80.9 LT 304.4 78.4 LT 305.2 78.4 LT 306.0 78.4 LT 306.8 78.4 LT 307.5 78.4 LT 308.3 78.4 LT 309.1 78.4 LT 309.9 78.4 LT 310.7 78.4 LT 311.4 78.4 LT 312.2 78.4 LT 313.0 78.4 LT 313.8 78.4 LT 314.5 78.4 LT 315.3 78.4 LT 316.1 78.4 LT 316.9 78.4 LT 317.6 80.9 LT 318.4 80.9 LT 319.2 80.9 LT stroke 319.2 80.9 MT 320.0 80.9 LT 320.7 80.9 LT 321.5 80.9 LT 322.3 80.9 LT 323.1 78.4 LT 323.8 78.4 LT 324.6 78.4 LT 325.4 78.4 LT 326.2 78.4 LT 326.9 78.4 LT 327.7 78.4 LT 328.5 78.4 LT 329.3 78.4 LT 330.1 78.4 LT 330.8 78.4 LT 331.6 78.4 LT 332.4 78.4 LT 333.2 78.4 LT 333.9 78.4 LT 334.7 78.4 LT 335.5 78.4 LT 336.3 78.4 LT 337.0 80.9 LT 337.8 80.9 LT 338.6 80.9 LT 339.4 80.9 LT 340.1 80.9 LT 340.9 80.9 LT 341.7 80.9 LT 342.5 78.4 LT 343.2 78.4 LT 344.0 78.4 LT 344.8 78.4 LT 345.6 78.4 LT 346.3 78.4 LT 347.1 78.4 LT 347.9 78.4 LT 348.7 78.4 LT 349.5 78.4 LT 350.2 78.4 LT stroke 1.000000 setlinewidth [] 0 setdash 43.7 243.5 1.0000 SNone 44.5 213.0 1.0000 SNone 45.3 190.1 1.0000 SNone 46.0 169.8 1.0000 SNone 46.8 157.1 1.0000 SNone 47.6 144.4 1.0000 SNone 48.4 134.2 1.0000 SNone 49.1 126.6 1.0000 SNone 49.9 119.0 1.0000 SNone 50.7 113.9 1.0000 SNone 51.5 108.8 1.0000 SNone 52.2 103.8 1.0000 SNone 53.0 98.7 1.0000 SNone 53.8 93.6 1.0000 SNone 54.6 91.1 1.0000 SNone 55.3 88.5 1.0000 SNone 56.1 86.0 1.0000 SNone 56.9 83.4 1.0000 SNone 57.7 80.9 1.0000 SNone 58.5 78.4 1.0000 SNone 59.2 126.6 1.0000 SNone 60.0 121.5 1.0000 SNone 60.8 119.0 1.0000 SNone 61.6 116.5 1.0000 SNone 62.3 113.9 1.0000 SNone 63.1 111.4 1.0000 SNone 63.9 108.8 1.0000 SNone 64.7 106.3 1.0000 SNone 65.4 103.8 1.0000 SNone 66.2 101.2 1.0000 SNone 67.0 98.7 1.0000 SNone 67.8 96.1 1.0000 SNone 68.5 93.6 1.0000 SNone 69.3 93.6 1.0000 SNone 70.1 91.1 1.0000 SNone 70.9 88.5 1.0000 SNone 71.6 88.5 1.0000 SNone 72.4 86.0 1.0000 SNone 73.2 86.0 1.0000 SNone 74.0 83.4 1.0000 SNone 74.7 83.4 1.0000 SNone 75.5 80.9 1.0000 SNone 76.3 80.9 1.0000 SNone 77.1 78.4 1.0000 SNone 77.9 78.4 1.0000 SNone 78.6 78.4 1.0000 SNone 79.4 101.2 1.0000 SNone 80.2 98.7 1.0000 SNone 81.0 98.7 1.0000 SNone 81.7 96.1 1.0000 SNone 82.5 96.1 1.0000 SNone 83.3 93.6 1.0000 SNone 84.1 93.6 1.0000 SNone 84.8 93.6 1.0000 SNone 85.6 91.1 1.0000 SNone 86.4 91.1 1.0000 SNone 87.2 88.5 1.0000 SNone 87.9 88.5 1.0000 SNone 88.7 88.5 1.0000 SNone 89.5 86.0 1.0000 SNone 90.3 86.0 1.0000 SNone 91.0 83.4 1.0000 SNone 91.8 83.4 1.0000 SNone 92.6 83.4 1.0000 SNone 93.4 80.9 1.0000 SNone 94.1 80.9 1.0000 SNone 94.9 80.9 1.0000 SNone 95.7 80.9 1.0000 SNone 96.5 78.4 1.0000 SNone 97.3 78.4 1.0000 SNone 98.0 78.4 1.0000 SNone 98.8 93.6 1.0000 SNone 99.6 93.6 1.0000 SNone 100.4 91.1 1.0000 SNone 101.1 91.1 1.0000 SNone 101.9 91.1 1.0000 SNone 102.7 88.5 1.0000 SNone 103.5 88.5 1.0000 SNone 104.2 88.5 1.0000 SNone 105.0 88.5 1.0000 SNone 105.8 86.0 1.0000 SNone 106.6 86.0 1.0000 SNone 107.3 86.0 1.0000 SNone 108.1 86.0 1.0000 SNone 108.9 83.4 1.0000 SNone 109.7 83.4 1.0000 SNone 110.4 83.4 1.0000 SNone 111.2 83.4 1.0000 SNone 112.0 80.9 1.0000 SNone 112.8 80.9 1.0000 SNone 113.5 80.9 1.0000 SNone 114.3 80.9 1.0000 SNone 115.1 78.4 1.0000 SNone 115.9 78.4 1.0000 SNone 116.7 78.4 1.0000 SNone 117.4 78.4 1.0000 SNone 118.2 78.4 1.0000 SNone 119.0 88.5 1.0000 SNone 119.8 88.5 1.0000 SNone 120.5 88.5 1.0000 SNone 121.3 88.5 1.0000 SNone 122.1 86.0 1.0000 SNone 122.9 86.0 1.0000 SNone 123.6 86.0 1.0000 SNone 124.4 86.0 1.0000 SNone 125.2 86.0 1.0000 SNone 126.0 83.4 1.0000 SNone 126.7 83.4 1.0000 SNone 127.5 83.4 1.0000 SNone 128.3 83.4 1.0000 SNone 129.1 83.4 1.0000 SNone 129.8 80.9 1.0000 SNone 130.6 80.9 1.0000 SNone 131.4 80.9 1.0000 SNone 132.2 80.9 1.0000 SNone 132.9 80.9 1.0000 SNone 133.7 78.4 1.0000 SNone 134.5 78.4 1.0000 SNone 135.3 78.4 1.0000 SNone 136.1 78.4 1.0000 SNone 136.8 78.4 1.0000 SNone 137.6 78.4 1.0000 SNone 138.4 88.5 1.0000 SNone 139.2 86.0 1.0000 SNone 139.9 86.0 1.0000 SNone 140.7 86.0 1.0000 SNone 141.5 86.0 1.0000 SNone 142.3 86.0 1.0000 SNone 143.0 83.4 1.0000 SNone 143.8 83.4 1.0000 SNone 144.6 83.4 1.0000 SNone 145.4 83.4 1.0000 SNone 146.1 83.4 1.0000 SNone 146.9 83.4 1.0000 SNone 147.7 80.9 1.0000 SNone 148.5 80.9 1.0000 SNone 149.2 80.9 1.0000 SNone 150.0 80.9 1.0000 SNone 150.8 80.9 1.0000 SNone 151.6 80.9 1.0000 SNone 152.3 80.9 1.0000 SNone 153.1 78.4 1.0000 SNone 153.9 78.4 1.0000 SNone 154.7 78.4 1.0000 SNone 155.5 78.4 1.0000 SNone 156.2 78.4 1.0000 SNone 157.0 78.4 1.0000 SNone 157.8 78.4 1.0000 SNone 158.6 86.0 1.0000 SNone 159.3 86.0 1.0000 SNone 160.1 83.4 1.0000 SNone 160.9 83.4 1.0000 SNone 161.7 83.4 1.0000 SNone 162.4 83.4 1.0000 SNone 163.2 83.4 1.0000 SNone 164.0 83.4 1.0000 SNone 164.8 83.4 1.0000 SNone 165.5 80.9 1.0000 SNone 166.3 80.9 1.0000 SNone 167.1 80.9 1.0000 SNone 167.9 80.9 1.0000 SNone 168.6 80.9 1.0000 SNone 169.4 80.9 1.0000 SNone 170.2 80.9 1.0000 SNone 171.0 80.9 1.0000 SNone 171.7 78.4 1.0000 SNone 172.5 78.4 1.0000 SNone 173.3 78.4 1.0000 SNone 174.1 78.4 1.0000 SNone 174.9 78.4 1.0000 SNone 175.6 78.4 1.0000 SNone 176.4 78.4 1.0000 SNone 177.2 78.4 1.0000 SNone 178.0 78.4 1.0000 SNone 178.7 83.4 1.0000 SNone 179.5 83.4 1.0000 SNone 180.3 83.4 1.0000 SNone 181.1 83.4 1.0000 SNone 181.8 83.4 1.0000 SNone 182.6 83.4 1.0000 SNone 183.4 83.4 1.0000 SNone 184.2 80.9 1.0000 SNone 184.9 80.9 1.0000 SNone 185.7 80.9 1.0000 SNone 186.5 80.9 1.0000 SNone 187.3 80.9 1.0000 SNone 188.0 80.9 1.0000 SNone 188.8 80.9 1.0000 SNone 189.6 80.9 1.0000 SNone 190.4 80.9 1.0000 SNone 191.1 78.4 1.0000 SNone 191.9 78.4 1.0000 SNone 192.7 78.4 1.0000 SNone 193.5 78.4 1.0000 SNone 194.3 78.4 1.0000 SNone 195.0 78.4 1.0000 SNone 195.8 78.4 1.0000 SNone 196.6 78.4 1.0000 SNone 197.4 78.4 1.0000 SNone 198.1 83.4 1.0000 SNone 198.9 83.4 1.0000 SNone 199.7 83.4 1.0000 SNone 200.5 83.4 1.0000 SNone 201.2 83.4 1.0000 SNone 202.0 80.9 1.0000 SNone 202.8 80.9 1.0000 SNone 203.6 80.9 1.0000 SNone 204.3 80.9 1.0000 SNone 205.1 80.9 1.0000 SNone 205.9 80.9 1.0000 SNone 206.7 80.9 1.0000 SNone 207.4 80.9 1.0000 SNone 208.2 80.9 1.0000 SNone 209.0 80.9 1.0000 SNone 209.8 78.4 1.0000 SNone 210.5 78.4 1.0000 SNone 211.3 78.4 1.0000 SNone 212.1 78.4 1.0000 SNone 212.9 78.4 1.0000 SNone 213.7 78.4 1.0000 SNone 214.4 78.4 1.0000 SNone 215.2 78.4 1.0000 SNone 216.0 78.4 1.0000 SNone 216.8 78.4 1.0000 SNone 217.5 78.4 1.0000 SNone 218.3 83.4 1.0000 SNone 219.1 83.4 1.0000 SNone 219.9 80.9 1.0000 SNone 220.6 80.9 1.0000 SNone 221.4 80.9 1.0000 SNone 222.2 80.9 1.0000 SNone 223.0 80.9 1.0000 SNone 223.7 80.9 1.0000 SNone 224.5 80.9 1.0000 SNone 225.3 80.9 1.0000 SNone 226.1 80.9 1.0000 SNone 226.8 80.9 1.0000 SNone 227.6 80.9 1.0000 SNone 228.4 78.4 1.0000 SNone 229.2 78.4 1.0000 SNone 229.9 78.4 1.0000 SNone 230.7 78.4 1.0000 SNone 231.5 78.4 1.0000 SNone 232.3 78.4 1.0000 SNone 233.1 78.4 1.0000 SNone 233.8 78.4 1.0000 SNone 234.6 78.4 1.0000 SNone 235.4 78.4 1.0000 SNone 236.2 78.4 1.0000 SNone 236.9 78.4 1.0000 SNone 237.7 83.4 1.0000 SNone 238.5 80.9 1.0000 SNone 239.3 80.9 1.0000 SNone 240.0 80.9 1.0000 SNone 240.8 80.9 1.0000 SNone 241.6 80.9 1.0000 SNone 242.4 80.9 1.0000 SNone 243.1 80.9 1.0000 SNone 243.9 80.9 1.0000 SNone 244.7 80.9 1.0000 SNone 245.5 80.9 1.0000 SNone 246.2 80.9 1.0000 SNone 247.0 80.9 1.0000 SNone 247.8 78.4 1.0000 SNone 248.6 78.4 1.0000 SNone 249.3 78.4 1.0000 SNone 250.1 78.4 1.0000 SNone 250.9 78.4 1.0000 SNone 251.7 78.4 1.0000 SNone 252.5 78.4 1.0000 SNone 253.2 78.4 1.0000 SNone 254.0 78.4 1.0000 SNone 254.8 78.4 1.0000 SNone 255.6 78.4 1.0000 SNone 256.3 78.4 1.0000 SNone 257.1 78.4 1.0000 SNone 257.9 80.9 1.0000 SNone 258.7 80.9 1.0000 SNone 259.4 80.9 1.0000 SNone 260.2 80.9 1.0000 SNone 261.0 80.9 1.0000 SNone 261.8 80.9 1.0000 SNone 262.5 80.9 1.0000 SNone 263.3 80.9 1.0000 SNone 264.1 80.9 1.0000 SNone 264.9 80.9 1.0000 SNone 265.6 80.9 1.0000 SNone 266.4 78.4 1.0000 SNone 267.2 78.4 1.0000 SNone 268.0 78.4 1.0000 SNone 268.7 78.4 1.0000 SNone 269.5 78.4 1.0000 SNone 270.3 78.4 1.0000 SNone 271.1 78.4 1.0000 SNone 271.9 78.4 1.0000 SNone 272.6 78.4 1.0000 SNone 273.4 78.4 1.0000 SNone 274.2 78.4 1.0000 SNone 275.0 78.4 1.0000 SNone 275.7 78.4 1.0000 SNone 276.5 78.4 1.0000 SNone 277.3 78.4 1.0000 SNone 278.1 80.9 1.0000 SNone 278.8 80.9 1.0000 SNone 279.6 80.9 1.0000 SNone 280.4 80.9 1.0000 SNone 281.2 80.9 1.0000 SNone 281.9 80.9 1.0000 SNone 282.7 80.9 1.0000 SNone 283.5 80.9 1.0000 SNone 284.3 80.9 1.0000 SNone 285.0 78.4 1.0000 SNone 285.8 78.4 1.0000 SNone 286.6 78.4 1.0000 SNone 287.4 78.4 1.0000 SNone 288.1 78.4 1.0000 SNone 288.9 78.4 1.0000 SNone 289.7 78.4 1.0000 SNone 290.5 78.4 1.0000 SNone 291.3 78.4 1.0000 SNone 292.0 78.4 1.0000 SNone 292.8 78.4 1.0000 SNone 293.6 78.4 1.0000 SNone 294.4 78.4 1.0000 SNone 295.1 78.4 1.0000 SNone 295.9 78.4 1.0000 SNone 296.7 78.4 1.0000 SNone 297.5 80.9 1.0000 SNone 298.2 80.9 1.0000 SNone 299.0 80.9 1.0000 SNone 299.8 80.9 1.0000 SNone 300.6 80.9 1.0000 SNone 301.3 80.9 1.0000 SNone 302.1 80.9 1.0000 SNone 302.9 80.9 1.0000 SNone 303.7 80.9 1.0000 SNone 304.4 78.4 1.0000 SNone 305.2 78.4 1.0000 SNone 306.0 78.4 1.0000 SNone 306.8 78.4 1.0000 SNone 307.5 78.4 1.0000 SNone 308.3 78.4 1.0000 SNone 309.1 78.4 1.0000 SNone 309.9 78.4 1.0000 SNone 310.7 78.4 1.0000 SNone 311.4 78.4 1.0000 SNone 312.2 78.4 1.0000 SNone 313.0 78.4 1.0000 SNone 313.8 78.4 1.0000 SNone 314.5 78.4 1.0000 SNone 315.3 78.4 1.0000 SNone 316.1 78.4 1.0000 SNone 316.9 78.4 1.0000 SNone 317.6 80.9 1.0000 SNone 318.4 80.9 1.0000 SNone 319.2 80.9 1.0000 SNone 320.0 80.9 1.0000 SNone 320.7 80.9 1.0000 SNone 321.5 80.9 1.0000 SNone 322.3 80.9 1.0000 SNone 323.1 78.4 1.0000 SNone 323.8 78.4 1.0000 SNone 324.6 78.4 1.0000 SNone 325.4 78.4 1.0000 SNone 326.2 78.4 1.0000 SNone 326.9 78.4 1.0000 SNone 327.7 78.4 1.0000 SNone 328.5 78.4 1.0000 SNone 329.3 78.4 1.0000 SNone 330.1 78.4 1.0000 SNone 330.8 78.4 1.0000 SNone 331.6 78.4 1.0000 SNone 332.4 78.4 1.0000 SNone 333.2 78.4 1.0000 SNone 333.9 78.4 1.0000 SNone 334.7 78.4 1.0000 SNone 335.5 78.4 1.0000 SNone 336.3 78.4 1.0000 SNone 337.0 80.9 1.0000 SNone 337.8 80.9 1.0000 SNone 338.6 80.9 1.0000 SNone 339.4 80.9 1.0000 SNone 340.1 80.9 1.0000 SNone 340.9 80.9 1.0000 SNone 341.7 80.9 1.0000 SNone 342.5 78.4 1.0000 SNone 343.2 78.4 1.0000 SNone 344.0 78.4 1.0000 SNone 344.8 78.4 1.0000 SNone 345.6 78.4 1.0000 SNone 346.3 78.4 1.0000 SNone 347.1 78.4 1.0000 SNone 347.9 78.4 1.0000 SNone 348.7 78.4 1.0000 SNone 349.5 78.4 1.0000 SNone 350.2 78.4 1.0000 SNone 1.000000 setlinewidth [2 3] 0 setdash 39.8 27.6 MT 40.6 27.6 LT 41.4 27.6 LT 42.2 27.6 LT 42.9 27.6 LT 43.7 27.6 LT 44.5 27.6 LT 45.3 27.6 LT 46.0 27.6 LT 46.8 27.6 LT 47.6 27.6 LT 48.4 27.6 LT 49.1 27.6 LT 49.9 27.6 LT 50.7 27.6 LT 51.5 108.8 LT 52.2 103.8 LT 53.0 98.7 LT 53.8 96.1 LT 54.6 93.6 LT 55.3 88.5 LT 56.1 86.0 LT 56.9 83.4 LT 57.7 80.9 LT 58.5 78.4 LT 59.2 27.6 LT 60.0 27.6 LT 60.8 27.6 LT 61.6 27.6 LT 62.3 27.6 LT 63.1 27.6 LT 63.9 68.2 LT 64.7 65.7 LT 65.4 65.7 LT 66.2 63.1 LT 67.0 63.1 LT 67.8 63.1 LT 68.5 63.1 LT 69.3 60.6 LT 70.1 60.6 LT 70.9 60.6 LT 71.6 58.0 LT 72.4 58.0 LT 73.2 55.5 LT 74.0 58.0 LT 74.7 55.5 LT 75.5 55.5 LT 76.3 80.9 LT 77.1 80.9 LT 77.9 78.4 LT 78.6 78.4 LT stroke 78.6 78.4 MT 79.4 53.0 LT 80.2 53.0 LT 81.0 50.4 LT 81.7 53.0 LT 82.5 50.4 LT 83.3 50.4 LT 84.1 50.4 LT 84.8 47.9 LT 85.6 50.4 LT 86.4 47.9 LT 87.2 50.4 LT 87.9 47.9 LT 88.7 68.2 LT 89.5 68.2 LT 90.3 65.7 LT 91.0 68.2 LT 91.8 65.7 LT 92.6 65.7 LT 93.4 65.7 LT 94.1 65.7 LT 94.9 63.1 LT 95.7 63.1 LT 96.5 63.1 LT 97.3 63.1 LT 98.0 60.6 LT 98.8 45.3 LT 99.6 42.8 LT 100.4 45.3 LT 101.1 60.6 LT 101.9 58.0 LT 102.7 60.6 LT 103.5 60.6 LT 104.2 58.0 LT 105.0 58.0 LT 105.8 58.0 LT 106.6 58.0 LT 107.3 55.5 LT 108.1 55.5 LT 108.9 58.0 LT 109.7 55.5 LT 110.4 55.5 LT 111.2 55.5 LT 112.0 55.5 LT 112.8 55.5 LT 113.5 68.2 LT 114.3 65.7 LT 115.1 68.2 LT 115.9 68.2 LT 116.7 65.7 LT 117.4 65.7 LT 118.2 65.7 LT stroke 118.2 65.7 MT 119.0 53.0 LT 119.8 53.0 LT 120.5 53.0 LT 121.3 50.4 LT 122.1 53.0 LT 122.9 53.0 LT 123.6 50.4 LT 124.4 50.4 LT 125.2 50.4 LT 126.0 63.1 LT 126.7 63.1 LT 127.5 60.6 LT 128.3 60.6 LT 129.1 60.6 LT 129.8 63.1 LT 130.6 60.6 LT 131.4 60.6 LT 132.2 60.6 LT 132.9 58.0 LT 133.7 60.6 LT 134.5 60.6 LT 135.3 60.6 LT 136.1 58.0 LT 136.8 58.0 LT 137.6 58.0 LT 138.4 58.0 LT 139.2 58.0 LT 139.9 58.0 LT 140.7 58.0 LT 141.5 55.5 LT 142.3 55.5 LT 143.0 58.0 LT 143.8 58.0 LT 144.6 55.5 LT 145.4 55.5 LT 146.1 55.5 LT 146.9 55.5 LT 147.7 55.5 LT 148.5 55.5 LT 149.2 55.5 LT 150.0 55.5 LT 150.8 63.1 LT 151.6 63.1 LT 152.3 63.1 LT 153.1 63.1 LT 153.9 63.1 LT 154.7 63.1 LT 155.5 63.1 LT 156.2 60.6 LT 157.0 60.6 LT 157.8 60.6 LT stroke 157.8 60.6 MT 158.6 53.0 LT 159.3 53.0 LT 160.1 53.0 LT 160.9 53.0 LT 161.7 53.0 LT 162.4 53.0 LT 163.2 60.6 LT 164.0 58.0 LT 164.8 58.0 LT 165.5 60.6 LT 166.3 60.6 LT 167.1 60.6 LT 167.9 58.0 LT 168.6 58.0 LT 169.4 58.0 LT 170.2 58.0 LT 171.0 58.0 LT 171.7 58.0 LT 172.5 58.0 LT 173.3 58.0 LT 174.1 58.0 LT 174.9 58.0 LT 175.6 63.1 LT 176.4 63.1 LT 177.2 63.1 LT 178.0 63.1 LT 178.7 58.0 LT 179.5 55.5 LT 180.3 55.5 LT 181.1 55.5 LT 181.8 55.5 LT 182.6 55.5 LT 183.4 55.5 LT 184.2 55.5 LT 184.9 55.5 LT 185.7 55.5 LT 186.5 55.5 LT 187.3 55.5 LT 188.0 60.6 LT 188.8 60.6 LT 189.6 60.6 LT 190.4 60.6 LT 191.1 60.6 LT 191.9 60.6 LT 192.7 60.6 LT 193.5 60.6 LT 194.3 60.6 LT 195.0 60.6 LT 195.8 58.0 LT 196.6 58.0 LT 197.4 58.0 LT stroke 197.4 58.0 MT 198.1 53.0 LT 198.9 53.0 LT 199.7 53.0 LT 200.5 58.0 LT 201.2 58.0 LT 202.0 60.6 LT 202.8 58.0 LT 203.6 58.0 LT 204.3 58.0 LT 205.1 58.0 LT 205.9 58.0 LT 206.7 58.0 LT 207.4 58.0 LT 208.2 55.5 LT 209.0 55.5 LT 209.8 58.0 LT 210.5 58.0 LT 211.3 58.0 LT 212.1 58.0 LT 212.9 63.1 LT 213.7 63.1 LT 214.4 60.6 LT 215.2 60.6 LT 216.0 60.6 LT 216.8 60.6 LT 217.5 60.6 LT 218.3 55.5 LT 219.1 55.5 LT 219.9 55.5 LT 220.6 55.5 LT 221.4 55.5 LT 222.2 55.5 LT 223.0 55.5 LT 223.7 55.5 LT 224.5 55.5 LT 225.3 60.6 LT 226.1 58.0 LT 226.8 58.0 LT 227.6 58.0 LT 228.4 60.6 LT 229.2 60.6 LT 229.9 60.6 LT 230.7 60.6 LT 231.5 60.6 LT 232.3 58.0 LT 233.1 58.0 LT 233.8 58.0 LT 234.6 58.0 LT 235.4 58.0 LT 236.2 58.0 LT 236.9 58.0 LT stroke 236.9 58.0 MT 237.7 58.0 LT 238.5 58.0 LT 239.3 58.0 LT 240.0 58.0 LT 240.8 58.0 LT 241.6 58.0 LT 242.4 58.0 LT 243.1 58.0 LT 243.9 55.5 LT 244.7 55.5 LT 245.5 55.5 LT 246.2 55.5 LT 247.0 55.5 LT 247.8 58.0 LT 248.6 58.0 LT 249.3 58.0 LT 250.1 60.6 LT 250.9 60.6 LT 251.7 60.6 LT 252.5 60.6 LT 253.2 60.6 LT 254.0 60.6 LT 254.8 60.6 LT 255.6 60.6 LT 256.3 58.0 LT 257.1 58.0 LT 257.9 55.5 LT 258.7 55.5 LT 259.4 55.5 LT 260.2 55.5 LT 261.0 55.5 LT 261.8 55.5 LT 262.5 58.0 LT 263.3 58.0 LT 264.1 58.0 LT 264.9 58.0 LT 265.6 58.0 LT 266.4 60.6 LT 267.2 60.6 LT 268.0 58.0 LT 268.7 58.0 LT 269.5 58.0 LT 270.3 58.0 LT 271.1 58.0 LT 271.9 58.0 LT 272.6 58.0 LT 273.4 58.0 LT 274.2 58.0 LT 275.0 60.6 LT 275.7 60.6 LT 276.5 60.6 LT stroke 276.5 60.6 MT 277.3 60.6 LT 278.1 58.0 LT 278.8 58.0 LT 279.6 58.0 LT 280.4 55.5 LT 281.2 55.5 LT 281.9 55.5 LT 282.7 55.5 LT 283.5 55.5 LT 284.3 55.5 LT 285.0 58.0 LT 285.8 58.0 LT 286.6 58.0 LT 287.4 60.6 LT 288.1 60.6 LT 288.9 60.6 LT 289.7 60.6 LT 290.5 60.6 LT 291.3 60.6 LT 292.0 58.0 LT 292.8 58.0 LT 293.6 58.0 LT 294.4 58.0 LT 295.1 58.0 LT 295.9 58.0 LT 296.7 58.0 LT 297.5 55.5 LT 298.2 55.5 LT 299.0 55.5 LT 299.8 58.0 LT 300.6 58.0 LT 301.3 58.0 LT 302.1 58.0 LT 302.9 58.0 LT 303.7 58.0 LT 304.4 58.0 LT 305.2 58.0 LT 306.0 58.0 LT 306.8 58.0 LT 307.5 58.0 LT 308.3 58.0 LT 309.1 58.0 LT 309.9 58.0 LT 310.7 58.0 LT 311.4 58.0 LT 312.2 60.6 LT 313.0 60.6 LT 313.8 60.6 LT 314.5 60.6 LT 315.3 60.6 LT 316.1 58.0 LT stroke 316.1 58.0 MT 316.9 58.0 LT 317.6 55.5 LT 318.4 55.5 LT 319.2 55.5 LT 320.0 55.5 LT 320.7 55.5 LT 321.5 55.5 LT 322.3 55.5 LT 323.1 58.0 LT 323.8 58.0 LT 324.6 60.6 LT 325.4 60.6 LT 326.2 60.6 LT 326.9 60.6 LT 327.7 60.6 LT 328.5 58.0 LT 329.3 58.0 LT 330.1 58.0 LT 330.8 58.0 LT 331.6 58.0 LT 332.4 58.0 LT 333.2 58.0 LT 333.9 58.0 LT 334.7 58.0 LT 335.5 58.0 LT 336.3 58.0 LT 337.0 58.0 LT 337.8 58.0 LT 338.6 58.0 LT 339.4 58.0 LT 340.1 55.5 LT 340.9 55.5 LT 341.7 55.5 LT 342.5 58.0 LT 343.2 58.0 LT 344.0 58.0 LT 344.8 58.0 LT 345.6 58.0 LT 346.3 58.0 LT 347.1 58.0 LT 347.9 58.0 LT 348.7 58.0 LT 349.5 60.6 LT 350.2 60.6 LT stroke 1.000000 setlinewidth [] 0 setdash 39.8 27.6 1.0000 SNone 40.6 27.6 1.0000 SNone 41.4 27.6 1.0000 SNone 42.2 27.6 1.0000 SNone 42.9 27.6 1.0000 SNone 43.7 27.6 1.0000 SNone 44.5 27.6 1.0000 SNone 45.3 27.6 1.0000 SNone 46.0 27.6 1.0000 SNone 46.8 27.6 1.0000 SNone 47.6 27.6 1.0000 SNone 48.4 27.6 1.0000 SNone 49.1 27.6 1.0000 SNone 49.9 27.6 1.0000 SNone 50.7 27.6 1.0000 SNone 51.5 108.8 1.0000 SNone 52.2 103.8 1.0000 SNone 53.0 98.7 1.0000 SNone 53.8 96.1 1.0000 SNone 54.6 93.6 1.0000 SNone 55.3 88.5 1.0000 SNone 56.1 86.0 1.0000 SNone 56.9 83.4 1.0000 SNone 57.7 80.9 1.0000 SNone 58.5 78.4 1.0000 SNone 59.2 27.6 1.0000 SNone 60.0 27.6 1.0000 SNone 60.8 27.6 1.0000 SNone 61.6 27.6 1.0000 SNone 62.3 27.6 1.0000 SNone 63.1 27.6 1.0000 SNone 63.9 68.2 1.0000 SNone 64.7 65.7 1.0000 SNone 65.4 65.7 1.0000 SNone 66.2 63.1 1.0000 SNone 67.0 63.1 1.0000 SNone 67.8 63.1 1.0000 SNone 68.5 63.1 1.0000 SNone 69.3 60.6 1.0000 SNone 70.1 60.6 1.0000 SNone 70.9 60.6 1.0000 SNone 71.6 58.0 1.0000 SNone 72.4 58.0 1.0000 SNone 73.2 55.5 1.0000 SNone 74.0 58.0 1.0000 SNone 74.7 55.5 1.0000 SNone 75.5 55.5 1.0000 SNone 76.3 80.9 1.0000 SNone 77.1 80.9 1.0000 SNone 77.9 78.4 1.0000 SNone 78.6 78.4 1.0000 SNone 79.4 53.0 1.0000 SNone 80.2 53.0 1.0000 SNone 81.0 50.4 1.0000 SNone 81.7 53.0 1.0000 SNone 82.5 50.4 1.0000 SNone 83.3 50.4 1.0000 SNone 84.1 50.4 1.0000 SNone 84.8 47.9 1.0000 SNone 85.6 50.4 1.0000 SNone 86.4 47.9 1.0000 SNone 87.2 50.4 1.0000 SNone 87.9 47.9 1.0000 SNone 88.7 68.2 1.0000 SNone 89.5 68.2 1.0000 SNone 90.3 65.7 1.0000 SNone 91.0 68.2 1.0000 SNone 91.8 65.7 1.0000 SNone 92.6 65.7 1.0000 SNone 93.4 65.7 1.0000 SNone 94.1 65.7 1.0000 SNone 94.9 63.1 1.0000 SNone 95.7 63.1 1.0000 SNone 96.5 63.1 1.0000 SNone 97.3 63.1 1.0000 SNone 98.0 60.6 1.0000 SNone 98.8 45.3 1.0000 SNone 99.6 42.8 1.0000 SNone 100.4 45.3 1.0000 SNone 101.1 60.6 1.0000 SNone 101.9 58.0 1.0000 SNone 102.7 60.6 1.0000 SNone 103.5 60.6 1.0000 SNone 104.2 58.0 1.0000 SNone 105.0 58.0 1.0000 SNone 105.8 58.0 1.0000 SNone 106.6 58.0 1.0000 SNone 107.3 55.5 1.0000 SNone 108.1 55.5 1.0000 SNone 108.9 58.0 1.0000 SNone 109.7 55.5 1.0000 SNone 110.4 55.5 1.0000 SNone 111.2 55.5 1.0000 SNone 112.0 55.5 1.0000 SNone 112.8 55.5 1.0000 SNone 113.5 68.2 1.0000 SNone 114.3 65.7 1.0000 SNone 115.1 68.2 1.0000 SNone 115.9 68.2 1.0000 SNone 116.7 65.7 1.0000 SNone 117.4 65.7 1.0000 SNone 118.2 65.7 1.0000 SNone 119.0 53.0 1.0000 SNone 119.8 53.0 1.0000 SNone 120.5 53.0 1.0000 SNone 121.3 50.4 1.0000 SNone 122.1 53.0 1.0000 SNone 122.9 53.0 1.0000 SNone 123.6 50.4 1.0000 SNone 124.4 50.4 1.0000 SNone 125.2 50.4 1.0000 SNone 126.0 63.1 1.0000 SNone 126.7 63.1 1.0000 SNone 127.5 60.6 1.0000 SNone 128.3 60.6 1.0000 SNone 129.1 60.6 1.0000 SNone 129.8 63.1 1.0000 SNone 130.6 60.6 1.0000 SNone 131.4 60.6 1.0000 SNone 132.2 60.6 1.0000 SNone 132.9 58.0 1.0000 SNone 133.7 60.6 1.0000 SNone 134.5 60.6 1.0000 SNone 135.3 60.6 1.0000 SNone 136.1 58.0 1.0000 SNone 136.8 58.0 1.0000 SNone 137.6 58.0 1.0000 SNone 138.4 58.0 1.0000 SNone 139.2 58.0 1.0000 SNone 139.9 58.0 1.0000 SNone 140.7 58.0 1.0000 SNone 141.5 55.5 1.0000 SNone 142.3 55.5 1.0000 SNone 143.0 58.0 1.0000 SNone 143.8 58.0 1.0000 SNone 144.6 55.5 1.0000 SNone 145.4 55.5 1.0000 SNone 146.1 55.5 1.0000 SNone 146.9 55.5 1.0000 SNone 147.7 55.5 1.0000 SNone 148.5 55.5 1.0000 SNone 149.2 55.5 1.0000 SNone 150.0 55.5 1.0000 SNone 150.8 63.1 1.0000 SNone 151.6 63.1 1.0000 SNone 152.3 63.1 1.0000 SNone 153.1 63.1 1.0000 SNone 153.9 63.1 1.0000 SNone 154.7 63.1 1.0000 SNone 155.5 63.1 1.0000 SNone 156.2 60.6 1.0000 SNone 157.0 60.6 1.0000 SNone 157.8 60.6 1.0000 SNone 158.6 53.0 1.0000 SNone 159.3 53.0 1.0000 SNone 160.1 53.0 1.0000 SNone 160.9 53.0 1.0000 SNone 161.7 53.0 1.0000 SNone 162.4 53.0 1.0000 SNone 163.2 60.6 1.0000 SNone 164.0 58.0 1.0000 SNone 164.8 58.0 1.0000 SNone 165.5 60.6 1.0000 SNone 166.3 60.6 1.0000 SNone 167.1 60.6 1.0000 SNone 167.9 58.0 1.0000 SNone 168.6 58.0 1.0000 SNone 169.4 58.0 1.0000 SNone 170.2 58.0 1.0000 SNone 171.0 58.0 1.0000 SNone 171.7 58.0 1.0000 SNone 172.5 58.0 1.0000 SNone 173.3 58.0 1.0000 SNone 174.1 58.0 1.0000 SNone 174.9 58.0 1.0000 SNone 175.6 63.1 1.0000 SNone 176.4 63.1 1.0000 SNone 177.2 63.1 1.0000 SNone 178.0 63.1 1.0000 SNone 178.7 58.0 1.0000 SNone 179.5 55.5 1.0000 SNone 180.3 55.5 1.0000 SNone 181.1 55.5 1.0000 SNone 181.8 55.5 1.0000 SNone 182.6 55.5 1.0000 SNone 183.4 55.5 1.0000 SNone 184.2 55.5 1.0000 SNone 184.9 55.5 1.0000 SNone 185.7 55.5 1.0000 SNone 186.5 55.5 1.0000 SNone 187.3 55.5 1.0000 SNone 188.0 60.6 1.0000 SNone 188.8 60.6 1.0000 SNone 189.6 60.6 1.0000 SNone 190.4 60.6 1.0000 SNone 191.1 60.6 1.0000 SNone 191.9 60.6 1.0000 SNone 192.7 60.6 1.0000 SNone 193.5 60.6 1.0000 SNone 194.3 60.6 1.0000 SNone 195.0 60.6 1.0000 SNone 195.8 58.0 1.0000 SNone 196.6 58.0 1.0000 SNone 197.4 58.0 1.0000 SNone 198.1 53.0 1.0000 SNone 198.9 53.0 1.0000 SNone 199.7 53.0 1.0000 SNone 200.5 58.0 1.0000 SNone 201.2 58.0 1.0000 SNone 202.0 60.6 1.0000 SNone 202.8 58.0 1.0000 SNone 203.6 58.0 1.0000 SNone 204.3 58.0 1.0000 SNone 205.1 58.0 1.0000 SNone 205.9 58.0 1.0000 SNone 206.7 58.0 1.0000 SNone 207.4 58.0 1.0000 SNone 208.2 55.5 1.0000 SNone 209.0 55.5 1.0000 SNone 209.8 58.0 1.0000 SNone 210.5 58.0 1.0000 SNone 211.3 58.0 1.0000 SNone 212.1 58.0 1.0000 SNone 212.9 63.1 1.0000 SNone 213.7 63.1 1.0000 SNone 214.4 60.6 1.0000 SNone 215.2 60.6 1.0000 SNone 216.0 60.6 1.0000 SNone 216.8 60.6 1.0000 SNone 217.5 60.6 1.0000 SNone 218.3 55.5 1.0000 SNone 219.1 55.5 1.0000 SNone 219.9 55.5 1.0000 SNone 220.6 55.5 1.0000 SNone 221.4 55.5 1.0000 SNone 222.2 55.5 1.0000 SNone 223.0 55.5 1.0000 SNone 223.7 55.5 1.0000 SNone 224.5 55.5 1.0000 SNone 225.3 60.6 1.0000 SNone 226.1 58.0 1.0000 SNone 226.8 58.0 1.0000 SNone 227.6 58.0 1.0000 SNone 228.4 60.6 1.0000 SNone 229.2 60.6 1.0000 SNone 229.9 60.6 1.0000 SNone 230.7 60.6 1.0000 SNone 231.5 60.6 1.0000 SNone 232.3 58.0 1.0000 SNone 233.1 58.0 1.0000 SNone 233.8 58.0 1.0000 SNone 234.6 58.0 1.0000 SNone 235.4 58.0 1.0000 SNone 236.2 58.0 1.0000 SNone 236.9 58.0 1.0000 SNone 237.7 58.0 1.0000 SNone 238.5 58.0 1.0000 SNone 239.3 58.0 1.0000 SNone 240.0 58.0 1.0000 SNone 240.8 58.0 1.0000 SNone 241.6 58.0 1.0000 SNone 242.4 58.0 1.0000 SNone 243.1 58.0 1.0000 SNone 243.9 55.5 1.0000 SNone 244.7 55.5 1.0000 SNone 245.5 55.5 1.0000 SNone 246.2 55.5 1.0000 SNone 247.0 55.5 1.0000 SNone 247.8 58.0 1.0000 SNone 248.6 58.0 1.0000 SNone 249.3 58.0 1.0000 SNone 250.1 60.6 1.0000 SNone 250.9 60.6 1.0000 SNone 251.7 60.6 1.0000 SNone 252.5 60.6 1.0000 SNone 253.2 60.6 1.0000 SNone 254.0 60.6 1.0000 SNone 254.8 60.6 1.0000 SNone 255.6 60.6 1.0000 SNone 256.3 58.0 1.0000 SNone 257.1 58.0 1.0000 SNone 257.9 55.5 1.0000 SNone 258.7 55.5 1.0000 SNone 259.4 55.5 1.0000 SNone 260.2 55.5 1.0000 SNone 261.0 55.5 1.0000 SNone 261.8 55.5 1.0000 SNone 262.5 58.0 1.0000 SNone 263.3 58.0 1.0000 SNone 264.1 58.0 1.0000 SNone 264.9 58.0 1.0000 SNone 265.6 58.0 1.0000 SNone 266.4 60.6 1.0000 SNone 267.2 60.6 1.0000 SNone 268.0 58.0 1.0000 SNone 268.7 58.0 1.0000 SNone 269.5 58.0 1.0000 SNone 270.3 58.0 1.0000 SNone 271.1 58.0 1.0000 SNone 271.9 58.0 1.0000 SNone 272.6 58.0 1.0000 SNone 273.4 58.0 1.0000 SNone 274.2 58.0 1.0000 SNone 275.0 60.6 1.0000 SNone 275.7 60.6 1.0000 SNone 276.5 60.6 1.0000 SNone 277.3 60.6 1.0000 SNone 278.1 58.0 1.0000 SNone 278.8 58.0 1.0000 SNone 279.6 58.0 1.0000 SNone 280.4 55.5 1.0000 SNone 281.2 55.5 1.0000 SNone 281.9 55.5 1.0000 SNone 282.7 55.5 1.0000 SNone 283.5 55.5 1.0000 SNone 284.3 55.5 1.0000 SNone 285.0 58.0 1.0000 SNone 285.8 58.0 1.0000 SNone 286.6 58.0 1.0000 SNone 287.4 60.6 1.0000 SNone 288.1 60.6 1.0000 SNone 288.9 60.6 1.0000 SNone 289.7 60.6 1.0000 SNone 290.5 60.6 1.0000 SNone 291.3 60.6 1.0000 SNone 292.0 58.0 1.0000 SNone 292.8 58.0 1.0000 SNone 293.6 58.0 1.0000 SNone 294.4 58.0 1.0000 SNone 295.1 58.0 1.0000 SNone 295.9 58.0 1.0000 SNone 296.7 58.0 1.0000 SNone 297.5 55.5 1.0000 SNone 298.2 55.5 1.0000 SNone 299.0 55.5 1.0000 SNone 299.8 58.0 1.0000 SNone 300.6 58.0 1.0000 SNone 301.3 58.0 1.0000 SNone 302.1 58.0 1.0000 SNone 302.9 58.0 1.0000 SNone 303.7 58.0 1.0000 SNone 304.4 58.0 1.0000 SNone 305.2 58.0 1.0000 SNone 306.0 58.0 1.0000 SNone 306.8 58.0 1.0000 SNone 307.5 58.0 1.0000 SNone 308.3 58.0 1.0000 SNone 309.1 58.0 1.0000 SNone 309.9 58.0 1.0000 SNone 310.7 58.0 1.0000 SNone 311.4 58.0 1.0000 SNone 312.2 60.6 1.0000 SNone 313.0 60.6 1.0000 SNone 313.8 60.6 1.0000 SNone 314.5 60.6 1.0000 SNone 315.3 60.6 1.0000 SNone 316.1 58.0 1.0000 SNone 316.9 58.0 1.0000 SNone 317.6 55.5 1.0000 SNone 318.4 55.5 1.0000 SNone 319.2 55.5 1.0000 SNone 320.0 55.5 1.0000 SNone 320.7 55.5 1.0000 SNone 321.5 55.5 1.0000 SNone 322.3 55.5 1.0000 SNone 323.1 58.0 1.0000 SNone 323.8 58.0 1.0000 SNone 324.6 60.6 1.0000 SNone 325.4 60.6 1.0000 SNone 326.2 60.6 1.0000 SNone 326.9 60.6 1.0000 SNone 327.7 60.6 1.0000 SNone 328.5 58.0 1.0000 SNone 329.3 58.0 1.0000 SNone 330.1 58.0 1.0000 SNone 330.8 58.0 1.0000 SNone 331.6 58.0 1.0000 SNone 332.4 58.0 1.0000 SNone 333.2 58.0 1.0000 SNone 333.9 58.0 1.0000 SNone 334.7 58.0 1.0000 SNone 335.5 58.0 1.0000 SNone 336.3 58.0 1.0000 SNone 337.0 58.0 1.0000 SNone 337.8 58.0 1.0000 SNone 338.6 58.0 1.0000 SNone 339.4 58.0 1.0000 SNone 340.1 55.5 1.0000 SNone 340.9 55.5 1.0000 SNone 341.7 55.5 1.0000 SNone 342.5 58.0 1.0000 SNone 343.2 58.0 1.0000 SNone 344.0 58.0 1.0000 SNone 344.8 58.0 1.0000 SNone 345.6 58.0 1.0000 SNone 346.3 58.0 1.0000 SNone 347.1 58.0 1.0000 SNone 347.9 58.0 1.0000 SNone 348.7 58.0 1.0000 SNone 349.5 60.6 1.0000 SNone 350.2 60.6 1.0000 SNone 39.1 27.6 MT 349.5 27.6 LT stroke 77.9 27.6 MT 77.9 31.2 LT stroke 116.7 27.6 MT 116.7 31.2 LT stroke 155.5 27.6 MT 155.5 31.2 LT stroke 194.3 27.6 MT 194.3 31.2 LT stroke 233.1 27.6 MT 233.1 31.2 LT stroke 271.9 27.6 MT 271.9 31.2 LT stroke 310.7 27.6 MT 310.7 31.2 LT stroke 349.5 27.6 MT 349.5 31.2 LT stroke /Helvetica findfont 12 scalefont setfont (Files per directory \(Nd\)) 227.7 0.0 0 DoLText (50) 71.3 12.0 0 DoLText (100) 106.8 12.0 0 DoLText (150) 145.6 12.0 0 DoLText (200) 184.4 12.0 0 DoLText (250) 223.2 12.0 0 DoLText (300) 262.0 12.0 0 DoLText (350) 300.8 12.0 0 DoLText (400) 339.6 12.0 0 DoLText 39.1 27.6 MT 39.1 281.6 LT stroke 39.1 53.0 MT 42.7 53.0 LT stroke 39.1 78.4 MT 42.7 78.4 LT stroke 39.1 103.8 MT 42.7 103.8 LT stroke 39.1 129.2 MT 42.7 129.2 LT stroke 39.1 154.6 MT 42.7 154.6 LT stroke 39.1 180.0 MT 42.7 180.0 LT stroke 39.1 205.4 MT 42.7 205.4 LT stroke 39.1 230.8 MT 42.7 230.8 LT stroke 39.1 256.2 MT 42.7 256.2 LT stroke 39.1 281.6 MT 42.7 281.6 LT stroke (Bytes per file) 12.0 212.4 90 DoLText (10) 22.2 47.0 0 DoLText (20) 22.2 72.4 0 DoLText (30) 22.2 97.8 0 DoLText (40) 22.2 123.2 0 DoLText (50) 22.2 148.6 0 DoLText (60) 22.2 174.0 0 DoLText (70) 22.2 199.4 0 DoLText (80) 22.2 224.8 0 DoLText (90) 22.2 250.2 0 DoLText (100) 15.6 275.6 0 DoLText (0) 28.9 12.0 0 DoLText /Helvetica findfont 10 scalefont setfont [] 0 setdash 1.000000 setlinewidth 130.2 208.0 MT 157.2 208.0 LT stroke 130.2 208.0 0.6500 SNone 157.2 208.0 0.6500 SNone (DOSFS Directory Overhead per File) 170.7 205.0 0 DoLText [5 4] 0 setdash 1.000000 setlinewidth 130.2 195.0 MT 157.2 195.0 LT stroke 130.2 195.0 0.6500 SNone 157.2 195.0 0.6500 SNone (FFS Directory Overhead per File) 170.7 192.0 0 DoLText [2 3] 0 setdash 1.000000 setlinewidth 130.2 182.0 MT 157.2 182.0 LT stroke 130.2 182.0 0.6500 SNone 157.2 182.0 0.6500 SNone (Difference of above \(DOSFS - FFS\)) 170.7 179.0 0 DoLText [] 0 setdash 1.000000 setlinewidth 116.7 171.9 MT 116.7 218.1 LT 334.1 218.1 LT 334.1 171.9 LT 116.7 171.9 LT stroke showpage restore %%Trailer restore %%DocumentFonts: Helvetica %%EndDocument GE /Times-Bold SF 21965 37709 MT (Figure 4:)SH /Times-Roman SF 26381 XM (Costs Of Directory Entries)SH 7120 41293 MT (Note that the block allocation algorithms used in the) 30 W( two file systems have no effects on disk utilization, but they)31 W 6120 42670 MT (do affect performance as indicated in Section 7.)SH 14 /Times-Bold AF 6120 46488 MT (7. Performance Evaluation)SH 10 /Times-Roman AF 7120 47865 MT (John Ousterhout published, as part of the Sprite OS sources, a set of file system tests) 161 W( [11],) SH( which we use to)160 W 6120 49242 MT (summarize the performance) 14 W( of our file system at the micro-benchmark level. The)15 W /Times-Bold SF 39305 XM (open)SH /Times-Roman SF 41626 XM (test opens \050and immediately)15 W 6120 50619 MT (closes\051 the same pathname a large number of times, and reports) 144 W( the average time per iteration. The)143 W /Times-Bold SF 48639 XM (crtdel)SH /Times-Roman SF 51531 XM (test)SH 6120 51996 MT (repeatedly creates, writes to, and deletes a file. The)58 W /Times-Bold SF 27666 XM (read)SH /Times-Roman SF 29918 XM (test reads from stdin in 16 KB sizes, until the end) 58 W( of the)59 W 6120 53373 MT (file. The file is then reset and the cycle is repeated at least 100) 3 W( times, for timing purposes. Similarly)2 W /Times-Bold SF 46529 XM (write)SH /Times-Roman SF 49002 XM (writes the)2 W 6120 54750 MT (given number of KB to stdout, in no more than 16 KB sizes. This is also repeated at least 100 times.)SH 7120 57229 MT (Most of the well-known) 61 W( macro-benchmarks are UNIX-specific and do not have an identical implementation and)62 W 6120 58606 MT (meaning under MS-DOS and UNIX. This is true for the Andrew benchmark) 28 W( [4],) SH( for which we do not have a native)28 W 6120 59983 MT (MS-DOS version. Similarly for) 27 W( the unpacking of the tar file described in Section 6; we can only compare the times)28 W 6120 61360 MT (to do the unpacking between FFS and DosFs. The Iostone test is a synthetic benchmark that models a timesharing)54 W 6120 62737 MT (load. The) 274 W( test was written by Arvin Park and Jeff Becker at UC Davis, and it is based on) 12 W( the traces John Ousterhout)13 W 6120 64114 MT (collected on a general-purpose machine at UC Berkeley) 48 W( [10].) SH( For) 346 W( MS-DOS, we) 48 W( report on typical operations a user)47 W 6120 65491 MT (would perform on a large number of files, such as copying or deleting file trees.)SH 7120 67970 MT (The test machine is a Gateway 2000 486/33C running Mach 3.0 \050MK83+UX42\051, with) 192 W( a 33 Mhz Intel i486)193 W 6120 69347 MT (processor, 16 MB of main memory and a) 62 W( 400 MB Maxtor SCSI disk interfaced via an Adaptec 1540c SCSI HBA.)61 W 6120 70724 MT (Effective memory bandwidth is about 10) 49 W( MB/sec. The disk is split into a 60 MB initial MS-DOS partition and the)50 W ES %%Page: 15 16 BS 0 SI 10 /Times-Roman AF 54080 4286 MT (15)SH 8280 7886 MT (remaining disk space for UNIX partitions. Both the MS-DOS and FFS partitions are over two years old. The)152 W 8280 9263 MT (MS-DOS partition is about 40% full, the cluster size is 2 KB. The FFS) 55 W( partition is about 60% full, fragsize is 512)56 W 8280 10640 MT (bytes, block size is) 69 W( 4 KB, rotdelay is 4 ms, maxcontig is 1, there are 62 cylinder groups. Using fresh file systems)68 W 8280 12017 MT (would lead to a more repeatable experiment, but using old) 132 W( file systems shows what happens to the performance)133 W 8280 13394 MT (numbers when the file systems age. The discrepancy between our) 67 W( results and the results presented in) 66 W( [7]) SH( seems to)66 W 8280 14771 MT (indicate that DosFs has a better degradation than FFS.)SH 46800 50 8280 16076 UL 8 /Times-Italic AF 8280 17190 MT (Test)SH 19980 XM (Native MS-DOS)SH 31680 XM (FFS)SH 43380 XM (DosFs)SH 1333 50 8280 17390 UL 2088 50 19980 17390 UL 2888 50 22268 17390 UL 1378 50 31680 17390 UL 2089 50 43380 17390 UL /Times-Bold SF 8280 18576 MT (open "foo")SH 19980 XM (0.50 ms)SH 31680 XM (0.75 ms)SH 43380 XM (0.75 ms)SH 8280 19962 MT (open "a/b/foo")SH 19980 XM (0.82 ms)SH 31680 XM (0.82 ms)SH 43380 XM (0.82 ms)SH 8280 21348 MT (open longpath)SH 19980 XM (1.16 ms)SH 31680 XM (0.95 ms)SH 43380 XM (0.95 ms)SH 8280 22734 MT (crtdel 0 KB)SH 19980 XM (32 ms)SH 31680 XM (3 ms)SH 43380 XM (3 ms)SH 8280 24120 MT (crtdel 10 KB)SH 19980 XM (521 ms)SH 31680 XM (36 ms)SH 43380 XM (20 ms)SH 8280 25506 MT (crtdel 100 KB)SH 19980 XM (3671 ms)SH 31680 XM (107 ms)SH 43380 XM (87 ms)SH 8280 26892 MT (read 1 KB)SH 19980 XM (0.1 MB/s)SH 31680 XM (1.1 MB/s)SH 43380 XM (1.1 MB/s)SH 8280 28278 MT (read 8 KB)SH 19980 XM (0.5 MB/s)SH 31680 XM (2.2 MB/s)SH 43380 XM (2.5 MB/s)SH 8280 29664 MT (read 100 KB)SH 19980 XM (1.2 MB/s)SH 31680 XM (3.0 MB/s)SH 43380 XM (3.3 MB/s)SH 8280 31050 MT (write 1 KB)SH 19980 XM (0.1 MB/s)SH 31680 XM (1.3 MB/s)SH 43380 XM (1.3 MB/s)SH 8280 32436 MT (write 8 KB)SH 19980 XM (0.5 MB/s)SH 31680 XM (3.7 MB/s)SH 43380 XM (3.7 MB/s)SH 8280 33822 MT (write 100 KB)SH 19980 XM (0.5 MB/s)SH 31680 XM (5.8 MB/s)SH 43380 XM (7.4 MB/s)SH 46800 50 8280 35408 UL 10 SS 20971 36746 MT (Table 3:)SH /Times-Roman SF 24999 XM (John Ousterhout's Basic File System Tests.)SH 9280 39225 MT (The results of the micro-benchmarks are illustrated in Table 3. DosFs is faster than FFS) 11 W( on cached read and write)12 W 8280 40602 MT (operations, but this is simply the result of the way data is moved between the) 99 W( UNIX server and the user process.)98 W 8280 41979 MT (Mach's Virtual Memory works best on large amounts of data, and in the case of DosFs it can move) 10 W( the entire 16 KB)11 W 8280 43356 MT (segment by remapping it at once. In the FFS case, data is split across 4 buffers and disjoint virtual addresses.)SH 9280 45835 MT (The lack) 32 W( of caching and/or prefetching in MS-DOS makes it run slower, on average, than the UNIX file systems.)31 W 8280 47212 MT (We modified the native MS-DOS)41 W /Times-Italic SF 22178 XM (read)SH /Times-Roman SF 24303 XM (test to read different amounts of data with various blocking factors; the best)42 W 8280 48589 MT (bandwidth was 1.2 MB/sec when reading a 100) 20 W( KB file in 16 KB blocks. In order to explain the results of the)19 W /Times-Bold SF 53024 XM (open)SH /Times-Roman SF 8280 49966 MT (test we must assume that native MS-DOS is doing some caching anyway. This was confirmed with the Mach) 73 W( 3.0)74 W 8280 51343 MT (MS-DOS emulator.)SH 9280 53822 MT (To evaluate the performance on uncached operations we use) 21 W( the)20 W /Times-Bold SF 35369 XM (read)SH /Times-Roman SF 37583 XM (and)SH /Times-Bold SF 39297 XM (write)SH /Times-Roman SF 41788 XM (tests above, on much larger files.)20 W 8280 55199 MT (The tests include both) 163 W( networked and local cases. Read and write performance of DosFs over NFS are nearly)164 W 8280 56576 MT (identical to the FFS performance, as indicated in Table 4. The client was a DECStation 5000/200, the server was) 39 W( a)38 W 8280 57953 MT (DEC Alpha workstation, both running Mach 3.0. The user-to-user bandwidth \050measured by)59 W /Times-Bold SF 46097 XM (ttcp)SH /Times-Roman SF (\051 between the two)60 W 8280 59330 MT (machines over a UDP transport was) 87 W( 860 KB/sec. Both the NFS and the networking code in the UNIX server are)86 W 8280 60707 MT (old, and these numbers show it.)SH 46800 50 8280 62012 UL 8 /Times-Italic AF 8280 63126 MT (Test)SH 19980 XM (FFS)SH 31680 XM (DosFs)SH 43380 XM (MS-DOS Native)SH 1333 50 8280 63326 UL 1378 50 19980 63326 UL 2089 50 31680 63326 UL 2888 50 43380 63326 UL 2088 50 46468 63326 UL /Times-Bold SF 8280 64512 MT (Uncached read 5MB)SH 19980 XM (170)SH 31680 XM (850)SH 43380 XM (1200)SH 8280 65898 MT (Uncached write 5MB)SH 19980 XM (178)SH 31680 XM (382)SH 43380 XM (624)SH 8280 67284 MT (NFS read 5MB)SH 19980 XM (377)SH 31680 XM (379)SH 43380 XM (n/a)SH 8280 68670 MT (NFS write 5MB)SH 19980 XM (749)SH 31680 XM (749)SH 43380 XM (n/a)SH 46800 50 8280 70256 UL 10 SS 15891 71594 MT (Table 4:)SH /Times-Roman SF 19919 XM (Uncached Data Transfers, For Local Disk And Over NFS, In KB/sec)SH ES %%Page: 16 17 BS 0 SI 10 /Times-Roman AF 6120 4286 MT (16)SH 7120 7886 MT (The UNIX server has disabled mapped files, therefore we) 224 W( incur data movement overheads that make local)225 W 6120 9263 MT (performance lower than) 73 W( in a monolithic kernel. To quantify the maximum disk performance, we wrote a program)72 W 6120 10640 MT (that accesses the disk directly through the Mach 3.0 kernel. This is the) 149 W( closest equivalent of the raw character)150 W 6120 12017 MT (device for traditional UNIX. This program uses multiple threads to) 50 W( guarantee that a request for the next sequential)49 W 6120 13394 MT (block is always ready in the disk driver queue by the time a request completes. This was verified with a SCSI) 53 W( bus)54 W 6120 14771 MT (analyzer. On) 340 W( the test machine this program obtains a 1.5 MB/sec read rate at a block size of 16) 45 W( KB. Higher block)44 W 8 SS 25752 15803 MT (1)SH 10 SS 6120 16148 MT (sizes obtain bandwidths in excess of 1.6 MB/sec)35 W 26152 XM (. By) 320 W( contrast, a dd\0501\051 of the) 35 W( raw device via the UNIX server only)36 W 6120 17525 MT (obtains 1.2 MB/sec, which indicates a 20% overhead in the UNIX emulation code along the I/O path.)SH 7120 20004 MT (In Table 4 we indicate the results of reading or writing a 5 MB file for each of the three file systems.) 35 W( The) 319 W( buffer)34 W 6120 21381 MT (cache size was set at 1.3) 79 W( MB and the file systems were unmounted between each of five test runs. We report the)80 W 6120 22758 MT (best results,) 77 W( but there is little variation even if the machine was running in multi-user mode on a regular Ethernet.)76 W 6120 24135 MT (Extra data copies make) 2 W( DosFs slower than MS-DOS. But the most remarkable result here is the five fold speedup of)3 W 6120 25512 MT (DosFs over FFS. This result can be) 119 W( explained in the same way as in) 118 W( [7]:) SH( DosFs) 486 W( performs I/Os on a file that is)118 W 6120 26889 MT (contiguous, whereas FFS allows for presumed rotational delays and interleaves) 78 W( blocks on the disk. Every track is)79 W 6120 28266 MT (only 1/4 utilized by FFS, losing most of the benefits of the track-level caching done by the) 57 W( disk. The speedup is a)56 W 6120 29643 MT (little higher than four because the FFS file system is not empty and occasionally FFS cannot) 137 W( allocate its blocks)138 W 6120 31020 MT (optimally. DosFs) 250 W( is still capable of reaching optimal allocation in its partition, despite the utilization.)SH 7120 33499 MT (We obtain another important result if we disable the large I/O optimizations,) 2 W( e.g. if we force DosFs to perform I/O)1 W 6120 34876 MT (at the 2 KB cluster size. The DosFs bandwidth becomes 480 KB/sec, almost three times higher) 105 W( than FFS which)106 W 6120 36253 MT (does I/O in 4 KB blocks. The disk compensates for the small access size by read-caching an entire track,) 114 W( but it)113 W 6120 37630 MT (cannot compensate for the extra) 2 W( seeks that FFS incurs. Adding track caches on the disk drives is quite common with)3 W 6120 39007 MT (SCSI disks.)SH 7120 41486 MT (Table 5 shows the results of our macro-benchmarks. The modified Andrew benchmark is commonly used to)139 W 6120 42863 MT (simulate the load of a programming environment. The test has five phases which mainly involve the) 129 W( creation of)130 W 6120 44240 MT (various directories \050phase I\051, copying of files \050phase II\051,) 4 W( doing many stat\0502\051 over the file tree \050phase III\051, sequentially)3 W 6120 45617 MT (scanning all files \050phase IV\051 and performing some compilations \050phase V\051.) 58 W( DosFs) 368 W( is faster than FFS in all phases,)59 W 6120 46994 MT (the larger gains are obtained in the phases that actually access file data, e.g. phases IV and V. Among all the tests we)4 W 6120 48371 MT (ran, this is the one with the least controlled execution) 197 W( environment. It uses scripts and system programs, for)198 W 6120 49748 MT (instance, which on the test machine are paged in from a different partition but on the same disk. The) 146 W( distance)145 W 6120 51125 MT (between the DosFs) 208 W( partition and the FFS partition from system data and code is not the same, and DosFs is)209 W 6120 52502 MT (penalized. To) 250 W( use this test effectively we would need a different test setup.)SH 7120 54981 MT (We report three cases for the Iostone test, in each one we used a different number of instances) 19 W( of the test, running)18 W 6120 56358 MT (in parallel directories. Each instance uses approximately 5 MB of disk space, to overflow the buffer cache. We)107 W 6120 57735 MT (selected this test to get a worse-case behavior from DosFs, because it invalidates the assumptions about a single-user)5 W 6120 59112 MT (load. When) 410 W( we) 80 W( checked the block allocations for the larger files we found them very scattered, as expected. But)81 W 6120 60489 MT (DosFs is still from 13% to 20% faster than 4.3 FFS when large I/O operations) 32 W( are enabled. If we disable large I/Os)31 W 6120 61866 MT (\050times in parentheses\051 DosFs becomes at most 20% slower than FFS.)SH 7120 64345 MT (We rewrote Iostone for native MS-DOS. MS-DOS is not a) 16 W( multi-tasking operating system, therefore we can only)17 W 6120 65722 MT (report the results from running a single instance of) 11 W( the test. The lack of caching has, as expected, a terrible effect on)10 W 6120 67099 MT (performance. Native,) 474 W( uncached MS-DOS is five times slower than DosFs. If we install the SmartDrive caching)113 W 10800 50 6120 70352 UL 6 SS 6920 71691 MT (1)SH 8 SS 7220 72000 MT (Poor cabling prevented us from making use of the faster SCSI synchronous transfer mode.)SH ES %%Page: 17 18 BS 0 SI 10 /Times-Roman AF 54080 4286 MT (17)SH 8280 7886 MT (software on MS-DOS the results \050time in parenthesis\051) 48 W( are better, but both FFS \05028%\051 and DosFs \05050%\051 outperform)47 W 8280 9263 MT (MS-DOS.)SH 46800 50 8280 10568 UL 8 /Times-Italic AF 8280 11682 MT (Test)SH 19980 XM (Native MS-DOS)SH 31680 XM (FFS)SH 43380 XM (DosFs)SH 1333 50 8280 11882 UL 2088 50 19980 11882 UL 2888 50 22268 11882 UL 1378 50 31680 11882 UL 2089 50 43380 11882 UL /Times-Bold SF 8280 13068 MT (Andrew - Phase I)SH 19980 XM (n/a)SH 31680 XM (0.5)SH 43380 XM (0.5)SH 8280 14454 MT (Andrew - Phase II)SH 19980 XM (n/a)SH 31680 XM (9)SH 43380 XM (8)SH 8280 15840 MT (Andrew - Phase III)SH 19980 XM (n/a)SH 31680 XM (8)SH 43380 XM (6)SH 8280 17226 MT (Andrew - Phase IV)SH 19980 XM (n/a)SH 31680 XM (12)SH 43380 XM (9)SH 8280 18612 MT (Andrew - Phase V)SH 19980 XM (n/a)SH 31680 XM (49)SH 43380 XM (40)SH 8280 19998 MT (Iostone-1)SH 19980 XM (996 \050300\051)SH 31680 XM (233)SH 43380 XM (195 \050287\051)SH 8280 21384 MT (Iostone-2)SH 19980 XM (n/a)SH 31680 XM (654)SH 43380 XM (550 \050700\051)SH 8280 22770 MT (Iostone-3)SH 19980 XM (n/a)SH 31680 XM (1089)SH 43380 XM (963 \050983\051)SH 8280 24156 MT (Unpack Tar File)SH 19980 XM (n/a)SH 31680 XM (187)SH 43380 XM (150)SH 8280 25542 MT (Copy Windows)SH 19980 XM (48)SH 31680 XM (76)SH 43380 XM (58)SH 8280 26928 MT (Delete Windows)SH 19980 XM (11)SH 31680 XM (5.4)SH 43380 XM (1.2)SH 46800 50 8280 28514 UL 10 SS 16862 29852 MT (Table 5:)SH /Times-Roman SF 20890 XM (Results For Selected Macro-Benchmarks, All Times In Seconds)SH 9280 32331 MT (We had expected DosFs to be as much as twice) 48 W( as slow as FFS in the Iostone test, due to the smaller I/O size \0502)49 W 8280 33708 MT (KB versus 4 KB\051. This is not) 40 W( the case, and the explanation is not immediate. The majority of the files used by the)39 W 8280 35085 MT (test are small, only 12 of the 404 work files are larger than 16 KB, 192 files are one sector or less,) 50 W( and 40 files are)51 W 8280 36462 MT (between 4 KB and 16 KB in size. Even the larger files are not totally fragmented.) 77 W( Two) 403 W( distinct phenomena help)76 W 8280 37839 MT (explain the results of this test. DosFs keeps the many little files close to) 161 W( each other, making better use of the)162 W 8280 39216 MT (disk-level cache, and when using the large buffers DosFs has a higher hit rate in main memory.)SH 9280 41695 MT (We measure the unpacking of a 1 MB tar file) 91 W( to a floppy disk for two reasons. It is an example of a common)90 W 8280 43072 MT (activity in UNIX, and the) 80 W( floppy is extremely slow when compared to a disk and does not have any read or write)81 W 8280 44449 MT (caches to help performance. Here the FFS optimizations show much gain,) 36 W( the difference versus DosFs is no longer)35 W 8280 45826 MT (a factor of two as in the) 174 W( uncached write test but a much smaller 25%. The test involves creating many files,)175 W 8280 47203 MT (therefore FFS pays the extra costs discussed in the)SH /Times-Bold SF 28694 XM (crtdel)SH /Times-Roman SF 31443 XM (test above.)SH 9280 49682 MT (For the last two tests we also have native MS-DOS times. The first one is a recursive copy of a large tree of)110 W 8280 51059 MT (MS-DOS system files, the Windows 3.1 directory. The tree is larger than the buffer cache, and the test was)199 W 8280 52436 MT (performed on a cold cache to guarantee pure uncached) 146 W( behavior. The results confirm the trend of the previous)145 W 8280 53813 MT (uncached micro-benchmarks, but the gap between systems is reduced.) 12 W( Deleting) 275 W( the Windows tree shows once again)13 W 8280 55190 MT (the advantage of delayed writes, as was partially indicated in the)SH /Times-Bold SF 34330 XM (crtdel)SH /Times-Roman SF 37079 XM (test.)SH 9280 57669 MT (There is one optimization we did not apply to) 106 W( DosFs which is instead present in FFS: caching of inodes. The)105 W 8280 59046 MT (UNIX server, for instance, uses an in-memory inode) 106 W( table of about 1,200 FFS inodes. Even of released \050usually)107 W 8280 60423 MT (because of name cache) 76 W( spills\051 FFS inodes stay around and can be reused without disk accesses. None of the tests)75 W 8280 61800 MT (above would be strongly affected by) 58 W( this optimization, but for instance the traversal of the whole file system name)59 W 8280 63177 MT (space probably would. Caching could be done at the Vnode layer, provided it benefits all file systems.)SH 12 /Times-Bold AF 8280 66861 MT (7.1. Performance in Mach 2.5)SH 10 /Times-Roman AF 9280 68238 MT (As previously noted, there is a certain amount of) 2 W( overhead along the I/O path in the Mach 3.0 Unix emulation. To)1 W 8280 69615 MT (quantify this overhead) 47 W( we have retrofitted the DosFs code into the monolithic Mach 2.5 kernel. Although the code)48 W 8280 70992 MT (is not very stable, we were able to repeat a number of the experiments above. The testing conditions) 3 W( are as indicated)2 W ES %%Page: 18 19 BS 0 SI 10 /Times-Roman AF 6120 4286 MT (18)SH 6120 7886 MT (above, the only difference is the Operating System kernel.)SH 7120 10365 MT (The first thing we) 63 W( noted was that the memory tests indicated a memory bandwidth twice as high as with the 3.0)64 W 6120 11742 MT (system. Cached) 482 W( operations, as indicated in Table) 116 W( 6, perform in excess of 21 MB/sec. We can only explain this)115 W 6120 13119 MT (assuming that the coding of the)36 W /Times-Italic SF 19113 XM (bcopy)SH /Times-Roman SF 21788 XM (routine for Mach 3.0 is inefficient when compared to the)37 W /Times-Italic SF 45070 XM (copyout)SH /Times-Roman SF 48523 XM (and)SH /Times-Italic SF 50254 XM (copyin)SH /Times-Roman SF 6120 14496 MT (routines in the Mach 2.5 kernel.)SH 7120 16975 MT (Another anomaly that must be explained is why) 51 W( FFS is so slow in the write test. There is an optimization in the)50 W 6120 18352 MT (4.3 FFS code that would issue a) 177 W( call to)178 W /Times-Italic SF 23438 XM (bawrite)SH /Times-Roman SF 26922 XM (when the user program writes sequential blocks of the file in)178 W 6120 19729 MT (multiples of the block size. This routine, contrary to)28 W /Times-Italic SF 27676 XM (bdwrite)SH /Times-Roman SF (, actually does issue) 28 W( the I/O operation but just does not)27 W 6120 21106 MT (wait for its completion. The idea behind this optimization is to reduce buffer) 26 W( usage, on the assumption that the user)27 W 6120 22483 MT (will not need to read back in the near future the file that) 20 W( was just created. Unfortunately, the test must be repeated a)19 W 6120 23860 MT (number of times to obtain a cumulative elapsed time that can be measured. Therefore on all) 95 W( subsequent runs the)96 W 6120 25237 MT (buffer cache will block the user program waiting for the asynchronous writes) 47 W( from the previous run. Therefore the)46 W 6120 26614 MT (test is basically run uncached.)SH 46800 50 6120 27919 UL 8 /Times-Italic AF 6120 29033 MT (Test)SH 21720 XM (FFS)SH 37320 XM (DosFs)SH 1333 50 6120 29233 UL 1378 50 21720 29233 UL 2089 50 37320 29233 UL /Times-Bold SF 6120 30419 MT (read 16 KB)SH 21720 XM (14.6 MB/s)SH 37320 XM (21.0 MB/s)SH 6120 31805 MT (write 16 KB)SH 21720 XM (0.5 MB/s)SH 37320 XM (19.3 MB/s)SH 6120 33191 MT (read 7 MB)SH 21720 XM (1.2 MB/s)SH 37320 XM (1.4 MB/s)SH 6120 34577 MT (Copy Windows)SH 21720 XM (118)SH 37320 XM (60)SH 6120 35963 MT (Delete Windows)SH 21720 XM (9.8)SH 37320 XM (2.7)SH 46800 50 6120 37549 UL 10 SS 20271 38887 MT (Table 6:)SH /Times-Roman SF 24299 XM (Mach 2.5 Test Results On Gateway.)SH 7120 41366 MT (The uncached I/O operations now work) 148 W( at least as well as or better than MS-DOS. Some of the results are,)149 W 6120 42743 MT (however, worse than the Mach 3.0 results. This is particularly acute in the copy/delete Windows test for FFS.) 46 W( We)340 W 6120 44120 MT (can explain this with the more optimized buffer cache code in the 3.0 system, which) 23 W( turns many synchronous writes)24 W 6120 45497 MT (into asynchronous writes.)SH 7120 47976 MT (Still DosFs does not reach the full disk bandwidth on the Gateway. To verify that) 33 W( this is a problem with the disk)32 W 6120 49353 MT (device driver we tried a different setup.) 52 W( We) 355 W( used a DECStation 5000/20 workstation, with a 20 Mhz MIPS R3000)53 W 6120 50730 MT (processor and an HP C2247 1.2) 133 W( GB SCSI disk drive and repeated once again the tests. This time the disk was)132 W 6120 52107 MT (dedicated exclusively) 174 W( to the tests \050system code was on a separate drive\051, and we optimized FFS for sequential)175 W 6120 53484 MT (allocation \050large maxcontig, rotdelay 0\051. The memory system performs at an apparent 29 MB/sec bandwidth, and)80 W 6120 54861 MT (the disk delivers 2.6 MB/sec in the multi-threaded read test.) 96 W( As) 443 W( can be noted in Table 7, on this machine DosFs)97 W 6120 56238 MT (does indeed reach the maximum disk read bandwidth. The SCSI disk driver) 97 W( used was the same as is used in the)96 W 6120 57615 MT (Mach 3.0 kernel \050for both Gateway and DECStations\051.)SH 7120 60094 MT (We do not have an explanation for) 133 W( why FFS is now faster than DosFs in the)134 W /Times-Bold SF 39866 XM (open)SH /Times-Roman SF 42306 XM (test, we just did not have)134 W 6120 61471 MT (enough time to investigate the anomaly. Some other tests also raise questions.) 107 W( For) 463 W( instance, why do the cached)106 W 6120 62848 MT (operations run so far from memory speed. Or why) 37 W( is there such a large drop in bandwidth for the 100 KB file read)38 W 6120 64225 MT (test, given that it fits in the buffer cache.)SH 7120 66704 MT (The Iostone tests reveals a close competition between the two file systems. This supports the explanations) 103 W( we)102 W 6120 68081 MT (gave before of why DosFs is so vastly superior) 159 W( to un-optimized FFS. It is interesting to note that, once again)160 W 6120 69458 MT (contrary to intuition, DosFs wins at higher levels of parallelism.) 76 W( We) 400 W( believe FFS spreads the many files involved)75 W 6120 70835 MT (across cylinder groups more widely than DosFs, resulting in more seeks.)SH ES %%Page: 19 20 BS 0 SI 10 /Times-Roman AF 54080 4286 MT (19)SH 46800 50 8280 7400 UL 8 /Times-Italic AF 8280 8514 MT (Test)SH 23880 XM (FFS)SH 39480 XM (DosFs)SH 1333 50 8280 8714 UL 1378 50 23880 8714 UL 2089 50 39480 8714 UL /Times-Bold SF 8280 9900 MT (open "foo")SH 23880 XM (0.20 ms)SH 39480 XM (0.23 ms)SH 8280 11286 MT (open "a/b/foo")SH 23880 XM (0.26 ms)SH 39480 XM (0.31 ms)SH 8280 12672 MT (open longpath)SH 23880 XM (0.39 ms)SH 39480 XM (0.43 ms)SH 8280 14058 MT (crtdel 0 KB)SH 23880 XM (3 ms)SH 39480 XM (3 ms)SH 8280 15444 MT (crtdel 10 KB)SH 23880 XM (69 ms)SH 39480 XM (60 ms)SH 8280 16830 MT (crtdel 100 KB)SH 23880 XM (257 ms)SH 39480 XM (173 ms)SH 8280 18216 MT (read 1 KB)SH 23880 XM (4.6 MB/s)SH 39480 XM (5.1 MB/s)SH 8280 19602 MT (read 8 KB)SH 23880 XM (17.5 MB/s)SH 39480 XM (17.5 MB/s)SH 8280 20988 MT (read 100 KB)SH 23880 XM (7.9 MB/s)SH 39480 XM (8.5 MB/s)SH 8280 22374 MT (read 7 MB)SH 23880 XM (2.0 MB/s)SH 39480 XM (2.6 MB/s)SH 8280 23760 MT (write 1 KB)SH 23880 XM (4.7 MB/s)SH 39480 XM (4.5 MB/s)SH 8280 25146 MT (write 8 KB)SH 23880 XM (16.9 MB/s)SH 39480 XM (17.1 MB/s)SH 8280 26532 MT (write 100 KB)SH 23880 XM (0.7 MB/s)SH 39480 XM (15.2 MB/s)SH 8280 27918 MT (Iostone-1)SH 23880 XM (103)SH 39480 XM (121 \050117\051)SH 8280 29304 MT (Iostone-2)SH 23880 XM (324)SH 39480 XM (278 \050264\051)SH 8280 30690 MT (Iostone-3)SH 23880 XM (563)SH 39480 XM (496 \050471\051)SH 8280 32076 MT (Andrew - Phase I)SH 23880 XM (0.5)SH 39480 XM (0.5)SH 8280 33462 MT (Andrew - Phase II)SH 23880 XM (7)SH 39480 XM (6)SH 8280 34848 MT (Andrew - Phase III)SH 23880 XM (5)SH 39480 XM (5)SH 8280 36234 MT (Andrew - Phase IV)SH 23880 XM (7)SH 39480 XM (7)SH 8280 37620 MT (Andrew - Phase V)SH 23880 XM (52)SH 39480 XM (52)SH 46800 50 8280 39206 UL 10 SS 16416 40544 MT (Table 7:)SH /Times-Roman SF 20444 XM (John Ousterhout's Basic File System Tests, Mach 2.5 DECStation)SH 9280 43023 MT (The modified Andrew benchmark indicates almost no difference between DosFs and optimized FFS.)SH 14 /Times-Bold AF 8280 46841 MT (8. Related Work)SH 10 /Times-Roman AF 9280 48218 MT (Sun provides the)191 W /Times-Italic SF 16825 XM (pcfs)SH /Times-Roman SF 18877 XM (file system in its UNIX offerings, which is) 191 W( a read/write Vnode based file system for)192 W 8280 49595 MT (MS-DOS disks, like our DosFs. Next has a similar file system in) 117 W( the NeXTStep product. Recently there was a)116 W 8280 50972 MT (posting on) 243 W( alt.sources of a "Filesystem Survival Kit" which provides the ISO and MS-DOS file systems for)244 W 8280 52349 MT (System-V UNIX systems. These file systems are strictly) 70 W( MS-DOS specific, and offer no protection extensions, or)69 W 8280 53726 MT (symlinks. They) 250 W( do not provide performance optimizations, and cannot be used as the root file system.)SH 9280 56205 MT (The SunOS 4.1 code lets the user change floppy disks without using umount/mount.) 17 W( It) 285 W( does this by serializing all)18 W 8280 57582 MT (operations and performing consistency checks between in-memory and on-disk data. As a result, the code is) 95 W( less)94 W 8280 58959 MT (effective at caching. NeXTStep uses the) 32 W( hardware to detect a change in floppy media, and auto-mounts floppies on)33 W 8280 60336 MT (insertion. The) 250 W( use of hardware detection should enable more optimizations.)SH 9280 62815 MT (In the non-UNIX world, IBM's OS/2 offers multi-user extensions to the PC-DOS FAT-based file) 76 W( system which)75 W 8280 64192 MT (they call)214 W /Times-Italic SF 12374 XM (extended attributes)214 W /Times-Roman SF (. These) 678 W( can support more than just protection information; they can be) 214 W( used for)215 W 8280 65569 MT (presentation purposes for instance. Extensions by the same name are defined in the) 73 W( ISO 9660 standard, and serve)72 W 8280 66946 MT (similar purposes.)SH 9280 69425 MT (Our optimizations for uncached accesses are similar, but unrelated to the optimizations described in) 149 W( [9, 7]) SH( for)149 W 8280 70802 MT (Extent Based File Systems. DosFs adds to McVoy's work the ability) 40 W( to specify the extent size at mount time. The)39 W ES %%Page: 20 21 BS 0 SI 10 /Times-Roman AF 6120 4286 MT (20)SH 6120 7886 MT (implementation of large operations is similar) 63 W( to the BSD 4.4)64 W /Times-Italic SF 31171 XM (cluster)SH /Times-Roman SF 34207 XM (idea, the)64 W /Times-Italic SF 37973 XM (bmap\050\051)SH /Times-Roman SF 41175 XM (changes are almost identical.)64 W 6120 9263 MT (But while our optimizations are specific) 30 W( to DosFs, the BSD 4.4 clusters are not file system-specific and can be used)29 W 6120 10640 MT (by any file system code. We call our)35 W /Times-Italic SF 21543 XM (bmap\050\051)SH /Times-Roman SF 24716 XM (only from within DosFs code,) 35 W( in 4.4 we would call the DosFs)36 W /Times-Italic SF 50032 XM (bmap\050\051)SH /Times-Roman SF 6120 12017 MT (from the file system-independent clustering code.)SH 14 /Times-Bold AF 6120 15835 MT (9. Conclusions)SH 10 /Times-Roman AF 7120 17212 MT (With DosFs we have demonstrated that it is possible to) 15 W( provide full UNIX semantics in a file system with simpler)14 W 6120 18589 MT (data structures than traditionally used in UNIX) 1 W( file systems. Removing inodes provides better disk utilization, better)2 W 6120 19966 MT (disk/power failure behavior, and) 75 W( eliminates many synchronous write operations in the handling of meta-data. The)74 W 6120 21343 MT (only cost is a more cumbersome and slow implementation of hard file links.)SH 7120 23822 MT (In the implementation of DosFs we have used a new block allocation) 34 W( algorithm, derived from MS-DOS) 35 W( [1].) SH( The)320 W 6120 25199 MT (algorithm obtains both) 48 W( contiguous allocation of disk blocks and compact disk utilization. DosFs is both faster than)47 W 6120 26576 MT (4.3 BSD FFS and more efficient in disk space.) 1 W( The) 253 W( performance gains are equivalent to Extent Based allocation, but)2 W 6120 27953 MT (without the high fragmentation costs. DosFs allocates small blocks, but close to each other.) 36 W( In) 320 W( this way it can take)35 W 6120 29330 MT (advantage of disk-level read and write caches, and obtains a three fold performance improvement over) 241 W( FFS.)242 W 6120 30707 MT (Moreover, DosFs takes advantage of the contiguous block allocation to perform large) 206 W( size I/O operations and)205 W 6120 32084 MT (obtains a five fold speedup over FFS.)SH 7120 34563 MT (An important) 27 W( factor in the DosFs performance profile is the effect of seek times, or more precisely the time spent)28 W 6120 35940 MT (by the disk to)73 W /Times-Italic SF 12079 XM (service)SH /Times-Roman SF 15234 XM (a given I/O) 73 W( request. Today's disks use a variety of multi-track caching strategies that make)72 W 6120 37317 MT (the old FFS model) 32 W( [8]) SH( unrealistic. Unfortunately, the service time has become very difficult to model. In) 32 W( our SCSI)33 W 6120 38694 MT (analyzer traces we observed large variations in service times, anywhere from 3 milliseconds to 45 milliseconds, on)54 W 6120 40071 MT (the same disk, and not at all a) 9 W( simple function of the distance between disk blocks. When the disk drive uses a write)10 W 6120 41448 MT (cache, not only the distance, but the type of access and previous history affects the service time. Finally, the) 21 W( zoning)20 W 6120 42825 MT (techniques used in recent drives add another variable to the already complicated model.) 214 W( All) 680 W( of these factors)215 W 6120 44202 MT (contribute to make DosFs' performance better than FFS, even in cases where we did not expect it.)SH 7120 46681 MT (The only deficiencies in the MS-DOS permanent data structures are in handling large files) 19 W( and large disks. Large)18 W 6120 48058 MT (files create two) 91 W( problems, both related to the choice of a linked list to represent the clusters of a file. In the first)92 W 6120 49435 MT (place, is it is impossible to represent files with holes, all clusters must be allocated by DosFs and the "holes" truly)66 W 6120 50812 MT (must be zeroed for security reasons. The programmer does not have to issues the) 29 W( intervening writes, but there is no)30 W 6120 52189 MT (way to indicate in a FAT entry that the block ought to be zeroed when accessed. FFS uses) 173 W( a tree as its data)172 W 6120 53566 MT (structure, and can easily mark the holes as missing blocks, to be zeroed on) 128 W( access. But files with holes are not)129 W 6120 54943 MT (commonplace, and a copy) 38 W( of the file will fill the holes anyway. The second problem is we must traverse the whole)37 W 6120 56320 MT (list to get to the last cluster of a file. We have argued that) 53 W( it is feasible to cache the entire FAT in memory so that)54 W 6120 57697 MT (the cost is just in memory accesses, and much less than the case where FFS) 92 W( must actually fetch an indirect block)91 W 6120 59074 MT (from disk.)SH 7120 61553 MT (Large disks create the) 239 W( problem of representing cluster numbers, which are currently 16 bit integers in the)240 W 6120 62930 MT (permanent data structures. It is possible to use a new FAT type, with 32 bit entries.) 240 W( It) 729 W( is not possible to)239 W 6120 64307 MT (transparently change the format of the directory entries to hold a 32 bit starting cluster instead of the 16 bit one. A)43 W 6120 65684 MT (temporary solution can be to grow the cluster size, but this) 12 W( can only gain a few more bits, if the cluster size becomes)11 W 6120 67061 MT (32 KB the fragmentation \050most MS-DOS files are small\051 is unacceptable. If we ignore MS-DOS compatibility) 44 W( this)45 W 6120 68438 MT (problem disappears.)SH 7120 70917 MT (We implemented DosFs inside the Mach 3.0 UX UNIX server. The file system code is the) 240 W( same as the)239 W ES %%Page: 21 22 BS 0 SI 10 /Times-Roman AF 54080 4286 MT (21)SH 8280 7886 MT (monolithic Mach) 84 W( 2.5 kernel and uses Sun's Vnode layer. We started from Pace Willisson's ISO file system code)85 W 8280 9263 MT (which is based on a different Vnode layer, therefore we know that retrofitting the changes back) 132 W( into a BSD 4.4)131 W 8280 10640 MT (environment is not difficult.) 17 W( Given) 286 W( the similarities in the)18 W /Times-Italic SF 31540 XM (bmap\050\051)SH /Times-Roman SF 34696 XM (function, it would be interesting to port DosFs to a)18 W 8280 12017 MT (4.4 BSD system and re-evaluate the performance profiles.)SH 12 /Times-Bold AF 8280 15701 MT (9.1. Status and Acknowledgements)SH 10 /Times-Roman AF 9280 17078 MT (The code described in this paper has been integrated in the CMU sources \050releases UX42/43\051, and is) 22 W( available for)21 W 8280 18455 MT (general use at CMU and elsewhere. Mike Dryfoos, Mahadev Satyanarayanan, Robert Baron, Daniel) 147 W( Stodolsky,)148 W 8280 19832 MT (Howard Gobioff and Peter Dinda gave us many helpful comments on earlier versions of) 40 W( this paper. Thanks for her)39 W 8280 21209 MT (patience, and good luck to Kelly.)SH ES %%Page: 22 23 BS 0 SI 10 /Times-Roman AF 6120 4286 MT (22)SH ES %%Page: 23 24 BS 0 SI 10 /Times-Roman AF 54080 4286 MT (23)SH 16 /Times-Bold AF 8280 8272 MT (References)SH 10 /Times-Roman AF 8280 10063 MT ([1])SH 11280 XM (Ray Duncan.)SH /Times-Italic SF 11280 11168 MT (Advanced MSDOS Programming.)SH /Times-Roman SF 11280 12273 MT (Microsoft Press, 1986.)SH 8280 14064 MT ([2])SH 11280 XM (David Golub, Randall Dean, Alessandro Forin, Richard Rashid.)SH 11280 15169 MT (Unix as an Application Program.)SH 11280 16274 MT (In)SH /Times-Italic SF 12363 XM (Proceedings of the USENIX Summer Conference)SH /Times-Roman SF (, pages 87-95. USENIX, Anaheim, CA, June, 1990.)SH 8280 18065 MT ([3])SH 11280 XM (David Golub and Richard Draves.)SH 11280 19170 MT (Moving the Default Memory Manager Out of the Mach Kernel.)SH 11280 20275 MT (In)SH /Times-Italic SF 12363 XM (Proceedings of the USENIX Mach Symposium)SH /Times-Roman SF (, pages 177-188. USENIX, Monterey, CA, November,)SH 12780 21380 MT (1991.)SH 8280 23171 MT ([4])SH 11280 XM (Howard, J. et al.)SH 11280 24276 MT (Scale and Performance in a Distributed File System.)SH /Times-Italic SF 11280 25381 MT (ACM Transactions on Computer Systems)SH /Times-Roman SF 28030 XM (6\0501\051, February, 1988.)SH 8280 27172 MT ([5])SH 11280 XM (ISO 9660 : 1988 \050E\051.)SH /Times-Italic SF 11280 28277 MT (Information processing - Volume and file structure of CD-ROM for information interchange.)SH /Times-Roman SF 11280 29382 MT (International Organization for Standardization, 1988.)SH 8280 31173 MT ([6])SH 11280 XM (Kleiman, S. R.)SH 11280 32278 MT (Vnodes: An Architecture for Multiple File System Types in Sun UNIX.)SH 11280 33383 MT (In)SH /Times-Italic SF 12363 XM (Proceedings of the Summer 1986 USENIX Conference)SH /Times-Roman SF (, pages 238-247. June, 1986.)SH 8280 35174 MT ([7])SH 11280 XM (Margo Seltzer, Keith Bostic, Kirk McKusick, Carl Staelin.)SH 11280 36279 MT (An Implementation of a Log-Structured File System for Unix.)SH 11280 37384 MT (In)SH /Times-Italic SF 12363 XM (Proceedings of the USENIX Winter Conference)SH /Times-Roman SF (, pages 201-220. USENIX, San Diego, CA, January,)SH 12780 38489 MT (1993.)SH 8280 40280 MT ([8])SH 11280 XM (Kirk McKusick, William Joy, Sam Leffler, R. Fabry.)SH 11280 41385 MT (A Fast File System for UNIX.)SH /Times-Italic SF 11280 42490 MT (ACM Transactions on Computer Systems)SH /Times-Roman SF 28030 XM (:181-197, August, 1984.)SH 8280 44281 MT ([9])SH 11280 XM (Larry McVoy and S. Kleiman.)SH 11280 45386 MT (Extent-like Performance from a Unix File System.)SH 11280 46491 MT (In)SH /Times-Italic SF 12363 XM (Proceedings of the USENIX Winter Conference)SH /Times-Roman SF (, pages 33-44. USENIX, Dallas, TX, January, 1991.)SH 8280 48282 MT ([10])SH 11280 XM (John Ousterhout, et al.)SH 11280 49387 MT (A Trace-Driven Analysis of the UNIX 4.2 BSD File System.)SH 11280 50492 MT (In)SH /Times-Italic SF 12363 XM (Proceedings of the Tenth Symposium on Operating Systems Principles)SH /Times-Roman SF (, pages 96-108. December, 1985.)SH 8280 52283 MT ([11])SH 11280 XM (John Ousterhout.)SH 11280 53388 MT (Why Aren't Operating Systems Getting Faster As Fast As Hardware?)SH 11280 54493 MT (In)SH /Times-Italic SF 12363 XM (Proceedings of the Summer 1990 USENIX Conference)SH /Times-Roman SF (. June,) 250 W( 1990.)SH 8280 56284 MT ([12])SH 11280 XM (Richard Rashid, Gerald Malan, David Golub, Robert Baron.)SH 11280 57389 MT (DOS as a Mach 3.0 Application.)SH 11280 58494 MT (In)SH /Times-Italic SF 12363 XM (Proceedings of the USENIX Mach Symposium)SH /Times-Roman SF (, pages 27-40. USENIX, Monterey, CA, November, 1991.)SH 8280 60285 MT ([13])SH 11280 XM (Rock Ridge Interchange Protocol, Version 1.)SH /Times-Italic SF 11280 61390 MT (An ISO 9660:1988 compliant approach to providing adequate CD-ROM support for Posix file system)SH 12780 62495 MT (semantics.)SH /Times-Roman SF 11280 63600 MT (Rock Ridge Technical Group, 1991.)SH 8280 65391 MT ([14])SH 11280 XM (Satyanarayanan, M.)SH 11280 66496 MT (Integrating Security in a Large Distributed System.)SH /Times-Italic SF 11280 67601 MT (ACM Transactions on Computer Systems)SH /Times-Roman SF 28030 XM (7\0503\051, August, 1989.)SH ES %%Page: 24 25 BS 0 SI 10 /Times-Roman AF 6120 4286 MT (24)SH ES %%Page: i 26 BS 0 SI 10 /Times-Roman AF 54802 4286 MT (i)SH 16 /Times-Bold AF 25591 8272 MT (Table of Contents)SH 10 SS 9780 9352 MT (1. Introduction)SH 54580 XM (3)SH 9780 10432 MT (2. The MS-DOS File System Structure)SH 54580 XM (4)SH 9780 11512 MT (3. Design Issues)SH 54580 XM (6)SH 11780 12592 MT (3.1. Protection)SH 54580 XM (6)SH 11780 13672 MT (3.2. File Naming)SH 54580 XM (7)SH 11780 14752 MT (3.3. Inode Numbering)SH 54580 XM (8)SH 11780 15832 MT (3.4. Hard/Symbolic Links)SH 54580 XM (8)SH 11780 16912 MT (3.5. NFS Access)SH 54580 XM (9)SH 11780 17992 MT (3.6. Other extensions)SH 54580 XM (9)SH 9780 19072 MT (4. Tools)SH 54080 XM (10)SH 9780 20152 MT (5. Optimizations)SH 54080 XM (10)SH 9780 21232 MT (6. Disk Utilization)SH 54080 XM (12)SH 9780 22312 MT (7. Performance Evaluation)SH 54080 XM (14)SH 11780 23392 MT (7.1. Performance in Mach 2.5)SH 54080 XM (17)SH 9780 24472 MT (8. Related Work)SH 54080 XM (19)SH 9780 25552 MT (9. Conclusions)SH 54080 XM (20)SH 11780 26632 MT (9.1. Status and Acknowledgements)SH 54080 XM (21)SH 12 SS 8280 28156 MT (References)SH 53880 XM (23)SH ES %%Page: ii 27 BS 0 SI 10 /Times-Roman AF 6120 4286 MT (ii)SH ES %%Page: iii 28 BS 0 SI 10 /Times-Roman AF 54246 4286 MT (iii)SH 16 /Times-Bold AF 26702 8272 MT (List of Figures)SH 10 SS 9780 9352 MT (Figure 1:) SH( Organization) 500 W( Of The MS-DOS File System)SH 54580 XM (5)SH 9780 10432 MT (Figure 2:) SH( Metadata) 500 W( Costs: FFS Over DosFs)SH 54080 XM (13)SH 9780 11512 MT (Figure 3:) SH( File) 500 W( System Overhead In Bytes, As A Function Of The File Size)SH 54080 XM (13)SH 9780 12592 MT (Figure 4:) SH( Costs) 500 W( Of Directory Entries)SH 54080 XM (14)SH ES %%Page: iv 29 BS 0 SI 10 /Times-Roman AF 6120 4286 MT (iv)SH ES %%Page: v 30 BS 0 SI 10 /Times-Roman AF 54580 4286 MT (v)SH 16 /Times-Bold AF 27013 8272 MT (List of Tables)SH 10 SS 9780 9352 MT (Table 1:) SH( Permanent) 500 W( Data Structures And UNIX Functionality Issues)SH 54580 XM (6)SH 9780 10432 MT (Table 2:) SH( A) 500 W( Simple Utilization Test: Moving Data To A Floppy Disk)SH 54080 XM (12)SH 9780 11512 MT (Table 3:) SH( John) 500 W( Ousterhout's Basic File System Tests.)SH 54080 XM (15)SH 9780 12592 MT (Table 4:) SH( Uncached) 500 W( Data Transfers, For Local Disk And Over NFS, In KB/sec)SH 54080 XM (15)SH 9780 13672 MT (Table 5:) SH( Results) 500 W( For Selected Macro-Benchmarks, All Times In Seconds)SH 54080 XM (17)SH 9780 14752 MT (Table 6:) SH( Mach) 500 W( 2.5 Test Results On Gateway.)SH 54080 XM (18)SH 9780 15832 MT (Table 7:) SH( John) 500 W( Ousterhout's Basic File System Tests, Mach 2.5 DECStation)SH 54080 XM (19)SH ES %%Trailer %%Pages: 30 %%DocumentFonts: Times-Roman Times-Bold Times-Italic Courier-Bold