MAC0122 - Princípios de Desenvolvimento de Algoritmos
Departamento de Ciência da Computação do IME-USP
Turma da Engenharia da Computação - POLI
Segundo semestre de 2024

Quarto Exercício-Programa

Escalonamento de tarefas em máquinas idênticas

Entrega: 5 de novembro

O objetivo deste exercício-programa é exercitar o uso de ordenação e filas de prioridade. O EP5 vai usar algumas coisas desenvolvidas neste EP.

Um problema bastante conhecido nos contextos de produção industrial e de sistemas operacionais é o de escalonamento (scheduling) de tarefas em máquinas. Estamos interessados em uma das versões mais simples do problema: dadas m máquinas idênticas e n tarefas com tempos de execução ou durações pré-determinados, encontrar uma atribuição das tarefas às máquinas que minimize o tempo máximo de operação de qualquer uma das máquinas (makespan ou duração do escalonamento).

Informalmente, o problema do escalonamento em máquinas idênticas consiste no seguinte. Dados inteiros positivos

     no_maquinas  no_tarefas  duracao[0] duracao[1] duracao[2] ... duracao[n0_tarefas-1],
onde no_maquinas é o número de máquinas, no_tarefas é o número de tarefas, e para t = 0,1,...,no_tarefas-1, duracao[t] é o tempo de execução da tarefa t, deseja-se distribuir todas as tarefas entre as máquinas (em outras palavras, deseja-se escalonar as tarefas) de modo que o tempo máximo de operação que qualquer uma das máquinas necessita para executar as tarefas atribuídas a ela seja o menor possível.

Exemplo: Considere 3 máquinas (0, 1 e 2) e 7 tarefas com os tempos de execução dados a seguir. 

 no. da tarefa :  0  1  2  3  4  5  6 
 duração       :  6  2  3  5  4  3  7

Um possível escalonamento dessas tarefas entre as três máquinas é:

   maquina:  tarefas       tempo
       0  :   0   3   6      18
       1  :   1   4           6
       2  :   2   5           6

   duração do escalonamento: 18
tarefas:  0 3 6
maquina 0: 6 5 7

1 4
maquina 1: 2 4

2 5
maquina 2: 3 3

Um escalonamento de duração mínima para o exemplo acima é: 

   maquina:  tarefas       tempo
       0  :   0   4          10
       1  :   1   2   3      10
       2  :   5   6          10

  duração do escalonamento:  10

0 4
maquina 0: 6 4

1 2 3
maquina 1: 2 3 5

5 6
maquina 2: 3 7


Algoritmos de aproximação e escalonamento de Graham

O problema do escalonamento de tarefas é um problema computacionalmente difícil. Só se consegue determinar um escalonamento de duração mínima para instâncias de tamanhos bem modestos. Por exemplo, para encontrar um escalonamento de duração mínima de 40 tarefas entre 2 máquinas pode-se consumir horas de computação. Nessa situação, é razoável tentar encontrar rapidamente um escalonamento de duração "não muito grande" em vez de um de duração mínima. Este compromisso entre perda de otimalidade e ganho de eficiência é o objetivo de algoritmos de aproximação.

O primeiro algoritmo de aproximação para o problema do escalonamento de tarefas foi apresentado e analisado por Ronald Graham e usa um critério muito simples: alocar as tarefas uma a uma destinando cada tarefa à maquina menos ocupada. Por esse critério, a escolha da máquina que vai receber determinada tarefa não depende dos tempos das tarefas que ainda não foram atribuídas a nenhuma máquina. O chamado escalonamento de Graham promete encontrar um escalonamento cuja duração é no máximo o dobro da duração mínima de um escalonamento.

Algoritmo de Graham

  1. para j de 0 até no_maquinas-1 faça Mj = { };
  2. para i de 0 até no_tarefas-1 faça
  3. devolva M0, M1, ..., Mno_maquinas-1;
Aplicando o algoritmo de Graham à instância descrita acima, obtemos o escalonamento a seguir: 
   maquina:   tarefas       tempo
       0  :   0   5           9
       1  :   1   3           7
       2  :   2   4   6      14
  
   duração do escalonamento: 14
tarefas:  0 5
maquina 0: 6 3

1 3
maquina 1: 2 5

2 4 6
maquina 2: 3 4 7

A razão de aproximação nesse caso é 14/10 = 1.4, que é de fato menor que 2, como prometido pelo algoritmo.

Uma variante do algoritmo de Graham que coloca as tarefas em ordem decrescente de tempo antes de começar o processo de escalonamento promete encontrar um escalonamento cuja duração é no máximo 4/3 da duração mínima de um escalonamento.

