Petersons algoritm för ömsesidig uteslutning | Set 1 (Basic C -implementering)
Problem: Med tanke på 2 processer I och J måste du skriva ett program som kan garantera ömsesidig uteslutning mellan de två utan ytterligare hårdvarustöd.
Lösning: Det kan finnas flera sätt att lösa detta problem men de flesta av dem kräver ytterligare hårdvarustöd. Det enklaste och det mest populära sättet att göra detta är att använda Petersons algoritm för ömsesidig uteslutning. Det utvecklades av Peterson 1981 även om det första arbetet i denna riktning gjordes av Theodorus Jozef Dekker som kom på Cover's algoritm 1960 som senare förfinades av Peterson och blev känd som Petersons algoritm .
I grund och botten ger Petersons algoritm garanterad ömsesidig uteslutning genom att endast använda det delade minnet. Den använder två idéer i algoritmen:
- Villighet att förvärva lås.
- Vänd dig för att skaffa lås.
Nödvändig förutsättning: Multithreading i C
Förklaring : Tanken är att först en tråd uttrycker sin önskan att förvärva ett lås och uppsättningar flagga [själv] = 1 Och ger sedan den andra tråden en chans att skaffa låset. Om tråden önskar att skaffa låset får det låset och överför chansen till den första tråden. Om det inte vill få låset bryts medan slingan och den första tråden får chansen.
Nedanstående kodimplementering använder POSIX -trådarna ( pthread ) vilket är vanligt i C-program och systemprogrammering på lägre nivå men kräver mer manuellt arbete och typekast.
#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.
Produktion:
Thread Entered: 1
Thread Entered: 0
Actual Count: 2000000000 | Expected Count: 2000000000
Den producerade utgången är 2*10 9 där 10 9 ökas av båda trådarna.
Läs mer om Petersons algoritm för ömsesidig uteslutning | Set 2
