completed lec 20,21,22 -- still need lec 23 master
authorKyle Spaans <kspaans@student.math.uwaterloo.ca>
Tue, 4 Aug 2009 18:51:34 +0000 (14:51 -0400)
committerKyle Spaans <kspaans@student.math.uwaterloo.ca>
Tue, 4 Aug 2009 18:51:34 +0000 (14:51 -0400)
lec20-0716.tex
lec21-0721.tex
lec22-0723.tex

index 6f589fa..7fb2900 100644 (file)
@@ -18,4 +18,60 @@ owner or any single process.
 \subsection*{File System to the OS}
 The FS is a system that collects many files under a single namespace and gives
 the OS the ability to explicitly create, modify, open, close, and destry files.
+Opening a file will return a file descriptor that can be used later to refer to
+the open file, and can be used to explicitly close it. There is a lot of
+overhead inherent in opening a file. The kernel has the check that the file
+exists, check it's permissions against the process requesting the open,
+translating the file position to a block on disk, etc. It would be slow to do
+this every time a read or write was requested.  Therefore, ot is the kernel's
+job to keep track of the open files for each process, and perform the
+operations that those processes request on the files. The \texttt{fstat()}
+system call can be used to get or set attributes from files.
+
+\subsubsection*{File Positioning}
+Every open file has a ``current position''. Read and write operations implicity
+position themselves in the file, making sequential I/O very easy. That is, when
+a read of 50 bytes is requested, the position in the file gets moved ahead by 50
+bytes as well. If a specific position in the file is required, then the
+\texttt{lseek()} syscall can be used (I.E. for random access). Each open file
+as a position attribute. So if the same file is opened multiple times, even by
+the same process, each file descriptor will have a different position. The file
+descriptor is associated with each process, so another process can't just guess
+an FD and intrude upon an existing open file.
+
+\subsubsection*{Read/Write Copy Semantics}
+Think of transfering blocks of data to and from a process's address space and
+to and from the file in the file system. (In POSIX, \texttt{read()} will return
+the number of bytes read, indicating EOF when reached.)
+
+\paragraph*{Memory Mapped Files}
+are even closer to virtual memory. Instead of copying the data from the file, a
+portion of the file is mapped directly into the process's address space. Load
+store instructions become read/write. The kernel has to manage this mapping.
+Each process will need it's own mapping for reading from the file.
+
+\subsection*{Update Semantics}
+What happens when a memory-mapped file is written to? It can have a read-only
+mapping, writes can simply be ignored (not propogated to the file), or finally
+writes can be eagerly or lazily updated. Eager updates are inefficient (imagine
+a large sequence of store operations, and calling write to write a word for
+each one).  Lazy updates can be performed at the request of the process, or
+when the file is unmapped.
+
+\subsubsection*{Concurrent Updates}
+What if multiple processes have memory mapped the same file? Lazy updates can't
+guarantee updates to the file, but eager updates can. The kernel would have to
+invalidate the page table entries of other process if their mapping gets
+written to by another process.
+
+\subsection*{File Names}
+A file name consists of a full path (absolute path), or any unique ID in a name
+space. Often a hierarchical structure is given to the name space, E.G.
+directories in a tree (Directed Acyclic Graph). This can be done by splitting
+the filename into directories and then a name (seperated by ``/'' in Unix).
+The file system manages this structure, translating a file name to a location
+on disk of the data and meta-data. One way to this can be to distribute file
+information in nodes of the tree, E.G. directory files. Then name translation
+becomes a recursive process of identifying the first directory in the path,
+opening it, finding the next directory, and then proceeding to open it in turn.
 \end{document}
index 646a4a5..6c9cef9 100644 (file)
 \section*{Lecture 21 -- Hierarchical Namespaces}
 We have the idea of ``directories'' which let users and applications organize
 their files in a hierarchical manner. Directories are files. They behave just
