Organization of the file system
Directories in the Unix OS The directory structure is simple. Each record
contains the name of the file and its index number hub. All other information
about the file (type, size, modification times, the owner, etc. and the number
of disk blocks) is in the index node. Search directory So is the file directory,
which has a special format, which consists of fixed-length records where each
record represents one ordinary files or directories that are members of the this
directory. Typically, a list of files in the directory is not structured to file
names. Therefore, the correct choice of the search algorithm filename in the
directory has a great impact on the efficiency and reliability of file systems.
Linear Search The combination of recordings on the files in the directory is a
linear list of symbolic names files. There are several strategies for viewing
such a list. The simplest of these is a linear search. Directory viewing from
the very beginning, has not meet the desired file. Although it is the least
effective way to search, it turns out that in most cases, he works with
acceptable performance. For example, the authors of Unix claimed that it is
quite linear search. Apparently, this is due to the fact that against the
background of relatively slow access to the disk, some of the delays encountered
in the process of scanning the list are insignificant. The method is simple, but
requires time-consuming. To create a new file need to scan the first directory
on the availability of the same name. Then, the name of the new file into a
directory end (unless, of course, a file with the same name in the directory
does not exist, otherwise, you need to inform the user). To delete a file you
want to search his name on the list and mark the record as unused. The real
drawback of this method is the linear search for a file. Information on the
structure of the directory is used frequently, and the poor implementation will
be seen by users. You can bring in binary search, if sorted list of files. But
this will make it harder creating and deleting files, as required displacement
of a large volume of information. Hash tables Hash is another method that could
be used to house and the subsequent search for the file name in the directory.
This method also file names are stored in the directory in the form of linear
list, but additionally used hash table. Hash tables, built precisely on that
basis hesh-funktsiya allows the file name to obtain a pointer to the file name
on the list. Thus, we can significantly reduce the search time. As a result hash
conflicts may arise, that is a situation where the hash function is applied to
different file names, gives the same result. Usually, the names of these files
are united in communication lists, suggesting further implementation of a
consistent finding the desired file name. Good Choice
Next part
|