34
Sem´ aforos Barreiras Tentativas do livro Barreiras restritas Futex glibc opicos em Sistemas Operacionais Sem´ aforos e Barreiras Islene Calciolari Garcia Instituto de Computa¸c˜ ao - Unicamp Segundo Semestre de 2013

T opicos em Sistemas Operacionais - ic.unicamp.brislene/2s2013-mo806/sem-barreiras/sem-barreiras.pdf- sem_post should only wake one thread and only when the state of the semaphore

  • Upload
    donga

  • View
    218

  • Download
    0

Embed Size (px)

Citation preview

Page 1: T opicos em Sistemas Operacionais - ic.unicamp.brislene/2s2013-mo806/sem-barreiras/sem-barreiras.pdf- sem_post should only wake one thread and only when the state of the semaphore

Semaforos Barreiras Tentativas do livro Barreiras restritas Futex glibc

Topicos em SistemasOperacionais

Semaforos e Barreiras

Islene Calciolari Garcia

Instituto de Computacao - Unicamp

Segundo Semestre de 2013

Page 2: T opicos em Sistemas Operacionais - ic.unicamp.brislene/2s2013-mo806/sem-barreiras/sem-barreiras.pdf- sem_post should only wake one thread and only when the state of the semaphore

Semaforos Barreiras Tentativas do livro Barreiras restritas Futex glibc

Semaforos

Semaforos sao contadores especiais para recursoscompartilhados.

Proposto por Dijkstra (1965)

Operacoes basicas (atomicas):

decremento (down, wait ou P)bloqueia se o contador for nuloincremento (up, signal (post) ou V)nunca bloqueia

Page 3: T opicos em Sistemas Operacionais - ic.unicamp.brislene/2s2013-mo806/sem-barreiras/sem-barreiras.pdf- sem_post should only wake one thread and only when the state of the semaphore

Semaforos Barreiras Tentativas do livro Barreiras restritas Futex glibc

SemaforosComportamento basico

sem init(s, 5)

wait(s)

if (s == 0)bloqueia_processo();

else s--;

signal(s)

if (s == 0 && existe processo bloqueado)acorda_processo();

else s++;

Veja a implementacao da glic: sem wait.c e sem post.c

Page 4: T opicos em Sistemas Operacionais - ic.unicamp.brislene/2s2013-mo806/sem-barreiras/sem-barreiras.pdf- sem_post should only wake one thread and only when the state of the semaphore

Semaforos Barreiras Tentativas do livro Barreiras restritas Futex glibc

glibc: TODO

- semaphore changes:

- sem_post should only wake one thread and only whenthe state of the semaphore changed from 0 to 1.this also requires that sem_wait and sem_timedwaitdon’t drop the post if they get canceled.

- possibly add counter field. This requires revivingthe differences between old and new semaphose funtions.The old ones stay as they are now. The new once canuse an additional field wich is the counter for thenumber of waiters

Page 5: T opicos em Sistemas Operacionais - ic.unicamp.brislene/2s2013-mo806/sem-barreiras/sem-barreiras.pdf- sem_post should only wake one thread and only when the state of the semaphore

Semaforos Barreiras Tentativas do livro Barreiras restritas Futex glibc

glibc: TODOSera que e uma boa abordagem?

- semaphore changes:

- sem_post should only wake one thread and only whenthe state of the semaphore changed from 0 to 1.

Considere o seguinte cenario:

3 threads estao aguardando na fila do futex

2 threads incrementam o contador (0-¿1 e 1-¿2) antes de aprimeira thread na espera decrementar o contador

apenas 1 thread seria acordada

Page 6: T opicos em Sistemas Operacionais - ic.unicamp.brislene/2s2013-mo806/sem-barreiras/sem-barreiras.pdf- sem_post should only wake one thread and only when the state of the semaphore

Semaforos Barreiras Tentativas do livro Barreiras restritas Futex glibc

O ponto de encontro das threadsAguardando N threads

Page 7: T opicos em Sistemas Operacionais - ic.unicamp.brislene/2s2013-mo806/sem-barreiras/sem-barreiras.pdf- sem_post should only wake one thread and only when the state of the semaphore

Semaforos Barreiras Tentativas do livro Barreiras restritas Futex glibc

