home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / bsd_srcs / share / doc / smm / 14.fastfs / 2.t < prev    next >
Encoding:
Text File  |  1991-04-17  |  6.5 KB  |  144 lines
  1. .\" Copyright (c) 1986 The Regents of the University of California.
  2. .\" All rights reserved.
  3. .\"
  4. .\" Redistribution and use in source and binary forms, with or without
  5. .\" modification, are permitted provided that the following conditions
  6. .\" are met:
  7. .\" 1. Redistributions of source code must retain the above copyright
  8. .\"    notice, this list of conditions and the following disclaimer.
  9. .\" 2. Redistributions in binary form must reproduce the above copyright
  10. .\"    notice, this list of conditions and the following disclaimer in the
  11. .\"    documentation and/or other materials provided with the distribution.
  12. .\" 3. All advertising materials mentioning features or use of this software
  13. .\"    must display the following acknowledgement:
  14. .\"    This product includes software developed by the University of
  15. .\"    California, Berkeley and its contributors.
  16. .\" 4. Neither the name of the University nor the names of its contributors
  17. .\"    may be used to endorse or promote products derived from this software
  18. .\"    without specific prior written permission.
  19. .\"
  20. .\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  21. .\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  22. .\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  23. .\" ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  24. .\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  25. .\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  26. .\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  27. .\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  28. .\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  29. .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  30. .\" SUCH DAMAGE.
  31. .\"
  32. .\"    @(#)2.t    6.3 (Berkeley) 4/17/91
  33. .\"
  34. .ds RH Old file system
  35. .NH
  36. Old File System
  37. .PP
  38. In the file system developed at Bell Laboratories
  39. (the ``traditional'' file system),
  40. each disk drive is divided into one or more
  41. partitions.  Each of these disk partitions may contain
  42. one file system.  A file system never spans multiple
  43. partitions.\(dg
  44. .FS
  45. \(dg By ``partition'' here we refer to the subdivision of
  46. physical space on a disk drive.  In the traditional file
  47. system, as in the new file system, file systems are really
  48. located in logical disk partitions that may overlap.  This
  49. overlapping is made available, for example,
  50. to allow programs to copy entire disk drives containing multiple
  51. file systems.
  52. .FE
  53. A file system is described by its super-block,
  54. which contains the basic parameters of the file system.
  55. These include the number of data blocks in the file system,
  56. a count of the maximum number of files,
  57. and a pointer to the \fIfree list\fP, a linked
  58. list of all the free blocks in the file system.
  59. .PP
  60. Within the file system are files.
  61. Certain files are distinguished as directories and contain
  62. pointers to files that may themselves be directories.
  63. Every file has a descriptor associated with it called an
  64. .I "inode".
  65. An inode contains information describing ownership of the file,
  66. time stamps marking last modification and access times for the file,
  67. and an array of indices that point to the data blocks for the file.
  68. For the purposes of this section, we assume that the first 8 blocks
  69. of the file are directly referenced by values stored
  70. in an inode itself*.
  71. .FS
  72. * The actual number may vary from system to system, but is usually in
  73. the range 5-13.
  74. .FE
  75. An inode may also contain references to indirect blocks
  76. containing further data block indices.
  77. In a file system with a 512 byte block size, a singly indirect
  78. block contains 128 further block addresses,
  79. a doubly indirect block contains 128 addresses of further singly indirect
  80. blocks,
  81. and a triply indirect block contains 128 addresses of further doubly indirect
  82. blocks.
  83. .PP
  84. A 150 megabyte traditional UNIX file system consists
  85. of 4 megabytes of inodes followed by 146 megabytes of data.
  86. This organization segregates the inode information from the data;
  87. thus accessing a file normally incurs a long seek from the
  88. file's inode to its data.
  89. Files in a single directory are not typically allocated
  90. consecutive slots in the 4 megabytes of inodes,
  91. causing many non-consecutive blocks of inodes
  92. to be accessed when executing
  93. operations on the inodes of several files in a directory.
  94. .PP
  95. The allocation of data blocks to files is also suboptimum.
  96. The traditional
  97. file system never transfers more than 512 bytes per disk transaction
  98. and often finds that the next sequential data block is not on the same
  99. cylinder, forcing seeks between 512 byte transfers.
  100. The combination of the small block size,
  101. limited read-ahead in the system,
  102. and many seeks severely limits file system throughput.
  103. .PP
  104. The first work at Berkeley on the UNIX file system attempted to improve both
  105. reliability and throughput.
  106. The reliability was improved by staging modifications
  107. to critical file system information so that they could
  108. either be completed or repaired cleanly by a program
  109. after a crash [Kowalski78].
  110. The file system performance was improved by a factor of more than two by
  111. changing the basic block size from 512 to 1024 bytes.
  112. The increase was because of two factors:
  113. each disk transfer accessed twice as much data, 
  114. and most files could be described without need to access
  115. indirect blocks since the direct blocks contained twice as much data.
  116. The file system with these changes will henceforth be referred to as the
  117. .I "old file system."
  118. .PP
  119. This performance improvement gave a strong indication that
  120. increasing the block size was a good method for improving
  121. throughput.
  122. Although the throughput had doubled, 
  123. the old file system was still using only about
  124. four percent of the disk bandwidth.
  125. The main problem was that although the free list was initially
  126. ordered for optimal access,
  127. it quickly became scrambled as files were created and removed.
  128. Eventually the free list became entirely random,
  129. causing files to have their blocks allocated randomly over the disk.
  130. This forced a seek before every block access.
  131. Although old file systems provided transfer rates of up
  132. to 175 kilobytes per second when they were first created,
  133. this rate deteriorated to 30 kilobytes per second after a
  134. few weeks of moderate use because of this
  135. randomization of data block placement.
  136. There was no way of restoring the performance of an old file system
  137. except to dump, rebuild, and restore the file system.
  138. Another possibility, as suggested by [Maruyama76],
  139. would be to have a process that periodically
  140. reorganized the data on the disk to restore locality.
  141. .ds RH New file system
  142. .sp 2
  143. .ne 1i
  144.