Escalonamento de CPU em Sistemas Operacionais Multiprogramados - Aula 03

INFRAESTRUTURA DE SISTEMAS COMPUTACIONAIS Sérgio Johann Filho Aula 03 2 MAPA DA AULA Neste material você tem uma linha do tempo com os principais acontecimentos das videoaulas organizados nas seguintes seções Momentos importantes da disciplina Conceitos e termos relevantes para o conteúdo da aula Para lembrar Dinâmicas exercícios interativos e infográficos Para exercitar Para ir além Curiosidades personalidades e entretenimento Esta é uma versão simplificada do Mapa da Aula para impressão Os recursos interativos disponíveis no material não funcionarão nesta versão Para uma experiência mais enriquecedora acesse a versão completa do Mapa da Aula na aba AULAS 3 AULA 3 PARTE 1 Nesta aula serão trabalhados conceitos critérios e algoritmos de escalonamento Entre os objetivos estão Introduzir o escalonamento de CPU que é a base para sistemas operacionais multiprogramados Multiprogramação sendo entendida como a execução de múltiplos programas em um mesmo sistema Os programas no contexto de sistemas são entidades vivas a partir do momento que eles são carregados passando a atuar como processos O escalonamento da CPU entre diversos processos acontece de maneira que temos um conjunto limitado de núcleos de execução sendo necessária a utilização de multiprogramação para multiplexar o uso desse recurso entre diferentes processos É dessa forma que temos a possibilidade de termos em execução um conjunto grande de processos de um mesmo sistema dando a ilusão para o usuário de que estão executando em paralelo Descrever diversos algoritmos de escalonamento FCFS e SJF principalmente Discutir critérios de avaliação para seleção de algoritmos de escalonamento para um sistema particular Dependendo do sistema específico teremos objetivos diferentes como o de maximizar o desempenho reduzir custos entre outros Métricas tempo de resposta conceito de justiça entre outros Conceitos critérios e algoritmos objetivos Alguns conceitos fundamentais para a compreensão do que é a multiprogramação e o escalonamento de processos são Máxima utilização da CPU é obtida com multiprogramação devemos considerar que os processos não estarão o tempo todo executando atividade de processamento Muitas vezes eles estarão comprometidos com outras atividades como as operações de entrada e saída como na leitura e escrita de um arquivo Enquanto isso ocorre a CPU não poderá estar processando Dessa forma o que nós teremos é a necessidade de aproveitar o poder de processamento da CPU O escalonador do sistema operacional tem aí então uma responsabilidade de analisar os diferentes processos que estão disponíveis no sistema e escolher algum para executar Assim o objetivo seria encontrar uma forma de atender as solicitações da melhor forma possível maximizando a utilização dos recursos dentro do sistema computacional o que acaba sendo uma responsabilidade do sistema operacional Fase de uso da CPU e de ES a grosso modo os processos estão divididos em duas fases a de uso da CPU e a em que são executadas operações de entrada e saída A execução de processos consiste em uma fase na qual está processando a informação e eventualmente chega a um ponto no qual é necessário realizar operações de entrada e saída É importante lembrar que cada processo possui um perfil específico relacionado com uma aplicação diferente e diferentes aplicações possuem necessidades distintas Uma característica comum que pode ser observada para boa parte das aplicações é que a execução inicia com um CPU burst rajada de processamento e posteriormente ocorre a uma rajada de entrada e saída onde o processo precisa se comunicar com o sistema ou outros processos Conceitos fundamentais 0810 0450 4 Conceitos Fundamentais II Distribuição das fases de uso da CPU CPU bursts a execução de um processo é dividida em fases de CPU e entrada e saída e o agendador de processos precisa distribuir as fases do uso da CPU de maneira a otimizála Histograma de duração das fases de uso da CPU se analisarmos um perfil padrão de execução de processos chegamos à conclusão de que boa parte deles possui um histograma semelhante grande número de bursts curtos e pequeno número de rajadas longas resultando em uma curva exponencial típica comum a diferentes tipos de aplicação Alternando fases do uso da CPU e ES em tempo de execução o que é possível observar é que um programa está executando uma série de operações de entrada e saída ou lógicoaritméticas e isso será referenciado como uma rajada de CPU Em um determinado momento o programa pode solicitar a leitura de um arquivo seguindose uma fase de entrada e saída Depois disso novamente ocorre um ciclo de uso da CPU seguido possivelmente por um novo ciclo de entrada e saída Isso ocorre durante todo o ciclo de vida de um processo Escalonador da CPU dentre os processos que estão parados em uma fila de prontos a CPU vai ser alocada pelo escalonador de acordo com a prioridade em determinado processo trazendoo para o estado de execução Assim o escalonador de CPU tem o objetivo de tomar algumas decisões de escalonamento de CPU Temos três estados que executam durante o tempo do processo e um que ocorre apenas quando ele é finalizado 1 Muda do estado executando para esperando bloqueio 2 Muda do estado executando para pronto 3 Muda do estado esperando para pronto 4 Termina Conceitos Fundamentais III Escalonamento nãopreemptivo a execução não pode ser interrompida a tarefa é executada até o fim O escalonamento nas condições 1 e 4 são nãopreemptivos Escalonamento preemptivo a execução pode ser interrompida com base em prioridades ou seja a tarefa é executada até que outra com maior prioridade seja selecionada As alocações 2 e 3 são preemptivas Despachante dispatcher é o módulo que fornece o controle da CPU ao processo selecionado pelo escalonador da CPU Essa função envolve troca de contexto mudança para o modo usuário desvio para o endereço adequado no programa do usuário para reiniciar o programa uso da pilha ou estrutura de dados para o armazenamento de estado Latência de despacho é o tempo gasto pelo despachante para interromper a execução de um processo e iniciar a de outro Não considera a latência da execução do algoritmo de agendamento A latência do despacho vai depender principalmente de fatores como a arquitetura em que está sendo executado o sistema operacional já que algumas possuem instruções especiais para acelerar o processo de despacho A latência do despacho vai depender de várias mudanças de estado mudança para modo kernel na qual a CPU precisa ser comutada do modo usuário para o modo kernel troca de contexto reprogramação dos registradores da arquitetura para o contexto da execução do processo selecionado mudança para modo usuário reinício do processo escolhido 5 Critérios de alocação de CPU existem diferentes critérios de alocação da CPU mas de forma geral os objetivos podem estar ligados à Utilização de CPU buscando mantêla ocupada a maior parte possível do tempo evitando desperdícios Sua utilização em um sistema real fica entre 40 e 90 Produtividade throughput ou seja o número de processos que completam sua execução por unidade de tempo quanto maior o número de processos tiver a execução completa por unidade de tempo mais o throuput Tempo de processamento turnaround time a quantidade de tempo necessária para executar um determinado processo do início até o fim É composto pela soma de todos os períodos no qual um processo fica no sistema em espera por recursos memória filas do sistema e executando CPU ou IO Tempo de espera que é a quantidade de tempo que um processo esteve esperando na fila de processos prontos Tempo de resposta que trata do intervalo de tempo entre o envio de uma requisição e a produção da primeira resposta Critérios de otimização os critérios de otimização podem ser maximizar a utilização da CPU maximizar produtividade minimizar o tempo de processamento minimizar o tempo de espera ou minimizar o tempo de resposta A otimização será realizada tendo em vista as especificidades do sistema um sistema mobile terá um sistema operacional com objetivo diferente do desktop por exemplo Critérios O escalonamento de CPU lida com o problema de decidir qual dos processos na fila de pronto deve ser alocado à CPU Existem diversos algoritmos diferentes para o escalonamento sendo que cada um utiliza critérios diferentes FCFS First come first served Primeiro a chegar primeiro a ser servido É o algoritmo mais simples que é implementado através de uma estrutura de dados que é uma fila Nesse algoritmo o processo que solicita a CPU primeiro é alocado Uma limitação desse algoritmo é o tempo de espera médio que pode ser longo dependendo da ordem de chegada dos processos Algoritmos de escalonamento I 1837 2321 6 AULA 3 PARTE 2 SJF Shortest Job First preemptive O Shortest Job First preemptive é outra versão do SJF que considera a preempção Nesse algoritmo preemptivo o próximo burst de um processo recémchegado pode ser menor do que o restante de execução para o processo corrente Se tivermos processos com tempo de burst pequeno chegando o tempo todo estaremos postergando a execução de processos que já estavam na fila de prontos para executar No SJF preemptivo o processo corrente será interrompido já no nãopreemptivo o processo corrente executará até o final de seu burst sem ser perturbado Escalonamento por prioridade Outra maneira de realizarmos o agendamento de processos é o escalonamento por prioridade Esse modelo considera associado a cada processo um número inteiro de prioridade A CPU é alocada para o processo com a maior prioridade menor inteiro maior prioridade Aqui um processo com um inteiro 0 possui a maior das prioridades já um com um inteiro 10 possui uma prioridade menor Ele pode ser implementado de forma preemptiva e não preemptiva Esse algoritmo sofre de um mal semelhante ao SJF problema de abandono do processo em função do starvation processo com prioridade baixa pode nunca ser escolhido para executar se tivermos processos com prioridade alta chegando No entanto em soluções mais modernas é feita a utilização de um algoritmo de aging ao passar do tempo aumentar a prioridade dos processos que ficam em espera no sistema Algoritmos de escalonamento III Ainda tratando dos algoritmos de escalonamento temos SJF Shortest Job First Nele os processos são agendados por tamanho a menor tarefa será priorizada Nesse algoritmo é associado a cada processo a duração da sua próxima fase de uso da CPU Quando a CPU estiver disponível é associado o processo com o menor tempo de burst com o objetivo de minimizar o tempo médio de espera No contexto desse algoritmo o uso dessas durações para escalonar o processo com o menor tempo é utilizado entre outras coisas para melhorar o tempo de resposta geral da aplicação Para o usuário isso irá ser percebido como uma maior eficiência do sistema O SJF é considerado ótimo porque permite o menor tempo médio de espera para um dado conjunto de processos No entanto não é considerado o melhor algoritmo existente Há uma condição na qual esse algoritmo não é considerado interessante que é quando existe a possibilidade de causar starvation Além disso existe um problema na impossibilidade de se saber o tamanho da próxima requisição de CPU Isso ocorre porque não é possível adivinhar o padrão representado por um conjunto até o momento da sua execução No entanto podese utilizar aproximações do real tamanho do próximo burst e com base nela selecionar o processo com o menor tempo de burst Isso pode ser feito utilizando como base a duração do uso na fase anterior calculando a média exponencial Algoritmos de escalonamento II Ocorre quando um processo não consegue ser executado porque sempre existem processos de prioridade maior na fila Starvation 1139 0231 7 Escalonamento RR round robin Também conhecido como alocação circular Nesse algoritmo cada processo recebe uma pequena unidade de tempo de CPU quantum fatia de execução que usualmente é de 10 a 100ms Depois de transcorrido este tempo o processo é preemptado e adicionado ao fim da fila de processos prontos Se existem n processos na fila e o quantum for q então cada processo obtém 1n do tempo da CPU em blocos de no máximo q unidades de tempo de uma vez como o algoritmo é rotativo se tivermos 5 processos no sistema com a mesma prioridade cada um receberá 20 de CPU No entanto nenhum processo espera mais do que n1q unidades de tempo Assim aqui estão envolvidos dois fatores o número de processos que fazem parte do sistema e o tempo que um processo deverá esperar para entrar na sua vez de execução O desempenho dependerá do tamanho do quantum se ele for alto se assemelhará a FIFO FCFS se for pequeno tenderá a aumentar o impacto do sistema operacional frente ao desempenho do sistema Alocação por múltiplas filas Podemos ter diversas filas para agendar processos No caso de processos com características de sistema interativo e outros que são executados em segundo plano a alocação em múltiplas filas tende a ser mais adequada Nesse sistema cada fila tem o seu próprio algoritmo de escalonamento que está de acordo com um objetivo em um sistema interativo faria sentido utilizar uma alocação circular RR já em um sistema batch os processos poderiam ser alocados na ordem que chegaram ao sistema O escalonamento deve ser realizado entre as filas sendo feitas transferências Em um escalonamento de prioridade fixa a fila de processos interativos será considerada absolutamente prioritária sobre a fila de processos batch Neste caso sempre haverá possibilidade de starvation No entanto uma estratégia para isso seria alocar tempo 80 para processos interativos em RR e 20 para processos batch em FCFS Algoritmos de escalonamento IV 2301 8 AULA 3 PARTE 3 Nesse modelo diferentemente do processo visto no último bloco ao invés de alocarmos exclusivamente apenas um processo a cada uma das filas podemos implementar a realimentação migrar processos de uma fila à outra Associado a cada processo teremos um mecanismo de aging implementado Esse tipo de escalonamento é definido pelos seguintes parâmetros Número de filas Algoritmos de escalonamento para cada fila Método usado para determinar quando transferir um processo para uma fila de prioridade mais alta Método usado para determinar quando transferir um processo para uma fila de prioridade mais baixa Método usado para determinar em qual fila um processo deve ser colocado quando precisar usar a CPU Múltiplas filas com realimentação Tratando sobre o escalonamento de threads a primeira distinção que deve ser feita é entre threads em nível de usuário e threads em nível de kernel threads em nível de usuário são gerenciadas por uma biblioteca o kernel não possui conhecimento sobre elas Já os threads em nível de kernel são gerenciadas pelo sistema operacional o Linux por exemplo ordena e agenda os processos em função dos threads isto é se o processo tiver apenas um fio de execução teremos um mapeamento 1 para 1 se tivermos múltiplos fios no mesmo processo teremos um mapeamento de muitos para 1 Nos modelos muitosparaum e muitosparamuitos a biblioteca de threads os escalona em nível de usuário para executar em um lightweight process LWP O LWP é conhecido como um processcontention scope PCS o escopo de execução acontece no contexto de um processo uma vez que a competição do escalonamento é dentro do próprio processo Threads em nível de kernel são escalonadas em CPUs disponíveis ou seja o escopo de contenção é em nível de sistema Assim nesse caso como são threads de kernel o sistema operacional tem a oportunidade de explorar melhor o multiprocessamento simétrico Escalonamento de Threads 0208 0646 9 Escalonamento de CPU é mais complexo quando muitos processadores estão disponíveis porque o kernel será responsável por gerenciar filas de múltiplos processadores o que é realidade para a maioria dos sistemas computacionais atuais Dentro de um sistema computacional multiprocessado os computadores podem ser heterogêneos de diferentes ISAs No entanto o caso mais comum são os sistemas com processadores homogêneos que possuem as mesmas características em termos de arquitetura Isso permite ao sistema operacional explorar de melhor forma a execução de múltiplos fios em múltiplos cores Multiprocessamento assimétrico seria o contexto de se ter apenas um processador a acessar a estrutura de dados do sistema Nele o sistema de agendamento só irá executar dentro de um único core Além disso irá acessar as estruturas de dados responsáveis por manter as filas de agendamento e as estruturas de dados como contexto de execução de diferentes fios No multiprocessamento simétrico SMP o que temos é uma série de threads responsáveis por implementar o escalonamento cada processador é autoescalonado todos os processos em uma fila de processos prontos comum ou cada um tem sua fila privada de processos prontos Um processo que executa em um mesmo processador possui um desempenho bom em função da taxa de acerto na cache Podemos ter múltiplos núcleos e em cada núcleo uma quantidade de memória cache integrada Se tivermos vários processos ou fios de execução executando no mesmo processador existe a oportunidade de explorar uma taxa de acerto maior na cache porque os dados já estarão disponíveis nela Escalonamento em multiprocessadores I Se um processo ou thread migrar para outro processador o que teremos é uma limitação com relação à localidade Se tivermos uma migração de threads entre processadores ocorrerá o aumento da taxa de falha princípio de localidade Por outro lado será limitada a questão relacionada aos conflitos se tivermos apenas uma thread alocada a cada core tendendo a aumentar o desempenho dependendo da aplicação A decisão sobre manter uma thread alocada ao mesmo processador ou migrála para múltiplos processadores é do próprio sistema operacional O mecanismo de agendamento precisa definir em qual core um determinado processo será executado Processos possuem afinidade com processador em que estão atualmente executando Isso se dá geralmente de duas formas soft affinity ou hard Affinity A soft Affinity é mais flexível já que o sistema operacional tentará manter um processo ou thread no mesmo processador porém poderá ocorrer migração com objetivo de maximizar alguma métrica do sistema A hard affinity seria um modelo fixo Nele um único fio é mapeado para um único core O sistema operacional manterá esse fio de execução no mesmo processador ou em um grupo de processadores Escalonamento em multiprocessadores II Tratase de um padrão POSIX para threads Ele define uma API padrão para criar e manipular threads As bibliotecas que implementam a POSIX threads são denominadas Pthreads Elas são muito difundidas no universo Unix e outros sistemas operacionais semelhantes como Linux e Solaris POSIX Threads Pthreads 1248 0904 10 O escalonamento no Linux é baseado em classes sendo uma delas o algoritmo CFS Para cada classe é definida uma prioridade específica e é possível utilizar algoritmos de escalonamento distintos podese modificar o comportamento do kernel do Linux utilizarse da criação de processos e estabelecer a associação desses processos a uma das classes para executar de acordo com uma característica específica da aplicação Isso permite adequar o kernel do Linux para diferentes aplicações Por padrão o escalonamento do Linux utiliza duas classes principais Na classe CFS o escalonador atribui a cada tarefa uma proporção do uso de CPU Por padrão uma tarefa é carregada com o valor de nice 0 Mas esses valores podem variar entre 20 e 19 onde um valor menor indicam alta prioridade Uma tarefa 20 deseja utilizar mais recursos do que outras por exemplo Na segunda classe a realtime o escalonador utiliza políticas para o agendamento de tarefa a FIFO que garante que as tarefas sejam executadas na ordem em que chegam a RR que é utilizada para tarefas críticas que possuem uma necessidade de tempo real ou tempo de resposta estrito O algoritmo CFS não utiliza valores de tempo mas uma medida que é chamada de latência alvo não usa o tempo efetivo mas um objetivo Não atribui diretamente prioridades às tarefas O que faz é manter informação a respeito do quanto uma tarefa executou em uma variável que guarda o tempo de execução virtual Essa percepção do tempo por parte da tarefa é chamada de vruntime Esse tempo é associado a um fator de decaimento que vai depender da prioridade da tarefa Tarefas de prioridade normal nice 0 têm um vruntime igual ao tempo físico Em tarefas de prioridade baixa nice 0 o vruntime é maior que o tempo físico Em tarefas de prioridade alta nice 0 o vruntime é menor que o tempo físico A próxima tarefa a executar de acordo com o escalonador CFS será a tarefa com o menor valor de vruntime Escalonamento no Linux 2019 Existe uma tendência recente de colocar múltiplos processadores dentro de um mesmo chip Isso se dá devido a diferentes fatores como a abundância de transistores Hoje em dia temos a possibilidade de integrar um número cada vez maior de transistores o que permite fabricar processadores com um número cada vez maior de núcleos Com o passar do tempo observouse que não é possível fabricar um processador eficiênte com um único núcleo já que as aplicações modernas não são construídas para funcionar nessas condições O modelo de aplicações modernas inclusive considera que a arquitetura é multiprocessada e essas abstrações são utilizadas pelos desenvolvedores para explorar o desempenho Um processador multicore pode ser mais rápido e consumir menos energia do que um processador single core Além disso nos multicore múltiplas threads podem ser executadas Existem processadores que em um mesmo core há replicações de algumas estruturas arquiteturais que permitem múltiplos fios de execução serem mantidos em execução em paralelo A ideia de termos múltiplos fios no mesmo core considera o atraso no acesso à memória para progredir em uma thread ou outra enquanto os dados são transferidos maximizando os recursos Processadores multicore 1633 11 Nesse sistema operacional as treads são escalonadas por um algoritmo preemptivo baseado em prioridades mas ele é bem diferente do algoritmo realtime do Linux O despachante utiliza 32 níveis de prioridade com diferentes classes Existem três agrupamentos gerência de memória que possui a maior prioridade de todas 0 classe variável que tem valor de 1 a 15 classe tempo real que tem os valores de 16 a 31 em termos de prioridade São utilizadas filas para cada prioridade As classes de prioridade são Idle Below normal Normal Above normal High e Realtime No Windows os processos são tipicamente membros da classe normal quando um programa é carregado na memória se tornando um processo ele é lançado na classe normal Dependendo da característica da aplicação ela poderá mudar de prioridade quem define isso é o próprio sistema operacional Uma thread com uma determinada classe possui prioridade relativa às outras dentro da mesma classe Isso é utilizado para não deixar que uma tarefa entre em starvation ou que uma tarefa de menor prioridade postergue a execução de outra de maior prioridade Quando uma thread é iniciada executa até ser interrompida Se ela estiver na classe variável 1 16 sua prioridade é reduzida Se não estiver vai ser mantida A prioridade não diminui além da prioridade base normal Quando um usuário está executando um programa interativo o sistema precisa prover desempenho bom ou seja ele irá aumentar a prioridade de uma tarefa Escalonamento no Windows Escalonamento no Solaris O sistema Solaris utiliza escalonamento baseado em prioridades mas com uma estratégia diferente elas são associadas a características de aplicações Seriam elas Time sharing TS Interactive IA Real time RT System SYS Fair share FSS e Fixed priority FP Em cada classe são utilizadas diferentes prioridades e diferentes algoritmos de escalonamento O padrão quando uma aplicação é carregada é que ela seja classificada como Time sharing TS Quanto maior a prioridade menor o time slice quantum de execução Essas classes e mecanismos de prioridade se traduzem em respectivas tabelas de despacho Entre os campos temos Priority que indica maior prioridade Time quantum que tem um quantum de tempo associado com cada prioridade Time quantum expired que é uma nova prioridade de uma thread que utilizou totalmente seu quantum sem bloquear Threads desse tipo são consideradas CPU bound Return from sleep que é a prioridade de uma thread que está retornando do estado dormindo sleep Threads desse tipo são consideradas IO bound 2619 2923 12 AULA 3 PARTE 4 Nesta parte de aula o professor propõe uma dinâmica Traz 9 exercícios acerca dos temas trabalhados em aula mostrando como podem ser resolvidos As questões abordam o escalonamento ligado a temas como parâmetros de tempo de chegada tempo de execução CPU ou burst parâmetro tempo de resposta starvation ou espera indefinida Os exercícios estão disponibilizados a seguir Bons estudos Exercícios Questão 1 Considere 3 processos com uso intensivo de CPU com tempos de burst de 10ms 20ms e 30ms respectivamente e com tempos de chegada de 0ms 2ms e 6ms Quantas trocas de contexto são necessárias se o algoritmo SJF shortest job first preemptivo for utilizado Questão 3 Se o tempo de quantum do algoritmo RR for muito grande então ele será equivalente ao algoritmo 146 Questão 2 Qual dos seguintes algoritmos de escalonamento podem levar a situação de starvation 1 2 3 FCFS Round Robin RR Shortest Job First SJF FCFS SJF SJF preemptivo 4 Nenhum dos anteriores Nenhum dos anteriores 13 Questão 6 Considere os tempos de chegada e tempos de burst dos processos P0 P1 e P2 Processo P0 P1 P2 Tempo de chegada 0ms 1ms 2ms Tempo de CPU 9ms 4ms 9ms Para o caso preemptivo do algoritmo SJF qual o tempo médio de espera dos três processos Questão 4 Um algoritmo de escalonamento atribui prioridades proporcionais ao tempo de espera de um processo Cada processo inicia com uma prioridade zero menor prioridade O escalonador reavalia as prioridades dos processos a cada T unidades de tempo e decide pelo próximo processo a ser escalonado Qual das afirmações é verdadeira considerando que não existem operações de entrada e saída e que todos os processos chegam juntos no instante zero Questão 5 Considere os seguintes processos seus tempos de chegada e tempos de uso de CPU Processo P1 P2 P3 Tempo de chegada 0ms 1ms 3ms Tempo de CPU 5ms 7ms 4ms A ordem na qual os processos irão completar considerando as políticas FCFS e RR com um quantum de 2 unidades será Questão 7 Quais das afirmações abaixo são verdadeiras I O algoritmo SJF pode causar starvation II Escalonamento preemptivo pode causar starvation III O algoritmo RR é melhor que o FCFS em termos de tempo de resposta Esse algoritmo é equivalente ao FCFS Esse algoritmo é equivalente ao RR Esse algoritmo é equivalente ao SJF Esse algoritmo é equivalente ao SJF preemptivo FCFS P1 P2 P3 RR2 P1 P2 P3 FCFS P1 P3 P2 RR2 P1 P3 P2 FCFS P1 P2 P3 RR2 P1 P3 P2 FCFS P1 P3 P2 RR2 P1 P2 P3 5ms 433ms 633ms 733ms Apenas a I Apenas I e III Apenas II e III I II e III 14 Questão 8 Um sistema operacional utiliza o algoritmo SJF preemptivo para o escalonamento de processos Considere os tempos de chegada e de execução de acordo com a tabela Processo P1 P2 P3 P4 Tempo de chegada 20ms 25ms 10ms 15ms Tempo de CPU 0ms 15ms 30ms 45ms Qual o tempo de espera total para o processo P2 5ms 15ms 40ms 55ms 15 AULA 3 PARTE 5 Nessa parte de aula o professor traz mais 7 questões de 9 a 15 que nos ajudam aprofundar nossos conhecimentos sobre o tema escalonamento relacionandoo com algoritmos tempo de chegada tempo de processamento CPU ou burst tempo de resposta tempo de execução tarefatempo As questões trabalhadas se encontram abaixo Exercícios Um sistema operacional utiliza o algoritmo SJF preemptivo Considere o seguinte conjunto de processos com seus tempos de chegada e tempos de burst de CPU Questão 10 Processo P1 P2 P3 P4 Tempo de chegada 0ms 2ms 3ms 8ms Tempo de CPU 12ms 4ms 6ms 5ms O tempo médio de espera dos processos é Considere quatro processos os quais possuem 10ms 20ms 30ms e 15ms de tempo de processamento respectivamente Os tempos de chegada são 0ms 2ms 6ms e 7ms Quantas trocas de contexto são necessárias se o sistema operacional estiver utilizando o algoritmo SJF preemptivo Questão 9 0015 1 2 3 4 45ms 5ms 55ms 65ms 16 Questão 12 Qual dos algoritmos abaixo é não preemptivo Questão 13 Considere um conjunto de n tarefas com tempos de execução r1 r2 rn executando em um sistema com um único processador Qual dos algoritmos de escalonamento abaixo resultará em uma maior taxa de execução Questão 11 Considere o seguinte conjunto de processos com tempos de chegada e de CPU de acordo com a tabela abaixo Processo P1 P2 P3 P4 Tempo de chegada 0ms 1ms 2ms 4ms Tempo de CPU 5ms 3ms 3ms 1ms Qual o tempo de resposta médio para os processos considerando o algoritmo SJF preemptivo 55ms 575ms 6ms 625ms Round robin FCFS Múltiplas filas Múltiplas filas com realimentação Round robin Shortest job first FCFS FIFO LIFO 17 Considere os processos abaixo com seus tempos de chegada e tempo de uso de CPU burst O algoritmo SJF preemptivo é utilizado Questão 15 Processo P1 P2 P3 P4 Tempo de chegada 0ms 3ms 7ms 8ms Tempo de CPU 10ms 6ms 1ms 3ms O tempo médio de resposta é Tempo de CPU 3ms 6ms 4ms 2ms Questão 14 Para os processos listados abaixo qual dos algoritmos de escalonamento resultará no menor tempo médio de resposta Processo A B C D Tempo de chegada 0ms 1ms 4ms 6ms FCFS SJF SJF preemptivo RR2 825ms 1025ms 635ms 425ms PUCRS online