Sistemas de ArchivosCecilia Hernndez2007-1

Sistemas de ArchivosConcepto simpleImplementa abstraccin para accesar almacenamiento secundario

Abstraccin : archivosProporciona organizacin lgica para accesar archivos en directorios

Normalmente directorio implementado como rbolesProporciona a usuarios mecanismos de proteccin y comparticin de archivos

Debe proporcionar semntica de consistencia para permitir acceso compartido

ArchivosArchivo es una coleccin de datos con algunas propiedadesContenido, tamao, dueo, ltima fecha de modificacin, proteccin, etcArchivos pueden tener tipos entendiblesSistema de archivos: archivo simple, directorio, enlaceOtras partes del SO, aplicaciones o bibliotecas

Ejecutable, biblioteca, cdigo fuente, etcTpicamente, tipos pueden incluidos en nombreEn Windows, tipo incluido en nombreEn unix, tipo especificado en los dos primeros bytes del archivo (magic numbers) o caracteres iniciales

Operaciones sobre archivoscreate(name)open(name, mode)read(fd, buf, len)write(fd, buf, len)sync(fd)seek(fd,pos)close(fd)unlink(name)rename(old, new)

DirectoriosOrganizar archivos en sistematil para usuariostil para sistema de archivos y usuarios para buscar y accesar archivosMayora de sistemas de archivos soportan mltiples niveles de directoriosCon jerarqua de nombresMayoria soport directorio actual y anteriorRutas absolutas y relativas

$cd /home/alumnos/pedro (absoluto)$cd tareas(relativo a dir actual)

Implementacin directoriosNormalmente un directorio es slo un archivo con metadatacon lista de archivos y atributos contenidos en actual directorio

Lista (nombre archivo, atributos archivo) Atributos pueden serTamao, proteccin, dueo, tiempo de creacin, tiempo de ltima modificacin, ubicacin en disco, etc

Implementacin de Sistemas de ArchivosComponentes de SAAdministracin de disco

Como organizar coleccin de bloques de discos en archivosNombres

