PRODUTOR E CONSUMIDOR (BOUNDED BUFFER) - JAVA

Isso acontece porque o Escalonador do sistema Operacional pode alocar o controle da CPU de uma forma inesperada. Para superar a barreira do Escalonador e evitar que Dead Locks ocorram, a operação de bloqueio deve ser atômica, ou seja, executada como se representasse uma única instrução para CPU, de modo que o Consumidor não perderá o controle da CPU no meio de um bloqueio, mas somente quando estiver totalmente bloqueado.

4- EXEMPLIFICAÇÃO - ANIMAÇÃO

No vídeo abaixo, toda a discussão das seções anteriores foi exemplificada e sumarizada em uma animação, na mesma ordem em que os assuntos foram abordados:

5- IMPLEMENTAÇÃO

A seguir descreveremos detalhes da implementação. Na primeira subseção abordaremos uma classe de fila criada para representar o buffer, na subseção seguinte criaremos a classe Produtor&Consumidor e por fim a classe de execução do programa responsável por integrar as anteriores.

5.1- FILA

Para implementar a solução do problema, utilizamos a linguagem JAVA com bibliotecas para controle de buffer já disponíveis, porém decidimos implementar também um buffer utilizando a estrutura simples First In First Out (fifo), ou fila, para facilitar o entendimento do problema, com métodos enque() e dequeue() para inserir e extrair da fila, respectivamente. Criamos uma fila que armazena valores inteiros para simplificar a solução:

1. public class FIFO

2. {

4. //VARIAVEIS

5. private int cabeca, cauda, qtd_elementos; //indices e contador

6. //cabeca -> primeiro item

7. //cauda-1 -> ultimo item

8. private int fila[]; //vetor de elementos

10. //METODOS

11. //constructor -- determina capacidade da fila / innicializando fila

12. public FIFO(int tamanho)

13. {

14. this.fila = new int[tamanho]; //cria vetor com capacidade = 'tamanho'

15. cauda = 0;

16. cabeca = 0;

17. qtd_elementos = 0;

18. }

20. //Funcao de insecao na fila

21. public void enqueue(int elemento)

22. {

24. //SE HOUVER ESPACO NA FILA

25. this.fila[this.cauda] = elemento; //insere elemento na cauda

27. //incrementa indice cauda

28. if(this.cauda == this.fila.length-1) /*se indice cauda aponta fim do vetor(length-1 pois indice vai de 0 a length-1)*/

29. this.cauda = 0; //circula e volta para o inicio

30. else //indice cauda não aponta o fim

31. this.cauda +=1; //incrementa indice cauda

33. this.qtd_elementos++; // incrementa qtd de elementos

34. //elemento inserido

35. return;

36. }

38. //Funcao remocao da fila

39. public int dequeue()

40. {

42. //SE HOUVER ITEM NA FILA

43. int valor = this.fila[this.cabeca]; //extrai o primeiro da fila

45. //incrementa indice cabeca

46. if(this.cabeca == this.fila.length-1) //se indice cabeca aponta fim do vetor(cabeca vai de 0 a length-1)

47. this.cabeca = 0; //circula e volta pro inicio

48. else //indice cabeca não aponta o fim

49. this.cabeca +=1; //incrementa indice cabeca

51. this.qtd_elementos--; // decrementa qtd de elementos

52. //elemento retirado

53. return valor;

54. }

56. //Funcao que indica fila cheia

57. public boolean cheia()

58. {

59. if(this.qtd_elementos == this.fila.length)

60. return true;

61. else

62. return false;

63. }

64. //Funcao que indica fila vazia

65. public boolean vazia()

66. {

67. if(this.qtd_elementos == 0)

68. return true;

69. else

70. return false;

71. }

73. }

5.2- PRODUTOR & CONSUMIDOR

E seguida, implementamos uma classe consumidor e produtor, onde os métodos produce() e consume(), enfileiram e extraem itens da fila, respectivamente. Como sabemos, o buffer/fila, é a região crítica que precisará ser acessada, e por esse motivo, utilizamos dentro dos métodos de produtor e consumidor o método synchronized() com parâmetro "this" que é o objeto chave, de modo que o acesso à fila desse objeto seja atômico e os threads não consigam acessa-la simultaneamente.

Os dois métodos verificam se a fila está vazia ou cheia, e caso aconteça, chamam o método wait() que bloqueia a thread em execução. O produtor e o consumidor também enviam um sinal após a inserção ou remoção de itens através do método notify():

1. public class ConsumerProducer

