Teorija
Blokovi, dijelovi i tablica alokacije
Disk je niz blokova jednake veličine, a datotečni sustav svakoj datoteci dodjeljuje blokove. Kod preallocation (predalokacija) najveća veličina datoteke zadaje se pri stvaranju; kod dynamic allocation (dinamička alokacija) prostor se dodaje kad zatreba, u portions (dijelovima) od jednog bloka ili niza blokova. Koje dijelove datoteka ima, bilježi file allocation table (tablica alokacije datoteka): kod Stallingsa je to općeniti naziv za zapis o dijelovima svake datoteke, a Stallingsova tablica metoda uspoređuje tri metode po predalokaciji, veličini dijela i broju zapisa po datoteci. Simulator dodjeljuje dinamički; jedan dio je jedan blok, osim kod kontinuirane alokacije, gdje je dio cijela datoteka.
Blocks, portions and the file allocation table
The disk is an array of blocks of equal size, and the file system allocates blocks to each file. With preallocation, the maximum size of a file is declared when it is created; with dynamic allocation, space is added as it is needed, in portions of one block or of a run of blocks. Which portions a file has is recorded in the file allocation table: in Stallings this is the general name for the record of each file's portions, and Stallings's table of allocation methods compares the three methods by preallocation, portion size and the number of entries per file. The simulator allocates dynamically; one portion is one block, except in contiguous allocation, where the portion is the whole file.
Kontinuirana alokacija i vanjska fragmentacija
Contiguous allocation (kontinuirana alokacija) daje datoteci jedan niz uzastopnih blokova, pa zapis u direktoriju čuva samo početak i duljinu, a čitanje bilo kojeg bloka košta jedno čitanje. Brisanjem nastaju rupe i javlja se external fragmentation (vanjska fragmentacija): slobodnih blokova ima dovoljno, ali ne u jednom nizu (u scenariju „Tri metode alokacije” 17 slobodnih blokova ne primi datoteku od 11). Datoteka koja raste mora se premjestiti ako iza nje nema mjesta. Lijek je compaction (sažimanje), na disku defragmentation (defragmentacija): datoteke se slože jedna do druge i slobodni prostor postaje jedan niz. Isti problem u glavnoj memoriji prikazuje Dodjela memorije.
Contiguous allocation and external fragmentation
Contiguous allocation gives a file a single run of consecutive blocks, so the directory entry keeps only the start and the length, and reading any block costs one read. Deleting files leaves holes, and external fragmentation appears: there are enough free blocks, but not in one run (in the scenario “Three allocation methods”, 17 free blocks cannot hold a file of 11). A file that grows must be moved if there is no room after it. The remedy is compaction, on a disk called defragmentation: the files are packed next to each other and the free space becomes one run. The same problem in main memory is shown on the Memory allocation page.
Lančana alokacija
Chained allocation (lančana alokacija; Tanenbaum: linked-list allocation) dodjeljuje pojedinačne blokove bilo gdje na disku, a svaki blok nosi pokazivač na sljedeći; zapis u direktoriju čuva prvi blok i duljinu. Vanjske fragmentacije nema, ali do bloka k treba pročitati k + 1 blokova, a blokovi su razbacani po disku. Consolidation (konsolidacija) povremeno složi lance u nizove, slično defragmentaciji. Tanenbaumov FAT nije isto što i Stallingsova tablica alokacije: FAT je jedna tablica u memoriji s jednim pokazivačem po bloku diska, pa se lanac prati bez čitanja podatkovnih blokova.
Chained allocation
Chained allocation (Tanenbaum: linked-list allocation) allocates individual blocks anywhere on the disk, and each block carries a pointer to the next one; the directory entry keeps the first block and the length. There is no external fragmentation, but reaching block k takes k + 1 block reads, and the blocks are scattered over the disk. Consolidation periodically gathers the chains into runs, much like defragmentation. Tanenbaum's FAT is not the same thing as Stallings's file allocation table: the FAT is a single table in memory with one pointer per disk block, so a chain is followed without reading the data blocks.
Indeksirana alokacija i inode
Indexed allocation (indeksirana alokacija) datoteci daje index block (blok indeksa) s pokazivačima na njezine blokove, pa bilo koji blok košta dva čitanja. Blok indeksa može umjesto pojedinih blokova čuvati extents (ekstente), nizove (početak, duljina). UNIX to razvija u inode: zapis o datoteci s atributima i s n izravnih pokazivača, zatim single, double i triple indirect block (jednostruko, dvostruko i trostruko neizravni blok) s po P = B / p pokazivača. Najveća datoteka ima n + P + P² + P³ blokova; uz 12 izravnih pokazivača, blokove od 4 KB i pokazivače od 8 B to je 134.480.396 blokova, oko 513 GiB (kalkulator iznad). Čitanje bloka na razini neizravnosti r košta r + 1 čitanja, a neizravni blokovi nastaju tek kad zatrebaju.
Indexed allocation and the inode
Indexed allocation gives a file an index block with pointers to its blocks, so any block costs two reads. Instead of single blocks, the index block can hold extents, runs given as (start, length). UNIX extends this into the inode: a record of the file with its attributes and n direct pointers, followed by a single, a double and a triple indirect block with P = B / p pointers each. The largest file has n + P + P² + P³ blocks; with 12 direct pointers, 4-KB blocks and 8-byte pointers that is 134,480,396 blocks, about 513 GiB (see the calculator above). Reading a block at indirection level r costs r + 1 reads, and indirect blocks are created only when they are needed.
Upravljanje slobodnim prostorom
Stallings opisuje četiri načina. Bit table (bit tablica) ima po jedan bit za svaki blok (0 slobodan, 1 zauzet); za disk od 16 GB s blokovima od 512 B zauzima 4 MB, ali se lako nađe niz slobodnih blokova. Chained free portions (lanac slobodnih dijelova) povezuje slobodne dijelove pokazivačem i duljinom u samim slobodnim blokovima: ne troši dodatni prostor, ali prije alokacije treba pročitati zaglavlje dijela, a nakon dužeg rada lanac se raspadne na sitne dijelove. Indexing (indeksiranje) drži tablicu slobodnih dijelova, a free block list (lista slobodnih blokova) popis brojeva slobodnih blokova, u simulatoru kao stog; Stallings procjenjuje da lista zauzima manje od 1 % diska.
Free space management
Stallings describes four methods. A bit table has one bit for each block (0 free, 1 in use); for a 16-GB disk with 512-byte blocks it takes 4 MB, but a run of free blocks is easy to find. Chained free portions links the free portions by a pointer and a length kept in the free blocks themselves: it uses no extra space, but the header of a portion must be read before allocating from it, and after a long time in use the chain breaks up into small portions. Indexing keeps a table of free portions, and a free block list keeps the numbers of the free blocks, in the simulator as a stack; Stallings estimates that the list takes less than 1% of the disk.
Direktoriji i razrješenje putanje
Directory (direktorij) je datoteka sa zapisima o drugim datotekama: imenom i, ovisno o metodi, početkom i duljinom, prvim blokom, blokom indeksa ili brojem inodea. Direktoriji tvore directory tree (stablo direktorija), a datoteka se imenuje path (putanjom) od korijena; relativna putanja polazi od working directory (radnog direktorija). Svaka razina putanje košta čitanje: za /home/ana/biljeske.txt čitaju se blokovi direktorija /, home i ana te inodei home, ana i same datoteke, pa razrješenje košta šest čitanja, a podaci jedno. Zato jezgra drži inodee i blokove direktorija u memoriji (postavka „Inodei direktorija u memoriji”). Kako do ovog čitanja dolazi sistemski poziv, vidi Sistemski pozivi; kako zahtjev za blok ide do diska, Upravljački programi, Raspoređivanje diska i Put jednog poziva, a zalihost i priručnu memoriju diska RAID i priručna memorija.
Directories and pathname resolution
A directory is a file of entries about other files: the name and, depending on the method, the start and the length, the first block, the index block or the inode number. Directories form a directory tree, and a file is named by its pathname from the root; a relative pathname starts from the working directory. Every level of the pathname costs a read: for /home/ana/biljeske.txt the directory blocks of /, home and ana are read, together with the inodes of home, ana and the file itself, so resolving the pathname costs six reads and the data one. That is why the kernel keeps inodes and directory blocks in memory (the setting “Directory inodes in memory”). For how a system call leads to this read, see System calls; for how the request for a block reaches the disk, Device drivers, Disk scheduling and Journey of a call; and for redundancy and the disk cache, RAID and disk cache.
Literatura: Stallings, Operating Systems: Internals and Design Principles, 9. izd., pogl. 12 File Management: 12.4 File Directories, 12.7 Secondary Storage Management (metode alokacije i upravljanje slobodnim prostorom), 12.8 UNIX File Management (inode); alternativno Tanenbaum & Bos, Modern Operating Systems, pogl. 4 File Systems: 4.2 Directories, 4.3.2 Implementing Files (contiguous allocation, linked-list allocation, FAT, i-nodes), 4.3.3 Implementing Directories, 4.4.1 Disk-Space Management.Reading: Stallings, Operating Systems: Internals and Design Principles, 9th ed., ch. 12 File Management: 12.4 File Directories, 12.7 Secondary Storage Management (allocation methods and free space management), 12.8 UNIX File Management (inode); alternatively Tanenbaum & Bos, Modern Operating Systems, ch. 4 File Systems: 4.2 Directories, 4.3.2 Implementing Files (contiguous allocation, linked-list allocation, FAT, i-nodes), 4.3.3 Implementing Directories, 4.4.1 Disk-Space Management.