Ao aplicar a variante do algoritmo de Graham à instância acima, usaremos a ordem a seguir: 

 no. da tarefa :  0  1  2  3  4  5  6
 duração       :  6  2  3  5  4  3  7
 ordem         :  6  0  3  4  2  5  1
e obteríamos o seguinte escalonamento: 

   maquina:  tarefas        tempo
       0  :   6   5           10
       1  :   0   2   1       11
       2  :   3   4            9
  
   duração do escalonamento:  11
tarefas:  6 5
maquina 0: 7 3

0 2 1
maquina 1: 6 3 2

3 4
maquina 2: 5 4

A razão de aproximação nesse caso é 11/10 = 1.1, que é de fato menor que 4/3=1.333..., como prometido pelo algoritmo.

Variante do algoritmo de Graham

  1. para j de 0 até no_maquinas-1 faça Mj = { };
  2. para i de 0 até no_tarefas-1 faça
  3. devolva M0, M1, ..., Mno_maquinas-1;

Objetivo do EP

O objetivo do EP é fazer implementações eficientes do algoritmo de Graham e de sua variante descrita acima, e usá-las para resolver instâncias do problema do escalonamento de tarefas em máquinas idênticas.

Para tanto, nas implementações do algoritmo de Graham, você deve usar duas coisas: uma fila de prioridades e ordenação indireta.

A fila de prioridade você vai usar para determinar o índice de uma máquina menos ocupada a cada iteração do algoritmo. A ordenação indireta você vai usar para implementar a variante do algoritmo de Graham.

Fila de prioridades

Implemente uma biblioteca para a seguinte interface heap.h: 
/* ************************************************************ */
/*              Interface para o EP4: heap.h                    */
/* ************************************************************ */
/*        Nao faca nenhuma alteracao neste arquivo.             */
/* ************************************************************ */

struct maquina {
  int id; 
  int carga; 
};

typedef struct maquina Maquina;

int min(Maquina v[]);                               /* devolve o id da máquina com a carga mínima do heap v */

void add_to_minkey(int m, Maquina v[], int delta);  /* reorganiza o heap v[0..m-1] depois de aumentar a carga da máquina de carga mínima de delta */
A sua implementação deve ser eficiente: a função min deve consumir tempo constante e a função add_to_minkey deve consumir tempo proporcional a log m.

Ordenação indireta

Será útil, para implementar a variante acima do algoritmo de Graham, ordenar as tarefas pela duração. Porém se simplesmente ordenarmos o vetor duracao, perderemos os rótulos originais das tarefas. Então, para que isso não aconteça, faremos a ordenação indireta do vetor duracao.

Para fazer isso, monte um vetor id[0..n-1] inicialmente com id[i] = i para i = 0,...,n-1. Agora ordene, com um bom algoritmo de ordenação, esse vetor id de modo que, depois da ordenação, duracao[id[0]] <= duracao[id[1]] <= ... <= duracao[id[n-1]]. O vetor duracao não deverá ser alterado.

Concretamente, implemente no seu programa a função 

void sortInd(int n, int d[], int id[]);  
/* ordena o vetor id[0..n-1] de modo que d[id[0]] <= d[id[1]] <= ... <= d[id[n-1]] */
Sua função sortInd não deve alterar o vetor d e deve consumir tempo O(n log n) (esperado ou no pior caso).

Especificações do programa

Seu programa deve pegar o nome de um arquivo de entrada da linha de comando. Nesse arquivo de entrada estará especificada uma instância no seguinte formato: a primeira linha desse arquivo contém o número de máquinas e o número de tarefas e segunda linha contém os tempos de execução das tarefas. Veja alguns exemplos na próxima seção.

Além da implementação da biblioteca heap.h e da rotina sortInd, o seu programa deve conter a implementação das seguintes funções:

Estas duas funções devolvem um vetor de inteiros com o número da máquina em que cada tarefa deve executar.

A saída do seu programa deve ser a impressão de dois escalonamentos: o escalonamento produzido pela rotina Graham e o escalonamento produzido pela rotina sortGraham. Veja nos arquivos exemplos todas as informações que seu programa deve imprimir.

Arquivos disponibilizados

Arquivos de entrada

Cada arquivo de entrada contém na sua primeira linha dois números inteiros positivos, indicando os valores de m e n. Na linha seguinte, contém uma sequência de n números inteiros positivos, indicando a duração de cada tarefa da instância. Seguem dois exemplos de arquivos nesse formato.

Primeiro exemplo de arquivo de entrada: 

