Descreva as vantagens e desvantagens das técnicas para gerência de espaços livres.

Sistema de Arquivos

1 Introdu��o

O Sistema de Arquivos � o modo como as informa��es s�o armazenadas nos dispositivos f�sicos de armazenamento, exemplo Disco R�gido, disquete, pendrive, etc...

O Sistema de Arquivos � a parte mais vis�vel de um Sistema Operacional, pois a manipula��o de arquivos � uma atividade freq�entemente realizada pelos usu�rios, devendo sempre ocorrer de maneira uniforme, independente dos diferentes dispositivos de armazenamento.

2 Arquivos

Os arquivos s�o constitu�do de informa��es logicamente relacionados, podendo representar programas ou dados, ou melhor, � um conjunto de registros definidos pelo sistema de arquivos.

Um arquivo pode ser identificado por um nome, com formato e extens�o m�xima variando conforme o sistema operacional.

Alguns Sistemas Operacionais definem o arquivo em duas partes, possibilitando a identifica��o do seu tipo atrav�s da segunda parte, como exemplo: MeuPrograma.exe (execut�vel), MeuTexto.txt (arquivo texto), MinhaClasse.Java (arquivo texto, fonte de um programa Java).

2.1 Organiza��o dos Arquivos

A organiza��o dos arquivos consiste no modo como os dados est�o internamente armazenados, podendo, sua estrutura, variar em fun��o do tipo de informa��o contida no arquivo.

A forma mais simples de organiza��o � atrav�s de uma seq��ncia n�o estruturadas de bytes. A aplica��o deve definir toda a organiza��o, com vantagem da flexibilidade, por�m de inteira responsabilidade da aplica��o.

Alguns Sistemas Operacionais estabelecem diferentes organiza��es de arquivos e cada arquivo deve seguir a um modelo suportado.

As organiza��es mais conhecidas e implementadas s�o a seq�encial, relativa e indexada.

2.2 M�todos de Acesso

Seq�encial:

• A grava��o de novos registros s� � poss�vel no final do arquivo.
• Exemplo : Fita magn�tica.

Acesso Direto:

• � mais eficiente que o seq�encial;
• Permite a leitura/grava��o de um registro diretamente na sua posi��o atrav�s do n�mero do registro, que � a posi��o relativa ao in�cio do arquivo.
• N�o existe restri��o � ordem em que os registros s�o lidos ou gravados, sendo sempre necess�rio especificar o n�mero do registro.
• Poss�vel apenas quando o arquivo � definido com registros de tamanho fixo.

Acesso Direto + Acesso Seq�encial:

• Poss�vel acessar diretamente um registro qualquer de um arquivo, e, a partir deste, acessar seq�encialmente os demais.

Acesso Indexado ou Acesso por Chave:

• � o mais sofisticado dos m�todos;
• Tem como base o acesso direto;
• O arquivo deve possuir uma �rea de �ndice onde existam ponteiros para os diversos registros.
• Quando a aplica��o deseja acessar um registro, dever� ser especificada uma chave atrav�s da qual o sistema.pesquisar�, na �rea de �ndice, o ponteiro correspondente, a partir disso, acessando diretamente o arquivo.

2.3 Opera��es de Entrada/Sa�da

Realizadas atrav�s de System Calls, que fornecem uma interface simples e uniforme entre a aplica��o e os diversos dispositivos, permitindo leitura/grava��o, cria��o/elimina��o de arquivos.

2.4 Atributos

Os atributos s�o informa��es de controle dos arquivos que variam dependendo do Sistema Operacional, por exemplo: tamanho, prote��o, identifica��o do criador e data e hora de cria��o;

Alguns atributos espec�ficos s�o alterados apenas pelo pr�prio Sistema Operacional, como data e hora de cria��o, tamanho e outros podem ser alterados pelo usu�rio como prote��o.

3 Diret�rios

A organiza��o por diret�rios � o modo como o Sistema organiza logicamente os diversos arquivos contidos em um dispositivo f�sico de armazenamento.

O diret�rio cont�m entradas associadas aos arquivos onde s�o armazenadas informa��es como localiza��o f�sica, nome, organiza��o e demais atributos.

Ao abrir um arquivo, o Sistema Operacional procura a sua entrada na estrutura de diret�rios em uma tabela mantida na mem�ria principal, contendo todos os arquivos. � necess�rio fechar o arquivo ao t�rmino de seu uso.

N�vel �nico:

• Organiza��o mais simples de uma estrutura de diret�rios.
• Existe apenas um �nico diret�rio contendo todos os arquivos do disco.
• O nivel �nico � bastante limitado, n�o permitindo que usu�rios criem arquivos com mesmo nome.

Master File Directory (MFD):

• Existe um n�vel de diret�rio adicional para controlar os diret�rios individuais dos usu�rios.
• indexado pelo nome do usu�rio e, nele, cada entrada aponta para o diret�rio (UFD) pessoal.

Estrutura de diret�rios em �rvore:

• Existe o diret�rio MFD que � a ra�z, os galhos s�o os UFD e os arquivos s�o as folhas.
• Cada subdiret�rio abaixo do MDF pode conter arquivos e novos subdiret�rios e assim por diante.
• Quando se referencia a um arquivo, � necess�rio especificar seu nome, bem como o diret�rio onde ele se encontra, refer�ncia chamada PATH.
• Mais organizada e adotada pela maioria dos Sistemas Operacionais.
• Na maioria dos sistemas, diret�rios tamb�m s�o tratados como arquivos, com identifica��o de atributos, prote��o identifica��o do criador e data da cria��o.

4 Aloca��o de Espa�o em Disco

O Sistema Operacional possui uma estrutura de dados que armazena informa��es que possibilitam ao sistema de arquivos gerenciar as �reas ou blocos livres.

Nessa estrutura, geralmente uma lista ou tabela, � poss�vel identificar blocos livres que poder�o ser alocados por um novo arquivo.

Quando um arquivo � eliminado, todos os seus blocos s�o liberados para a estrutura de espa�os livres.

Mapa de Bits:

• Forma mais simples de implementar uma estrutura de espa�os livres;
• Cada entrada da tabela � associada a um bloco do disco representado por um bit que pode ser 0 (livre) ou 1 (ocupado).

• Existe uma lista encadeada de todos os blocos livres do disco;
• Cada bloco possui uma �rea reservada para armazenamento do endere�o do pr�ximo bloco;
• A partir do primeiro bloco livre pode-se ter acesso seq�encial aos demais de forma encadeada;
• Problema: para se achar espa�o livre, o algoritmo deve sempre realizar uma pesquisa seq�encial na lista.

Blocos Cont�guos:

• Blocos cont�guos s�o geralmente alocados ou liberados simultaneamente;
• Enxerga o disco como um conjunto de segmentos de blocos livres;
• Poss�vel manter uma tabela com o endere�o do primeiro bloco de cada segmento e o n�mero de blocos livres cont�guos que se seguem.

4.2.1 Aloca��o Cont�gua

A aloca��o cont�gua consiste em armazenar um arquivo em blocos seq�encialmente dispostos, permitindo ao sistema localizar um arquivo atrav�s do endere�o do primeiro bloco e da sua extens�o em blocos. O aceso � feito de maneira simples, tanto para a forma seq�encial quanto para a direta.

Um problema desse tipo de aloca��o � que quando um arquivo � criado com n blocos, � necess�rio que exista uma cadeia de n blocos livres disposto seq�encialmente. Nesse tipo de aloca��o, o disco � visto como um grande vetor, com segmentos ocupados e livres.

A aloca��o em um novo segmento livre consiste t�cnicas para escolha, algumas das principais s�o:

• First-fit: Seleciona o primeiro segmento livre com o tamanho suficiente para alocar o arquivo e a busca � feita seq�encialmente, interrompendo ao achar um segmento livre do tamanho adequado.
• Best-fit: Seleciona o menor segmento livre dispon�vel com o tamanho suficiente para armazenar o arquivo e � necess�ria a busca em toda a lista, caso esta n�o esteja ordenada por tamanho.
• Worst-fit: Seleciona o maior segmento livre e a busca funciona como no caso anterior.

Um problema na aloca��o cont�gua � a fragmenta��o dos espa�os livres causado pela cria��o e elimina��o constante de arquivos � que com o tempo surgem espa�os vagos sem o tamanho suficiente para se alocar novos arquivos.

A defragmenta��o busca solucionar o problema da fragmenta��o, reorganizando os arquivos no disco de maneira que s� exista um �nico segmento de blocos. A defragmenta��o � lenta e deve ser realizada periodicamente.

