Petersonin algoritmi keskinäiseen syrjäytymiseen | Aseta 1 (perus C -toteutus)
Ongelma: Annetaan 2 prosessia I ja J, sinun on kirjoitettava ohjelma, joka voi taata keskinäisen poissulkemisen näiden kahden välillä ilman lisälaitteistotukea.
Ratkaisu: Tämän ongelman ratkaisemiseksi voi olla useita tapoja, mutta suurin osa niistä vaatii lisälaitteistotukea. Yksinkertaisin ja suosituin tapa tehdä tämä on käyttää Petersonin algoritmia keskinäiseen syrjäytymiseen. Sen kehitti Peterson vuonna 1981, vaikka tämän suuntaan alkuperäisen työn teki Theodorus Jozef Dekker, joka keksi Kannen algoritmi Vuonna 1960, jonka Peterson myöhemmin puhdisti ja tuli tunnetuksi nimellä Petersonin algoritmi .
Pohjimmiltaan Petersonin algoritmi tarjoaa taatun keskinäisen poissulkemisen käyttämällä vain jaettua muistia. Se käyttää kahta ideaa algoritmissa:
- Halukkuus hankkia lukko.
- Käänny hankkia lukko.
Edellytys: Monisäikeinen luja C: ssä
Selitys : Ajatuksena on, että ensin ketju ilmaisee haluavansa lukko ja asettaa lippu [itse] = 1 ja antaa sitten toiselle säielle mahdollisuuden hankkia lukko. Jos lanka haluaa hankkia lukon, se saa lukon ja siirtää mahdollisuuden 1. säieeseen. Jos se ei halua saada lukkoa, niin silmukka rikkoutuu ja 1. säie saa mahdollisuuden.
Alla oleva koodin toteutus käyttää POSIX -ketjuja ( pthread ), joka on yleistä C-ohjelmissa ja alemman tason järjestelmän ohjelmointi, mutta vaatii enemmän manuaalista työtä ja typisting.
#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.
Lähtö:
Thread Entered: 1
Thread Entered: 0
Actual Count: 2000000000 | Expected Count: 2000000000
Tuotettu lähtö on 2*10 9 missä 10 9 sitä lisäävät molemmat säikeet.
Lukea lisää jstk Petersonin algoritmi keskinäiseen syrjäytymiseen | Set 2