3 6
1 5 3 2 7 1
Segundo exemplo de arquivo de entrada: 
3 7
6 2 1 7 8 2 4
Terceiro exemplo de arquivo de entrada: 
3 7
6 2 3 5 4 3 7

Saída do programa

A saída do seu programa deve imprimir:
  1. o nome do arquivo de entrada, lido da linha de comando;
  2. a impressão da instância lida do arquivo de entrada;
  3. a impressão do escalonamento produzido pela rotina Graham;
  4. a impressão das tarefas em ordem decrescente de duração;
  5. a impressão do escalonamento produzido pela rotina sortGraham.
Veja exemplos de saída do programa abaixo, e siga este padrão.

Saída para o primeiro exemplo de arquivo de entrada: 

Nome do arquivo de entrada: input1

m = 3      n = 6

Tarefas:   0  1  2  3  4  5
Duração:   1  5  3  2  7  1

Algoritmo de Graham:
Tarefa Maquina
   0      0
   1      1
   2      2
   3      0
   4      0
   5      2

Duracao do escalonamento: 10

Tarefas em ordem decrescente de duracao:
4  1  2  3  0  5

Algoritmo de Graham com ordenação:
Tarefa Maquina
   0      2
   1      1
   2      2
   3      2
   4      0
   5      1

Duracao do escalonamento: 7

Saída para o segundo exemplo de arquivo de entrada: 

Nome do arquivo de entrada: input2

m = 3      n = 7

Tarefas:   0  1  2  3  4  5  6
Duração:   6  2  1  7  8  2  4

Algoritmo de Graham:
Tarefa Maquina
   0      0
   1      1
   2      2
   3      2
   4      1
   5      0
   6      0

Duracao do escalonamento: 12

Tarefas em ordem decrescente de duracao:
4  3  0  6  1  5  2

Algoritmo de Graham com ordenação:
Tarefa Maquina
   0      2
   1      1
   2      1
   3      1
   4      0
   5      0
   6      2

Duracao do escalonamento: 10

Saída para o terceiro exemplo de arquivo de entrada: 

Nome do arquivo de entrada: input3

m = 3      n = 7

Tarefas:   0  1  2  3  4  5  6
Duração:   6  2  3  5  4  3  7

Algoritmo de Graham:
Tarefa Máquina
   0      0
   1      1
   2      2
   3      1
   4      2
   5      0
   6      2

Duracao do escalonamento: 14

Tarefas em ordem decrescente de duracao:
6  0  3  4  2  5  1

Algoritmo de Graham com ordenação:
Tarefa Máquina
   0      1
   1      1
   2      1
   3      2
   4      2
   5      0
   6      0

Duracao do escalonamento: 11

Manipulação do arquivo de entrada

  1. O nome do arquivo de entrada deve ser fornecidos pelo usuário através da linha de comando. Para isso considere o trecho de programa a seguir. 
      
int main(int argc, char *argv[]) {
    /* argc = numero de argumentos na linha de comando */
    /* argv = vetor de apontadores para strings contendo esses argumentos */
 
  FILE *entrada; /* declaracao da variavel para o arquivo de entrada */

  [...]
      
  if (argc == 1) {
     printf("Uso: %s <arquivo de entrada>\n", argv[0]);
     return -1;
  }          

  if ((entrada = fopen(argv[1],"r")) == NULL) {
     printf("%s: arquivo de entrada %s nao pode ser aberto.\n", argv[0], argv[1]);
     return -1;
  }

  [...]  /* leitura dos dados */
      
  fclose(entrada);

  [...]  /* restante do programa */    
}
  2. Na leitura dos números contidos no arquivo de entrada você pode utilizar a função fscanf: 
              fscanf(entrada,"%d ", &numero);

O tempo é curto: como se organizar para fazer o EP em tempo?

Comece já, baixando os arquivos e fazendo a parte da leitura dos dados, e impressão da instância.

Primeiro faça uma versão preliminar do algoritmo de Graham que não usa heap. Determine qual é a máquina menos carregada em tempo linear no número de máquinas. Apenas essa parte já deve valer 3.0 pontos. Tente estar com isso pronto no fim desta semana.

Depois que fizer isso, você pode escolher: faça primeiro a ordenação indireta e o sortedGraham, ou então faça a implementação do heap.c e o modifique o Graham para usá-la. Cada uma destas partes deve valer 3.5 pontos.

Recomendações

Siga as informações sobre os EPs, disponibilizadas no início do semestre.

Escreva funções para fazer cada tarefa diferente do EP: por exemplo, escreva uma função que imprime um escalonamento.

A eficiência da sua resolução vai ser levada em conta na sua nota. Use o que foi ensinado nas aulas!

Divirta-se com o EP!