sábado, 11 de setembro de 2010

ESCALONAMENTO


Get a Voki now!


Escalonamento de processos

Existem vários processos que estão num mesmo tempo de execução na máquina, o sistema operacional através de suas técnicas de escalonamento é o responsável em definir a ordem de execução para que a CPU não fique muito tempo sem executar nenhuma tarefa.
O escalonamento de processos é uma tarefa complicada, pois nenhum algoritmo é totalmente eficiente e a prova de falhas, principalmente em se tratando de sistemas interativos, como o Windows, pois a interação com o usuário é fundamental para este sistema onde quem o utiliza procura respostas rápidas e a todo o momento processos são interrompidos pelo usuário.
É uma atividade organizacional feita pelo escalonador da CPU possibilitando executar os processos mais viáveis e concorrentes.
Existem três tipos básicos de escalonador:

Escalonador de curto prazo
Quando os processos estão no estado de pronto é selecionado para ser executado pelo processador.

Escalonador de médio prazo
Quando os processos estão na memória virtual são selecionados, reduzindo o grau de multiprogramação. Ele remove temporariamente o processo da memória principal e coloca na memória secundária fazendo as operações de swapping.

Escalonador de longo prazo
Seleciona entre os processos novos, os que são limitados por entrada/saída e os que são limitados por CPU. Este escalonador é o responsável pelo grau de multiprocessamento, ou seja a quantidade de processos que o sistema irá trabalhar.

Objetivos do Escalonamento
Ser justo: Todos os processos devem ser tratados igualmente, tendo possibilidades idênticas de uso do processador, devendo ser evitado o adiamento indefinido.
Maximizar a produtividade (taxa de transferência): Procurar maximizar o número de tarefas processadas por unidade de tempo.
Ser previsível: Uma tarefa deveria ser sempre executada com aproximadamente o mesmo tempo e custo computacional.
Minimizar o tempo de resposta para usuários interativos.
Maximizar o número possível de usuário interativos.
Minimizar a sobrecarga (overhead): Recursos não devem ser desperdiçados embora algum investimento em termos de recursos para o sistema pode permitir maior eficiência.
Favorecer processos "bem comportados": Processos que tenham comportamento adequado poderiam receber um serviço melhor.
Balancear o uso de recursos: o escalonador deve manter todos os recursos ocupados, ou seja, processos que usam recursos sub- utilizados deveriam ser favorecidos.
Exibir degradação previsível e progressiva em situações de intensa carga de trabalho.

Algoritmos escalonadores
Existem os algoritmos preemptivos e os não preemptivos. Os preemptivos são algoritmos que permitem que um processo seja interrompido durante sua execução, quer seja por força de uma interrupção de entrada/saída, quer seja em decorrência da politica de escalonamento adotada e aplicada por parte do escalonador de processos ou simplesmente por força do término da execução do processo. Após a interrupção deste processo, ocorre a troca de contexto, que consiste em salvar o conteúdo dos registradores e a memoria utilizada pelo processo e conceder à outro processo o privilégio de executar na CPU, restaurando assim o contexto deste último processo. Os algoritmos não preemptivos, por serem utilizados exclusivamente em sistemas monoprocessados, esse fato não ocorre, sendo cada programa executado até o fim.
Exemplos de Algoritmos:
FIFO (First in, first out) ou FCFS (First come, first served): O primeiro que chega será o primeiro a ser executado;
SJF (Shortest Job First): O menor processo ganhará a CPU e atrás do mesmo formar uma fila de processos por ordem crescente de tempo de execução;
SRT (Shortest Remaining Time): Neste algoritmo é escolhido o processo que possua o menor tempo restante, mesmo que esse processo chegue à metade de uma operação, se o processo novo for menor ele será executado primeiro;
Algoritmo Loteria: O Sistema Operacional distribui tokens (fichas), numerados entre os processos, para o escalonamento é sorteado um numero aleatório para que o processo ganhe a vez na CPU, processos com mais tokens têm mais chance de receber antes a CPU.
Escalonamento garantido: Este algoritmo busca cumprir promessas de alocação de CPU o mais preciso possível.
RR (Round-Robin): Nesse escalonamento o sistema operacional possui um timer, chamado de quantum, onde todos os processos ganham o mesmo valor de quantum para rodarem na CPU. Com exceção do algoritmo RR e escalonamento garantido, todos os outros sofrem do problema de Inanição (starvation).
Múltiplas Filas: São usadas várias filas de processos prontos para executar, cada processo e colocado em uma fila, e cada fila tem uma política de escalonamento própria e outra entre filas.
Todos os algoritmos classificam os processos em estados: Iniciando, Pronto, Executando, Entrada/ Saída e Terminado.

