22
Escalonamento Linux Escalonamento Linux

Escalonamento Linux. Escalonamento de UCP Cada processo tem uma prioridade de escalonamento associada a si, com números maiores indicando prioridade mais

Embed Size (px)

Citation preview

Page 1: Escalonamento Linux. Escalonamento de UCP Cada processo tem uma prioridade de escalonamento associada a si, com números maiores indicando prioridade mais

Escalonamento LinuxEscalonamento Linux

Page 2: Escalonamento Linux. Escalonamento de UCP Cada processo tem uma prioridade de escalonamento associada a si, com números maiores indicando prioridade mais

Escalonamento de UCPEscalonamento de UCP

Cada processo tem uma prioridade de escalonamento associada a si, com números maiores indicando prioridade mais baixa.

A realimentação negativa no escalonamento de UCP torna difícil para um único processo monopolizar o tempo de UCP.

Envelhecimento do processo é empregado para prevenir que um processo sofra inanição.

Quando um processo escolhe pela liberação da UCP, ele deve ser bloqueado em um evento.

Quando o evento ocorre, o sistema operacional permite o processamento deste evento percorrendo a fila dos processos bloqueados neste evento e desbloqueando esses processos, de tal forma que se tornam processos prontos para executar.

Page 3: Escalonamento Linux. Escalonamento de UCP Cada processo tem uma prioridade de escalonamento associada a si, com números maiores indicando prioridade mais

Escalonamento LinuxEscalonamento Linux

Enquanto o escalonamento é normalmente compreendido como a execução e interrupção de processos, no Linux o escalonamento também inclui a execução de várias tarefas do núcleo.

As tarefas de execução do núcleo englobam tanto as tarefas requisitadas por um processo em execução quanto as tarefas que executam internamente em nome de um driver de dispositivo.

Como no kernel do 2.5, o novo algoritmo de escalonamento – preemptivo e baseado em prioridade

Tempo real

Valor nice

Page 4: Escalonamento Linux. Escalonamento de UCP Cada processo tem uma prioridade de escalonamento associada a si, com números maiores indicando prioridade mais

Relação entre prioridades e tamanho da fatia Relação entre prioridades e tamanho da fatia de tempode tempo

Page 5: Escalonamento Linux. Escalonamento de UCP Cada processo tem uma prioridade de escalonamento associada a si, com números maiores indicando prioridade mais

Escalonamento de processosEscalonamento de processos

O Linux usa dois tipos de algoritmos para escalonamento:

Um algoritmo de tempo compartilhado para escalonamento preemptivo equitativo entre múltiplos processos

Um algoritmo de tempo real para tarefas onde as prioridades absolutas são mais importantes do que a equidade

Uma classe de escalonamento do processo define qual algoritmo aplicar para o processo.

Para processos de tempo compartilhado, o Linux usa um algoritmo de prioridade baseado em créditos e o processo pronto com maior número de créditos é executado.

A prioridade default é 120, pode ser alterada pelo nice (-20 a +19) e variando de 100 a 140 (prioridade = 120 – valor).

O tique é de 10 ms e cada tique de relógio, o crédito é decrementado e o processo é preemptado quando o crédito chega a zero.

Page 6: Escalonamento Linux. Escalonamento de UCP Cada processo tem uma prioridade de escalonamento associada a si, com números maiores indicando prioridade mais

Escalonamento de processosEscalonamento de processos

Se nenhum processo tem crédito, o Linux faz uma operação de recrédito.

Recrédito:

Para todos os processos (inclusive os bloqueados), faça:

créditos = créditos/2 + prioridade

Leva em conta a história e prioridade do processo

Este sistema de créditos automaticamente prioriza processos interativos ou orientados a E/S.

O valor da prioridade é estático e pode ser alterado pelo comando nice ou renice.

Page 7: Escalonamento Linux. Escalonamento de UCP Cada processo tem uma prioridade de escalonamento associada a si, com números maiores indicando prioridade mais

Escalonamento de processosEscalonamento de processos

Para o kernel 2.6:

Bonus vai de 0 à 10 e representa o tempo médio de espera do processo;

Prioridade dinâmica =

