Lista 3 - 2023-2

UNIVERSIDADE FEDERAL DE SANTA CATARINA CAMPUS ARARANGUÁ Sistemas Operacionais Prof. Roberto Rodrigues Filho Lista de Exercício 3 – 2023/2 Esta atividade consiste em responder x questões referente Escalonamento de Processos e Impasse. Importante: • Cuidado com Plágio nas respostas. • Pode responder no formato digital. Não precisa tirar foto com as respostas. • A resolução da lista é individual. • Ao anexar o arquivo colocar no formato PDF – caso contrário não será aceito 1) Defina escalonamento de processos e descreva algumas das métricas que este processo tem por objetivo otimizar. 2) No contexto de escalonamento de processos, descreva o que é o Dispatcher e o que ele faz. 3) No escalonamento de processos não-preemptivos, em quais situações os processos são chaveados? 4) Já no escalonamento de processos preemptivos, em quais situações os processos são chaveados? 5) Descreva o algoritmo de escalonamento First-Come First-Served (FCFS). Em quais situações que o tempo médio de espera é mínimo quando se usa FCFS? 6) Considere a tabela abaixo. Monte um gráfico de execução desses processos e calcule o tempo médio de espera levando em consideração que todos os processos chegaram na ordem P1, P2, P3, P4 e P5, todos no tempo = 0, utilizando os seguintes algoritmos: a. First-Come First-Served (FCFS) b. Shortest Job First (JSF) Explique qual método obteve o menor tempo média de espera e por quê? 7) Descreva como o algoritmo de escalonamento de processos Round-Robin (RR) funciona? Considere o quantum de 4ms e a tabela de processos da questão 6 para mostrar a ordem de execução dos processos e o tempo médio de execução. 8) Descreva o algoritmo de escalonamento de processos com prioridade. Defina o que é prioridade estática e o que é prioridade dinâmica. 9) Considerando a tabela de processos da questão 6 e o algoritmo de escalonamento de processos com prioridade, mostre a ordem de execução dos processos e o tempo médio de execução 10) No contexto dos algoritmos de escalonamento de processos com prioridade estática, explique o que é starving? 11) Explique o algoritmo de escalonamento de processos de múltiplas filas com retroalimentação. 12) Explique como funciona o algoritmo de escalonamento de processos fração justa (fair share scheduling). 13) Defina o que é deadlock e descreva as condições necessárias para ocorrer deadlocks, explicando cada uma dessas condições. 14) Quais são as quatro estratégias para lidar com deadlock. Descreva cada uma dessas estratégias. 15) Descreva como deadlocks podem ser detectados. 16) Explique como funciona o algoritmo do banqueiro, dando um exemplo. 17) Explique por que o algoritmo do banqueiro é pouco útil na prática. Lista de Exercício 3 Questão 1 É um aspecto crítico da gestão de sistemas operacionais, referindo-se ao modo como os processos são atribuídos a recursos de CPU para execução. Seu principal objetivo é otimizar diversas métricas, garantindo o uso eficiente dos recursos e uma boa experiência do usuário. Algumas dessas métricas incluem: Tempo de Resposta: Tempo que leva desde a solicitação até a primeira resposta. O escalonamento visa minimizar este tempo, especialmente em sistemas interativos. Throughput: Número de processos completados por unidade de tempo. Um bom escalonador aumenta o throughput, processando o máximo de tarefas possível dentro de um determinado período. Utilização da CPU: Refere-se à manutenção da CPU o mais ocupada possível. Um escalonamento eficaz maximiza a utilização da CPU, reduzindo o tempo ocioso. Equidade: Garante que todos os processos recebam uma quantidade justa de tempo de CPU, evitando a inanição de processos menos prioritários. Tempo de Espera: O tempo que um processo passa na fila de prontos, aguardando ser executado. O escalonamento eficiente procura reduzir o tempo de espera médio. Questão 2 Sua função principal é a transição de um processo do estado de espera para o estado de execução. Atua como um controlador que efetivamente gerencia a execução de processos, permitindo que o sistema operacional otimize a utilização da CPU e mantenha uma execução eficiente dos processos. Questão 3 Ocorre principalmente em duas situações: Quando um processo termina: Após a conclusão de sua execução, o controle é devolvido ao sistema operacional, que pode então selecionar outro processo para execução. Quando um processo bloqueia: Se um processo em execução realiza uma operação de E/S (entrada/saída) ou espera por um evento, ele se bloqueia voluntariamente, cedendo o controle da CPU para outro processo. Questão 4 A troca de processos pode ocorrer em várias situações: Interrupção de Timer: Um temporizador interrompe o processo atual após um período predefinido, permitindo que o escalonador selecione outro processo. Bloqueio por Operações de E/S: Assim como no não-preemptivo, se um processo inicia uma operação de entrada/saída, ele é colocado em espera, e outro processo é escolhido. Finalização do Processo: Quando um processo conclui sua execução, ele é removido da CPU. Criação de Processos de Maior Prioridade: Se um processo de maior prioridade fica pronto para executar, ele pode pré-emptar o processo atual. Solicitação de Espera: Se um processo precisa esperar por um recurso ou evento, ele é suspenso, permitindo a execução de outros processos. Questão 5 O FCFS funciona seguindo uma abordagem linear e não-preemptiva, onde os processos são atendidos na ordem em que chegam, sem preempção. Basicamente, o primeiro processo na fila é o primeiro a ser executado, e assim sucessivamente. O tempo médio de espera é mínimo no FCFS nas seguintes situações: Processos com Tempos de Execução Similares: Quando todos os processos têm tempos de execução aproximadamente iguais, o tempo de espera tende a ser mínimo. Processos com Tempos de Execução Curto Chegando Primeiro: Se os processos com os menores tempos de execução chegam primeiro, eles são rapidamente atendidos, reduzindo o tempo de espera acumulado para os processos subsequentes. Baixa Variabilidade nos Tempos de Chegada e Execução: Quando os processos chegam em intervalos regulares e têm tempos de execução semelhantes, o algoritmo FCFS é eficiente, mantendo o tempo de espera baixo. Em cenários onde há grande variabilidade nos tempos de execução ou chegada, o FCFS pode não ser ideal, podendo levar ao problema conhecido como "efeito convoy", onde processos rápidos são atrasados por processos mais longos que chegaram primeiro. Questão 6 O método Shortest Job First obteve o menor tempo médio de espera No gráfico de execução do SJF, podemos observar que os processos com menor tempo de execução, como P2 e P4, são executados primeiro, seguidos por aqueles com tempos de execução maiores. Isso resulta em uma acumulação menor de tempos de espera em comparação com o FCFS, que executa os processos na ordem de chegada, independentemente de sua duração. O tempo médio de espera para o FCFS foi de 9.6 enquanto que para o SJF foi de 3.2, o que confirma que o SJF é mais eficiente em termos de tempo de espera médio nesse cenário específico. Questão 7 O algoritmo de escalonamento Round-Robin funciona atribuindo um tempo fixo, chamado quantum, para a execução de cada processo. Com um quantum de 4ms, cada processo é executado por até 4ms. Se um processo não terminar nesse tempo, ele é movido para o final da fila. Se terminar antes, a CPU é passada para o próximo processo na fila. Com base na tabela de processos da questão 6 e um quantum de 4ms, a ordem de execução seria: P1, P2, P3, P4, P5, P1, P5, P1. Isso ocorre porque P1 começa a execução, mas como o seu tempo é superior ao quantum, ele é interrompido após 4ms e colocado no final da fila. P2, P3 e P4, que têm tempos de execução de 1ms ou 2ms, são capazes de concluir a execução no seu tempo de quantum. P5 executa por 4ms e é interrompido, e na sua segunda chance, finaliza a execução. P1, sendo o processo mais longo, é executado em várias fatias de 4ms até sua conclusão. O tempo médio de espera calculado para esta sequência de execução é de 10.4ms, que é a média dos tempos de espera individuais para cada processo. Este valor é determinado considerando o tempo que cada processo passa na fila antes de ter a chance de executar. Questão 8 Este algoritmo atribui a cada processo uma prioridade e seleciona o processo com a maior prioridade (sendo o número mais baixo indicativo de maior prioridade em muitos sistemas) para ser executado primeiro. Se dois processos têm a mesma prioridade, eles podem ser escalonados usando o método First-Come First-Served ou algum outro critério de desempate. Pode ser preemptivo ou não-preemptivo. Prioridade Estática é uma prioridade que é atribuída a um processo no momento de sua criação e não muda ao longo de sua execução. Esta prioridade é fixa e definida com base na natureza do processo ou outros critérios definidos pelo sistema ou usuário. Prioridade Dinâmica é uma prioridade que pode mudar durante a execução do processo. Sistemas operacionais podem ajustar dinamicamente as prioridades para evitar a inanição de processos de baixa prioridade ou para recompensar processos que utilizam menos CPU. Isso ajuda a melhorar a responsividade e eficiência do sistema. Questão 9 A ordem de execução dos processos seria: P2, P5, P1, P3 e P4. Isso é determinado pelas prioridades atribuídas a cada processo, onde o número mais baixo indica maior prioridade. O tempo médio de espera para esta sequência de execução é de 8.2ms, que é a média dos tempos de espera individuais para cada processo antes de começar sua execução. Questão 10 Starving refere-se a uma condição onde processos com prioridades mais baixas podem nunca ser executados porque os processos de prioridade mais alta estão sempre disponíveis e tomam a CPU, impedindo que os de menor prioridade sejam escolhidos. Esse problema ocorre em sistemas onde as prioridades não são reajustadas e os processos de alta prioridade continuam chegando, causando um atraso indefinido ou mesmo a omissão completa da execução dos processos de baixa prioridade. Questão 11 É um algoritmo complexo que permite a um processo se mover entre várias filas de escalonamento com base no seu comportamento de execução e nas necessidades de processamento. O MLFQ usa múltiplas filas, cada uma com um nível de prioridade diferente. Novos processos começam na fila de mais alta prioridade e podem ser rebaixados para filas de menor prioridade se não terminarem antes de usar todo o seu quantum de tempo. Questão 12 Este algoritmo é projetado para garantir que cada usuário ou grupo de usuários receba uma quantidade justa de recursos computacionais, como tempo de CPU. Ao contrário de algoritmos que se concentram exclusivamente nos processos individualmente, o fair share leva em conta a posse do processo, distribuindo o tempo de CPU entre os usuários de forma equitativa. Questão 13 É um estado em um sistema onde dois ou mais processos ficam bloqueados permanentemente, esperando por recursos ou eventos que nunca serão liberados ou ocorrerão porque cada processo detém um recurso necessário para o outro. As condições necessárias para que um deadlock ocorra, são: Exclusão Mútua: Um recurso só pode ser usado por um processo de cada vez. Posse e Espera: Um processo deve estar segurando pelo menos um recurso e esperando adquirir recursos adicionais que estão sendo segurados por outros processos. Não Preempção: Recursos não podem ser retirados à força de um processo; eles devem ser liberados voluntariamente pelo processo que os detém. Espera Circular: Deve existir um conjunto de processos em que cada processo está esperando por um recurso que o próximo processo na fila detém, formando um ciclo de espera. A ocorrência simultânea dessas quatro condições cria um ciclo de interdependência que resulta em um impasse, onde nenhum dos processos pode avançar. Para evitar deadlocks, sistemas operacionais tentam prevenir, evitar ou detectar e corrigir uma ou mais dessas condições. Questão 14 Prevenção de Deadlock: foca em negar pelo menos uma das quatro condições necessárias para que um deadlock ocorra. Evitação de Deadlock: diferente da prevenção, a evitação permite a ocorrência das quatro condições mas toma decisões dinâmicas para assegurar que o sistema nunca entre em estado de deadlock. Detecção e Recuperação de Deadlock: esta estratégia envolve a detecção de deadlocks após eles terem ocorrido e a tomada de ações para recuperar o sistema. Ignorar o Problema: em alguns sistemas, principalmente devido ao custo e complexidade dos três primeiros métodos, os deadlocks são simplesmente ignorados. Esta é uma abordagem prática em sistemas onde deadlocks são considerados muito raros ou onde suas consequências são não críticas. Questão 15 Grafo de Alocação de Recursos: Um sistema operacional pode manter um grafo que represente as alocações de recursos aos processos e as solicitações pendentes. Se um ciclo é encontrado no grafo, isso indica a presença de um deadlock. Matriz de Alocação e Solicitação: O sistema operacional pode manter uma matriz de alocação que mostra os recursos alocados a cada processo e uma matriz de solicitação que mostra os recursos que cada processo deseja. Se a solicitação de um processo não puder ser atendida com os recursos disponíveis e os processos envolvidos formarem uma cadeia circular de dependências, um deadlock é detectado. Verificação de Deadlock: Em intervalos regulares, o sistema operacional pode executar um algoritmo de detecção de deadlock que procura por condições de espera circular entre os processos e recursos. Contadores e Temporizadores: O sistema pode usar contadores ou temporizadores para detectar situações em que os processos estão esperando por um tempo anormalmente longo, o que pode indicar um deadlock. Questão 16 O algoritmo do banqueiro é um método de evitação de deadlock que foi proposto por Edsger Dijkstra. Ele é usado para decidir se um pedido de recursos pode ser atendido sem levar o sistema a um estado inseguro. Funciona da seguinte forma: Estado Seguro: O algoritmo verifica se o sistema está em um estado seguro, onde existe pelo menos uma sequência de alocações que permite que cada processo termine. Recursos Disponíveis: O sistema mantém o registro dos recursos disponíveis, os recursos alocados a cada processo e os recursos máximos que cada processo pode solicitar. Pedido de Recurso: Quando um processo solicita um recurso, o algoritmo do banqueiro simula a alocação para verificar se este recurso pode ser concedido sem deixar o sistema em um estado inseguro. Simulação de Terminação: Se a simulação mostra que todos os processos ainda podem terminar usando uma ordem específica de execução, o recurso é alocado ao processo. Se não, o processo deve esperar. Exemplo: Considere um sistema com três processos (P1, P2, P3) e dois tipos de recursos (A e B), onde A tem 10 instâncias e B tem 5 instâncias. Se P1 tem alocado 5 de A e 2 de B, mas ainda precisa de 3 de A e 2 de B para concluir, P2 tem 2 de A e 1 de B e precisa de mais 2 de A e 1 de B, e P3 não tem nada mas precisa de 3 de A e 3 de B, o algoritmo do banqueiro calculará se os recursos disponíveis podem satisfazer essas necessidades sem levar a um estado inseguro. Se um novo pedido de recurso puder ser atendido e ainda permitir que todos os processos eventualmente terminem, o estado é considerado seguro e o pedido é atendido. Caso contrário, o pedido é negado ou o processo é colocado em espera. Questão 17 Alguns dos motivos pelos quais este algoritmo é pouco útil na prática são: Estimativas de Recursos: É difícil para muitos processos saber antecipadamente o máximo de recursos que podem precisar durante a execução. Sobrecarga de Informação: Manter e atualizar constantemente a estrutura de dados necessária para o algoritmo (recursos disponíveis, alocados e máximos requeridos) pode ser uma tarefa com muita sobrecarga. Ambientes Dinâmicos: Em sistemas modernos, onde o conjunto de processos e seus requisitos de recursos podem mudar dinamicamente, aplicar o algoritmo do banqueiro pode ser impraticável. Multiplicidade de Recursos: O algoritmo se torna complexo e pesado quando há um grande número de tipos de recursos diferentes. Desempenho: As verificações e simulações necessárias antes de atender a cada solicitação de recurso podem levar a uma degradação do desempenho. Por essas razões, o algoritmo é mais um conceito teórico usado para entender os deadlocks do que uma solução prática adotada em sistemas operacionais reais.