1. Algoritmos de escalonamento
1.1. O escalonamento de CPU lida com o problema de decidir a quais processos na fila de processos prontos a CPU deverá ser alocada. Existem muitos algoritmos diferentes de escalonamento de CPU
1.2. Escalonamento first-come, first-served
1.2.1. O algoritmo de escalonamento mais simples é de longe o algoritmo de escalonamento first-come, first-served (FCFS)
1.2.1.1. O processo que solicita a CPU primeiro, a recebe primeiro. A implementação da política FCFS é facilmente gerenciada com uma fila FIFO. Quando um processo entra na fila de processos prontos, seu PCB é ligado ao final da fila. Quando a CPU é liberada, ela é alocada ao processo no início da fila.
1.3. Escalonamento job mais curto primeiro
1.3.1. Esse algoritmo associa a cada processo a duração de seu próximo surto de CPU. Quando a CPU está disponível, ela é atribuída ao processo que tem o próximo surto de CPU menor. Se dois processos tiverem seus próximos surtos de CPU de mesma duração, o escalonamento FCFS será usado para desempate
1.3.2. A verdadeira dificuldade com o algoritmo SJF 6 conhecer a duração do próximo pedido de CPU
1.3.3. não pode ser implementado no nível do escalonamento de CPU de curto prazo. Não existe como saber a duração do próximo surto de CPU
1.3.4. Escalonamento por prioridade
1.3.4.1. Uma prioridade está associada a cada processo, c a CPU é alocada ao processo com prioridade mais alta. Processos de prioridade igual são escalonados na ordem FCFS.
1.3.4.2. Um algoritmo SJF nada mais é do que um algoritmo por prioridade no qual a prioridade (/>) é 0 inverso do próximo surto de CPU (previsto). Quanto maior o surto, menor a prioridade, e vice-versa.
1.3.4.3. Preemptivo
1.3.4.3.1. Um algoritmo de escalonamento por prioridade preemptivo interromperá a CPU se a prioridade do processo recem-chegado for maior do que a prioridade do processo em execução no momento.
1.3.4.4. Não-preemptivo
1.3.4.4.1. Um algoritmo de escalonamento por prioridade não-preemptivo simplesmente colocará o novo processo no topo da fila de processos prontos.
1.3.4.5. Um problema crítico com os algoritmos de escalonamento por prioridade é o bloqueio por tempo indefinido ou starvation (estagnação).
1.3.4.5.1. Um processo que está pronto para executar mas que não tem a CPU pode ser considerado bloqueado, esperando pela CPU. Um algoritmo de escalonamento por prioridade pode deixar que alguns processos de baixa prioridade fiquem esperando indefinidamente pela CPU
1.3.4.6. Uma solução para o problema do bloqueio indefinido de processos de baixa prioridade é o envelhecimento (aging)
1.3.4.6.1. O envelhecimento é uma técnica para aumentar gradualmente a prioridade dos processos que ficam esperando no sistema durante muito tempo
1.4. Escalonamento Round-Robin
1.4.1. O algoritmo de escalonamento Round-Robin (RR) (revezamento circular) foi projetado especialmente para sistemas de tempo compartilhado.
1.4.2. Implementar o escalonamento Round-Robin
1.4.2.1. a fila de processos prontos é mantida como uma fila FIFO dos processos. Novos processos são adicionados ao final da fila. O escalonador de CPU seleciona o primeiro processo da fila, define um temporizador para interromper depois de 1 quantum e submete o processo.
1.4.3. O desempenho do algoritmo RR depende do tamanho do quantum de tempo.
1.5. Escalonamento por múltiplas filas
1.5.1. algoritmos de escalonamento foi criada para situações em que os processos são facilmente classificados em diferentes grupos
1.5.2. algoritmo de escalonamento por múltiplas filas divide a fila de processos prontos em várias filas separadas
1.5.2.1. 1. Processos do sistema 2. Processos interativos 3. Processos de edição interativa 4. Processos cm batch 5. Processos secundários
1.5.3. Escalonamento por múltiplas filas com realimentação
1.5.3.1. permite que um processo se mova entre as filas. A ideia é separar os processos com diferentes características de surto de CPU.
1.5.3.2. Se um processo usar tempo de CPU excessivo, será movido para uma fila de menor prioridade. Esse esquema deixa os processo limitados por entrada/saída e interativos nas filas de prioridade mais alta. Da mesma forma, um processo que espera demais em uma fila de baixa prioridade pode ser passado para uma fila de maior prioridade. Essa forma de envelhecimento evita a estagnação.
1.5.3.3. É definido pelos seguintes parâmetros:
1.5.3.3.1. • O número de filas • O algoritmo Je escalonamento para cada fila • O método usado para determinar quando promover um processo para uma fila de maior prioridade • O método usado para determinar quando rebaixar um processo para uma fila de menor prioridade • O método usado para determinar em que fila um processo entrará quando esse processo precisar de serviço
1.5.3.3.2. Torna o algoritmo de escalonamento de CPU mais geral. Pode ser configurado para corresponder a um sistema específico cm desenvolvimento. Embora uma fila multinível com realimentação seja o esquema mais geral, também c o mais complexo.
2. Escalonamento com múltiplos processadores
2.1. Estático
2.1.1. fila global para evitar ociosidade de processador
2.1.2. contexto do processo disponível para todos os processadores (depende muito do projeto)
2.2. Dinâmico
2.2.1. estimativas são conhecidas antes da execução e não as características reais.
2.2.2. a especificação do escalonamento é feita ao longo da execução da aplicação
2.3. Multiprocessamento simétrico (SMP)
2.3.1. Cada processador examina a fila de processos prontos comum e seleciona um processo para executar
3. Escalonamento de tempo real
3.1. Sistemas de tempo real crítico
3.1.1. São compostos por software de propósito especial executando cm hardware dedicado aos seus processos críticos.
3.2. Sistemas de tempo real não-crítico
3.2.1. Processos críticos recebam prioridade cm relação a outros menos favorecidos
3.2.2. Acrescentar funcionalidade de tempo real não-crítico a um sistema de tempo compartilhado possa causar alocação injusta de recursos e resultar em atrasos maiores, ou mesmo starvation (paralisação), para alguns processos.
3.2.3. requer o projeto cuidadoso do escalonador e aspectos relacionados do sistema operacional.
4. Escalonamento de threads Java
4.1. Escalonamento de threads Java
4.1.1. A JVM escalona threads usando um algoritmo de escalonamento preemptivo baseado em prioridades
4.1.1.1. Todos os threads Java recebem uma prioridade e a JVM escalona o thread executável com a prioridade mais alta para execução. Se dois ou mais threads executáveis tiverem a prioridade mais alta, a JVM escalonará os threads usando uma fila FIFO
4.1.2. A JVM escalona um thread para execução quando um dos seguintes eventos ocorre:
4.1.2.1. 1. O thread em execução no momento sai do estado Executável. Um thread pode deixar o estado Executável de várias formas, tais como bloqueando operações de l/O, saindo do seu método run( ) ou chamando o método suspendi ) ou stop{ ).
4.1.2.2. 2. Um thread com prioridade mais alta do que o thread em execução no momento entra no estado Executável. Nesse caso, a JVM interrompe o thread em execução no momento e escalona o thread com prioridade mais alta para execução.
4.2. Fatia de tempo
4.2.1. Com fatias de tempo
4.2.1.1. Um thread Executável será executado durante seu quantum de tempo ou até sair do estado Executável ou ser interrompido por um thread de prioridade mais alta
4.2.2. Sem fatias de tempo
4.2.2.1. Um thread será executado até que um de dois eventos listados ocorra
4.3. Prioridades de thread
4.3.1. Todos os threads Java recebem como prioridade um inteiro positivo dentro de um determinado intervalo
4.3.2. Os threads recebem uma prioridade default quando são criados e - a menos que sejam alterados explicitamente pelo programa
4.3.2.1. eles mantêm a mesma prioridade em toda sua vida; a JVM não altera prioridades de forma dinâmica
4.3.3. A classe Thread de Java identifica as seguintes prioridades de thread:
4.3.3.1. Thread.N0RM_PR10RITY A prioridade default de thread.
4.3.3.2. Thread.MIN_PRIORITY A prioridade mínima de thread.
4.3.3.3. Thread.MAX_PRIORITY A prioridade máxima de thread.
4.3.3.4. O valor de MINPRIORITY é 1, o de MAX_PRIORITY é 10 e o de N0RM_PR10R1TY é 5
5. Conceitos básicos
5.1. O objetivo da multiprogramação é ter sempre algum processo cm execução para maximizar a utilização de CPU. Para um sistema uni processador, nunca haverá mais de um processo em execução. Se houver mais processos, o restante terá de esperar até que a CPU esteja livre e possa ser reescalonada.
5.2. Ciclo de surtos de CPU e I/O
5.3. Escalonador de CPU
5.4. Escalonamento preemptivo
5.5. Dispatcher
6. Critérios de escalonamento
6.1. Utilização de CPU
6.1.1. A CPU deverá ficar o mais ocupada possível. A utilização da CPU pode variar de 0 a 100%
6.2. Throughput
6.2.1. Sc a CPU estiver ocupada executando processos, o trabalho estará sendo feito. Uma medida de trabalho é o número de processos completados por unidade de tempo, denominado throughput. Para processos longos, essa taxa pode ser de um processo por hora; para transações curtas, o throughput pode ser de 10 processos por segundo.
6.3. Tempo de retorno
6.3.1. Do ponto de vista de determinado processo, o critério importante é quanto tempo leva para executar esse processo. O intervalo entre a submissão de um processo até o seu tempo de conclusão é o tempo de retorno. Esse tempo é a soma dos períodos gastos esperando para acessar a memória, aguardando na fila de processos prontos, executando na CPU e realizando operações de entrada/saída
6.4. Tempo de espera
6.4.1. O algoritmo de escalonamento de CPU não afeta a quantidade de tempo durante a qual determinado processo executa ou efetua I/O; afeta apenas o tempo que um processo gasta esperando na fila de processos prontos. O tempo de espera é a soma dos períodos gastos esperando na fila de processos prontos.
6.5. Tempo de resposta
6.5.1. Um processo pode produzir algum resultado logo de início c pode continuar computando novos resultados enquanto os anteriores estiverem sendo repassadas para o usuário. Assim, outra medida é o tempo entre a submissão de um pedido até a primeira resposta ser produzida. Essa medida, chamada de tempo de resposta, é 0 tempo que O processo leva para começar a responder, mas não é o tempo que leva para gerar a resposta. O tempo de resposta geralmente é limitado pela velocidade do dispositivo de saída.
7. Escalonamento de threads
7.1. Máquina com uma única CPU utiliza paralelismo
7.2. Mesmo com várias CPUs, pode haver mais threads querendo rodar do que CPUs disponíveis
7.3. Escalonamento do Solaris 2
7.3.1. São definidas quatro classes de escalonamento, que são, cm ordem de prioridade: de tempo real, de sistema, de tempo compartilhado e interativa.
7.3.2. Em cada classe, existem diferentes prioridades e diferentes algoritmos de escalonamento
7.3.3. Utiliza a classe de sistema para executar processos do kerncl, tais como o escalonador e o daemon de paginação.
7.3.3.1. A prioridade de um processo de sistema não muda. A classe de sistema é reservada para uso do kernel
7.3.4. Os threads na classe de tempo real recebem a mais alta prioridade
7.3.4.1. Um processo de tempo real executará antes que um processo em qualquer outra classe. Em geral, poucos processos pertencem à classe de tempo real.
7.3.5. Existe um conjunto de prioridades em cada classe de escalonamento. No entanto, o escalonador converte as prioridades específicas de classe em prioridades globais e selcciona executar o thread com a prioridade global mais alta
8. Avaliação de algoritmos
8.1. Para selccionar um algoritmo, devemos primeiro definir a importância relativa dessas medidas. Nossos critérios podem incluir várias medidas, como:
8.1.1. • Maximizar a utilização de CPU sob a limitação de que o tempo de resposta máximo é 1 segundo
8.1.2. • Maximizar o throughput de modo que o tempo de retorno seja (em média) linearmente proporcional ao tempo de execução total
8.2. Modelagem determinista
8.2.1. É um tipo de avaliação analítica
8.2.1.1. Esse método pega um determinado volume de trabalho predeterminado e define o desempenho de cada algoritmo para esse volume de trabalho.
8.2.2. Avaliação analítica
8.2.2.1. A avaliação analítica utiliza o algorit' mo dado e o volume de trabalho do sistema para gerar uma fórmula ou número que avalia o desempenho do algoritmo para aquele volume de trabalho.
8.2.3. A modelagem determinista é simples e rápida
8.2.4. Os principais usos da modelagem determinista são em descrever algoritmos de escalonamento e em fornecer exemplos. Nos casos em que os mesmos programas estejam sendo executados seguidamente e nos quais seja possível medir exatamente os requisitos de processamento do programa, a modelagem determinista talvez possa ser usada para selecionar um algoritmo de escalonamento
8.3. Modelos de filas
8.3.1. A distribuição dos surtos de CPU e de l/O
8.3.1.1. podem ser medidas e aproximadas, ou simplesmente estimadas
8.3.1.2. O resultado é uma fórmula matemática par descrever a probabilidade de determinado surto de CPU
8.3.1.3. A equação, conhecida como a fórmula de Littlc, é particularmente útil porque é válida para qualquer algoritmo de escalonamento e distribuição de chegada
8.3.1.3.1. n = X x W
8.4. Simulações
8.4.1. obter uma avaliação mais precisa dos algoritmos de escalonamento
8.4.1.1. envolve programar um modelo de sistema de computador.
8.4.2. o baseada em distribuição
8.4.2.1. Os dados que conduzem a simulação podem ser gerados de várias formas. O método mais comum utiliza um gerador de números aleatórios, que é programado para gerar processos, tempos de surtos de CPU, chegadas, partidas e assim por diante, de acordo com distribuições de probabilidade
8.4.2.2. As distribuições podem ser definidas matematicamente (uniforme, exponencial, Poisson) ou empiricamente. Se a distribuição for definida empiricamente, são feitas medidas do sistema real sendo estudado. Os resultados definem a distribuição real de eventos no sistema real; essa distribuição pode então ser usada para conduzir a simulação.
8.4.2.3. As simulações podem ser caras, geralmente exigindo horas de tempo do computador. Uma simulação mais detalhada fornece resultados mais precisos, mas requer mais tempo de computação.
8.5. Implementação
8.5.1. A única forma completamente precisa de avaliar um algoritmo de escalonamento c codificá-lo, colocá-lo no sistema operacional e verificar seu funcionamento
8.5.2. A principal dificuldade dessa abordagem é o alto custo
8.5.2.1. Os custos envolvem não apenas a codificação do algoritmo e modificação do sistema operacional para suportá-lo e as estruturas de dados exigidas por ele, mas também a reação dos usuários a um sistema operacional em constante mudança
8.5.2.2. O ambiente no qual o algoritmo é usado será alterado
8.5.2.2.1. O ambiente mudará não só da forma normal, à medida que novos programas são escritos e os tipos de problemas mudam, mas também como resultado do desempenho do escalonador
8.5.3. A grande variedade de algoritmos de escalonamento exige que tenhamos métodos para selecionar dentre eles. Os métodos analíticos utilizam análise matemática para determinar o desempenho de um algoritmo. Os métodos de simulação determinam o desempenho imitando o algoritmo de escalonamento em uma amostra "representativa" de processos e calculando o desempenho resultante.