Aula Escalonamento de processos- USTM

Prévia do material em texto

UNIVERSIDADE SÃO TOMÁS DE MOÇAMBIQUE
FACULDADE DE CIÊNCIAS E TECNOLOGIAS DE INFORMAÇÃO
ESCALONAMENTO DE PROCESSOS 
Sistemas Operativos I 
Tópicos 
Estados de um processo
Bloco de Controle de processo (BCP)
Gestão de Processo 
Escalonamento de processos 
Algoritmos de escalonamento 
Qualidade de escalonamento
Diferenca entre Processo X Programa
Um processo tem características que são dinâmicas e que mudam ao longo do tempo. Dentre essas características podemos citar variáveis, estado, arquivos abertos, contexto. 
O programa é o código (instruções) que encontra-se eu uma memória não volátil diferentemente do processo que estará obrigatóriamente na RAM, quando em execução.
Estrutura / arquitectura do Processo
Características da estrutura de um processo
Bloco de controle do processo (PCB)
Escalonamento 
 Em sistemas multiprogramados (multi-tarefa), a cada instante um ou mais processos podem estar no estado pronto, ex:
 Processos do sistema vs processos de utilizadores 
 Processos curtos vs longos/externos
processos interativos vs intensivos em CPU (CPUbound) ou jobs em batch
O Escalonador é a parte do núcleo responsável por:
 Gestão da/s fila/s de prontos, ajustando prioridades dos processos
 Escolher qual dos processos prontos vai ser o próximo a usar CPU (de acordo com as prioridades dos processos )
Estados de um Processo 
Escalonador- FUNÇãO 
O Escalonador é quem decide a ordem de execução das tarefas prontas. Ele é um dos componentes mais importantes do SO, e faz um uso de um algoritmo, chamado algoritmo de escalonamento. 
O escalonador também permite a execução mais eficiente e rápida de tarefas como aplicações interativas, processamento de grandes volumes de dados, programas de cálculo, 
Dispatcher é Pequeno programa que troca o processador de um processo para outro.
Dispatcher- Função 
Critérios que o escalonador e o algoritmo de escalonamento devem priorizar:
Justiça: fazer com que cada processo ganhe um tempo justo de CPU;
 Eficiência: manter a CPU ocupada 100% do tempo (se houver demanda);
 Tempo de Reposta: minimizar o tempo de resposta aos usuários;
 Tempo de Turnaround: minimizar o tempo que utilizador devem esperar pelo resultado;
 Throughput: maximizar o número de tarefas processadas por unidade de tempo.
Escalonamento
 Escalonamento de longo prazo
Determina quando um processo é inserido no sistema para execução ao ser criado, processo recebe uma prioridade (vai para uma fila dos prontos)
 Escalonamento de médio prazo
 Determina quando processo “swapped out” é recarregado na memória RAM
 Escalonamento de curto prazo (“dispatching”)
 Escolhe um dos processos da fila de prontos para executar (usar o processador)
Processos do tipo CPU-BOUND E I/O-BOUND 
CPU-Bound ( limitado pelo processamento) 
Ligado a CPU passa a maior parte do tempo usando o processador ( estado de execução) e pouco utiliza as operação de E/S. 
Exemplo: Programas de cálculo ou análise, próprias de programas científicos. 
I/O-Bound ( limitado pelas entradas/saídas) 
Esse tipo de processamento usa pouco a CPU e passa a maior parte do seu tempo no estado de bloqueado (ou espera), pois realiza muita operações de E/S. 
Exemplos: Aplicações comerciais (leitura X gravação); 
 Processos interativos ( logon e entrada de dados); 
 Manipulação de Banco de Dados. 
PROCESSOS do tipo CPU-BOUND E I/O-BOUND 
ESTRATÉGIAS DE ESCALONAMENTO 
Preemptivo 
um algoritmo de escalonamento é considerado preemptivo quando a CPU designada para um processo pode ser retirada deste em favor de um outro processo
 Não-preemptivo 
Um algoritmo de escalonamento é dito não preemptivo quando o processador designado para um certo processo não pode ser retirado deste até que o processo seja finalizado
Algoritmos de Escalonamento 
Existem vários algoritmos de escalonamento cujo objectivo principal é alocar o processador para um certo processo, dentre vários processos existentes, optimizando um ou mais aspectos do comportamento geral do sistema. Quatro algoritmos de escalonamento serão abordados neste capítulo 
 FIFO - First- Come-First-Served (FCFS) 
 JSF- Shortest Job First 
 Prioridades 
 RR - Round Robin 
