Resumo - UNIVESP - 2021 - Sistemas Operacionais

Prévia do material em texto

SISTEMAS OPERACIONAIS - EEO001 
Revisão Final 
 
O presente documento tem como objetivo fornecer ao aluno um apanhado geral do conteúdo 
ministrado durante o curso de Sistemas Operacionais (SO). Nesta revisão, abordaremos os seguintes 
tópicos: 
• Função do SO 
• Tipos de SOs 
• Estruturação de um SO 
• Chamadas ao sistema e interrupções 
• Processos e Threads 
• Escalonamento de processos 
• Deadlocks 
• Gerenciamento de memória 
• Escalonamento de disco 
• Alocação de arquivos em disco 
 
Função do Sistema Operacional 
Do ponto de vista do programador, o Sistema Operacional (SO) age como um facilitador, 
tomando conta do gerenciamento do hardware e de como este será compartilhado com os demais 
programas, além de esconder detalhes sobre comunicação em rede, interação com o usuário etc. Para 
o usuário final, este se apresenta como uma interface mais amigável, permitindo que ele consiga 
interagir com a máquina de modo mais fácil e natural. Finalmente, seu papel junto aos fabricantes de 
hardware é prover uma interface de comunicação, padronizando o modo como cada dispositivo irá 
interagir com os programas desenvolvidos, e assim facilitando o acoplamento ao sistema de novos 
produtos. 
 
Tipos de Sistemas Operacionais 
Quanto ao compartilhamento de hardware, SOs podem ser monoprogramáveis ou 
multiprogramáveis. SOs monoprogramáveis (ou monotarefa) rodam um único programa por vez, 
dedicando todos os recursos da máquina a este programa. Nesse modelo, em um dado momento, há 
apenas um programa em memória (Ex.: MS-DOS). Em contraste, SOs multiprogramáveis (ou 
multitarefa) têm como objetivo manter mais de um programa em memória ao mesmo tempo, 
compartilhando os demais recursos do computador (Ex.: UNIX, Windows etc.). 
SOs multiprogramáveis podem ser subdivididos, de acordo com a forma de interação permitida 
com as aplicações, em SOs para Sistemas em Batch, para Sistemas de Tempo Compartilhado, e para 
Sistemas de Tempo Real. Em SOs para Sistemas em Batch, um grupo de programas (um lote) é 
submetido ao processador de uma única vez, em uma ordem determinada pelo escalonador do SO. 
Um ponto crucial nesse modelo é que, uma vez submetido ao processamento, não há interação entre 
o usuário e o programa até que este termine sua execução. 
Outro ponto importante em sistemas em Batch é a noção de tempo de resposta (turnaround 
time). O tempo de resposta é sempre medido sob o ponto de vista do usuário, ou seja, do momento 
em que este deixa o programa para ser executado, até o momento em que ele obtém a resposta. Então, 
se múltiplos programas são agrupados em um lote e executados, o tempo de resposta de cada um irá 
refletir tanto o tempo em que este executou quanto o tempo em que ficou aguardando os programas 
anteriores executarem. 
Por exemplo, suponha que um usuário envie um lote com 4 programas, A, B, C e D, e que o 
escalonador os executa nessa ordem. O primeiro programa a executar será A, rodando sem 
interrupções até o final, tomando um tempo tA – seu tempo de resposta. O programa B, contudo, teve 
de esperar A executar, para então ser executado. Como ele foi entregue pelo usuário junto a A, do 
ponto de vista do usuário, B entregou sua resposta depois de um tempo tA + tB. Naturalmente, o tempo 
de resposta do último programa, D, refletirá não somente o tempo por ele gasto no processador, mas 
também o tempo gasto esperando todos os demais executarem. 
Como, então, podemos calcular o tempo de resposta do lote como um todo, quando este contém 
múltiplos programas? Uma possibilidade é calcular o tempo de resposta médio (mean turnaround 
time) – a média aritmética dos tempos de resposta dos programas que compõem o lote (ou, 
alternativamente, quanto em média os programas do lote demoram para executar). Assim, se um lote 
contém 3 processos – A, B e C – e estes são rodados nessa ordem, o processo A levará tempo tA para 
executar, B levará tB e C levará tC. O tempo de resposta de cada um seria: 
TA: tA; TB: tA + tB; e TC: tA + tB + tC 
Supondo que não haja E/S, o tempo médio de resposta será então a soma do tempo de resposta 
de cada programa dividida pelo número de programas, ou seja: 
TM = (TA + TB + TC) / 3 = (tA + tA + tB + tA + tB + tC) / 3 = (3 tA + 2 tB + tC) / 3 
O segundo grupo de sistemas multiprogramáveis – Sistemas de Tempo Compartilhado – tem 
como característica o compartilhamento da CPU com os demais programas em memória. Nesses 
sistemas, em vez da CPU rodar cada programa do começo ao fim, normalmente é destinado a eles 
“fatias de tempo” (chamadas de quantum) em que podem rodar. Assim, mesmo que na CPU haja 
apenas um programa rodando por vez, para o usuário a impressão que fica é a de que todos estão 
rodando simultaneamente, em paralelo. Uma subclasse desse tipo de sistema é a classe dos Sistemas 
Interativos, cuja característica é a possibilidade de interação entre o usuário final e a aplicação. 
Sistemas interativos podem ser monousuários, em que apenas um usuário é permitido no sistema, 
ou multiusuários, em que diversos usuários podem interagir com suas respectivas aplicações, 
podendo inclusive haver compartilhamento de aplicações entre eles. 
Por fim, Sistemas de Tempo Real são aqueles em que o tempo de resposta é crucial, devendo 
as requisições serem atendidas o mais rapidamente possível. Não raro esses sistemas impõem prazos 
para execução de uma determinada requisição, e atrasos podem ser tão ruins quanto sua não execução. 
Em geral, sistemas de tempo real são subdivididos em Hard Real Time, em que atrasos não são 
tolerados, e um atraso equivale à não execução de uma tarefa (como em monitoradores de usinas 
nucleares), e Soft Real Time, em que atrasos ocasionais, embora indesejáveis, não são tão graves 
(como em transmissões de vídeo). 
 
