1 Linguagem de Programação IICarlos Eduardo Batista Centro de Informática - UFPB
2 Roteiro Introdução Sintaxe e Semântica Problemas ClássicosSeções Críticas Produtores e Consumidores Buffers limitados Jantar dos Filósofos Leitores e Escritores
3 Introdução Algoritmos que utilizam o mecanismo de espera ocupada são ineficientes na maioria dos programas concorrentes. Semáforos foram a primeira ferramenta para prover sincronização entre processos e é considerada uma das mais importantes. Incluídos em todas as bibliotecas voltadas à programação concorrente. Com exceção do cenário no qual o número de processos é igual ao número de processadores.
4 Introdução Podem ser implementados através de técnicas de espera ocupada ou via funcionalidades oferecidas pelos sistemas operacionais. Sua criação foi motivada pela maneira como o tráfego em uma ferrovia é sincronizado para evitar colisões. São utilizados para implementar exclusão mútua e sincronização condicional.
5 Sintaxe e Semântica P(s) (wait) e V(s) (signal) sem lock = 1;Semáforo é um tipo especial de variável compartilhada que é manipulada por duas operações atômicas. São elas: O valor de um semáforo é um inteiro não-negativo. Sua inicialização se assemelha com a inicialização de uma variável inteira. P(s) (wait) e V(s) (signal) sem lock = 1;
6 Sintaxe e semântica Operação wait ou P: Decrementa o valor do semáforo. Se o semáforo está com valor zero, o processo é posto para dormir. Operação signal ou V: Se o semáforo estiver com o valor zero e existir algum processo adormecido, um processo será acordado. Caso contrário, o valor do semáforo é incrementado. Advindas dos verbos holandeses proberen (testar), e verhogen (incrementar) no trabalho original de Dijkstra As operações de incrementar e decrementar devem ser operações atômicas, ou indivisíveis, ou seja, enquanto um processo estiver executando uma dessas duas operações, nenhum outro processo pode executar outra operação sob o mesmo semáforo, devendo esperar que o primeiro processo encerre a sua operação sob o semáforo. Essa obrigação evita condições de disputa entre vários processos
7 Sintaxe e semântica Inicialização(Semáforo S, Inteiro N){ S = N; }P(Semáforo S){ Se(S == 0) bloqueia_processo(); Senão S--; V(Semáforo S){ Se(S == 0 && existe_processo_bloqueado()) desbloqueia_processo(); S++;
8 Sintaxe e Semântica P(s):
9 Sintaxe e Semântica Um semáforo genérico é aquele que pode conter qualquer valor não-negativo. Semáforo binário apenas pode armazenar os valores 0(zero) e 1(um.) Os processos são despertados na mesma ordem em que são retardados quando executam a operação P(s).
10 Problemas Clássicos Semáforos têm suporte direto para a implementação de exclusão mútua e de sincronização condicional. Alguns problemas clássicos ilustram tal suporte e a importância da utilização dos semáforos. Seções Críticas Barreiras Produtores/Consumidores Buffers limitados
11 Seções Críticas: Exclusão MútuaSolução utilizando Locks
12 Seções Críticas: Exclusão MútuaSolução utilizando Semáforos
13 Barreiras: Sinalização de EventosA implementação de barreiras utilizando mecanismos de espera ocupada faz uso de variáveis compartilhadas que são setadas e resetadas quando chegam e deixam as barreiras. A implementação de barreiras através de semáforos consiste em utilizar um semáforo para cada flag de sincronização.
14 Barreiras: Sinalização de EventosSolução utilizando Semáforos Semáforos de sinalização. Sinalização de evento.
15 Barreiras: Sinalização de EventosSemáforos podem ser utilizados na implementação das barreiras borboleta e de disseminação, as quais suportam a execução de n processos. Um array de semáforos deve ser empregado para cada estágio da barreira. Em cada estágio, um processo i sinaliza sua chegada ao executar V(arrive[i]) e espera por um processo j ao invocar P(arrive[j]).
16 Produtores e ConsumidoresO processo de comunicação entre produtores e consumidores ocorre a partir das seguintes operações: Deposit Fetch Elas devem ser executadas de forma alternada, a fim de que as mensagens não sejam sobrescritas, nem recebidas mais de uma vez.
17 Produtores e ConsumidoresSolução utilizando o comando
18 Produtores e ConsumidoresSolução utilizando Semáforos
19 Produtores e ConsumidoresSolução utilizando Semáforos Os semáforos empty e full podem ser vistos como um único semáforo binário, dividido em dois. No máximo um tem o valor 1 em um dado instante. O semáforos que apresentam esse comportamento são denominados de Semáforos Binários Divididos (Split Binary Semaphore).
20 Buffers limitados SlotÉ comum produtores e consumidores trabalharem em rajadas com o intuito de aumentar a performance do programa concorrente. Para isso, necessita-se de um buffer com vários slots disponíveis para armazenamento. Slot
21 Buffers limitados O buffer pode ser representado por um array, uma lista encadeada ou uma outra estrutura de dados. Buffer como um array: Produtor(deposit) Consumidor(fetch) buf rear front buf[rear] = data; rear = (rear + 1) % n; result = buf[front]; front = (front + 1) % n;
22 Buffers limitados Solução utilizando Semáforos
23 Buffers limitados Solução utilizando SemáforosSemáforos funcionam como contadores de recursos (semáforo contador). Quando os processos não estão executando as operações deposit e fecht, a soma dos valores dos dois semáforos é igual ao número total de slots. Semáforos contadores de recurso são úteis quando processos competem por múltiplas unidades de um mesmo recurso.
24 Buffers limitados Vários produtores e consumidores
25 Buffers limitados Considerações Sempre que múltiplos tipos de sincronização são necessários para solucionar um mesmo problema, implemente-os separadamente e depois combine suas soluções.
26 Semáforos em C
27 Buffers limitados – Semáforos em C
28 Jantar dos Filósofos Descrição do problema Cinco filósofos estão sentados ao redor de uma mesa em forma de círculo. Cada filósofo passa sua vida pensando e comendo. No centro da mesa se encontra um prato de espaguete. Uma vez que o espaguete é longo e emaranhado, um filósofo precisa de dois garfos para comer. Infelizmente, eles dispõem de apenas cinco garfos. Um garfo é colocado entre um par de filósofos e foi acordado que cada filósofo pode apenas usar os garfos imediatamente à sua direita e à sua esquerda. O problema é escrever um programa que simule o comportamento dos filósofos. Dessa forma, ele deve evitar uma situação na qual todos os filósofos estão com fome, mas nenhum deles conseguem adquirir ambos os garfos (por exemplo, cada um segura um garfo e se recusa a liberá-lo). Os problemas de sincronização clássicos Jantar dos Filósofos e Leitores e Escritores ilustram a implementação da exclusão mútua seletiva.
29 Jantar dos Filósofos Ilustração
30 Jantar dos Filósofos process Philosopher[i = 1 to 4] { while (true) {Esboço da solução process Philosopher[i = 1 to 4] { while (true) { think; acquire forks; eat; release forks; }
31 Jantar dos Filósofos Solução utilizando Semáforos Cada garfo pode ser representado como um semáforo. As ações de pegar e liberar os garfos podem ser vistas como operações P(s) e V(s), respectivamente. Pelo menos um filósofo deve pegar os garfos em uma ordem diferente das dos demais. Uma condição necessária para o deadlock é a existência de uma espera circular.
32 Jantar dos Filósofos Solução utilizando semáforos
33 Jantar dos Filósofos #define N 5 #define LEFT(i) (i+N-1)%N#define RIGHT(i) (i+1)%N #define THINKING 0 #define HUNGRY 1 #define EATING 2 int state[N]; sema_t mutex; // = 1 sema_t Sem[N]; // = 0 void philosopher(int i) { while(TRUE) { think(); take_forks(i); eat(); put_forks(i); } void take_forks(int i) { sema_wait(&mutex); state[i] = HUNGRY; test(i); sema_post(&mutex); sema_wait(&Sem[i]);
34 Jantar dos Filósofos --- void put_forks(int i) { sema_wait(&mutex);state[i] = THINKING; test(LEFT); test(RIGHT); sema_post(&mutex); } void test(int i) if ( state[i] == HUNGRY && state[LEFT(i)]!=EATING && state[RIGHT(i)]!=EATING ) state[i] = EATING; sema_post(&Sem[i]);
35 Jantar dos Filósofos Exclusão Mútua SeletivaPares de processos competem entre si para acessar os garfos. Não há uma competição generalizada.
36 Leitores e Escritores Descrição do problema Dois tipos de processos (leitores e escritores) compartilham uma base de dados. Leitores executam transações que examinam registros da base de dados; escritores executam transações que examinam e atualizam a base. A base de dados está inicialmente em um estado consistente (isto é, os dados estão armazenados em um estado válido). Cada transação, se executada isoladamente, transforma a base de dados de um estado consistente para outro. Para evitar interferência entre as transações, processos escritores devem ter acesso exclusivo à base. Assumindo que nenhum escritor está acessando à base de dados, qualquer número de leitores concorrentemente executar transações.
37 Leitores e Escritores Duas abordagens são empregadas na solução do problema. Encarado como um problema de Exclusão Mútua. Considerado como um problema de Sincronização Condicional. Utiliza a técnica “Passagem de Bastão”.
38 Leitores/Escritores como um problema de Exclusão MútuaSolução intermediária (overconstrained)
39 Leitores/Escritores como um problema de Exclusão MútuaEsboço da Solução
40 Leitores/Escritores como um problema de Exclusão MútuaSolução utilizando Semáforos
41
42 Leitores/Escritores como um problema de Exclusão MútuaSolução utilizando Semáforos Dá-se prioridade aos leitores em detrimento dos escritores. Um contínuo fluxo de leitores pode impossibilitar os escritores de acessarem a base de dados. Solução não justa.
43 Leitores/Escritores usando Sincronização CondicionalUtilizando sincronização condicional, pode-se evitar que os processos escritores entrem em um estado de starvation. A ideia é utilizar contadores que registram o número de processos leitores e escritores tentando acessar a base de dados.
44 Leitores/Escritores usando Sincronização CondicionalEstado a ser evitado Estado desejado Onde, nr: número de leitores acessando a base; nw: número de escritores acessando a base. (nr > 0 ^ nw > 0) v (nw > 1) (nr == 0 v nw == 0) ^ (nw <= 1)
45 Leitores/Escritores usando Sincronização CondicionalSolução utilizando comandos
46 Leitores/Escritores usando Sincronização CondicionalTécnica de Passagem de Bastão Em geral, comandos
47 Leitores/Escritores usando Sincronização CondicionalTécnica de Passagem de Bastão Algoritmo Substituir o ‘<‘ (menor) por uma operação p(e) em um semáforo que controlará o acesso nos protocolos de entrada. Verificar a condição para fazer o processo dormir através de um if e implementar as instruções para alcançar tal finalidade. Incrementar o número de processos atrasados. Liberar a entrada através da operação v(e). Fazer o processo dormir através da operação p(). Incrementar as instruções necessárias quando o processo não satisfaz as condições para dormir. Despertar um processo vinculado a um dos semáforos utilizados (passar o bastão).
48 Leitores/Escritores usando Sincronização CondicionalSolução utilizando a Técnica de Passagem de Bastão if (dr>0) { dr--; v(r);} else v(e); Processo Leitor if (nr==0 and dw>0) { dw--; v(w); } else v(e);
49 Leitores/Escritores usando Sincronização CondicionalSolução utilizando a Técnica de Passagem de Bastão v(e); Processo Escritor if (dr>0) { dr--; v(r);} else if (dw>0) {dw--; v(w);} else v(e);
50 Leitores/Escritores usando Sincronização CondicionalTécnica de Passagem de Bastão Código SIGNAL if (nw == 0 and dr > 0) { # acorda o leitor dr = dr – 1; V(r); } elseif (nr == 0 and nw == 0 and dw > 0) { # acorda o escritor dw = dw – 1; V(w); } else { # libera o lock de entrada V(e); }
51 Leitores/Escritores usando Sincronização CondicionalTécnica de Passagem de Bastão Os três semáforos utilizados formam um Semáforo Binário Dividido, pois no máximo um deles é 1 (um) em um determinado instante. Quando um processo alcança o código SIGNAL, ele “passa o bastão” para outro processo que está esperando por uma condição que agora é verdadeira. Algumas linhas do código SIGNAL podem ser eliminadas ou simplificadas, dependendo do local onde ele está sendo empregado.
52 Políticas de escalonamento alternativasA solução baseada na técnica de Passagem de Bastão permite a implementação de políticas de escalonamento alternativas. Condições de guarda podem ser manipuladas de modo a alterar a ordem em que os processos são acordados sem afetar a corretude da solução.
53 Políticas de escalonamento alternativasExemplos Atrasar novos leitores quando um escritor está esperando. Acordar um leitor apenas se não houver escritor esperando. if (nw > 0 or dw > 0) {dr = dr + 1; V(e); P(r)} if (dw > 0) { dw = dw – 1; V(w); } elseif (dr > 0) { dr = dr – 1; V(r); } else V(e);
54 Escalonamento e alocação de recursosProblema de decidir qual processo poderá acessar um recurso em um determinado momento. Um recurso pode ser entendido como um componente de hardware (ex.: impressora) ou de software (ex.: entrada de uma seção crítica, slot de um buffer limitado). As soluções dos problemas anteriores não especificam qual processo em particular terá acesso à seção crítica em determinado momento. Quando o acesso é liberado através de um protocolo de saída, há uma competição entre os processos que estão aguardando pelo recurso, haja vista a inexistência de uma regra que determina qual processo específico poderá progredir. Esta seção mostra como controlar explicitamente qual processo adquirirá o recurso em determinado momento.
55 Escalonamento e alocação de recursosComo controlar explicitamente qual processo particular acessará o recurso quando há uma disputa entre vários processos?
56 Escalonamento e alocação de recursosDefinição do problema e a solução padrão Processos competem por unidades de recursos, cujas solicitações e liberações são realizadas pelas operações request e release.
57 Escalonamento e alocação de recursosDefinição do problema e a solução padrão A solução padrão, implementada através da técnica de Passagem de Bastão, tem a seguinte estrutura: request(params) { P(e); if (solicitação não pode ser atendida) DELAY; aloca unidades; SIGNAL; } release(params) { P(e); return unidades; SIGNAL; }
58 Escalonamento e alocação de recursosAlocação Shortest-Job-Next Vários processos competem por um único recurso compartilhado. Um recurso é solicitado através de uma operação request(time, id), onde: time especifica o tempo de utilização do recurso. id é identificador do processo. Se o recurso estiver disponível, ele é alocado para o processo com o menor valor de time. Caso haja um empate no valor de time, adquire o recurso o processo que está esperando há mais tempo. Menor job primeiro (Shortest Job First). Ex. de utilização: alocação de processador, spooling de impressoras e transferência de arquivos utilizando ftp.
59 Escalonamento e alocação de recursosAlocação Shortest-Job-Next Vantagem Minimiza o tempo médio de finalização de jobs. Desvantagem Política injusta. Um processo pode ficar esperando para sempre, caso haja um contínuo fluxo de solicitações especificando menores tempos de utilização de recursos. Na prática, a situação na qual um processo espera indefinidamente raramente ocorre. Pode ser facilmente modificada para resolver o problema da injustiça.
60 Escalonamento e alocação de recursosAlocação Shortest-Job-Next Princípios para sua implementação Se um processo faz uma solicitação por um recurso que se encontra livre e não há solicitações pendentes, o processo deve ser imediatamente atendido. Uma variável booleana pode controlar esta situação. Solicitações pendentes precisam ser lembradas e ordenadas. Solução: um array com elementos ordenados pelo campo time. Na prática, a situação na qual um processo espera indefinidamente raramente ocorre. Pode ser facilmente modificada para resolver o problema da injustiça.
61 Escalonamento e alocação de recursosAlocação Shortest-Job-Next Princípios para sua implementação Um processo somente consegue enxergar que o recurso está livre se a lista de solicitações estiver vazia. Na prática, a situação na qual um processo espera indefinidamente raramente ocorre. Pode ser facilmente modificada para resolver o problema da injustiça.
62 Escalonamento e alocação de recursosAlocação Shortest-Job-Next Esboço da solução Como implementar DELAY e SIGNAL? request(time, id) { P(e); if (!free) DELAY; free = false; SIGNAL; } release() { P(e); free = true; SIGNAL; }
63 Escalonamento e alocação de recursosSolução
64 Escalonamento e alocação de recursosAlocação Shortest-Job-Next Cada processo possui uma condição de delay diferente. O primeiro processo do conjunto pairs precisa ser despertado antes do segundo e assim sucessivamente. Semáforos privados são utilizados em situações nas quais necessita-se sinalizar processos individualmente. Semáforo privado: Um semáforo s é denominado de privado se apenas um processo executa uma operação P sobre ele. O primeiro processo do conjunto Pairs precisa ser despertado antes do segundo e assim sucessivamente.
65 Referências BibliográficasAndrews, G. Foundations of Multithreaded, Parallel, and Distributed Programming. Addison-Wesley, 2000. Notas de aula do Prof. Bruno Jefferson
66 Referências Notas de Aula do Prof. Bruno PessoaNotas de aula – Claudio Esperança e Paulo Cavalcanti (UFRJ) Notas de aula – Allan Lima (citi/UFPE) Notas de aula – Markus Endler (PUC-Rio) c++0x-part-1-starting-threads.html