Sistemas Operacionais I

Gerência de Processos: Sincronização

Prof. Alexandre Duarte : http://alexandrend.comCentro de Informática | Universidade Federal da Paraíba

Estes slides são baseados no material que acompanha o livro Operating Systems Concepts de Silberschatz, Galvin and Gagne

Objetivos

Introduzir o problema da seç ão críticas, cujas soluç ões podem ser utilizadas para garantir consistência no acesso a dados compartilhados

Apresentar soluç ões em software e hardware para o problema da seç ão crítica

Introduzir o conceito de transaç ão atô mica e descrever os mecanismos utilizados para garantir atomicidade

Antecendentes

Acesso concorrente a dados compartilhados pode resultar em inconsistência nos dados

Para manter a consistência dos dados precisamos de mecanismos para garantir ordem na execuç ão de processos cooperativos

Revisitando o problema do Produtor/ Consumidor

Suponha que desejamos alterar a soluç ão apresentada anteriormente para o problema do Produtor/Consumidor que preencha todas as posiç ões do buffer

Uma ideia seria utilizar uma variável inteira count para contar o número de posiç ões ocupadas no buffer.

Inicialmente count recebe 0 e é incrementado sempre que o produtor inserir algo no buffer e decrementado sempre que o consumidor remover algo do buffer.

Produtor

Consumidor

Condição de corrida

count++ poderia ser implementado assim:

count-- poderia ser implementado assim:

Condição de corrida

O problema da seção crítica Considere um sistema composto por n processo [P0, P1, ... ,

Pn]

Cada um desses processos tem um segmento de código denominado seção crítica em que o processo pode alterar variáveis compartilhadas

Para evitar inconsistências nos dados compartilhados é preciso garantir que dois desses processos jamais executarão ao mesmo tempo código de suas seções críticas

O problema da seção crítica consiste em elaborar um protocolo que possibilite a cooperação entre os processos e que garanta a consistência dos dados compartilhados

Estrutura geral de um processo

Requisitos de uma solução para o problema da seção crítica

Exclusão mútua : se o processo Pi está executando có digo de sua seç ão crítica então nenhum outro processo pode estar executando có digo de suas seç ões críticas

Progresso: Se nenhum processo estiver executando sua seç ão crítica e alguns processos quiserem entrar em suas seç ões críticas, só os processos que não estiverem executando suas seç ões remanescentes poderão participar da decisão sobre qual processo será o pró ximo a entrar em sua seç ão crítica e essa seleç ão não poderá ser adiada indefinidamente

Espera limitada : Há um limite para o número de vezes que outros processos podem entrar em suas seç ões críticas apó s um processo ter feito uma solicitaç ão para entrar na sua seç ão crítica e ter essa solicitaç ão atendida Pode-se presumir que cada processo execute em uma velocidade

diferente de zero mas não se pode fazer qualquer suposiç ão sobre as velocidades relativas dos n processos

Solução de Peterson

Utilizada apenas para pares de processos

Assume que as instruç ões LOAD e STORE são atô micas.

Os processos compartilham duas variáveis: int turn; boolean flag[2]

A variável turn indica de quem é a vez de entrar na seç ão crítica.

O array flag é utilizado para indicar se um processo está pronto ou não para entrar em sua seç ão crítica flag[i] = true implica que o processo Pi está pronto!

Algoritmo para o processo Pi

Hardware de sincronização

Muitos sistemas oferecerem suporte em hardware para controle de acesso a seç ões críticas

Processador único: poderia desabilitar interrupç ões O có digo atualmente em execuç ão não seria interrompido Geralmente essa abordagem é muito ineficiente em sistemas

com múltiplos núcleos/processadores Um sistema operacional que funciona dessa forma não é escalável

Máquinas modernas oferecem instruç ões especiais de hardware com execuç ão atô mica Atô mica = não interrompível Testar e modificar o conteúdo de uma palavra de memó ria Trocar os conteúdos de duas palavras de memó ria

Solução para o problema da seção crítica utilizando locks

A instrução TestAndSet

