Desafio 3: Desfragmentação

Você já ouviu falar em desfragmentação de disco?

Se você usou computadores na década de 1990, muito provavelmente se lembra da necessidade de deixar o seu computador desfragmentando o disco rígido noite a fora de vez em quando.

Essa ação era necessária porque a velocidade de acesso a um disco fragmentado era muito inferior a de um disco desfragmentado e o funcionamento de sistemas operacionais como o Windows inevitavelmente faziam com que os discos ficassem fragmentados.

Mas o que isso significa? Ao salvarmos informações em um disco rígido, pedaços de um mesmo arquivo podem acabar sendo gravados em regiões distantes ou mesmo fora de ordem. Isso é esperado, já que podemos iniciar um arquivo, gravá-lo no disco, iniciarmos um segundo arquivo, que vai acabar sendo gravado no espaço adjacente ao primeiro, e depois voltarmos ao primeiro acrescentando mais conteúdo. Isso faz com que o primeiro arquivo fique dividido em dois pedaços separados pelo segundo arquivo, como na Figura 1.

Figura 1

Mais ainda, se apagamos um arquivo antigo, teremos um espaço livre no disco que pode acabar sendo preenchido com uma nova parte de um outro arquivo, bagunçando ainda mais a ordem das coisas.

Desfragmentar o disco significa justamente reordenar o conteúdo dos pedaços de memória de modo a agrupar e ordenar os pedaços de um mesmo arquivo, fazendo com que a leitura do disco seja mais rápida.

Porém, desfragmentar um disco pode exigir muitas ações! Por exemplo, a Figura 2 mostra um disco fragmentado com 3 arquivos (laranja com 3 trechos, verde com 2 trechos e bege com 2 trechos) e três espaços em branco.

Figura 2

Gostaríamos que ele ficasse como mostrado na Figura 3: pedaços de um mesmo arquivo juntos e em ordem e, além disso, com todos os espaços livres no final. Note que a ordem entre os arquivos não é importante, ou seja, também seria considerada desfragmentada uma configuração que começasse com o arquivo verde.

Figura 3

Mas para desfragmentar um disco, a única ação permitida é mover o conteúdo de um espaço de memória para um espaço livre.

Por exemplo, partindo da situação mostrada na Figura 2, podemos fazer o movimento 4→7, obtendo o disco mostrado na Figura 4, mas não poderíamos fazer a troca 3→6 diretamente, pois isso significaria perder o conteúdo do espaço 6 da memória.

Figura 4

A desfragmentação de discos é um processo necessário até hoje em alguns dispositivos e ainda não se conhece um algoritmo capaz de realizá-la sempre com o menor número de movimentos possível, o que economizaria processamento e energia. Esse é o seu desafio!

Nos links abaixo, você pode interagir com alguns discos fragmentados e tentar desfragmentá-los com o mínimo de movimentos.

Disco 1 Disco 2 Disco 3 Disco 4

Dessa vez, o desafio da ANPMat não vai receber vídeos com as soluções, mas vai convidar estudantes e professores a compartilharem suas soluções para cada um dos discos no nosso perfil do Instagram.

Boa desfragmentação!