Projeto e Análise de Algoritmos I

Aula 16 - Algoritmos Gulosos: Escalonamento para Minimização de Atraso Máximo e Caching

Lucas Nunes Alegre

Universidade Federal do Rio Grande do Sul
Instituto de Informática
Departamento de Informática Teórica


Estes slides utilizam conteúdo adaptado da bibliografia da disciplina e também de notas de aula e slides prévios dos professores Bruno Grisci, Rodrigo Machado, André Grahl Pereira, Lucas Nunes Alegre, Marcus Ritt e Luciana Buriol.

Algoritmos Gulosos

Algoritmos Gulosos

“Embora a gula seja considerada um dos sete pecados capitais, acontece que algoritmos gulosos frequentemente tem uma performance muito boa.”

— Stuart Russell

Algoritmos Gulosos

Ideia Geral:

  • Realizamos uma sequência de passos.
  • A cada passo, fazemos uma escolha.

Premissa dos Algoritmos Gulosos:

  • A escolha é aquela que parece ser a melhor no momento (miópica).
  • Essa escolha é denominada escolha gulosa.
  • É feita de acordo com um critério guloso.

Algoritmos Gulosos

Definição. Um algoritmo guloso é aquele que constrói a solução global para o problema a partir de decisões locais ótimas.

Observação. Quando um algoritmo guloso resolve um problema otimamente, isso implica em algo fundamental sobre a estrutura do problema.

Algoritmos Gulosos

Divisão e Conquista vs. Algoritmos Gulosos:

Divisão e Conquista Algoritmos Gulosos
Propor Algoritmos Difícil Fácil
Análise de Complexidade Difícil Fácil
Corretude Fácil Difícil Demonstrar


Observação. A maioria das estratégias gulosas não são corretas (não garantem a solução ótima).

Provas de Corretude

Ficar à Frente:

  • Mostra que após cada passo do algoritmo guloso, a solução atual é tão boa quanto qualquer outra solução.

Argumento da Troca:

  • Transforma gradualmente qualquer solução para a encontrada pelo algoritmo guloso sem piorar a qualidade da solução.

O que Funcionar:

  • Prova por indução, estrutural, contradição.

Escalonamento para Minimizar Atraso

Minimizar Atraso Máximo

Definição:

  • Um único recurso que processa uma tarefa por vez.
  • A tarefa j requer tempo {\color{green}{t}}_j para completar e tem um deadline de {\color{purple}{d}}_j.
  • Se a tarefa j inicia em {\color{blue}{s}}_j, ela termina em {\color{blue}{s}}_j + {\color{green}{t}}_j.
  • O atraso da tarefa j é {\color{orange}{l}}_j = \max\{0, {\color{red}{f}}_j - {\color{purple}{d}}_j\}.
  • Objetivo é alocar todas as tarefas minimizando o atraso máximo {\color{orange}{L}} = \max_j {\color{orange}{l}}_j.
Tarefa 1 t1 = 1 d1 = 2 Tarefa 2 t2 = 2 d2 = 4 Tarefa 3 t3 = 3 d3 = 6 Solução Tarefa 1 Tarefa 2 Tarefa 3 0123456

Minimizar Atraso Máximo

Note que aqui estamos minimizando o atraso máximo, mas poderíamos ter outros objetivos:

  • Minimizar o número de tarefas com atraso.
  • Minimizar a soma dos atrasos de todas as tarefas.
  • Minimizar o atraso final após todas as tarefas serem executadas.
  • \dots

Cada objetivo pode necessitar de algoritmos diferentes, e pode não haver uma estratégia gulosa ótima.

Exemplo de Alocação

Considere as seguintes tarefas:

j tj dj 1 3 6 2 2 8 3 1 9 4 4 9 5 3 14 6 2 15


Observe que a seguinte alocação não é ótima: a tarefa 1 possui atraso 2, e a tarefa 4 possui atraso 6 (no caso, o atraso máximo):


d3 = 9 d2 = 8 d6 = 15 d1 = 6 d5 = 14 d4 = 9 0123456789101112131415 atraso = 2 atraso = 0 atraso = 6

Visualização Interativa

Estratégias Gulosas para Minimizar Atraso Máximo

Estratégia Gulosa: Considera alocar as tarefas em alguma ordem natural.

P. Qual ordem?

  1. Menor Duração Primeiro: Considera as tarefas por ordem de {\color{green}{t}}_j.
  1. Menor Folga: Considera as tarefas por ordem de {\color{purple}{d}}_j - {\color{green}{t}}_j.
  1. Menor Deadline: Considera as tarefas por ordem de {\color{purple}{d}}_j.


Pergunta: Alguma funciona?

Exemplo de Instância (1)

