Módulo 5 - pag. 1 Alexandre Sztajnberg @ 2001 Sistemas Operacionais Programação concorrente

Módulo 5 - pag. 1Alexandre Sztajnberg @ 2001

Sistemas Operacionais

Programação concorrente


Monoprogramação apenas um programa executando

Multiprogramação vários programas podem executar

Monoprogramação apenas um programa executando

Multiprogramação vários programas podem executar

Monousuário apenas um usuário

Multiusuário vários usuários podem utilizar

Monousuário apenas um usuário

Multiusuário vários usuários podem utilizar

Conceitos


Multitarefa » programa pode ser implementado por várias tarefas » processo · uma tarefa · multitarefa

Multitarefa » programa pode ser implementado por várias tarefas » processo · uma tarefa · multitarefa

Multiprocessado » vários processadores Multiprocessado » vários processadores

Núcleo (kernel) X Micronúcleo (microkernel) Núcleo (kernel) X Micronúcleo (microkernel)

Conceitos


E/S

CPU

tempo

monomono

livre11 11

11

Sistemas Multiprogramados

E/S

CPU

tempomultimulti

livre11 11

11

22

• concorrência– princípio do intercalamento– maior utilização da CPU

• concorrência– princípio do intercalamento– maior utilização da CPU


Programação Concorrente

primeiros conceitos

• explorar o paralelismo

• várias aplicações executadas compartilhando a mesma CPU

• aplicações estruturadas de forma que seus módulos podem ser executados concorrentemente

– sem interação

– com interação (compartilhando recursos)

• o SO pode (e precisa) utilizar esta técnica internamente

– “o SO pode ser visto como um grande monitor...”


Programação ConcorrenteHipóteses

• teórica– programas distribuídos

– funcionam em qualquer plataforma

– independe da velocidade de execução

• intercalamento no tempo– vários cenários de execução possíveis

– velocidade do PC de cada processo é independente

– não determinística

( o )o[ ]o( )o[ ]o( )o

o( )o[ ]o( )o[ ]o

execução e uma instruçãoPC e dados indefinidos

PC e dados definidosestáveis

a:=

a:=

a

PC1PC2


Especificação de Concorrência em Programas

• Linguagens:– Pascal Concorrente: cobegin - coend

– OOCAM

– ADA

• Unix:– fork

– wait

• Mecanismos para compartilhamento de Recursos

– memória compartilhada

– troca de mensagens


Interação entre Processos

• Processos (que compõem um mesmo programa ou não) podem precisar cooperar entre si

• Mecanismos para compartilhamento de Recursos

troca de mensagens

pedidopedido

respostarespostavariável_comum

Memória compartilhada


Problemas de Comunicação e Exclusão Mútua

• comunicação entre processos– IPC - Inter Process Communication

– implementação do compartilhamento de recursos

• problema: inconsistência nos dados compartilhados– solução: exclusão mútua e sincronização

– garantia de que algumas condições serão respeitadas na comunicação entre processos

• outros problemas– deadlock

– livelock

– starvation

– injustiça


Exclusão Mútua

• Requisitos– apenas um processo pode acessar a região crítica no

acesso a recursos compartilhados

– a entrada ou saída de processos competindo pelo mesmo recursos não deve influenciar outros processos

– ausência de deadlock ou starvation

– nada é assumido em relação à velocidade de execução dos processos nem ao número dos processos

– um processo não conhece implicitamente o estado de outro processo

» daí a necessidade de se garantir o sincronismo e a exclusão mútua


• uma abstração

• “área de segurança” para acesso à recursos compartilhados

• um processo desejando entrar na RC

– deve ser garantido ao processo a entrada na RC

– se a RC estiver livre, deve poder fazê-lo sem atrasos

• um processo só pode ficar na RC durante um período finito de tempo

program exclusão_mutua;const n = ...; { número de processos }