2. {

4. //VARIAVEIS

5. FIFO fila; //fila que ser usada como memoria compartilhada entre threads consumidor e produtor

7. //METODOS

8. //constructor

9. public ConsumerProducer(FIFO fila)

10. {

11. this.fila = fila; //variavel fila referencia uma fila passada como argumento

12. }

14. //produtor

15. public void produce()

16. {

17. int elemento = 0;

19. while(true)// executa em loop

20. {

21. synchronized (this)//acesso atomico à fila

22. {

23. while(this.fila.cheia())//se fila cheia

24. {

25. //System.out.println("produtor Dormindo");

26. try

27. {

28. wait(); //bloqueia o thread

29. }

30. catch (InterruptedException e){}

31. }

33. //Se houver espaco na fila

34. this.fila.enqueue(elemento); //insere elemento

35. System.out.println("Elemento "+elemento+" produzido");

36. elemento++;

37. notify(); //notifica que há elementos na fila

38. }

39. }

40. }

43. //consumidor

44. public void consume()

45. {

46. int elemento;

48. while(true)

49. {

50. synchronized (this)//inicia operacao atomica

51. {

52. while(this.fila.vazia())//se fila vazia

53. {

54. //System.out.println("consumidor Dormindo");

55. try{

56. wait(); //bloqueia o thread

57. }

58. catch (InterruptedException e){}

59. }

61. //Se houver elemento na fila

62. elemento = this.fila.dequeue(); //retira primeiro da fila

63. System.out.println("Elemento "+elemento+" consumido");

64. notify(); //notifica que há espaço na fila

65. }

66. }

67. }

70. }

Toda a operação de inserir na fila ou de retirar da fila é atômica. Isso é necessários por conta da variável qtd_elementos da classe FIFO. Lembre-se da analogia feita na seção 3, sobre os deadLocks. No nosso caso em específico, o Consumidor pode encontrar a fila vazia, perder o controle, e o Produtor poderá produzir todos os itens e bloquear. Depois o Consumidor restaura seu contexto e também bloqueia. Com o uso de synchronized e notify, podemos atualizar a quantidade de elementos de forma atômica.

5.3- EXECUÇÃO

Por fim, no método main() criamos um objeto fila e um consumidor/produtor. O Java nos permite rodar funções de um objeto em diferentes threads através da criação de um objeto Thread que recebe como parâmetro uma interface Runnable. Essa interface nos permite sobrescrever seu método run() com o método que desejamos rodar em uma thread.

Criamos duas Threads, uma para o método consume() e outra para produce(), e em seguida iniciamos a execução de ambas com Thread.start(). O método Thread.join() permite que a função principal abdique do controle da CPU, de modo que as threads possam ser executadas sem interrupção:

1. public class Programa

2. {

3. public static void main(String[] args) throws InterruptedException

4. {

6. //OBJETOS

7. FIFO fila = new FIFO(3); //fila de tamanho 3

8. ConsumerProducer programa = new ConsumerProducer(fila); /*fila é passado como buffer para novo Objeto ConsumerProducer*/

10. Thread produtor = new Thread //cria um objeto Thread para o metodo produtor

11. (

12. new Runnable() /*Thread recebe interface Runnable como parametro, e roda seu método run como uma thread*/

13. {

14. public void run() //Runnable permite sobrescrever seu método run

15. {

16. programa.produce(); //metodo produce do objeto ConsumerProducer sobrescreve metodo run

17. }

18. }

19. );

20. Thread consumidor = new Thread //cria uma thread para o metodo consumidor

21. (

22. new Runnable()

23. {

24. public void run()

25. {

26. programa.consume(); //método consume de ProducerConsumer rodará como thread

27. }

28. }

29. );

31. //INICIA PROGRAMA

32. //inicia as threads criadas

33. produtor.start();

34. consumidor.start();

35. //main abdica do controle - aguarda execucao das threads

36. produtor.join();

37. consumidor.join();

38. }

40. }

Output:

Elemento 0 produzido

Elemento 1 produzido

Elemento 2 produzido

.....

Elemento 3953 consumido

Elemento 3954 consumido

Elemento 3955 consumido

Elemento 3956 produzido

Elemento 3957 produzido

Elemento 3956 consumido

Elemento 3957 consumido

Elemento 3958 produzido

Elemento 3959 produzido

Elemento 3960 produzido

Elemento 3958 consumido

Elemento 3959 consumido

Elemento 3960 consumido

.....

Perceba que, apesar de a nossa fila ter tamanho 3 nesse exemplo, nem sempre serão produzidos 3 elementos de uma só vez. O Escalonador pode passar o controle para a Thread Consumidora a qualquer momento, como destacado na saída acima.

6- CONCLUSÃO

A classe Thread e a interface Runnable da linguagem Java tornam possível a execução de threads paralelamente, de modo que diversas soluções tornem-se possíveis para os casos em que a programação concorrente é necessária. Podemos criar vários threads para um mesmo método, ou para execução métodos distintos, o que permite dar ao usuário do programa a impressão de paralelismo - como quando vemos uma barra de progresso sendo executada concomitantemente com o carregamento de uma informação. A utilidade da programação concorrente é ampla, e além de abranger a interação com o usuário, também exerce um papel importante em outras aplicações que exigem a execução de múltiplas tarefas simultaneamente, como no caso dos sistemas operacionais.