Teste as seguintes estratégias para minimizar o atraso máximo:

  1. menor tempo de duração {\color{green}{t}}_j
  2. menor folga ({\color{purple}{d}}_j - {\color{green}{t}}_j)
  3. menor deadline {\color{purple}{d}}_j


Instância 1:

Tarefa a b c
Duração ({\color{green}{t}}) 1 2 6
Deadline ({\color{purple}{d}}) 3 2 7
  • Menor duração: a, b, c (maxAtraso = 2)
  • Menor folga: b, c, a (maxAtraso = 6)
  • Menor deadline: b, a, c (maxAtraso = 2)

Exemplo de Instância (2)

Teste as seguintes estratégias para minimizar o atraso máximo:

  1. menor tempo de duração {\color{green}{t}}_j
  2. menor folga ({\color{purple}{d}}_j - {\color{green}{t}}_j)
  3. menor deadline {\color{purple}{d}}_j


Instância 2:

Tarefa a b c
Duração ({\color{green}{t}}) 4 5 3
Deadline ({\color{purple}{d}}) 10 6 9
  • Menor duração: c, a, b (maxAtraso = 6)
  • Menor folga: b, a, c (maxAtraso = 3) ou b, c, a (maxAtraso = 2)
  • Menor deadline: b, c, a (maxAtraso = 2)

Escalonamento para Minimizar Atraso Máximo

\begin{algorithmic} \Procedure{MenorDeadlinePrimeiro}{$\{t_1, d_1\}, \ldots, \{t_n, d_n\}$} \State \texttt{Sort}$(\{t_1, d_1\}, \ldots, \{t_n, d_n\})$ \Comment{Em ordem crescente de deadline} \State $t \leftarrow 0$ \For{$j = 1$ \textbf{to} $n$} \State $j \leftarrow [t, t + t_j]$ \State $s_j \leftarrow t;\ f_j \leftarrow t + t_j$ \State $t \leftarrow t + t_j$ \EndFor \EndProcedure \end{algorithmic}


j tj dj 1 3 6 2 2 8 3 1 9 4 4 9 5 3 14 6 2 15 d1 = 6 d2 = 8 d3 = 9 d4 = 9 d5 = 14 d6 = 15 0123456789101112131415 atraso = 1

Correção de MenorDeadlinePrimeiro

Observação 1. Existe uma solução ótima sem tempo ocioso.

d = 4 d = 6 d = 12 ocioso ocioso 01234567891011 d = 4 d = 6 d = 12 01234567891011

Observação 2. MenorDeadlinePrimeiro produz uma alocação sem tempo ocioso.

Correção de MenorDeadlinePrimeiro (2)

Definição. Dado um escalonamento S, uma inversão é um par de tarefas i e j tal que: d_i < d_j, mas j é alocado antes de i (onde d_i e d_j correspondem aos deadlines das tarefas).

j i inversão fi

Observação 3. MenorDeadlinePrimeiro não tem inversões.

Observação 4. Se um escalonamento tem uma inversão, ele tem uma inversão com tarefas consecutivas.

Correção de MenorDeadlinePrimeiro (3)

j i fi i j f′j

Afirmação. Trocar duas tarefas adjacentes invertidas reduz o número de inversões e não aumenta o atraso máximo.

Demonstração. Seja {\color{orange}{l}} o atraso antes da troca, e {\color{orange}{l}}' o atraso depois da troca.

Primeiro, {\color{orange}{l}}_k' = {\color{orange}{l}}_k para toda tarefa k diferente de i, j, e {\color{orange}{l}}_i' \leq {\color{orange}{l}}_i.

Se j possui atraso: \begin{aligned} {\color{orange}{l}}_j' &= {\color{red}{f}}_j' - {\color{purple}{d}}_j \\ {\color{orange}{l}}_j' &= {\color{red}{f}}_i - {\color{purple}{d}}_j \\ {\color{orange}{l}}_j' &\leq {\color{red}{f}}_i - {\color{purple}{d}}_i \\ {\color{orange}{l}}_j' &\leq {\color{orange}{l}}_i \qquad \blacksquare \end{aligned}

Correção de MenorDeadlinePrimeiro (4)

Teorema. O MenorDeadlinePrimeiro é ótimo.

Demonstração. Seja S^* uma solução ótima.

  • S^* não tem tempo ocioso.
  • Se S^* não tem inversões, então S^* = S.
  • Se S^* tem uma inversão, seja i, j uma inversão adjacente.
  • Trocar i e j não aumenta o atraso e diminui o número de inversões.
  • Argumento da troca: repetindo as trocas adjacentes, eliminamos todas as inversões sem aumentar o atraso máximo. \blacksquare

