|
Ms-dos, Windows 98, Windows me
|
tarix | 07.11.2018 | ölçüsü | 3,17 Mb. | | #78614 |
|
MS-DOS, Windows 98, Windows ME Still supported in Windows NT, XP, Vista Its use has been shifted towards embedded devices such as - Digital cameras
- MP3 playes
- iPod (the default filesystem)
Filenames are limited to 8+3 characters.. Smaller ones are left justified and padded with space. Filenames are limited to 8+3 characters.. Smaller ones are left justified and padded with space. Attributes: read-only, archive, hidden, system Time represented with 2 bytes: correct upto +-2 second Date: Counts in three fields: day (5 bit), month (4 bits), year (7 bits). File size: 2 bytes. Theoretically 4GB limit, but the limit is 2GB due to other reasons. 10 bits reserved for future use.
MS-DOS keeps track of files through FAT table hold in memory. MS-DOS keeps track of files through FAT table hold in memory. First block number (2 bytes) used as the index to the FAT table which has 64K entries. Block size can be set as multiple of 512 byes. Three versions of FAT depending on the number of bits a disk address contains: - FAT-12
- FAT-16
- FAT-32 (actually should be called as FAT-28)
FAT is also used for keeping track of free blocks.
Block size: 512 bytes Block size: 512 bytes (2^12-10) X 512 bytes =~ 2MB - 10 disk addresses are used as special markers.
FAT table size: 4096 entries with 2 bytes each. Worked well for floppy disks. The limit was extended using larger block sizes: 1KB, 2KB, 4KB providing support for partitions 16MB. Limited for hard disks.
A file system must be mounted before it can be accessed A file system must be mounted before it can be accessed A unmounted file system is mounted at a mount point
At boot time, the root filesystem is registered with VFS. At boot time, the root filesystem is registered with VFS. When other filesystems are mounted, they must also register with VFS. When a filesystem registers, it provides the list of addresses of the functions that the VFS demands, such as reading a block. After registration, when one opens a file: open(“/usr/include/unistd.h”, O_RDONLY) VFS creates a v-node and makes a call to the concrete filesystem to return all the information needed. The created v-node also contains pointers to the table of functions for the concrete filesystem that the file resides.
What happens when you are making changes to a filesystem and the system crashes? What happens when you are making changes to a filesystem and the system crashes? - Example: Modifying block 5 of a large directory, adding lots of new file entries
- System crashes while the block is being written
- The new files are “lost!”
System runs fsck program on reboot - Scans through the entire filesystem and locates corrupted inodes and directories
- Can typically find the bad directory, but may not be able to repair it!
- The directory could have been left in any state during the write
fsck can take a very long time on large filesystems - And, no guarantees that it fixes the problems anyway
Example: removing a file requires - Remove the file from its directory
- Release the i-node to the pool of free i-nodes
- Return all the disk blocks to the pool of free disk blocks
In the absence of crashes the order these steps taken do not matter. In the presence of crashes, however, it does!
Example: removing a file requires Example: removing a file requires - Remove the file from its directory
- Release the i-node to the pool of free i-nodes
- Return all the disk blocks to the pool of free disk blocks
The inodes and file blocks will not be accessible from any file yet they will not be available for reassignment.
Example: removing a file requires Example: removing a file requires - Remove the file from its directory
- Release the i-node to the pool of free i-nodes
- Return all the disk blocks to the pool of free disk blocks
The directory node will point to an invalid inode or (if the inode is reassigned) point to a different file. The blocks of the file will not be available for reassignment.
Example: removing a file requires Example: removing a file requires - Remove the file from its directory
- Release the i-node to the pool of free i-nodes
- Return all the disk blocks to the pool of free disk blocks
The file will point to empty blocks, or (after reassignment) it will share the blocks of other files to which these were reassigned..
Consistency check is typically done after a crash.. Consistency check is typically done after a crash.. - UNIX: fsck
- Windoze: scandisk
Redundant information in the filesystem is used: - Check the blocks
- Check the files
Two tables, each containing a counter initialized to 0 - Blocks in use: How many times a block is present in a file
- Read all the i-nodes using a raw device (not through the filesystem calls)
- For each block that is referenced in the inode structure, increment the corresponding block use counter by one.
- Free blocks:
- Examine the free block list of free block bitmap structure
- Each appearance of a free block increments the counter by one
Uses a table of counters per file (rather than per block) Uses a table of counters per file (rather than per block) Starts from the root and traverses the tree - For each i-node, it increments the corresponding counter for that file
- Remember due to hard links, a file can appear more than once
- It then checks the link counts stored in the i-nodes to these values.
- If the link count > counter
- Even if the file is deleted by from all the directory entries, it will continue to exist.
- Solution: correct the link count
- If the counter > link count
- Although the file is linked from, say, two directories, removal from one would cause the i-node deleted leaving the other one invalid.
- Solution: correct the link count
-
Ensure that changes to the filesystem are made atomically Ensure that changes to the filesystem are made atomically - That is, a group of changes are made all together, or not at all
- In the directory modification example, this means that after the system reboots:
- The directory either looks exactly as it did before the block was modified
- Or the directory looks exactly as it did after the block was modified
- Cannot leave an FS entity (data block, inode, directory, etc.) in an intermediate state!
Idea: Maintain a log of all changes to the filesystem - Log contains entries that indicate what was done
- e.g., “Directory 2841 had inodes 404, 407, and 408 added to it”
To make a filesystem change: - 1. Write an intent-to-commit record to the log
- 2. Write the appropriate changes to the log
- Do not modify the filesystem data directly!!!
- 3. Write a commit record to the log
This is essentially the same as the notion of database transactions
What happens when the system crashes? What happens when the system crashes? - Filesystem data has not actually been modified, just the log!
- So, the FS itself reflects only what happened before the crash
Periodically synchronize the log with the filesystem data - Called a checkpoint
- Ensures that the FS data reflects all of the changes in the log
No need to scan the entire filesystem after a crash... - Only need to look at the log entries since the last checkpoint!
For each log entry, see if the commit record is there - If not, consider the changes incomplete, and don't try to make them
Full backup Full backup - backup all the filesystem providing a snapshot of the system at that point which can be fully restored
- Typically done weekly or monthly
Incremental backup - Backup only the files that were changed after the most recent backup
- Typically, a weekly backup is followed by daily incremental backups
- Smaller backup size, and faster
Compressed backups - Reduced storage
- Less secure: a single bad byte can screw the whole backup
- Since during backup, files and directories are being modified
Makes the system less secure - Each backup tape/disk needs to be as safe as the serve itself..
- It doesn’t matter if your backup tapes are lying around, even if you have the most secure computer system..
Algorithm Algorithm - Starts at block 0 of the disk and copies all the data onto a tape/disk
Pros - Simple to implement in a bug-free way
- Fast
Cons - Backups the free blocks as well
- Backuping a free disk takes as much storage/time as a full disk
- Dumping of “bad blocks” is a concern
- Typically disk controllers provide bad block replacement transparently without the OS even knowing about it
- If a block goes bad after formatting, then the OS typically creates a “file” consisting of all the bad blocks.
Pros Pros - Allows to restore a single file. If directories that lie on the path to the file-to-be-restored were deleted, then they would also be restored.
Cons
Algorithm Algorithm - Full backup: Traverses the filesystem as a tree and creates the same filesystem structure on the backup disk/tape.
- Partial backup: all the directories on the path to the particular file needs to be saved. For instance, backing up file 9 requires the saving of directories, 1,5,6, and 7.
Bitmaps, indexed by i-node number are used. Bitmaps, indexed by i-node number are used. Phase 1: Examine all files and directories below the starting directory (root in this case), and
Phase 2: Recursively walk the tree again, and Phase 2: Recursively walk the tree again, and - UNMARK all the directories that do not have any modified files under them.
Note: - 10 and 11 are unmarked
- 5 and 6 remain marked
Phase 3: Scan the i-nodes in numerical order and Phase 3: Scan the i-nodes in numerical order and - Dump all the marked directories
Phase 4: dump the marked files. Phase 4: dump the marked files.
Restoring: Restoring: - Restore all the directories that were backupped
- Restore all the files
Links: Links: - If a file is linked to more than one directory, only one copy should be saved.
Holes: - In UNIX, some file, such as core files may contain holes.
- These files, write a few bytes, and then seek to a distant file offset and write some more bytes.
- These empty blocks that are not written should not be dumped and stored.
- Cores typically have may megabytes of empty blocks.
Special files - Such as named pipes (which can appear anywhere in the filesystem) should not be dumped.
Most filesystems cache significant amounts of disk in memory - e.g., Linux tries to use all “free” physical memory as a giant cache
- Avoids huge overhead for going to disk for every I/O
Issues: - When do you commit a write to the disk?
- What happens if you write only to the memory cache and then the system crashes?
- How do you keep the memory and disk views of a file consistent?
- What if the file metadata (inodes, etc.) is modified before the data blocks?
Read-ahead - Read a few extra blocks into memory when you do one read operation
- Amortize the cost of the seek
- Useful if the blocks of a file are laid out in contiguous blocks
- Take advantage of sequential access patterns on the file
Reading a 32-bit word from memory takes 10 nsec. Reading a 32-bit word from memory takes 10 nsec. Hard disks can transfer data at: 100MB/sec, that is 40nsec per 32-bit words.. - PLUS 5-10 msecs of seek time!
Caching aims to fill in the gap.. Often thousands of blocks are kept in cache.
The system tries to get blocks into the cache, before they are accessed to increase the hit rate. The system tries to get blocks into the cache, before they are accessed to increase the hit rate. - Sequential access: performance improvement
- Random access: performance degradation
Dostları ilə paylaş: |
|
|