Apesar das vantagens, alguns cuidados precisam ser tomados em relação aos recursos compartilhados pelas aplicações concorrentes, para que não haja perda de informações. É necessário ter cautela com as áreas críticas que devem impor regras de acesso, de maneira a evitar conflitos gerados pela disputa por controle entre as tarefas. Um sistema bancário por exemplo, deve atomizar as operações de rendimento e depósitos, pois se um usuário realizar um depósito, interrompendo uma operação de rendimento, seu depósito poderá ser ignorado após o rendimento ser calculado e registrado mais tarde. Por esse motivo, é importante sincronizar as tarefas e restringir o acesso às variáveis que não são thread safe (passíveis de gerar conflito).

O problema do produtor e consumidor é importante para abordagem dessas características da programação concorrente, que exigem uma solução baseada no uso das ferramentas de gerenciamento de execução de tarefas paralelas.

7- REFERÊNCIAS

Caelum Escola de Tecnologia Cursos Online. Disponível em: <https://www.caelum.com.br/apostila-java-orientacao-objetos/>. Acesso em: 19 jul. 2021.

Producer-Consumer solution using threads in Java - GeeksforGeeks. Disponível em: <https://www.geeksforgeeks.org/producer-consumer-solution-using-threads-java/>. Acesso em: 19 jul. 2021.

TANENBAUM, A. S. Modern operating systems. Fourth edition ed. Boston: Pearson, 2015.

APÊNDICE

Apêndice A - Definição original do problema

Originalmente, o problema do produtor e consumidor reside no fato de que uma operação para realizar o incremento de uma variável, exige que três instruções de máquina sejam utilizadas.

Abaixo estão representações de ambas as funções responsáveis pelo consumo e produção dos itens no buffer:

Produtor:

proximo_produto = produzir();

while(qtd_elementos == n); //bloquear se fila estiver cheia

buffer[cauda] = proximo_produto;

cauda = (cauda+1) % qtd_elementos; //maneira de circular o índice cauda na fila

qtd_elementos++;

Consumidor:

while(qtd_elementos ==0);

proximo_consumo = buffer[cabeca];

cabeca = (cabeca+1)%qtd_elementos;

qtd_elementos++;

consumir(proximo_consumo);

O while fica responsável por manter cada processo aguardando a disponibilidade do buffer, sem a necessidade de bloqueio. Itens são inseridos no fim da fila e consumidos do início da fila, e após cada inserção ou consumo, a variável qtd_elementos é atualizada, e é aí que reside o problema.

Na linguagem Assembly, para a maioria dos sistemas, o comando utilizado para incrementar a variável qtd_elementos é composto de três instruções, como a seguir:

registrador_auxiliar = qtd_elementos

registrador_auxiliar = registrador_auxiliar+1

qtd_elementos = registrador_auxiliar

A variável é incrementada com o uso de um registrador, e portanto são 3 etapas para que o seu valor seja calculado e registrado.

Se o produtor perder o controle antes que a primeira instrução seja executada, nenhum problema ocorrerá. O máximo que pode acontecer é o consumidor tomar controle e pensar que fila ainda está vazia, mas não haverá nenhuma inconsistência externa. O consumidor apenas devolverá o controle para o produtor, que em seguida incrementará a qtd_elementos.

O problema ocorre se o Produtor perder o controle depois da primeira ou segunda instrução. Porque o valor antigo de qtd_elementos será registrado e operado mais tarde, independente de qualquer atualização feita por quem tomou o controle. Exemplo: O produtor produz o segundo item da fila, e executa a primeira instrução, ou seja, salva o valor de qtd_elementos=1. Depois desse momento o consumidor toma o controle e consome o item que já havia no buffer, e decrementa a qtd_elementos para 0. Quando o produtor reassumir o controle, irá incrementar de 1 para 2. Eis uma inconsistência interna (que ocorre no código). A inconsistência externa (que ocorre na saída), é de que o Consumidor irá consumir um item duplicado ou nulo, já que irá iterar uma unidade além do devido (já que qtd_elementos vale uma unidade maior que o devido).

Do lado do consumidor, também são três as instruções de modificação da variável qtd_elementos, porém ela é decrementada. Imagine que existam 2 itens no buffer, e o consumidor consuma um deles, mas antes de decrementar qtd_elementos, ele perde o controle, com qtd_elementos=2 registrado. O produtor assume, produz um elemento e incrementa qtd_elementos=3. O consumidor retoma o controle, e decrementa o valor antigo para qtd_elementos=1, então um item deixou de ser contado. Por esse motivo o produtor produzirá uma unidade além do permitido, e irá sobrescrever algum item.

E por fim, nada impediria que o consumidor registrasse qtd_elementos=1 após consumir o último item, em seguida perdesse o controle e o produtor enchesse o buffer, bloqueando em seguida no while. Ao retomar o controle novamente, o consumidor decrementaria a qtd_elementos=1 para zero, ignorando as atualizações do produtor. E isso desencadearia um deadlock.