O objetivo deste exercício-programa é determinar um
escalonamento de tarefas em máquinas idênticas.
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 máximo dos tempos de operação das máquinas (makespan ou duração do escalonamento). Em outras palavras, encontrar um escalonamento que minimize o tempo de execução do conjunto de tarefas.
Informalmente, o problema do escalonamento em máquinas idênticas
consiste no seguinte.
Dada uma sequência de inteiros positivos
num_maquinas num_tarefas duracao[0] duracao[1] ... duracao[num_tarefas-1]onde num_maquinas é o número de máquinas, num_tarefas é o número de tarefas, e para t = 0, 1, ..., num_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 três máquinas (0, 1 e 2) e
sete tarefas (0, 1, 2, 3, 4, 5 e 6)
com os tempos de execução dados a seguir.
número da tarefa : 0 1 2 3 4 5 6 duração : 4 2 1 5 9 2 6
Um possível escalonamento dessas tarefas entre as três máquinas é:
máquina : tarefas atribuídas tempo total
0 : 0 4 13
1 : 1 6 8
2 : 2 3 5 8
duração do escalonamento : 13
| tarefas: | 0 | 4 |
| máquina 0: | 4 | 9 |
| tarefas: | 1 | 6 |
| máquina 1: | 2 | 6 |
| tarefas: |
2 | 3 | 5 |
| máquina 2: | 1 | 5 | 2 |
Um escalonamento de duração mínima para o exemplo acima é:
máquina : tarefas atribuídas tempo total
0 : 0 2 3 10
1 : 1 5 6 10
2 : 4 9
duração do escalonamento : 10
| tarefas: | 0 | 2 | 3 |
| máquina 0: | 4 | 1 | 5 |
| tarefas: | 1 | 5 | 6 |
| máquina 1: | 2 | 2 | 6 |
| tarefas: | 4 |
| máquina 2: | 9 |
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 optimalidade e ganho de eficiência é o objetivo de algoritmos de aproximação.
O primeiro algoritmo de aproximação para o problema do escalonamento foi
apresentado e analisado por R.L. Graham e usa um critério muito simples:
atribuir as tarefas, uma a uma, destinando cada tarefa à máquina 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. É possível provar que o algoritmo de Graham encontra
um escalonamento cuja duração é no máximo o dobro da duração mínima de um
escalonamento.
Algoritmo de Graham
máquina : tarefas atribuídas tempo total
0 : 0 5 6 12
1 : 1 4 11
2 : 2 3 6
duração do escalonamento : 12
| tarefas: | 0 | 5 | 6 |
| máquina 0: | 4 | 2 | 6 |
| tarefas: | 1 | 4 |
| máquina 1: | 2 | 9 |
| tarefas: | 2 | 3 |
| máquina 2: | 1 | 5 |
A razão de aproximação nesse caso é 12/10 = 1.2, que é de fato
menor que 2, como prometido pelo algoritmo.
Existe uma variante do algoritmo de Graham que coloca as tarefas em ordem
decrescente de tempo antes de começar o processo de escalonamento.
Pode-se provar que essa variante encontra um escalonamento cuja duração é no máximo 4/3 da
duração mínima de um escalonamento.
Variante do algoritmo de Graham
maquina : tarefas atribuídas tempo total
0 : 4 2 10
1 : 6 1 5 10
2 : 3 0 9
duração do escalonamento : 10
| tarefas: | 4 | 2 |
| máquina 0: | 9 | 1 |
| tarefas: | 6 | 1 | 5 |
| máquina 1: | 6 | 2 | 2 |
| tarefas: | 3 | 0 |
| máquina 2: | 5 | 4 |
A razão de aproximação nesse caso é 10/10 = 1.0, que é de fato menor que 4/3, como prometido pelo algoritmo. Na realidade, como vocês podem perceber, o escalonamento obtido pela variante do algoritmo de Graham é, por acaso, um escalonamento de duração mínima.
Escreva um programa que resolva o problema do escalonamento de tarefas em máquinas idênticas. O programa deve seguir o seguinte roteiro:
Seu algoritmo de busca exaustiva pode supor que a tarefa 0 é sempre atribuída à máquina 0. (Note que não há perda de generalidade com essa suposição, pois as máquinas são idênticas.)
O arquivo de saída deve conter as seguintes informações:
A seguir escrevemos uma possível saída (parcial) para a instância descrita acima.
(1) Informações gerais:
número de máquinas = 3 número de tarefas = 7
número da tarefa : 0 1 2 3 4 5 6
duração : 4 2 1 5 9 2 6
(2) Informações sobre o escalonamento obtido pelo algoritmo de Graham:
- Duração do escalonamento : 12
- Tempo total de trabalho de cada máquina
máquina tempo total
0 12
1 11
2 6
- Tarefas atribuídas a cada máquina
máquina tarefas atribuídas
0 0 5 6
1 1 4
2 2 3
- Número de tarefas atribuídas a cada máquina
máquina número de tarefas
0 3
1 2
2 2
- Informações de cada tarefa
tarefa duração máquina
0 4 0
1 2 1
2 1 2
3 5 2
4 9 1
5 2 0
6 6 0
(3) Informações sobre o escalonamento de duração mínima obtido pela busca exaustiva:
... [informações similares às do ítem (2) acima]
(4) Razão de aproximação do escalonamento obtido pelo algoritmo
de Graham : 12/10 = 1.2
int main(int argc, char *argv[])
{
FILE *entrada; /* arquivo de entrada */
FILE *saida; /* arquivo de saida */
int no_maquinas; /* numero de maquinas */
int no_tarefas; /* numero de tarefas */
int *duracao; /* vetor de duracoes das tarefas:
duracao[t] e' a duracao da tarefa t */
int *t_maquina; /* vetor com os tempos de trabalho das maquinas:
t_maquina[m] contem a soma das duracoes das
tarefas associadas `a maquina m */
int *escalonamento; /* vetor com um escalonamento:
escalonamento[t] contem o indice da maquina
associada `a tarefa t */
int duracao_graham; /* duracao de um escalonamento de Graham */
int duracao_min; /* duracao de um escalonamento de duracao minima */
...
}
Outras funções.
Implemente em seu programa, obrigatoriamente, as seguintes funções:
int escalonamento_graham(int no_tarefas, int duracao[], int no_maquinas,
int t_maquina[], int escalonamento[]);
Esta função recebe nos três primeiros parâmetros uma instância do problema do escalonamento. Ela armazena em t_maquina e
escalonamento as informações sobre um escalonamento obtido
com o algoritmo de Graham e devolve como valor da função a duração desse
escalonamento.
É dentro da função escalonamento_graham que deve estar o min-heap mencionado
no ítem 2 das especificações do programa.
(Dica:
Os elementos do min-heap podem ser os índices das máquinas.
Nesse caso, se o vetor h for o min-heap,
então cada h[i] será um índice de máquina. Note que a
comparação entre h[i] e h[j] deve ser baseada
nos tempos das máquinas correspondentes, isto é, em
t_maquina[h[i]] e t_maquina[h[j]].)
int escalonamento_busca_exaustiva(int limitante,
int no_tarefas, int duracao[], int no_maquinas,
int t_maquina[], int escalonamento[]);
Determina um escalonamento de duração mínima, por busca exaustiva, e
devolve como valor da função a duração desse escalonamento.
O parâmetro limitante é o valor inicial do limitante
mencionado no ítem 4 das especificações do
programa. Os demais parâmetros são análogos aos da função
escalonamento_graham.
void peneira_min_heap(int p, int no_maquinas, int h[], int t_maquina[]);Esta é a função peneira do min-heap usado pelo algoritmo de Graham.
void imprime_escalonamento (FILE *saida, int duracao_escalonamento,
int no_tarefas, int duracao[], int no_maquinas,
int t_maquina[], int escalonamento[]);
Escreve no arquivo especificado pelo parâmetro saida as
informações sobre o escalonamento representado pelos demais parâmetros. Essas
informações devem aparecer como no exemplo de saída
fornecido.
/**************************************************************************/
/* Aluno: Fulano de Tal */
/* Número USP: 12345678 */
/* Curso: ... */
/* Exercicio-Programa 4 -- Escalonamento de tarefas em maquinas identicas */
/* MAC0122 -- 2009 -- IME/USP, turma XX -- Prof. YYYYY */
/* Compilador: ... (gcc ou Code::Blocks) versão ... */
/* Sistema Operacional: ... */
/**************************************************************************/
gcc ou o
Code::Blocks (que na verdade chama o gcc para
fazer a compilação). Caso você use diretamente o gcc, passe
ao compilador (na linha de comando) as seguintes opções:
-Wall -ansi -pedantic -O2 -U_FORTIFY_SOURCECaso você use o
Code::Blocks, entre em
Settings -> Compiler and debugger... -> Compiler settings -> Compiler Flags,
selecione as quatro opcões correspondentes a -Wall,
-ansi, -pedantic e -O2, e clique
em OK. Entre também em
Settings -> Compiler and debugger... -> Compiler settings -> Other options,
digite -U_FORTIFY_SOURCE na caixa de texto
Other options e clique OK.
ep4-<seu-número-USP>.c.
Exemplo: Se seu número USP for 12345678, você deverá
entregar um arquivo com o nome ep4-12345678.c.
(Note que não há espaços no nome do arquivo.)