A more Perfect union

Nesta seção é detalhado como funciona o algoritmo de escalonamento Flow através da apresentação do pseudocódigo do mesmo.

O Algoritmo 1 corresponde à parte principal do algoritmo de escalonamento Flow. Este algoritmo recebe a lista Fluxos a serem escalonados F, o conjunto de dispositivos produtores de informações Do e respectivas taxas de atualização destes produtores. O

Algoritmo Flow retorna uma matriz M de dimensão 15 (número de canais disponíveis no WirelessHART) por lM, que corresponde a quantidade de slots de tempo que equivale

a duração da maior taxa de atualização (PRMax) dentre os dispositivos produtores de in-

formação. Cada elemento da matriz corresponde a uma combinação de canal com um slot de tempo e é preenchida por um link (origem, destino e dispositivo inicial de uma transmissão). Um exemplo pode ser visto na Figura 4.5.

4.2. ALGORITMO FLOW DE ESCALONAMENTO DE MENSAGENS 63

Algoritmo 1: Algoritmo de escalonamento de mensagens Flow.

Entrada: Lista Fluxos a serem escalonados F e Conjunto de dispositivos produtores de informações Docom valores da taxa de atualização;

Saída : Matriz M16xlM escalonada;

M// Superframe com o tamanho da maior taxa de publicação dentre os dispositivos produtores de dados;

TMSF=PRMax/10 ms // Calculo do Tamanho do Maior Superframe ;

Chamar Gerar_Multiplos_Fluxos(); for Todos os slots t, sendo 0<=t<TSF do

while t<TMSF e (ainda há fluxos não escalonados em F) do

Ordenar Fluxos F de acordo com o esquema de ordenamento escolhido; Gerar o conjunto dos Fluxos Ativos F′_;

// F′_{: Conjunto dos fluxos em que F}

i.Liberação<= t <Fi.Deadline e que

NÃO estejam finalizados; for todo F′i ∈F’do

//Ser escalonável significa que nenhum dos dispositivos envolvidos na transmissão (origem e destino) estejam escalonados neste slot em outro canal (Seja como origem ou destino) e que exista um canal livre para a alocação.;

if F_i′.ProximoHop for escalonável no slot t then

Escalonar em M F′_{i.ProximoHop em um canal ch disponível no}

slot t ;

Atualizar Fluxo F;

if A alocação NÃO for bem sucedida then Retorne “Erro de Alocação”;

end end end t++; end end

Em seguida é chamada a função Gerar_Multiplos_Fluxos, que tem por objetivo adap- tar os fluxos com taxas de atualização menores que a taxa de atualização máxima que define o superframe representado pela matriz M. Essa adaptação consiste em calcular quantas vezes o fluxo tem de ser repetidamente alocado dentro da matriz M, uma vez que vários pacotes podem ser produzidos no tempo em que os dispositivos com maior taxa de atualização produzem um único pacote. É importante notar que os tempos de liberação e de deadline das mensagens devem ser adaptados para que os slots reservados possam ser utilizados e não fiquem ociosos. O Algoritmo 2 representa a Função Ge- rar_Multiplos_Fluxos. Ele inicia com o conjunto de todos os Fluxos F e todas as taxas de atualização configuradas nos dispositivos produtores de dados. A saída deste algoritmo é o conjunto de fluxos F atualizado com os novos fluxos criados a partir dos fluxos com taxas de atualização menores. Para cada dispositivo produtor de dados Do, cuja taxa de

atualização seja igual a maior dentre os dispositivos, é criado um fluxo com liberação igual a zero e o deadline igual ao último slot do maior superframe. Este Fluxo criado é adicionado ao conjunto F.

Caso o dispositivo possua uma taxa de atualização menor que a taxa máxima, é calcu- lado um fator K (número inteiro positivo) que significa quantas vezes aquele fluxo deve ser escalonado dentro de M. Assim, são criados K fluxos que têm sua liberação e seu deadlinealterados de modo que cada fluxo tenha uma janela de transmissão com a dura- ção igual a sua taxa de atualização. Estas janelas são definidas de modo que elas não se sobreponham. Ao final os fluxos criados são adicionados a F. Após a chamada à função da Gerar_Multiplos_Fluxos, o algoritmo principal é retomado e itera todos os slots de tempo t enquanto ainda existam fluxos para serem alocados. A cada iteração, os fluxos são ordenados de acordo com a prioridade previamente escolhida. A partir deste conjunto de fluxos ordenados, é criado o subconjunto dos fluxos ativos F′_{. F}′_{consiste nos fluxos}

que estão dentro de sua janela de transmissão e que ainda não foram finalizados. Para cada item F′

i, é verificado se o próximo link pertencente a Fi′ é escalonável na-

quele slot de tempo t. Ser escalonável significa que nenhum dos dispositivos envolvidos na transmissão (origem e destino) estão escalonados neste slot de tempo em outro canal (seja como origem ou destino) e que exista pelo menos um canal livre para a alocação naquele slot de tempo. Em caso positivo, o slot é escalonado no slot t e canal ch e o fluxo em questão é atualizado em termos de qual o próximo link será escalonado ou se o fluxo foi finalizado. Em caso negativo, o link deste fluxo não é escalonado e o algoritmo segue para o próximo fluxo F′

i. Terminado os fluxos em F′, o algoritmo incrementa o slot t e

prossegue até que todos os links de todos os fluxos sejam alocados ou que t ultrapasse o número de slots disponiveis.

4.2. ALGORITMO FLOW DE ESCALONAMENTO DE MENSAGENS 65

Algoritmo 2: Algoritmo da Função Gerar_Multiplos_Fluxos.

Entrada: Conjunto Fluxos a serem escalonados F e Conjunto de dispositivos produtores de informações Docom valores da taxa de atualização;

Saída : Conjunto ATUALIZADO de fluxos a serem escalonados F; // PRiTaxa de Publicação dispositivo i;

// MPR A maior dentre as taxas de Publicação dentre os dispositivos que produzem dados (iniciais) nos Fluxos;

for Para cada Dispositivo Produtor de dados Dopertencente a F do

if PRDo < MPR then

K = MPR/PRDo// K é Número de repetições do fluxo ;

T SFPRi= PRi/10 ms //Tamanho do superframe baseado em PRDo;

for i = 0 até K do

Criar Novo Fluxo NF a partir dos caminho entre Doe o destino

fornecido pelo roteamento; NF.Liberação = K*T SFPRi;

NF.Deadline = (K*T SFPRi+(T SFPRi-1);

Adicionar NF a F end

else

Criar Novo Fluxo NF a Partir dos caminho entre Doe o destino fornecido

pelo roteamento;

NF.Liberação = 0 // O Release é o primeiro slot do maior superframe; NF.Deadline = (MPR/10ms)-1 // O deadline é o Último slot do maior superframe;

Adicionar NF a F; end