Relat´orio de Simula¸c˜ao com Pol´ıtica de Escalonamento EDF em Sistemas Multiprocessados

Relat´orio de Simula¸c˜ao com Pol´ıtica de
Escalonamento EDF em Sistemas
Multiprocessados
Luciano Pinheiro dos Santos.
Tiago Mesquita de Araujo Cunha.
16 de outubro de 2014
Data: 16 de outubro de 2014
Instrutor: Prof.
a
Fl´avia Maristela
1 Introdu¸c˜ao
Sistemas multiprocessadores passaram a fazer parte do nosso cotidiano, j´a sendo
dif´ıcil encontrar computadores monoprocessados `a venda. O desenvolvimento
de sistemas para computadores com multiprocessadores requer novos paradigmas no desenvolvimento de solu¸c˜oes. Para obter um melhor aproveitamento
desses computadores e uso efetivo de m´ultiplos n´ucleos, novas t´ecnicas de escalonamento e divisibilidade de tarefas passaram a ser adotadas, conforme aponta
Luciano Bertini (2004).
Os sistemas de tempo real tamb´em foram afetados pela ado¸c˜ao de multiprocessadores. Em virtude da grande variedade de processadores multithread possibilitando a execu¸c˜ao de tarefas com t´ecnicas como o pipeline, algumas abordagens
foram propostas para escalonar os processos. Uma destas abordagens define
um escalonamento global: Neste modelo, um ´unico escalonador gerencia todos
os processos que, por sua vez, est˜ao dispostos em uma fila (tamb´em ´unica) e
executados de acordo as prioridades definidas, sendo que ´e permitido a um processo migrar de um processador para outro. Deste modo, partes de um ´unico
processo (threads) podem ser executados em diferentes processadores de acordo
a disponibilidade e a gerˆencia do escalonador.
Em um cen´ario em que o sistema ´e monoprocessado, compete ao escalonador
a preocupa¸c˜ao com os atributos das tarefas (custo, deadline, per´ıodo) e as preemp¸c˜oes (quando houver), de acordo a pol´ıtica de escalonamento adotada. Ao
enveredar para um ambiente com multiprocessamento, outras atribui¸c˜oes s˜ao
adicionadas `as atividades do escalonador, o que requer preocupa¸c˜ao com alguns
aspectos n˜ao considerados quando existe um ´unico processador, como o fato de
haver mem´oria compartilhada (mem´oria cache), barramentos que interligam os
processadores, o custo computacional com interrup¸c˜oes e troca de tarefas entre
1
os processadores, dentre outros. Logo, uma das principais metas desses algoritmos para defini¸c˜ao de pol´ıticas de escalonamento em sistemas multiprocessados
consiste em diminuir as preemp¸c˜oes e otimizar o tempo de execu¸c˜ao global das
tarefas do sistema. Starke (2012)
Neste trabalho iremos abordar alguns aspectos dos sistemas de tempo real e
realizar experimentos com foco na pol´ıtica de escalonamento G-EDF (GlobalEarliest Deadline First), que traduz-se na pol´ıtica EDF, utilizada em sistemas
monoprocessados, aplicada em sistemas multiprocessados.
Esse trabalho ´e formado por 6 se¸c˜oes. Na se¸c˜ao II, apresentada abaixo, s˜ao abordados cinco artigos relacionados a ´area. Na se¸c˜ao III ´e feita a contextualiza¸c˜ao
do problema, abrangendo o referencial te´orico apresentado na se¸c˜ao II. Na se¸c˜ao
IV s˜ao realizados experimentos com a pol´ıtica de escalonamento G-EDF em um
simulador denominado SimSO, escolhido para uso neste trabalho. Na se¸c˜ao V
s˜ao apresentados os resultados e ´e feita a an´alise do comportamento e valores
encontrados. Na se¸c˜ao VI ´e apresentada a conclus˜ao.
1.1 Defini¸c˜oes
Earliest Deadline First Pol´ıtica de escalonamento adotada em alguns sistemas de tempo real onde as tarefas com menor deadline absoluto s˜ao
executadas primeiro.
2 Estado da Arte
Foram selecionados cinco trabalhos correlatos, usados como referencial te´orico
para esse documento. Os trabalhos selecionados possuem caracter´ısticas espec´ıficas abordadas na ´area de sistemas de tempo real com foco em sistemas
multiprocessados e est˜ao listados na subse¸c˜ao abaixo:
2.1 Trabalhos relacionados
Um Breve Survey: Escalonamento em Sistemas de Tempo Real com
Otimiza¸c˜ao do Consumo de Energia
Apresentado em Luciano Bertini (2004) apresenta um survey sobre m´etodos
e pol´ıticas para economia de energia em sistemas de tempo real. Apresenta os sistemas power-aware, como aqueles que conseguem reduzir o seu
consumo em tempo de execu¸c˜ao e os low-power como aqueles de projeto
espec´ıfico, objetivando o melhor consumo sem perda de desempenho. Outras quest˜oes relacionadas a redu¸c˜ao de energia ainda s˜ao abordadas ao
longo desse trabalho.
Uma Abordagem De Escalonamento Heterogˆeneo Preemptivo E N˜ao
Preemptivo Para Sistemas De Tempo Real Com Garantia Em
Multiprocessadores
2
Na disserta¸c˜ao apresentada em Starke (2012) o autor aborda criteriosamente diversos aspectos dos sistemas de tempo real em ambientes multiprocessados. Dentre os diversos aspectos destacados no trabalho de disserta¸c˜ao foi utilizado nesse trabalho a abordagem do autor aos diversos
mecanismos de escalonamento para esses sistemas, como: escalonamento
particionado; global; h´ıbrido.
A Survey of Hard Real-Time Scheduling for Multiprocessor Systems.
Neste survey, Robert I. Davis (2011) apresenta alguns algoritmos de escalonamento em tempo real cr´ıticos (hard), bem como t´ecnicas de an´alise de
escalonabilidade para sistemas com m´ultiplos processadores homogˆeneos.
Os autores focam nos principais resultados neste campo desde as suas
origens na d´ecada de 1960 para uma pesquisa publicada no final de 2009.
S˜ao apresentadas as diferentes caracter´ısticas e m´etodos de alogoritmos de
escalonamento, sendo consideras as diversas m´etricas de desempenho que
podem ser usadas para fins de compara¸c˜ao. Uma an´alise detalhada ´e fornecida destacando os tipos de escalonadores (particionado, global, h´ıbridos)
e os mais recentes resultados de pesquisas emp´ıricas de compartilhamento
de recursos. Ao final, s˜ao propostas quest˜oes a serem solucionadas e os
principais desafios de pesquisa na ´area.
Techniques for Multiprocessor Global Schedulability Analysis.
Em Baruah (2011) o autor faz uma abordagem a diferentes agendadores,
focando na utiliza¸c˜ao do Global EDF, tamb´em apresenta uma modifica¸c˜ao
no funcionamento do Global EDF a fim de solucionar um problema espec´ıfico, tratado no artigo. O Autor tamb´em realiza testes com o agendador Global EDF.
Efficiency Assessment of Job-level dynamic Scheduling Algorithms
on Identical Multiprocessors. Em VAHID SALMANI and NEJAD
(2010) Os autores fazem uma abordagem aos diferentes agendadores poss´ıveis
para o escalonamento de tarefas. Os autores tamb´em abordam os aspectos
do agendamento em sistemas multiprocessador e realizam uma discuss˜ao
entre pol´ıtica de escalonamento EDF e LLF. Os autores ainda fazem um
experimento onde analisam tempo de resposta e outros aspectos de um
sistema de tempo real.
3
3 Contextualiza¸c˜ao do Problema
Um sistema passa a ser considerado como sistema de tempo real (STR) quando,
al´em de executar suas tarefas de maneira logicamente correta, atende `as restri¸c˜oes de temporalidade. Ao atender estas restri¸c˜oes, o sistema torna-se previs´ıvel, sendo a previsibilidade outra caracter´ıstica que distingue os sistemas
convencionais de STRs. O que faz, por exemplo, um sistema de controle da malha ferrovi´aria ser considerado um STR n˜ao ´e o fato deste ser r´apido ou n˜ao: A
execu¸c˜ao das tarefas no instante planejado garante categoriza¸c˜ao deste sistema
como de tempo real.
Garantir que sistemas cr´ıticos como o de controle de uma malha ferrovi´aria, das
aeronaves, de equipamentos m´edico-hospitalar para monitoramento de pacientes
tenham previsibilidade, exige o entendimento dos atributos de uma tarefa, bem
como das pol´ıticas de escalonamento para gerenci´a-las. Estes atributos e seus
conceitos s˜ao apresentados na tabela a seguir.
ATRIBUTOS CONCEITO
Per´ıodo (T
i ) Intervalo regular de ativa¸c˜ao da tarefa.
Deadline (Di ) Tempo de vida (validade) da tarefa.
Custo (Ci ) Dura¸c˜ao m´ınima de uma tarefa.
Tabela 1: Atributos de uma tarefa.
H´a outras propriedades inerentes `as tarefas que devem ser destacadas, segundo
Rˆomulo S. de Oliveira (2000), como as que dizem respeito a criticidade e a
regularidade de ativa¸c˜ao, elencadas a seguir:
• Cr´ıticas (tarefas ”hard”): Uma tarefa ´e dita cr´ıtica quando, ao ser completada depois de seu deadline, pode causar falhas catastr´oficas no sistema
de tempo real e em seu ambiente;
• Brandas ou N˜ao Cr´ıticas (tarefas ”soft”): Essas tarefas, quando se completam depois de seus deadlines, no m´aximo implicam numa diminui¸c˜ao
de desempenho do sistema;
• Peri´odicas: Quando as ativa¸c˜oes do processamento de uma tarefa ocorrem,
numa sequˆencia infinita, uma vez por per´ıodo;
• Aperi´odicas ou Ass´ıncronas: Quando a ativa¸c˜ao ocorre em tempos irregulares (per´ıodos n˜ao previstos);
• Espor´adica: S˜ao tarefas aperi´odicas com caracter´ıstica de execu¸c˜ao em um
intervalo m´ınimo entre duas ativa¸c˜oes consecutivas e conhecidas.
Entender as propriedades inerentes `as tarefas possibilita melhor compreens˜ao e
defini¸c˜ao das pol´ıticas de escalonamento adotadas no gerenciamento das execu¸c˜oes
4
destas no sistema. Para estas pol´ıticas, tamb´em foram associados atributos, resumidos na quadro comparativo abaixo, onde os campos da coluna nomeada
TIPO 1 s˜ao caracter´ısticas opostas `a coluna TIPO 2:
TIPO 1 TIPO 2
Otimizada: quando o algoritmo
provˆe uma solu¸c˜ao ´otima.
Heur´ıstica: por que n˜ao existe uma
solu¸c˜ao ´otima.
Preemptiva: a tarefa pode ser interrompida por um processo de
maior prioridade.
N˜ao-Preemptiva: a tarefa n˜ao sofre interrup¸c˜ao. Executa at´e ser conclu´ıda.
Est´aticos: as decis˜oes das tarefas s˜ao baseadas em parˆametros
fixos.
Dinˆamicos: as decis˜oes das tarefas s˜ao
baseadas em parˆametros que mudam
durante a evolu¸c˜ao do sistema.
Offline: as decis˜oes s˜ao definidas
antes da execu¸c˜ao da tarefa.
Online: as decis˜oes s˜ao tomadas em
tempo de execu¸c˜ao, quando uma nova
tarefa chega ou outra ativa ´e conclu´ıda.
Tabela 2: Quadro comparativo dos atributos de um escalonador.
As caracter´ısticas at´e ent˜ao apresentadas s˜ao de grande relevˆancia quando tratase de sistemas monoprocessados. Com o multiprocessamento, al´em da preocupa¸c˜ao em garantir a execu¸c˜ao das tarefas respeitando seu deadline, sejam
estas peri´odicas ou aperi´odicas, as pol´ıticas de escalonamento visam contemplar
solu¸c˜oes para outros problemas.
Sejam tais pol´ıticas preemptivas ou n˜ao, est´aticas ou dinˆamicas, no cen´ario em
que h´a a utiliza¸c˜ao de mais de um processador, o fato de existir uma mem´oria
compartilhada pode ter um impacto significativo sobre a execu¸c˜ao de outra
tarefa (surge uma regi˜ao cr´ıtica). Al´em disto, o custo computacional com a
troca de threads entre processadores (considerando tamb´em os barramentos) e
as poss´ıveis preemp¸c˜oes geradas por estas a¸c˜oes, tornam-se mais um fator de
diferencia¸c˜ao de algoritmos escalonadores para sistemas de tempo real multiprocessados.
Robert I. Davis (2011) destacam caracter´ısticas a serem consideradas acerca dos
sistemas multiprocessados:
• Heterogˆeneos: Os processadores s˜ao diferentes, fazendo com que a taxa de
execu¸c˜ao de uma tarefa dependa tanto do processador quanto da tarefa.
O impacto neste caso, ´e que nem todas as tarefas podem ser capazes de
executar em todos os processadores;
• Homogˆeneos: Os processadores s˜ao idˆenticos, garantindo a mesma taxa
de execu¸c˜ao das tarefas em todos os processadores;
• Uniformes: A taxa de execu¸c˜ao de uma tarefa depende apenas da velocidade do processador.
5
Diversos algoritmos de escalonamento globais foram propostos visando reduzir
custos computacionais gerais, limitando assim, a quantidade de preemp¸c˜oes.
Neste experimento foi utilizada pol´ıtica G-EDF com o intuito de analisar e
comparar o n´umero de preemp¸c˜oes e migra¸c˜oes em fun¸c˜ao do n´umero de tarefas
e a quantidade de processadores para o cen´ario exposto na se¸c˜ao subsequente.
4 Experimento e Simula¸c˜ao
Para a realiza¸c˜ao do experimento foi utilizado o simulador SimSO (2014), no
qual ´e poss´ıvel programar um agendador e analisar seu comportamento em diferentes cen´arios, variando em tarefas, processador e parˆametros poss´ıveis de
serem estabelecidos. Este trabalho n˜ao aborda os aspectos de utiliza¸c˜ao do simulador, mas ´e feita uma breve an´alise do algoritmo utilizado para o agendador
estudado nesse trabalho, o Global EDF.
4.1 An´alise de algoritmo do Global EDF
No c´odigo demonstrado na figura 1 foi utilizado a pol´ıtica de escalonamento
Global EDF. Nessa pol´ıtica o uso de m´ultiplos processadores ´e contemplado.
Na execu¸c˜ao do c´odigo escrito em Python na figura supracitada existem quatro
fun¸c˜oes para o funcionamento do agendador. Na fun¸c˜ao “init” o agendador
´e inicializado com a sua lista de tarefas zerada. Nas fun¸c˜oes ” on activate” e
“on terminated” o agendador notifica o processador um novo evento, no primeiro
caso de in´ıcio e no segundo de t´ermino de sua execu¸c˜ao. Na fun¸c˜ao “schedule”
o agendador faz o processo interno para escalonamento das tarefas.
No c´odigo de escalonamento Global EDF utilizado, conforme demonstrado em
c´odigo, o algoritmo segue a l´ogica de buscar por processadores livres e ent˜ao
atribuir uma tarefa baseada naquela que tiver o menor deadline absoluto. Caso
n˜ao existam processadores dispon´ıveis o agendador ent˜ao localiza, dentre os
processadores em utiliza¸c˜ao, aquele que cont´em uma prioridade inferior a tarefa
que precisa ser executada para realizar a preemp¸c˜ao dela em detrimento da
atividade de maior prioridade.
6
Figura 1: Global Earliest Deadline First scheduling utilizado na simula¸c˜ao.Maxime Cheramy and Deplanche (2014)
7
4.2 Experimento Realizado
Nessa experimenta¸c˜ao ser´a suposto um sistema de fechamento de v´alvulas para
uma hidrel´etrica. Partindo do suposto que o sistema da hidrel´etrica analisado
possui seis v´alvulas de fechamento e abertura para passagem de ´agua que s˜ao
distintas, cada v´alvula possui como possibilidade de tarefa a sua abertura e
o seu fechamento. Neste trabalho ser´a abordado apenas a atividade de seu
fechamento. Ser˜ao analisadas seis tarefas de fechamento onde T1 = Tarefa de
fechamento de v´alvula 1 at´e T6, onde T6 = Tarefa de fechamento de v´alvula 6.
TAREFA Ci
T
i Di
T1 5 10 10
T2 15 30 30
T3 15 25 25
T4 10 20 40
T5 5 40 45
T6 20 40 50
Tabela 3: Tabela de tarefas do experimento e seus valores.
Na tabela 3 ´e poss´ıvel visualizar as tarefas, assim como seu custo associado em
WCET e seu per´ıodo de deadline.
Na primeira experimenta¸c˜ao foi realizada a execu¸c˜ao do experimento com 2
processadores, o gr´afico Gantt gerado pode ser visualizado na figura 2.
Figura 2: Gr´afico Gantt de execu¸c˜ao com dois processadores.
No segundo estudo de simula¸c˜ao foi adicionado mais um processador, totalizando assim trˆes processadores. O resultado em gr´afico Gantt dessa simula¸c˜ao
pode ser visualizado no figura 3.
8
Figura 3: Gr´afico Gantt de execu¸c˜ao com trˆes processadores.
5 An´alise de Resultados
Conforme j´a apresentado nos gr´aficos Gantt anexo, o sistema n˜ao obteve um
escalonamento ideal sendo executado com dois processadores. Nesse cen´ario
ocorreria a perda de deadlines nas tarefas T1, T2, T3 e T4, onde seus tempos
m´aximos respectivamente apresentados foram de: 20, 35, 30 e 45, ultrapassando
seus deadlines previstos. Apesar do uso de 100% de ambos os processadores o simulador nesse cen´ario n˜ao conseguiu estipular a possibilidade de escalonamento
com a pol´ıtica Global EDF, conforme visualizado na figura 2.
Em uma situa¸c˜ao real esse sistema poderia se tornar perigoso no momento em
que 4 v´alvulas teriam relativo atraso no seu fechamento, sendo assim poderia
ocorrer o desperd´ıcio de ´agua ou at´e mesmo a inviabilidade de opera¸c˜ao da
hidrel´etrica.
Em um segundo experimento foi adicionado um novo processador na execu¸c˜ao,
deixando o sistema com trˆes processadores com o objetivo de resolver o problema
de escalonamento com cumprimento dos deadlines previstos. Nesse novo cen´ario
foi observado atrav´es do gr´afico Gantt exibido na figura 3 e dos resultados
gerados da simula¸c˜ao, que o sistema passa a ser escalonado com a utiliza¸c˜ao
m´edia de 90% dos processadores, possibilitando tamb´em a ado¸c˜ao futura de
t´ecnicas de tolerˆancia a falha.
Nesse cen´ario foi poss´ıvel observar que todos os deadlines foram cumpridos com
a ocorrˆencia de preemp¸c˜ao nas tarefas T2, T3, T4 e T6.
9
6 Conclus˜ao
A apresenta¸c˜ao desse estudo demonstra como um algoritmo de escalonamento
pode apresentar diferentes resultados e como a utiliza¸c˜ao da simula¸c˜ao pode-se
antever poss´ıveis problemas na implementa¸c˜ao de sistemas de tempo real.
No estudo apresentado podemos verificar que a utiliza¸c˜ao de dois processadores
no cen´ario observado n˜ao seria ideal, gerando inconsistˆencia e falha no sistema
com a perda do deadline espec´ıfico de algumas das tarefas. Apesar do objeto
de estudo desse trabalho ter sido o algoritmo de escalonamento Global EDF
´e v´alido tamb´em citar que outros algoritmos de escalonamento para sistemas
multiprocessados poderiam ser utilizados para atingir o objetivo do sistema
ainda que com apenas dois processadores.
Referˆencias
Baruah, S. (2011). Techniques for multiprocessor global schedulability analysis.
Luciano Bertini, J. L. (2004). Um breve survey: Escalonamento em sistemas de
tempo real com otimiza¸c˜ao do consumo de energia. WTR2004.pdf.
Maxime Cheramy, P.-E. H. and Deplanche, A.-M. (2014). Simso - a simulation
tool to evaluate real-time multiprocessor scheduling algorithms.
Robert I. Davis, A. B. (2011). A survey of hard real-time scheduling for multiprocessor systems. Journal ACM Computing Surveys.
Rˆomulo S. de Oliveira, Joni S. Fraga, J.-M. F. (2000). Sistemas de tempo real.
livro-tr.pdf.
SimSO (2014). Simso - simulation of multiprocessor scheduling with overheads.
Starke, R. A. (2012). Uma abordagem de escalonamento heterogˆeneo preemptivo
e n˜ao preemptivo para sistemas de tempo real com garantia em multiprocessadores.
VAHID SALMANI, MAHMOUD NAGHIBZADEH, A. T. M. B. and NEJAD,
S. K. (2010). Efficiency assessment of job-level dynamic scheduling algorithms
on identical multiprocessors