Usuarios identifican sus archivos mediante nombres, abstrayndose de como se almacenan internamente (#cilindro, pista y sectores). Uso de nombres para archivos y directoriosProteccin

Como se protege la informacin de archivos en el sistema entre distintos usuarios y sistemaConfiabilidad/durabilidad/Rendimiento

Cuando sistema se cae, se pierde informacin en Memoria (caches), pero se desea que informacin de archivos no se pierda

Implementacin de Sistemas de ArchivoEstructuras en Disco y Memoria para implementar SAEn disco

Bloque Control de Buteo (Boot Control Block)Informacin para butear SO de particin (si existe en particin). Unix : Boot block, NTFS : Partition Block SectorBloque de Control de Particin (Partition Control Block)Detalles de particin: Tamao bloque, contador y punteros de bloques libres, contador y punteros de FCBs. Unix Superblock, NTFS : Tabla de Archivo Maestra (Master File Table). En Unix/linux llamado superblockEstructura de Directorios a usarFCB (File Control Block) Contiene informacin de archivo: dueo, tamao, permisos, punteros a bloques de disco, etc Unix Inodo, NTFS, info guardada en Tabla de Archivo Maestra

Implementacin de Sistemas de Archivos cont.Estructuras en MemoriaTabla de Particiones

Tabla con informacin acerca de cada particinEstructura de directorios

Tabla de directorios accesados recientemente con su informacinTabla de Archivos Abiertos a nivel de Sistema (TAAS)

Contiene copia de los FCBs de cada archivo, y otra informacion como nmero de Procesos que tiene archivo abiertoTabla de Archivos Abiertos a nivel de Proceso (TAAP)

Contiene puntero a entrada a tabla de archivos abiertos de sistema

Particiones de disco Caso Unix/linuxCada particinboot block, puede subir sistema cargando programa residente aquiSuperblock. Especifica los lmites de las reas siguientes, contiene punteros a listas de inodos libres y bloques de archivos libresArea de inodos. Contiene descriptores (inodos) para cada archivo en el disco. Todos los inodes son del mismo tamaoDir root. Inodo y directorio rootArchivos y directorios. Bloques de se usan para Una particin puede usarse para un sistema de archivos o como area de swapping ( en este caso es slo bloques para respaldo)

Proceso de buteoCaso Unix/linuxCPU ejecuta cdigo residente en ROM BIOS (Read Only Memory Basic Input Output System)Cdigo verifica y prepara HW de sistemaCarga programa (master boot program o boot loader) ubicado en sector 0 (Master Boot Record) de disco

En linux puede ser lilo o grub, los que permiten elegir una particin a subirContiene programa ejecuta SO en particinEstos boot loaders estn en MBR o en primer sector de parcicin activaCon programas Lilo o Grub es posible definir varias particiones con diferentes SOs

Aunque tambien sirven para usar el mismo sistema de archivos pero identificar diferentes SO (asociados a diferentes linux kernels)

Sistema de Archivos Unix (UFS)Sistema de Archivos original en Unix (1970)Disco dividido en particionesUna particin: grupo de cilindros adyacentesUn sistema de archivos puede residir en una particinBIOS define sector de buteo (boot sector) para estar en cabeza 0, cilindro 0, sector 1Master Boot Record (MBR) usado para butear computadorSabe de boot loader y tabla de particionesTabla de particinDefine direcciones de inicio y fin de cada particinUna particin es marcada como activaCuando sistema subeBIOS ejecuta MBRMBR localiza particin activa y ejecuta bloque de buteo

Para que usar particiones?Dividir el disco para diversos propsitosTener diversos SOs cargados uno en cada particinSOs y sistemas de archivos pueden ser usados en forma independiente

Respaldos o cualquier uso que quiera darle el usuario

Crear, Abrir y Usar un ArchivoCrearSO busca en bloque de control de particin por un puntero de un FCB no usadoSO suma puntero de FCB en la estructura del directorio. AbrirBuscar si archivo esta abierto en TAAS, si no esta Buscar en directorios por nombre de archivo Copiar informacin de FCB a la TAASSumar una entrada para el archivo en la TAAP, que contiene puntero a TAASSA retorna descriptor de archivo o handle a proceso que lo abreUsarEscribir, buscar el bloque de control de particin por punteros a bloques de disco vacosLeer. buscar en FCB bloques a leer

Usando Disco para Almacenar ArchivosSA almacena archivos en bloquesDefine tamao de bloque, en general entre 1KB y 4KBExiste un Bloque Maestro que define la ubicacin del directorio root

Siempre una ubicacin bien conocidaEn general replicada para proporcionar mayor disponibilidadPosee una lista con bloques libres y bloques ocupados

En general, bitmap, define un bit por bloque de disco1 si esta ocupado, 0 si esta libreAlmacenada en disco y en memoria (para aumentar rendimiento)SO usa Caching

SO mantiene cache con bloques de disco usados mas recientemente (disminuir latencia de acceso a disco)

Registro de Bloques Asignado a ArchivosEstructura de datos comnEncabezado de archivo: cada archivo posee uno

Que bloques de disco estan siendo ocupados por archivoDistintas implementaciones: Como se sabe que bloques pertenecen a que archivos

Asignacin contiguaArchivos enlazadosArchivos indexadosArchivos indexados en mltiples niveles

Asignacin ContiguaUsuario dice por adelantado tamao de archivoSO busca en bitmap (usando criterio) bloques de disco que satisfacen requerimiento de usuarioEl encabezado de archivo poseePrimer sector de bloque en discoTamao de archivo en trminos de nmero de sectoresVentajas/Desventajas+ Acceso secuencial rpido+ Acceso aleatorio fcil- Fragmentacin externa- Difcil cuando archivo crece ms de lo definido originalmente

Archivos EnlazadosCada bloque de disco incluye puntero al siguiente bloque de discoEncabezado de archivo posee direccin del primer bloque de discoVentajas/Desventajas

+ Archivos pueden crecer dinmicamente- Acceso secuencial no es tan bueno, pero mejor que aleatorioRequiere tiempo de bsqueda de prximo bloque - Acceso aleatorio muy lento- No es confiable, que pasa si se pierde o se estropea un bloque?MS-DOS FAT (File Allocation Table) usa esta filosofa, pero implementacin mediante una tablaMejor rendimiento, sobretodo si tabla esta en memria

Archivos IndexadosUsuario especifica tamao mximo de archivoSA define un arreglo de punteros a bloques acorde al tamao mximoEncabezado de archivo posee arreglo de punteros de bloques (index block: contiene punteros a los bloques de disco del archivo)Ventajas/Desventajas

+ Tamao de archivo puede crecer fcilmente hasta mximo+ Acceso aleatorio es rpido- Costoso si archivo crece sobre mximo- Acceso secuencial lento, ya que bloques pueden estar distantes unos de otros en disco

Archivos Indexados con Mltiples NivelesObjetivoRpido para archivos pequenos y permitir archivos grandesEncabezado de archivo posee 13 punterosTabla de punteros de tamao fijo, aunque no son todos equivalentesPrimeros 10 (ahora 12) punteros direcccionan bloques de datosPuntero dcimo primero (11) (ahora 13): Puntero indirecto

Apunta a bloque de punteros de bloques de datosPuntero dcimo segundo (12) (ahora 14): Puntero doblemente indirecto

Apunta a bloque de punteros, los que a su vez contienen punteros a bloques de datosPuntero dcimo tercero (13) (ahora 15): Puntero triplemente indirecto

Apunta a bloque de punteros, los que a su vez contienen punteros a bloques de punteros, los que contienen punteros a bloques de datos

Archivos Indexados con Mltiples NivelesUnix implementa este mecanismoVentajas/Desventajas

+ Simple+ Archivos pueden crecer fcilmente (tamao max relativamente grande)+ Archivos pequeos rpidos- Archivos grandes penalizados en tiempo de bsqueda, por el uso de indireccin de mltiples niveles- Mucho tiempo usado en bsqueda de bloques (cuando archivos son grandes)

Ejemplo FATEntrada directorio

3510325200EOF

Ejemplo Inodos Unix (tambin en FFS)Inodo estructura de datos que contiene dueo archivo, modo, tamao, proteccin, contadores de enlaces y tabla de asignacin de bloques de disco

Ejemplo InodosEn el SA Unix, con archivos indexados con multiples niveles, con encabezado de archivo de 13 entradas, 10 entradas para direccionar bloques directamente, 1 entrada indirecta, 1 entrada doblemente indirecta y 1 triplemente indirecta. Si el tamao de bloque es de 1KB. Calcule:Mximo tamao de archivo posibleNmero de accesos a disco son necesarios para alcanzar bloque 23, cuales son?

Ejemplo con i-nodos y bsqueda en directorios

Ejemplo Traduccin Rutas con InodosArchivos directorios: archivos en que cada entrada contiene archivo o directorio y adems Inodo donde esta ubicadoArchivo /home/juan/tarea.txt. Archivo directorio / contiene lista archivos/directorio con sus InodosDirectorio home tiene Inodo 100Inodo 100 contiene puntero a bloques donde esta home: bloque 200Bloque 200 : archivo directorio home posee inodo para juan: inodo 110Inodo 110 contiene puntero a bloques donde esta juan: bloque 300Bloque 300 : archivo diretorio juan posee inodo para tarea.txt: inodo 120Inodo 120 contiene punteros a bloques donde esta tarea.txt: bloques 400, 401 y 402

Ubicacin de inodosUnix original tena dos problemas de desempeo importantesBloques de datos en cualquier parte del disco

Cuando archivo es nuevo se buscan bloques de archivos Cuando SA envejece y se llena necesita ubicar nuevos archivos mientras otros han sido borradosArchivos de diferentes tamaosBloques para archivos nuevos empiezan a estar dispersos en el discoInodos estn ubicados lejos de los bloques de disco

Todos los inodos al inicio del disco y luego los bloques de discoBsqueda de archivos en directorios requiere referencias a inodos y bloques de disco, como estan lejos unos de otros ms tiempo es requerido para su acceso

Mejorando desempeoUso de Buffer cacheExplotar localidad usando memoria como cache para archivos

Cache es compartida por todos los procesosMuchos sistemas de archivos leen por adelantado (antes que se necesite) a buffer cache Caching escriturasNecesario manejar consistencia en algunos casos se requiere write-throughAlgunos problemas con el buffer cache

Competencia de pginas con la administracin de memoriaTambin requiere algoritmos de reemplazoUsualmente LRU

Proteccin de archivosProteccin usada paraControlar quien tiene acceso a qu archivoControlar el tipo de acceso que un usuario puede realizar sobre archivoEn forma generalGeneralizar archivos a objetos Generalizar usuarios a principalesGeneralizar lectura/escritura a accionesUn sistema de proteccin dice si una determinada accin realizada por un determinado principal en un deteminado objeto debera ser permitidaUsuario dueo puede leer/escribir sobre archivo, pero no otrosUsuario puede leer algn archivo de sistema, pero no escribirlo

Modela para representar proteccinDos maneras de verloListas de control de acceso (ACLs)

Para cada objeto, guardar una lista de los principales y las acciones permitidas para principalesCapacidades

Para cada principal, guardar una lista de los objetos y acciones permitidas para principalesRepresentacin en siguiente matriz

principalesobjetosACLcapacidad

/etc/passwd/home/juan/home/otrorootrwrwrwjuanrrwrotror

ACLs y CapacidadesCapacidades son ms fcil de transferirComo llaves (caso casa)Facilitan comparticinACLs son ms fciles de manejarBasado en objetos, fcil de entregar y quitar

Quitar capacidades es ms difcil, hay que mantener historia de principales que han tenido capacidadDifcil de seguir, pues principales se pueden pasar capacidadesACLs se hacen grandes cuando objetos son muy compartidosEsquema puede simplificarse agrupando

Poner usuarios en grupos, poner grupos en ACLsCambiando acciones sobre grupos afecta al grupo completo

Consistencia del SALos i-nodos y los bloques de discos residen en buffer cache (memoria usada para cache de archivos)El comando sync fuerza la escritura en disco de la informacin de disco residente en memoria Sistema hace un sync cada unos pocos segundosUna cada del sistema o corte de energa entre syncs puede dejar el disco inconsistenteSe podra mejorar consistencia usando menos caching pero esto perjudicara el desempeo

Manejando consistencia de archivos(i-cache)Verificar que cada bloque este asociado slo a un archivoUn vector de bits, un bit por cada bloque en discoSeguir la lista de bloques libres e inodos libres

Cuando un bloque es encontrado, ver el bitSi bit == 0, ponerlo en 1Si bit == 1, Si bloque esta asociado a archivo y en lista de bloques libresEliminarlo de la lista de libres ( no garantia de lo que suceda)Si bloque est asociado a dos archivos error

Consistencia de directorios (d-cache)Verificar que directorios formen un rbolVerificar que el contador de links de un archivo sea igual al nmero de directorios que apuntan a archivo

Compartiendo archivos 1Enlaces durosUn archivo en Unix puede tener mltiples nombresNombre en entrada en el directorio es llamado enlace duro. Mltiples entrada en directorio apuntan a mismo inodoCada inodo tiene un campo count que indica el nmero de enlaces durosLlamada a sistema relacionadas link y unlinklink(nombre existente, nuevo nombre) crea nueva entrada en directorio con nombre dado e incrementa el count de inodoUnlink(nombre), destruye entrada en directorio, decrementa count, si count == 0 libera bloques de disco e inodo ocupado por archivo

Compartiendo archivosEnlace simblicoEnlace simblico entrada en directorio que contiene pathname a otro archivo en el SALlamada a sistema Symlink(nombre existente, nuevo nombre)Asigna nuevo inodo a nuevo archivo, nuevo archivo contienen path de archivo existente,Si antiguo archivo es eliminado, accesar nuevo archivo no ser posible

Comparticin de archivos 2Cada usuario tiene una tabla de canal o tabla de archivos abiertos por usuarioCada entrada en la tabla de archivos abiertos es un puntero a una entrada a la tabla de archivos abiertos del sistemaCada entrada en la tabla de archivos abiertos contiene un file offset y un puntero a una entrada en la tabla de inodos residentes en memoriaSi un proceso abre un archivo ya abierto se crea una nueva entrada en la tabla de archivos abiertos con un nuevo file offset apuntando a la misma entrada en la tabla de inodos residentes en memoriaSi un proceso hace un fork, el hijo obtiene una copia de la channel table ( y luego el mismo file offset)

Usuario 1Usuario 2Usuario 3channel tablechannel tablechannel tableopen file tablememory-resident i-node table

Algunos SAs popularesNTFS (Windows)Minix (No se usa tanto, pero disponible)UFSExt2fs: Ext2 (linux) estandar, basado en inodosExt3fs: Ext3 (linux). Journaling. Basado en otroVeritasFS (VxFS). Journaling o logging ReinserFS (linux) Journaling con logging. Completamente nuevo. Incluido en linux estandarJFS (de IBM). Journaling o logging. Basado en otroFFSXFS (de SGI). Journaling o logging. Basado en otrohttp://www.tldp.org/HOWTO/Filesystems-HOWTO.htmlLarga lista de sistemas de archivos

UFS (Sistema de Archivos Unix original)Layout en disco de UFSMetadata al principio en discoBloques de disco son asignados aleatoriamente a archivos sistema usado por largo tiempoCuando sistema nuevo, bloques asignados secuencialmente a archivosInodos lejos de bloques

Ubicacin de inodos y bloques de disco por archivo en UFSInodo contiene metadata de archivo incluyendo direcciones a bloques de discoTiempo de bsqueda malo, cabeza debe moverse entre cilindros distantes

FFS (Fast File System)Proyecto en Berkeley BSD FFS (1970)Idea es mejorar productividad y disminuir tiempo de respuestas de Unix Original (UFS)Idea se basa en conocimiento de layout en disco

Layout en disco en FFSGrupos de cilindrosTamaos de bloque de disco incrementado de 512 bytes a 4KBMejor soporte para archivos grandesPuede producir fragmentacin interna

Uso de fragmentos para solucionarla

FFSFFS (File Fast System) usa idea de grupos de cilindrosDisco particionado en grupos de cilindrosBloques de datos de un mismo archivo ubicado en el mismo grupo de cilindrosInodo de archivo ubicado en el mismo grupo de cilindrosIntroduce un requerimiento de espacio librePara poder hacer lo explicado arriba se necesita tener espacio libre disperso en todo el discoEn FFS se reserva el 10 % del disco para estar disponible

Sistemas de Archivos JournalingUFS y FFS usan memoria como cache para disco (buffer cache)UFS y FFS tienen problemas cuando sistema se caeEjemplo cada de sistema en la creacin de archivo

1 Asignacin de inodoApuntar en entrada de directorio inodo de archivoProblema de consistencia en estructuras de datos en memoria y discoUFS y FFS proporcionan utilitarios para reconstruir consistencia (fsck), pero muy lento

Debe verificar cada bloqueNo escalable (ms lento a medida que aumenta disco)

Sistemas de Archivos JournalingSe hicieron populares en 2002Varias opcionesExt3, ReinserFS, XFS, ntfsIdea bsicaActualizar metadatos y datos transaccionalmente

Los dos o ningunoEn caso de falla, puede perderse un proco de trabajo, pero disco queda consistente

En forma precisa, consistencia mediante uso de log o journal transaccional, en lugar de barrer cada bloque de disco para verificar estado

Almacenamiento de datosDatosEn buffer cacheEn discoIdea bsica de solucinSiempre dejar copia de datos en estado consistenteActualizar datos persistentemente escribiendo secuencialmente (tiempo) en archivo journalEn tiempo libre de sistema, hacer actualizaciones escritas en journal cronologicamente y liberar espacio de archivo journal

Redo logLogArchivo que se escribe slo al final conteniendo registros de logs

Start tTransaccin t ha empezadoT, x, vTransaccin T ha actualizado bloque x y su nuevo valor en vPuede loggear diferencia de bloques en lugar de bloquesCommit tTransaccin T ha committed actualizacin sobrevive caidaAccin de Commit incluye escribir registro redo

Si ocurre caida de sistemaRecupera LogRedo transacciones committedBarre el log en orden y reejecuta actualizaciones de las transacciones committedEscrituras son idempotent (slo ocurre una vez independiente del nmero de veces que se ejecute)Transacciones no committed Ignorarlas

Como si caida ocurriera antes de commit

DesempeoLog es una escritura continuaEscritura eficienteEn lugar de varias escrituras asincrnicasCostosas en trminos de desempeoJournalingBueno, eficienteManejo de consistencia y recuperacin eficiente

Detalles sobre buffer cacheCompartido por todos los procesosUtiliza algoritmo de reemplazamiento Tpicamente LRUIncluso una cache pequea puede ser efectiva (4MB)Hoy tenemos memorias grandes por lo que podemos tener caches mas grandesMuchos sistemas de archivos leen por adelantado a la cache, aumentando su efectividad

Escrituras y lecturas en buffer cacheUsuarios y aplicaciones asumen que datos estn en disco despus de una escrituraEn realidad, no necesariamente, para eso se usa cacheSistema de archivos puede quedar inconsistente en caso de falla si datos y metadatos no estn consistentes en discoMantener consistencia es caraAlgunos enfoquesWrite through lo que se escribe en buffer cache se escribe en disco (escritura sincrnica)Write behind mantener cola de bloques no escritos, periodicamente escribir en disco (no es confiable)NVRAM: escribir en una RAM energizada y mas tarde en disco (NVRAM es cara)

Lecturas vs escriturasLecturas se ven beneficiadas con buffer cache grandesEscrituras son un problemaCualquier estrategia debe incluir escritura a disco en algn momentoLuego trfico a disco esta dominado por escriturasEscribir inodos y bloques de datos incluye movimiento de cabeza en disco (caro en tiempo) y transferencia de datos.

Log-Structured File System(LFS)Diseado por avances enDiscos grandes y creciendo cada aoDisponibilidad de grandes memorias

Buffer cache puede ser mas grandePuede manejar mas bloques de disco en MemoriaIdea de LFS es tratar el disco como un log cuyas operaciones se agregan en el tiempo

Coleccionar escrituras en el buffer cache y escribir un conjunto de escrituras al discoToda la informacin escrita en disco se realiza en el log Recuperacin en base a checkpoints (tratar el disco como bases de datos)

Idea LFSUsar disco como un logSi disco es manejado como log, no habra costo de bsquedaNuevos datos y metadatos (inodos y directorios) son acumulados en buffer cache, luego escritos todos al mismo tiempo en bloques grandes (segmentos de 0.5 M 1 MB)Mejora utilizacin de disco

Comparacin entre FFS y LFSarchivo1archivo2dir1dir2FFS

archivo1archivo2dir1dir2LFSLoginode

directorio

datos

Map inode2 archivos de 1 bloque:dir1/archivo1dir2/archivo2

Desafos y solucionesUbicando datos en el logFFS pone los datos y metadatos en lugares conocidos en el disco LFS escribe datos y metadatos al final del log

LFS usa una map de inodosMapea archivo con ubicacin de inodo para archivo en un lugar bien definidoManejando espacio libre en el logDisco es finito, luego log tambien es finitoNo se puede seguir agregando en log infinitamente

Se necesita recuperar bloques borrados en parte antigua de logLog organizado en segmentos grandes (0.5 1 MB)Cuando segmento se llena se escribe en discoCon el tiempo segmentos se fragmentan (nuevos y viejos bloques)Segmentos con pocos datos vlidos se recuperanDatos previamente copiados a final de log

LFS ProblemasSu implementacin no es tan simpleUbicando datos en log no es tan rpidaManejando espacio libre no es tan sencillo, no siempre se puede agregar info, cuando se elimina informacin deben recuperarse bloques escritos previamente en log

Manejo de fragmentacin de segmentos y limpieza es complicadoUso de demonio de limpieza encargado de verificar fragmentacin, compactacin y recuperacin

Comparacin entre FFS, JFS y LFSLFS y FFSCarga de trabajo por metadatos es cara

Incluye escritura pequeas (inodos ocupados y entradas en directorios)Problema de limpieza de segmentos en LFS es un problemaLFS y JFSJFS es robusto como LFS, pero metadata debe ser escrita en disco ms frecuentementeNo confundir JFS con LFS

JFS tiene log de transacciones a disco para manejar caidas y recuperacin ms rpido manejando consistencia en disco asincrnicamenteLFS el disco es visto como log