상호 배제를 위한 피터슨의 알고리즘 | 세트 2(CPU 사이클 및 메모리 펜스)
문제: 2개의 프로세스 i와 j가 주어지면 추가 하드웨어 지원 없이 둘 사이의 상호 배제를 보장할 수 있는 프로그램을 작성해야 합니다.
CPU 클럭 사이클 낭비
일반인의 관점에서 보면 스레드가 차례를 기다리고 있을 때 조건을 초당 수백만 번 테스트하여 불필요한 계산을 수행하는 긴 while 루프로 종료되었습니다. 기다리는 더 좋은 방법이 있으며 그것은 다음과 같이 알려져 있습니다. '생산하다' .
이것이 무엇을 하는지 이해하려면 프로세스 스케줄러가 Linux에서 어떻게 작동하는지 자세히 살펴봐야 합니다. 여기에 언급된 아이디어는 스케줄러의 단순화된 버전이지만 실제 구현에는 많은 복잡성이 있습니다.
다음 예를 고려하십시오
P1, P2, P3의 세 가지 프로세스가 있습니다. 프로세스 P3에는 유용하지 않은 계산을 수행하는 코드와 유사한 while 루프가 있으며 P2가 실행을 완료할 때만 루프에서 존재합니다. 스케줄러는 모든 항목을 라운드 로빈 대기열에 넣습니다. 이제 프로세서의 클럭 속도가 1000000/초이고 각 반복에서 각 프로세스에 100개의 클럭을 할당한다고 가정합니다. 그런 다음 첫 번째 P1은 100클럭(0.0001초) 동안 실행되고 그 다음에는 P2(0.0001초), 그 다음에는 P3(0.0001초)가 실행됩니다. 이제 더 이상 프로세스가 없기 때문에 이 주기는 P2가 끝날 때까지 반복된 다음 P3의 실행과 결국 종료가 이어집니다.
이는 100개의 CPU 클럭 사이클을 완전히 낭비하는 것입니다. 이를 방지하기 위해 우리는 CPU 시간 조각, 즉 본질적으로 이 시간 조각을 종료하는 항복을 상호 포기하고 스케줄러는 실행할 다음 프로세스를 선택합니다. 이제 조건을 한 번 테스트한 다음 CPU를 포기합니다. 테스트에 25클럭 사이클이 소요된다는 점을 고려하면 시간 분할에서 계산의 75%를 절약할 수 있습니다. 이것을 그래픽으로 표현하자면
프로세서 클럭 속도를 1MHz로 고려하면 이는 많은 절약 효과입니다!.
다양한 배포판은 이 기능을 달성하기 위해 다양한 기능을 제공합니다. 리눅스가 제공하는 sched_yield() .
void lock ( int self ) { flag [ self ] = 1 ; turn = 1 - self ; while ( flag [ 1 - self ] == 1 && turn == 1 - self ) // Only change is the addition of // sched_yield() call sched_yield (); }
기억의 울타리.
이전 튜토리얼의 코드는 대부분의 시스템에서 작동했을 수도 있지만 100% 정확하지는 않습니다. 논리는 완벽했지만 대부분의 최신 CPU는 잘못된 실행을 초래할 수 있는 성능 최적화를 사용합니다. 메모리 작업(로드 및 저장)의 이러한 재정렬은 일반적으로 단일 실행 스레드 내에서 눈에 띄지 않지만 동시 프로그램에서 예측할 수 없는 동작을 일으킬 수 있습니다.
이 예를 고려하십시오
while ( f == 0 ); // Memory fence required here print x ;
위의 예에서 컴파일러는 두 문을 서로 독립적인 것으로 간주하고 순서를 변경하여 코드 효율성을 높이려고 시도하며 이는 동시 프로그램에 문제가 발생할 수 있습니다. 이를 방지하기 위해 우리는 장벽을 가로지르는 명령문 간의 가능한 관계에 대한 힌트를 컴파일러에 제공하기 위해 메모리 울타리를 배치합니다.
그래서 진술 순서는
플래그[self] = 1;
턴 = 1-자기;
while(회전 상태 확인)
생산하다();
잠금이 작동하려면 정확히 동일해야 합니다. 그렇지 않으면 교착 상태가 발생하게 됩니다.
이 컴파일러는 이 장벽을 넘어 명령문의 순서를 지정하지 않는 명령을 제공합니다. gcc의 경우 __sync_synchronize() .
따라서 수정된 코드는 다음과 같습니다.
C로 전체 구현:
// Filename: peterson_yieldlock_memoryfence.cpp // Use below command to compile: // g++ -pthread peterson_yieldlock_memoryfence.cpp -o peterson_yieldlock_memoryfence #include #include #include std :: atomic < int > flag [ 2 ]; std :: atomic < int > turn ; const int MAX = 1e9 ; int ans = 0 ; void lock_init () { // Initialize lock by resetting the desire of // both the threads to acquire the locks. // And giving turn to one of them. flag [ 0 ] = flag [ 1 ] = 0 ; turn = 0 ; } // Executed before entering critical section void lock ( int self ) { // Set flag[self] = 1 saying you want // to acquire lock flag [ self ] = 1 ; // But first give the other thread the // chance to acquire lock turn = 1 - self ; // Memory fence to prevent the reordering // of instructions beyond this barrier. std :: atomic_thread_fence ( std :: memory_order_seq_cst ); // Wait until the other thread loses the // desire to acquire lock or it is your // turn to get the lock. while ( flag [ 1 - self ] == 1 && turn == 1 - self ) // Yield to avoid wastage of resources. std :: this_thread :: yield (); } // Executed after leaving critical section void unlock ( int self ) { // You do not desire to acquire lock in future. // This will allow the other thread to acquire // the lock. flag [ self ] = 0 ; } // A Sample function run by two threads created // in main() void func ( int s ) { int i = 0 ; int self = s ; std :: cout < < 'Thread Entered: ' < < self < < std :: endl ; lock ( self ); // Critical section (Only one thread // can enter here at a time) for ( i = 0 ; i < MAX ; i ++ ) ans ++ ; unlock ( self ); } // Driver code int main () { // Initialize the lock lock_init (); // Create two threads (both run func) std :: thread t1 ( func 0 ); std :: thread t2 ( func 1 ); // Wait for the threads to end. t1 . join (); t2 . join (); std :: cout < < 'Actual Count: ' < < ans < < ' | Expected Count: ' < < MAX * 2 < < std :: endl ; return 0 ; }
C // Filename: peterson_yieldlock_memoryfence.c // Use below command to compile: // gcc -pthread peterson_yieldlock_memoryfence.c -o peterson_yieldlock_memoryfence #include #include #include 'mythreads.h' int flag [ 2 ]; int turn ; const int MAX = 1e9 ; int ans = 0 ; void lock_init () { // Initialize lock by resetting the desire of // both the threads to acquire the locks. // And giving turn to one of them. flag [ 0 ] = flag [ 1 ] = 0 ; turn = 0 ; } // Executed before entering critical section void lock ( int self ) { // Set flag[self] = 1 saying you want // to acquire lock flag [ self ] = 1 ; // But first give the other thread the // chance to acquire lock turn = 1 - self ; // Memory fence to prevent the reordering // of instructions beyond this barrier. __sync_synchronize (); // Wait until the other thread loses the // desire to acquire lock or it is your // turn to get the lock. while ( flag [ 1 - self ] == 1 && turn == 1 - self ) // Yield to avoid wastage of resources. sched_yield (); } // Executed after leaving critical section void unlock ( int self ) { // You do not desire to acquire lock in future. // This will allow the other thread to acquire // the lock. flag [ self ] = 0 ; } // A Sample function run by two threads created // in main() void * func ( void * s ) { int i = 0 ; int self = ( int * ) s ; printf ( 'Thread Entered: %d n ' self ); lock ( self ); // Critical section (Only one thread // can enter here at a time) for ( i = 0 ; i < MAX ; i ++ ) ans ++ ; unlock ( self ); } // Driver code int main () { pthread_t p1 p2 ; // Initialize the lock lock_init (); // Create two threads (both run func) Pthread_create ( & p1 NULL func ( void * ) 0 ); Pthread_create ( & p2 NULL func ( void * ) 1 ); // Wait for the threads to end. Pthread_join ( p1 NULL ); Pthread_join ( p2 NULL ); printf ( 'Actual Count: %d | Expected Count:' ' %d n ' ans MAX * 2 ); return 0 ; }
Java import java.util.concurrent.atomic.AtomicInteger ; public class PetersonYieldLockMemoryFence { static AtomicInteger [] flag = new AtomicInteger [ 2 ] ; static AtomicInteger turn = new AtomicInteger (); static final int MAX = 1000000000 ; static int ans = 0 ; static void lockInit () { flag [ 0 ] = new AtomicInteger (); flag [ 1 ] = new AtomicInteger (); flag [ 0 ] . set ( 0 ); flag [ 1 ] . set ( 0 ); turn . set ( 0 ); } static void lock ( int self ) { flag [ self ] . set ( 1 ); turn . set ( 1 - self ); // Memory fence to prevent the reordering of instructions beyond this barrier. // In Java volatile variables provide this guarantee implicitly. // No direct equivalent to atomic_thread_fence is needed. while ( flag [ 1 - self ] . get () == 1 && turn . get () == 1 - self ) Thread . yield (); } static void unlock ( int self ) { flag [ self ] . set ( 0 ); } static void func ( int s ) { int i = 0 ; int self = s ; System . out . println ( 'Thread Entered: ' + self ); lock ( self ); // Critical section (Only one thread can enter here at a time) for ( i = 0 ; i < MAX ; i ++ ) ans ++ ; unlock ( self ); } public static void main ( String [] args ) { // Initialize the lock lockInit (); // Create two threads (both run func) Thread t1 = new Thread (() -> func ( 0 )); Thread t2 = new Thread (() -> func ( 1 )); // Start the threads t1 . start (); t2 . start (); try { // Wait for the threads to end. t1 . join (); t2 . join (); } catch ( InterruptedException e ) { e . printStackTrace (); } System . out . println ( 'Actual Count: ' + ans + ' | Expected Count: ' + MAX * 2 ); } }
Python import threading flag = [ 0 0 ] turn = 0 MAX = 10 ** 9 ans = 0 def lock_init (): # This function initializes the lock by resetting the flags and turn. global flag turn flag = [ 0 0 ] turn = 0 def lock ( self ): # This function is executed before entering the critical section. It sets the flag for the current thread and gives the turn to the other thread. global flag turn flag [ self ] = 1 turn = 1 - self while flag [ 1 - self ] == 1 and turn == 1 - self : pass def unlock ( self ): # This function is executed after leaving the critical section. It resets the flag for the current thread. global flag flag [ self ] = 0 def func ( s ): # This function is executed by each thread. It locks the critical section increments the shared variable and then unlocks the critical section. global ans self = s print ( f 'Thread Entered: { self } ' ) lock ( self ) for _ in range ( MAX ): ans += 1 unlock ( self ) def main (): # This is the main function where the threads are created and started. lock_init () t1 = threading . Thread ( target = func args = ( 0 )) t2 = threading . Thread ( target = func args = ( 1 )) t1 . start () t2 . start () t1 . join () t2 . join () print ( f 'Actual Count: { ans } | Expected Count: { MAX * 2 } ' ) if __name__ == '__main__' : main ()
JavaScript class PetersonYieldLockMemoryFence { static flag = [ 0 0 ]; static turn = 0 ; static MAX = 1000000000 ; static ans = 0 ; // Function to acquire the lock static async lock ( self ) { PetersonYieldLockMemoryFence . flag [ self ] = 1 ; PetersonYieldLockMemoryFence . turn = 1 - self ; // Asynchronous loop with a small delay to yield while ( PetersonYieldLockMemoryFence . flag [ 1 - self ] == 1 && PetersonYieldLockMemoryFence . turn == 1 - self ) { await new Promise ( resolve => setTimeout ( resolve 0 )); } } // Function to release the lock static unlock ( self ) { PetersonYieldLockMemoryFence . flag [ self ] = 0 ; } // Function representing the critical section static func ( s ) { let i = 0 ; let self = s ; console . log ( 'Thread Entered: ' + self ); // Lock the critical section PetersonYieldLockMemoryFence . lock ( self ). then (() => { // Critical section (Only one thread can enter here at a time) for ( i = 0 ; i < PetersonYieldLockMemoryFence . MAX ; i ++ ) { PetersonYieldLockMemoryFence . ans ++ ; } // Release the lock PetersonYieldLockMemoryFence . unlock ( self ); }); } // Main function static main () { // Create two threads (both run func) const t1 = new Thread (() => PetersonYieldLockMemoryFence . func ( 0 )); const t2 = new Thread (() => PetersonYieldLockMemoryFence . func ( 1 )); // Start the threads t1 . start (); t2 . start (); // Wait for the threads to end. setTimeout (() => { console . log ( 'Actual Count: ' + PetersonYieldLockMemoryFence . ans + ' | Expected Count: ' + PetersonYieldLockMemoryFence . MAX * 2 ); } 1000 ); // Delay for a while to ensure threads finish } } // Define a simple Thread class for simulation class Thread { constructor ( func ) { this . func = func ; } start () { this . func (); } } // Run the main function PetersonYieldLockMemoryFence . main ();
C++ // mythread.h (A wrapper header file with assert statements) #ifndef __MYTHREADS_h__ #define __MYTHREADS_h__ #include #include #include // Function to lock a pthread mutex void Pthread_mutex_lock ( pthread_mutex_t * m ) { int rc = pthread_mutex_lock ( m ); assert ( rc == 0 ); // Assert that the mutex was locked successfully } // Function to unlock a pthread mutex void Pthread_mutex_unlock ( pthread_mutex_t * m ) { int rc = pthread_mutex_unlock ( m ); assert ( rc == 0 ); // Assert that the mutex was unlocked successfully } // Function to create a pthread 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 ); // Assert that the thread was created successfully } // Function to join a pthread void Pthread_join ( pthread_t thread void ** value_ptr ) { int rc = pthread_join ( thread value_ptr ); assert ( rc == 0 ); // Assert that the thread was joined successfully } #endif // __MYTHREADS_h__
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__
Python import threading import ctypes # Function to lock a thread lock def Thread_lock ( lock ): lock . acquire () # Acquire the lock # No need for assert in Python acquire will raise an exception if it fails # Function to unlock a thread lock def Thread_unlock ( lock ): lock . release () # Release the lock # No need for assert in Python release will raise an exception if it fails # Function to create a thread def Thread_create ( target args = ()): thread = threading . Thread ( target = target args = args ) thread . start () # Start the thread # No need for assert in Python thread.start() will raise an exception if it fails # Function to join a thread def Thread_join ( thread ): thread . join () # Wait for the thread to finish # No need for assert in Python thread.join() will raise an exception if it fails
산출:
Thread Entered: 1
Thread Entered: 0
Actual Count: 2000000000 | Expected Count: 2000000000
