Escalonamento de processos Escalonamento de processos Prof. Luiz Henrique BiazottoqFAJ

Escalonamento de processos Escalonamento de processos

O escalonamento de processos uma O escalonamento de processos uma atividade organizacional feita pelo escalonador possibilitando executar os processos mais possibilitando executar os processos mais viveis e concorrentes, priorizando determinados tipos de processos como os de determinados tipos de processos, como os de I/O Bound e os computacionalmente intensivosintensivos.

Tipos BsicosTipos Bsicos

Escalonador de curto prazo Escalonador de curto prazo Escalonador de mdio prazo Escalonador de longo prazo Escalonador de longo prazo

Escalonador de curto prazoEscalonador de curto prazo

Seleciona entre os processos em estado de Seleciona entre os processos em estado de pronto que esto na memria, para serem executados pelo processador O escalonador de executados pelo processador. O escalonador de curto prazo faz decises de escalonamento muito mais frequentemente que os de mdio e longo mais frequentemente que os de mdio e longo prazo

Escalonador de mdio prazoEscalonador de mdio prazo

Seleciona entre os processos que esto na Seleciona entre os processos que esto na memria virtual, reduz o grau de multiprogramao Ele temporariamente multiprogramao. Ele temporariamente remove o processo da memria principal e o coloca na memria secundria (swap) fazendo as coloca na memria secundria (swap) fazendo as operaes de swapping in e swapping out.

Escalonador de longo prazoEscalonador de longo prazo

Seleciona entre os processos novos os que so Seleciona entre os processos novos, os que so limitados por entrada/sada e os que so limitados por CPU dando prioridade aqueles limitados por CPU, dando prioridade aqueles limitados por I/O, j que utilizam menos tempo o processador Este escalonador o responsvel o processador. Este escalonador o responsvel pelo grau de multiprocessamento, ou seja a quantidade de processos que o sistema ir quantidade de processos que o sistema ir trabalhar.

Definio Definio Para que a CPU no fique muito tempo sem executar q q p

tarefa alguma, os sistemas operacionais utilizam tcnicas para escalonar os processos que esto em execuo ao mesmo tempo na maquina. p q

O escalonamento de processos uma tarefa complicada, pois nenhum algoritmo totalmente eficiente e a prova de falhas, principalmente em se tratando de sistemas de falhas, principalmente em se tratando de sistemas interativos, como o Windows, pois a interao com o usurio fundamental para este sistema onde quem o utiliza procura respostas rpidas e a todo o momento utiliza procura respostas rpidas e a todo o momento processos so interrompidos pelo usurio.

Algoritmos escalonadores Algoritmos escalonadores Existem os algoritmos preemptivos e os no Existem os algoritmos preemptivos e os no

preemptivos. Os preemptivos so algoritmos que permitem que um processo seja interrompido durante sua execuo, quer seja por fora de uma interrupo de entrada/sada, quer seja em decorrncia da poltica de escalonamento adotada e aplicada por parte do escalonamento adotada e aplicada por parte do escalonador de processos ou simplesmente por fora do trmino da execuo do processo. trmino da execuo do processo.

Algoritmos escalonadoresAlgoritmos escalonadores consiste em salvar o contedo dos registradores e a consiste em salvar o contedo dos registradores e a

memoria utilizada pelo processo e conceder outro processo o privilgio de executar na CPU, restaurando assim o contexto deste ultimo processo. Cabe ressaltar que nos algoritmos no preemptivos, por serem utilizados exclusivamente em sistemas utilizados exclusivamente em sistemas monoprocessados, esse fato no ocorre, sendo cada programa executado at o fim. programa executado at o fim.

Exemplos de Algoritmos Exemplos de Algoritmos

FIFO : FIFO : SJF : SRT: SRT: Escalonamento garantido:

RR RR : Mltiplas Filas:

FIFO FIFO

Em engenharia da computao FIFO Em engenharia da computao, FIFO(acrnimo para First In, First Out, que em portugus significa primeiro a entrar primeiro portugus significa primeiro a entrar, primeiro a sair) refere-se a estruturas de dados do tipo fila Tem uma estrutura diferente da estrutura de fila. Tem uma estrutura diferente da estrutura de uma LIFO (que significa Last In, First Out, as pilhas)as pilhas).

