Armazenamento de Arquivos Grandes em Dvds

Armazenamento de Arquivos Grandes em DvdsMAC5758 - Introducao ao Escalonamento e Aplicacoes

Viviane Teles de Lucca Maranhao

Instituto de Matematica e Estatıstica da Universidade de Sao Paulo

Dezembro de 2009

1 / 21

Armazenamento de Arquivos Grandes em Dvds

Sumario

1 Introducao

2 Objetivos

3 Heurısticas

4 Exemplo

5 Implementacao

6 Proximas Etapas

7 Referencias Bibliograficas

2 / 21

Armazenamento de Arquivos Grandes em Dvds

Introducao

O problema

Problema Principal

Dados n arquivos de tamanhos t1, t2, ... , tn, distribuı-los em xDVDs de tamanho C de modo que x seja o menor possıvel.

3 / 21

Armazenamento de Arquivos Grandes em Dvds

Introducao

Exemplos de areas com problemas semelhantes

Carpintaria;

Industrias;

Emissoras de televisao.

4 / 21

Armazenamento de Arquivos Grandes em Dvds

Introducao

Formulacao

Bin-packing

Dadas L = < a1, a2, ..., an > uma lista com numeros no intervalo(0, 1], e uma sequencia de bins (recipentes) com capacidadeunitaria B1,B2, .... Encontrar uma atribuicao dos numeros aos binsde modo que em nenhum bin a soma dos numeros atribuıdos a eleseja maior que 1, e tal que o numero de bins utilizados eminimizado.

5 / 21

Armazenamento de Arquivos Grandes em Dvds

Objetivos

Objetivos

Estudar heurısticas de resolucao do Bin-packing ;

Elaborar um programa em Python que sugira gravacoes dearquivos passados pelo usuario em uma mıdia de tamanhodado.

6 / 21

Armazenamento de Arquivos Grandes em Dvds

Heurısticas

Terminiologia

Um recipiente aberto e aquele no qual podemos inserir itens;

Um recipiente fechado e aquele no qual nao podemos maisinserir itens;

R∞A e a razao assintotica de pior caso

R∞A (α) e a razao assintotica de pior caso com tamanholimitado dos itens;

R∞A (F ) e a razao assintotica esperada para A sob F .

7 / 21

Armazenamento de Arquivos Grandes em Dvds

Heurısticas

Heurısticas Online

Next-Fit (NF)

Descricao

Mantem apenas um recipiente aberto por vez; quando um novorecipiente precisa ser aberto o anterior e fechado.

Desempenho

R∞NF = 2

R∞NF (α) = 11−α , α < 1

2

R∞NF (U[0, 1]) = 43

8 / 21

Armazenamento de Arquivos Grandes em Dvds

Heurısticas

Heurısticas Online

First-Fit (FF)

Descricao

Insere o item no primeiro recipiente possıvel, ou abre um novo senao couber nos abertos ate o momento.

Desempenho

R∞FF∼= 1.69103

Para 1m+1 < α ≤ 1

m

R∞FF (α) = 1.7 se m = 1 e R∞FF (α) = 1 + 1m , se m ≥ 2

R∞FF (U[0, 1]) = 1

9 / 21

Armazenamento de Arquivos Grandes em Dvds

Heurısticas

Heurısticas Online

Best-Fit (BF)

Descricao

A cada alocacao todos os recipientes sao avaliados e o queapresentar a menor sobra de espaco apos a alocacao e selecionado.Assim como nos casos anteriores, um novo recipiente e abertoquando nao e possıvel alocar o item em nenhum dos recipientesanteriores.

Desempenho

R∞BF (α) = R∞FF (α)

R∞FF (U[0, 1]) = 1

10 / 21

Armazenamento de Arquivos Grandes em Dvds

Heurısticas

Heurısticas Online

Worst-Fit (WF), Almost-Worst-Fit (AWF)

Descricao

O WF seleciona o recipiente no qual que resta o maior espaco aposa alocacao. O AWF aloca o item no recipiente que apos a alocacaodeste apresente a segunda maior sobra de espaco.

Desempenho

R∞WF (α) = R∞NF (α), 0 < α ≤ 1

R∞AWF (α) = R∞FF (α), 0 < α ≤ 1

11 / 21

Armazenamento de Arquivos Grandes em Dvds

Heurısticas

Heurısticas Offline

First-Fit-Decreasing (FFD), Best-Fit-Descreasing (BFD)

Descricao

Ordenam o vetor com os itens em ordem nao crescente detamanho antes de aplicar o FF ou o BF, respectivamente. Pelapossibilidade de ordenacao previa garantem melhor desempenhoque seus respectivos algoritmos online.

Desempenho

R∞FFD = R∞BFD = 119 = 1.222...

12 / 21

Armazenamento de Arquivos Grandes em Dvds

Exemplo

Instancia

Vamos considerar a seguinte lista de objetosL = (a1, a2, a3, a4, a5, a6, a7, a8) com seus tamanhosS(L) = ( 1

2 ,34 ,

38 ,

25 ,

23 ,

18 ,

35 ,

14 ) mostrada na figura 1.

Figura: Exemplo de uma lista de objetos

13 / 21

Armazenamento de Arquivos Grandes em Dvds

Exemplo

Solucao utilizando heuristicas online

14 / 21

Armazenamento de Arquivos Grandes em Dvds

Exemplo

Solucao utilizando heuristicas offline

15 / 21

Armazenamento de Arquivos Grandes em Dvds

Implementacao

Estrutura do programa

Linguagem utilizada: Python 2.6 com a biblioteca graficawxpython versao 2.8.Separamos o programa em dois arquivos:

organizador.py Interface grafica para o usuario entrar com asinformacoes: tamanho da mıdia, lista de arquivos e metododesejado para resolucao, e que apos rodar o metodo apresentauma sugestao de gravacao.

metodos.py Contem a implementacao das heurısticas deempacotamento citadas anteriormente.

16 / 21

Armazenamento de Arquivos Grandes em Dvds

Implementacao

Screenshot do programa

17 / 21

Armazenamento de Arquivos Grandes em Dvds

Implementacao

Screenshot do programa

18 / 21

Armazenamento de Arquivos Grandes em Dvds

Proximas Etapas

Passos a serem realizados

1 Teste do programa implementado para diversas instancias;

2 Analise dos resultados obtidos confrontando com os esperados;

3 Elaboracao das conclusoes.

19 / 21

Armazenamento de Arquivos Grandes em Dvds

Referencias Bibliograficas

Johnson D. S., Near-optimal bin packing algorithms,Massachusetts Institute of Technology (1973)

Xavier, E. C., Miyazawa F. K., Algoritmos para Problemas deEmpacotamento, Anais do XXVII Congresso da SBC, CTD,XX Concurso de Teses e Dissertacoes, p1966 - 1973, Rio deJaneiro (2007)

Hochbaum, D. , Approximation algoritms for NP-hardproblems, PWS Publishing Company, Boston (1995)

Wronski, F., Alocacao Dinamica de Tarefas em NoCs Malhacom Reducao do Consumo de Energia, Universidade Federaldo Rio Grande do Sul, Dissertacao de Mestrado, Porta Alegre,(2007)

Coffman E. G, et. Al. Average Analysis of on-line Bin-packingAlgorithms. OR-Seminar, Michaelmas (1996)

20 / 21

Armazenamento de Arquivos Grandes em Dvds

Fim

Obrigada

21 / 21