ALGORITMO DE PETERSON PARA LA EXCLUSIÓN MUTUA | CONJUNTO 2 (CICLOS DE CPU Y BARRERA DE MEMORIA)

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

Desperdicio de ciclos de reloj de la CPU

En términos sencillos, cuando un hilo estaba esperando su turno, terminaba en un largo bucle while que probaba la condición millones de veces por segundo, realizando así cálculos innecesarios. Hay una mejor manera de esperar y se conoce como 'producir' .

Para comprender qué hace, debemos profundizar en cómo funciona el programador de procesos en Linux. La idea mencionada aquí es una versión simplificada del programador; la implementación real tiene muchas complicaciones.

Considere el siguiente ejemplo
Hay tres procesos P1 P2 y P3. El proceso P3 es tal que tiene un bucle while similar al de nuestro código que no realiza cálculos tan útiles y existe desde el bucle solo cuando P2 finaliza su ejecución. El programador los coloca a todos en una cola de todos contra todos. Ahora digamos que la velocidad del reloj del procesador es 1000000/seg y asigna 100 relojes a cada proceso en cada iteración. Luego, primero se ejecutará P1 durante 100 relojes (0,0001 segundos), luego P2 (0,0001 segundos) seguido de P3 (0,0001 segundos). Ahora, dado que no hay más procesos, este ciclo se repite hasta que P2 finaliza y luego sigue la ejecución de P3 y, finalmente, su terminación.

Esto es una completa pérdida de los 100 ciclos de reloj de la CPU. Para evitar esto, renunciamos mutuamente al intervalo de tiempo de la CPU, es decir, al rendimiento, que esencialmente finaliza este intervalo de tiempo y el programador selecciona el siguiente proceso para ejecutar. Ahora probamos nuestra condición una vez y luego abandonamos la CPU. Teniendo en cuenta que nuestra prueba requiere 25 ciclos de reloj, ahorramos el 75% de nuestro cálculo en un intervalo de tiempo. Para poner esto gráficamente

Algoritmo de Peterson para la exclusión mutua | Conjunto 2 (ciclos de CPU y barrera de memoria)

Teniendo en cuenta que la velocidad del reloj del procesador es de 1 MHz, ¡esto supone un gran ahorro!
Diferentes distribuciones proporcionan diferentes funciones para lograr esta funcionalidad. Linux proporciona sched_yield() .

