Group:
memory management
Topic:
device driver
Topic:
file
Topic:
memory management by reference counting
| |
Summary
A file system needs to allocate files on disk. As files are created and deleted, the available space may become fragmented. Space is typically allocated in fixed size blocks or clusters. Files may be stored contiguously.
Unix partitions disks into cylinder groups. Free space may be identified with a bit map, but these data structures may need rebuilding after a failure. (cbb 11/07)
Subtopic: cylinder groups 
| Quote: UNIX partitions disks into cylinder groups with copy of superblock, local inodes, free block bit map, and usage statistics [»mckuMK8_1984]
| | Quote: a UNIX cylinder group preallocates an inode for every 2K bytes of disk; far more than needed [»mckuMK8_1984]
| | Quote: bookkeeping information for a UNIX cylinder group is staggered to prevent a lost platter from destroying everything [»mckuMK8_1984]
| | Quote: UNIX directories on different cylinder groups; inodes in a directory in the same group; at most 16 disk transfers for inodes of cylinder group [»mckuMK8_1984]
| | Quote: large UNIX files spread across cylinder groups by new group at 48K bytes and every megabyte [»mckuMK8_1984]
| | Quote: overflow UNIX allocation by rotational closest in cylinder, in same group, rehash to another group, exhaustive search [»mckuMK8_1984]
| | Quote: Cedar partitions the disk into big and small file areas to curtail fragmentation; the areas are hints [»hagmR_1987]
| | Quote: a file must lie in a single partition (set of tracks); may be specified [»lampBW4_1974]
|
Subtopic: block allocation and fragmented blocks
| Quote: UNIX file as zero or more data blocks plus fragmented blocks; e.g., 1K fragments of 4K data blocks [»mckuMK8_1984]
| | Quote: free disk bit map for UNIX at fragment level, but blocks are aligned [»mckuMK8_1984]
| | Quote: smallest UNIX fragment is a disk sector; need about 5% free disk space
| | Quote: files should be extended one block at a time, with fragment at end; UNIX tells applications the optimal read/write size [»mckuMK8_1984]
|
Subtopic: block size
| Quote: store data in large block sizes; balances bandwidth with latency [»pattDA10_2004]
|
Subtopic: storage allocation
| Quote: UNIX file system allocation accounts for block interleave; divides cylinder group into 8 rotational groups [»mckuMK8_1984]
|
Subtopic: disk errors
| Quote: for hardware failures, 30% memory, 26% disk, 17% processor; for driver failures, 35% display, 13% anti-virus, 10% CD-burning, 9% audio, 9% modem
|
Subtopic: rebuilding a disk
| Quote: Unix can quickly verify disk allocation by a sequential scan of the i-list [»ritcDM7_1978a]
| | Quote: DoubleSpace rebuilds its sector bit map whenever the disk is mounted
| | Quote: the bit table for free disk pages is a hint, verified against the label of the free page [»lampBW10_1983]
| | Quote: Cedar uses a free page bit map; reconstruct if necessary; shadow bitmap for uncommitted file deletes [»hagmR_1987]
| | Quote: all free pages kept in OS6's free storage file, in cache memory, and on backup disk [»stoyJE3_1972]
|
Subtopic: binary buddy disk allocation
| Quote: Dartmouth Time-Sharing using binary buddy system for disk allocation; fast and effective [»kochPD11_1987]
| | Quote: binary buddy disk allocation just needs a 250 slot free-space table in memory; access overflow lists every 1000 allocate and free operations [»kochPD11_1987]
| | Quote: an extent for binary buddy disk allocation is a triple of device number, first sector, and log(sectorCount); 36-bit code with 24 bits for sector [»kochPD11_1987]
| | Quote: binary buddy disk allocation used for 20 years; no problem if disks are nearly full; 50% bandwidth utilization; 1.5 extents per file; simple [»kochPD11_1987]
| | Quote: binary buddy disk allocation has 2-6% internal fragmentation and 0-10% external fragmentation; most files contiguous
|
Subtopic: mounted devices
| Quote: include a device number in a disk address (extent) for multiple devices per file; for balancing, full allocation, and huge files
| | Quote: each mounted Unix device has a separate free pool; allows for easy unmounting [»thomK7_1978]
|
Subtopic: contiguous and clustered files
| Quote: all Amoeba files are stored contiguously on disk and in memory [»taneAS12_1990]
| | Quote: Amoeba's bullet server stores files contiguously, both on the disk and in the server's main memory; for rapid access [»vanrR10_1988]
| | Quote: Telesophy objects stored as contiguous blocks; infrequent deletion and nearly constant size over lifetime [»caplM12_1987]
| | Quote: Helix allocates disk blocks sequentially from a bit map; write-with-move ensures clustered writes [»fridM5_1985]
|
Subtopic: file headers
Quote: Oberon files include a header of disk addresses for each sector; extension table for large files
[»wirtN9_1989]
|
Related Topics
Group: memory management (11 topics, 367 quotes)
Topic: device driver (15 items)
Topic: file (22 items)
Topic: memory management by reference counting
(23 items)
|