O ponto de encontro das threadsN threads na barreira

Page 8: T opicos em Sistemas Operacionais - ic.unicamp.brislene/2s2013-mo806/sem-barreiras/sem-barreiras.pdf- sem_post should only wake one thread and only when the state of the semaphore

Semaforos Barreiras Tentativas do livro Barreiras restritas Futex glibc

O ponto de encontro dos threadsThreads devem prosseguir

Page 9: T opicos em Sistemas Operacionais - ic.unicamp.brislene/2s2013-mo806/sem-barreiras/sem-barreiras.pdf- sem_post should only wake one thread and only when the state of the semaphore

Semaforos Barreiras Tentativas do livro Barreiras restritas Futex glibc

O ponto de encontro das threadsNenhuma thread pode ficar presa

Page 10: T opicos em Sistemas Operacionais - ic.unicamp.brislene/2s2013-mo806/sem-barreiras/sem-barreiras.pdf- sem_post should only wake one thread and only when the state of the semaphore

Semaforos Barreiras Tentativas do livro Barreiras restritas Futex glibc

O ponto de encontro das threadsVamos implementar?

Grupo de N threads

Vida monotona

Trabalham eSincronizam

Varios exemplos retirados do livro The Little Book ofSemaphores

E possıvel ser mais eficiente?

Page 11: T opicos em Sistemas Operacionais - ic.unicamp.brislene/2s2013-mo806/sem-barreiras/sem-barreiras.pdf- sem_post should only wake one thread and only when the state of the semaphore

Semaforos Barreiras Tentativas do livro Barreiras restritas Futex glibc

Primeira tentativa (3.4)

int c;sem barreira = 0;atomic inc(c);if (c == N) sem_post(barreira);sem_wait(barreira);

Quais sao os problemas deste codigo?

Quando funciona?

Veja o arquivo barreira1.c

Page 12: T opicos em Sistemas Operacionais - ic.unicamp.brislene/2s2013-mo806/sem-barreiras/sem-barreiras.pdf- sem_post should only wake one thread and only when the state of the semaphore

Semaforos Barreiras Tentativas do livro Barreiras restritas Futex glibc

Segunda tentativa (3.5)

int c;sem barreira = 0;atomic inc(c);if (c == N) sem_post(barreira);sem_wait(barreira);sem_post(barreira);

Veja o arquivo barreira2.c

Page 13: T opicos em Sistemas Operacionais - ic.unicamp.brislene/2s2013-mo806/sem-barreiras/sem-barreiras.pdf- sem_post should only wake one thread and only when the state of the semaphore

Semaforos Barreiras Tentativas do livro Barreiras restritas Futex glibc

Barreiras reutilizaveis: varios encontrosThreads devem se ressincronizar!

Page 14: T opicos em Sistemas Operacionais - ic.unicamp.brislene/2s2013-mo806/sem-barreiras/sem-barreiras.pdf- sem_post should only wake one thread and only when the state of the semaphore

Semaforos Barreiras Tentativas do livro Barreiras restritas Futex glibc

Barreiras reutilizaveis: varios encontrosThreads devem se ressincronizar!

Page 15: T opicos em Sistemas Operacionais - ic.unicamp.brislene/2s2013-mo806/sem-barreiras/sem-barreiras.pdf- sem_post should only wake one thread and only when the state of the semaphore

Semaforos Barreiras Tentativas do livro Barreiras restritas Futex glibc

Barreiras reutilizaveis: varios encontrosThreads devem se ressincronizar!

Page 16: T opicos em Sistemas Operacionais - ic.unicamp.brislene/2s2013-mo806/sem-barreiras/sem-barreiras.pdf- sem_post should only wake one thread and only when the state of the semaphore

Semaforos Barreiras Tentativas do livro Barreiras restritas Futex glibc

Barreiras reutilizaveis: varios encontrosThreads devem se ressincronizar!

Page 17: T opicos em Sistemas Operacionais - ic.unicamp.brislene/2s2013-mo806/sem-barreiras/sem-barreiras.pdf- sem_post should only wake one thread and only when the state of the semaphore

Semaforos Barreiras Tentativas do livro Barreiras restritas Futex glibc

Barreiras reutilizaveis: varios encontrosThreads devem se ressincronizar!