-like any other file. However, they are special...
+like any other file. However, they are special. They can contain the meta-data
+and other information about the files under them.
+
+\subsection*{Hard and Soft Links}
+A hard link is a relationship between file system name and an underlying file
+object. Think of it as a copy that doesn't take up additional space. It can be
+implemented as an entry in a directory structure. Therefore there can be
+files (entires in directory structures) that refer to the same underlying
+object. A soft link, or symbolic link, is a relationship between a name and a
+name. It can be implemented as a special file, containg the file name of the
+link it points to. \texttt{Open()} can then know to open the target file
+rather than the symlink.
+
+Hardlinks preserve referential integrity. While there are still references to
+an object, it will not be destroyed. When a new file is created, a single hard
+link is made from its name to its object. Objects have a reference count
+associated with them. The operation of deleting a file is actually just
+unlinking it (deleting all references).
+
+\subsection*{Multiple File Systems}
+OS kernels can support multiple file systems mounted at the same time. The
+underlying VFS and file API means that this can be done easily. A FS gets
+mounted at a point starting from the root of the FS tree. That is, they are
+mounted on directories. All file paths in a mounted FS gain a prefix equal
+to the path to their mount point. Alternatively, Windows uses a file system ID
+(drive letter) and a special seperator (``:''). The tradeoffs are a wide root
+node in Windows and longer pathname translation in Unix.
+
+Hard links cannot cross file systems because they refer to FS specific objects.
+These objects might not be the same in a different file system, or might be
+duplicated in an ambiguous way. Symbolic links, however, are just fine for
+crossing FS boundaries. This can get tricky though, one could create cycles
+with symlinks that point to directories. For this reason POSIX forbids making
+symbolic links to directories.
+
+\subsection*{File System Implementation}
+The file system manages space on the storage device. It has to locate file data
+and meta-data (by keeping some kind of index of their location), work with
+directories, work with links, buffer frequently used data, maintain it's own
+data structures, and make sure that file objects persist. Recall that a disk
+drive is like an array of bytes. Just like with a virtual memory system, the
+file system must layout files (segments) in blocks on disk (pages). This means
+that fixed-size allocation is easy, but suffers from internal fragmentation
+(like paging). Variable-sized allocation is more like segmentation, and is more
+complicated to manage. Because of the nature of hard drisks, with spinning
+heads, cylinders, and seek time, layout of files matters! Sequentially layed
+out files are easier to access. Next best thing is to have multiple, large
+\textbf{extents} that are sequential on disk. Extents are contiguous chunks
+``owned'' by a single file.
+
+\subsubsection*{Keeping Track of Files on Disk}
+The file system must maintain a translation of files to sectors on disk.
+
+\paragraph*{Chaining}
+is when a file's meta-data points to it's first block of data, and that block
+contains a pointer to the next block of data, and so on. This simple scheme is
+OK for sequential access but pretty bad for random access. 
+
+\paragraph*{External-Chaining}
+lays out files the same way as with Chaining, but the chain of block pointers is
+kept in a block of meta-data (think FAT, File Allocation Table) in a known part
+of the disk. Randonly accessing a file now means traversing on the table, rather
+than every block making up the file. The table can be cached in main memory, but
+if it gets damaged, your data is gone, or at least very tricky to recover.
 \end{document}
index 6cb5c20..3db9011 100644 (file)
 \section*{Lecture 22 -- File Systems Implementation}
 Keeping track of files on a disk drive.
 
-\subsection*{Per-file Indexing}
+\paragraph*{Per-file Indexing}
 An idea from the Unix world, keep an array of pointers to disk blocks, the
-index, in a well known place on disk... Example are Unix i-nodes.
+index, in a well known place on disk, possibly in the file's meta-data.
+Example is Unix i-nodes. Each i-node in a file-system can be identified by a
+unique number, and the entire i-node can be cached when the file is opened.
+Indexs must be a set size though, how to choose the size?
+
+\subsection*{File Meta-Data Storage}
+There a couple options. The data can be stored in directory files. But if
+there are multiple copies (hard links) then the file system has to remember
+to update each directory's entries. Alternatively a large table can be stored
+on disk. Each file gets its own entry in the table, and gets a unique ID number
+to be used to find it in the table. Directories can then store the ID, making
+links even cheaper.
+
+Unix i-nodes are stored on the disk. They are a fixed size, containing meta-data
+and pointers (direct and single/double/triple indirect pointers) to data blocks.
+Files are accessed by their unique i-node numbers. The indirect block pointers
+let a fixed-size i-node describe a large amount of data (8TB behind a triple
+indirect block pointer if block size is 8KB and block pointers are 8 bytes:
+$2^10$ pointers per block, makes for $2^10 \cdot 2^10 \cdot 2^10$ times 8KB).
+The price is that blocks full of pointers take up space on the disk (that can't be
+used by files) and require extra disk I/O to drill down to direct block pointers.
+Course notes at this point contain questions we should be able to answer, E.G.
+directory files should be able to be written to by users.
+
+\subsection*{Things that go In Main Memory}
+System and per-process open-file-tables, i-node numbers, block buffer cahces.
+We can apply our paging and replacement policies to these block caches as well.
+
+\subsection*{Crashes}
+Some types of file system operations are not atomic, such as deleting a file.
+Deleting means: remove directory entry, remove i-node, free disk space. It's
+possibly that one or more of these steps could be interrupted by an accidental
+shutdown. This causes the FS to be left in an inconsisten state, which will
+need to be repaired (E.G. a Unix \texttt{fsck}). Checking the entire file
+system can take a long time, so journaling file systems were invented. A log,
+or journal of meta-data operations is kept, and periodically written to the
+disk. If a deletion is interrupted, then the log makes it very simple to
+complete the deletion. If the writing of the log is interrupted, then the file
+still exists, and it was like it was never deleted in the first place. This
+makes file system operations appear to be atomic by simplifying their
+maintenance.
 \end{document}