[Dúvida] Semaforos em c

alves077 · October 6, 2013 at 08:49 PM

Boa noite,

Tenho andando de volta do problema típico de semáforos, com 10 produtores e 10 consumidores. Em que quando um produtor escrever mais ninguem pode aceder ao buffer, quando um consumidor lê, todos podem ler mas ninguem pode estar a escrever, isto é os produtores não podem acceder.

Teria que solver a questão com um mutex e um semáforo. Só que não estou a conseguir resolver o problema só com estes dois semáforos.

A parte de só acederem ao produtor um de cada vez, é um semáforo, inicializado a 1, por exemplo

wait(prod)

Produtor()

post(prod)

E no Consumidor faria um semáforo inicializado com 10, e o código com a mesma lógica:

wait(cons)

Consumidor()

post(cons)

Mas isto não bate certo, porque não tenho nada que me controle a relação entre os produtores e os consumidores, se me percebem, assim como está eles podem actuar ao mesmo tempo..

Não sei só com dois semáforos digo, por exemplo, que o produtor pode avançar e todos os consumidores parem...

Alguém me consegue dar alguma dica como resolver?

Obrigado pela atenção,

alves077

motherFFH · October 7, 2013 at 12:55 AM

O produtor tem que bloquear os consumidores, i.e. fazer 10 wait(cons) a seguir ao wait(prod), e libertá-los depois da escrita, claro.

HappyHippyHippo · October 7, 2013 at 08:19 AM

A parte de só acederem ao produtor um de cada vez, é um semáforo, inicializado a 1, por exemplo

...

Não sei só com dois semáforos digo, por exemplo, que o produtor pode avançar e todos os consumidores parem...

Alguém me consegue dar alguma dica como resolver?

O produtor tem que bloquear os consumidores, i.e. fazer 10 wait(cons) a seguir ao wait(prod), e libertá-los depois da escrita, claro.

este é um problema muito habitual, de quem anda a aprender este tipo de coisas.

e também é muito habitual as pessoas pensarem que o problema se resolve em volta dos objectos principais do problema.

logo, o post anterior onde indica a execução do wait n<consumidores> vezes e ir pelp caminho errado.

a solução está, por exclusão das partes, no buffer.

imagina que tens um buffer com n posições onde n < 10. se andares a brincar com semáforos com valores de 10, irás ter sempre problemas de acesso inválidos:

exemplo de erro:

- 10 produtores

- 10 consumidores

- buffer com 1 posição

- 1 semáforo de escrita inicializado a 10 (10 produtores)

- 1 semáforo de leitura inicializado a 0 (nada produzido)

>> um produtor executa o wait com sucesso, o que faz diminuir o semáforo para 9 e escreve no buffer. antes de um consumidor possa ler do buffer, um segundo produtor executa o wait com sucesso sobre o semáforo (pois este ainda contêm um valor interno superior a 0) e escreve aonde ?

agora imagina o contrário, ter um buffer com n superior a m produtores/consumidores, onde n > m:

- 1 produtor

- 2 consumidor

- buffer com 10 posição

- 1 semáforo de escrita inicializado a 1 (1 produtor)

- 1 semáforo de leitura inicializado a 0 (nada produzido)

>> por muito que é feito o wait, nunca escreverás mais do que 1 elemento no buffer porque o semáforo de escrita é inicialiszado a 1. logo tens um buffer (neste caso) com 9 espaços a "fazer nada".

conclusão: o que tens de fazer é ter dois semáforos, um de leitura e um de escrita onde o de escrita terá sempre o tamanho do buffer.

// init
- criar buffer com "n" posições
- criar semáforo de leitura inicializado a 0
- criar semáforo de escrita inicializado a "n"
- criar mutex de acesso ao buffer
- criar produtores
- criar consumidores

// ciclo do produtor
- fazer wait no semáforo de escrita
- entrar na área reservada criada pelo mutex
- inserir o valor no buffer
- sair da área reservada criada pelo mutex
- fazer post no semáforo de leitura

// ciclo do consumidor
- fazer wait no semáforo de leitura
- entrar na área reservada criada pelo mutex
- ler o valor do buffer
- sair da área reservada criada pelo mutex
- fazer post no semáforo de escrita

prontos ... só isso (tendo em conta o número de ciclos que cada produto/consumidor irá fazer)

Edited October 7, 2013 at 08:25 AM by HappyHippyHippo

alves077 · October 8, 2013 at 09:01 PM

Desde já obrigado pelas dicas.

Eu com 2 semáforos e um mutex (semáforo binário) até conseguia chegar a solução, mas como o exercicio pede só para usar um semafóro e o mutex, já me confunde um bocado as ideias como controlo tudo. Só tendo contadores por fora, mas acho isso um bocado esquisito em programação concorrente...

