logo

Algoritmul lui Peterson pentru excluderea reciprocă | Setul 1 (implementarea de bază C)

Problemă: Având în vedere 2 procese I și J, trebuie să scrieți un program care să poată garanta excluderea reciprocă între cele două, fără niciun suport hardware suplimentar.

Soluţie: Pot exista mai multe modalități de a rezolva această problemă, dar majoritatea necesită suport hardware suplimentar. Cel mai simplu și cel mai popular mod de a face acest lucru este folosind algoritmul lui Peterson pentru excluderea reciprocă. A fost dezvoltat de Peterson în 1981, deși lucrarea inițială în această direcție a fost făcută de Theodorus Jozef Dekker Algoritmul Cover în 1960, care a fost rafinat ulterior de Peterson și a fost cunoscut ca Algoritmul lui Peterson .



Practic, algoritmul lui Peterson oferă o excludere reciprocă garantată prin utilizarea doar a memoriei partajate. Folosește două idei în algoritm:

  1. Voința de a dobândi Lock.
  2. Întoarceți -vă pentru a achiziționa Lock.

Premisă: MultiTithreading în c

Explicaţie : Ideea este că mai întâi un fir își exprimă dorința de a dobândi un blocaj și seturi steag [self] = 1 și apoi oferă celuilalt fir o șansă de a achiziționa blocajul. Dacă firul dorește să dobândească blocajul, acesta primește blocajul și trece șansa primului fir. Dacă nu dorește să obțină blocajul, atunci bucla se rupe și primul fir are șansa.

Implementarea codului de mai jos folosește firele POSIX (pthread) care este frecventă în programele C și în programarea sistemului de nivel inferior, dar necesită mai multă muncă manuală și tipografie.



C++
#include    #include  using namespace std; int flag[2]; int turn; const int MAX = 1e9; int ans = 0; void lock_init() {  flag[0] = flag[1] = 0;  turn = 0; } void lock(int self) {  flag[self] = 1;  turn = 1 - self;  while (flag[1 - self] == 1 && turn == 1 - self); } void unlock(int self) {  flag[self] = 0; } void* func(void* s) {  int i = 0;  int self = (int)s;  cout << 'Thread Entered: ' << self << endl;  lock(self);  for (i = 0; i < MAX; i++)  ans++;  unlock(self);  return nullptr; } int main() {  pthread_t p1 p2;  lock_init();  pthread_create(&p1 nullptr func (void*)0);  pthread_create(&p2 nullptr func (void*)1);  pthread_join(p1 nullptr);  pthread_join(p2 nullptr);  cout << 'Actual Count: ' << ans << ' | Expected Count: ' << MAX * 2 << endl;  return 0; 
C
// 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__ 
Java
import java.util.concurrent.locks.Lock; import java.util.concurrent.locks.ReentrantLock; public class PetersonSpinlockThread {  // Shared variables for mutual exclusion  private static int[] flag = new int[2];  private static int turn;  private static final int MAX = (int) 1e9;  private static int ans = 0;  private static Lock mutex = new ReentrantLock();  // Initialize lock variables  private static void lockInit() {  flag[0] = flag[1] = 0;  turn = 0;  }  // Acquire lock  private static void lock(int self) {  flag[self] = 1;  turn = 1 - self;  // Spin until the other thread releases the lock  while (flag[1 - self] == 1 && turn == 1 - self);  }  // Release lock  private static void unlock(int self) {  flag[self] = 0;  }  // Function representing the critical section  private static void func(int self) {  int i = 0;  System.out.println('Thread Entered: ' + self);  lock(self); // Acquire the lock  for (i = 0; i < MAX; i++)  ans++;  unlock(self); // Release the lock  }  // Main method  public static void main(String[] args) throws InterruptedException {  // Create two threads  Thread t1 = new Thread(() -> func(0));  Thread t2 = new Thread(() -> func(1));  lockInit(); // Initialize lock variables  t1.start(); // Start thread 1  t2.start(); // Start thread 2  t1.join(); // Wait for thread 1 to finish  t2.join(); // Wait for thread 2 to finish  // Print the final count  System.out.println('Actual Count: ' + ans + ' | Expected Count: ' + MAX * 2);  } } 
Python
import threading # Shared variables for mutual exclusion flag = [0 0] turn = 0 MAX = int(1e9) ans = 0 mutex = threading.Lock() # Initialize lock variables def lock_init(): global flag turn flag = [0 0] turn = 0 # Acquire lock def lock(self): global flag turn flag[self] = 1 turn = 1 - self # Spin until the other thread releases the lock while flag[1 - self] == 1 and turn == 1 - self: pass # Release lock def unlock(self): global flag flag[self] = 0 # Function representing the critical section def func(self): global ans i = 0 print(f'Thread Entered: {self}') with mutex: lock(self) # Acquire the lock for i in range(MAX): ans += 1 unlock(self) # Release the lock # Main method def main(): # Create two threads t1 = threading.Thread(target=lambda: func(0)) t2 = threading.Thread(target=lambda: func(1)) lock_init() # Initialize lock variables t1.start() # Start thread 1 t2.start() # Start thread 2 t1.join() # Wait for thread 1 to finish t2.join() # Wait for thread 2 to finish # Print the final count print(f'Actual Count: {ans} | Expected Count: {MAX * 2}') if __name__ == '__main__': main() 
JavaScript
const flag = [0 0]; let turn = 0; const MAX = 1e9; let ans = 0; function lock_init() {  flag[0] = flag[1] = 0;  turn = 0; } function lock(self) {  flag[self] = 1;  turn = 1 - self;  while (flag[1 - self] === 1 && turn === 1 - self); } function unlock(self) {  flag[self] = 0; } async function func(self) {  let i = 0;  console.log('Thread Entered:' self);  lock(self);  for (i = 0; i < MAX; i++)  ans++;  unlock(self); } async function main() {  lock_init();  const promise1 = func(0);  const promise2 = func(1);  await Promise.all([promise1 promise2]);  console.log('Actual Count:' ans '| Expected Count:' MAX * 2); } main(); //This code is contribuited by Prachi. 

Ieșire: 

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

Producția produsă este de 2*109unde 109este incrementat de ambele fire.

Citiți mai multe despre Algoritmul lui Peterson pentru excluderea reciprocă | Set 2
 



șir de caractere java concatenate