Come è implementato fseek() nel filesystem?

Question

Questa non è una pura domanda di programmazione, tuttavia influisce sulle prestazioni dei programmi che utilizzano fseek(), quindi è importante sapere come funziona. Un piccolo disclaimer in modo che non si chiuda.

Mi chiedo quanto sia efficiente inserire i dati nel mezzo del file. Supponendo di avere un file con dati da 1 MB e quindi inserisco qualcosa nell'offset di 512 KB. Quanto sarebbe efficiente rispetto all'aggiunta dei miei dati alla fine del file? Giusto per rendere completo l'esempio, diciamo che voglio inserire 16 KB di dati.

Capisco che la risposta varia a seconda del filesystem, tuttavia presumo che le tecniche utilizzate nei comuni filesystem siano abbastanza simili e voglio solo avere la nozione giusta.

Answer 1

(disclaimer: voglio solo aggiungere qualche accenno a questa discussione interessante) IMHO ci sono alcune cose da prendere in considerazione:

1) fseek non è un servizio di sistema primario, ma una funzione di libreria. Per valutare le sue prestazioni, è necessario considerare come viene implementata la libreria del flusso di file. In generale, la libreria I/O di file aggiunge uno strato di buffering nello spazio utente, quindi le prestazioni di fseek potrebbero essere piuttosto diverse se la posizione di destinazione è all'interno o all'esterno del buffer corrente. Inoltre, i servizi di sistema utilizzati dalla libreria I/O possono variare molto. Cioè su alcuni sistemi la libreria usa estesamente la mappatura della memoria di file, se possibile.

2) Come hai detto, diversi filesystem possono comportarsi in modo molto diverso. In particolare, mi aspetto che un filesystem transazionale debba fare qualcosa di molto intelligente e forse costoso da preparare a un possibile rollback di un'operazione di scrittura interrotta nel mezzo di un file.

3) I sistemi operativi moderni hanno algoritmi di caching molto aggressivi. È probabile che un file "fseeked" sia già presente nella cache, quindi le operazioni diventano molto più veloci. Ma possono peggiorare molto se l'intera attività del filesystem prodotta da altri processi diventa importante.

Eventuali commenti?

Answer 2

È possibile inserire dati nel mezzo del file in modo efficiente solo se la dimensione dei dati è un multiplo del settore FS, ma i SO non forniscono tali funzioni, quindi è necessario utilizzare l'interfaccia di basso livello per il driver FS.

Answer 3

Supponiamo che l'ext2 FS e il SO Linux siano un esempio. Non penso che ci sarà una significativa differenza di prestazioni tra un inserto e un'appendice. In entrambi i casi devono essere letti il ​​nodo file e la tabella offset, il relativo settore del disco viene mappato in memoria, i dati aggiornati e in un secondo momento i dati riscritti sul disco. Ciò che farà una grande differenza di prestazioni in questo esempio è una buona località temporale e spaziale quando si accede a parti del file poiché questo ridurrà il numero di combo di carico/archivio.

Come perverse risposte dice che si può essere in grado di velocizzare entrambe le operazioni se si affrontano i dati che scrivono esattamente i multipli della dimensione del blocco FS, in questo caso si può saltare la fase di caricamento e inserire semplicemente i nuovi blocchi nel file inode datastrucure. Questo non sarebbe pratico, avresti bisogno di un accesso di basso livello al driver di FS e utilizzarlo sarebbe molto restrittivo e non portatile.

Answer 4

L'inserimento di dati nel mezzo del file è meno efficiente dell'appendice alla fine perché quando si inserisce si dovrebbero spostare i dati dopo il punto di inserimento per fare spazio per i dati inseriti. Lo spostamento di questi dati comporterebbe la lettura da disco, la scrittura dei dati da inserire e quindi la scrittura dei vecchi dati dopo i dati inseriti. Quindi hai almeno una lettura in più e scrivi quando inserisci.

Answer 5

fseek(...) è una chiamata di libreria, non una chiamata di sistema del sistema operativo. È la libreria run-time che si prende cura del sovraccarico effettivo coinvolto nel fare una chiamata di sistema al sistema operativo, tecnicamente parlando, fseek sta facendo indirettamente una chiamata al sistema, ma in realtà non lo è (questo fa emergere una chiara distinzione tra differenze tra una chiamata in biblioteca e una chiamata di sistema). fseek(...) è una funzione di input-output standard indipendentemente dal sistema sottostante ... però ... e questo è un grande però ...

Il sistema operativo sarà più che probabile di avere nella cache il file nella sua memoria del kernel , cioè, l'offset diretto alla posizione sul disco su cui sono memorizzati gli 1 e gli 0, è attraverso i livelli del kernel del sistema operativo, più che probabile, uno strato superiore all'interno del kernel che avrebbe l'istantanea di ciò che il file è composto da, cioè dati indipendentemente da ciò che contiene (non gli interessa in alcun modo, purché i 'puntatori' alla struttura del disco per quell'offset alla lcoation sul disco siano validi!) ...

Quando si verifica fseek(..), lì d un sacco di overhead, indirettamente, il kernel ha delegato il compito di leggere dal disco, a seconda di quanto sia frammentato il file, potrebbe essere teoricamente "tutto il posto", che potrebbe essere un significativo overhead in termini di dover, dal punto di vista dell'utente-terra, cioè il codice C che fa un fseek(...), potrebbe spargersi dappertutto per raccogliere i dati in una "vista contigua dei dati" e quindi, inserendo nel al centro di un file, (ricorda in questa fase, il kernel dovrebbe regolare la posizione/gli offset nel piatto del disco effettivo per i dati) sarebbe considerato più lento di accodare alla fine del file.

La ragione è molto semplice, il kernel "sa" che cosa era l'offset scorso è stata, e semplicemente pulire il marcatore EOF e inserire più dati, dietro le quinte, il kernel, si trova a dover allocare un altro blocco di memoria per il buffer del disco con l'offset corretto per la posizione sul disco che segue un indicatore EOF, una volta completata l'aggiunta dei dati.

Answer 6

Un'osservazione che ho effettuato su fseek su Solaris è che ogni chiamata ripristina il buffer di lettura dello FILE. La prossima lettura leggerà quindi un blocco completo (8K di default). Quindi, se hai un sacco di accesso casuale con le letture piccole, è una buona idea farlo senza buffer (setvbuf con il buffer NULL) o utilizzare anche le syscalls dirette (lseek + read o anche meglio pread che è solo 1 syscall invece di 2). Suppongo che questo comportamento sarà simile su altri sistemi operativi.