completed lec 20,21,22 -- still need lec 23
[kspaans/CS350] / lec21-0721.tex
1 \documentclass{article}
2 \usepackage{fullpage}
3 \usepackage{amsmath}
4 \author{Kyle Spaans}
5 \date{July 21, 2009}
6 \title{Operating Systems Lecture Notes}
7 \begin{document}
8 \maketitle 
9
10 \section*{Lecture 21 -- Hierarchical Namespaces}
11 We have the idea of ``directories'' which let users and applications organize
12 their files in a hierarchical manner. Directories are files. They behave just
13 like any other file. However, they are special. They can contain the meta-data
14 and other information about the files under them.
15
16 \subsection*{Hard and Soft Links}
17 A hard link is a relationship between file system name and an underlying file
18 object. Think of it as a copy that doesn't take up additional space. It can be
19 implemented as an entry in a directory structure. Therefore there can be
20 files (entires in directory structures) that refer to the same underlying
21 object. A soft link, or symbolic link, is a relationship between a name and a
22 name. It can be implemented as a special file, containg the file name of the
23 link it points to. \texttt{Open()} can then know to open the target file
24 rather than the symlink.
25
26 Hardlinks preserve referential integrity. While there are still references to
27 an object, it will not be destroyed. When a new file is created, a single hard
28 link is made from its name to its object. Objects have a reference count
29 associated with them. The operation of deleting a file is actually just
30 unlinking it (deleting all references).
31
32 \subsection*{Multiple File Systems}
33 OS kernels can support multiple file systems mounted at the same time. The
34 underlying VFS and file API means that this can be done easily. A FS gets
35 mounted at a point starting from the root of the FS tree. That is, they are
36 mounted on directories. All file paths in a mounted FS gain a prefix equal
37 to the path to their mount point. Alternatively, Windows uses a file system ID
38 (drive letter) and a special seperator (``:''). The tradeoffs are a wide root
39 node in Windows and longer pathname translation in Unix.
40
41 Hard links cannot cross file systems because they refer to FS specific objects.
42 These objects might not be the same in a different file system, or might be
43 duplicated in an ambiguous way. Symbolic links, however, are just fine for
44 crossing FS boundaries. This can get tricky though, one could create cycles
45 with symlinks that point to directories. For this reason POSIX forbids making
46 symbolic links to directories.
47
48 \subsection*{File System Implementation}
49 The file system manages space on the storage device. It has to locate file data
50 and meta-data (by keeping some kind of index of their location), work with
51 directories, work with links, buffer frequently used data, maintain it's own
52 data structures, and make sure that file objects persist. Recall that a disk
53 drive is like an array of bytes. Just like with a virtual memory system, the
54 file system must layout files (segments) in blocks on disk (pages). This means
55 that fixed-size allocation is easy, but suffers from internal fragmentation
56 (like paging). Variable-sized allocation is more like segmentation, and is more
57 complicated to manage. Because of the nature of hard drisks, with spinning
58 heads, cylinders, and seek time, layout of files matters! Sequentially layed
59 out files are easier to access. Next best thing is to have multiple, large
60 \textbf{extents} that are sequential on disk. Extents are contiguous chunks
61 ``owned'' by a single file.
62
63 \subsubsection*{Keeping Track of Files on Disk}
64 The file system must maintain a translation of files to sectors on disk.
65
66 \paragraph*{Chaining}
67 is when a file's meta-data points to it's first block of data, and that block
68 contains a pointer to the next block of data, and so on. This simple scheme is
69 OK for sequential access but pretty bad for random access. 
70
71 \paragraph*{External-Chaining}
72 lays out files the same way as with Chaining, but the chain of block pointers is
73 kept in a block of meta-data (think FAT, File Allocation Table) in a known part
74 of the disk. Randonly accessing a file now means traversing on the table, rather
75 than every block making up the file. The table can be cached in main memory, but
76 if it gets damaged, your data is gone, or at least very tricky to recover.
77 \end{document}