RELATORIO_SO

Prévia do material em texto

Relatório Técnico – Trabalho de Sistemas Operacionais
Vinı́cius Lourenço de Ponte1,
Rodolfo Borri de Souza1
1Departamento de Informática – Universidade Estadual de Maringá (UEM)
87.020-900 – Maringá – PR – Brasil
{ra115700,ra96639}@uem.br
Sumário
1 Descrição do Trabalho 3
2 Introdução e Tecnologias Utilizadas 4
3 Desenvolvimento 5
3.1 Mapa de Bits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3.2 Lista Encadeada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.3 Sistema Buddy - First Fit . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.4 Sistema Buddy - Next Fit . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.5 Sistema Buddy - Best Fit . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.6 Sistema Buddy - Quick Fit . . . . . . . . . . . . . . . . . . . . . . . . . 13
4 Considerações Finais 19
1. Descrição do Trabalho
O trabalho realizado por nossa equipe foi desenvolvido de acordo com as instruções des-
critas abaixo:
”Em Sistemas Operacionais o gerenciador de memória é um módulo do sistema
operacional que gerencia a memória principal e a área de memória secundária. Um ge-
rente de memória possui algumas funções básicas como controlar as áreas de memória em
uso e as disponı́veis. Para esse gerenciamento existem duas técnicas, a monoprogramação
e a multiprogramação. Dada essa definição, vimos na disciplina algumas formas de como
o gerenciador se comporta, ou seja, alguns de seus algoritmos.Esses algoritmos, são:
• Mapa de Bits;
• Lista encadeada de espaços disponı́veis;
• Sistema Buddy.
O trabalho consiste na implementação desses três problemas. Apesar de parecer
trabalhoso a implementação é simples. Para o mapa de bits você deve ler um arquivo de
entrada preenchido com zeros e uns. Para a Lista encadeada você deve utilizar ponteiros
e para o Sistema Buddy você pode utilizar um vetor (uma hipótese, seja criativo). Para a
implementação desse trabalho, alguns critérios devem ser seguidos:
1. O trabalho pode ser feito em, no máximo, duas pessoas.
2. A linguagem na qual o trabalho deverá ser desenvolvido deverá ser em C, Python
ou Pascal.
3. Um único relatório técnico em PDF no formato de artigo deverá ser enviado jun-
tamente com os arquivos do trabalho.
Tentem conversar entre si para que não existam trabalhos semelhantes, como por
exemplo: três duplas escolhem o mesmo algoritmo de gerenciamento. Ou também, pode-
se alterar a forma de resolver o problema, como por exemplo: Uma dupla utilizará pilha,
outra dupla utilizará fila, e assim por diante.
DICAS: Leia o livro do TANEMBAUM, Andrew S. ”Sistemas Operacionais Mo-
dernos. São Paulo, 2003. Nele existem algumas implementações de gerenciamento,
mesmo que visual. Tente verifica-lo para que você possa dar inı́cio a sua implementação.
É permitido utilizar ferramentas que auxiliem o desenvolvimento do trabalho em qualquer
linguagem, porém, não esqueça de explicar como utilizá-lo. Em hipótese alguma copie
ou plagie trabalhos da internet ou dos colegas de sala. É muito fácil descobrir se alguém
copiou de outra pessoa ou se pegou um trabalho pronto do github. Caso o plágio seja
encontrado o trabalho será zerado.”
2. Introdução e Tecnologias Utilizadas
O código desenvolvido se refere à segunda avaliação da disciplina de Sistemas Operacio-
nais ministrada pelo professor Felippe Fernandes da Silva.
O intuito do desenvolvimento deste trabalho é detalhar a implementação de três
principais algoritmos de gerenciamento de memória: Mapa de Bits, Lista Encadeada e
Sistema Buddy, seguindo as instruções fornecidas pelo professor no documento original.
No algoritmo de Mapa de Bits, a memória é subdividida em unidades de um de-
terminado tamanho, e então se associa a cada unidade um bit: se esse bit for igual a 0,
significa que parte da memória está disponı́vel; se esse bit for igual a 1, significa que parte
da memória está ocupada.
No algoritmo de Lista Encadeada, mantemos uma lista encadeada de todos os
blocos livres do disco, com cada bloco possuindo uma área reservada para armazenar o
endereço do próximo bloco. Para cada novo bloco alocado, inclui-se um novo item na
lista.
No algoritmo do Sistema Buddy, o gerente de memória mantém uma lista dos blo-
cos livres para cada tamanho múltiplo de 2, com a memória inteira estando disponı́vel ao
iniciarmos o sistema. Para este trabalho, detalharemos quatro algoritmos para a alocação
de memória: First Fit, Next Fit, Best Fit e Quick Fit.
No First Fit, o sistema escolhe a primeira área grande o suficiente para se alocar
o processo desejado; o Next Fit segue a mesma estratégia que o First Fit, porém inicia
sua pesquisa de espaço por onde parou na última vez; o Best Fit irá percorrer toda a lista
para encontrar o espaço mais adequado para efetuar o encaixe do processo desejado; e,
por fim, o Quick Fit separa as listas por tamanhos de áreas disponı́veis que mais foram
solicitadas.
Este documento tem como função explicar a execução e o propósito dos proce-
dimentos desenvolvidos para a execução dos algortimos de gerenciamento de memória e
como eles se interligam para garantir o devido funcionamento de cada um.
Para o desenvolvimento deste trabalho foi utilizada a linguagem C.
A IDE utilizada foi o Dev-C++ na Versão Estável 5.11.
3. Desenvolvimento
Para demonstrarmos o devido funcionamentos dos algoritmos de gerenciamento de
memória desenvolvidos, foram implementadas as funções ”printaProcesso”e ”printaMe-
moria”para o Mapa de Bits, ”printa lista”para a Lista Encadeada e ”printa processos”para
os algoritmos de encaixe do Sistema Buddy. Como o intuito dessas funções é apenas re-
presentar visualmente o andamento do algoritmo, não as detalhamos neste documento;
este documento foca apenas em explicar e entender a lógica por trás dos algoritmos re-
quisitados.
3.1. Mapa de Bits
Figura 1. Algoritmo Principal do Mapa de Bits
Para o correto funcionamento do algoritmo de Mapa de Bits, carregamos um arquivo que
possui processos diversos separados por quebras de linha, descritos com 1 caso sejam um
processo ou 0 caso sejam um buraco. O arquivo utilizado para leitura deste trabalho
se encontra dentro da raı́z do documento enviado ao professor. Para garantir a
execução adequada do algoritmo, pedimos para que o caminho do arquivo no código-
fonte seja alterado para corresponder ao caminho do arquivo de texto fornecido por
nossa equipe.
Primeiramente, temos um while que lê todos os processos contidos no arquivo
para identificar o tamanho a ser utilizado do pente de memória. Feito isso, retornamos o
cursor ao inı́cio do arquivo e executamos outro while para printar os processos carregados,
separando-os com um espaço em branco a cada 8 bits do pente em questão para uma
melhor visualização.
3.2. Lista Encadeada
Figura 2. Algoritmo Principal da Lista Encadeada
Para o devido funcionamento do algoritmo de Lista Encadeada, carregamos um arquivo
que possui processos diversos separados por quebras de linha, descritos com 1 caso sejam
um processo ou 0 caso sejam um buraco.
Primeiramente, temos um while que lê todos os processos contidos no arquivo
analogamente ao algoritmo de Mapa de Bits, mas agora substituindo o caractere de que-
bra de linha pelo caractere de final de string. Logo após a leitura de um processo, o
adicionamos à lista encadeada de processos disponı́veis.
Figura 3. Lista Encadeada - Procedimento ”add lista”
Contido no procedimento “addLista”, temos uma condição que verifica se o pro-
cesso lido é o primeiro elemento da lista: caso positivo, criamos a lista encadeada reali-
zando a alocação do primeiro elemento da mesma; caso contrário, preenchemos devida-
mente os dados do novo elemento em questão e o adicionamos ao final da lista.
Figura 4. Lista Encadeada - Procedimento ”cria lista”
Para o preenchimento dos dados do elemento, possuimos o método ”preencheDa-
dosElemento”,no qual realizamos a distinção entre processo e buraco do processo em
questão. Para isso, verificamos o primeiro caractere do processo vindo do arquivo e o
transformamos em inteiro. Em seguida, verificamos se este inteiro é 0 ou 1. Caso seja 0,
sabemos que é um buraco; caso seja 1, sabemos que é um processo.
Figura 5. Lista Encadeada - Procedimento ”preencheDadosElemento”
Feita a verificação, realizamos o cálculo para determinar o inı́cio do novo elemento
a ser inserido na lista juntamente à análise de seu comprimento, obtida ao calcularmos
seu tamanho. A partir das etapas descritas, inserimos este elemento na lista e repetimos
esse processo até que não existam mais elementos dentro do arquivo que carregamos
inicialmente.
3.3. Sistema Buddy - First Fit
Para o algoritmo do First Fit do Buddy System, temos primeiramente um array de pro-
cessos contendo números inteiros que se referem ao tamanho de processos junto de outro
array de caracteres que representa os processos do nosso array de processos (Ex.: Pro-
cesso 70 = Caractere A).
Figura 6. Algoritmo Principal do First Fit
Iniciamos o programa chamando o procedimento ”cria lista inicial”que cria uma
lista com apenas um elemento de tamanho 1024, pré-definido no cabeçalho do algoritmo.
Após isso, faremos um for que percorerrá todos os processos contidos no array e iremos
adicioná-los à memória seguindo o padrão First Fit.
Figura 7. First Fit - Procedimento ”cria lista inicial”
Para a realização do First Fit, seguimos o fluxo abaixo:
Figura 8. First Fit - Procedimento ”first fit”
1. Começamos com uma variável de controle chamada ”inserido”para verificar se o
processo foi ou não inserido na memória;
2. Percorremos a lista utilizando uma variável auxiliar ”aux”que, enquanto ela for
diferente de nula, verificamos as condições a seguir:
• Caso o tamanho dessa variável for maior ou igual ao tamanho da memória
e caso a metade do tamanho da memória dessa variável for menor que o
tamanho do processo a ser inserido (não é possı́vel dividir essa memória
para alocarmos o processo em questão) e caso a variável não esteja alocada
(não existe um processo já ocupando este espaço), podemos então inserir
um processo neste espaço de memória.
• Se alguma das verificações acima falhar, executamos a seguinte condição:
Caso o tamanho dessa variável for maior ou igual ao tamanho da memória
e caso a metade do tamanho da memória dessa variável for maior ou igual
que o tamanho do processo a ser inserido (é possı́vel dividir a memória no-
vamente para alocarmos o processo em questão) **e** caso a variável não
esteja alocada (não existe um processo já ocupando este espaço), conse-
guimos então chamar o procedimento ”add lista”.
3. O procedimento ”add lista”obtém a variável representando um elemento da lista
e a divide por 2. Isso nos permite verificar se, nesse novo elemento dividido, o
processo encaixa no espaço em questão.
Figura 9. First Fit - Procedimento ”add lista”
4. Executamos então novamente o laço de repetição sem prosseguir ao elemento pos-
terior, para que consigamos observar e validar se o elemento em questão encaixa
no novo espaço dividido.
5. Caso nenhuma das condições descritas no passo 2 forem satisfeitas, apenas passa-
mos para o próximo elemento da lista;
6. Validamos então se o elemento de agora consegue satisfazer as condições descri-
tas, para assim realizarmos a inserção do processo respectivo na lista represen-
tando o pente de memória.
7. Finalizamos a inserção de processos mostrando o estado atual do pente de
memória para cada processo inserido.
Após realizada a inserção de processos, agora realizamos a remoção de todos estes
processos. Para isto, seguimos o fluxo abaixo:
Figura 10. First Fit - Procedimento ”remove processo”
1. Primeiro utilizaremos a chave do processo para encontrar o processo que quere-
mos remover;
2. Para realizar essa busca, percorremos todos os processos do pente de memória
comparando suas respectivas chaves com a chave que desejamos encontrar;
3. Caso não encontremos o processo, mostramos uma mensagem indicando que não
foi possı́vel encontrar o processo em questão;
4. Caso encontremos o processo, verificamos a possibilidade de realizarmos o merge
desse espaço de memória com o espaço agora liberado através do procedimento
”verifica possibilidade merge”;
5. No procedimento ”verifica possibilidade merge”, temos um while que irá percor-
rer a lista de processos sempre observando o próximo elemento. Com essa aborda-
gem, o único problema que surge é o fato de não conseguirmos verificar a cabeça
da lista.
6. Para resolver este problema e conseguirmos identificar se o primeiro elemento da
lista é passı́vel de merge, verificamos as seguintes condições:
Figura 11. First Fit - Procedimento ”verifica possibilidade merge”
• Caso o tamanho de memória da cabeça da lista for igual ao tamanho de
memória do elemento removido e a cabeça da lista não está alocada, po-
demos então realizar o merge (adição do tamanho de memória da cabeça
da lista com o tamanho de memória do elemento removido) e fazer com
que a cabeça da lista seja o próximo elemento dela mesma — removendo,
dessa forma, o primeiro elemento da lista e garantindo que a cabeça seja
efetivamente o próximo elemento.
• Se alguma das verificações acima falhar, executamos a seguinte condição
— dessa vez, utilizando o elemento ”aux”como base: Caso o tamanho de
memória do próximo elemento do auxiliar for igual ao tamanho do ele-
mento removido e o próximo elemento do auxiliar não esteja alocado, po-
demos então realizar o merge (adição do tamanho de memória do próximo
elemento do auxiliar com o tamanho de memória do elemento a ser re-
movido) e fazer com que o próximo elemento do auxiliar seja o ”próximo
do próximo”elemento do auxiliar, removendo efetivamente um elemento
desse fluxo.
7. Caso qualquer validação descrita no passo acima seja válida, iremos buscar um
novo merge: um novo elemento que seja passı́vel de merge com o elemento a ser
removido.
8. Para isso, atribuı́mos a cabeça da lista para a variável auxiliar e chamamos a
próxima execução do laço de repetição.
9. Por fim, caso nenhuma das validações funcione, iremos para o próximo elemento
da lista de processos.
3.4. Sistema Buddy - Next Fit
Para o Next Fit, as regras de merge e de inserção são exatamente iguais às regras descritas
no First Fit, contendo e seguindo as mesmas validações e fluxos. O único diferencial é
que, para cada inserção, armazenamos o elemento em que paramos para que na próxima
vez que se realizar uma inserção seja possı́vel percorrer a partir desse elemento. Caso não
encontremos opções de inserção a partir do elemento em questão até o fim da lista, iremos
novamente iniciar a busca do começo da lista, fazendo novamente um laço de repetição
que começa na cabeça da lista e indo até o elemento atual – elemento em que paramos.
Figura 12. Next Fit - Condição Única
3.5. Sistema Buddy - Best Fit
O Best Fit, analogamente ao Next Fit, também segue as mesmas regras descritas no First
Fit. O diferencial desta vez está na inserção: nesse caso, percorremos toda a lista de
processos verificando se já não existe um elemento no espaço de memória disponı́vel
para realizarmos a inserção. Caso não exista um espaço disponı́vel, realizamos a mesma
regra descrita no First Fit: a partir da cabeça da lista, dividimos a memória e executamos a
inserção em algum dos espaços agora disponı́veis, liberados graças às divisões resultantes.
Figura 13. Best Fit - Condição Única
3.6. Sistema Buddy - Quick Fit
Figura 14. Algoritmo Principal do Quick Fit
O Quick Fit segue uma linha diferente do restante dos algoritmos de encaixe. Da mesma
forma que os algoritmos anteriores, temos os processos representados por um array de
inteiros e suas chaves representadas por um array de caracteres.
Inicialmente,realizamos um laço de repetição percorrendo todos os elementos
contidos no array de processos a fim de determinar o tamanho médio utilizado para a
alocação de memória. Após determinados o tamanho médio dos processos a serem alo-
cados, criamos a lista inicial, contendo apenas um processo correspondente ao tamanho
inicial pré-definido no cabeçalho, e a partir dela realizamos a divisão de memória, deta-
lhada no procedimento ”divide memoria”.
Figura 15. Quick Fit - Procedimento ”divide memoria”
No procedimento ”divide memoria”, encontramos o valor em base 2 que é maior
que o tamanho médio. Feito isso, descobrimos a quantidade de vezes que é necessário
realizar a divisão da memória através da conta a seguir:
Figura 16. Quick Fit - Variável ”numeroDeDivisoes”
Com esse número de divisões, criamos um laço de repetição que realizará a di-
visão da memória utilizando o tamanho em base 2 que calculamos. Após o final desse,
a memória se encontrará dividida x vezes, com cada espaço da memória possuindo o
mesmo tamanho e com a soma de todos esses espaços resultando no tamanho da memória
inicial — nesse caso, 1024 bytes.
Continuando, percorremos o array de processos realizando a inserção de cada
processo utilizando o ”tipo Quick Fit”. Como já calculamos a média de espaço necessário
para a alocação de processos previamente, a probabilidade de inserção imediata na lista
de processos no Quick Fit é maior. Contudo, pode haver alguns processos em que será
necessário realizar o merge de dois ou mais espaços de memória que estejam disponı́veis
para serem alocados.
Dito isso, o fluxo que temos para o Quick Fit se dá por:
Figura 17. Quick Fit - Procedimento ”quick fit”
1. Iremos percorrer a lista de processos começando da cabeça da lista;
2. Temos uma variável de controle ”merge realizado”que verifica se um merge de
dois espaços de memória foi executado;
3. Validaremos inicialmente se o tamanho da memória do elemento auxiliar é maior
ou igual ao tamanho do processo a ser inserido e se o espaço de memória deste
elemento auxiliar já não está alocado, o que nos permite realizar a alocação do
elemento neste espaço de memória;
4. Caso contrário, se o tamanho da memória do elemento auxiliar for menor que
o tamanho do processo a ser inserido (que, dessa vez, é maior que o tamanho
alocado como média) e que o espaço de memória deste elemento auxiliar não
está alocado, então realizamos um merge de dois ou mais elementos da lisa de
processos para alocar este processo novo.
Para o processo de merge, seguimos o fluxo abaixo:
Figura 18. Quick Fit - Procedimento ”realiza merge”
1. Temos duas variáveis de controle para manipularmos o merge:
”merge realizado”e ”elementos para merge”;
2. Percorremos a lista de processos com inı́cio na cabeça da lista e sempre apontando
para o próximo elemento;
3. Por causa disso, precisamos discernir então se a própria cabeça da lista é um can-
didato ou não para merge.
4. Portanto, validamos a cabeça da lista da seguinte forma: caso o tamanho de
memória da cabeça da lista for igual ao tamanho de memória designado para
merge e a cabeça da lista não está alocada, então conseguimos incrementar a
variável ”elementos para merge”em uma unidade;
5. Feito isso, realizamos um laço de repetição que percorre a lista de processos
olhando para o próximo elemento até que um merge aconteça ou até que seja
nulo;
6. Dentro do laço, realizamos a seguinte validação: Se o tamanho de memória do
próximo elemento do auxiliar for igual ao tamanho de memória designado para
merge e o próximo elemento do auxiliar não está alocado, significa que o elemento
está pronto e disponı́vel para o merge. Continuamos então com outra condição:
• Caso a quantidade de ”elementos para merge”for maior que zero, reali-
zamos então o merge, definido como: o tamanho de memória do auxi-
liar recebe o tamanho de memória designado para merge + o tamanho de
memória do próximo elemento do auxiliar. O próximo elemento do auxi-
liar será agora o ”próximo do próximo”elemento do auxiliar, removendo
efetivamente um elemento da lista. Finalizando a execução da condição,
alteramos a variável de controle ”merge realizado”para 1 e encerramos a
execução do laço;
• Caso a quantidade de ”elementos para merge”seja igual a zero, apenas
incrementamos a variável em questão.
7. Após a execução da condição descrita no passo acima, passamos para o próximo
elemento da lista;
8. Concluindo a descrição do método, retornamos como resposta a própria variável
de controle ”merge realizado”.
Com o retorno da chamada da função ”realiza merge”, verificamos se a variável de
controle ”merge realizado”é ou não igual a 1. Caso positivo, executamos o algoritmo do
inı́cio novamente para validar se é possı́vel inserir o processo nesse espaço de memória
mergeado, onde, caso ainda não seja possı́vel a inserção desse processo, realizaremos
o merge até que seja possı́vel executar a inserção devidamente. Ao final da execução,
passamos para o próximo elemento da lista.
Com o final da execução do laço que percorre todos os processos, conseguimos
observar se os processos contidos no array foram ou não devidamente alocados.
Para se realizar a remoção de algum processo, temos o seguinte fluxo:
Figura 19. Quick Fit - Procedimento ”remove processo”
1. De forma análoga aos outros algoritmos de Fit, faremos a busca pelo processo
através da chave do processo;
2. Caso não encontremos o processo, mostramos uma mensagem indicando que não
foi possı́vel encontrar o processo em questão;
3. Caso encontremos o processo, verificamos então a possibilidade de divisão da
memória novamente, uma vez que para cada ”desalocação”é necessário retornar a
lista ao seu estado inicial — nesse caso, com seu tamanho de memória em base 2
calculado previamente;
4. Para verificar a possibilidade de divisão, precisamos entender o procedimento res-
ponsável por isso:
• Primeiramente, utilizamos uma variável auxiliar para percorrer toda a lista
de processos;
• Com isso, executamos um laço de repetição que se encerra quando essa
variável auxiliar for nula;
• Para averiguar a divisão, temos a seguinte condição:
Caso o tamanho de memória da variável auxiliar for maior que o tama-
nho final de alocação (valor calculado em base 2) e a variável auxiliar
não estar alocada, criamos um novo elemento que possuirá as seguintes
configurações: não está alocado, não possui chave, seu tamanho de
memória é igual a metade do tamanho da memória da variável au-
xiliar e seu próximo elemento corresponde ao próximo elemento da
variável auxiliar (estamos essencialmente colocando este novo elemento
no meio da lista);
• Alteramos também o elemento da variável auxiliar: agora, o tamanho da
memória auxiliar será metade de seu próprio valor e o próximo elemento
da variável auxiliar é o novo elemento criado anteriormente.
• Feito isso, atribuimos a cabeça da lista ao elemento auxiliar (o que nos
permite iniciar a busca por divisões novamente) e chamamos a execução
do próximo laço.
• Caso a validação inicial não seja verdadeira, apenas vamos ao próximo
elemento da variável auxiliar.
Concluindo, realizamos tanto a inserção dos processos com a utilização da es-
tratégia de Quick Fit, efetuando merges caso seja necessário a alocação de espaços mai-
ores que o valor calculado na base 2, quanto a remoção dos processos — este também
sendo executado através da divisão da memória para seu estado inicial, com seu tamanho
de memória sendo previamente o valor calculado em base 2.
4. Considerações Finais
Abordamos neste trabalho a implementação e documentação dos algoritmos de geren-
ciamento de memória requisitados: Mapa de Bits, Lista Encadeada e Sistema Buddy.
A decisão pela utilização da linguagem C para o desenvolvimento foi influenciada pela
familiaridade da equipecom os artefatos da linguagem. A maior dificuldade superada
durante o desenvolvimento dos algoritmos está relacionada à implementação dos proce-
dimentos de merge utilizados no Sistema Buddy, já que necessitavam de uma abordagem
recursiva em certos pontos de seu funcionamento, o que levou a realização de diversos
testes para garantir que o algoritmo estava funcionando apropriadamente e não quebrava
alguma restrição imposta anteriormente.
Referências
TANEMBAUM, A. S. Sistemas operacionais modernos. são paulo, 2003.