Begin cobegin P (1); P (2); ... P (n); coend End.

program exclusão_mutua;const n = ...; { número de processos }

Begin cobegin P (1); P (2); ... P (n); coend End.

procedure P (i : integer);Begin repeat <código restante> entra_reg_crítica (R); <código para a região crítica R> sai_reg_critica (R); <código restante> foreverEnd;

procedure P (i : integer);Begin repeat <código restante> entra_reg_crítica (R); <código para a região crítica R> sai_reg_critica (R); <código restante> foreverEnd;

Região CríticaRegião Crítica


Sincronização

• Velocidade de execução dos processos é diferente

– uso de buffers

– lê o que ainda não foi escrito

– inconsistência em banco de dados

– processos tem “visão” diferente de variáveis

» problemas semelhantes ao de cache


Exclusão Mútua - Soluções por Software

• algoritmo de Dekker– Djikstra

» propôs série de soluções evolutivas

» cada uma evidencia bugs comuns em programas concorrentes

• 1 - uma variável, buzy waiting

• 2 - duas variáveis

• 3 - 3 variáveis

• 4 - correta

• algoritmo de Peterson– garante exclusão mútua

– garante justiça para 2 processos


Primeira Tentativa• espera ocupada (busy-waiting) => while

• alternância explícita dos processos

• velocidade ditada pelo mais lento

• falhas na RC ?

...while turn <> 0 do { nothing };< região crítica >turn := 1;...


Processo 0



Processo 1

variável global compartilhada => turn: 0..1;variável global compartilhada => turn: 0..1;


Segunda Tentativa• cada processo tem sua própria chave para a RC

• cada processo vê o quadro de avisos do outro mas não pode alterá-lo

• não existe bloqueio se outro processo falha fora da RC (o mesmo não é garantido se este falha dentro da RC)

• existe falha grave no algoritmo (não garante exclusão mútua)

...while flag[ 1 ] do { nothing };flag[ 0 ] := true;< região crítica >flag[ 0 ] := false;...


Processo 0



Processo 1

variável global compartilhada => var flag: array [0..1] of boolean;variável global compartilhada => var flag: array [0..1] of boolean;


Terceira Tentativa• em relação à segunda tentativa, apenas uma mudança no

código

• garante exclusão mútua

• problemas de deadlock (os dois setam o respectivos flags para 1)

• cada processo pode setar o valor de seu flag sem saber da condição do outro

...flag[ 0 ] := true;while flag[ 1 ] do { nothing };< região crítica >flag[ 0 ] := false;...


Processo 0



Processo 1


flag[0] = flag[1] =

flag[0] = flag[1] = FALSE

FALSE

. flag[1] := true; while flag[0] do begin flag[1] := false; <delay for a short time>; flag[1] := true; end; < critical section >; flag[1] := false; .


Process 1 . flag[0] := true; while flag[1] do begin flag[0] := false; <delay for a short time>; flag[0] := true; end; < critical section >; flag[0] := false; .


Process 0

P1 sets flag [1] to true

TRUEP1 sets flag [1] to false FALSE

PO sets flag [0] to true

TRUEP0 sets flag [0] to false FALSE


TRUE

flag[0] := true; flag[1] := true;

flag[1] := false;

flag[0] := true;

flag[0] := false; flag[1] := false;

flag[1] := true;while flag[1] doflag[0] := true; flag[1] := true;flag[0] := true;

Quarta Tentativa• processos agora setam seu flag para indicar a intenção

• pode haver livelock (tracing abaixo) “mutual courtesy”

P0 checks flag [1]P1 checks flag [0]


TRUE

while flag[0] do

flag[0] := false;

while flag[1] do while flag[0] do


Solução Correta

• uso da variável turn

• as variáveis flag ainda são usadas

• algoritmo original de Dekker

• algoritmo complexo e de prova difícil


Algoritmo de Dekker

var flag: array [0 .. 1] of boolean; turn: 0 .. l;

