Swapping      A técnica de swapping veio para tentar resolver o problema de insuficiência de memória para todos os usuários. Nos esquemas apresentados até o momento, um processo permanecia na memória principal até o final de sua execução, inclusive quando realizava operações de entrada e saída.      O swapping é uma técnica aplicada à gerência de memória, para processos que esperam por memória livre para serem processados.O sistema escolhe um processo residente que é levado da memória para o disco (swapped out), retornando posteriormente para amemória principal (swapped in), como se nada tivesse ocorrido. Um dos problemas gerados pelo swapping é a relocação dos processos.O loader realocável permite que um processo seja colocado em qualquer posição de memória, porém a relocação é realizada no momento do carregamento.       O conceito de swapping permitiu um maior compartilhamentodememória e, conseqüentemente, um maior throughput. Mostrou-se eficiente em ambientes onde existiam poucos usuários competindo pela memória e com aplicações pequenas. Seu maior problema é o custo das operações de entrada e saída.

Memória virtual é uma técnica sofisticada e poderosa de gerência de memória onde as memórias principal e secundária são combinadas, dando ao usuário a impressão de que existe muito mais memória do que a capacidade real de memória principal. O conceito de memória virtual baseia-­se em não vincular o endereçamento feito pelo programa aos endereços físicos da memória principal. Desta forma, o programa e suas estruturas de dados deixam de estar limitados ao tamanho da memória física disponível, pois podem possuir endereços vinculados à memória secundária, que funciona como uma extensão da memória principal. Outra vantagem desta técnica é permitir um número maior de processos compartilhando a memória principal, já que apenas partes de cada processo estarão residentes. Isto leva a uma utilização mais eficiente do processador, além de minimizar (ou quase eliminar) o problema da fragmentação. A seguir, os conceitos que envolvem a gerência de memória virtual, incluindo a paginação: ­ - Espaço de endereçamento virtual:  o conjunto de endereços virtuais que um processo pode endereçar. - Espaço de endereçamento real: analogamente, é o conjunto de endereços reais que um processo pode endereçar. ­ - Mapeamento: como o espaço de endereçamento virtual não tem nenhuma relação com o espaço de endereçamento real, um programa pode fazer referência a um endereço virtual que esteja fora dos limites da memória principal (real), ou seja, os programas e suas estruturas de dados não estão mais limitados ao tamanho da memória física disponível. Quando um programa é executado,  apenas uma parte do seu código fica residente na memória principal, permanecendo o restante na memória virtual até o momento de ser referenciado. Este esquema de endereçamento virtual é ignorado pelo programador no desenvolvimento das aplicações.  Cabe ao compilador e ao linkeditor gerar códigos executáveis em função do endereçamento virtual, e o sistema operacional se incumbe de administrar os detalhes durante a sua execução. O processador apenas executa instruções e referencia dados residentes no espaço de endereçamento real. Portanto, deve existir um mecanismo que transforme os endereços virtuais em endereços reais. Este mecanismo é o que chamamos de mapeamento, e consiste em permitir a tradução do endereço virtual em endereço real. Como conseqüência, um programa não mais precisa estar necessariamente em endereços contíguos na memória real para ser executado. ­ - Tabela de endereçamento de páginas: estrutura mantida pelo sistema para armazenar, entre outras informações, o mapeamento. É única e exclusiva para cada processo, relacionando os endereços virtuais do processo ás suas posições na memória real. ­ - Memória virtual por paginação: é a técnica de gerência de memória onde o espaço de endereçamento virtual e o espaço de endereçamento real são divididos em blocos do mesmo tamanho chamados páginas. As páginas do espaço virtual são chamadas páginas virtuais, enquanto as páginas do espaço real são chamadas páginas reais ou frames. ­ - Page fault: é a falha de página. Sempre que o processo referencia um endereço virtual, o sistema verifica se a página correspondente já está carregada na memória real. Se não estiver, acontece o page fault. Neste caso, o sistema deve transferir a página virtual para um endereço na memória real. Esta transferência é chamada de paginação. O número de page faults gerados por um processo em um determinado intervalo de tempo é chamado de taxa de paginação do processo. Se esta taxa atingir valores elevados, pode haver um comprometimento do desempenho do sistema. Um page fault provoca uma interrupção no processo, pois há a necessidade de acessar operações de E/S. Assim, sempre que acontece a paginação, uma interrupção de E/S fará com que o processo em execução seja interrompido e colocado em estado de espera até que sua intervenção de E/S seja realizada, quando então o processo voltará à fila de pronto e entrará em execução de acordo com o escalonamento normal. Enquanto o sistema trata a interrupção deste processo, um outro ocupará a CPU. - Working­set: é o conjunto de páginas de um processo, em memória real, em um determinado instante. Este conceito surgiu com o objetivo de reduzir o problema do thrashing e está relacionado ao princípio da localidade. Existem dois tipos de localidade que são observados durante a execução da maioria dos programas. A localidade espacial é a tendência de que, após uma referência a um endereço de memória, sejam realizadas novas referências a endereços próximos ou adjacentes. A localidade espacial é a tendência de que, após a referência a uma posição de memória, esta mesma posição seja referenciada novamente num curto intervalo de tempo. A partir desse princípio de localidade, o processador tenderá a concentrar suas referências a um conjunto de páginas do processo durante um determinado período de tempo. Imagine um loop principal de um programa que ocupe três páginas. A tendência é que estas três páginas tenham um alto índice de referências durante a execução do programa. ­ - Thrashing: é o efeito causado pelo excesso de page faults durante a execução de um processo. Pode acontecer a nível de programa ou de sistema. A nível de programa, pode ser provocado por um programa mal escrito, com desvios incondicionais espalhados por seu código (desobedecendo portanto aos princípios da localidade), ou por um limite de working­set muito pequeno (que não comporte o loop principal do programa, por exemplo). A solução para estes casos é reescrever o programa ou aumentar o limite do working­set. No caso de thrashing de sistema, significa que há mais páginas sendo requeridas na memória real do que ela pode realmente suportar. A solução é aumentar o tamanho da memória física. ­ - Tamanho da página: deve estar entre 512 bytes e 128KB, aproximadamente. Páginas menores promovem maior compartilhamento da memória, permitindo que mais programas possam ser executados. Páginas maiores diminuem o grau de compartilhamento da memória, com menos programas disputando o processador. Assim conclui-­se que quanto menor o tamanho da página, MAIOR é o grau de compartilhamento da memória e da CPU. ­ - Políticas de busca de páginas: definem como as páginas serão carregadas da memória virtual para a memória real. A política por demanda estabelece que uma página somente será carregada quando for referenciada. Este mecanismo é conveniente, pois leva para a memória real somente as páginas realmente necessárias à execução do programa, ficando as outras na memória virtual. A outra política, chamada paginação antecipada, funciona carregando antecipadamente várias páginas da memória virtual para a principal, na tentativa de economizar tempo de E/S. Nem sempre o sistema acerta na antecipação, mas o índice de acertos é quase sempre maior que o de erros. ­ - Políticas de alocação de páginas: determinam quantos frames cada processo pode manter na memória real. A política de alocação fixa determina um limite de working­set igual para todos os processos, e pode ser vista como uma política injusta, na medida em que processos maiores normalmente necessitam de um working­set maior. A outra política é a variável, que define um limite de working­set diferente e variável para cada processo, em função de seu tamanho, taxa de paginação ou até mesmo da taxa de ocupação da memória principal. 4 ­ Políticas de substituição de páginas: definem onde serão trocadas as páginas, quando se fizer necessária uma substituição. Na política local, somente as páginas do processo que gerou o page fault são candidatas a serem substituídas.Já na política global, todas as páginas alocadas na memória principal são candidatas à substituição, independente do processo que gerou o page fault. Como uma página de qualquer processo pode ser escolhida, pode ser que este processo sofra um aumento temporário da taxa de paginação em função da diminuição das suas páginas alocadas em memória.