Estruturação de um Sistema Operacional 
Em geral, SOs são estruturados obedecendo alguns princípios. SOs com estrutura Monolítica 
têm como característica a implementação do SO como um único módulo (um monolito), consistindo 
em um conjunto de rotinas que rodam como se fossem um único programa. Dentro dessa organização, 
destacam-se o MS-DOS, UNIX (e derivados) e Windows. A estrutura de Microkernel (ou 
Micronúcleo), por sua vez, tem como principal característica a minimalização da estrutura do núcleo 
do SO, cabendo a este não somente o gerenciamento da CPU e comunicação entre processos. Todos 
os demais serviços são implementados no modo do usuário (Ex.: Minix, Symbian). 
A modularidade é também observada no modelo correspondente à estrutura em Camadas, em 
que o núcleo do SO é dividido em camadas hierárquicas, em que cada camada é construída como uma 
extensão da anterior, adicionando novas funcionalidades, e fazendo uso de funcionalidades já 
oferecidas, sem se preocupar em como estas são implementadas. Dessa forma, esse modelo nos 
permite, a cada camada, ignorar os detalhes das camadas inferiores (daí a noção de hierarquia). 
Exemplos de sistemas assim são o Multics e o OpenVMS. Por fim, a estrutura de Máquina Virtual 
se caracteriza pela existência de uma aplicação – o Gerenciador de Máquina Virtual – com a função 
de criar diversos ambientes (as máquinas virtuais), virtualmente replicando o hardware em cada uma 
delas. Essas máquinas podem, então, rodar SOs diferentes. De fato, a estrutura de Máquina Virtual 
trata da criação de um meta-SO – um SO para SOs. Um sistema assim era o VM370, mas esse modelo 
é encontrado hoje em diversas áreas. 
 