Page 18: T opicos em Sistemas Operacionais - ic.unicamp.brislene/2s2013-mo806/sem-barreiras/sem-barreiras.pdf- sem_post should only wake one thread and only when the state of the semaphore

Semaforos Barreiras Tentativas do livro Barreiras restritas Futex glibc

Segunda tentativa (3.5)Barreiras reutilizaveis???

int c;sem barreira = 0;atomic inc(c);if (c == N) sem_post(barreira);sem_wait(barreira);sem_post(barreira);

Veja o codigo barreira2b.c

Page 19: T opicos em Sistemas Operacionais - ic.unicamp.brislene/2s2013-mo806/sem-barreiras/sem-barreiras.pdf- sem_post should only wake one thread and only when the state of the semaphore

Semaforos Barreiras Tentativas do livro Barreiras restritas Futex glibc

Barreiras reutilizaveis: varios encontrosCuidado com os espertinhos!

Page 20: T opicos em Sistemas Operacionais - ic.unicamp.brislene/2s2013-mo806/sem-barreiras/sem-barreiras.pdf- sem_post should only wake one thread and only when the state of the semaphore

Semaforos Barreiras Tentativas do livro Barreiras restritas Futex glibc

Barreiras reutilizaveis: varios encontrosCuidado com os espertinhos!

Page 21: T opicos em Sistemas Operacionais - ic.unicamp.brislene/2s2013-mo806/sem-barreiras/sem-barreiras.pdf- sem_post should only wake one thread and only when the state of the semaphore

Semaforos Barreiras Tentativas do livro Barreiras restritas Futex glibc

Barreiras reutilizaveis: varios encontrosCuidado com os espertinhos

Page 22: T opicos em Sistemas Operacionais - ic.unicamp.brislene/2s2013-mo806/sem-barreiras/sem-barreiras.pdf- sem_post should only wake one thread and only when the state of the semaphore

Semaforos Barreiras Tentativas do livro Barreiras restritas Futex glibc

Deadlock (3.6)

int c; lock t mutex;sem barreira = 0;lock(mutex);c++;if (c == N) sem_post(barreira);sem_wait(barreira);sem_post(barreira);unlock(mutex);

Uso claro para variaveis de condicao...

Page 23: T opicos em Sistemas Operacionais - ic.unicamp.brislene/2s2013-mo806/sem-barreiras/sem-barreiras.pdf- sem_post should only wake one thread and only when the state of the semaphore

Semaforos Barreiras Tentativas do livro Barreiras restritas Futex glibc

Terceira tentativa (3.7)

int c;sem barreira = 0;atomic inc(c);if (c == N) sem_post(barreira);sem_wait(barreira);sem_post(barreira);atomic dec(c);if (c == 0) sem_wait(barreira);

Veja o arquivo barreira3.c

Page 24: T opicos em Sistemas Operacionais - ic.unicamp.brislene/2s2013-mo806/sem-barreiras/sem-barreiras.pdf- sem_post should only wake one thread and only when the state of the semaphore

Semaforos Barreiras Tentativas do livro Barreiras restritas Futex glibc

Quarta tentativa (3.8)

int c;sem barreira = 0;local c = atomic inc(c);if (local c == N) sem_post(barreira);sem_wait(barreira);sem_post(barreira);local c = atomic dec(c);if (local c == 0) sem_wait(barreira);

Veja o arquivo barreira4.c

Page 25: T opicos em Sistemas Operacionais - ic.unicamp.brislene/2s2013-mo806/sem-barreiras/sem-barreiras.pdf- sem_post should only wake one thread and only when the state of the semaphore

Semaforos Barreiras Tentativas do livro Barreiras restritas Futex glibc

Roleta dupla

int c;sem roleta_entrada = 0, roleta_saida = 1;local c = atomic inc(c);if (local c == N)

sem_wait(roleta_saida);sem_post(roleta_entrada);

sem_wait(roleta_entrada);sem_post(roleta_entrada);

Page 26: T opicos em Sistemas Operacionais - ic.unicamp.brislene/2s2013-mo806/sem-barreiras/sem-barreiras.pdf- sem_post should only wake one thread and only when the state of the semaphore

