Linguagem de Programação II: Sincronização e Exclusão Mútua com Monitores

Linguagem de Programação II Carlos Eduardo Batista Centro de Informática UFPB biduciufpbbr Roteiro Introdução Sintaxe e Semântica Exclusão Mútua Variáveis Condicionais Tipos de Sinalização Técnicas de Sincronização Monitores em C Monitores em Java Introdução O fato de os semáforos consistirem em um mecanismo de sincronização de baixo nível torna sua utilização mais susceptível a erros O programador pode omitir acidentalmente operações P ou V Ele pode executar mais operações P do que V ou vice versa Pode empregar semáforos errados ou falhar em proteger seções críticas e em garantir atomicidade Tanto exclusão mútua quanto sincronização condicional são implementadas com o mesmo par de primitivas Introdução Monitores são módulos de programas que fornecem mais estrutura que os semáforos sendo implementados de forma igualmente eficiente Monitores consistem em um mecanismo de abstração de dados que encapsula a representação de um objeto e fornece um conjunto de operações Introdução Eles possuem variáveis que armazenam o estado de um objeto e procedimentos que operam sobre ele Exclusão mútua é provida implicitamente ao garantir que procedimentos no mesmo monitor não executem concorrentemente Sintaxe e Semântica O monitor agrupa a representação e a implementação de um recurso compartilhado Possui uma interface e um corpo A interface representa as operações providas O corpo contém as variáveis e as implementações das operações Sintaxe e Semântica monitor nome declarações de variáveis permanentes instruções de inicialização procedimentos Sintaxe e Semântica Propriedades Apenas os procedimentos são visíveis fora do monitor nomeMonitornomeOpargs Instruções dentro do monitor não podem acessar variáveis declaradas fora dele A inicialização das variáveis permanentes ocorre antes das chamadas dos procedimentos Exclusão Mútua Com monitores a exclusão mútua ocorre de forma implícita No máximo um procedimento pode estar ativo em determinado momento em um monitor Cabe à linguagem biblioteca e sistema operacional proverem a exclusão mútua Geralmente implementada através de locks e semáforos Variáveis condicionais Sincronização condicional é implementada através de variáveis condicionais São utilizadas atrasar processos através de uma condição booleana O valor de uma variável condicional é uma fila de processos atrasados cond cv Variáveis condicionais Três operações básicas emptycv Verifica se a fila de processos atrasados está vazia waitcv Bloqueia a execução de um processo inserindoo em uma fila de espera signalcv Acorda o processo que está no início da fila FIFO da variável condicional Tipos de Sinalização Quando o processo sinalizador acorda um processo através da operação signalcv qual dos dois terá a posse do monitor Tipos de Sinalização Sinalizar e continuar O processo sinalizador continua e o sinalizado entra na fila para executar no monitor Sinalizar e esperar O processo sinalizador é interrompido dando lugar para o processo sinalizado assumir a execução no monitor Sinalizar e esperar urgentemente O processo sinalizador é colocado no início da fila de espera Tipos de Sinalização Diagrama de estados Tipos de Sinalização Implementação de semáforos utilizando monitor Tipos de Sinalização Implementação de semáforos utilizando monitor Semaphore s process CSi1 to n while true sPsem Seção crítica sVsem Seção não crítica Tipos de Sinalização Não Implementa apenas para o tipo SE O código do monitor anterior implementa um semáforo FIFO para ambos os tipos de sinalização Tipos de Sinalização Semáforo FIFO Tipos de Sinalização Considerações A técnica utilizada no algoritmo anterior chamase passagem de condição O sinalizador implicitamente passa a condição de que s é positivo ao processo que ele acorda Pode ser usada sempre que procedimentos que usam wait e signal contêm ações complementares A sinalização preferida pelas linguagens e sistemas operacionais é a SC Tipos de Sinalização Considerações Semáforos x Monitores A operação wait sempre atrasa um processo ao passo que a operação P retarda um processo apenas se o valor do semáforo for igual a zero Diferentemente da operação V a operação signal não tem efeito se não há processo esperando Operação adicionais em variáveis condicionais Operação adicionais em variáveis condicionais Os processos são atrasados e despertados em ordem crescente de rank A operação signalallcv pode ser implementada através de várias chamadas a signalcv Ela é apenas bem definida quando o tipo de sinalização SC é utilizado Técnicas de Sincronização Problemas a serem abordados Buffers limitados Leitores e escritores Alocação Shortestjobnext Temporizador de Intervalo Barbeiro dorminhoco Buffers limitados Forma de garantir que a condição desejada seja sempre verdadeira Buffers limitados Código principal BoundedBuffer bb process Produceri1 to n TypeT data while true data bbdepositdata process Consummeri1 to n TypeT data null while true bbfetchdata Leitores e Escritores Podese encapsular normalmente o acesso ao database em um monitor O monitor é apenas utilizado para sincronizar o acesso ao database através das seguintes operações requestread requestwrite releaseread releasewrite monitor RWController int nr 0 nw 0 nr 0 nw 0 nw 1 cond oktoread signaled when nw 0 cond oktowrite signaled when nr 0 and nw 0 procedure requestread while nw 0 waitoktoread nr nr 1 procedure releaseread nr nr 1 if nr 0 signaloktowrite awaken one writer procedure requestwrite while nr 0 nw 0 waitoktowrite nw nw 1 procedure releasewrite nw nw 1 awaken one writer and signaloktowrite signalalloktoread all readers Leitores e Escritores Código principal RWController c process Readeri1 to n while true crequestread Lê a base de dados creleaseread process Writeri1 to n while true crequestwrite Escreve na base de dados creleasewrite Alocação shortjobnext Solução utilizando Monitor Alocação shortjobnext Considerações Utiliza a técnica de passagem de condição As ações complementares são free false no procedimento request free true no procedimento release Temporizador de intervalo Problema de projetar um temporizador que permite que um processo durma por um determinado período de tempo Duas soluções serão abordadas Espera com prioridade Condição de cobertura Temporizador de intervalo Recurso compartilhado clock lógico Duas operações envolvidas delayinterval Faz o processo dormir pelo intervalo passado parâmetro tick Incrementa o valor do clock lógico Temporizador de intervalo Solução usando Condição de Cobertura Temporizador de intervalo Solução usando Condição de Cobertura Processos de aplicação chamam delayinterval onde interval é um inteiro não negativo A operação tick é chamada por um processo que é periodicamente acordado por um timer implementado em hardware Com a técnica de condição de cobertura evita se que sejam criadas várias variáveis de condição Temporizador de intervalo Solução usando Condição de Cobertura Ela consiste em utilizar uma única variável de condição que cobre as condições específicas de todos os processos envolvidos Solução não eficiente para este problema em particular O custo dos falsos alarmes degrada a performance do sistema Temporizador de intervalo Solução usando Espera com Prioridade Temporizador de intervalo Solução usando Espera com Prioridade Espera com Prioridade pode ser usada sempre que existe uma ordem estática entre as condições que fazem os processos esperarem Deve ser a primeira escolha sendo seguida pela Condição de Cobertura e pela utilização de várias variáveis de condição Barbeiro dorminhoco Descrição do problema Em uma cidade pacata existe uma pequena e singela barbearia que possui duas portas e poucas cadeiras Os clientes entram por uma porta e saem pela outra Uma vez que a barbearia é pequena no máximo um cliente ou o barbeiro pode se locomover em determinado instante O barbeiro passa a vida servindo os clientes Quando não há cliente no seu empreendimento ele dorme em sua cadeira Quando um cliente chega e encontra o barbeiro dormindo ele o acorda senta em sua cadeira e dorme enquanto o barbeiro corta seu cabelo Caso o barbeiro esteja ocupado quando um cliente chega o cliente se põe a cochilar em uma das cadeiras de espera Após realizar seu trabalho o barbeiro abre a porta de saída para o cliente e a fecha assim que ele sai Se há clientes esperando o barbeiro acorda um deles e espera que ele sente em sua cadeira Caso contrário o barbeiro dormirá até que um novo cliente chegue Barbeiro dorminhoco Ilustração Entrance Barber Customer Exit Waiting customer Waiting customer Barbeiro dorminhoco Relação do tipo clienteservidor Três procedimentos básicos gethaircut Solicitação de corte de cabelo getnextcostumer Espera por um cliente sentar na cadeira do barbeiro e corta seu cabelo finishedcut Permite o cliente sair da barbearia Barbeiro dorminhoco O barbeiro e os clientes passam por uma série de estágios a partir do encontro inicial Clientes Sentar na cadeira do barbeiro Sair da barbearia Barbeiro Tornarse disponível Cortar o cabelo Finalizar o corte Barbeiro dorminhoco Especificação de contadores para sincronização E1 cinchair cleave bavail bbusy bdone E2 cinchair bavail bbusy cinchair Barbeiro dorminhoco O problema do uso de contadores é a falta de limite máximo para eles Podese evitálo caso seja encontrada uma relação entre os contadores Obs Eles apenas podem assumir os valores 0 ou 1 barber bavail cinchair chair cinchair bbusy open bdone cleave Barbeiro dorminhoco Definidos os contadores falta apenas encontrar as condições de sincronização Clientes precisam esperar até que o barbeiro fique disponível Clientes esperam até que o barbeiro abra a porta de saída Barbeiro espera um cliente chegar Barbeiro espera o cliente sair monitor BarberShop int barber 0 chair 0 open 0 cond barberavailable signaled when barber 0 cond chairoccupied signaled when chair 0 cond dooropen signaled when open 0 cond customerleft signaled when open 0 procedure gethaircut while barber 0 waitbarberavailable barber barber 1 chair chair 1 signalchairoccupied while open 0 waitdooropen open open 1 signalcustomerleft procedure getnextcustomer barber barber 1 signalbarberavailable while chair 0 waitchairoccupied chair chair 1 procedure finishedcut open open 1 signaldooropen while open 0 waitcustomerleft Monitores em C template class F struct FunctionType template class R class Object class Args struct FunctionTypeR ObjectArgs typedef R returntype template class R class Object class Args struct FunctionTypeR ObjectArgs const typedef R returntype Monitores em C template class Object class Monitor public typedef Object objecttype template class F class Args typename FunctionTypeFreturntype operationconst F f Args args criticalsection cs return objectfargs template class F class Args typename FunctionTypeFreturntype operationconst F f Args args const criticalsection cs return objectfargs private objecttype object class criticalsection Monitores em C Monitorstdvectorint v voperationvoid stdvectorintconst int stdvectorintpushback 1 voperationvoid stdvectorintconst int stdvectorintpushback 2 size voperationstdvectorintsize stdcout size stdendl Monitores em C template class F struct FunctionType template class R class Object struct FunctionTypeR Object typedef R returntype template class R class Object struct FunctionTypeR Object const typedef R returntype template class R class Object class Arg1 struct FunctionTypeR ObjectArg1 typedef R returntype template class R class Object class Arg1 struct FunctionTypeR ObjectArg1 const typedef R returntype template class R class Object class Arg1 class Arg2 struct FunctionTypeR ObjectArg1Arg2 typedef R returntype template class R class Object class Arg1 class Arg2 struct FunctionTypeR ObjectArg1Arg2 const typedef R returntype Monitores em C template class Object class Monitor public typedef Object objecttype template class F typename FunctionTypeFreturntype operationconst F f criticalsection cs return objectf template class F typename FunctionTypeFreturntype operationconst F f const criticalsection cs return objectf template class F class Arg1 typename FunctionTypeFreturntype operationconst F f Arg1 arg1 criticalsection cs return objectfarg1 Monitores em C template class F class Arg1 typename FunctionTypeFreturntype operationconst F f Arg1 arg1 const criticalsection cs return objectfarg1 template class F class Arg1 class Arg2 typename FunctionTypeFreturntype operationconst F f Arg1 arg1 Arg2 arg2 criticalsection cs return objectfarg1 arg2 template class F class Arg1 class Arg2 typename FunctionTypeFreturntype operationconst F f Arg1 arg1 Arg2 arg2 const criticalsection cs return objectfarg1 arg2 private objecttype object class criticalsection Monitores em C class A void F ScopedLock lm Void G ScopedLock lm mutex m Monitores em C Void G ScopedLock lm F DEADLOCK Monitores em C Qt Biblioteca de threads própria Monitores em C class BankAccount public BankAccount balance 0 void withdrawint amount QMutexLocker lockermutex balance amount void depositint amount QMutexLocker lockermutex balance amount private QMutex mutex int balance Monitores em C monitor BankAccount public BankAccount balance 0 void withdrawuint amount while amount balance waitmoreMoney balance amount void deposituint amount balance amount signalAllmoreMoney private cond moreMoney uint balance Monitores em C class BankAccount public BankAccount balance 0 void withdrawuint amount QMutexLocker lockermutex while amount balance moreMoneywaitmutex balance amount void deposituint amount QMutexLocker lockermutex balance amount moreMoneywakeAll private QMutex mutex QWaitCondition moreMoney uint balance Monitores em C monitor BoundedBuffer public BoundedBuffer head 0 tail 0 void putchar ch while tail head N waitbufferIsNotFull buffertail N ch signalbufferIsNotEmpty char get while head tail waitbufferIsNotEmpty char ch bufferhead N signalbufferIsNotFull return ch Monitores em C private cond bufferIsNotFull cond bufferIsNotEmpty int head tail char bufferN Monitores em C Monitores em C class BoundedBuffer public BoundedBuffer head 0 tail 0 void putchar ch QMutexLocker lockermutex while tail head N bufferIsNotFullwaitmutex buffertail N ch bufferIsNotEmptywakeOne char get QMutexLocker lockermutex while head tail bufferIsNotEmptywaitmutex char ch bufferhead N bufferIsNotFullwakeOne return ch Monitores em C private QMutex mutex QWaitCondition bufferIsNotFull QWaitCondition bufferIsNotEmpty int head tail char bufferN Monitores em Java Métodos Sincronizados class Interfere private int data 0 public void update data class Interfere private int data 0 public void synchronized update data class Interfere private int data 0 public void update synchronized this data Monitores em Java Métodos Sincronizados Implementam a exclusão mútua As variáveis permanentes são os campos privados e os procedimentos dos monitores são os métodos sincronizados Existe apenas um lock por objeto Java suporta sincronização condicional através dos métodos wait notify e notifyAll Esses métodos devem ser executados dentro porções de código sincronizadas Monitores em Java Métodos Sincronizados Java utiliza uma fila de espera por objeto Geralmente é FIFO mas não necessariamente A thread que chama notify continua com a posse do lock do objeto Utiliza o tipo de sincronização Sinalizar e Continuar Chamadas aninhadas a métodos sincronizados podem levar a um deadlock Monitores em Java Leitores e Escritores class Main public static void mainString args ReadersWriters rw new ReadersWrites Reader readers new Reader10 Writer writers new Writer10 for int i0 i 10 i readeri new Readerrw writeri new Writerrw for int i0 i 10 i readeristart writeristart Código Principal class Reader extends Thread ReadersWriters rw public ReaderReadersWriters rw thisrw rw public void run while true rwread class Writer extends Thread ReadersWriters rw public WriterReadersWriters rw thisrw rw public void run while true rwwrite Leito r Escritor class ReadersWriters private int data 0 private int nr 0 private synchronized void startRead nr private synchronized void endRead nr if nr 0 notify public void read startRead Systemoutprintlnread data endRead public synchronized void write while nr 0 try wait catch InterruptedException ie return data Systemoutprintlnwrite data notify Código do Monitor Referências Notas de aula Prof Bruno Jefferson httpdocqtdigiacomqqqq21 monitorshtml httpcppguruwordpresscom 20090105cmonitorpattern