Race Condition ปัญหาที่ทำให้โปรแกรมเมอร์ปวดหัวมานาน

ช่วงไม่กี่สัปดาห์ที่ผ่านมา เราได้มีโอกาส Debug Code ชุดนึงที่น่าสนใจมาก ๆ มันทำงานผิด ๆ ถูก ๆ แปลก ๆ ใช้เวลาอยู่ไม่นานเราก็สามารถรู้ที่มาของปัญหานั่นคือ Race Condition วันนี้เราเลยอยากจะมาเล่าถึงปัญหานี้กันว่า มันหน้าตาเป็นอย่างไร ทำไมมันถึงตรวจจับได้ยาก และ เราจะมีเครื่องมือและวิธีการใดในการแก้ปัญหานี้ได้บ้าง

Race Condition คืออะไร ?

#include <stdio.h>

int counter = 0;
int main () {

   for (int i = 0; i<200000; i++) {
      counter++;
   }
   printf("Final counter value: %d\n", counter);
   printf("Expected counter value: %d\n", 200000);
   
   return 0;
}

เพื่อให้เข้าใจปัญหานี้ได้ง่ายขึ้น เราอยากให้พิจารณา Snippet ด้านบนนี้ก่อน หากอ่านดู เราจะเห็นว่า มันพยายามที่จะนับเลขบวกขึ้นไปเรื่อย ๆ ทีละ 1 ดังนั้น เมื่อ counter ถูกเริ่มค่าที่ 0 และ ถูกบวกทั้งหมด 2 แสนครั้ง ดังนั้น ค่าของ counter ตอนสุดท้ายที่เราคาดหวังย่อมเป็น 2 แสนอย่างแน่นอน เมื่อเรารัน Snippet ตัวนี้ออกมา บรรทัด Final และ Expected ยังไงมันก็จะเท่ากันคือ 2 แสนอย่างแน่นอน

#include <stdio.h>
#include <pthread.h>

int counter = 0;

void* increment_counter(void* arg) {
    for (int i = 0; i < 100000; i++) {
        // Read counter
        int temp = counter;
        // Increment
        temp++;
        // Write back to counter
        counter = temp;
    }
    return NULL;
}

int main() {
    pthread_t thread1, thread2;
    
    // Create two threads that both increment the counter
    pthread_create(&thread1, NULL, increment_counter, NULL);
    pthread_create(&thread2, NULL, increment_counter, NULL);
    
    // Wait for both threads to finish
    pthread_join(thread1, NULL);
    pthread_join(thread2, NULL);
    
    printf("Final counter value: %d\n", counter);
    printf("Expected counter value: %d\n", 200000);
    
    return 0;
}

งั้นถ้าเราอยากจะเร่งความเร็วด้วยการเขียนแบบ Multithread แน่นอนว่าในภาษา C เราจะต้องใช้ pthread อย่างแน่นอน เริ่มจากการประกาศตัวแปร counter เหมือนเดิม จากนั้นเราจะประกาศ Function สำหรับการนับเลขกัน ในรอบนี้ เราจะแบ่งออกมาเป็น 2 Threads ดังนั้น ในแต่ละ Thread จะต้องนับ 1 แสนครั้ง ก็บวกเลขไป ซึ่งวิธีการที่ทำคือ เราจะเอาค่าจาก counter มาเก็บไว้ที่ temp แล้วค่อยบวก จากนั้น เราค่อยให้ counter มีค่าเป็น temp

ใน Main Function เปิดมาขอสร้าง Object ของ Thread ขึ้นมาก่อน 2 ตัว จากนั้น เราจะเรียกคำสั่ง pthread_create เพื่อสร้าง Thread ขึ้นมาทำงานโดยที่ให้มันไปเรียก Function increment_counter ที่ได้เขียนไว้ด้านบน จากนั้น เราก็จะเรียก pthread_join เพื่อรอให้แต่ละ Thread ทำงานเสร็จสิ้น และสุดท้าย ก็จะเอาค่า Counter ที่ถูกแต่ละ Thread บวกกันออกมาที่หน้าจอ

Final counter value: 101789
Expected counter value: 200000

