Requisito previo: sección crítica , sincronización de procesos , comunicación entre procesos
El algoritmo Bakery es una de las soluciones conocidas más simples al problema de exclusión mutua para el caso general de N proceso. Bakery Algorithm es una solución de sección crítica para N procesos. El algoritmo conserva la propiedad por orden de llegada.
- Antes de ingresar a su sección crítica, el proceso recibe un número. El titular del número más pequeño entra en la sección crítica.
- Si los procesos Pi y Pj reciben el mismo número,
if i < j Pi is served first; else Pj is served first.
- El esquema de numeración siempre genera números en orden creciente de enumeración; es decir, 1, 2, 3, 3, 3, 3, 4, 5, …
Notación: orden lexicográfico (n.° de ticket, n.° de id. de proceso): en primer lugar, se compara el número de ticket. Si es igual, el ID del proceso se compara a continuación, es decir,
– (a, b) < (c, d) if a < c or if a = c and b < d – max(a [0], . . ., a [n-1]) is a number, k, such that k >= a[i] for i = 0, . . ., n - 1
Datos compartidos: la elección es una array [0..n – 1] de valores booleanos; & number es una array [0..n – 1] de valores enteros. Ambos se inicializan en Falso y Cero respectivamente.
Pseudocódigo de algoritmo –
repeat
choosing[i] := true;
number[i] := max(number[0], number[1], ..., number[n - 1])+1;
choosing[i] := false;
for j := 0 to n - 1
do begin
while choosing[j] do no-op;
while number[j] != 0
and (number[j], j) < (number[i], i) do no-op;
end;
critical section
number[i] := 0;
remainder section
until false;
Explicación:
en primer lugar, el proceso establece que su variable de «selección» sea VERDADERA, lo que indica su intención de ingresar a la sección crítica. Luego se le asigna el número de ticket más alto correspondiente a otros procesos. Luego, la variable «elegir» se establece en FALSO, lo que indica que ahora tiene un nuevo número de boleto. Esta es, de hecho, la parte más importante y confusa del algoritmo.
¡En realidad es una pequeña sección crítica en sí misma! El propósito mismo de las primeras tres líneas es que si un proceso está modificando su valor de BOLETO, en ese momento no se debe permitir que otro proceso verifique su valor de boleto anterior, que ahora está obsoleto. Es por eso que dentro del ciclo for antes de verificar el valor del ticket, primero nos aseguramos de que todos los demás procesos tengan la variable «elegir» como FALSO.
Después de eso, procedemos a verificar los valores de los tickets de los procesos donde el proceso con el menor número de ticket/ID de proceso entra en la sección crítica. La sección de salida simplemente restablece el valor del boleto a cero.
Código: aquí está la implementación del código C del algoritmo de panadería. Ejecute lo siguiente en un entorno UNIX :
// Importing the thread library
#include "pthread.h"
#include "stdio.h"
// Importing POSIX Operating System API library
#include "unistd.h"
#include "string.h"
// This is a memory barrier instruction.
// Causes compiler to enforce an ordering
// constraint on memory operations.
// This means that operations issued prior
// to the barrier will be performed
// before operations issued after the barrier.
#define MEMBAR __sync_synchronize()
#define THREAD_COUNT 8
volatile int tickets[THREAD_COUNT];
volatile int choosing[THREAD_COUNT];
// VOLATILE used to prevent the compiler
// from applying any optimizations.
volatile int resource;
void lock(int thread)
{
// Before getting the ticket number
//"choosing" variable is set to be true
choosing[thread] = 1;
MEMBAR;
// Memory barrier applied
int max_ticket = 0;
// Finding Maximum ticket value among current threads
for (int i = 0; i < THREAD_COUNT; ++i) {
int ticket = tickets[i];
max_ticket = ticket > max_ticket ? ticket : max_ticket;
}
// Allotting a new ticket value as MAXIMUM + 1
tickets[thread] = max_ticket + 1;
MEMBAR;
choosing[thread] = 0;
MEMBAR;
// The ENTRY Section starts from here
for (int other = 0; other < THREAD_COUNT; ++other) {
// Applying the bakery algorithm conditions
while (choosing[other]) {
}
MEMBAR;
while (tickets[other] != 0 && (tickets[other]
< tickets[thread]
|| (tickets[other]
== tickets[thread]
&& other < thread))) {
}
}
}
// EXIT Section
void unlock(int thread)
{
MEMBAR;
tickets[thread] = 0;
}
// The CRITICAL Section
void use_resource(int thread)
{
if (resource != 0) {
printf("Resource was acquired by %d, but is still in-use by %d!\n",
thread, resource);
}
resource = thread;
printf("%d using resource...\n", thread);
MEMBAR;
sleep(2);
resource = 0;
}
// A simplified function to show the implementation
void* thread_body(void* arg)
{
long thread = (long)arg;
lock(thread);
use_resource(thread);
unlock(thread);
return NULL;
}
int main(int argc, char** argv)
{
memset((void*)tickets, 0, sizeof(tickets));
memset((void*)choosing, 0, sizeof(choosing));
resource = 0;
// Declaring the thread variables
pthread_t threads[THREAD_COUNT];
for (int i = 0; i < THREAD_COUNT; ++i) {
// Creating a new thread with the function
//"thread_body" as its thread routine
pthread_create(&threads[i], NULL, &thread_body, (void*)((long)i));
}
for (int i = 0; i < THREAD_COUNT; ++i) {
// Reaping the resources used by
// all threads once their task is completed !
pthread_join(threads[i], NULL);
}
return 0;
}
Producción:
Publicación traducida automáticamente
Artículo escrito por Siddhant-Bajaj y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA