Document

Introdução

Para melhor entendimento sobre o escalonador de processos é necessario o conhecimento de alguns termos e cenarios especificos

-Processo em Sistemas Operacionais

Processo é uma abstração do programa em execução, o qual mantem a capacidade de operações pseudo concorrentes,mesmo havendo apenas uma CPU disponivel

A CPU chaveia de programa para programa, executando cada um deles dezenas ou centenas de milisegundos. A cada instante a CPU executa somente um programa, mas ao decorrer de um segundo ela pode trabalhar sobre vários programas, provocando uma sensação de paralelismo.

-Multiprogramação

em definição ,cada processo tem sua própria CPU virtual, mas na prática a CPU troca a todo momento de um processo para outro. Assim um conjunto de processos executando paralelamenteé conceitual quando há apenas uma CPU. O mecanismo de trocas rapidas, onde a CPU faz os chaveamentos é chamado de multiprogramação.

Uma maquina para cada processo;

Paralelismo Real.

Compartilhameto do tempo;

Pseudo-paralelsimo.

Escalonamento

Para que a CPU não fique muito tempo sem executar tarefa alguma, os sistemas operacionais utilizam técnicas para escalonar os processos que estão em execução na máquina.

O escalonamento de processos é uma atividade complicada já que nenhum algoritmo é totalmente eficiente e a prova de falhas, principalmente em se tratando de sistemas interativos, como o Microsoft Windows. Nos sistemas interativos a interação com o usuário é fundamental já que quem o utiliza busca respostas rápidas e, a todo o momento, processos são interrompidos pelo usuário.

Escalonamento é muito atuante nos sistemas em tempo real, onde o tempo é um fator extremamente crítico, como: aviões, hospitais, usinas nucleares, bancos, multimídia, etc. Em ambientes como estes, quando um sistema tem respostas com atraso, é tão ruim quanto não obter.

Tipos de sistemas em tempo real:

Hard Real Time onde atrasos não são tolerados (aviões, usinas nucleares, hospitais); Soft Real Time quando atrasos são tolerados (Bancos, Multimídia). O escalonador do SO utiliza alguns critérios de escalonamento, como:

A taxa de utilização de CPU, que é a fração de tempo durante a qual ela está sendo ocupada;

Throughput que são números de processos terminados por unidade de tempo;

Turnaround que é o tempo transcorrido desde o momento em que o software entra e o instante em que termina sua execução;

Tempo de resposta: intervalo entre a chegada ao sistema e inicio de sua execução;

Tempo de espera: soma dos períodos em que o processo estava no seu estado pronto.

Os responsáveis por essa tarefa são algoritmos de escalonamento. Os sistemas operacionais utilizam combinações deles para melhor escalonar os processos.

Objetivos do Escalonamento

O projeto de um escalonador adequado deve levar em conta uma série de diferentes necessidades, ou seja, o projeto de uma política de escalonamento deve contemplar os seguintes objetivos[carece de fontes]

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 (throughput): 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.

Como pode ser visto facilmente, alguns destes objetivos são contraditórios, pois dado que a quantidade de tempo disponível de processamento (tempo do processador) é finita, assim como os demais recursos computacionais, para que um processo seja favorecido outro deve ser prejudicado.

O maior problema existente no projeto de algoritmos de escalonamento está associado à natureza imprevisível dos processos, pois não é possível prevermos se um dado processo utilizará intensamente o processador, ou se precisará grandes quantidades de memória ou se necessitará numerosos acessos aos dispositivos e E/S.

Escalonamento em Dois Niveis

Nem sempre a memória principal é suficiente para comportar todos os processos. Às vezes é preciso manter algumas tarefas no disco. Um processo que esteja parcialmente na memória principal e parcialmente em disco pode comprometer o tempo de resposta, já que o tempo de comutação de processos em disco é muito maior do que o tempo de comutação da memória principal. Para melhorar a comutação em disco, uma solução seria utilizar o escalonamento em dois níveis: nível alto e nível baixo.

Inicialmente, divide-se o processo em subconjuntos, em seguida é feita a escolha de qual desses subconjuntos serão carregados na memória principal temporariamente. O papel do nível alto tem a função de esvaziar a memória principal quando os processos estiverem em tempo suficiente e carregar os processos que estiverem muito tempo em disco. Enquanto o nível baixo restringe-se aos processos que estão carregados na memória principal e dedica exclusivamente em escolher entre esses processos, o nível alto dedica a fazer o transporte de processos memória ↔ disco.

O escalonamento de processos ou agendador de tarefas é uma atividade organizacional feita pelo escalonador da CPU ou de um sistema distribuído, possibilitando executar os processos mais viáveis e concorrentes, priorizando determinados tipos de processos, como os de I/O Bound e os CPU Bound.

