Discussao interessante sobre broadcast

[Guilherme O'Connor de Lungarzo <guioc@linux.ime.usp.br>]

Pessoal, um aluno da turma fez uma pergunta muito boa que acabou descambando em
uma discussao interessante que eu gostaria de por na lista. Infelizmente o nosso
colega nao quis que a conversa fosse colocada verbatim e pediu que eu colocasse
como uma explicacao minha portanto eu vou colocar apenas os trechos relevantes
das perguntas dele e omitir a sua identidade. Espero que ele nao se incomode com
esses trechos (que, devo confessar, sao extensos, nao teve muito jeito).

Ressalto que a duvida deste aluno me fez pensar em acrescentar uma secao à minha
apostila e já agradeci ao aluno pelos testes e respostas que ele me deu, mas
como isso nao vai ser imediato, quero colocar na lista antes da entrega do EP,
para ajudar o maximo possivel.

Se o aluno resolver abandonar o anonimato, ele pode me mandar um email e quando
eu modificar a apostila, eu faco o agradecimento formal a ele.


---------------------

/*****************
 * O Aluno perguntou o seguinte:
 *****************/

Suponha que VÁRIOS consumidores tenham o código:

pthread_mutex_lock(&mutex_acesso_ao_buffer);
pthread_cond_wait(&cond_buffer_tem_algo, &mutex_acesso_ao_buffer);
faz algo com o conteúdo do buffer;
pthread_mutex_unlock(&mutex_acesso_ao_buffer);

E o produtor:

pthread_mutex_lock(&mutex_acesso_ao_buffer);
coloca algo no buffer;
pthread_cond_signal(&cond_buffer_tem_algo);
pthread_mutex_unlock(&mutex_acesso_ao_buffer);

Isso funciona? Funcionaria se eu usasse broadcast ao invés de signal? Faz
alguma diferença nesse caso usar broadcast ou signal? Porque eu li em algum
lugar que tanto a escolha da thread a ser liberada no signal como a escolha
de qual thread pega o mutex (no caso do broadcast, em que vários
consumidores são liberados ao mesmo tempo) dependem do escalonador do SO.
Nesse caso, ambos os casos, broadcast e signal, estariam sujeitos ao
escalonador do SO da mesma maneira... 


/*****************
 * A resposta foi
 *****************/

O que eu sei é o seguinte. A alocacao de processos no processador é
responsabilidade exclusiva do SO, faz parte do seu trabalho. O SO é um programa
que serve justamente para prover uma abstracao da maquina para vc programar em
cima de chamadas de funcao e sem preocupacao com a maquina.

Na medida em que os processos sao independentes, eles ocupam o processador
alternadamente mas é tao rapido que parece simultaneo, mas se vc está usando o
emacs e o mozilla ao mesmo tempo, para vc nao faz nenhuma diferenca para vc qual
executa instrucoes antes do outro, desde que a mudanca de contexto ocorra
suficientemente rapido para parecer simultaneo.

Isto é muito adequado, mas tem uma limitacao, se vc precisa uma ordem
especifica, vc nao sem suporte, pelo menos nao a principio. É aí que entra o uso
de regioes criticas.

Quando vc deixa um processo esperando, o SO sabe que ele esta esperando e ele é
posto de lado, ele nao executa. Quer fazer um teste muito simples? Executa o
comando sleep da shell dentro do comando time.

$time sleep 3
real    0m3.019s
user    0m0.000s
sys     0m0.000s

O programa executou 3 segundos, mas nao consumiu nenhum recurso.

Eu tenho a impressao que sinalizar uma trhead especifica poderia ser controlado
pela biblioteca, tanto que vc pode fazer isso facilmente usando variaveis de
condicao diferentes para cada thread.

Eu nao conheco o broadcast (por favor me passa um link) mas suponho que ele
sinalize todos os processos que esperam pela variavel. Isto quer dizer que o SO
acorda eles (todos eles) mas só um vai conseguir entrar no mutex. Quem? Oras, o
primeiro que pedir, provavelmente o primeiro a ser acordado. Mas repara o que vc
está tratando agora. Agora vc tem um monte de processos que acham que tem algo
para eles apenas esperando para entrar na RC. Pode ser que eles acabem pegando o
mesmo valor.

É mais ou menos como dar o mesmo numero de senha em um daqueles restaurantes que
dao uma senha para vc esperar pela comida. Quando sair uma bandeja, todo mundo
com o mesmo numero vai correndo para o balcao, mas só um vai pegar.

O certo é sinalizar apenas um e o resto espera sua vez.

Agora o exercicio, Faz um programinha simples onde o produtor produz um numero e
n consumidores tem que pegar (todos tem que pegar o mesmo numero, mas só depois
que ele for colocado, é aqui onde entra a variavel de condicao) e faz tres
versoes, uma que usa broadcast, uma que usa um signal e uma que usa um for de
signals.

Provavelmente vc vai encontrar o seguinte resultado. O primeiro e o terceiro
caso vai ser igual em termos de resultado, enquanto que no segundo apenas um vai
pegar.

Bom, depois de um email deste tamanho acho que vou colocar esta nova informacao
na apostila assim que tiver tempo (talvez no feriado), agradeco se vc me contar
o resultado dos testes ;-)