Escalonamento para Minimizar Atraso Máximo: Extensão

  • Na versão estudada, o algoritmo tem liberdade para decidir quando executar qualquer tarefa.
  • E se, para cada tarefa, além da sua duração e do seu deadline, houvesse também um horário de lançamento (release time), sendo que a tarefa deve ser executada antes do seu deadline mas depois do seu lançamento?
  • Essa versão do problema é muito mais difícil.

Caching

Caching Offline Ótimo

  • Cache com capacidade para armazenar k itens.
  • Sequência de m requisições de itens d_1, d_2, \dots, d_m.


  • Cache hit (acerto): item está na cache quando requisitado.
  • Cache miss (falta): item não está na cache quando requisitado.
    • Neste caso, deve-se remover (evict) algum item da cache para trazer o item requisitado.


Objetivo: Escalonamento de remoção que minimize o número de faltas na cache.

Caching Offline Ótimo: Exemplo

Exemplo: k = 2, cache inicial = \{a, b\}, requisições: a, b, c, b, c, a, b.

Escalonamento ótimo: 2 remoções (cache misses).

início 1 2 3 4 5 6 7 requisição cache resultado abcbcab aaacccaa bbbbbbbb acerto acerto falta remove a acerto acerto falta remove c acerto

Aplicações de Caching

Aplicações:

  • CPU
  • RAM
  • Disco rígido
  • Web
  • Browser
  • \dots


Visualização: https://brunogrisci.github.io/schedulingalgorithms

Caching Offline Ótimo: Algoritmos Gulosos

  • LIFO/FIFO: Remove o item trazido para a cache mais (menos) recentemente.

  • LRU (Least Recently Used): Remove o item cujo acesso recente foi o mais antigo.

  • LFU (Least Frequently Used): Remove o item que foi menos frequentemente requisitado.

cache requisições ⋮····· aawxyz dawxdz aawxdz babxdz cabcdz eabcde g????? b e d ⋮ FIFO: remove a LRU: remove d LIFO: remove e falta na cache (qual item remover?)

Caching Offline Ótimo: Farthest-in-Future

Farthest-in-future (Mais distante no futuro): Remove o item da cache que não será requisitado até o momento mais distante no futuro.

cache requisições aabcde f????? a b c e g b e d ⋮ falta na cache (qual item remover?) FF: remove d

Teorema [Bélády 1966]. FF (Farthest-in-future) produz o escalonamento ótimo de remoções.

Demonstração. O algoritmo e o teorema são intuitivos; a prova é sutil.

Quiz: FF

Pergunta: Qual item vai ser removido seguindo o algoritmo FF?

cache requisições ⋮···· BDBYA CDBCA EDECA F???? C D A E A C ⋮ falta na cache (qual item remover?)

Escalonamentos de Remoção Reduzidos

Definição. Um escalonamento reduzido é um escalonamento que traz um item d para a cache no passo j somente se houver uma requisição por d no passo j e d não estiver já na cache.

Ideia Intuitiva: Não faz sentido trazer itens para a cache antes que eles sejam necessários, ou quando já estão lá.

aabc aabc cadc dadc aacb bacb cacb ddcb ddcd aabc aabc cabc dadc aadc badb cacb ddcb ddcb d entra na cache sem requisição d entra na cache mesmo já estando nela escalonamento não-reduzido escalonamento reduzido

Escalonamentos de Remoção Reduzidos

Afirmação. Dado qualquer escalonamento não-reduzido S, podemos transformá-lo em um escalonamento reduzido S' com o mesmo número ou menos remoções.

Demonstração [por indução no número de passos j]:

  • Suponha que S traga d para a cache no passo j mesmo que d não seja requisitado.
  • Seja c o item que S remove quando traz d para a cache.
  • Caso 1a: d é removido de S antes de ser requisitado.
escalonamento não-reduzido S S′ passo j passo j′ ··c ··c ··c ¬d··d ¬d··d ¬d··d e··e ··e ··c ··c ··c ¬d··c ¬d··c ¬d··c e··e ··e d entra na cache sem requisição d é removido antes da próxima requisição de d podemos deixar c na cache até d ser removido

Escalonamentos de Remoção Reduzidos

Afirmação. Dado qualquer escalonamento não-reduzido S, podemos transformá-lo em um escalonamento reduzido S' com o mesmo número ou menos remoções.

Demonstração [por indução no número de passos j]:

  • Suponha que S traga d para a cache no passo j mesmo que d não seja requisitado.
  • Seja c o item que S remove quando traz d para a cache.
  • Caso 1b: próxima requisição de d ocorre antes da remoção de d.