Chamadas ao sistema e Interrupções 
Mais do que um simples gerente, o SO trabalha junto ao hardware para proteger os sistemas 
que nele rodam de erros. Para tal, os processadores são projetados de modo a oferecerem dois tipos 
de instruções: as não privilegiadas, que podem ser executadas por qualquer aplicação, e as 
privilegiadas, que dependem de uma linha de controle extra no processador, linha essa que o coloca 
em modo kernel (ou modo núcleo). A ideia por trás dessa divisãoé fazer com que apenas o SO tenha 
acesso a instruções no modo kernel, protegendo, assim, o sistema de eventuais problemas gerados 
pelas aplicações. 
E como então uma aplicação comum pode executar instruções em modo kernel para, por 
exemplo, ter acesso ao sistema de arquivos? Ela não pode. Ela só pode fazer uma requisição ao SO 
para que essa instrução seja executada, por meio de uma instrução especial – a trap, cabendo ao SO 
decidir se executa ou não a requisição. Dizemos então que a aplicação fez uma chamada ao sistema, 
ou seja, um pedido de alteração do modo usuário (não privilegiado) para o modo kernel (privilegiado), 
para execução de uma determinada ação privilegiada. Assim, a principal função das chamadas de 
sistema é fazer com que aplicações possam executar instruções privilegiadas, e o modo como 
aplicações fazem tais chamadas é por meio de instruções do tipo trap. 
Por serem geradas pela própria aplicação, interrompendo seu fluxo normal, as traps são 
conhecidas como interrupções de software. Em contraste, temos as interrupções de hardware (ou 
simplesmente interrupções), que são causadas por eventos externos ao processador, geralmente 
oriundos de dispositivos de E/S ou do clock. 
 
Processos e Threads 
Processos são programas em execução. Assim, enquanto um programa se caracteriza pelo seu 
código, o processo possui não somente o código do programa, mas também todo seu contexto de 
execução. Esse contexto, por sua vez, subdivide-se em espaço de endereçamento, que é o conjunto 
de endereços de memória ao qual um processo tem acesso, ou seja, o espaço em memória reservado 
a ele; contexto de hardware, compreendendo os registradores usados pelo processo; e contexto de 
software, contendo atributos gerais do processo, como permissões, arquivos etc. 
O espaço de endereçamento de um processo subdivide-se em 3 partes (também chamadas de 
segmentos): segmento de texto, que contém o código dos programas que rodam no processo; 
segmento de dados, que armazena as variáveis dinamicamente alocadas em memória; e a pilha de 
execução, que gerencia as chamadas a sub-rotinas. Além dessa informação, o contexto também 
determina o estado do processo, definindo se este está atualmente ocupando o processador 
(executando), se está impedido de prosseguir por depender de informação externa (bloqueado), 
como quando espera por E/S, ou se está apto a rodar, mas ainda não foi escolhido pelo SO (pronto). 
Enquanto podemos ter diversas cópias de um mesmo programa em execução, processos são 
únicos. Para gerenciá-los, o SO armazena toda a informação referente a um determinado processo (ou 
seja, seu contexto, exceto pelo seu espaço de endereçamento) em uma estrutura denominada Bloco 
de Controle de Processo (BCP). Cada BCP é então armazenado em uma estrutura denominada 
tabela de processos. 
Dentro de cada processo podemos ter uma ou mais linhas de execução (ou threads), 
gerenciadas por meio de uma tabela de threads. Embora as threads possuam seu próprio estado e 
contexto (registradores e pilha de execução), elas compartilham do mesmo espaço de endereçamento 
do processo. Threads são suportadas pelo SO de três formas. No modo usuário elas são 
implementadas somente no espaço do usuário, por meio de bibliotecas, sem que o kernel do SO saiba 
de sua existência. No mono núcleo, o kernel do SO gerencia as threads, conhecendo, portanto, todas 
elas. Nesse modelo, todo o gerenciamento das threads (escalonamento e tabela de threads) se encontra 
no kernel. Por fim, no modelo híbrido, o SO possui suporte para threads em modo núcleo, podendo 
também o usuário criar threads em modo usuário. Nesse modelo, há uma correspondência N:M em 
que N threads de usuário são mapeadas em M (≤ N) threads de núcleo. 
 
Escalonamento de processos 
A escolha de qual processo irá ocupar o processador (ou seja, irá rodar) é feita por uma rotina 
do SO chamada de escalonador. Diferentes escalonadores utilizam diferentes algoritmos de 
escalonamento, a depender do tipo de SO (se em batch, de tempo compartilhado ou de tempo real). 
Nesse curso, são apresentados apenas algoritmos para sistemas em batch e de tempo compartilhado. 
 
Escalonamento em Batch: First Come First Served (FCFS ou FIFO) 
Algoritmo não preemptivo, no qual os processos são executados na ordem em que estão na fila 
de processos prontos, sendo interrompidos somente no caso de E/S ou término. Assim, se a fila 
contém 3 processos, A, B, C, estes são executados até o fim, na ordem em que estão na fila. 
 
Escalonamento em Batch: Shortest Job First (SJF) 
Algoritmo não preemptivo, em que sempre se executa o menor processo do lote primeiro. 
Assim, os processos são ordenados por tempo estimado de execução, e executados do mais rápido ao 
mais lento, levando ao menor tempo de resposta médio (mean turnaround time). E como isso ocorre? 
Suponha que temos 3 processos distintos no lote. Para esse caso, vimos que o tempo de resposta 
médio será dado por (3 tA + 2 tB + tC) / 3. Assim, se ordenarmos a lista por tempo estimado de execução 
do processo, de modo que o processo A seja o mais rápido (tempo menor), B o intermediário e C o 
mais lento (tempo maior), teremos feito com que o menor contribua mais, e o maior contribua menos 
para a média, reduzindo-a. 
 
Escalonamento em Batch: Shortest Remaining Time Next (SRTN) 
Versão preemptiva do Shortest Job First, em que processos com tempo estimado de execução 
menor são rodados antes. A diferença é que, se um novo processo chegar, e seu tempo for menor que 
o atualmente em execução, este é interrompido e o novo processo é rodado em seu lugar. 
 
Escalonamento em Sistemas Interativos: Round-Robin 
No Round-Robin, cada processo recebe um tempo de execução, chamado quantum. Os 
processos são então organizados em uma fila de prontos e rodados em ordem, um a um. Cada processo 
roda pelo tempo de seu quantum, sendo então trocado pelo próximo processo na fila, e voltando ao 
final da fila, para esperar sua vez de rodar novamente. Caso um processo execute E/S, este é 
bloqueado (ou seja, é movido para a fila de bloqueados) e, ao término da E/S, ele é então movido 
novamente para o final da fila de prontos. 
 
Escalonamento em Sistemas Interativos: Prioridade 
Com esse algoritmo, além do tempo de execução dos processos ser dividido em quanta (plural 
de quantum), a eles é atribuída uma prioridade. Os processos com maior prioridade são então 
executados primeiro. Medidas devem ser tomadas, contudo, para que os de menor prioridade não 
sofram de inanição, ou seja, nunca sejam escalonados para rodar. Vale notar que Round-Robin é um 
caso específico deste algoritmo, em que todos os processos têm igual prioridade. 
 
Escalonamento em Sistemas Interativos: Múltiplas Filas 
No algoritmo de múltiplas filas (também chamado de CTSS), o sistema é organizado em várias 
filas, e processos vão mudando de uma fila para a outra. Processos em uma determinada fila, recebem 
um número específicos de quanta para rodarem, sendo que os da primeira fila recebem 1 quantum, os 
da segunda, 2 quanta, da terceira, 4, e assim por diante. Na n-ésima fila um processo receberá 2n-1 
quanta para rodar. 
Dessa forma, todo processo inicia na primeira fila, recebendo 1 quantum. Dentro da fila eles 
são rodados segundo Round-Robin. A diferença, no entanto, é que quando um processo termina de 
usar seu tempo de CPU, em vez de voltar ao final de sua fila, ele vai para o final da próxima fila, 
recebendo 2 quanta. Ao rodar seus 2 quanta, irá ao final da próxima, recebendo 4 quanta, e assim 
por diante. Naturalmente, o número de filas não é infinito, então processos na última fila rodam seus 
quanta usando um modelo Round-Robin. 
 