ALOCAÇÃO CONTÍGUA DE MEMÓRIA A alocação contígua consiste em armazenar um arquivo em blocos sequencialmente 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 sequencial 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 sequencialmente. 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.   ALOCAÇÃO NÃO-CONTÍGUA DE MEMÓRIA  Paginação: A paginação permite que o programa possa ser espalhado por áreas não contíguas de memória. Com isso, o espaço de endereçamento lógico de um processo é dividido em páginas lógicas de tamanho fixo e a memória física é dividida em páginas com tamanho fixo, com tamanho igual ao da página lógica. Nisso, o programa é carregado página a página, cada página lógica ocupa uma página física e as páginas físicas não são necessariamente contíguas. O endereço lógico é inicialmente dividido em duas partes : um número de página lógica (usado como índice no acesso a tabela de páginas, de forma a obter o número da página física correspondente) e um deslocamento dentro da página. Não existe fragmentação externa, porém existe fragmentação interna (Ex: um programa que ocupe 201kb, o tamanho de página é de 4 kb, serão alocadas 51 páginas resultando uma fragmentação interna de 3kb). Além da localização a tabela de páginas armazena também o bit de validade, (1 ou TRUE) se a página está na memória (0 ou FALSE) se a página não está na memória. E a transferência das páginas de processo podem ser transferidas para a memória por demanda, levando apenas o que é necessário para a execução do programa ou por paginação antecipada, onde o sistema tenta prever as páginas que serão necessárias à execução do programa. Abaixo um exemplo de páginas constantemente referenciadas:   Segmentação: Técnica de gerência de memória onde programas são divididos em segmentos de tamanhos variados cada um com seu próprio espaço de endereçamento. A principal diferença entre a paginação e a segmentação é a alocação da memória de maneira não fixa, a alocação depende da lógica do programa. O mapeamento é feito através das tabelas de mapeamento de segmentos e os endereços são compostos pelo número do segmento e um deslocamento dentro do segmento. Cada entrada na tabela mantém o endereço físico do segmento, o tamanho do segmento, se ele está ou não na memória e sua proteção. Para isso ocorrer sem problemas, o sistema operacional mantém uma tabela com as áreas livres e ocupadas da memória e somente segmentos referenciados são transferidos para a memória principal. Nesse modelo diferentemente da Paginação, ocorre fragmentação externa. Abaixo um exemplo de Segmentação:

Sistema de Arquivos               O sistema de arquivos é a parte do sistema operacional mais visível para os usuários. Durante o tempo todo, usuários manipulam arquivos contendo textos, planilhas, desenhos, figuras, jogos, etc. Os arquivos são normalmente implementados a partir de discos magnéticos. Como um acesso a disco demora cerca de 10000 vezes mais tempo do que um acesso à memória principal, são necessárias estruturas de dados e algoritmos que otimizem os acessos ao disco. É importante observar que os sistemas de arquivos implementam um recurso em software que não existe no hardware. O hardware oferece simplesmente espaço em disco, na forma de setores que podem ser acessados (gravados e lidos) individualmente, em ordem aleatória. O conceito de arquivo, muito mais útil que o simples espaço em disco, é uma abstração criada pelo SO.     Um arquivo pode ser genericamente definido como uma coleção de dados relacionados entre si. Normalmente, arquivos contém programas (tanto fonte como objeto) ou dados.             Arquivos são referenciados através de nomes. Além de um nome, cada arquivo possui também outros atributos, tais como: tipo, momento da criação, identificação do criador, tamanho, etc.   Tipos de arquivos   Diferentes tipos de informação podem ser armazenados em um arquivo: programas fonte, programas objeto, texto, dados numéricos, registros de funcionários, som, imagem, etc. Cada arquivo possui uma estrutura interna, conforme sua aplicação. Por exemplo, um arquivo texto é uma seqüência de caracteres organizados em linhas e parágrafos; um programa executável é uma seqüência de bytes representando instruções em código de máquina; um programa fonte é uma seqüência de caracteres que representam comandos de uma linguagem de programação (normalmente estes arquivos são do tipo “somente texto”, não admitindo qualquer tipo de formatação especial).             Uma questão importante é até que ponto o SO deve conhecer a estrutura interna dos arquivos. Para ter esse conhecimento, o SO vai ser maior e mais complexo. Além disso, para evoluir, deverá permitir a definição de novos tipos de arquivos, uma vez que novas aplicações podem expor novas demandas, e com elas, tipo de arquivos diferentes. Isto inviabiliza a pretenção de conhecer a estrutura interna dos arquivos, na prática. Em geral, o conhecimento do SO se limita às informações contidas no registro descritor do arquivo. Isto já lhe permite bloquear algumas operações inválidas. Por exemplo, pode recusar-se a imprimir um arquivo que contenha um programa executável.     Sistemas baseados em fita   Os primeiros sistemas eram baseados em fita magnética. No início, cada arquivo era mapeado para uma única fita. Isso ocasionava um enorme desperdício de espaço, porque cada fita (de 2400 pés, cerca de 750 m) era capaz de armazenar 5 gigabytes, mas a maioria dos arquivos era pequena (alguns Kb). Por outro lado, havia o problema dos arquivos muito grandes, que poderiam superar a capacidade de uma única fita. O problema dos arquivos grandes foi resolvido com o sistema de armazenamento multi-volume. O desperdício de espaço foi resolvido permitindo a gravação de diversos arquivos em uma única fita. Como resultado, passou a ser necessário saber em que posição da fita cada arquivo estava armazenado. A solução foi adicionar à fita um diretório, onde cada entrada continha um nome de arquivo e sua posição na fita. Tais diretórios também armazenavam informações adicionais sobre os arquivos.   Passos para a leitura de um arquivo em fita:   Localizar e carregar a fita indicada pelo usuário Localizar no diretório a entrada correspondente ao arquivo Posicionar a fita no ponto correspondente ao início do arquivo Iniciar a leitura Terminar a leitura quando encontrar marca de fim de arquivo.               Para um programa poder trabalhar simultaneamente com dois arquivos, eles tinham que estar em fitas diferentes.   Sistemas baseados em disco   Muitos dos problemas dos sistemas de fita foram resolvidos com os sistemas baseados em discos. Um disco é dividido em trilhas, sendo o número de trilhas uma característica particular de cada dispositivo. Cada trilha é dividida em setores, sendo o setor a menor unidade de informação que pode ser lida ou escrita no disco. Unidades de disco fixo usualmente possuem diversos discos superpostos, cada um com duas faces magnetizadas, o que corresponde a diversas superfícies de gravação (a tecnologia atual permite sobrepor até 8 discos). Para acessar um determinado setor do disco é necessário informar: face, trilha e setor. As cabeças de leitura e gravação são deslocadas até a trilha correta (tempo de seek), chaveadas eletronicamente para a face correta e então esperam até que o setor solicitado passe por baixo (tempo de latência). Um cilindro é o conjunto de trilhas que estão na mesma posição, porém em diferentes faces. Não é necessário deslocar as cabeças para acessar trilhas de um mesmo cilindro.             Usualmente, o SO trata o disco como um grande vetor unidimensional de blocos, cada bloco correspondendo a um setor. Esses blocos são numerados desde 0 até N-1, onde N é o número de setores do disco.             A vantagem do disco em relação à fita é a possibilidade de acessar facilmente qualquer setor a qualquer momento. A fita impõe um acesso estritamente seqüencial. O acesso também é mais rápido no disco.             Assim como nas fitas, e por mais forte razão, os discos também possuem um diretório, indicando em que posições se encontram os arquivos. O diretório é armazenado no próprio disco, permitindo que o disco seja removido e utilizado mais tarde, sem que os nomes dos arquivos sejam perdidos. Na verdade, cada entrada de diretório contém todas as informações necessárias sobre o arquivo, constituindo o que se denomina registro descritor de arquivo.   Registro descritor de arquivo   A estrutura básica de um sistema de arquivos é o descritor de arquivo (DA). Para cada arquivo existente no sistema há um DA. Trata-se de um bloco (registro) que contém todas as informações sobre um determinado arquivo. Algumas informações não são visíveis aos usuários, embora sejam essenciais para o SO implementar as operações sobre arquivos. Tipicamente, um descritor de arquivo contém as seguintes informações: Nome do arquivo; Tipo do arquivo; Tamanho em bytes; Data e hora do último acesso; Data e hora da última alteração; Identificação do usuário que criou o arquivo; Lista de usuários que podem acessar o arquivo e respectivos direitos de acesso; Local no disco onde o conteúdo do arquivo foi colocado.   8.2      Suporte a arquivos   O sistema operacional permite realizar um conjunto de operações sobre arquivos. Essas operações são solicitadas através de chamadas de sistema.   Operações em arquivos   A seguir é considerado o que o SO deve fazer para realizar as diversas operações sobre arquivos (supondo um sistema baseado em disco):   - Criar um arquivo: dois passos são necessários, (a) encontrar e alocar espaço suficiente no disco para conter o arquivo (isto é, os dados do arquivo) e (b) adicionar uma entrada no diretório para conter os atributos do arquivo (nome, tamanho, localização, etc.).   - Escrever registro no arquivo: para escrever em um arquivo, o usuário executa uma chamada de sistema fornecendo o nome do arquivo e o bloco com a informação a ser escrita. O sistema procura no diretório, através do nome, a localização do arquivo no disco e a posição do ponteiro que indica o final do arquivo (onde deve ser escrito o próximo bloco).   - Ler próximo registro do arquivo: o usuário executa uma chamada de sistema passando como parâmetros o nome do arquivo e a posição na memória principal para onde as informações lidas devem ser copiadas. Novamente, o sistema procura no diretório a entrada correspondente, lê do disco e atualiza o ponteiro indicador de próximo registro a ser lido.   - Remover o arquivo: para remover o arquivo, primeiramente o diretório é pesquisado. A seguir, o espaço alocado é liberado e a entrada correspondente é removida do diretório.   - Reposicionar o arquivo: esta operação não envolve I/O de fato, pois consiste em localizar a entrada no diretório correspondente ao arquivo e modificar o valor do ponteiro indicador do próximo registro a ser acessado.               Todas as operações mencionadas acima envolvem uma pesquisa no diretório em busca da entrada correspondente ao arquivo desejado. Para evitar esta pesquisa constante no disco, muitos sistemas abrem o arquivo quando ele começa a ser utilizado. Abrir o arquivo significa trazer para a memória o seu registro descritor.   Tabela de arquivos abertos   O sistema operacional mantém na memória principal uma tabela contendo os registros descritores dos arquivos abertos (TDAA – Tabela de Descritores de Arquivos Abertos). Quando uma operação é solicitada, apenas esta tabela é pesquisada (em memória) e não todo o diretório (em disco).             Alguns sistemas abrem automaticamente o arquivo quando ele é utilizado pela primeira vez, enquanto outros exigem um pedido de abertura explícito do usuário (isto é feito através da operação open). Neste último caso, o diretório é pesquisado e a entrada correspondente ao arquivo é copiada para a tabela TDAA. É devolvido para o programa um ponteiro para a entrada nessa tabela. Nas próximas operações este ponteiro será utilizado para identificar o arquivo. O arquivo deve ser “fechado” após a utilização (operação close), o que permite liberar o espaço que seu descritor ocupava na TDAA. A TDAA mantém informações sobre os arquivos abertos por todos os processos no sistema. Normalmente, é permitido que vários processos abram um mesmo arquivo simultaneamente. Para cada arquivo há apenas uma entrada na TDAA, a qual armazena todas as informações do arquivo em disco, mais uma informação que indica o número de processos utilizando o arquivo no momento. Quando um processo realiza a chamada de sistema close, o número de processos utilizando o arquivo em questão é decrementado. Quando esse número chega a zero, significa que nenhum processo está usando o arquivo. Nesse caso, o descritor do arquivo é atualizado em disco e a entrada da TDAA liberada. As entradas da TDAA armazenam informações que não variam em função do processo que está acessando o arquivo Entretanto, existem informações correspondentes ao processo que acessa o arquivo. Um exemplo de informação que depende do processo é a posição corrente no arquivo. Em um dado instante, cada processo pode acessar uma parte diferente do arquivo. Logo, é necessário armazenar uma posição corrente no arquivo para cada processo. Da mesma forma, alguns processos podem abrir o arquivo para apenas leitura, enquanto outros abrem para leitura e escrita. Essa informação deve ser mantida pelo sistema de arquivos para que ele possa rejeitar chamadas de escrita quando o processo abriu o arquivo para apenas leitura. A solução típica é criar, para cada processo, uma Tabela de Arquivos Abertos por Processo (TAAP). Cada processo possui a sua TAAP. Cada entrada ocupada na TAAP corresponde a um arquivo aberto pelo processo correspondente. No mínimo, a TAAP contém em cada entrada as seguintes informações: Posição corrente no arquivo; Tipo de acesso (apenas leitura ou leitura e escrita); Apontador para a entrada correspondente na TDAA. A Figura 8.1 ilustra o emprego conjunto das TAAP e da TDAA. No exemplo da figura, o processo 0 possui dois arquivos abertos. O arquivo A foi aberto apenas para leitura, e a sua posição corrente é 12. O arquivo B foi aberto para leitura e escrita, e a sua posição corrente é 55. O processo 1 também abriu o arquivo B. Entretanto, o processo 1 pode apenas ler o arquivo, e a sua posição corrente é 10. Tanto a TDAA como as TAAP devem ficar na memória do sistema operacional, fora do acesso dos processos de usuário. Caso contrário, um usuário mal intencionado poderia burlar o mecanismo de controle de acesso simplesmente alterando sua TAAP. A função open retorna para o processo o número da entrada na TAAP associada com o arquivo aberto. Dessa forma, nas chamadas de sistema após o open, o processo indica o arquivo através do número de sua correspondente entrada na TAAP. A partir da TAAP, o sistema de arquivos pode imediatamente localizar o descritor do arquivo na TDAA. No exemplo da Figura 8.4, o processo 0 acessa o arquivo B através de referências à entrada 1 da sua TAAP.   8.3      Métodos de Acesso   Existem diversas maneiras de acessar as informações contidas em um arquivo. Enquanto alguns sistemas oferecem um único método de acesso, outros sistemas implementam diversos métodos.   Acesso seqüencial   Neste método, uma leitura sempre acessa o próximo registro e avança um ponteiro sobre o arquivo. Este ponteiro indica qual a próxima posição a ser lida. O mesmo acontece com a escrita.   Acesso direto   O arquivo consiste em uma seqüência numerada de registros. Qualquer registro pode ser diretamente lido ou escrito. As operações indicam o número do bloco a ser acessado. Este número é geralmente um número de bloco relativo, ou seja, um índice em relação ao início do arquivo (usuários não lidam com números de blocos absolutos).   Outros métodos de acesso   Outros métodos de acesso podem ser construídos utilizando como base o serviço de acesso direto. Estes métodos normalmente envolvem a construção de índices nos descritores de arquivos. Os índices são utilizados para localizar a informação desejada dentro do arquivo, objetivando sempre minimizar o acesso ao disco (maximizar o desempenho). Exemplo: o ISAM (Indexed Sequential Acess Method) da IBM usa um pequeno índice mestre que aponta para blocos de disco secundários com índices secundários, que por sua vez apontam para os blocos de disco contendo os dados.   8.4      Métodos de Alocação   Na maioria das vezes muitos arquivos estarão armazenados no mesmo disco. É necessário alocar espaço para estes arquivos de forma que o disco seja utilizado eficientemente e os arquivos possam ser acessados rapidamente. Três métodos principais de alocação de espaço em disco se encontram em uso: contígua, encadeada e indexada, cada um com suas vantagens e desvantagens.   Gerência do espaço livre   Arquivos são criados e removidos freqüentemente durante a operação do sistema. Uma vez que o espaço em disco é limitado, é necessário reaproveitar todo o espaço liberado. Para manter o controle do espaço livre no disco, o sistema mantém uma lista dos setores livres. Para criar um arquivo, o espaço necessário é obtido da lista. O espaço ocupado por um arquivo é devolvido à lista quando este é removido.             Esta lista, apesar de seu nome, pode não ser implementada como uma lista, mas sim como um “mapa de bits”, onde cada bit representa um bloco do disco. Se o bloco está ocupado o bit vale 1, se o bloco está livre o bit vale 0. O tamanho do mapa (número de bytes no mapa) corresponderia a um oitavo do número de blocos do disco.   Alocação contígua   O método de alocação contígua exige que cada arquivo ocupe um conjunto de setores contíguos no disco. Para localizar um arquivo basta saber o número do setor inicial e o tamanho do arquivo, em blocos.             Para acessar o arquivo de forma seqüencial, o sistema operacional mantém o número do último bloco acessado, incrementando este valor a cada acesso. Para um acesso direto ao setor i de um arquivo que inicia no setor b, o sistema deve acessar o setor b+i. Ambos os métodos seqüencial e direto são facilmente implementados.             A dificuldade com este esquema é encontrar um espaço livre para um novo arquivo. Se o novo arquivo ocupa n setores, é necessário pesquisar a lista de setores livres até encontrar n setores contíguos livres.             O espaço em disco pode ser visto como um grande vetor de blocos. Em um determinado momento, alguns blocos estão ocupados e outros livres, compondo segmentos de blocos contíguos ocupados e segmentos de blocos contíguos livres (buracos). O problema da alocação dinâmica de armazenamento consiste em como satisfazer um pedido de n blocos livres contíguos a partir de uma lista de blocos vazios. Os algoritmos que podem ser utilizados são os mesmos já vistos no capítulo de gerência de memória (first-fit, best-fit, etc.).             O maior problema deste método é determinar o número de setores a serem alocados para cada arquivo, no momento de sua criação. Em algumas situações isto é simples, como na cópia de um arquivo existente. Mas, em geral, esta tarefa édifícil. Se pouco espaço é alocado, o arquivo talvez não possa ser estendido porque o espaço nos dois lados está ocupado. A única solução neste caso é a cópia de todo o arquivo para um espaço maior. Se o espaço alocado é maior que o necessário, o disco não estará sendo utilizado de forma eficiente.   Alocação encadeada   Neste método, cada arquivo corresponde a uma lista encadeada de blocos, estando os mesmos em qualquer local do disco. O diretório contém apenas o endereço do bloco inicial e o número de blocos (ou endereço do último bloco), e cada bloco de dados contém o endereço do bloco seguinte. Existe uma perda associada a cada bloco, uma vez que é necessário gastar bytes com ponteiros.             Com alocação encadeada, os arquivos podem ser criados com tamanho zero. Na medida em que o arquivo precisa crescer, setores serão removidos da lista de setores livres e inseridos na lista encadeada que forma o arquivo. Qualquer setor do disco, independente de sua posição, pode ser aproveitado. Os arquivos podem crescer livremente até o limite do disco.             Este método somente pode ser utilizado de forma eficiente para implementar acesso seqüencial. Para acessar diretamente o setor n, seria necessário realizar n acessos ao disco. Isto impede, na prática, o acesso direto. Além disto, este método apresenta problemas de confiabilidade: como cada setor contém o endereço do setor seguinte, basta que um setor seja danificado (hardware ou software) para que boa parte do arquivo seja perdida.   Alocação indexada   Este método é capaz de resolver o problema do crescimento dos arquivos ao mesmo tempo que permite o acesso relativo. Na alocação indexada, cada arquivo possui uma tabela de índices. Cada entrada dessa tabela contém o endereço de um dos blocos físicos que formam o arquivo.  Um acesso relativo pode ser facilmente realizado através de uma consulta à tabela de índices. O endereço no disco de qualquer bloco lógico é obtido através de um único acesso a essa tabela. Para que esse acesso seja rápido, a tabela de índices é normalmente mantida na memória principal enquanto o arquivo está aberto. Uma forma conveniente é manter a tabela de índices dentro do próprio descritor do arquivo.   Uma questão importante é o tamanho da tabela de índices. Ele define o tamanho máximo de um arquivo no sistema. Por exemplo, suponha que cada bloco físico corresponda a 4 Kbytes. Para que o tamanho máximo de um arquivo no sistema seja de 4 Gbytes, será necessário uma tabela de índices contendo “4 Gbytes 4 Kbytes” entradas, ou seja, 1.048.576 entradas (1 M na informática, ou seja, 1024 1024). Manter uma tabela de índices desse tamanho para cada arquivo é um absurdo. O tamanho médio dos arquivos em sistemas de propósito geral fica entre 10 Kbytes e 20 Kbytes. Mantendo a suposição de que cada bloco físico corresponde a 4 Kbytes, uma tabela de índices com apenas 5 entradas seria suficiente para um arquivo de 20 Kbytes. A solução típica para compatibilizar uma maioria de arquivos pequenos com um tamanho máximo de arquivo satisfatório é empregar níveis de indireção na indexação. Por exemplo, suponha que o descritor de arquivos contém uma tabela de índices com 13 entradas. As primeiras 10 entradas (numeradas de 0 a 9) apontam para blocos de dados do arquivo, permitindo o acesso aos primeiros 40 Kbytes de cada arquivo (supondo sempre blocos de 4 Kbytes). Eles são chamados de apontadores diretos. A entrada 10 da tabela não aponta para um bloco de dados do arquivo, mas sim para um bloco que contém apontadores para blocos de dados. Supondo que os números de blocos físicos ocupem 4 bytes, um bloco de 4 Kbytes é capaz de armazenar 1024 apontadores. Como cada apontador representa um bloco físico, temos que um único apontador indireto na tabela de índices permite o acesso a 4 Mbytes de dados do arquivo.   A entrada 11 da tabela contém um apontador duplamente indireto, o que permite o acesso a até 4 Gbytes de dados. Para suportar arquivos realmente grandes, é usada a entrada 12, a qual contém um apontador triplamente indireto. Ele aponta para um bloco que contém 1024 apontadores. Esses 1024 apontadores, em conjunto, apontam para 10241024 apontadores. Cada um deles aponta para 1024 apontadores. No total temos 102410241024 apontadores para blocos de dados, o que permite indexar um total de 4 Tbytes (terabytes). As necessidades da maioria dos sistemas são atendidas apenas com a dupla indireção. Esse esquema de apontadores indiretos é muito atraente. Considerando o exemplo, arquivos de até 40 Kbytes possuem sua tabela de índices completa dentro do descritor de arquivo, o qual é necessariamente lido para a memória quando o arquivo é aberto. Dessa forma, arquivos com até 40 Kbytes, o que corresponde à maioria, são sempre acessados rapidamente. Por sua vez, arquivos com mais de 40 Kbytes e não mais que 4 Mbytes 40 Kbytes necessitam de apenas um nível de indireção, ou seja, de um único bloco contendo apontadores. Esse bloco também pode ser mantido na memória principal todo o tempo, fazendo com que o acesso aos dados não necessite de acesso adicional ao disco para a leitura de apontadores. Somente arquivos maiores que 4 Mbytes 40 Kbytes terão o acesso mais lento em função da necessidade de ler também os apontadores do disco. Entretanto, os blocos de apontadores utilizados com maior freqüência podem ser mantidos em cache, o que acelera o processo de localização dos dados no disco. Acessos seqüenciais são também eficientes, pois os mesmos blocos de apontadores são utilizados para acessar um longo trecho seqüencial do arquivo. A partir dos três métodos básicos (alocação contígua, encadeada e indexada) é possível imaginar diversas combinações. Por exemplo, a técnica conhecida como FAT (File Allocation Table) é uma variação da alocação encadeada, na qual os apontadores foram removidos de cada bloco físico individual e colocados todos juntos em uma única tabela, chamada de Tabela de Alocação de Arquivos.   8.5      Sistemas de Diretórios   Um diretório na forma de lista de arquivos pode ser suficiente para um sistema monousuário, com pouco espaço em disco. Na medida em que o espaço em disco aumenta ou aumenta o número de usuários, é necessário criar um diretório cuja estrutura permita que os usuários organizem os seus arquivos. A seguir são discutidas as possíveis formas de organizar os diretórios.   Diretório de nível único   Nesta estrutura todos os arquivos fazem parte do mesmo diretório. Na medida em que o número de arquivos aumenta, aparecem problemas de organização. Por exemplo, é necessário que cada arquivo tenha um nome único.   Diretório de dois níveis   A maior desvantagem do diretório de nível único é a confusão de nomes de arquivos entre diferentes usuários. A solução mais comum é criar um diretório separado para cada usuário. Um diretório principal mantém os endereços dos diretórios dos usuários, enquanto os diretórios de usuários contêm informações sobre os respectivos arquivos.             Quando um usuário faz referência a um arquivo, apenas o seu próprio diretório é pesquisado. Logo, diferentes usuários podem ter arquivos com o mesmo nome. Os usuários estão naturalmente protegidos de acessos indevidos. É necessário de alguma forma criar diretórios para novos usuários e destruir diretórios não mais usados.             Para economizar espaço em disco, todos os utilitários do sistema (compiladores, editores, etc.) podem ser colocados em um único diretório e não duplicados em todos os diretórios dos usuários. Este é um diretório especial. Sempre que o usuário tenta executar um programa, primeiramente o diretório especial é pesquisado. Se o arquivo do programa não é encontrado, então o diretório do usuário é pesquisado. Pode-se também inverter o caminho de pesquisa.   Diretórios estruturados em árvore   Neste esquema, usuários podem criar seus próprios sub-diretórios para organizar os seus arquivos. A árvore possui um diretório raiz. Cada arquivo no sistema tem um único pathname. O pathname é o nome do arquivo composto pelos nomes de diretórios que formam o caminho da raiz até ele.             Um diretório ou sub-diretório contém um conjunto de arquivos e/ou sub-diretórios. Em cada entrada de diretório existe um campo indicando se a entrada é um arquivo ou um sub-diretório.             Os pathnames podem ser completos ou relativos. Um pathname completo inicia na raiz e vai até o arquivo a ser identificado. Se o pathname começa no diretório corrente, então ele é relativo.   8.6      Formas de Implementar Diretórios   A forma mais simples de implementar diretórios é considerá-los como arquivos especiais, manipulados pelo próprio sistema operacional. Dessa forma, todos os mecanismos de alocação, liberação e localização de blocos físicos no disco, disponíveis para arquivos, também são usados para os diretórios. Diretórios passam a ser arquivos cujo conteúdo é definido pelo sistema operacional e cujo acesso, por parte de usuários, é controlado. Como diretórios são arquivos, cada diretório possui também o seu descritor. Um diretório pode ser organizado na forma de um conjunto de descritores de arquivos, ou como um conjunto de endereços de descritores de arquivos. No primeiro caso, o diretório contém diretamente descritores de arquivos e/ou diretórios. Nesse caso, o nome do arquivo (ou do diretório) faz parte do descritor. Nesse esquema, após a leitura do diretório, o sistema de arquivos já terá na memória todas as informações necessárias para procurar pelo nome do arquivo buscado e, caso encontre, acessar o seu conteúdo. A Figura 8.4 ilustra esta solução. Nessa figura, retângulos representam diretórios e retângulos de cantos arrendodados representam arquivos de dados. As desvantagens deste esquema são: (1) os nomes ficam fortemente vinculados aos descritores de arquivos, impedindo, por exemplo, que um mesmo arquivo possua mais de um nome; (2) os diretórios tendem a ser maiores e estão mais sujeitos a inconsistências, pois informações importantes estão espalhadas por todo o disco.     No caso do diretório ser um conjunto de endereços de descritores, tem-se em cada entrada do diretório apenas um par: nome do arquivo (ou diretório) e um ponteiro para o descritor correspondente. Neste esquema, é comum reservar uma parte do disco para armazenar exclusivamente descritores de arquivos. Esses blocos reservados constituem um vetor de descritores, no qual cada descritor pode ser perfeitamente identificado pela posição nesse vetor. Essa estrutura de dados forma o que se denomina um flat file system (na terminologia do UNIX), pois não existe nenhuma estruturação dos arquivos em diretórios, existindo apenas um diretório único (o vetor). A estrutura em árvore é criada a partir de alguns arquivos do sistema flat (que atuam como subdiretórios), cada um organizado internamente como uma tabela contendo nomes e respectivos endereços no vetor de descritores. Dessa forma, para percorrer um caminho na árvore dos arquivos (pathname), é necessário abrir o subdiretório, procurar o nome desejado, pegar o endereço flat associado e ler o respectivo descritor de arquivo. Esse procedimento deve ser repetido para cada nome presente no caminho a ser percorrido. A Figura 8.5 ilustra essa solução, considerando novamente a árvore de arquivos que aparece na Figura 8.4. É suposto que o primeiro descritor de arquivo do vetor de descritores (índice 0) descreve o diretório raiz da árvore.   8.7      Proteção dos Arquivos   Quando a informação é mantida em um computador, ela deve ser protegida contra dano físico (confiabilidade) e acesso indevido (proteção).               A confiabilidade é obtida geralmente criando cópias dos arquivos. Muitos sistemas operacionais automaticamente copiam o conteúdo do disco para fita em intervalos regulares (uma vez ao dia ou a cada semana).             A proteção é necessária apenas nos sistemas multiusuários (se o sistema só tem um usuário, nenhuma proteção é necessária). Os mecanismos de proteção garantem acesso controlado, limitando o tipo de acesso que pode ser feito a um arquivo. Diversos tipos de acesso podem ser permitidos (ou negados), tais como: leitura, gravação, execução, criação e remoção. Vale observar que as três primeiras operações (leitura, gravação e execução) envolvem acesso a arquivos enquanto as duas últimas (criação e remoção) envolvem acesso a diretórios. Outras operações (sobre diretórios) possíveis de serem protegidas são listagem de diretório pesquisa de diretório.             Existem diferentes mecanismos de proteção, cada um com vantagens e desvantagens. O melhor mecanismo depende do sistema em questão. Um método bastante utilizado é vincular o acesso à identificação do usuário ou de um grupo de usuários com interesses afins, como ocorre no sistema Unix.   8.8      Questões de Implementação   Um sistema de arquivos envolve dois problemas de projeto bastante diferentes. Um deles é definir como o sistema de arquivos deve aparecer para o usuário (visão do usuário). Isto envolve a definição dos arquivos e de seus atributos, operações permitidas e estrutura de diretórios. O outro problema de projeto é definir quais algoritmos e estruturas de dados serão usados para mapear o sistema de arquivos lógicos visto pelo usuário, nos dispositivos físicos disponíveis ao sistema de arquivos.             Conceitualmente, um sistema de arquivos pode ser dividido em três níveis de serviço: serviço de disco, de arquivo básico e de diretório:   serviço de disco: é responsável pela leitura e escrita de setores diretamente no disco, sem interessar a forma como eles estão organizados; serviço de arquivo básico: lida com arquivos básicos, compostos de um descritor e um conjunto de registros. Operações são a leitura e a escrita de blocos a partir de uma determinada posição do arquivo; serviço de diretório: preocupa-se com a identificação e proteção de arquivos, descritos a partir de diretórios, de forma que eles possam ser acessados de forma segura e conveniente. O serviço de diretório tipicamente fornece objetos denominados diretórios que mapeiam nomes simbólicos de arquivos em identificadores numéricos utilizados pelo serviço de arquivo básico.