Petersonov algoritam za međusobnu isključenje | SET 1 (osnovna provedba C)
Problem: S obzirom na 2 procesa i i j, morate napisati program koji može jamčiti međusobnu isključenje između njih dvojice bez dodatne hardverske podrške.
Otopina: Može biti više načina za rješavanje ovog problema, ali većina njih zahtijeva dodatnu podršku hardvera. Najjednostavniji i najpopularniji način za to je korištenje Petersonovog algoritma za međusobnu isključenje. Razvio ga je Peterson 1981. godine, iako je početni rad u ovom smjeru obavio Theodor Jozef Dekker koji je smislio Algoritam naslovnice 1960. godine koju je Peterson kasnije rafinirao i postao poznat kao Petersonov algoritam .
U osnovi Petersonov algoritam pruža zajamčeno međusobno isključenje koristeći samo zajedničku memoriju. Koristi dvije ideje u algoritmu:
- Spremnost za stjecanje brave.
- Okrenite se da steknete bravu.
Preduvjet: Multithreading u c
Obrazloženje : Ideja je da prvo nit izražava svoju želju za stjecanjem brave i postavljanja zastava [self] = 1 a zatim drugoj nit daje priliku da nabavi bravu. Ako nit želi nabaviti bravu, tada dobiva bravu i prenosi priliku u 1. nit. Ako ne želi dobiti bravu, tada se petlja probija i prva nit dobiva priliku.
Donja implementacija koda koristi Posix niti ( pthread ) što je uobičajeno u programima C i programiranju niže razine, ali zahtijeva više ručnog rada i tipkanja.
#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.
Izlaz:
Thread Entered: 1
Thread Entered: 0
Actual Count: 2000000000 | Expected Count: 2000000000
Proizvedeni izlaz je 2*10 9 gdje 10 9 Povećava se obje niti.
Pročitajte više o Petersonov algoritam za međusobnu isključenje | Postavite 2
