Escalonamento - ?· Algoritmo de Escalonamento Round Robin com filas mútiplas. Tadeu Ferreira IFRN…

Embed Size (px)

Text of Escalonamento - ?· Algoritmo de Escalonamento Round Robin com filas mútiplas. Tadeu Ferreira...

  • Tadeu Ferreira IFRN 2016 1/25

    Escalonamento

    Escalonamento em Sistemas Operacionais Embarcados de Tempo Real

  • Tadeu Ferreira IFRN 2016 2/25

    Escalonamento

    Tipos de Escalonamento Preempitivo No-Preempitivo

  • Tadeu Ferreira IFRN 2016 3/25

    Escalonamento em RTOS

    Duas preocupaes especficas: Manter os prazos de tempo de resposta Previsibilidade - Garantir que respostas sejam

    entregues de maneira ordenada e correta em tempo

  • Tadeu Ferreira IFRN 2016 4/25

    Escalonamento em RTOS

    Rate Monotonic Scheduling (RMS) Preempitivo Prioridades fixas Prioridades dependentes de tempo da frequncia

    que o processo se apresenta Aplicvel apenas a processos peridicos

  • Tadeu Ferreira IFRN 2016 5/25

    Escalonamento em RTOS

    Earliest Deadline First (EDF) Preemptivo Considera o momento que a resposta deve ser

    entregue Quanto mais prximo do deadline mais prioritrio o

    processo Aplicvel a processos peridicos ou aperidicos Algoritmo mais complexo

  • Tadeu Ferreira IFRN 2016 6/25

    Alguns RTOS para embarcados

    QNX Linux

    uCLinux eCos SnapGear

    NetBSD MicroC/OSII

  • Tadeu Ferreira IFRN 2016 7/25

    QNX

    Direcionado a plataformas ARM e X86 O algoritmo de escalonamento definido por

    thread, no globalmente Mltiplos Algoritmos de Escalonamento

    FIFO Round Robin Sporadic Adaptative Partitioning Scheduler

  • Tadeu Ferreira IFRN 2016 8/25

    FIFO

    First in First Out Comum em sistemas batch Executa o processo at o fim antes de passar o

    processador a outro processo Um processo fica de posse da CPU at que:

    Termine sua execuo e libere expontaneamente Fique Bloqueado Um processo de maior prioridade esteja pronto

  • Tadeu Ferreira IFRN 2016 9/25

    Round Robin

    Um processo fica de posse do processador at que: Termine sua execuo e libere expontaneamente Fique Bloqueado Um processo de maior prioridade esteja pronto Expire o seu tempo de execuo (quantum)

  • Tadeu Ferreira IFRN 2016 10/25

    Sporadic

    Existem 2 nveis de prioridade Normal e Baixo

    Toda thread iniciada com um saldo A medida que a thread executa seu saldo

    diminuido Quando a thread zera o saldo cai de prioridade O saldo restaurado depois de um tempo T

    configurvel

  • Tadeu Ferreira IFRN 2016 11/25

    Sporadic

    Um processo executa Gasta parte de seu

    saldo e bloqueado Volta a executar com

    saldo completo

  • Tadeu Ferreira IFRN 2016 12/25

    Prioridades no Sporadic

  • Tadeu Ferreira IFRN 2016 13/25

    Adaptative Partitioning Scheduler

    Processos rodam dentro de parties A cada partio garantido uma porcentagem

    da CPU Prioridades so relacionadas aos processos de

    cada partio apenas Processos Crticos podem sobrepor as

    prioridades

  • Tadeu Ferreira IFRN 2016 14/25

    Adaptative Partitioning Scheduler

    Execuo de tempo real enquanto estiver dentro do saldo da partio

    Parties com mesma prioridade se sobrepe O tempo livre de CPU passado a parties

    mesmo que estas no sejam a prioridade no momento

  • Tadeu Ferreira IFRN 2016 15/25

    eCos

    Criado em 1997 para ser um RTOS open-source altamente configurvel royalty-free

    Escalonamento de processos Multilevel Queue Bitmap Lottery (experimental)

  • Tadeu Ferreira IFRN 2016 16/25

    eCos

    Escalonador pode ser interrompido Pode-se tambm desativar o escalonador Chamada ao kernel para desativar escalonador

    til ao manipular interrupes uma thread de modo usurio pode desativar o

    escalonador usando a chamada cyg_scheduler_lock()

  • Tadeu Ferreira IFRN 2016 17/25

    eCos

    Multiple Queue 32 filas de prioridade O nico algoritmo do eCos que suporta Symmetric

    Multi-Processing (Mltiplos Processadores) Round Robin de mltiplas filas Prioridade esttica Nmero de threads limitados apenas pela

    capacidade de memria

  • Tadeu Ferreira IFRN 2016 18/25

    eCos

    Bitmap um algoritmo preemptivo Funcionamento parecido com o Mltiplas Filas Porm, cada Fila pode ter apenas um processo No existe o conceito de timeSlice bem mais simples e mais leve Nmero mximo de processos limitado a 32

  • Tadeu Ferreira IFRN 2016 19/25

    eCos

    Lottery Cada thread mantm um nmero de loteria A cada novo quantum um nmero aleatrio

    gerado A thread sorteada colocada para execuo Existem tickets de compensao para threads que

    bloqueiem antes do quantum Obs.: um algoritmo usado apenas em testes do Kernel

    no deve ser usado em produo

  • Tadeu Ferreira IFRN 2016 20/25

    NetBSD

    Baseado no Unix de Berkeley Projeto irmo do FreeBSD um SO pequeno cujo objetivo principal ser

    altamente portvel e estvel Slogan Of course it runs NetBSD Algoritmo de Escalonamento

    Round Robin com filas mtiplas

  • Tadeu Ferreira IFRN 2016 21/25

    NetBSD

    Round Robin de mtiplas filas 32 filas de prioridade threads so colocados nas filas cada um com sua

    prioridade da fila cada fila servida por um Round Robin comum a medida que uma thread acumula tempo de CPU

    sua prioridade alterada

  • Tadeu Ferreira IFRN 2016 22/25

    MicroC/OSII

    Mantido pela Micrium Inc. Criado para ser um Kernel escrito em C com o

    mnimo de asssembly Escalonamento baseado em prioridades No poder haver dois processos com a

    mesma prioridade O scheduler pode ser desativado

  • Tadeu Ferreira IFRN 2016 23/25

    uCLinux

    Algoritmo de Scheduling semelhante ao do Linux

    Seleo de processos Preemptivo Round Robin Preemptivo

    Processos em modo de Kernel so No-Preemptivos Pode comprometer tempo de resposta para tempo

    real

  • Tadeu Ferreira IFRN 2016 24/25

    Referncias Tanenbaum, S. Andrew. Modern Operating Systems, 2 ed Cesati, M., Boveti, D. Undesrtanding Linux Kernel Danko, A. Adaptative Scheduler QNX QNX Software, QNX Migration Guide Manual NetBSD acessado em:

    http://www.netbsd.org/docs/internals/en/index.html 21 de maro de 2008

    Wang, C. L., Yao B., Yang Y., Zhu Z., A Survey of Embedded Operating System

    Massa, Antonyh J.,Embedded Software Development with eCos

    http://www.netbsd.org/docs/internals/en/index.html

  • Tadeu Ferreira IFRN 2016 25/25

    Referncias Hellstrm, D., Manual: SnapGear Linux for LEON eCos Reference Manual acessado em:

    http://ecos.sourceware.org/docs-1.3.1/ref/ecos-ref.2.html Labrosse, Jean J. MicroC/OSII The Real-Time Kernel, CMP Books

    http://ecos.sourceware.org/docs-1.3.1/ref/ecos-ref.2.html

    Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25