Escalonamento First-In-First-Out - FIFO
Esta é a forma mais simples de escalonamento. No escalonamento FIFO (First In, First Out – Primeiro a entrar, Primeiro a sair), os processos prontos são colocados em uma fila organizada por ordem de chegada. No seu momento, cada processo recebe o uso da CPU até que a sua execução total seja completada, ou seja, o processo permanece em execução até que seja finalizado. Os demais processos na fila de prontos ficam esperando o seu momento de ser executado pelo processador. Desta maneira, o escalonamento FIFO é um algoritmo não preemptivo 
Escalonamento FIFO.
Algoritmos de escalonamento
Escalonamento Shortest Job First (SJF)
Este algoritmo associa a cada processo o tempo aproximado do seu próximo ciclo de UCP a ser executado. Quando o processador fica disponível ele é entregue ao processo que possui o menor próximo ciclo de UCP que foi estimado. 
Exemplo 1 do Algoritmos de SJF- Não Preemptivo
Exemplo 2 do Algoritmos de SJF- Preemptivo
Escalonamento por Prioridade
A cada processo é atribuída uma prioridade, representada por um número inteiro (se é o maior ou o menor número inteiro que representa a maior ou menor prioridade varia de implementação para implementação). A UCP é entregue ao processo que tiver maior prioridade. Processos que tiverem prioridades iguais são escalonados usando-se a idéia de FCFS.
Exemplo de Algoritmo E. por Prioridade
Escalonamento Round Robin (RR)
O algoritmo Round Robin é naturalmente preemptivo e especialmente projectado para sistemas de time-sharing. Cada processo pode ocupar a UCP durante uma quantidade de tempo definida pelo sistema. Essa fatia de tempo recebe o nome de time-slice. Ao final desse tempo o processo executando perde o direito de continuar usando a UCP e é inserido no final da fila de prontos. Neste caso, o processo passa do estado executando para o estado pronto, sem ter passado pelo estado bloqueado. O primeiro processo da fila recebe o processador e começa a sua execução. Novos processos que entram na fila de prontos também são adicionados ao seu final. 
é preemptive 
O escalonador Round Robin é bastante utilizado e bastante recorrente nas questões.
Escalonamento Round Robin.
Exemplo de algortimos RR
Representação gráfica do tempo de permanência.
Qualidade do Escalonamento
A qualidade do serviço oferecido por um algoritmo de escalonamento pode ser avaliada por meio de um critério simples: 
tempo de permanência (tp), 
tempo de espera (te)
tempo de serviço ou execução (ts), 
tpermanência = tespera + tserviço / Tp= Te+Ts 
T.médio de espera=SUM(N.Processos tempo de espera)/n
 
Tempo de permanência normalizado (tpn)
Uma outra forma de avaliar o escalonamento é utilizando o tempo de permanência normalizado (tpn), ou seja, a razão entre o tempo de permanência e o tempo de serviço conforme mostrado a seguir. 
Tpn= Tp = Te+Ts 
 Ts Ts 
T.médio de espera=SUM(N.Processos tempo de espera)/n
Exercícios 
1. Descreva o escalonamento SJF e o escalonamento por prioridades
2. Quais as funções do escalonador e do dispatcher? 
3. Quais os principais critérios utilizados em uma política de escalonamento?
4.seja o caso de quatro processos A, B, C e D com tempos de serviço distintos, 3, 35, 12 e 4 segundos respectivamente, e tendo como o seu nivel de prioridade o seguinte,3, 4,1e 2, os quais são escalonados conforme a sua ordem de chegada pelo SO. 
 Desenhe um diagrama de Gantt ilustrando o escalonamento dos processos e seus respectivos tempos , segundo as políticas especificadas a seguir. O tempo de troca de contexto deve ser desconsiderado.
a) FIFO 
b) SJF 
c) Prioridade (número menor implica prioridade maior) 
d) Circular com fatia de tempo igual a (quantum=2). 
Estrutura monolítica
Topicos para o teste -1
1. Sistema Computacional 
2.Tiposde Sistemas operativos 
3. Composição do Sistema Operativo (Arquitectura)
 Composição do Núcleo
Funções do Núcleo 
Gestão de Processos