O tempo de execu\u00e7\u00e3o de cada tarefa \u00e9 conhecido.<\/li>\n<\/ol>\nM\u00e9tricas do Planejador<\/h3>\n \n Al\u00e9m de algumas suposi\u00e7\u00f5es sobre a carga, tamb\u00e9m \u00e9 necess\u00e1rio um certo instrumento de compara\u00e7\u00e3o de v\u00e1rias pol\u00edticas de planejamento: as m\u00e9tricas do planejador. M\u00e9tricas s\u00e3o apenas alguma medida de algo. Existe uma quantidade de m\u00e9tricas que podem ser usadas para comparar planejadores.<\/p>\n
Por exemplo, vamos usar uma m\u00e9trica chamada tempo de retorno<\/b> (turnaround time). O tempo de retorno de uma tarefa \u00e9 definido como a diferen\u00e7a entre o tempo de conclus\u00e3o da tarefa e o tempo de chegada da tarefa ao sistema.<\/p>\n
Tturnaround=Tcompletion\u2212Tarrival<\/u><\/p>\n
Como supomos que todas as tarefas chegaram ao mesmo tempo, ent\u00e3o Ta=0 e assim Tt=Tc. Este valor naturalmente mudar\u00e1 quando alterarmos as suposi\u00e7\u00f5es listadas acima.<\/p>\n
Outra m\u00e9trica \u00e9 a justi\u00e7a<\/b> (fairness). Desempenho e justi\u00e7a muitas vezes s\u00e3o caracter\u00edsticas opostas no planejamento. Por exemplo, o planejador pode otimizar o desempenho, mas \u00e0 custa da espera para que outras tarefas sejam iniciadas, diminuindo assim a justi\u00e7a.<\/p>\nFIRST IN FIRST OUT (FIFO)<\/h3>\n
\n O algoritmo mais b\u00e1sico que podemos implementar chama-se FIFO ou primeiro a chegar, primeiro a ser atendido<\/b>. Este algoritmo possui v\u00e1rias vantagens: \u00e9 muito simples de implementar e atende a todas as nossas suposi\u00e7\u00f5es, realizando o trabalho de forma bastante eficaz.<\/p>\n
Vamos considerar um exemplo simples. Suponha que 3 tarefas foram designadas ao mesmo tempo. Mas imagine que a tarefa A chegou um pouco antes das demais, portanto ela estar\u00e1 no in\u00edcio da lista de execu\u00e7\u00e3o, assim como a tarefa B em rela\u00e7\u00e3o \u00e0 tarefa C. Suponha que cada uma delas ser\u00e1 executada por 10 segundos. Qual seria, nesse caso, o tempo m\u00e9dio de execu\u00e7\u00e3o dessas tarefas?<\/p>\n
Como se v\u00ea, diferentes tempos de execu\u00e7\u00e3o das tarefas afetam negativamente a produtividade do algoritmo FIFO. Suponha que a tarefa A ser\u00e1 executada por 100 segundos, enquanto B e C ainda levar\u00e3o 10 segundos cada.<\/p>\n
de efeito de comboio<\/b>, quando alguns consumidores de curto prazo de um recurso ficam na fila atr\u00e1s de um consumidor pesado. Isso \u00e9 semelhante a uma fila no supermercado, onde um cliente \u00e0 sua frente possui um carrinho cheio. A melhor solu\u00e7\u00e3o para o problema \u00e9 tentar mudar de caixa ou relaxar e respirar fundo.<\/p>\nShortest Job First<\/h3>\n
\n \u00c9 poss\u00edvel resolver essa situa\u00e7\u00e3o com processos pesados? Claro. Outro tipo de escalonamento \u00e9 chamadoShortest Job First<\/b> (SJF). Seu algoritmo tamb\u00e9m \u00e9 bastante primitivo \u2014 como o nome indica, as tarefas mais curtas ser\u00e3o executadas primeiro, uma ap\u00f3s a outra.<\/p>\n
50 em vez de 110<\/b>, que \u00e9 praticamente 2 vezes melhor.<\/p>\n
Assim, de acordo com a suposi\u00e7\u00e3o de que todas as tarefas chegam ao mesmo tempo, o algoritmo SJF parece ser o mais otimizado. No entanto, nossas suposi\u00e7\u00f5es ainda n\u00e3o parecem realistas. Desta vez, mudaremos a suposi\u00e7\u00e3o 2 e consideraremos que as tarefas podem chegar a qualquer momento, e n\u00e3o todas ao mesmo tempo. Quais problemas isso pode causar?<\/p>\n
Shortest Time-to-Completion First (STCF)<\/h3>\n \n Para melhorar a situa\u00e7\u00e3o, vamos ignorar a suposi\u00e7\u00e3o 3 de que o programa \u00e9 iniciado e executado at\u00e9 a conclus\u00e3o. Al\u00e9m disso, precisamos de suporte de hardware e, como voc\u00ea pode imaginar, usaremos um temporizador<\/b> para interromper a tarefa em execu\u00e7\u00e3o e mudar contextos<\/b>. Assim, o escalonador pode agir no momento em que as tarefas B e C chegam \u2014 interromper a execu\u00e7\u00e3o da tarefa A e come\u00e7ar a processar as tarefas B e C e, ap\u00f3s sua conclus\u00e3o, retomar a execu\u00e7\u00e3o do processo A. Esse tipo de escalonador \u00e9 chamado de STCF<\/b>ou Preemptive Job First<\/b>.<\/p>\n
M\u00e9trica do Tempo de Resposta (Response Time)<\/h3>\n \n Portanto, se soubermos o tempo de execu\u00e7\u00e3o das tarefas e que essas tarefas usam apenas CPU, o STCF ser\u00e1 a melhor solu\u00e7\u00e3o. Em tempos antigos, esses algoritmos funcionavam e at\u00e9 que muito bem. No entanto, agora o usu\u00e1rio passa a maior parte do tempo no terminal e espera dela uma intera\u00e7\u00e3o produtiva e interativa. Assim surgiu uma nova m\u00e9trica \u2014 o tempo de resposta<\/b> (response).<\/p>\n
O tempo de resposta \u00e9 calculado da seguinte forma:<\/p>\n
Tresponse=Tfirstrun\u2212Tarrival<\/u><\/p>\n
Assim, para o exemplo anterior, o tempo de resposta ser\u00e1: A=0, B=0, C=10 (abg=3,33).<\/p>\n
E o algoritmo STCF n\u00e3o \u00e9 t\u00e3o eficiente em situa\u00e7\u00f5es em que 3 tarefas chegam ao mesmo tempo \u2014 ele ter\u00e1 que esperar at\u00e9 que as pequenas tarefas sejam conclu\u00eddas. Assim, o algoritmo \u00e9 bom para a m\u00e9trica de tempo de resposta, mas ruim para a m\u00e9trica de interatividade. Imagine que, ao usar um terminal na tentativa de digitar caracteres em um editor, voc\u00ea precisasse esperar mais de 10 segundos porque uma outra tarefa estava ocupando o processador. Isso n\u00e3o \u00e9 nada agrad\u00e1vel.<\/p>\n
Round Robin<\/h3>\n \n Para resolver esse problema, foi desenvolvido o algoritmo Round Robin<\/b> (RR). A ideia principal \u00e9 bastante simples: em vez de executar as tarefas at\u00e9 sua conclus\u00e3o, vamos executar uma tarefa por um determinado intervalo de tempo (chamado de qu\u00e2ntico de tempo) e, em seguida, trocar para outra tarefa na fila. O algoritmo repete esse processo at\u00e9 que todas as tarefas sejam conclu\u00eddas. Nesse caso, o tempo de execu\u00e7\u00e3o do programa deve ser um m\u00faltiplo do tempo em que o timer interrompe o processo. Por exemplo, se o timer interrompe o processo a cada x=10ms, o tamanho da janela de execu\u00e7\u00e3o do processo deve ser um m\u00faltiplo de 10 e ser 10, 20 ou x*10.<\/p>\n
Vamos considerar um exemplo: as tarefas ABC chegam simultaneamente ao sistema e cada uma delas deseja executar por 5 segundos. O algoritmo SJF executar\u00e1 cada tarefa at\u00e9 o fim antes de iniciar outra. Em contraste, o algoritmo RR com janela de execu\u00e7\u00e3o = 1s passar\u00e1 pelas tarefas da seguinte maneira (fig. 4.3):<\/p>\n
O tempo m\u00e9dio de resposta para o algoritmo RR (0+1+2)\/3=1, enquanto para SJF (0+5+10)\/3=5.<\/p>\n
\u00c9 l\u00f3gico supor que a janela de tempo \u00e9 um par\u00e2metro muito importante para o RR, quanto menor ela for, maior ser\u00e1 o tempo de resposta. No entanto, n\u00e3o se deve torn\u00e1-la excessivamente pequena, pois o tempo de troca de contexto tamb\u00e9m desempenha um papel na performance geral. Assim, a escolha do tempo de janela de execu\u00e7\u00e3o \u00e9 definida pelo arquiteto do sistema operacional e depende das tarefas que est\u00e3o previstas para serem executadas. A troca de contexto n\u00e3o \u00e9 a \u00fanica opera\u00e7\u00e3o de servi\u00e7o que consome tempo \u2014 o programa em execu\u00e7\u00e3o opera com muitos outros aspectos, como diferentes caches, e a cada troca \u00e9 necess\u00e1rio salvar e restaurar esse ambiente, o que tamb\u00e9m pode demandar bastante tempo.<\/p>\n
O RR \u00e9 um excelente planejador, se estivermos falando apenas sobre a m\u00e9trica do tempo de resposta. Mas como se comportar\u00e1 a m\u00e9trica do tempo de retorno da tarefa com esse algoritmo? Vamos considerar o exemplo acima, quando os tempos de execu\u00e7\u00e3o A, B, C = 5s e chegam ao mesmo tempo. A tarefa A ser\u00e1 conclu\u00edda em 13s, B em 14s, C em 15s, resultando em um tempo m\u00e9dio de retorno de 14s. Assim, o RR \u00e9 o pior algoritmo para a m\u00e9trica de retorno.<\/p>\n
De maneira mais geral, qualquer algoritmo do tipo RR \u00e9 justo, pois divide o tempo de processamento no CPU igualmente entre todos os processos. E, assim, essas m\u00e9tricas est\u00e3o em constante conflito entre si.<\/p>\n
Portanto, temos v\u00e1rios algoritmos opostos e ainda restam algumas suposi\u00e7\u00f5es \u2014 de que o tempo da tarefa \u00e9 conhecido e que a tarefa utiliza apenas o CPU.<\/p>\n
Mistura com I\/O<\/h3>\n \n Em primeiro lugar, vamos remover a suposi\u00e7\u00e3o 4, de que o processo apenas utiliza o CPU, o que, naturalmente, n\u00e3o \u00e9 verdade, pois os processos podem interagir com outros equipamentos.<\/p>\n
No momento em que um processo solicita uma opera\u00e7\u00e3o de entrada e sa\u00edda, ele passa para o estado bloqueado, aguardando a conclus\u00e3o do I\/O. Se o I\/O \u00e9 enviado para o disco r\u00edgido, essa opera\u00e7\u00e3o pode levar v\u00e1rios milissegundos ou mais, e o processador ficar\u00e1 ocioso nesse momento. Nesse tempo, o planejador pode alocar o processador para qualquer outro processo. A pr\u00f3xima decis\u00e3o que o planejador ter\u00e1 que tomar \u00e9 quando o processo concluir seu I\/O. Quando isso ocorrer, haver\u00e1 uma interrup\u00e7\u00e3o e o sistema operacional mudar\u00e1 o processo que solicitou o I\/O para o estado pronto.<\/p>\n
Vamos considerar um exemplo de v\u00e1rias tarefas. Cada uma delas precisa de 50 ms de tempo de processador. No entanto, a primeira ir\u00e1 acessar I\/O a cada 10 ms (que tamb\u00e9m ser\u00e1 executado a cada 10 ms). E o processo B simplesmente utiliza 50 ms de processador sem I\/O.<\/p>\n
O Or\u00e1culo n\u00e3o existe mais.<\/h3>\n \n Agora tentaremos nos livrar da suposi\u00e7\u00e3o de que o tempo de execu\u00e7\u00e3o da tarefa \u00e9 conhecido. Essa suposi\u00e7\u00e3o \u00e9, em geral, a mais errada e irrealista de toda a lista. Na verdade, em sistemas operacionais comuns, o pr\u00f3prio SO geralmente sabe muito pouco sobre o tempo de execu\u00e7\u00e3o das tarefas, como podemos ent\u00e3o construir um planejador sem saber quanto tempo a tarefa levar\u00e1? Talvez pud\u00e9ssemos usar alguns princ\u00edpios de RR para resolver esse problema?<\/p>\n
Resultado<\/h3>\n \n Examinamos as ideias b\u00e1sicas de escalonamento de tarefas e revisamos dois grupos de planejadores. O primeiro inicia a tarefa mais curta primeiro, melhorando assim o tempo de retorno, enquanto o segundo se divide igualmente entre todas as tarefas, melhorando o tempo de resposta. Ambos os algoritmos s\u00e3o ruins onde os algoritmos do outro grupo s\u00e3o bons. Tamb\u00e9m examinamos como o uso paralelo de CPU e I\/O pode melhorar o desempenho, mas ainda n\u00e3o resolvemos o problema da previs\u00e3o do SO. E na pr\u00f3xima aula, veremos um planejador que observa o passado recente e tenta prever o futuro. Ele se chama fila de feedback multi-n\u00edvel.habr.com<\/a><\/p>","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"excerpt":{"rendered":"\u0412\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0432 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u043e\u043d\u043d\u044b\u0435 \u0441\u0438\u0441\u0442\u0435\u043c\u044b \u041f\u0440\u0438\u0432\u0435\u0442, \u0425\u0430\u0431\u0440! \u0425\u043e\u0447\u0443 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0432\u0430\u0448\u0435\u043c\u0443 \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u044e \u0441\u0435\u0440\u0438\u044e \u0441\u0442\u0430\u0442\u0435\u0439-\u043f\u0435\u0440\u0435\u0432\u043e\u0434\u043e\u0432 \u043e\u0434\u043d\u043e\u0439 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e\u0439 \u043d\u0430 \u043c\u043e\u0439 \u0432\u0437\u0433\u043b\u044f\u0434 \u043b\u0438\u0442\u0435\u0440\u0430\u0442\u0443\u0440\u044b \u2014 OSTEP. \u0412 \u044d\u0442\u043e\u043c \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b\u0435 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0433\u043b\u0443\u0431\u043e\u043a\u043e \u0440\u0430\u0431\u043e\u0442\u0430 unix-\u043f\u043e\u0434\u043e\u0431\u043d\u044b\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u043e\u043d\u043d\u044b\u0445 \u0441\u0438\u0441\u0442\u0435\u043c, \u0430 \u0438\u043c\u0435\u043d\u043d\u043e \u2014 \u0440\u0430\u0431\u043e\u0442\u0430 \u0441 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u0430\u043c\u0438, \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u043c\u0438 \u043f\u043b\u0430\u043d\u0438\u0440\u043e\u0432\u0449\u0438\u043a\u0430\u043c\u0438, \u043f\u0430\u043c\u044f\u0442\u044c\u044e \u0438 \u043f\u0440\u043e\u0447\u0438\u0438\u043c\u0438 \u043f\u043e\u0434\u043e\u0431\u043d\u044b\u043c\u0438 \u043a\u043e\u043c\u043f\u043e\u043d\u0435\u043d\u0442\u0430\u043c\u0438, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u044e\u0442 \u0441\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u0443\u044e \u041e\u0421. \u041e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0432\u0441\u0435\u0445 \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b\u043e\u0432 \u0432\u044b \u043c\u043e\u0436\u0435\u0442\u0435 \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u0432\u043e\u0442 \u0442\u0443\u0442. […]<\/p>\n","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"author":1,"featured_media":23990,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[688],"tags":[],"class_list":["post-32158","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-administrirovanie"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t