แต่ผลที่ได้ไหงมันเป็นแบบนั้นกันละ ก็ในเมื่อเรา มี 2 แสน เราแยก Thread ละแสน ทำไมมันกลายเป็นแสนกว่า ๆ ได้ละ

void* increment_counter(void* arg) {
    for (int i = 0; i < 100000; i++) {
        // Read counter
        int temp = counter;
        // Increment
        temp++;
        // Write back to counter
        counter = temp;
    }
    return NULL;
}

เหตุผลน่ะเหรอ กลับมาที่ Function สำหรับการบวกเลขกัน เราลองดูดี ๆ คือ เราเริ่มจากการอ่านค่าจาก counter ที่เราประกาศไว้ด้านบนมาเก็บไว้ในตัวแปร temp จากนั้น เราค่อยบวก 1 เข้าไป และเก็บกลับเข้าไปใน counter เอ๊ะอะไรกันมั้ย ลองคิดภาพนะถ้าเรามี Thread เดียวรัน มันก็จะค่อย ๆ ทำไปเรื่อย ๆ ดึงค่าออกมา และอัพเดท counter กลับเข้าไป

แต่ถ้าเรามี 2 Thread ละมันจะเกิดอะไรขึ้น สมมุติว่า Thread 1 อ่าน Counter ออกมาได้ 20 ระหว่างที่มันบวกอยู่ก่อนจะเก็บลงไปใน Counter อีกครั้ง

Thread 2 จะต้องอ่านค่า counter เข้ามา ซึ่งตอนนั้น Thread 1 ยังไม่ได้อัพเดทค่าเข้าไปทำให้อ่านออกมาเลยได้ 20 แล้วก็เอามาบวก 1 ตามโปรแกรม ระหว่างนั้น Thread 1 ดันบวกเสร็จพอดีแล้วเก็บค่า counter เป็น 21 ไปแล้ว และจังหวะต่อไปเอง Thread 2 ที่บวกจาก 20 เป็น 21 แล้วก็จะเอาไปเก็บใน counter เหมือนกัน ดังนั้นค่าที่ควรจะวิ่งเป็น 22 มันก็จะกลายเป็น 21 นั่นทำให้ สุดท้ายบวกกันมันเลยไม่ได้ 2 แสน และถ้าเราลองหลาย ๆ รอบ เราก็จะเห็นเลยว่ามันได้ไม่เท่ากันสักครั้งเดียว

นี่แหละคือ อาการของ Race Condition หลัก ๆ มักจะเกิดจากการมี Shared Memory ระหว่าง Thread หรือ Process หรืองานบางอย่างที่เราจะต้องทำงานพร้อมกัน แต่เราไม่สามารถการันตีลำดับของมันได้ ส่วนใหญ่เรามักจะเจอกับอาการที่บัคนี้มันยากในการที่จะทำซ้ำเพื่อส่งให้ QE หรือกระทั่งว่า ถ้าเราเปลี่ยนปัจจัยภายนอกบางอย่างมันจะทำงานถูกต้อง หรือกระทั่งว่า ถ้าเราใส่ Debug Statement เข้าไปเพื่อเช็ค อ้าวหายเฉย สงสัยไว้ได้เลยว่า แมร่ง น่า จะ ใช่

เราจะแก้ Race Condition ได้อย่างไร ?

แกนหลักของการแก้ Race Condition คือการควบคุมการทำงานของโปรแกรมเราให้อยู่ในลำดับที่ต้องการ หรือ ป้องกันการเข้าถึง Memory ในเวลาที่ Thread อื่นกำลังใช้งานอยู่ วันนี้เราขอเอา 2 วิธีที่น่าจะได้ใช้บ่อย ๆ มาใช้กันคือ Mutex และ Atomic Operation

Mutex

Mutex หรือ Mutual Exclusion เป็นกลไกนึงที่เราสามารถ Implement เข้าไปเพื่อแก้ไขปัญหานี้ได้ หลักการของมันง่ายมาก ๆ คือ มันพยายามที่จะการันตีให้ได้ว่า มีเพียงแค่ Thread เดียวเท่านั้นที่จะสามาถรเข้าถึงทรัพยากรนึงได้ โดยอาศัยการ Lock และ Unlock การเข้าถึง หากสถานะของ Mutex เป็น Lock โดย Thread หนึ่ง ก็จะทำให้ Thread ที่เหลือไม่สามารถเข้าถึงข้อมูลได้ และเมื่อใช้งานเสร็จ Thread ที่เป็นคน Lock ก็จะต้องคืนโดยการสั่ง Unlock ด้วย ทำให้อีกหนึ่งประโยชน์นอกจากการเอามาแก้ปัญหา มันคือการนำมาใช้เป็นการส่งสัญญาณกันระหว่าง Thread ได้ด้วย

#include <stdio.h>
#include <pthread.h>

int counter = 0;
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

void *increment_counter(void *arg)
{
    for (int i = 0; i < 100000; i++)
    {
        // MUTEX LOCK
        pthread_mutex_lock(&mutex);

        // Critical section
        // Read Counter
        int temp = counter;
        // Increment
        temp++;
        // Write back to counter
        counter = temp;

        // MUTEX UNLOCK
        pthread_mutex_unlock(&mutex);
    }
    return NULL;
}

int main()
{
    pthread_t thread1, thread2;

    // Create two threads that both increment the counter
    pthread_create(&thread1, NULL, increment_counter, NULL);
    pthread_create(&thread2, NULL, increment_counter, NULL);

    // Wait for both threads to finish
    pthread_join(thread1, NULL);
    pthread_join(thread2, NULL);

    printf("Final counter value: %d\n", counter);
    printf("Expected counter value: %d\n", 200000);

    // Destroy MUTEX after finish
    pthread_mutex_destroy(&mutex);

    return 0;
}

ด้านบนเป็น Snippet ที่ใช้ Mutex ในการแก้ เราจะเห็นว่า Code ส่วนใหญ่จะเหมือนเดิมหมด โดยเฉพาะใน Main Function (แหงแหละ เราแก้จากของเดิมเนอะ !) แต่สิ่งที่เพิ่มมา เราเริ่มจากการประกาศ pthread_mutex_t ที่เป็น Struct อีกทีนึงเป็นเหมือนส่วนสำหรับควบคุมการทำงานของ Mutex แล้วภายใน increment_counter Function เราเพิ่มส่วนที่มี Mutex Lock และ Unlock เข้าไปครอบส่วนที่ใช้ในการบวกเลข ตรงส่วนที่มันมีการเข้าถึง Shared Memory ตรงนี้แหละ เราจะเรียกว่า Critical Section ให้เราเอา Mutex มาครอบตรงนี้ได้เลย

~ gcc mutex.c -o mutex | ./mutex
Final counter value: 200000
Expected counter value: 200000

เมื่อเรารันออกมา เราก็จะเห็นว่า ค่าที่โปรแกรมหาออกมาได้และค่าที่ควรจะเป็นมันเท่ากัน เย้ ปัญหา Race Condition ถูกแก้ไปแล้ว จากการใช้งาน เราจะเห็นได้เลยว่า Mutex มันใช้งานได้ง่ายมาก ๆ และสามารถแก้ไขปัญหา Race Condition ได้จริง ๆ หากเราสามารถกำหนด Critical Section ได้อย่างถูกต้อง

แต่ข้อเสีย อย่างแรกคือ เมื่อ Mutex Lock ไปแล้วนั่นแปลว่า Thread อื่นจะต้องรอไปเรื่อย ๆ จนกว่า Thead เดิมจะสั่ง Mutex Unlock เท่ากับเราเสีย CPU Cycle ไปเลยฟรี ๆ และ ถามว่า ถ้าเกิดวันนึง Thread หลับไปแล้วลืมตื่น หรือโดน Thread อื่น ๆ ภายในระบบดันความสำคัญขึ้นมาจนไม่ได้รันสักที เท่ากับว่า Thread อื่น ๆ จะไม่สามารถเข้าไปทำงานใน Critical Section ได้เลย ชิบหายการช่างเลยนะ เราเรียกอาการนี้ว่า Starvation

ส่วนตัวจากประสบการณ์มองว่า เราน่าจะเลือกใช้ Mutex เมื่อ เรามีขั้นตอนเยอะ ๆ หรือเงื่อนไขที่ซับซ้อน อยู่ใน Critical Section เพราะมันคือ การเอา Lock และ Unlock มาครอบ มันการันตีว่า ทุกอย่างที่อยู่ตรงกลางมันจะเข้าถึงได้แค่ทีละ Thread มันก็น่าจะทำงานได้อย่างถูกต้องแน่ ๆ ซึ่งทำให้ตัวอย่างนี้ อาจจะไม่เหมาะกับการใช้สักเท่าไหร่

Atomic Operation

มาที่อีกวิธีหนึ่ง คือการใช้ Atomic Operation ตามชื่อของมันเลยคือ การทำงานที่แบ่งแยกไม่ได้ และทำให้ Thread อื่น ๆ จะไม่เห็นสถานะระหว่างทำงานขึ้นได้ โดยมันอาศัยการทำงานหลายแบบมาก ๆ เช่น การใช้คำสั่งพิเศษบน CPU อย่าง Compare and Swap (CAS) คือการตรวจสอบค่าในตำแหน่งว่าตรงกับที่เราคาดหวังหรือไม่ หากตรงกันจะเปลี่ยนค่าใหม่ หรือการทำ Test And Ser (TAS) หรือกระทั่งการใช้ Bus Locking ที่ CPU จะล๊อคหน่วนความจำชั่วคราวระหว่างที่เกิด Atomic Operation หรือกระทั่งการใช้ MESI Protocol (Modified, Exclusive, Shared, Invalid)

#include <stdio.h>
#include <pthread.h>
#include <stdatomic.h>

atomic_int counter = 0;

void *increment_counter(void *arg)
{
    for (int i = 0; i < 100000; i++)
    {
        // Atomic Operation
        atomic_fetch_add(&counter, 1);
    }
    return NULL;
}

int main()
{
    pthread_t thread1, thread2;

    // Create two threads that both increment the counter
    pthread_create(&thread1, NULL, increment_counter, NULL);
    pthread_create(&thread2, NULL, increment_counter, NULL);

    // Wait for both threads to finish
    pthread_join(thread1, NULL);
    pthread_join(thread2, NULL);

    printf("Final counter value: %d\n", counter);
    printf("Expected counter value: %d\n", 200000);

    return 0;
}

มาที่ Code กันบ้างดีกว่า ในภาษา C มันจะมี stdatomic Header ที่รวมชุดคำสั่งมาให้เราหมดแล้ว จากนั้นตอนที่เราจะสร้างตัวแปรที่เก็บ แทนที่จะใช้ int ธรรมดา เราจะ atomic_int แทน และสุดท้าย ตอนที่เราจะบวก แทนที่เราจะบวกเฉย ๆ เราจะต้องใช้ atomic_fetch_add และยัด Address ของตัวแปร Counter เข้าไป และ 1 คือการเพิ่มอีก 1 นั่นเอง

ข้อดีของ Atomic Operation เราคิดว่ามันมี Overhead ในการทำงานที่ดีกว่ามาก ๆ เพราะหลาย ๆ ครั้ง เราจะทำงานโดยการเรียกคำสั่งระดับ Hardware โดยตรงที่มีการ Optimise มาค่อนข้างดีกว่า แต่ข้อเสียเราจะเห็นได้อย่างชัดจาก Code ด้านบนว่า มันจะเหมาะกับงานที่ส่วนของ Critical Section ไม่ได้ซับซ้อนมาก

สรุป

Race Condition เป็นเหตุการณ์ที่ทำให้ Programmer ปวดหัวมากันนัดต่อนัดแล้ว ส่วนใหญ่มักจะเกิดกับเหตุการณ์ที่เราพยายาม Parallel แล้วแค่แก้ Code เพื่อม Thread ลงไปแค่นั้น โดยไม่ได้มีการเช็คดี ๆ แต่แน่นอนว่า เราสามารถแก้ไขมันได้หลากหลายวิธีการมาก ๆ เช่น การใช้ Mutex, Atomic Operation และวิธีการอื่น ๆ ได้อีกมากมาย