max(100, min(prioridade – bonus + 5, 139)

Quantum básico =

(140 – prioridade)20 se prioridade < 120

(140 – prioridade)x5 se prioridade >= 120

Page 8: Escalonamento Linux. Escalonamento de UCP Cada processo tem uma prioridade de escalonamento associada a si, com números maiores indicando prioridade mais

Lista de tarefas indexada por prioridadeLista de tarefas indexada por prioridade

Page 9: Escalonamento Linux. Escalonamento de UCP Cada processo tem uma prioridade de escalonamento associada a si, com números maiores indicando prioridade mais

Escalonamento de Processos (Cont.)Escalonamento de Processos (Cont.)

O Linux implementa classes de escalonamento de tempo real baseadas em FIFO e round-robin e em ambos os casos, cada processo tem uma prioridade em adição a sua classe de escalonamento

O escalonador executa os processos com a prioridade mais alta, e para empate, executa o processo que está esperando a mais tempo.

Os processos FIFO continuam executando até o bloqueio ou até a terminação.

Os processos round-robin executam até serem preemptados por um outro processo round-robin ou por um processo FIFO, ao tempo do qual se movem para o fim da fila se sua fatia de tempo tiver acabado.

Page 10: Escalonamento Linux. Escalonamento de UCP Cada processo tem uma prioridade de escalonamento associada a si, com números maiores indicando prioridade mais

Escalonamento no LinuxEscalonamento no Linux

Classes de escalonamento

SCHED_FIFO: Escalonamento de threads de tempo-real por ordem de chegada - First-in-first-out

SCHED_RR: Escalonamento de threads de tempo-real de forma circular - Round-robin

SCHED_OTHER: Escalonamento de threads que não são de tempo real

Dentro de cada classe prioridades múltiplas podem ser usadas

Page 11: Escalonamento Linux. Escalonamento de UCP Cada processo tem uma prioridade de escalonamento associada a si, com números maiores indicando prioridade mais

Exemplo do escalonamento de tempo-Exemplo do escalonamento de tempo-real do Linuxreal do Linux

Page 12: Escalonamento Linux. Escalonamento de UCP Cada processo tem uma prioridade de escalonamento associada a si, com números maiores indicando prioridade mais

Sincronização de KernelSincronização de Kernel

Uma requisição para execução em modo kernel pode ocorrer de duas formas:

Um programa em execução pode requisitar um serviço do sistema operacional, tanto explicitamente quanto na forma de uma chamada ao sistema, ou implicitamente, como na ocorrência de uma falta de página.

Um dispositivo pode requisitar uma interrupção de hardware que causa uma execução de um tratador de interrupção do kernel para lidar com a interrupção

A sincronização do kernel requer um esquema que permita que as seções críticas do kernel possam executar sem serem interrompidas por outra seção crítica.

Page 13: Escalonamento Linux. Escalonamento de UCP Cada processo tem uma prioridade de escalonamento associada a si, com números maiores indicando prioridade mais

Sincronização de Kernel (Cont.)Sincronização de Kernel (Cont.)

O Linux utiliza duas técnicas para proteger suas seções críticas:

1. Código do kernel não é preemptável (até 2.4)– quando uma interrupção de tempo é recebida enquando um processo está executando uma rotina de serviço do kernel, o flat do kernel need_resched é setado de tal forma que o escalonador irá executar apenas quando do término da chamada ao sistema e na iminência do retorno para o modo usuário

2. A segunda técnica aplica-se para seções críticas que ocorrem dentro de uma rotina de serviço de interrupção

– através do uso do hardware de controle de interrupção, pode-se desabilitar interrupções durante uma seção crítica, de tal forma que o kernel garante que o tratador de interrupção corrente não será preemptador por outro tratador de interrupção durante sua execução.

Page 14: Escalonamento Linux. Escalonamento de UCP Cada processo tem uma prioridade de escalonamento associada a si, com números maiores indicando prioridade mais

Sincronização de Kernel (Cont.)Sincronização de Kernel (Cont.)

Para evitar penalidades no desempenho, o kernel do Linux usa uma arquitetura de sincronização que permite que seções críticas de longa duração possam executar sem ter que impedir o tratamento de interrupções que estão desabilitadas durante a seção crítica

As rotinas de serviço de interrupção são separadas em top half (metade superior) e bottom half (metade inferior). A metade superior é a rotina de serviço de interrupção normal

e executa com interrupções recursivas desabilitadas. A metade inferior executa com todas as interrupções

habilitadas através de um escalonador que assegura que as metades inferiores não se interrompem mutuamente.

A arquitetura é completada por um mecanismo que desabilita algumas metades inferiores selecionadas quando da execução de código de kernel em determinadas situações.

Page 15: Escalonamento Linux. Escalonamento de UCP Cada processo tem uma prioridade de escalonamento associada a si, com números maiores indicando prioridade mais

Níveis de proteção de interrupçãoNíveis de proteção de interrupção

Cada nível pode ser interrompido por código executando em um nível mais alto, mas nunca por um código executando no mesmo nível ou em nível mais baixo.

Processos de usuário podem ser sempre preemptados por outro processo quando uma interrupção de escalonamento de tempo compartilhado ocorrer.

Page 16: Escalonamento Linux. Escalonamento de UCP Cada processo tem uma prioridade de escalonamento associada a si, com números maiores indicando prioridade mais

Escalonamento UNIX tradicional (SVR2)Escalonamento UNIX tradicional (SVR2)

A realimentação multinível usando round robin (circularidade) dentro de cada fila de prioridade;

Se um processo em execução não bloquear ou completar dentro de 1s, é preemptado.

As prioridades são recomputadas uma vez por segundo. O contador é incrementado a cada tique de relógio para o

processo que está executando. Recômputo:

contador = contador/2; prioridade = prioridade_base + nice + contador/2;

Um valor numericamente baixo implica em uma prioridade de escalonamento maior.

O valor de nice é reajustado entre -20 e +20 (default 0).

Page 17: Escalonamento Linux. Escalonamento de UCP Cada processo tem uma prioridade de escalonamento associada a si, com números maiores indicando prioridade mais

Exemplo do escalonamento tradicional do UnixExemplo do escalonamento tradicional do Unix

Page 18: Escalonamento Linux. Escalonamento de UCP Cada processo tem uma prioridade de escalonamento associada a si, com números maiores indicando prioridade mais

BandasBandas

A prioridade de base divide todos os processos em bandas fixas de níveis de prioridade.

Ordem decrescente de prioridade

Swapper ou permutador

Controle de dispositivo de E/S de bloco

Tratamento de arquivos

Controle de dispositivo de E/S de caractere

Processos de usuário

Page 19: Escalonamento Linux. Escalonamento de UCP Cada processo tem uma prioridade de escalonamento associada a si, com números maiores indicando prioridade mais

Escalonador do UNIXEscalonador do UNIX

Baseado em estrutura de filas multinível

Page 20: Escalonamento Linux. Escalonamento de UCP Cada processo tem uma prioridade de escalonamento associada a si, com números maiores indicando prioridade mais

Escalonamento UNIX SVR4Escalonamento UNIX SVR4

Escalonador preemptável com prioridade estática

Introdução de um conjunto de 160 níveis de prioridade divididos em 3 classes de prioridade

Inserção de pontos de preempção

Maior preferência para processos em tempo real

Segunda preferência para processos em modo kernel

Terceira preferência para processos em modo usuário

Page 21: Escalonamento Linux. Escalonamento de UCP Cada processo tem uma prioridade de escalonamento associada a si, com números maiores indicando prioridade mais

Classes de prioridade SVR4Classes de prioridade SVR4

Page 22: Escalonamento Linux. Escalonamento de UCP Cada processo tem uma prioridade de escalonamento associada a si, com números maiores indicando prioridade mais

Classes de prioridade do SVR4Classes de prioridade do SVR4

Tempo real (159 – 100) Tem garantia de ser selecionado para executar antes de

qualquer processo kernel ou de tempo compartilhado. Pode preemptar processos em kernel ou usuário.

Kernel (99 – 60) Tem garantia de ser selecionado para executar antes de

qualquer processo de tempo compartilhado. Tempo compartilhado (59-0)

Prioridade mais baixa