Petersonov algoritem za medsebojno izključitev | Set 1 (osnovna izvedba C)
Problem: Glede na 2 procesa I in J morate napisati program, ki lahko zagotovi medsebojno izključitev med obema brez dodatne podpore strojne opreme.
Rešitev: Obstaja več načinov za rešitev te težave, vendar večina zahteva dodatno podporo strojne opreme. Najpreprostejši in najbolj priljubljen način za to je z uporabo Petersonovega algoritma za medsebojno izključitev. Peterson ga je razvil leta 1981, čeprav je začetno delo v tej smeri opravil Theodorus Jozef Dekker, ki je prišel do Algoritem naslovnice Leta 1960, ki ga je kasneje prefišil Peterson in je postal znan kot Petersonov algoritem .
V bistvu Petersonov algoritem zagotavlja zagotovljeno medsebojno izključitev z uporabo samo skupnega pomnilnika. V algoritmu uporablja dve ideji:
- Pripravljenost pridobiti ključavnico.
- Obrnite se za pridobitev ključavnice.
Predpogoj: Multithreading v c
Pojasnilo : Ideja je, da prva nit izraža željo po pridobitvi ključavnice in nastavitve zastava [self] = 1 in nato drugi nit daje možnost, da pridobi ključavnico. Če nit želi pridobiti ključavnico, potem dobi ključavnico in prenese priložnost na 1. nit. Če ne želi dobiti ključavnice, potem se zanka prelomi in prva nit dobi priložnost.
Spodnja izvedba kode uporablja niti Posix ( pthread ), ki je pogosta v programih C in sistemu na nižji ravni, vendar zahteva več ročnega dela in tipanja.
#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.
Izhod:
Thread Entered: 1
Thread Entered: 0
Actual Count: 2000000000 | Expected Count: 2000000000
Izdelani izhod je 2*10 9 kjer 10 9 se poveča z obema nitma.
Preberite več o Petersonov algoritem za medsebojno izključitev | Set 2
