Faculdade Pernambucana FAPE Sistemas Operacionais Prof. Flávio Gonçalves da Rocha Comunicação entre Processos Monitores Deve-se ter semáforos. muito cuidado ao utilizar Ex: código do produtor com os dois down invertidos, ou seja, o down do mutex antes do down do empty. Se o buffer estiver cheio o produtor é bloqueado com mutex em 0 O consumidor fazendo down no mutex também será bloqueado resultando em deadlock df Para tornar mais fácil escrever programas foi proposta uma primitiva de sincronização de nível mais alto chamada de monitor. Comunicação entre Processos Monitores Um monitor é uma coleção de variáveis, de procedimentos e de estruturas de dados que são agrupados em um tipo especial de módulo ou de pacote. Os monitores facilitam o uso de semáforos df Comunicação entre Processos Monitores Um Monitor df Comunicação entre Processos Monitores Principais aspectos do uso de monitores Todas as regiões críticas não são codificadas dentro df do próprio processo, mas são transformadas em procedimentos do monitor As estruturas de dados internas do monitor só podem ser acessadas por seus procedimentos Quando um processo referencia dados compartilhados ele chama um procedimento do monitor Só um processo pode estar ativo em um monitor em qualquer instante. Comunicação entre Processos Monitores Monitores são uma construção de linguagem de programação Cabe ao compilador implementar a exclusão mútua Implementar exclusão mútua é facil mas não é suficiente, é preciso encontrar uma maneira de bloquear os processos Para o controle de bloqueio são usadas variáveis de condição df São variáveis associadas a condições que provocam a suspensão ou ativação do processo dentro do monitor. Comunicação entre Processos Monitores São declaradas dentro do monitor As variáveis de condições são usadas por dois procedimentos especiais: wait(condicao): O monitor bloqueia o processo. Há uma estrutura de dados associada que guarda as informações do processo signal(condicao): O monitor desbloqueia um processo da fila associada à variável de condição df Comunicação entre Processos Monitores Implementações propostas quando ocorrer um SIGNAL Solução de Hoare O processo que fez a chamada é imediatamente bloqueado O processo recentemente desbloqueado passa a executar. Solução de Brinch Hansen O processo que fez a chamada conclui a operação em curso df Comunicação entre Processos Monitores Solução de Brinch Hansen (Continuação) O processo recentemente desbloqueado aguarda que nenhum processo esteja executando dentro do monitor. df Comunicação entre Processos Monitores df df Um esboço do problema produtores e consumidores com monitores. Só um procedimento de monitor está ativo por vez. O buffer tem N entradas. Comunicação entre Processos Passagem de Mensagem df Semáforos e monitores foram projetados para resolver problemas da exclusão mútua em uma ou mais CPUs, com memória compartilhada/comum Para sistemas distribuídos estas soluções não atendem, é preciso de algo mais: passagem de mensagem A passagem de mensagem é um método de comunicação interprocesso que utiliza duas primitivas, SEND e RECEIVE, que, como os semáforos e, ao contrário dos monitores são chamadas de sistema. Comunicação entre Processos Passagem de Mensagem Questões de Projeto para Passagem de Mensagem Sistemas de Controle de erro (perda de mensagens ou do próprio reconhecimento de entrega) Identificação dos processos Autenticação Desempenho df Comunicação entre Processos Passagem de Mensagem df O problema dos produtores e dos consumidores com N mensagens Escalonamento de Processos Quando mais de um processo é executável, cabe ao SO decidir qual executar primeiro. A parte do SO que toma essa decisão é chamada Agendador. O algoritmo que utiliza é chamado algoritmo de agendamento. Vários critérios vem à mente sobre o que constitui um bom algoritmo de agendamento: 1. A imparcialidade 2. A eficiência 3. Tempo de resposta df 4. Turnaround Escalonamento de Processos 5. Throughput Algumas das contraditórias metas descritas são Para minimizar o tempo de resposta para usuários interativos, o agendador não deve executar nenhum trabalho de lote (isso violaria o critério 4) Qualquer algoritmo de agendamento que favorece alguma classe de trabalho acaba prejudicando outra classe de trabalho df Uma outra complicação para o agendador é que os processos são únicos e imprevisíveis O uso de interrupção de relógio garante que nenhum processo executará por muito tempo Escalonamento de Processos A estratégia de permitir que processos que são logicamente executáveis sejam temporiamente suspensos é chamada de agendamento preemptivo. No agendamento não-preemptivo o processo executa até concluir (antigos sistemas de lote) df Escalonamento de Processos Agendamento Round Robin Mais simples, mais antigo e mais utilizado Fácil de implementar A cada processo é atribuído um intervalo de tempo, chamado quantum, durante o qual lhe é permitido executar. Se o processo ainda está executando no fim do df quantum, é feita a preempção da CPU e ela é dada a outro processo. Se o processo bloqueiou ou terminou antes de o quantum ter passado, é feita a comutação da CPU quando o processo bloqueia, naturalmente. Escalonamento de Processos Agendamento Round Robin Próximo Processo Processo atual B F D G A (a) Processo atual F df D G A B (b) Agendamento round robin. (a) Lista de processos executáveis. (b) Lista de processos executáveis depois que B utiliza todo seu quantum. Escalonamento de Processos Agendamento Round Robin Uma questão importante é o tamanho do quantum Quantum muito pequeno gera muitas comutações de processos e a eficiência da CPU é reduzida Quantum muito longo a resposta pode ser demorada para curtas requisições interativas df Um quantum em torno de 100ms freqüentemente um compromisso razoável. é Escalonamento de Processos Agendamento por Prioridade Processos podem ter prioridades diferentes A necessidade de levar em conta fatores externos conduz ao agendamento por prioridade. A cada processo é atribuído uma prioridade, e o processo executável com a maior prioridade recebe permissão para executar. df A prioridade de um processo em execução pode ser diminuída a cada interrupção de relógio para evitar que um processo execute indefinidamente Escalonamento de Processos Agendamento por Prioridade Alternativamente, a cada processo pode ser atribuído um quantum máximo em que lhe é permitido usar a CPU continuamente. Quando esse quantum é utilizado é dada uma chance de executar ao próximo processo com maior prioridade df As prioridades podem ser atribuídas aos processos estática ou dinamicamente Escalonamento de Processos Agendamento por Prioridade df Muitas vezes é conveniente agrupar processos em classes de prioridade e utilizar agendamento por prioridade entre as classes, mas agendamento round robin dentro da classe. Escalonamento de Processos Agendamento por Prioridade Cabeçalhos de Fila Prioridade 4 Processos executáveis (Maior Prioridade) Prioridade 3 Prioridade 2 Prioridade 1 df (Menor Prioridade) Um algoritmo de agendamento com quatro classes de prioridade Escalonamento de Processos Múltiplas Filas Útil em situações nas quais processos são facilmente classificáveis em diferentes grupos (Ex.: interativos e batch); Prioridades são atribuídas à classes de processos (de acordo com o tipo de processamento), cada qual com sua própria fila de prontos com seu mecanismo de seleção Cada fila pode ter diferentes necessidades de escalonamento (algoritmo diferente); df Escalonamento de Processos Múltiplas Filas Os processos devem ser previamente classificados para serem enviados à fila correspondente. Processos das classes de maior prioridade recebem o processador Os processos das classes de menor prioridade só receberão o processador se as filas de prontos das outras classes (de maior prioridade) estiverem vazias df Escalonamento de Processos Múltiplas Filas df Escalonamento de Processos O Menor Job Primeiro (Shortest-Job-First) Apropriado para o processamento de Jobs em lote, para os quais o tempo de execução é conhecido com antemão É um algoritmo não preemptivo no qual o job na fila de espera com o menor tempo total estimado de processamento é executado em seguida. Esse algoritmo reduz o tempo médio de espera sobre o algoritmo FIFO. df Escalonamento de Processos O Menor Job Primeiro (Shortest-Job-First) Agendamento FIFO 8 4 A Tempo de execução 4 B 8 C 12 4 Agendamento Menor Job Primeiro 4 4 4 8 D B 16 Média de retorno: (8+12+16+20)/4 = 14 minutos df 20 C 4 D 8 A 12 20 Média de retorno: (4+8+12+20)/4 = 11 minutos Escalonamento de Processos O Menor Job Primeiro (Shortest-Job-First) Pode ser usado para processos interativos também desde que seja feito estimativas do tempo de execução do comando tomando por base as execuções passadas. O algoritmo do job mais curto primeiro só é ótimo quando todos os jobs estão disponíveis simultaneamente. df Escalonamento de Processos Escalonamento Dirigido à Política Ás vezes acontece de um processo ter muitos filhos que executam sob seu controle. É plenamente possível que o processo principal tenha uma excelente idéia de quais de seus filhos são os mais importantes (ou de tempo crítico) e quais são menos. df Como os agendadores anteriores não aceita qualquer entrada de processos de usuário sobre decisões de agendamento, raramente, o agendador faz a melhor escolha. Escalonamento de Processos Escalonamento Dirigido à Política A solução é separar o mecanismo de agendamento da política de agendamento. O algoritmo de agendamento é parametrizado de alguma maneira, mas os parâmetros podem ser preenchidos por processos de usuários. Ex: o kernel utiliza um algoritmo de agendamento por prioridade, mas fornece uma chamada de sistema por meio da qual um processo pode definir (e alterar) as prioridades de seus filhos. df Escalonamento de Processos Escalonamento Dirigido à Política Mesmo que os pais não façam o agendamento eles podem controlar em detalhe como seus filhos são agendados. O mecanismo está no kernel, mas a política é configurada por um processo de usuário. df Escalonamento de Processos Agendamento de Dois Níveis Se a memória principal disponível for insuficiente, alguns dos processos executáveis terão de permanceer no disco, inteiros ou em parte. Carregar processo de disco é muito mais demorado do que a comutação de um processo já em memória. Solução: usar um agendador em dois níveis. df O agendador de nível mais baixo fica preocupado com fazer uma escolha entre os processos executáveis que estão na memória principal. Escalonamento de Processos Agendamento de Dois Níveis O agendador de nível mais alto fica preocupado com o movimento dos processos de um lado a outro entre memória e disco. a, b, c, d Processos Na memória principal e, f, g, h b,c, f,g e, f, g, h Processos no disco a, b, c, d a, d, e, h (a) (b) (c) df Um agendador de dois níveis deve mover processos entre disco e memória e também eleger processos para executar na memória. Três instantes diferentes de tempo são representados por (a), (b) e (c) Escalonamento de Processos Agendamento de Dois Níveis Entre os critérios que o agendador de nível mais alto poderia utilizar para tomar suas decisões estão os seguintes: Quanto tempo se passou desde que o processo foi df levado para o disco ou para a memória? Quanto tempo de CPU o processo teve recentemente? Qual é o tamanho do processo? (Os pequenos não atrapalham) Qual o nível de prioridade do processo?