Ms-dos, Windows 98, Windows me



Yüklə 3,17 Mb.
tarix07.11.2018
ölçüsü3,17 Mb.
#78614



MS-DOS, Windows 98, Windows ME

  • 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).

    • Contains: Y2108 problem
  • 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

  • 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
  • Backing up and active filesystem is tricky

    • 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

    • Slow and complicated.


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

  • 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




Yüklə 3,17 Mb.

Dostları ilə paylaş:




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©genderi.org 2024
rəhbərliyinə müraciət

    Ana səhifə