Semaforos Barreiras Tentativas do livro Barreiras restritas Futex glibc

Roleta dupla (continuacao)

local c = atomic dec(c);if (local c == 0)sem_wait(roleta_entrada);sem_post(roleta_saida);

sem_wait(roleta_saida);sem_post(roleta_saida);

Veja o arquivo barreira5.c

Page 27: T opicos em Sistemas Operacionais - ic.unicamp.brislene/2s2013-mo806/sem-barreiras/sem-barreiras.pdf- sem_post should only wake one thread and only when the state of the semaphore

Semaforos Barreiras Tentativas do livro Barreiras restritas Futex glibc

Barreiras restritasNao ha lugar para todos...

Page 28: T opicos em Sistemas Operacionais - ic.unicamp.brislene/2s2013-mo806/sem-barreiras/sem-barreiras.pdf- sem_post should only wake one thread and only when the state of the semaphore

Semaforos Barreiras Tentativas do livro Barreiras restritas Futex glibc

Barreiras restritasUm grupo deve sair para que outro possa entrar!

Page 29: T opicos em Sistemas Operacionais - ic.unicamp.brislene/2s2013-mo806/sem-barreiras/sem-barreiras.pdf- sem_post should only wake one thread and only when the state of the semaphore

Semaforos Barreiras Tentativas do livro Barreiras restritas Futex glibc

Barreiras restritasCuidado com os espertinhos!

Page 30: T opicos em Sistemas Operacionais - ic.unicamp.brislene/2s2013-mo806/sem-barreiras/sem-barreiras.pdf- sem_post should only wake one thread and only when the state of the semaphore

Semaforos Barreiras Tentativas do livro Barreiras restritas Futex glibc

Sobre desempenho...

Duas roletas causam muitas trocas de contexto

Na secao 3.6.6 o livro sugere um semaforo de incrementomaior do que 1

Variaveis de condicao e broadcast?

Futex?

Page 31: T opicos em Sistemas Operacionais - ic.unicamp.brislene/2s2013-mo806/sem-barreiras/sem-barreiras.pdf- sem_post should only wake one thread and only when the state of the semaphore

Semaforos Barreiras Tentativas do livro Barreiras restritas Futex glibc

Tentativa com futex: roleta dupla

int c;int roleta_entrada = 0, roleta_saida = 1;local c = atomic inc(c);if (local c == N)

roleta_saida = 0;roleta_entrada = 1;futex_wake(&roleta_entrada, N-1);

elsefutex_wait(&roleta_entrada, 0);

Page 32: T opicos em Sistemas Operacionais - ic.unicamp.brislene/2s2013-mo806/sem-barreiras/sem-barreiras.pdf- sem_post should only wake one thread and only when the state of the semaphore

Semaforos Barreiras Tentativas do livro Barreiras restritas Futex glibc

Tentativa com futex: roleta dupla (continuacao)

local c = atomic dec(c);if (local c == 0)roleta_entrada = 0;roleta_saida = 1;futex_wake(&roleta_saida, N-1);

elsefutex_wait(&roleta_saida, 0);

Veja o arquivo barreira futex.c

Page 33: T opicos em Sistemas Operacionais - ic.unicamp.brislene/2s2013-mo806/sem-barreiras/sem-barreiras.pdf- sem_post should only wake one thread and only when the state of the semaphore

Semaforos Barreiras Tentativas do livro Barreiras restritas Futex glibc

Vamos analisar a implementacao da glibc?

Veja o arquivo barrier wait.c e teste o comandopthread barrier wait

Veja o codigo pthread barrier wait.c

Page 34: T opicos em Sistemas Operacionais - ic.unicamp.brislene/2s2013-mo806/sem-barreiras/sem-barreiras.pdf- sem_post should only wake one thread and only when the state of the semaphore

Semaforos Barreiras Tentativas do livro Barreiras restritas Futex glibc

Algoritmo da glibc com semaforos

sem_t sem_mutex = 1, sem_barreira = 0;

sem_wait(sem_mutex);c++;if (c < N) {

sem_post(sem_mutex);sem_wait(sem_barreira); }

local_c = atomic dec(c);if (local_c > 0)

sem_post(sem_barreira);elsesem_post(sem_mutex);

Veja o arquivo barreira6.c