Algoritmos de Escalonamento Sistemas de Tempo Real Centro de Informtica - UFPE Equipe Ademir Jr. Andr Guedes Andr Souza Bruno Barros Digo Santiago Francisco Simes Rebeka Gomes Renato Marcelino Rodrigo Melo Valmir Sena Roteiro Algoritmos de escalonamento Rate Monotonic Earliest Deadline First Deadline Monotonic Introduo Escalonamento: Procedimento de ordenar a execuo de tarefas na fila de pronto Aspecto importante em sistemas com restries temporais Detalhes de implementao tratados na fase de projeto Tarefa Abstrao bsica de um problema de escalonamento: Concorrncia por recursos computacionais Correctness e Timeliness Precedncia e Excluso Hard / Soft Peridicas / Aperidicas Espordicas Tarefa Tempo de Incio Tempo de Trmino Tempo de Chegada Tempo de Liberao Tempo de Computao Perodo Deadline Release Jitter Tarefa Tempo de Incio Tempo de Trmino Tempo de Chegada Tempo de Liberao Tempo de Computao Perodo Deadline Intervalo Mnimo Escalonamento Procedimento de ordenar a execuo de tarefas na fila de pronto Escalonador Escala de execuo Problema NP-Completo Algoritmo timo Caractersticas: Preemptivo / No-Preemptivo Esttico / Dinmico Offline / Online Escalonamento Abordagens Escalonamento Teste de Escalonabilidade Escalonamento Utilizao de uma tarefa Rate Monotonic Scheduling Motivao STR desenvolvidos com tcnicas empricas podem ser altamente imprevisveis STR atuais so baseados em modificaes dos sistemas time sharing: Multitarefas Escalonamento baseado em prioridade Suporte de um clock de tempo real Motivao Algoritmos de escalonamento no consideram: Tempo de computao Restrio de tempo Recursos compartilhados Relao de precedncia entre as tarefas Definies Algumas definies importantes com respeito a Tarefas Peridicas C: WCET de uma tarefa T: Periodo de uma tarefa U: Processor Utilization Factor Ulub: Least Upper Bound Processor Utilization Factor Rate Monotonic Scheduling (RMS) Algoritmo de Escalonamento Preemptivo e com prioridades Prioridades fixas e inversamente proporcionaisao perodo Tem garantias determinsticas em relao ao tempo de resposta Qualquer tarefa pode ser interrompida por outra tarefa com maior prioridade que esteja no estado PRONTO Rate Monotonic Scheduling(RMS) Premissas As tarefas so peridicas e independentes O deadline de cada tarefa coincide com o seu perodo e so conhecidos e estticos O tempo de computao (WCET) de cada tarefa conhecido e constante O tempo de chaveamento dentre tarefas no causa impacto no modelo Rate Monotonic Scheduling(RMS) Escalonabilidade por Liu e Layland Para um conjunto de tarefas, se U Interferncia sofrida pela tarefa i pela outras tarefas. Se para toda tarefa itemos Ri