Algoritmo de Peterson en Sincronización de Procesos

Requisito previo: sincronización , sección crítica

Problema: El problema del consumidor del productor (o problema del búfer acotado) describe dos procesos, el productor y el consumidor, que comparten un búfer común de tamaño fijo que se utiliza como cola. El productor produce un artículo y lo coloca en el búfer. Si el búfer ya está lleno, el productor tendrá que esperar un bloque vacío en el búfer. El consumidor consume un artículo del búfer. Si el búfer ya está vacío, el consumidor tendrá que esperar un artículo en el búfer. Implemente el Algoritmo de Peterson para los dos procesos que usan memoria compartida de modo que haya una exclusión mutua entre ellos. La solución debería estar libre de problemas de sincronización.

Producer-Consumer

Algoritmo de Peterson –

// code for producer (j)
  
// producer j is ready
// to produce an item
flag[j] = true;
  
// but consumer (i) can consume an item
turn = i;
  
// if consumer is ready to consume an item
// and if its consumer's turn
while (flag[i] == true && turn == i)
  
    { // then producer will wait }
  
    // otherwise producer will produce
    // an item and put it into buffer (critical Section)
  
    // Now, producer is out of critical section
    flag[j] = false;
    // end of code for producer
  
    //--------------------------------------------------------
    // code for consumer i
  
    // consumer i is ready
    // to consume an item
    flag[i] = true;
  
    // but producer (j) can produce an item
    turn = j;
  
    // if producer is ready to produce an item
    // and if its producer's turn
    while (flag[j] == true && turn == j)
  
        { // then consumer will wait }
  
        // otherwise consumer will consume
        // an item from buffer (critical Section)
  
        // Now, consumer is out of critical section
        flag[i] = false;
// end of code for consumer

Explicación del algoritmo de Peterson –

El algoritmo de Peterson se utiliza para sincronizar dos procesos. Utiliza dos variables, una bandera de array bool de tamaño 2 y una variable int para lograrlo.
En la solución i representa al Consumidor y j representa al Productor. Inicialmente las banderas son falsas. Cuando un proceso quiere ejecutar su sección crítica, establece su indicador en verdadero y se convierte en el índice del otro proceso. Esto significa que el proceso quiere ejecutarse pero permitirá que el otro proceso se ejecute primero. El proceso realiza una espera ocupada hasta que el otro proceso haya terminado su propia sección crítica.
Después de esto, el proceso actual ingresa a su sección crítica y agrega o elimina un número aleatorio del búfer compartido. Después de completar la sección crítica, establece su propio indicador en falso, lo que indica que ya no desea ejecutar.

El programa se ejecuta durante un tiempo fijo antes de salir. Este tiempo se puede cambiar cambiando el valor de la macro RT.

// C program to implement Peterson’s Algorithm
// for producer-consumer problem.
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <time.h>
#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/shm.h>
#include <stdbool.h>
#define _BSD_SOURCE
#include <sys/time.h>
#include <stdio.h>
  
#define BSIZE 8 // Buffer size
#define PWT 2 // Producer wait time limit
#define CWT 10 // Consumer wait time limit
#define RT 10 // Program run-time in seconds
  
int shmid1, shmid2, shmid3, shmid4;
key_t k1 = 5491, k2 = 5812, k3 = 4327, k4 = 3213;
bool* SHM1;
int* SHM2;
int* SHM3;
  
int myrand(int n) // Returns a random number between 1 and n
{
    time_t t;
    srand((unsigned)time(&t));
    return (rand() % n + 1);
}
  
int main()
{
    shmid1 = shmget(k1, sizeof(bool) * 2, IPC_CREAT | 0660); // flag
    shmid2 = shmget(k2, sizeof(int) * 1, IPC_CREAT | 0660); // turn
    shmid3 = shmget(k3, sizeof(int) * BSIZE, IPC_CREAT | 0660); // buffer
    shmid4 = shmget(k4, sizeof(int) * 1, IPC_CREAT | 0660); // time stamp
  
    if (shmid1 < 0 || shmid2 < 0 || shmid3 < 0 || shmid4 < 0) {
        perror("Main shmget error: ");
        exit(1);
    }
    SHM3 = (int*)shmat(shmid3, NULL, 0);
    int ix = 0;
    while (ix < BSIZE) // Initializing buffer
        SHM3[ix++] = 0;
  
    struct timeval t;
    time_t t1, t2;
    gettimeofday(&t, NULL);
    t1 = t.tv_sec;
  
    int* state = (int*)shmat(shmid4, NULL, 0);
    *state = 1;
    int wait_time;
  
    int i = 0; // Consumer
    int j = 1; // Producer
  
    if (fork() == 0) // Producer code
    {
        SHM1 = (bool*)shmat(shmid1, NULL, 0);
        SHM2 = (int*)shmat(shmid2, NULL, 0);
        SHM3 = (int*)shmat(shmid3, NULL, 0);
        if (SHM1 == (bool*)-1 || SHM2 == (int*)-1 || SHM3 == (int*)-1) {
            perror("Producer shmat error: ");
            exit(1);
        }
  
        bool* flag = SHM1;
        int* turn = SHM2;
        int* buf = SHM3;
        int index = 0;
  
        while (*state == 1) {
            flag[j] = true;
            printf("Producer is ready now.\n\n");
            *turn = i;
            while (flag[i] == true && *turn == i)
                ;
  
            // Critical Section Begin
            index = 0;
            while (index < BSIZE) {
                if (buf[index] == 0) {
                    int tempo = myrand(BSIZE * 3);
                    printf("Job %d has been produced\n", tempo);
                    buf[index] = tempo;
                    break;
                }
                index++;
            }
            if (index == BSIZE)
                printf("Buffer is full, nothing can be produced!!!\n");
            printf("Buffer: ");
            index = 0;
            while (index < BSIZE)
                printf("%d ", buf[index++]);
            printf("\n");
            // Critical Section End
  
            flag[j] = false;
            if (*state == 0)
                break;
            wait_time = myrand(PWT);
            printf("Producer will wait for %d seconds\n\n", wait_time);
            sleep(wait_time);
        }
        exit(0);
    }
  
    if (fork() == 0) // Consumer code
    {
        SHM1 = (bool*)shmat(shmid1, NULL, 0);
        SHM2 = (int*)shmat(shmid2, NULL, 0);
        SHM3 = (int*)shmat(shmid3, NULL, 0);
        if (SHM1 == (bool*)-1 || SHM2 == (int*)-1 || SHM3 == (int*)-1) {
            perror("Consumer shmat error:");
            exit(1);
        }
  
        bool* flag = SHM1;
        int* turn = SHM2;
        int* buf = SHM3;
        int index = 0;
        flag[i] = false;
        sleep(5);
        while (*state == 1) {
            flag[i] = true;
            printf("Consumer is ready now.\n\n");
            *turn = j;
            while (flag[j] == true && *turn == j)
                ;
  
            // Critical Section Begin
            if (buf[0] != 0) {
                printf("Job %d has been consumed\n", buf[0]);
                buf[0] = 0;
                index = 1;
                while (index < BSIZE) // Shifting remaining jobs forward
                {
                    buf[index - 1] = buf[index];
                    index++;
                }
                buf[index - 1] = 0;
            } else
                printf("Buffer is empty, nothing can be consumed!!!\n");
            printf("Buffer: ");
            index = 0;
            while (index < BSIZE)
                printf("%d ", buf[index++]);
            printf("\n");
            // Critical Section End
  
            flag[i] = false;
            if (*state == 0)
                break;
            wait_time = myrand(CWT);
            printf("Consumer will sleep for %d seconds\n\n", wait_time);
            sleep(wait_time);
        }
        exit(0);
    }
    // Parent process will now for RT seconds before causing child to terminate
    while (1) {
        gettimeofday(&t, NULL);
        t2 = t.tv_sec;
        if (t2 - t1 > RT) // Program will exit after RT seconds
        {
            *state = 0;
            break;
        }
    }
    // Waiting for both processes to exit
    wait();
    wait();
    printf("The clock ran out.\n");
    return 0;
}

Producción:

Producer is ready now.

Job 9 has been produced
Buffer: 9 0 0 0 0 0 0 0 
Producer will wait for 1 seconds

Producer is ready now.

Job 8 has been produced
Buffer: 9 8 0 0 0 0 0 0 
Producer will wait for 2 seconds

Producer is ready now.

Job 13 has been produced
Buffer: 9 8 13 0 0 0 0 0 
Producer will wait for 1 seconds

Producer is ready now.

Job 23 has been produced
Buffer: 9 8 13 23 0 0 0 0 
Producer will wait for 1 seconds

Consumer is ready now.

Job 9 has been consumed
Buffer: 8 13 23 0 0 0 0 0 
Consumer will sleep for 9 seconds

Producer is ready now.

Job 15 has been produced
Buffer: 8 13 23 15 0 0 0 0 
Producer will wait for 1 seconds

Producer is ready now.

Job 13 has been produced
Buffer: 8 13 23 15 13 0 0 0 
Producer will wait for 1 seconds

Producer is ready now.

Job 11 has been produced
Buffer: 8 13 23 15 13 11 0 0 
Producer will wait for 1 seconds

Producer is ready now.

Job 22 has been produced
Buffer: 8 13 23 15 13 11 22 0 
Producer will wait for 2 seconds

Producer is ready now.

Job 23 has been produced
Buffer: 8 13 23 15 13 11 22 23 
Producer will wait for 1 seconds

The clock ran out.

Este artículo es una contribución de Nabaneet Roy . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *