completed lec 20,21,22 -- still need lec 23
[kspaans/CS350] / lec22-0723.tex
1 \documentclass{article}
2 \usepackage{fullpage}
3 \usepackage{amsmath}
4 \author{Kyle Spaans}
5 \date{July 23, 2009}
6 \title{Operating Systems Lecture Notes}
7 \begin{document}
8 \maketitle 
9
10 \section*{Lecture 22 -- File Systems Implementation}
11 Keeping track of files on a disk drive.
12
13 \paragraph*{Per-file Indexing}
14 An idea from the Unix world, keep an array of pointers to disk blocks, the
15 index, in a well known place on disk, possibly in the file's meta-data.
16 Example is Unix i-nodes. Each i-node in a file-system can be identified by a
17 unique number, and the entire i-node can be cached when the file is opened.
18 Indexs must be a set size though, how to choose the size?
19
20 \subsection*{File Meta-Data Storage}
21 There a couple options. The data can be stored in directory files. But if
22 there are multiple copies (hard links) then the file system has to remember
23 to update each directory's entries. Alternatively a large table can be stored
24 on disk. Each file gets its own entry in the table, and gets a unique ID number
25 to be used to find it in the table. Directories can then store the ID, making
26 links even cheaper.
27
28 Unix i-nodes are stored on the disk. They are a fixed size, containing meta-data
29 and pointers (direct and single/double/triple indirect pointers) to data blocks.
30 Files are accessed by their unique i-node numbers. The indirect block pointers
31 let a fixed-size i-node describe a large amount of data (8TB behind a triple
32 indirect block pointer if block size is 8KB and block pointers are 8 bytes:
33 $2^10$ pointers per block, makes for $2^10 \cdot 2^10 \cdot 2^10$ times 8KB).
34 The price is that blocks full of pointers take up space on the disk (that can't be
35 used by files) and require extra disk I/O to drill down to direct block pointers.
36 Course notes at this point contain questions we should be able to answer, E.G.
37 directory files should be able to be written to by users.
38
39 \subsection*{Things that go In Main Memory}
40 System and per-process open-file-tables, i-node numbers, block buffer cahces.
41 We can apply our paging and replacement policies to these block caches as well.
42
43 \subsection*{Crashes}
44 Some types of file system operations are not atomic, such as deleting a file.
45 Deleting means: remove directory entry, remove i-node, free disk space. It's
46 possibly that one or more of these steps could be interrupted by an accidental
47 shutdown. This causes the FS to be left in an inconsisten state, which will
48 need to be repaired (E.G. a Unix \texttt{fsck}). Checking the entire file
49 system can take a long time, so journaling file systems were invented. A log,
50 or journal of meta-data operations is kept, and periodically written to the
51 disk. If a deletion is interrupted, then the log makes it very simple to
52 complete the deletion. If the writing of the log is interrupted, then the file
53 still exists, and it was like it was never deleted in the first place. This
54 makes file system operations appear to be atomic by simplifying their
55 maintenance.
56 \end{document}