O escalonador de processo é um processo que deve ser executado quando da mudança de contexto (troca de processo), ao passo que ele escolhe o processo que será executado pela CPU, sendo o escalonamento realizado com o auxílio do hardware.

São utilizados algoritmos de escalonamento para determinar qual processo será executado em determinado momento e por quanto tempo.

O escalonador de processos de 2 níveis escolhe o processo que tem mais prioridade e menos tempo e coloca-o na memória principal, ficando os outros alocados em disco; com essa execução o processador evita ficar ocioso.

O escalonador deve ainda se preocupar com a eficiência da CPU, pois o chaveamento de processos é complexo e custoso, uma vez que ele afeta o desempenho do sistema e por sua vez a satisfação do usuário.

Aqui precisamos manter parte dos processos em disco (pois a memória principal dificilmente comporta todos os dados necessários). O problema é que o tempo para ativar um processo que está em disco é muito maior que o para ativar um que está na memória. A melhor solução para isto é a utilização de um escalonador em dois níveis. Para isso um subconjunto dos processos executáveis é mantido na memória e um outro subconjunto é mantido no disco. Um escalonador (baixo nível(tempo curto)) é utilizado para realizar o chaveamento (por qualquer método descrito anteriormente) apenas entre os processos que estão na memória e outro escalonador (alto nível) é utilizado para trocar periodicamente o conjunto de processos que estão na memória (por aqueles que estavam em disco). Para escolher qual conjunto de processos será colocado na memória, o escalonador de alto nível deve verificar: o tamanho do processo, a prioridade do processo, o tempo de UCP do processo, quando tempo se passou desde que o processo foi posto ou retirado.

O uso da CPU se alternam com periodos de espera por E/S. (a) Um processo orientado a CPU. (b) Um processo orientado à E/S.

Exemplos

Considere este problema: um sistema contém 50 processos em execução, todos com igual prioridade. No entanto, a memória do sistema pode conter apenas 10 processos na memória simultaneamente. Portanto, sempre haverá 40 processos trocados gravados na memória virtual do disco rígido. O tempo necessário para trocar e trocar em um processo é de 50 ms, respectivamente.

Com o escalonamento round-robin direto , toda vez que ocorre uma troca de contexto , um processo precisa ser trocado (porque apenas os 10 processos menos usados recentemente são trocados). A escolha aleatória entre os processos diminuiria a probabilidade para 80% (40/50). Se isso ocorrer, obviamente um processo também precisa ser trocado. Trocar dentro e fora é caro, e o planejador perderia muito do seu tempo fazendo trocas desnecessárias.

É aí que a programação de dois níveis entra em cena. Ele usa dois planejadores diferentes, um escalonador de nível baixo que só pode selecionar entre os processos na memória para executar. Esse escalonador pode ser um escalonador round-robin.

O outro escalonador é o escalonador de nível alto, cuja única preocupação é entrar e trocar processos da memória. Ele faz sua programação com muito menos frequência do que o escalonador de nível baixo, pois a troca leva muito tempo.

Assim, o escalonador de nível alto seleciona entre os processos na memória que foram executados por um longo tempo e os troca. Eles são substituídos por processos no disco que não são executados há muito tempo. Exatamente como ele seleciona os processos depende da implementação do escalonador de nível alto. Um compromisso deve ser feito envolvendo as seguintes variáveis:

Tempo de resposta : um processo não deve ser trocado por muito tempo. Então, algum outro processo (ou o usuário) terá que esperar muito tempo. Se essa variável não for considerada falta de recursos, pode ocorrer e um processo pode não ser concluído.

Tamanho do processo: processos maiores devem estar sujeitos a menos trocas do que os menores, porque demoram mais tempo para trocar. Por serem maiores, menos processos podem compartilhar a memória com o processo.

Prioridade: quanto maior a prioridade do processo, mais tempo ele deve permanecer na memória para que seja concluído mais rapidamente.

Escalonamento FCFC(First-Come, First Served)

É a forma mais elementar de escalonamento. Utiliza um algoritmo simples que atende as tarefas em sequência assim que ficam prontas. Ou seja, de acordo com sua chegada na fila de prontos (FIFO). Não utiliza preempção.