escalonamento não-reduzido S S′ passo j passo j′ ··c ··c ··c ¬d··d ¬d··d ¬d··d d··d ··d ··c ··c ··c ¬d··c ¬d··c ¬d··c d··d ··d d entra na cache sem requisição d ainda está na cache na próxima requisição de d podemos deixar c na cache até d ser requisitado

Escalonamentos de Remoção Reduzidos

Afirmação. Dado qualquer escalonamento não-reduzido S, podemos transformá-lo em um escalonamento reduzido S' com o mesmo número ou menos remoções.

Demonstração [por indução no número de passos j]:

  • Suponha que S traga d para a cache no passo j mesmo que d já esteja na cache.
  • Seja c o item que S remove quando traz d para a cache.
  • Caso 2a: d é removido antes de ser requisitado.
escalonamento não-reduzido S S′ passo j passo j′ d1ac d1ac d1ac dd1ad3 dd1ad3 ccad3 bcab dcad3 d1ac d1ac d1ac dd1ac dd1ac ccac bcab dcad3 d3 entra na cache mesmo com d1 já na cache d3 não é necessário d3 é removido d3 é necessário podemos deixar c na cache até d3 ser removido

Escalonamentos de Remoção Reduzidos

Afirmação. Dado qualquer escalonamento não-reduzido S, podemos transformá-lo em um escalonamento reduzido S' com o mesmo número ou menos remoções.

Demonstração [por indução no número de passos j]:

  • Suponha que S traga d para a cache no passo j mesmo que d já esteja na cache.
  • Seja c o item que S remove quando traz d para a cache.
  • Caso 2b: d é requisitado antes de ser removido.
escalonamento não-reduzido S S′ passo j passo j′ d1ac d1ac d1ac dd1ad3 dd1ad3 ccad3 acad3 dcad3 d1ac d1ac d1ac dd1ac dd1ac ccac acac dcad3 d3 entra na cache mesmo com d1 já na cache d3 não é necessário d3 é necessário podemos deixar c na cache até d3 ser necessário

Escalonamentos de Remoção Reduzidos (4)

Demonstração [continuação]:

  • Caso 1: S traz d para a cache no passo j sem que haja uma requisição por d. ✓ (Resolve-se da mesma forma: postergando a inserção até o momento da requisição)
  • Caso 2: S traz d para a cache no passo j mesmo que d já esteja na cache. ✓ (Visto nos slides anteriores)
  • Se há múltiplos itens não-reduzidos no passo j, aplicamos a transformação a cada um, lidando com o Caso 1 antes do Caso 2. \blacksquare


Observação: Resolver o Caso 1 pode acabar engatilhando o Caso 2.

Farthest-in-Future: Análise

Teorema. FF é o algoritmo ótimo de remoção.

Demonstração. Segue diretamente do seguinte invariante:

Invariante. Existe um escalonamento ótimo reduzido S que realiza as mesmas remoções que o S_{FF} durante os primeiros j passos.


Prova completa: Seção 4.3 do livro Algorithm Design, de Kleinberg e Tardos.

Perspectiva de Caching

Algoritmos Online vs. Offline:

  • Offline: sequência completa de requisições é conhecida a priori.
  • Online (realidade): requisições não são conhecidas com antecedência.
  • Caching é um dos problemas online mais fundamentais na Ciência da Computação.
  • Last-in-first-out (LIFO): Remove o item trazido mais recentemente.
  • Least-Recently-Used (LRU): Remove o item cujo acesso mais recente foi o mais antigo.
  • Farthest-in-future (FF): Remove o item cujo próximo acesso é o mais distante no futuro (LRU com a direção do tempo invertida!).

Teorema. FF é o algoritmo ótimo de remoção offline.

  • Fornece uma base teórica para entender e analisar algoritmos online.
  • Experimentalmente, variantes do LRU funcionam muito bem no caso online.

Algoritmos em Python

Algoritmos de Escalonamento

https://github.com/BrunoGrisci/projeto-e-analise-de-algoritmos/blob/main/paa1/scheduling.ipynb

Conclusão

Análise de Estratégias Gulosas

  • Algoritmo guloso fica à frente: Mostrar que, após cada passo, a solução do algoritmo guloso é pelo menos tão boa quanto a de qualquer outra estratégia.
    • Ex: Escalonamento de Intervalos.
  • Argumento estrutural: Encontrar um limitante simples que toda solução possível deve satisfazer e provar que o algoritmo sempre atinge esse valor.
    • Ex: Particionamento de Intervalos.
  • Argumento da troca: Transformar gradualmente qualquer solução em outra com as mesmas escolhas do algoritmo guloso sem piorar sua qualidade.
    • Ex: Escalonamento para Minimizar Atraso Máximo.
  • Outros algoritmos gulosos: Gale-Shapley, Kruskal, Prim, Dijkstra, Huffman, entre outros.

?