Escalonamento em Sistemas Interativos: Shortest Process Next 
Versão interativa do Shortest Job First, em que o tempo de execução de um processo é estimado 
com base em execuções antigas do mesmo programa. 
 
Escalonamento em Sistemas Interativos:Garantido 
Um escalonador garantido seleciona processos de modo a cumprir uma promessa feita aos 
processos de cada usuário. Assim, por exemplo, se um sistema possui n processos, é garantido que 
1/n do tempo da CPU é dado a cada um. E no que esse se diferencia de um Round-Robin? No Round-
Robin, se um processo faz E/S ele é bloqueado e, ao voltar, é movido para o final da fila de prontos. 
Isso, contudo, faz com que processos com grande volume de E/S acabem não usando a CPU o mesmo 
tanto que outros sem essa característica. O algoritmo garantido vem então corrigir esse problema. 
 
Escalonamento em Sistemas Interativos: Loteria 
No algoritmo de loteria, cada processo recebe um determinado número de “bilhetes”, 
geralmente proporcional à sua prioridade, sendo que cada bilhete dá ao processo o direito de executar 
um quantum. Quando precisa escolher um processo para rodar, o escalonador sorteia um bilhete, e o 
processo detentor desse bilhete é então rodado. De modo a evitar inanição, bilhetes já sorteados são 
eliminados de sorteios posteriores, dessa forma, todos terão sua vez de rodar. Ao término de todos os 
bilhetes, estes são então redistribuídos aleatoriamente, reiniciando o processo. 
 
Escalonamento em Sistemas Interativos: Fair-Share 
Semelhante ao garantido, um escalonador fair-share seleciona processos de modo a cumprir 
uma promessa feita, desta vez, aos usuários donos dos processos. Assim, em um sistema com n 
usuários, é prometido que 1/n do tempo da CPU é dado a cada um desses usuários. A escolha dos 
processos de um determinado usuário pode seguir algoritmos já vistos, como Round-Robin ou 
Prioridade. O tempo total desses processos, contudo, não pode ultrapassar 1/n do tempo total de CPU. 
 
Comunicação entre processos 
A comunicação entre processos é essencial para que eles possam sincronizar suas ações, de 
modo a evitar que dois processos estejam na mesma região crítica, ou seja, na região com recursos 
compartilhados por esses processos, ao mesmo tempo. Esse tipo de acesso compartilhado a algum 
recurso é denominado condição de corrida, e a restrição de que apenas um processo por vez esteja 
na região crítica é denominado exclusão mútua. 
Resolver problemas de exclusão mútua não é algo fácil. Ao longo do tempo diversas soluções 
foram propostas, sendo que hoje, em geral, aplicam-se soluções ligadas a semáforos, monitores e 
trocas de mensagens. Em geral, quando uma nova técnica é proposta, esta é testada em problemas 
clássicos de comunicação entre processos. 
Um desses problemas é o do produtor-consumidor, em que dois processos compartilham uma 
região de memória – um buffer – em que o processo consumidor armazena dados que, então, são 
removidos pelo produtor. Quando um consumidor tenta remover um dado de um buffer vazio, este 
deve aguardar. Da mesma forma, um produtor deve aguardar antes de armazenar um dado em um 
buffer cheio. O problema é então como gerenciar essa dinâmica. 
No caso do jantar dos filósofos, um determinado número de filósofos estão sentados ao redor 
de uma mesa circular, cada um com um prato de macarrão à sua frente. Entre cada par de pratos há 
apenas um hashi, sendo necessário 2 para que um filósofo possa comer. Há assim menos hashis que 
o necessário, fazendo com que estes precisem ser compartilhados. Cada filósofo alterna entre um 
tempo comendo e um tempo pensando. Quando vai comer, pega primeiro um hashi e então o outro, e 
só aí pode comer. Ao terminar seu tempo de comer, este larga um hashi para então largar o outro. O 
problema é então como fazer com que o maior número de filósofos coma ao mesmo tempo. 
Por fim, o problema dos leitores e escritores trata de um número de processos que somente 
leem uma base de dados (os leitores), enquanto outros apenas a modificam (escritores). Enquanto 
escritas são feitas, nenhum outro processo pode ter acesso à base, e quando leituras ocorrem outros 
processos também podem ler. O problema é então como permitir o máximo de acesso a essa base. 
 