import java.text.DecimalFormat; import java.util.ArrayList; import java.util.Scanner; public class fcfs { public static void main(String[] args) { // declaracao de variaveis Scanner scanner = new Scanner(System.in); int N, entrada, tempoAtual; double tempoExecucao, tempoEspera; ArrayList processos, ingressos, duracoes, temposFinais, temposIniciais; int contTeste = 0; N = scanner.nextInt(); String formato, saida; DecimalFormat nf = new DecimalFormat("0.00"); while (N != 0) { contTeste++; // inicializacao de variaveis processos = new ArrayList(); ingressos = new ArrayList(); duracoes = new ArrayList(); temposFinais = new ArrayList(); temposIniciais = new ArrayList(); tempoEspera = 0; tempoExecucao = 0; for (int i = 1; i <= N; i++) { // adiciona processo a lista de processos processos.add(i); // le e adiciona ingresso no processo i entrada = scanner.nextInt(); ingressos.add(entrada); // le e adiciona duracao do processo i entrada = scanner.nextInt(); duracoes.add(entrada); } // tempo inicial = tempo de ingresso do primeiro processo tempoAtual = ingressos.get(0); // adicionando tempos de inicio e termino dos processos for (int i = 0; i < N; i++) { if (ingressos.get(i) > tempoAtual) { tempoAtual = ingressos.get(i); } temposIniciais.add(tempoAtual); tempoAtual += duracoes.get(i); temposFinais.add(tempoAtual); } // calculo dos tempos medios de espera e execucao for (int i = 0; i < N; i++) { tempoExecucao += temposFinais.get(i) - ingressos.get(i); tempoEspera += temposIniciais.get(i) - ingressos.get(i); } tempoExecucao = tempoExecucao / N; tempoEspera = tempoEspera / N; System.out.println("Teste " + contTeste); formato = nf.format(tempoExecucao); saida = "Tempo medio de execucao: " + formato + "s"; saida = saida.replace(".", ","); System.out.println(saida); formato = nf.format(tempoEspera); saida = "Tempo medio de espera: " + formato + "s"; saida = saida.replace(".", ","); System.out.println(saida); // ordem dos processos = em tempo de entrada for (int i = 0; i < N; i++) { System.out.print("P" + processos.get(i) + " "); } System.out.println(); System.out.println(); N = scanner.nextInt(); } } }

Escalonamento Round-Robin

O FCFS não leva em conta a importância das tarefas nem seu comportamento em relação aos recursos. É o algoritmo FCFS com a adição de preempção por tempo ao escalonamento. Define um tempo de quantum.

tempo de quantum = 2

import java.text.DecimalFormat; import java.util.ArrayList; import java.util.Scanner; public class round { @SuppressWarnings("unchecked") public static void main(String[] args) { Scanner scanner = new Scanner(System.in); // declaracao de variaveis int quantum, N, entrada, tempoAtual, execucao, q, temposFinais[], qteprocessos, novaDuracao, temposExecucao[]; ArrayList ingressos, duracoes, processos, cpingressos, cpduracoes; String ordem; double tempoMedioExecucao, tempoMedioEspera; int contTeste = 0; String formato, saida; DecimalFormat nf = new DecimalFormat("0.00"); quantum = scanner.nextInt(); N = scanner.nextInt(); while (N != 0) { contTeste++; processos = new ArrayList(); ingressos = new ArrayList(); duracoes = new ArrayList(); ordem = ""; qteprocessos = N; temposFinais = new int[N]; temposExecucao = new int[N]; // lendo os processos for (int i = 0; i < N; i++) { entrada = scanner.nextInt(); ingressos.add(entrada); entrada = scanner.nextInt(); duracoes.add(entrada); } cpingressos = (ArrayList) ingressos.clone(); cpduracoes = (ArrayList) duracoes.clone(); // int tmpInicial = ingressos.get(0); tempoAtual = ingressos.get(0); processos = new ArrayList(); processos = new ArrayList(); while (qteprocessos > 0) { // verifica antes de iniciar a execucao de um processo for (int i = 0; i < N; i++) { if (ingressos.get(i) != -1 && ingressos.get(i) <= tempoAtual) { processos.add(i); ingressos.set(i, -1); } } if (processos.isEmpty()) { tempoAtual++; } else { execucao = processos.remove(0); ordem += "P" + (execucao + 1) + " "; q = quantum; while (q > 0 && duracoes.get(execucao) > 0) { tempoAtual++; q--; novaDuracao = duracoes.get(execucao) - 1; duracoes.set(execucao, novaDuracao); } if (duracoes.get(execucao) > 0) { // verificar primeiramente se algum processo entrou // durante // o // tempo de execucao for (int i = 0; i < N; i++) { if (ingressos.get(i) != -1 && ingressos.get(i) <= tempoAtual) { processos.add(i); ingressos.set(i, -1); } } processos.add(execucao); } else { // processo acabou temposFinais[execucao] = tempoAtual; qteprocessos--; } } } // calculo de tempo medio de espera e execucao; tempoMedioExecucao = 0; tempoMedioEspera = 0; for (int i = 0; i < N; i++) { temposExecucao[i] = temposFinais[i] - cpingressos.get(i); tempoMedioExecucao += temposExecucao[i]; tempoMedioEspera += temposExecucao[i] - cpduracoes.get(i); } tempoMedioExecucao = tempoMedioExecucao / N; tempoMedioEspera = tempoMedioEspera / N; System.out.println("Teste " + contTeste); formato = nf.format(tempoMedioExecucao); saida = "Tempo medio de execucao: " + formato + "s"; saida = saida.replace(".", ","); System.out.println(saida); formato = nf.format(tempoMedioEspera); saida = "Tempo medio de espera: " + formato + "s"; saida = saida.replace(".", ","); System.out.println(saida); System.out.println(ordem); System.out.println(); N = scanner.nextInt(); } } }

Escalonamento SJF

O algoritmo de escalonamento que proporciona os menores tempos médios de execução e de espera é conhecido como menor tarefa primeiro, ou SJF (Shortest Job First). Consiste em atribuir o processador à menor (mais curta) tarefa da fila de tarefas prontas.

import java.text.DecimalFormat; import java.text.NumberFormat; import java.util.ArrayList; import java.util.Locale; import java.util.Scanner; public class sjf { // versao 2 @SuppressWarnings("unchecked") public static void main(String[] args) { Scanner scanner = new Scanner(System.in); // declaracao de variaveis int N, entrada; ArrayList processos, ingressos, cpingressos = new ArrayList(), duracoes; int[] temposFinais = new int[1], temposIniciais = new int[1]; int idProcessoAtual; String ordemExecucao = "", formato, saida; double tempoEspera, tempoExecucao; int contTeste = 0; DecimalFormat nf = new DecimalFormat("0.00"); N = scanner.nextInt(); while (N != 0) { contTeste++; ordemExecucao = ""; processos = new ArrayList(); ingressos = new ArrayList(); duracoes = new ArrayList(); temposFinais = new int[N]; temposIniciais = new int[N]; for (int i = 0; i < N; i++) { // le e adiciona tempo de ingresso do processo entrada = scanner.nextInt(); ingressos.add(entrada); // le e adiciona tempo de duracao do processo entrada = scanner.nextInt(); duracoes.add(entrada); } // cria copia da lista de tempos de ingressos devido a modificacoes cpingressos = (ArrayList) ingressos.clone(); int execucao; int qteprocessos = N; // tempo inicial = primeiro tempo da lista de ingressos int tempoAtual = ingressos.get(0); while (qteprocessos > 0) { // percorre ingressos para achar processos que ingressam nesse // tempo processos = new ArrayList(); for (int i = 0; i < N; i++) { if (ingressos.get(i) != -1 && ingressos.get(i) <= tempoAtual) { // adicionar na lista de processos processos.add(i); } } // assumindo que o primeiro da lista eh o de menor duracao if (processos.isEmpty()) { tempoAtual++; } else { execucao = processos.get(0); for (int i = 0; i < processos.size(); i++) { idProcessoAtual = processos.get(i); // se a duracao do processo atual for menor do que a // menor // duracao // ja encontrada if (duracoes.get(idProcessoAtual) < duracoes .get(execucao)) { // entao alteramos o processo que vai executar execucao = processos.get(i); } } temposIniciais[execucao] = tempoAtual; tempoAtual += duracoes.get(execucao); temposFinais[execucao] = tempoAtual; ingressos.set(execucao, -1); // define ordem de execucao ordemExecucao += "P" + (execucao + 1) + " "; qteprocessos--; } } // calculo tempo de execucao e tempo de espera tempoExecucao = 0; tempoEspera = 0; for (int i = 0; i < N; i++) { tempoExecucao += temposFinais[i] - cpingressos.get(i); tempoEspera += temposIniciais[i] - cpingressos.get(i); } tempoExecucao = tempoExecucao / N; tempoEspera = tempoEspera / N; // DecimalFormat f = (DecimalFormat) DecimalFormat // .getInstance(new Locale("pt", "BR")); // String saida = "Tempo medio de execucao: " // + f.format(tempoExecucao) + "s"; System.out.println("Teste " + contTeste); formato = nf.format(tempoExecucao); saida = "Tempo medio de execucao: " + formato + "s"; saida = saida.replace(".", ","); System.out.println(saida); formato = nf.format(tempoEspera); saida = "Tempo medio de espera: " + formato + "s"; saida = saida.replace(".", ","); System.out.println(saida); System.out.println(ordemExecucao); System.out.println(); N = scanner.nextInt(); } } }

Referências

https://pt.wikipedia.org/wiki/Escalonamento_de_processos#:~:text=O%20escalonador%20 de%20processos%20de,o%20processador%20evita%20ficar%20ocioso.

https://alexcoletta.eng.br/artigos/escalonamento-de-processos/

http://marcelmesmo.blogspot.com/2011/11/escalonamento-de-processos.html#.X4mk89BKhPZ

https://en.wikipedia.org/wiki/Two-level_scheduling

http://wiki.inf.ufpr.br/maziero/doku.php?id=so:livro_de_sistemas_operacionais