Distribuição de Prioridades

Para melhorar essa distribuição da CPU entre os processos, alguns algoritmos utilizam diferentes prioridades, essas prioridades podem ser mudadas no Windows, por exemplo, pelo próprio usuário. Com intuito de gerenciar melhor as prioridades de processo, o sistema operacional cria filas de processos. Em cada fila existem processos de mesma prioridade, e existe também fila para processos de entrada e saída. Prioridades podem ser mudadas pelo usuário, ou atribuídas automaticamente pelo sistema operacional em questão.
Mesmo com a aplicação de prioridades e algoritmos melhor implementados, alguns processos ainda correm o risco de sofrer starvation (ficar muito tempo sem receber a CPU) por isso em determinando momento pode ocorrer o que chamamos de aging (O aging ocorre quando a prioridade de um processo vai se alterando com o "tempo de vida" do mesmo, controlando o starvation), que muda momentaneamente a prioridade de um processo que não é executado há muito tempo e joga sua prioridade para a mais alta possível para que ele seja atendido, logo após as prioridades voltam ao normal.
Outro caso em que prioridades são alteradas é quando um programa de baixa prioridade começou a fazer uso de algum periférico de entrada e saída antes de outro de prioridade alta. Neste caso processos de alta prioridade são obrigados a esperarem os de baixa terminar sua E/S para poderem usar este periférico.

Alterando prioridades no Windows

Existem ainda sistemas em que quando um processo inicia sua execução, o sistema garante que este processo vai ser terminado, são chamados sistemas garantidos. Nestes sistemas a intervenção do usuário é mínima, ao contrario do que ocorre em sistemas em tempo real como o Windows em que o usuário interrompe processos a todo instante por isso o sistema não garante que um processo vai ser Terminado.

Trocas de contexto

Processos são interrompidos e retomados a todo tempo, para que o sistema operacional possa fazer esse tipo de ação, é necessário a troca de contexto. Para que o sistema operacional possa interromper um processo e retomar ele mais tarde, ele usa a PCB (Process Control Block) para guardar todas as informações que a CPU estava usando naquele momento e possa consulta-la mais tarde para que retome exatamente no ponto em que foi interrompido anteriormente.

Threads

Processos podem ser divididos em “pedaços” para que ele não deixe de responder por algum motivo externo, onde isto possa atrapalhar a execução do mesmo, ou para agilizar a programação e execução. Quando programas são divididos em threads, podemos ter partes do processo rodando em paralelo, threads também são escalonáveis.

Diagrama de mudanças de estado de uma thread:

Escalonamento no sistema operacional
Windows NT/2000/XP


    Hoje, todos os computadores são capazes de executar várias tarefas ao mesmo tempo. O usuário, quando executa um programa o computador pode ler dados de um disco e mostrar um texto na tela ou enviar para a impressora. O sistema multiprogramado, a CPU alterna de programa para programa, executando cada um deles por dezenas ou centenas milissegundos. Por isso que a CPU a cada instante que executa um programa, no decorrer de um segundo ele pode trabalhar com vários programas, dando ao usuário a ilusão de paralelismo.

  • Processo é um programa em execução. Que pode ser formado por um conjunto de threads.


  • A thread é uma unidade de execução para o SO.


  • Cada processo tem pelo menos uma thread, que é chamada de thread primária, a qual é criada quando o processo é carregado para execução.



  • Exitem processos que criam outras threads, para que se explore o paralelismo da execução.


  • Cada threads tem a sua própria pilha de execução, seu contexto de execução ( reproduzido pelos registradores da CPU) e sua prioridade.


  • A memória alocada para um processo é dividida proporcionalmente ao número de threads que o processo possui.
Escalonamento de threads

  • No Windows 2000/XP o escalonador usa múltiplas filas e os processos interativos (I/O bound) possuem prioridade sobre os CPU bound.


  • O escalonamento tem por base as prioridades. Cada thread possui um número de prioridade, que varia de 0 a 31 (0 é a menor e 31 a maior)


  • A prioridade 0 é uma thread especial, sendo responsável por zerar as páginas livres do sistema. Somente ela pode receber a prioridade 0.


  • As prioridades são divididas em duas classes de threads:


    Real time: prioridades de 16 a 31 (executam até terminar ou bloquear);
    Normal: prioridades de 0 a 15 (recebem fatias de tempo).
  • Temos uma classe especial chamada idle, a de mais baixa prioridade. As threads nesta classe só vão ser executadas quando não existirem outras threads aptas, isto é, elas não interferem na performance, não causam overhead.


  • O escalonador seleciona a thread de maior prioridade.


  • As threads da classe real time são executadas até terminar ou serem bloqueadas.