Deadlocks 
Suponha que um processo A esteja bloqueado, esperando uma ação de outro processo B. 
Suponha agora que B também esteja na mesma situação, mas esperando uma ação do processo A. 
Nesse caso, dizemos que ambos estão em deadlock. Embora com dois processos seja bastante simples 
de se identificar, a identificação de deadlocks com vários processos é desafiador, e mesmo algoritmos 
eficazes, como o do banqueiro, fazem suposições pouco realistas, como o conhecimento de antemão 
dos recursos a serem demandados por um processo. 
 
Gerenciamento de Memória 
Nas máquinas modernas, é comum o gerenciamento de memória ser feito através do uso de 
uma técnica conhecida como paginação, segundo a qual a memória é particionada em blocos de 
tamanho fixo – as molduras de página. A estas são, então, mapeados blocos lógicos, as páginas, que 
formam o espaço de endereçamento lógico do processo ou, grosso modo, a memória que o processo 
“acredita” possuir. O truque então é mapear as páginas (os endereços que o processo crê estar 
acessando) as molduras no hardware (os endereços reais na memória). Esse mapeamento é feito por 
meio da tabela de páginas, e constitui uma das técnicas para implementação de memória virtual, 
ou seja, o uso da memória secundária para armazenar a memória usada pelos processos. 
Quando uma página é acessada por um processo, sem que esta esteja associada a alguma 
moldura, ocorre uma falha de página (page fault). Se houver molduras não utilizadas, o SO pode 
simplesmente buscar a página faltante no disco, armazená-la nessa moldura, e atualizar a tabela de 
páginas, associando essa moldura à página do processo. Se, contudo, não houver moldura vazia, ele 
precisa escolher uma moldura, para então enviar seu conteúdo (sua página) ao disco, usando esse 
espaço para armazenar a nova página. Essa escolha é feita usando-se diversos algoritmos. 
O primeiro deles – Not Recently Used (NRU) – associa 2 bits a cada página: o bit R, que indica 
que a página foi acessada (Referenciada) no último tique do clock, e o bit M, que indica que ela foi 
escrita (Modificada) em algum momento desde que foi carregada. O algoritmo separa então as 
páginas em 4 classes: Classe 0 (R=0, M=0) – página não referenciada nem modificada; Classe 1 (R=0, 
M=1) – não referenciada, mas modificada; Classe 2 (R=1, M=0) – referenciada, mas não modificada; 
e Classe 3 (R=1, M=1) – referenciada e modificada. Quando ocorre um page fault, o algoritmo 
escolhe aleatoriamente uma página da Classe 1. Se não houver nenhuma nessa classe, escolhe da 
Classe 2, e assim por diante. 
No First-in-first-out (FIFO), toda vez que uma página é levada à memória ela é colocada ao 
final de uma lista. Na ocorrência de um page fault, a primeira página da lista é enviada ao disco. 
Assim, as páginas carregadas há mais tempo são removidas primeiro. Uma variante desse algoritmo 
é o da Segunda Chance, em que o bit R da página mais antiga é verificado. Se R=1, ele é feito 0 e, 
em vez de remover a página, esta é enviada ao final da fila, tendo seu tempo de carregamento 
modificado, como se tivesse sido recém trazida à memória. O algoritmo então procede, analisando o 
segundo elemento da fila, e assim por diante. 
Uma melhoria no algoritmo da Segunda Chance se dá ao organizarmos a fila de páginas de 
forma circular, percorrendo-a no sentido horário. Esse é o algoritmo do Relógio. Então, ao analisar 
uma página (em que está o ponteiro), se R=0 ela é substituída pela página nova, e o ponteiro avança 
(a nova foi para o “fim da fila”). Se R=1, R é feito zero, o ponteiro avança, e a análise recomeça. 
No caso do Least Recently Used (LRU), substitui-se a página que foi menos usada no sistema. 
Para tal, associa-se um contador a cada página, incrementando-o toda vez que esta é referenciada. Em 
um page fault, aquela com menor valor nesse contador é removida. Em sua implementação puramente 
em software, o algoritmo é chamado de NotFrequently Used (NFU). 
No algoritmo do Working Set, busca-se determinar o working set do processo, ou seja, o 
conjunto de páginas que ele referenciou durante os últimos t segundos. No caso de um page fault, o 
algoritmo remove uma página de fora do working set. Uma melhoria ao algoritmo do working set é 
organizar as páginas na forma de uma lista circular, percorrendo-as no sentido horário. Esse é o 
algoritmo WS-Clock. 
 
