OPERACIONAIS Escalonadores

Sumário

•Conceitos básicos •Escalonador

•Despachante

•Algoritmos de escalonamento

•Escalonamento de threads

•Escalonamento em sistemas multiprocessados

Conceitos básicos

•Sistemas multiprogramados melhoram a eficiência no uso da CPU

•Em um sistema monoprogramado a CPU tende a ficar muito tempo ociosa

•Processos tendem a alternar períodos de uso de CPU e uso de E/S até o fim da sua “vida”

•A ideia é não deixar a CPU ociosa!

Alternância entre CPU / Entrada e saída

Escalonador

•Escalonador é responsável por selecionar processos em uma fila e atribuí-lo a uma CPU

•A decisão é tomada quando processos:

1.Deixam de executar e vão para fila de espera

2.Deixam de executar e vão para o estado pronto

3.Deixam de esperar e vão para o estado pronto

4.Terminam

Escalonador

•No primeiro e último casos não há muito o que fazer

•Sistema sem preempção: cooperativo

•Usado até o Windows 3.x

•Não requer auxílio de hardware

•Os dois casos intermediários permitem alguma ação

•Sistema com preempção •Windows 95 e posteriores, MacOS, Linux

•Em todas as situações, entra em ação o escalonador!

Escalonador

•O escalonador é quem decide qual processo será executado

•Troca de processos tem um custo

•Processos que saem precisam ter integridade de dados e segurança

•Kernel do sistema precisa ser informado que o processo saiu da execução

•Tempo de troca de processos não pode ser ignorado

•Despachante é quem coloca o processo escolhido pelo escalonador para executar

Despachante

•A etapa de despacho consiste em:

•Troca efetiva do contexto

•Alternância entre modo kernel para modo de usuário

•Desvio do contador de programa para o ponto em que o programa recém escalonado deve ser retomado

•Latência do despacho é o tempo levado para executar estas tarefas

Critérios para o escalonador

•O escalonador pode decidir qual processo será executado com base nos critérios a seguir:

•Taxa de utilização da CPU •Throughput de processos concluídos

•Tempo de turnaround

•Tempo de espera

•Tempo de resposta

•Algoritmos de escalonamento visam otimizar um ou mais desses critérios

Algoritmo FCFS

•Vem de “first come, first served”

•Processos são executados na ordem em que chegam

•Fila FIFO simples para os BCP’s

•Processos são executados enquanto não terminarem

•Tempo de espera por processo, na média, é alto

•Tem resultados extremamente ruins quando ocorrem operações de E/S

Algoritmo FCFS

Processo Tempo de execução P 24 P 3 P 3

•Suponha que os processos cheguem na ordem: P , P , P

P P P 24 27 30 0

Algoritmo FCFS

•Agora suponha que os processos cheguem na ordem: P2 , P3 , P1

•Tempo de espera para P1 = 6; P2 = 0; P3 = 3 •Tempo médio de espera: (6 + 0 + 3)/3 = 3

•Efeito comboio: processos menores precisam esperar processo maior terminar

P P P 6 3 30 0

Algoritmo SJF

•Vem de “shortest job first”

•Processos que são executados primeiro são os que levam menos tempo para executar

•Algoritmo ótimo quando o critério é tempo de espera

•O problema é saber por quanto tempo um processo será executado

•Estimativas são usadas na prática

•Variante com preempção usa como critério o menor tempo para terminar

Algoritmo SJF Processo TimeTempo de execução

P P P 3 16 0 9

Algoritmo SJF

•Com preempção, a coisa melhora Processo Tempo de chegada Tempo de execução P 0 8 P1 4 P 2 9 P 3 5

P P P 1 17 0 10

Algoritmo baseado em prioridades

•Algoritmo se baseia em prioridade de execução de processos

•Processos de mais alta prioridade são executados primeiro

•Prioridade é definida por um número

•Alguns sistemas definem número menores para maior prioridade, outros fazem o contrário

•Aqui, maior prioridade tem menor número

•Processos de prioridade baixa podem sofrer de inanição

•Envelhecimento: aumenta-se a prioridade do processo de acordo com o tempo de espera

Algoritmo baseado em prioridades

ProcessoATempo de execuçãoT Prioridade P 10 3 P1 1 P 2 4 P 1 5 P5 2

Tempo de espera médio: 8,2

P P P 1 18 0 16 P 19 6 P

Algoritmo Round-Robin

•Processos são executados na ordem em que chegam, mas por um tempo máximo

•Tempo máximo de execução de processos é chamado de quantum

•Quantum geralmente tem entre 10 e 100 milissegundos

•Quando um processo não consegue terminar num prazo definido, vai para o fim da fila de BCP’s

Algoritmo Round-Robin

•Se existem processos na fila, cada processo recebe 1

intervalos de tempo

•Assim, processos esperam no máximo −1∙ unidades de tempo para executar

•Normalmente a interrupção de tempo é quem define o tamanho do quantum

•Quantum muito grande: desempenho aproxima-se de FCSF

•Quantum muito pequeno: overhead com a troca de contexto começa a ficar importante

Algoritmo Round-Robin com Q = 4 Processo Tempo de execução