FIFOFIFO As listas so amplamente utilizadas em As listas so amplamente utilizadas em

programao para implementar filas de espera. Em uma fila de tipo FIFO os elementos p pvo sendo colocados na fila e retirados (ou processados) por ordem de chegada. A idia f d l d fil d i i fundamental da fila que s podemos inserir um novo elemento no final da fila e s podemos retirar o elemento do incioretirar o elemento do incio.

FIFOFIFO Como exemplo de aplicao para filas, pode-se citar a p p p , p

fila de processos de um sistema operacional. Nela, estabelecido um tempo t a ser usado por cada um dos processos Se durante a execuo de um processo o dos processos. Se durante a execuo de um processo o tempo passa de 0 a t, este posto na fila e o processo seguinte executado. Se o processo seguinte no terminar de ser executado no tempo t, ele posto na fila e o processo subsequente executado, e assim por diante at todos os processo serem executadosat todos os processo serem executados.

SJF SJF O SJF (Shortest Job First ou Processo mais curto (

primeiro) um algoritmo de escalonamento que executa, dentre processos igualmente importantes, o mais curto primeiromais curto primeiro.

O escalonador SJF funciona a partir de um conceito bem simples: os processos menores tero prioridade, ou seja, p p p , j ,sero executados primeiro. Isso tem como resultado um tempo mdio mnimo de espera para cada conjunto de processos a serem executadosprocessos a serem executados.

SJFSJF

O clculo de cada tempo mdio feito a partir da O clculo de cada tempo mdio feito a partir da prxima alocao de CPU, ou seja, o processo que utilizar a CPU por menos tempo ser que utilizar a CPU por menos tempo ser executado primeiro. Existem dois esquemas j conhecidos desse tipo de escalonamento:conhecidos desse tipo de escalonamento:

SJFSJF No-Preemptivo No Preemptivo

Uma vez a CPU atribuda a um processo, este no pode ser interrompido at completar a execuo do processo.

i Preemptivo Se um novo processo chega ao estado "pronto" com um tempo de

alocao menor que o tempo restante do processo em execuo, alocao menor que o tempo restante do processo em execuo, ento h preempo (interrupo). Este esquema conhecido por Shortest-Remaining-Time-First (SRTF).

SRTSRT

SRT (sigla de Shortest Remaining Time ou SRT (sigla de Shortest Remaining Time, ou "tempo mais curto remanescente") um algoritmo de escalonamento de processos que algoritmo de escalonamento de processos que tem a finalidade de escolher, dentre os processos que esto na fila de prontos o processo que que esto na fila de prontos, o processo que tenha o menor tamanho para ser executado.

Vantagens Vantagens A principal diferena para o algoritmo SJF a p p p g

preempo, digamos que um processo X esteja em execuo na CPU e nesse meio tempo chegue um processo Y menor do que o restante do processo X nesse processo Y menor do que o restante do processo X, nesse momento ocorrer uma preempo, ou seja, o processo X ir parar sua execuo e ceder lugar para o processo Y executar. Caso chegue um processo ainda menor que o restante do processo Y, esse processo ganhar a CPU e o processo Y retornar para a fila de prontos antes de processo Y retornar para a fila de prontos antes de terminar e ir aguardar um momento para ser executado.

Escalonamento garantidoEscalonamento garantido

Escalonamento garantido um dos tipos de Escalonamento garantido um dos tipos de algoritmos escalonadores. Ele garante aos processos sua execuo dando a todos eles a processos sua execuo, dando a todos eles a mesma quantidade de tempo de execuo utilizando a CPUutilizando a CPU.

Escalonamento garantidoEscalonamento garantido

Se acontecer de um processo utilizar menos Se acontecer de um processo utilizar menos tempo de execuo do que poderia, sua prioridade de execuo aumentada Se outro prioridade de execuo aumentada. Se outro processo utilizou mais do que deveria, sua prioridade diminuidaprioridade diminuida.

Round-robin Round-robin

algoritmo de escalonamento Round-Robin algoritmo de escalonamento Round Robin um dos mais antigos e simples algoritmos, alm de ser totalmente imune a problemas de de ser totalmente imune a problemas de starvation. usado em projetos de sistemas operacionais multitarefa e foi projetado operacionais multitarefa, e foi projetado especialmente para sistemas time-sharing, pois este algoritmo depende de um temporizador este algoritmo depende de um temporizador (Timer).

Funcionamento Funcionamento

O funcionamento deste algoritmo acontece da O funcionamento deste algoritmo acontece da seguinte forma: uma unidade de tempo, denominada quantum definida pelo sistema denominada quantum, definida pelo sistema operativo, onde determina o perodo de tempo entre cada sinal de interrupo Todos os entre cada sinal de interrupo. Todos os processos so armazenados em uma fila circular. Como no exemplo abaixoComo no exemplo abaixo.

Mltiplas FilasMltiplas Filas Mltiplas Filas um tipo de algoritmo de p p g

escalonamento, no qual so usadas filas de processos. Cada fila tem um determinado nvel de prioridade. Sendo um dos mais antigos agendadores de prioridade Sendo um dos mais antigos agendadores de prioridade, estava presente no CTSS (Compatible Time-Sharing System - Sistema Compatvel de Diviso por Tempo). No algoritmo de Mltiplas Filas, tambm pode ser aplicado particularmente, em cada fila, diferentes algoritmos como por exemplo o algoritmo RR ou FCFScomo por exemplo, o algoritmo RR ou FCFS.

Estados de processos Estados de processos

Para o sistema operacional organizar os Para o sistema operacional organizar os processos que sero atendidos eles so atribudos estados para os mesmosatribudos estados para os mesmos.

Diagrama de Estados de Processos Diagrama de Estados de Processos

Quem armazena essas informaes como os Quem armazena essas informaes como os estados de processos e outras como: tempo e execuo por exemplo o PCB (Process Control execuo, por exemplo, o PCB (Process Control Block).

Distribuio de Prioridades Distribuio de Prioridades Para melhorar essa distribuio da CPU entre os

processos, alguns algoritmos utilizam diferentes prioridades, essas prioridades podem ser mudadas no Windows, por exemplo, pelo prprio usurio. Com , p p , p p pintuito de gerenciar melhor as prioridades de processo, o sistema operacional cria filas de processos. Em cada fila existem processos de mesma prioridade, e existe p p ,tambm fila para processos de entrada e sada. Prioridades podem ser mudadas pelo usurio, ou atribudas automaticamente pelo sistema operacional atribudas automaticamente pelo sistema operacional em questo.

Alterando prioridades no WindowsAlterando prioridades no Windows Existem ainda sistemas em que quando um processo Existem ainda sistemas em que quando um processo

inicia sua execuo, o sistema garante que este processo vai ser terminado, so chamados sistemas garantidos. Nestes sistemas a interveno do usurio mnima, ao contrario do que ocorre em sistemas em tempo real como o Windows em que o usurio interrompe processos como o Windows em que o usurio interrompe processos a todo instante por isso o sistema no garante que um processo vai ser Terminado.processo vai ser Terminado.

Trocas de contexto Trocas de contexto Processos so interrompidos e retomados a todo tempo, p p ,

para que o sistema operacional possa fazer esse tipo de ao, necessrio a troca de contexto. Para que o sistema operacional possa interromper um processo e sistema operacional possa interromper um processo e retomar ele mais tarde, ele usa a PCB (Process Control Block) para guardar todas as informaes que a CPU estava usando naquele momento e possa consulta-la mais tarde para que retome exatamente no ponto em que foi interrompido anteriormentefoi interrompido anteriormente.

Dvidas???Dvidas???

Prof. Luiz Henrique Biazotto

E-mail: lzbiazotto@gmail.com

Exerccios Exerccios 1. O que Escalonamento de processos ?q p2. Defina Escalonador de curto prazo ?3. Defina Escalonador de mdio prazo?4 Defina Escalonador de longo prazo?4. Defina Escalonador de longo prazo?5. O que so Algoritmos escalonadores ? E quais so eles?6. O que Estados de processos?

O i ib i d i id d ?7. O que Distribuio de Prioridades?8. Como possvel Alterar prioridades no Windows?9. Defina Trocas de contexto? 9. Defina Trocas de contexto?