4.2 Aloca��o Encadeada

Na aloca��o encadeada um arquivo pode ser organizado como um conjunto de blocos ligados logicamente no disco, independente da sua localiza��o f�sica, sendo que cada bloco possui um ponteiro para o bloco seguinte do arquivo e assim sucessivamente.

Neste tipo de aloca��o, ocorre grande fragmenta��o dos arquivos devido aos blocos livres dos arquivos n�o precisarem ser cont�guos, existe a quebra do arquivo em diversos peda�os, denominados extents. Essa fragmenta��o aumenta o tempo de acesso aos arquivos, pois exige que o mecanismo de leitura/grava��o se desloque diversas vezes sob sua superf�cie. Dessa forma se torna necess�rio a execu��o da opera��o de defragmenta��o peri�dicamente

Um problema na aloca��o encadeada � que ela s� permite o acesso seq�encial aos blocos dos arquivos, n�o possuindo acesso direto aos blocos e desperdi�a espa�o nos blocos com o armazenamento de ponteiros.

4.3 Aloca��o Indexada

A aloca��o indexada soluciona o problema da aloca��o encadeada referente ao acesso direto aos blocos dos arquivos pois mant�m os ponteiros de todos os blocos do arquivo em uma �nica estrutura denominada bloco de �ndice.

5 Prote��o de Acesso

A prote��o de acesso aos arquivos visa possibilitar o compartilhamento seguro de arquivos entre usu�rios, quando desejado. Em geral, existe concess�o ou n�o de acessos como leitura, grava��o, execu��o e elimina��o.

Existem diferentes mecanismos de n�veis de prote��o. Alguns deles s�o:

Senha de Acesso:

• O sistema concede acesso a determinadosarquivos/diret�rios atrav�s de uma senha;
• Cada arquivo possui apenas uma senha e o acesso pode ter diversos n�veis de acesso
• Desvantagem de compartilhamento, pois al�m do dono, todos os demais usu�rios precisam conhecer a senha de acesso.

Grupos de Usu�rios:

• Existente em diversos Sistemas Operacionais;
• Associa cada usu�rio a um grupo de usu�rios que compartilham arquivos e diret�rios;
• Existe tr�s n�veis de prote��o: owner (dono), group (grupo) all (todos);
• Necess�rio associar o tipo do acesso (leitura, escrita, execu��o e elimina��o) aos tr�s n�veis de prote��o.

Lista de Controle de Acesso (Access Control List - ACL):

• Consiste em uma lista associada a cada arquivos, especificando usu�rios e tipos de acesso permitido;>
• O Sistema Operacional verifica se a lista de controle autoriza a opera��o desejada pelo usu�rio;
• A estrutura pode ter um tamanho bastante extenso considerando que um arquivo pode ter seu acesso compartilhado por diversos usu�rios;
• A pesquisa seq�encial na lista pode causar overhead.

6 Implementa��o de Caches

Um dos principais problemas para o desempenho do sistema � que o acesso � bastante lento comparado ao acesso a mem�ria principal. Para contornar este problema, s�o implementados nos sistemas operacionais sistemas de cache

O buffer cache � uma �rea da mem�ria que armazena informa��es de disco e busca minimizar o problema da lentid�o, pois ao se acessar o disco, se a informa��o desejada estiver no buffer cache, n�o ser� necess�rio o acesso ao disco. O tamanho do buffer cache � limitado, necessitando pol�ticas para substitui��o de blocos como FIFO ou Last Recently Used (LRU).

A falta de energia pode acarretar perda de dados que foram modificados no cache e n�o foram atualizados no disco. Neste caso, existem duas poss�veis solu��es:

• Solu��o 1: Atualizar periodicamente em disco todos os blocos modificados no cache;
• Solu��o 2: Atualizar imediatamente no disco toda a vez que os blocos s�o modificados no cache.

[voltar]

Quais são as vantagens e as desvantagens dos métodos para alocação de espaço em disco?

Quais as desvantagens que se pode ter ao armazenar arquivos sequencialmente?

O que é alocação contígua de blocos e quais os benefícios a desfragmentação pode proporcionar quando esta técnica é aplicada?

Qual a desvantagem da estratégia de alocação de arquivos Worst Fit?