Escalonamento de disco 
Por ser um componente mecânico, um ponto em que um algoritmo eficaz pode acelerar acessos 
ao disco é na movimentação da cabeça de leitura, o chamado seek time. O problema torna-se, então, 
dada uma série de requisições de cilindros, como ordená-las de modo a reduzir a distância percorrida 
pela cabeça de leitura. Uma possibilidade é atender às requisições na ordem em que chegam, 
algoritmo conhecido como First-Come-First-Served (FCFS). Outra possibilidade é ordenar a lista 
de requisições conforme sua distância à posição atual da cabeça (em número de cilindros), e então 
atendê-las nessa ordem. Esse é o algoritmo Shortest Seek First (SSF). Por fim, uma terceira 
possibilidade é o algoritmo do Elevador. Assim como ocorre em um elevador, o algoritmo define 
uma direção inicial (crescente ou decrescente no número dos cilindros), e vai se movendo no disco 
nessa direção, atendendo as requisições em seu caminho. Ao chegar no último cilindro, ele inverte a 
direção, voltando no disco e atendendo as demais requisições. 
 
Alocação de arquivos em disco 
Em um sistema de arquivos, estes são geralmente organizados como uma sequência não 
estruturada de bytes, com seus bytes agrupados em blocos. Para gerenciar esses blocos, uma 
alternativa bastante comum é o uso de tabelas, como a FAT – File Allocation Table. Uma FAT nada 
mais é que um arranjo cujos índices correspondem aos blocos do disco (ou seja, possui tantos 
elementos quanto o disco tiver blocos). Nesse modelo, o diretório que “armazena” o arquivo contém, 
de fato, o endereço (índice na tabela) do primeiro bloco desse arquivo. Nessa posição da FAT há então 
o endereço (índice) do segundo bloco. Nessa nova posição há o endereço do terceiro bloco, e assim 
por diante, até se chegar ao endereço do último bloco, em cuja posição há um marcador de final (o 
valor -1 por exemplo). Consulte a videoaula 28, slide 7, para uma ilustração de FAT. 
Outra possibilidade é a organização do sistema por meio de uma lista de i-nodes (index-nodes) 
– uma estrutura contendo os atributos de um arquivo e seus endereços de blocos de disco. Em geral, 
o i-node é feito do tamanho de um bloco. Há espaço então para os atributos e alguns endereços de 
bloco – os endereços diretos. Em sua organização mais simples, o último endereço no bloco é 
reservado para um bloco extra, contendo mais endereços de disco – os endereços indiretos. Essa 
organização pode ser incrementada com endereços indiretos duplos, triplos etc. Consulte a videoaula 
28, slides 12 a 15, para uma ilustração do funcionamento dos i-nodes.