Será possivel fazer só ocm um semáforo e um mutex?

Obrigado pela atenção,

alves077

HappyHippyHippo · October 9, 2013 at 02:21 AM

... mas como o exercicio pede só para usar um semafóro e o mutex ...

???

apresenta o enunciado. se faz o favor

alves077 · October 9, 2013 at 01:44 PM

O enunciado diz é qulquer coisa como, Quando um produtor coloca uma nova entrada na fila, nenhum outro processo pode aceder a fila, tanto um produtor como um consumidor. Quando existe um processo consumidor na fila, nenhum produtor pode aceder a fila, mas outros consumidores podem consumir simultaneamente. Este comportamento é conseguida através de dois semáforos, uma para controlar o acesso dos produtores para a fila e outro que controla o acesso dos consumidores .

Acho que consegui construir o código só com dois semáforos, incluindo o mutex, fiz algo como:

void produz(int n) {
	  sem_wait(stop_produtores);
	  produz();
	   sem_post(stop_produtores);
}

void consumidor(int n)
{
	 sem_wait(mutex);
	++contador_leituras;
	if(contador_leituras == 1)
		sem_wait();
	sem_signal(stop_produtores);

  	 consume();

	  sem_wait(mutex);
	--contador_leituras;
	if(contador_leituras == 0)
		sem_signal(stop_produtores);
	sem_signal(mutex);

Sem ligar muito a questões de sintaxe, a logica que segui é isto. Com os semáforos iniciados a 1. e o contador_leituras = 0.

Mas minha questão agora é que como está isto pode claramente dar problemas, pelas simples razão que o produtor pode ficar a espera até que o consumidor liberta, mas o consumidor pode nunca libertar, logo ficará eternamente a espera....

Dou assim prioridade clara aos leitores, fazem ideia como pode fazer sem dar prioridade ao consumidor ou ao produtor ? Reduzindo assim a probabilidade de erro.

Obrigado pela atenção,

alves077

Edited October 9, 2013 at 01:45 PM by alves077

HappyHippyHippo · October 9, 2013 at 01:55 PM

mas como o exercicio pede só para usar um semafóro

Este comportamento é conseguida através de dois semáforos

afina é boi ou é vaca ?

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

Acho que consegui construir o código só com dois semáforos, incluindo o mutex, fiz algo como:

fizes algo que nem te deste ao trabalho de

- compilar

- verificar o protótipo das funções de manipulação de mutexes

- verificar o protótipo das funções de manipulação de semáforos

Edited October 9, 2013 at 01:56 PM by HappyHippyHippo

alves077 · October 10, 2013 at 02:27 PM

Quando falo em dois semáforos é já com o mutex.

Mutex é um semáforo algo especial, por isso é que as vezes falo em um semáforo + mutex, e as vezes em dois semáforos. Mas, para que fique claro, é um semáforo e um mutex.

O código que escrevi não foi compilado, foi escrito diretamente aqui, só queria passar a ideia que tinha, não tinha o código comigo na altura que respondi. Por isso como disse é provável que tenha erros de sintaxe e afins. Mas o que queria passar era a ideia do algoritmo que acho que funciona com aquele caso, controlando com um contador se o produtor está a produzir. Mas assim como está dá clara preferência aos consumidores, podendo os produtores ficarem eternamente à espera..

Obrigado pela atenção,

alves077

HappyHippyHippo · October 10, 2013 at 02:39 PM

vamos lá a ver uma coisa:

mutexes são mutexes e semáforos são semáforos.

só faltava vir dizer que condições/monitores, fibras e a afins também são uma espécie de semáforos

um pé é a mão têm a mesma estrutura, os mesmos tipo de ossos, 5 dedos separados, unhas em cada dedo, etc ... são a mesma coisa ???

deste modo, volto a dizer : apresenta o enunciado

alves077 · October 10, 2013 at 07:14 PM

Ok.... Sinceramente pensava que os mutexes eram semáforos binário, que por consequência de serem binários dão a tal: exclusão mútua. Mas sendo assim erro meu.

O enunciado está num dos meus posts.

Quando um produtor coloca uma nova entrada na fila, nenhum outro processo pode aceder a fila, seja um produtor ou um consumidor. Quando há um processo consumidor na fila, nenhum produtor pode aceder a fila, mas outros consumidores podem consumir simultaneamente. Este comportamento é conseguido através de dois semáforos, um para controlar o acesso dos produtores para a fila (STOP) e outro que controla o acesso dos consumidores (MUTEX).

HappyHippyHippo · October 10, 2013 at 07:50 PM

esse é o texto exacto do enunciado ?

alves077 · October 11, 2013 at 10:02 PM

Não queria por todo o enunciado, não sei se a pessoa que fez o enunciado ia gostar da ideia. Mas o que falta é a parte de explicar que estamos a falar de uma fila de espera partilhada e memória. A parte dos semáforos foi o que escrevi.

HappyHippyHippo · October 11, 2013 at 10:30 PM

eu quero saber se no enunciado diz explicitament que é somente com um (1) semáforo.

isto porque, como te já foi dito, não é possivel resolver com essa quantidade de semáforos.

terás sempre de ter um de leitura e um de escrita.

ps : se estas com problemas de "ai o criador do enunciado pode não gostar", eu preocupo-me mais com "ai o criador do tópico não disponibiliza a informação, então não quero saber, deixo para outro"

Edited October 11, 2013 at 10:31 PM by HappyHippyHippo

alves077 · October 13, 2013 at 02:08 PM

Mas repara, que a parte do post que eu escrevi:

"Quando um produtor coloca uma nova entrada na fila, nenhum outro processo pode aceder a fila, seja um produtor ou um consumidor. Quando há um processo consumidor na fila, nenhum produtor pode aceder a fila, mas outros consumidores podem consumir simultaneamente. Este comportamento é conseguido através de dois semáforos, um para controlar o acesso dos produtores para a fila (STOP) e outro que controla o acesso dos consumidores (MUTEX)."

É literalmente retirada do enunciado, só o que não está aqui fala como funciona o acesso a memoria, neste caso uma fila.

Voltando a ideia que tinha atrás, como resolver a questão.

Com o semáforo stop_produtor iniciado a 1. E o mutex também iniciado a 1. Acho que com esta ideia funciona. Só que dou claramente prioridade a um, isto é o consumidor ou o produtor, dependendo de quem eu dou a prioridade, pode ficar eternamente com o cpu, enquanto o outro fica eternamente a espera do recurso e nunca o têm.

E ai é que não sei se é possivel resolver só com este número de semáforos...

int contador_leituras = 0;
void produtor(int n) {
			  sem_wait(stop_produtores);
			  produz();
			  sem_post(stop_produtores);
}

void consumidor(int n)
{
			 sem_wait(mutex);
			++contador_leituras;
			if(contador_leituras == 1)
					sem_wait();
			sem_signal(stop_produtores);

	 consume();

			  sem_wait(mutex);
			--contador_leituras;
			if(contador_leituras == 0)
					sem_signal(stop_produtores);
			sem_signal(mutex);
}

Não compilei o código, mas acho que dá para ter uma ideia de como eu penso resolver. Por isso não ligues a erros de sintaxe.

Obrigado pela atenção,

alves077

Edited October 13, 2013 at 02:15 PM by alves077

HappyHippyHippo · October 13, 2013 at 10:09 PM

É literalmente retirada do enunciado

se essa frase é retirada do enunciado, da próxima vez que chegares à beira do escritor do enunciado dá-lhe duas chapadas na cara e diz para ir renovar o canudo.

a solução já foi apresentada num post anterior.

Rui Carlos · October 14, 2013 at 02:19 PM

HHH, na tua solução é possível estarem vários consumidores a ler ao mesmo tempo?

Ou eu estou a complicar, ou para tal ser possível não dá para usar uma simples queue, pois torna-se complicado controlar os espaços disponíveis na queue (podiam aparecer buracos no meio, não?).

Em pensei numa solução em que usaria um semáforo para controlar quando é que se pode ler/escrever, e um mutex para controlar o acesso a uma estrutura de dados que nos diz o estado de cada posição no buffer, e também para controlar o acesso ao semáforo.

O problema que vejo na solução que pensei, é que o produtor podia conseguir o acesso para escrita, mas depois chegar à conclusão que não tinha espaço para escrever, ou seja, estaria a desperdiçar ciclos. Mas penso que isso só aconteceria se estivesse constantemente a ser dada prioridade aos produtores.

HappyHippyHippo · October 14, 2013 at 02:51 PM

HHH, na tua solução é possível estarem vários consumidores a ler ao mesmo tempo?

é um problema padrão de partinha de recursos, nunca um consumidor ou produtor tem acesso concorrente à fila de espera.

é para isso que se usa um mutex (mutually exclusive)

Ou eu estou a complicar, ou para tal ser possível não dá para usar uma simples queue, pois torna-se complicado controlar os espaços disponíveis na queue (podiam aparecer buracos no meio, não?).

sim dá para usar uma queue perfeitamente normal, pois como disse anteriormente, nunca tens acessos concorrentes à queue pois o mutex cria a àrea de exclusividade.

os semáforos servem para sinalizar quandos "recursos" estão disponíveis para serem consumidos.

exemplo para uma inicialização de uma fila de espera com 3 espaços:

- um semáforo de escrita inicializado a 3 (3 espaços disponíveis para escrita)

- um semáforo de leitura inicializado a 0 (nenhum espaço com informação)

- um mutex que cria a o acesso sincronizado ao recurso/fila de espera.

basta usar o algoritmo que apresentei num post anterior.

Estejam N produtores a fazer "sem_wait" ao semáforo de escrita (com valor inicial de 3) somente a 3 é que é dado permissão, no entanto o mutex garante que a fila de espera é manipulada por uma de cada vez.

Estejam N consumidores a tentar ler da fila de espera, sejam escritos M <= 3 dados na fila de espera, a esses M consumidores seram dadas permissões de leitura, mas novamente ficam sincronizadas pelo mesmo mutex que dita que só acede à fila de esepra, um de cada vez.

é claro que é necessário ter atenção ao momento de sinalização dos semáforos (como explicado no post com o algoritmo) para que os consumidores não sejam sinalizados antes de que a informação seja escrita na fila de espera.

-----

conclusão : o algoritmo é do mais simples que existe.

volto a fazer post do algorimto para ficar tido junto :

(nota que quando digo "entrar"/"sair" da área reservada não é mais do que fazer "lock"/"unlock" do mutex, e quando refiro "buffer" não é mais do que fila de espera")

// init
- criar buffer com "n" posições
- criar semáforo de leitura inicializado a 0
- criar semáforo de escrita inicializado a "n"
- criar mutex de acesso ao buffer
- criar produtores
- criar consumidores

// ciclo do produtor
- fazer wait no semáforo de escrita
- entrar na área reservada criada pelo mutex
- inserir o valor no buffer
- sair da área reservada criada pelo mutex
- fazer post no semáforo de leitura

// ciclo do consumidor
- fazer wait no semáforo de leitura
- entrar na área reservada criada pelo mutex
- ler o valor do buffer
- sair da área reservada criada pelo mutex
- fazer post no semáforo de escrita

Edited October 14, 2013 at 02:53 PM by HappyHippyHippo

Rui Carlos · October 14, 2013 at 03:03 PM

HHH, o enunciado diz que podes ter vários consumidores a ler ao mesmo tempo. Em geral, não me parece que isso seja uma problema, mas tudo depende da estrutura de dados que está por trás.

Assim, diria que o algoritmo que sugeristes não cumpre os requisitos do enunciado (se bem que provavelmente o enunciado não é explícito sobre se é obrigatório ou opcional permitir acessos concorrentes de leitura).

De qualquer modo, eu suspeito que o enunciado, que limita a dois os mutex/semáforos, é exequível. Mas provavelmente terá uma solução bem mais complexa do que a que propões.

HappyHippyHippo · October 14, 2013 at 03:14 PM

HHH, o enunciado diz que podes ter vários consumidores a ler ao mesmo tempo.

só existe uma maneira de teres consumidores a "ler ao mesmo tempo" : uma mutex para cada posição do buffer. não consegues controlar de outra forma o acesso à posições do buffer de outra forma. (e nunca será uma queue)

mas ao ter uma mutex em cada posição do buffer, invalida a permissa que só se pode usar um mutex e um semáforo, porque mesmo que tenhas um buffer com uma posição, não tens maneira de controlar o acesso dos consumidores e dos produtores sem estares a fazeres ciclos de execução contínuos.

basta pensar no problema desta forma:

- como fazer parar os consumidores de escrever no buffer quando este está cheio ? resposta = semáforo

- como fazer parar os produtores de escrever no buffer quando este está vazio ? resposta = semáforo

como vês, sem o uso de dois semáforos distintos, terás sempre um ciclo de execução contínuo, o que não é o objectivo de uma solução com mutexes/semáforos.

ninguém quer ter o CPU a 100% ...

Edited October 14, 2013 at 03:15 PM by HappyHippyHippo

Rui Carlos · October 14, 2013 at 03:37 PM

Penso que um mutex para controlar a atribuição de uma posição do buffer a um consumidor/produtor era suficiente para permitires leituras concorrentes (a menos que me esteja a escapar alguma coisa, o que é bem possível).

Em todo o caso, para já também não estou a ver nenhuma solução que não tenha pelo menos um ciclo constantemente a correr.

Sign In

[Dúvida] Semaforos em c

Recommended Posts

alves077

motherFFH

HappyHippyHippo

alves077

HappyHippyHippo

alves077

HappyHippyHippo

alves077

HappyHippyHippo

alves077

HappyHippyHippo

alves077

HappyHippyHippo

alves077

HappyHippyHippo

Rui Carlos

HappyHippyHippo

Rui Carlos

HappyHippyHippo

Rui Carlos

Create an account or sign in to comment

Create an account

Sign in

Home

Activity

Revista PROGRAMAR

Important Information