Algoritmo de Peterson para exclusión mutua | Conjunto 1 (Implementación básica de C)

Problema: dados 2 procesos i y j, debe escribir un programa que pueda garantizar la exclusión mutua entre los dos sin ningún soporte de hardware adicional.

Solución: puede haber varias formas de resolver este problema, pero la mayoría de ellas requieren soporte de hardware adicional. La forma más sencilla y popular de hacerlo es mediante el algoritmo de Peterson para la exclusión mutua. Fue desarrollado por Peterson en 1981, aunque el trabajo inicial en esta dirección fue realizado por Theodorus Jozef Dekker, quien ideó el algoritmo de Dekker en 1960, que luego fue refinado por Peterson y se conoció como el Algoritmo de Peterson .

Básicamente, el algoritmo de Peterson proporciona una exclusión mutua garantizada al usar solo la memoria compartida. Utiliza dos ideas en el algoritmo:

1. Voluntad de adquirir candado.
2. Gire para adquirir bloqueo.

Requisito previo: subprocesos múltiples en C

Explicación:

La idea es que primero un subproceso exprese su deseo de adquirir un bloqueo y establezca flag[self] = 1 y luego le dé al otro subproceso la oportunidad de adquirir el bloqueo. Si el subproceso desea adquirir el bloqueo, obtiene el bloqueo y pasa la oportunidad al primer subproceso. Si no desea obtener el bloqueo, el ciclo while se rompe y el primer subproceso tiene la oportunidad.

Implementación en lenguaje C 

// Filename: peterson_spinlock.c
// Use below command to compile:
// gcc -pthread peterson_spinlock.c -o peterson_spinlock
 
#include <stdio.h>
#include <pthread.h>
#include"mythreads.h"
 
int flag[2];
int turn;
const int MAX = 1e9;
int ans = 0;
 
void lock_init()
{
    // Initialize lock by resetting the desire of
    // both the threads to acquire the locks.
    // And, giving turn to one of them.
    flag[0] = flag[1] = 0;
    turn = 0;
}
 
// Executed before entering critical section
void lock(int self)
{
    // Set flag[self] = 1 saying you want to acquire lock
    flag[self] = 1;
 
    // But, first give the other thread the chance to
    // acquire lock
    turn = 1-self;
 
    // Wait until the other thread looses the desire
    // to acquire lock or it is your turn to get the lock.
    while (flag[1-self]==1 && turn==1-self) ;
}
 
// Executed after leaving critical section
void unlock(int self)
{
    // You do not desire to acquire lock in future.
    // This will allow the other thread to acquire
    // the lock.
    flag[self] = 0;
}
 
// A Sample function run by two threads created
// in main()
void* func(void *s)
{
    int i = 0;
    int self = (int *)s;
    printf("Thread Entered: %d\n", self);
 
    lock(self);
 
    // Critical section (Only one thread
    // can enter here at a time)
    for (i=0; i<MAX; i++)
        ans++;
 
    unlock(self);
}
 
// Driver code
int main()
{
    // Initialized the lock then fork 2 threads
    pthread_t p1, p2;
    lock_init();
 
    // Create two threads (both run func)
    pthread_create(&p1, NULL, func, (void*)0);
    pthread_create(&p2, NULL, func, (void*)1);
 
    // Wait for the threads to end.
    pthread_join(p1, NULL);
    pthread_join(p2, NULL);
 
    printf("Actual Count: %d | Expected Count: %d\n",
                                        ans, MAX*2);
 
    return 0;
}

// mythread.h (A wrapper header file with assert
// statements)
#ifndef __MYTHREADS_h__
#define __MYTHREADS_h__
 
#include <pthread.h>
#include <assert.h>
#include <sched.h>
 
void Pthread_mutex_lock(pthread_mutex_t *m)
{
    int rc = pthread_mutex_lock(m);
    assert(rc == 0);
}
                                                                                 
void Pthread_mutex_unlock(pthread_mutex_t *m)
{
    int rc = pthread_mutex_unlock(m);
    assert(rc == 0);
}
                                                                                 
void Pthread_create(pthread_t *thread, const pthread_attr_t *attr,    
           void *(*start_routine)(void*), void *arg)
{
    int rc = pthread_create(thread, attr, start_routine, arg);
    assert(rc == 0);
}
 
void Pthread_join(pthread_t thread, void **value_ptr)
{
    int rc = pthread_join(thread, value_ptr);
    assert(rc == 0);
}
 
#endif // __MYTHREADS_h__

Producción: 

Thread Entered: 1
Thread Entered: 0
Actual Count: 2000000000 | Expected Count: 2000000000

La salida producida es 2*10 ⁹ donde 10 ⁹ se incrementa en ambos subprocesos.

Este artículo es una contribución de Pinkesh Badjatiya . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@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.