void lock(int self) {  flag[self] = 1;  turn = 1-self;  while (flag[1-self] == 1 &&  turn == 1-self)    // Only change is the addition of  // sched_yield() call  sched_yield(); }

Valla de la memoria.

Es posible que el código del tutorial anterior haya funcionado en la mayoría de los sistemas, pero no era 100% correcto. La lógica era perfecta, pero la mayoría de las CPU modernas emplean optimizaciones de rendimiento que pueden provocar una ejecución desordenada. Esta reordenación de las operaciones de memoria (cargas y almacenes) normalmente pasa desapercibida dentro de un único hilo de ejecución, pero puede provocar un comportamiento impredecible en programas concurrentes.
Considere este ejemplo

C while (f == 0); // Memory fence required here print x;

En el ejemplo anterior, el compilador considera las 2 declaraciones independientes entre sí y, por lo tanto, intenta aumentar la eficiencia del código reordenándolas, lo que puede generar problemas para programas concurrentes. Para evitar esto, colocamos una barrera de memoria para darle una pista al compilador sobre la posible relación entre las declaraciones a través de la barrera.

Entonces el orden de las declaraciones

bandera[yo] = 1;
turno = 1-yo;
while (verificación de condición de giro)
producir();

tiene que ser exactamente el mismo para que el bloqueo funcione, de lo contrario terminará en una condición de punto muerto.

Para garantizar que esto, los compiladores proporcionen una instrucción que evite el orden de declaraciones a través de esta barrera. En el caso de gcc es __sync_synchronize() .
Entonces el código modificado se convierte en
Implementación completa en C:

C++

// Filename: peterson_yieldlock_memoryfence.cpp // Use below command to compile: // g++ -pthread peterson_yieldlock_memoryfence.cpp -o peterson_yieldlock_memoryfence #include   #include #include   std::atomic<int> flag[2]; std::atomic<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;  // Memory fence to prevent the reordering  // of instructions beyond this barrier.  std::atomic_thread_fence(std::memory_order_seq_cst);  // Wait until the other thread loses the  // desire to acquire lock or it is your  // turn to get the lock.  while (flag[1-self]==1 && turn==1-self)  // Yield to avoid wastage of resources.  std::this_thread::yield(); } // 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(int s) {  int i = 0;  int self = s;  std::cout << 'Thread Entered: ' << self << std::endl;  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() {   // Initialize the lock   lock_init();  // Create two threads (both run func)  std::thread t1(func 0);  std::thread t2(func 1);  // Wait for the threads to end.  t1.join();  t2.join();  std::cout << 'Actual Count: ' << ans << ' | Expected Count: ' << MAX*2 << std::endl;  return 0; }

// Filename: peterson_yieldlock_memoryfence.c // Use below command to compile: // gcc -pthread peterson_yieldlock_memoryfence.c -o peterson_yieldlock_memoryfence #include #include #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;  // Memory fence to prevent the reordering  // of instructions beyond this barrier.  __sync_synchronize();  // Wait until the other thread loses the  // desire to acquire lock or it is your  // turn to get the lock.  while (flag[1-self]==1 && turn==1-self)  // Yield to avoid wastage of resources.  sched_yield(); } // 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: %dn'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() {   pthread_t p1 p2;  // Initialize the lock   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:'  ' %dn'ansMAX*2);  return 0; }

Java

import java.util.concurrent.atomic.AtomicInteger; public class PetersonYieldLockMemoryFence {  static AtomicInteger[] flag = new AtomicInteger[2];  static AtomicInteger turn = new AtomicInteger();  static final int MAX = 1000000000;  static int ans = 0;  static void lockInit() {  flag[0] = new AtomicInteger();  flag[1] = new AtomicInteger();  flag[0].set(0);  flag[1].set(0);  turn.set(0);  }  static void lock(int self) {  flag[self].set(1);  turn.set(1 - self);  // Memory fence to prevent the reordering of instructions beyond this barrier.  // In Java volatile variables provide this guarantee implicitly.  // No direct equivalent to atomic_thread_fence is needed.  while (flag[1 - self].get() == 1 && turn.get() == 1 - self)  Thread.yield();  }  static void unlock(int self) {  flag[self].set(0);  }  static void func(int s) {  int i = 0;  int self = s;  System.out.println('Thread Entered: ' + self);  lock(self);  // Critical section (Only one thread can enter here at a time)  for (i = 0; i < MAX; i++)  ans++;  unlock(self);  }  public static void main(String[] args) {  // Initialize the lock  lockInit();  // Create two threads (both run func)  Thread t1 = new Thread(() -> func(0));  Thread t2 = new Thread(() -> func(1));  // Start the threads  t1.start();  t2.start();  try {  // Wait for the threads to end.  t1.join();  t2.join();  } catch (InterruptedException e) {  e.printStackTrace();  }  System.out.println('Actual Count: ' + ans + ' | Expected Count: ' + MAX * 2);  } }

Python

import threading flag = [0 0] turn = 0 MAX = 10**9 ans = 0 def lock_init(): # This function initializes the lock by resetting the flags and turn. global flag turn flag = [0 0] turn = 0 def lock(self): # This function is executed before entering the critical section. It sets the flag for the current thread and gives the turn to the other thread. global flag turn flag[self] = 1 turn = 1 - self while flag[1-self] == 1 and turn == 1-self: pass def unlock(self): # This function is executed after leaving the critical section. It resets the flag for the current thread. global flag flag[self] = 0 def func(s): # This function is executed by each thread. It locks the critical section increments the shared variable and then unlocks the critical section. global ans self = s print(f'Thread Entered: {self}') lock(self) for _ in range(MAX): ans += 1 unlock(self) def main(): # This is the main function where the threads are created and started. lock_init() t1 = threading.Thread(target=func args=(0)) t2 = threading.Thread(target=func args=(1)) t1.start() t2.start() t1.join() t2.join() print(f'Actual Count: {ans} | Expected Count: {MAX*2}') if __name__ == '__main__': main()

JavaScript

class PetersonYieldLockMemoryFence {  static flag = [0 0];  static turn = 0;  static MAX = 1000000000;  static ans = 0;  // Function to acquire the lock  static async lock(self) {  PetersonYieldLockMemoryFence.flag[self] = 1;  PetersonYieldLockMemoryFence.turn = 1 - self;  // Asynchronous loop with a small delay to yield  while (PetersonYieldLockMemoryFence.flag[1 - self] == 1 &&  PetersonYieldLockMemoryFence.turn == 1 - self) {  await new Promise(resolve => setTimeout(resolve 0));  }  }  // Function to release the lock  static unlock(self) {  PetersonYieldLockMemoryFence.flag[self] = 0;  }  // Function representing the critical section  static func(s) {  let i = 0;  let self = s;  console.log('Thread Entered: ' + self);    // Lock the critical section  PetersonYieldLockMemoryFence.lock(self).then(() => {  // Critical section (Only one thread can enter here at a time)  for (i = 0; i < PetersonYieldLockMemoryFence.MAX; i++) {  PetersonYieldLockMemoryFence.ans++;  }    // Release the lock  PetersonYieldLockMemoryFence.unlock(self);  });  }  // Main function  static main() {  // Create two threads (both run func)  const t1 = new Thread(() => PetersonYieldLockMemoryFence.func(0));  const t2 = new Thread(() => PetersonYieldLockMemoryFence.func(1));  // Start the threads  t1.start();  t2.start();  // Wait for the threads to end.  setTimeout(() => {  console.log('Actual Count: ' + PetersonYieldLockMemoryFence.ans + ' | Expected Count: ' + PetersonYieldLockMemoryFence.MAX * 2);  } 1000); // Delay for a while to ensure threads finish  } } // Define a simple Thread class for simulation class Thread {  constructor(func) {  this.func = func;  }  start() {  this.func();  } } // Run the main function PetersonYieldLockMemoryFence.main();

C++

// mythread.h (A wrapper header file with assert statements) #ifndef __MYTHREADS_h__ #define __MYTHREADS_h__ #include  #include  #include  // Function to lock a pthread mutex void Pthread_mutex_lock(pthread_mutex_t *m) {  int rc = pthread_mutex_lock(m);  assert(rc == 0); // Assert that the mutex was locked successfully }   // Function to unlock a pthread mutex void Pthread_mutex_unlock(pthread_mutex_t *m) {  int rc = pthread_mutex_unlock(m);  assert(rc == 0); // Assert that the mutex was unlocked successfully }   // Function to create a pthread 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); // Assert that the thread was created successfully } // Function to join a pthread void Pthread_join(pthread_t thread void **value_ptr) {  int rc = pthread_join(thread value_ptr);  assert(rc == 0); // Assert that the thread was joined successfully } #endif // __MYTHREADS_h__

// mythread.h (A wrapper header file with assert // statements) #ifndef __MYTHREADS_h__ #define __MYTHREADS_h__ #include  #include    #include  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__

Python

import threading import ctypes # Function to lock a thread lock def Thread_lock(lock): lock.acquire() # Acquire the lock # No need for assert in Python acquire will raise an exception if it fails # Function to unlock a thread lock def Thread_unlock(lock): lock.release() # Release the lock # No need for assert in Python release will raise an exception if it fails # Function to create a thread def Thread_create(target args=()): thread = threading.Thread(target=target args=args) thread.start() # Start the thread # No need for assert in Python thread.start() will raise an exception if it fails # Function to join a thread def Thread_join(thread): thread.join() # Wait for the thread to finish # No need for assert in Python thread.join() will raise an exception if it fails

Producción:

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