var flag: array [0 .. 1] of boolean; turn: 0 .. l;

procedure P0;begin repeat flag [0] := true; while flag [1] do if turn = 1 then begin flag [O] := false; while turn = 1 do {nothing}; flag [0] := true end; < região crítica >; turn := 1; flag [0] := false; < restante > foreverend;

procedure Pl;begin repeat flag [1] := true; while flag [0] do if turn = 0 then begin flag [1] := false; while turn = 0 do {nothing}; flag [1] := true end; < região crítica >; turn := 0; flag [1] := false; < restante > foreverend; Begin

flag [0] := false; flag [1] := false; turn := 1; parbegin P0; P1 parendend.

Begin flag [0] := false; flag [1] := false; turn := 1; parbegin P0; P1 parendend.


Algoritmo de Petterson• garante exclusão mútua e justiça (para 2 processos ?)

• também usa flags (mutex) e turn (conflitos)

var flag array [0 ..1] of boolean; turn:0..1;

var flag array [0 ..1] of boolean; turn:0..1;

procedure P0;begin repeat flag [0] := true; turn := 1; while flag [1] and turn = 1 do {nothing}; < região crítica >; flag [0] := false; < restante > foreverend;

procedure Pl;begin repeat flag [1] := true; turn := 0; while flag [0] and turn = 0 do {nothing}; < região crítica >; flag [1] := false; < restante > foreverend; begin

flag [0] := false; flag [1] := false; turn := 1; parbegin P0; P1 parendend.

begin flag [0] := false; flag [1] := false; turn := 1; parbegin P0; P1 parendend.


Sincronização - Soluções por Hardware

• desabilitar interrupções

• instruções implementadas por hardware– test-and-set (atômicas)

– exchange

– protocolo de exclusão mútua

» ex.:• repeat { nothing } until testeset (variável);

» ex.:• repeat exchange (key_i, bolt) until key_i = 0;

– simples, vários processos, várias RCs

– espera ocupada, starvation, deadlock


Sincronização - Soluções por Software

Semáforos

• mecanismo proposto em 1967 por Dijkstra

• recurso acessado somente por funções específicas: wait e signal

• wait e signal são atômicos

• o semáforo deve ser compartilhados por todos os processos que vão utilizá-lo como mecanismo para exclusão mútua ou sincronização



• wait (sem) : s:= s - 1 – se sem >= 0 então processo prossegue

– se sem < 0 então processo é bloqueado na fila de espera K

• signal (sem) : s:= s + 1– se houver processo bloqueado na fila de espera, um deles é escolhido para

se desbloquear e prosseguir

• operações também chamadas de P e V por motivos históricos

0..N

wait (sem )

signal ( sem)

init ( sem)

Contador S

Fila K


• Definir um semáforo como um “record”:

• Oferecer duas operações simples:– “block” suspende o processo que a invocou.– “wakeup(P)” reinicia a execução de um processo “P”

bloqueado.

Implementação de semáforos:

type semaphore = record value: integer; L: list of process; end;


Implementação (Cont.)• As operações dos semáforos agora serão definidas como:

wait(S): S.value := S.value – 1;

if S.value < 0

then begin

adiciona esse processo à S.L;block;

end;

signal(S): S.value := S.value + 1;

if S.value 0

then begin

remove o processo P de S.L;wakeup(P);

end;


Dois tipos de semáforos

• Counting semaphore (semáforo contador) – valor inteiro que pode variar por uma faixa de valores sem restrição.

• Binary semaphore (semáforo binário) – valor inteiro que varia somente entre 0 e 1; pode ser simples de se implementar.

• Podemos implementar um semáforo contador como um semáforo binário.


Exemplos

• exclusão mútua

• sincronização– tarefa A espera em L1: até que tarefa B atinja ponto L2:

• situação de deadlock

sem := 1;...wait (sem);.seção crítica.signal (sem);...

sem := 1;...wait (sem);.seção crítica.signal (sem);...

Tarefa_A

prossiga := 0; ...L1: wait (prossiga); ...

Tarefa_A

prossiga := 0; ...L1: wait (prossiga); ...

Tarefa_B

...L2: signal (prossiga); ...

Tarefa_B

...L2: signal (prossiga); ...

Tarefa_A

...wait (x); ...wait (y); ...

Tarefa_A

...wait (x); ...wait (y); ...

Tarefa_B

...wait (y); ...wait (x); ...

Tarefa_B

...wait (y); ...wait (x); ...


Problema I: Produtores/Consumidores

• vários processos:– produtores

– consumidores

• cada processo tem seu ritmo (nada é assumido sobre o tempo de execução

• produtor– produz item e coloca em um buffer

• consumidor– pega item no buffer e consome

• buffer– infinitos

– finitos (circular)


Produtor/ConsumidorBuffer Ilimitado

• proposta da turma

• dica– consumidor só é liberado para pegar item depois que o

produtor colocar o item no buffer

– um semáforo

– um ponteiro para a posição do produtor na fila

– um ponteiro para a posição do consumidor na fila


0 1 2 3

Exemplos Bounded Buffer

Solução “Ad Hoc”

in out

task producer: loop ... produz um item em netxp ... while (in + 1) mod 3 = out do nothing; ... buffer [in] := nextp; in := (in + 1) mod 3;endloop;

task producer: loop ... produz um item em netxp ... while (in + 1) mod 3 = out do nothing; ... buffer [in] := nextp; in := (in + 1) mod 3;endloop; task consumer: loop

... while in = out do nothing; nextc := buffer [out]; out := (out + 1) mod 3; ... consome o item em netxp ...endloop;

task consumer: loop ... while in = out do nothing; nextc := buffer [out]; out := (out + 1) mod 3; ... consome o item em netxp ...endloop;

Begin in := 0; out := 0;endModule;

Begin in := 0; out := 0;endModule;

Module Example ( );type item : ...;var buffer: array [ 0..3 ] of item; in, out : 0..3; nextp, nextc: item;

Module Example ( );type item : ...;var buffer: array [ 0..3 ] of item; in, out : 0..3; nextp, nextc: item;

in in inout out outin out


Solução com semáforo de contagem

procedure Produtor;var

FimFila : (1..TamFila);V : tipDado;

beginFimFila := 1;repeat

Produzir (V);wait (Vaga);Fila [ FimFila ] := V;FimFila := (FimFila mod TamFila) + 1;signal (Item);

until Fim;end;

procedure Produtor;var

FimFila : (1..TamFila);V : tipDado;

beginFimFila := 1;repeat

Produzir (V);wait (Vaga);Fila [ FimFila ] := V;FimFila := (FimFila mod TamFila) + 1;signal (Item);

until Fim;end;

procedure Consumidor;var

IniFila : (1..TamFila);W : tipDado;

beginIniFila := 1;repeat

wait (Item);W := Fila [ IniFila ] ;IniFila := (IniFila mod TamFila) + 1;signal (Vaga);Consumir (W);

until Fim;end;

procedure Consumidor;var

IniFila : (1..TamFila);W : tipDado;

beginIniFila := 1;repeat

wait (Item);W := Fila [ IniFila ] ;IniFila := (IniFila mod TamFila) + 1;signal (Vaga);Consumir (W);

until Fim;end;

program BufferLimitado;const

TamFila = ...;var

Fila : array [1..TamFila] of TipDado;Item : semaphore;Vaga: semaphore;

program BufferLimitado;const

TamFila = ...;var

Fila : array [1..TamFila] of TipDado;Item : semaphore;Vaga: semaphore;

BeginInitSem (Item, 0);InitSem (Vaga, TamFila);cobegin

Produtor; Consumidor;coend;

End.

BeginInitSem (Item, 0);InitSem (Vaga, TamFila);cobegin

Produtor; Consumidor;coend;

End.


Exemplos Bounded Buffer

Solução com Semáforos

Module Example;type item : ...;var buffer: array [0.. n-1] of item; full, empty, mutex: semaphore; nextp, nextc: item; pontP, pontC: ponteiros;

Module Example;type item : ...;var buffer: array [0.. n-1] of item; full, empty, mutex: semaphore; nextp, nextc: item; pontP, pontC: ponteiros;

task consumer: loop ... wait (full); wait (mutex); ... remove um item do buffer ajusta pontC ... signal (mutex); signal (empty); ... consome o item em netxpendloop;

task consumer: loop ... wait (full); wait (mutex); ... remove um item do buffer ajusta pontC ... signal (mutex); signal (empty); ... consome o item em netxpendloop;

funciona paraqualquer estruturade dados para o buffer

•mutex: exclusão mútua•full > 0 existe algum item produzido•empty > 0 existe espaço vazio no buffer

task producer: loop produz um item em netxp ... wait (empty); wait (mutex); ... adiciona nextp ao buffer; ajusta PontP; ... signal (mutex); signal (full);endloop;

task producer: loop produz um item em netxp ... wait (empty); wait (mutex); ... adiciona nextp ao buffer; ajusta PontP; ... signal (mutex); signal (full);endloop;

Begin full := 0; pontC = 0; empty := n; pontP = 0; mutex := 1;endModule;

Begin full := 0; pontC = 0; empty := n; pontP = 0; mutex := 1;endModule;



• Brich Hansen e Hoare

• Monitores– solução estruturada

– concentra partes críticas de sincronização

– funções e procedimentos declarados pelo programador estão protegidas e encapsuladas dentro do monitor

– além das funções o monitor encapsula dados

– procedimentos dentro do monitor são executados em exclusão mútua

– o monitor possui uma fila (FIFO) de entrada onde, processos desejando executar um procedimento do monitor, aguardam sua vez


Monitores: programação• Variável de Condição (um tipo primitivo dos monitores,

na verdade são os nomes de uma fila FIFO)

• dois procedimentos e uma função atuam sobre a variável de condição

– wait (condição)

» processo é suspenso e vai para o fim da fila “condição”

– signal (condição)

» primeiro processo suspenso na fila “condição” retorna a sua execução

– NonEmpty (condição)

» TRUE se a fila “condição” não estiver vazia

• semântica das funções wait e signal dos monitores é diferente do semáforo (não tem memória)


processos só temacesso aos procedimentosdo monitor

processos só temacesso aos procedimentosdo monitor

processos na pilha têmprioridade sobre osnovos

processos na pilha têmprioridade sobre osnovos

saída domonitor

fila de entrada no monitor

Quintal da PilhaQuintal da Pilha

topo...

Procedimentos do MonitorProcedimentos do Monitor

P1 PnP2 P3 ...

Quintal das filas de condiçõesQuintal das filas de condições

.. . .. . .. .

C1 C2 C3

Monitor

signal (C2)

wait (C1)


Monitores: Interface de Programação

monitor exemplo;< declara variáveis locais ao monitor>;

procedure entry proc_name_1;Begin

<corpo do procedimento 1>End;procedure entry proc_name_2;Begin

<corpo do procedimento 2>;End;...Begin

< inicialização das variáveis do monitor >;End exemplo;


Produtores/Consumidores com Monitor

Produtores/Consumidores com Monitor

• encapsulamento

• exclusão mútua

Tarefa produtor:bounded_buffer.insert (p);

Tarefa consumidor:bounded_buffer.remove (p);

var buf: array [1..n] of item;in, out, count: integer;a_buf_is_full, a_buf_is_empty: condition;

monitor bounded_buffer (n: integer);

beginin := 0;out := 0;a_buf_is_empty := true;a_buf_is_full := false;count := 0;

end;

beginin := 0;out := 0;a_buf_is_empty := true;a_buf_is_full := false;count := 0;

end;

Inicialização

beginif count = n then a_buf_is_empty.wait;buf [in] := it;in := (in mod n) + 1;count := count + 1;a_buf_is_full.signal;

end;

beginif count = n then a_buf_is_empty.wait;buf [in] := it;in := (in mod n) + 1;count := count + 1;a_buf_is_full.signal;

end;

proc entry insert (it: item);

beginif count = 0 then a_buf_is_full.wait;it := buf [out];out := (out mod n) + 1;count := count -1;a_buf_is_empty.signal;

end;

beginif count = 0 then a_buf_is_full.wait;it := buf [out];out := (out mod n) + 1;count := count -1;a_buf_is_empty.signal;

end;

proc entry remove (it: item);


Monitores e Semáforos

• podemos simular semáforos do tipo FIFO com monitores

– exercício para turma

• podemos construir um monitor com semáforos


Barbeiro DorminhocoBarbeiro Dorminhoco


Leitores e Escritores• vários processos escritores e leitores competindo por um

recurso comum

• O acesso ao recurso comum por um escritor deve ser feito em exclusão mútua

• entre leitores, exclusão mútua não é exigida• se há um escritor escrevendo, escritores esperando para escrever e

leitores esperando para ler» o primeiro escritor na fila não começará a a escrever até que todos os

leitores que estiverem esperando o escritor escrever tenham acabado de ler

» se há leitores lendo

– chega primeiro um escritor para esperar para escrever

– novos leitores que chegarem ficarão suspensos

• se há leitores lendo, escritores esperando e leitores esperando– todos os leitores esperando para ler não vão começar a ler até que o

primeiro escritor que está esperando para escrever acabe de escrever


Escr/Leit: monitor

procedure Leitor; begin repeat ComecarALer; LerDado; AcabarDeLer; ConsumirDado; until false;end; procedure Escritor;begin repeat ProduzirDado; ComecarAEscrever; EscreverDado; AcabarDeEscrever; until false;end;

Begin cobegin Leitorl ; Escritorl; ...; coend;end.

program LeitoresEscritores;

monitor MonitorLeitoresEscritores;var Leitores : integer; Escrevendo : boolean; PodeLer, PodeEscrever : condition;

procedure ComecarALer;begin if (Escrevendo or NonEmpty(PodeEscrever)) then wait(PodeLer); Leitores:=Leitores+l; signal (PodeLer);end;

procedure AcabarDeLer;begin Leitores:=Leitores-1; if Leitores=0 then signal(PodeEscrever);end;

procedure ComecarAEscrever;begin if ((Leitores<>0) or Escrevendo) then wait(PodeEscrever); Escrevendo:=true;end;

procedure AcabarDeEscrever;begin escrevendo := false; if NonEmpty(PodeLer) then signal(PodeLer) else signal (PodeEscrever);end;

begin Leitores:=0; Escrevendo:=false; end;


Sincronização

• Troca de Mensagens

• send / receive

• endereçamento– direto

– caixa postal

• API– System V IPC Messages

– sockets

– RPC

– CORBA


Verificação de Programas Concorrentes

• Provas formais de corretude

• lógica temporal

• linguagens que permitem verificações formais de propriedades

– ADA (Rendevouz)

– CCS

– CSP

– Estelle

– Lotus

– Redes de Petri

– Pi Calculus


• problema clássico de exclusão mútua

• filósofos pensam e comem em um tempo arbitrário

• para comer: 2 pauzinhos

• evitar– starvation (esfomeação)

– deadlock

• soluções– semáforo

– monitor

Problema dos FilósofosProblema dos Filósofos

Documents

Módulo 5 - pag. 1 Alexandre Sztajnberg @ 2001 Sistemas Operacionais Programação concorrente