/*****************
 * E o aluno
 *****************/

A versão normal, com um signal só, deu certo. No caso do broadcast e do "for de
signals", "todo mundo pegou a bandeja", ou seja, a sessão crítica não foi
respeitada. Deu a impressão de que o wait/broadcast NÃO está
dando lock depois de receber o signal. O esperado seria que um dos
consumidores conseguisse o recurso e todos os outros ficassem bloqueados,
não? 

/*****************
 * E segue
 *****************/

Ah, agora que eu reparei que isso foi exatamente o que você previu :-)
Mas ainda não entendi... O wait/broadcast não dá um lock depois de receber o
signal? Isso não deveria permitir que apenas uma thread que deu wait entre
na seção crítica?

/*****************
 * E eu disse
 *****************/

A explicacao é simples. A regiao critica deve ter sido respeitada sim, mas
acontece que como vc acordou TODOS os consumidores eles formaram uma fila para
pegar a "bandeja". O primeiro entrou, pegou e terminou a execucao, liberando a
RC. Com a RC liberada, o segundo da fila Conseguiu entrar na RC e pegou tb, e
assim por diante.

Diferentemente do INPS, do SUS e da Caixa Economica Federal, o tempo gasto em
uma fila dessas é micrometrico, entao vc nao conseguiu perceber a olho nú a
diferenca de tempo.

Mas que fila é essa afinal de contas? Essa é a pergunta que vc me fez
originalmente, essa fila não tem nada a ver com as pthreads, se vc lembrar bem
uma thread tem propriedades de escalonamento, logo ele entra na fila de
escalonamento do SO. Na verdade NAO há uma fila na porta da RC, o que há é uma
fila de escalonamento de processos. Ocasionalmente os processos ativos ganham o
processador e fazem o que tem que fazer. No caso dos consumidores, o que eles
estao fazendo é esperando para entrar na RC. Se ela estiver livre, entao o
sortudo que for o primeiro a ser escalonado vai entrar.

Isto quer dizer que a ordem é, em principio, aleatoria. Claro que em um código
deste tamanho é provavel que elas sejam escalonadas na ordem, porque cada
execucao provavelmente leva menos tempo do que é alocado, mas se a execucao
fosse maior....

Sugestao: Modifica o código dos consumidores para que eles imprimam mensagens e
usa a funcao sleep dentro da RC para fazer a execucao demorar mais.

A mensagem poderia ser algo como
"Eu sou a thread $id e peguei o valor $valor, agora vou dormir $tempo segundos"

O que deveria acontecer é que vai acontecer que haverá um delay de $tempo
segundos entre as mensagens, isto pq enquanto a thread $id dorme, dentro da RC,
os outros nao podem pegar $valor, mas quando finalmente $id acorda e sai da RC
algum outro, que já foi chamado pelo broadcast ou pelo for de signals, entra e
faz o mesmo.

Com um valor de $tempo apropriado vc pode acompanhar facilmente este processo