Tempo de espera médio (tempo de execução total – tempo de execução):

Algoritmo com múltiplas filas

•Processos entram em filas de acordo com a sua prioridade

•Cada fila tem seu próprio algoritmo de escalonamento

•Escolhem, dentro daquela fila, qual será o próximo processo a ser executado

•Escalonador escolhe de qual fila irá executar o processo

•Quando é permitido a um processo trocar de fila de acordo com algum critério, o algoritmo é chamado de múltiplas filas com retroalimentação

Algoritmo com múltiplas filas Sem retroalimentação

•Processos entram em filas de prioridades diferentes e ficam ali até saírem

Com retroalimentação

•Processos entram em uma fila, mas podem ir para outras filas com prioridades diferentes

Escalonamento de threads

•Em sistemas que suportam threads, o escalonador define qual thread de sistema será executada

•Sistemas que fazem mapeamentos muitos-paraum ou muitos-para-muitos decidem qual thread de usuário será mapeada em uma thread de sistema para ser executada

•A disputa entre threads de usuário ocorre dentro do escopo do processo (process content scope) e as prioridades são definidas pelo programador

•A disputa entre threads de sistema ocorrem entre todo o sistema (system content scope)

Escalonamento de threads Modelo muitos-para um Modelo muitos-para-muitos

Escalonamento com multiprocessadores

•Objetivo extra do escalonador quando existem muitos processadores: manter o balanceamento de carga

•Existem vários modelos de sistemas multiprocessados, entre eles:

•Sistemas homogêneos: processadores são idênticos em relação à sua funcionalidade

•Mas podem haver dispositivos conectados a apenas alguns processadores

•Sistemas heterogêneos: processadores têm funcionalidades diferentes

•Podem haver processos que só podem ser executados em algum(ns) deles.

Escalonamento com multiprocessadores

•Mesmo em sistemas homogêneos, podemos ter modelos de processamento diferentes

•Modelo assimétrico: atividades relacionadas ao sistema são realizadas pelo processador mestre, processos de usuário são vinculados aos demais processadores (escravos)

•Modelo simétrico: qualquer processo pode ser executado por qualquer processador

•Cada processador pode ter sua própria fila de processos e realizar seu escalonamento

•Existe uma única fila de processos e o escalonador atribui processos a processadores

•Suportado por Linux, MacOS, Windows 2000+

Escalonamento com multiprocessadores

•Apesar dos sistemas atuais trabalharem com modelo de processamento simétrico, a troca de processos entre processadores nem sempre é bem vinda

•A troca de processadores envolve cópia de dados e invalidação da cache

•Solução: processos terem afinidade com processadores Afinidade fraca: processos tendem a serem executados pelo mesmo processador Afinidade forte: processos são mantidos no mesmo processador

Escalonamento em sistemas multicore

•Tendência atual é integrar dois ou mais processadores em um único chip físico •Intel Série Core, AMD Athlon X2/Phenom, UltraSparc T1

•Melhoria no desempenho e menor custo

•Cada processador integrado tem sua própria memória cache

•Comunicação com a memória principal e sistema de interrupção é compartilhado

•Processadores atuais suportam processamento simétrico de threads

•Na Intel, isso é conhecido como hyperthreading

Processamento simétrico de threads

•No processamento simétrico de threads, cada processador físico é mostrado para o S.O. como dois ou mais processadores lógicos

•Cada processador lógico tem seu próprio estado – conjunto de registradores

•Cada conjunto de processadores lógico compartilha o processador físicos

•Interrupções são atribuídas a processadores lógicos

Processamento simétrico de threads

•Processadores normalmente buscam dados e instruções na memória cache

•Cache miss: quando dados ou instruções não estão na cache, devem ser buscados em memória principal e a cache atualizada

•Quando ocorrem cache misses o núcleo responsável por executar aquela thread tem que parar tudo o que está fazendo: memory stall

•Situação comum quando dados ou instruções da memória cache são esgotados

•Execução de threads se transforma em alternância de ciclos de execução e memory stalls

Processamento simétrico de threads

•Processadores com suporte a processamento simétrico de threads aproveitam memory stalls de uma thread para executar outra

•Uma thread é executada enquanto o memory stall da outra é resolvido

•Ganho de desempenho

•Escalonamento de dois níveis •Entre threads de sistema

•Entre threads do processador

Exercício

Suponha que os processos abaixo tenham chegado na ordem mostrada, no tempo 0, com as prioridades mostradas.

Processo Tempo de execução Prioridade P1 10 3 P2 1 1 P3 2 3 P4 1 4

P5 5 2 Mostre os diagramas de Gantt para FCFS, SJF, prioridade e R (Q=1). Mostre o tempo de turnaround para cada um dos processos em cada algoritmo. Mostre o tempo de espera para cada um dos processos em cada algoritmo. Qual dos algoritmos resulta na menor média de tempo de espera?

Exercícios

Diagramas de Gantt Referências

•Tanenbaum, Andrew S. Sistemas operacionais modernos. 2ed. Pearson.

•Silberschatz, Abraham. Fundamentos de sistemas operacionais. 8ed. LTC.

Comentários