Solução utilizando TestAndSet

Instrução SWAP

Solução utilizando SWAP

Exclusão mútua com espera limitada utilizando a operação TestAndSet()

Semáforos

Ferramenta de sincronizaç ão baseada em duas operaç ões simples

Semaphore S – variável inteira Duas operaç ões para modificar o semáforo S: wait() e signal() Originalmente P() e V()

Só podem ser acessados através de duas operaç ões indivisíveis (atô micas)

Semáforos como uma ferramenta geral de sincronização

Semáforo de contagem: um valor inteiro que pode variar em um domínio irrestrito Semáforo binário: valor inteiro que só pode variar entre 0 e 1

Também conhecido como bloqueio mutex Garante exclusão mútua

Implementação de Semáforos

É preciso garantir que dois processos não possam executar wait () e signal () em um mesmo semáforo ao mesmo tempo Portanto, o có digo das operaç ões wait e signal se torna

parte da seç ão crítica

Poderíamos então ter agora espera ocupada na implementaç ão da seç ão crítica

Note que algumas aplicaç ões podem gastar bastante tempo em suas seç ões críticas portanto está não é uma boa soluç ão

Implementação de Semáforos sem espera ocupada

Associar uma fila de espera a cada semáforo Cada entrada na fila tem dois itens:

valor (inteiro) ponteiro para o pró ximo registro na fila

Duas operaç ões: block: coloca o processo invocando a operaç ão na

fila de espera apropriada. wakeup: remove um dos processos da fila de espera

e o coloca na fila de prontos

Implementação de Semáforos sem espera ocupada

Deadlock e Starvation Deadlock: dois ou mais processo esperam indefinidamente

por um evento que só pode ser causado por um dos processos em espera

Sejam S e Q dois semáforos inicializados com 1

Starvation: bloqueio indefinido – um processo pode nunca ser removido da fila de espera de um semáforo na qual ele está bloqueado

Inversão de prioridade: Problema de escalonamento que ocorre quando um processo de baixa prioridade bloqueia um processo de prioridade mais alta

Problemas clássicos de sincronização

Problema do Buffer Limitado Problema dos Leitores e Escritores Problema do Jantar dos Filó sofos

Problema do buffer limitado

N buffers, cada um pode armazenar um item Semáforo mutex inicializado com 1 Semáforo full inicializado com 0 Semáforo empty inicializado com N

Problema do buffer limitado: Produtor

Problema do buffer limitado: Consumidor

Problema dos leitores e escritores

Um conjunto de dados é compartilhado entre um número de processos concorrentes Leitores – apenas leem os dados, não fazem qualquer atualizaç ão Escritores – podem tanto ler quanto atualizar os dados

Problema Permitir que múltiplos leitores possam acessar os dados ao mesmo

tempo. Permitir que apenas um escritor tenha acesso aos dados

compartilhados em um determinado momento Dados compartilhados

Conjunto de dados Semáforo mutex inicializado com 1 Semáforo wrt inicializado com 1 Contador inteiro readcount inicializado com 0

Problema dos leitores e escritores: Escritor

Problema dos leitores e escritores: Leitor

O problema do jantar dos filósofos

O problema do jantar dos filósofos

Problemas com semáforos

Uso correto das operaç ões com semáforos

signal (mutex) …. wait (mutex)

wait (mutex) … wait (mutex)

Esquecer um wait (mutex) ou um signal (mutex) (ou ambos)

Monitores

Uma abstraç ão de alto nível que fornece um mecanismo mais conveniente para sincronizaç ão de processos

Apenas um processo pode estar ativo em um monitor a cada momento

Visão esquemática de um monitor

Variáveis condicionais

condition x, y;

Duas operaç ões em uma variável condicional x.wait () – um processo que invoca a operaç ão é

suspenso. x.signal () – reinicia um processo que tenha

invocado um x.wait ()

Monitor com variáveis condicionais

Solução para o problema do jantar dos filósofos

Solução para o problema do jantar dos filósofos

Cada filó sofo invoca as operaç ões pickup() e putdown() na seguinte ordem: