5.8 - תהליכונים - פתרון

פתרונות - threads

זכרו לקמפל עם הדגל -lpthread:

gcc program.c -lpthread -o program

---

פתרון 1 - יצירת threads בסיסית

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

void *thread_func(void *arg) {
    int num = *(int *)arg;
    printf("thread %d\n", num);
    return NULL;
}

int main() {
    pthread_t threads[3];
    int nums[3] = {0, 1, 2};

    // create 3 threads
    for (int i = 0; i < 3; i++) {
        int ret = pthread_create(&threads[i], NULL, thread_func, &nums[i]);
        if (ret != 0) {
            fprintf(stderr, "pthread_create failed for thread %d\n", i);
            return 1;
        }
    }

    // wait for all the threads
    for (int i = 0; i < 3; i++) {
        pthread_join(threads[i], NULL);
    }

    printf("all threads finished\n");
    return 0;
}

הערה חשובה: שימו לב שהעברנו &nums[i] ולא &i. אם היינו מעבירים &i, כל ה-threads היו מצביעים לאותו משתנה, ובזמן שהם רצים הערך של i כבר יכול להשתנות (race condition).

---

פתרון 2 - מרוץ תחרות - Race Condition

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

int counter = 0;

void *increment(void *arg) {
    for (int i = 0; i < 1000000; i++) {
        counter++;
    }
    return NULL;
}

int main() {
    pthread_t t1, t2;

    pthread_create(&t1, NULL, increment, NULL);
    pthread_create(&t2, NULL, increment, NULL);

    pthread_join(t1, NULL);
    pthread_join(t2, NULL);

    printf("final counter = %d\n", counter);
    // the result will not be 2000000 in most runs!
    return 0;
}

הסבר: התוצאה לא תמיד 2000000 בגלל מרוץ תחרות (race condition). הפעולה counter++ היא בעצם שלוש פעולות נפרדות: קריאת הערך, הוספת 1, וכתיבה חזרה. כשני threads מבצעים את זה במקביל, ייתכן ששניהם קוראים את אותו ערך לפני שאחד מהם מספיק לכתוב את הערך המעודכן. כך עדכונים "הולכים לאיבוד" והתוצאה הסופית קטנה מהמצופה.

---

פתרון 3 - תיקון עם mutex

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

int counter = 0;
pthread_mutex_t lock;

void *increment(void *arg) {
    for (int i = 0; i < 1000000; i++) {
        pthread_mutex_lock(&lock);
        counter++;
        pthread_mutex_unlock(&lock);
    }
    return NULL;
}

int main() {
    pthread_mutex_init(&lock, NULL);

    pthread_t t1, t2;

    pthread_create(&t1, NULL, increment, NULL);
    pthread_create(&t2, NULL, increment, NULL);

    pthread_join(t1, NULL);
    pthread_join(t2, NULL);

    printf("final counter = %d\n", counter);
    // now the result is always 2000000

    pthread_mutex_destroy(&lock);
    return 0;
}

עכשיו בכל רגע רק thread אחד יכול להריץ את counter++, כך שאין יותר race condition. שימו לב שהתוכנית תרוץ יותר לאט מהגרסה ללא mutex, כי ה-threads מחכים אחד לשני.

---

פתרון 4 - העברת ארגומנט וקבלת ערך חזרה

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

void *compute_length(void *arg) {
    char *str = (char *)arg;
    printf("thread received: \"%s\"\n", str);

    size_t len = strlen(str);

    // return the length as void* using a cast
    return (void *)(intptr_t)len;
}

int main() {
    pthread_t thread;
    char *message = "hello pthreads";

    pthread_create(&thread, NULL, compute_length, message);

    void *result;
    pthread_join(thread, &result);

    int length = (int)(intptr_t)result;
    printf("string length = %d\n", length);

    return 0;
}

הערה: אנחנו משתמשים ב-intptr_t מ-stdint.h כדי להמיר בצורה בטוחה בין int ל-void*. זה עובד כל עוד המספר קטן מספיק להיכנס לפוינטר (מה שתמיד נכון במקרה הזה).

---

פתרון 5 - חישוב מקבילי

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

#define ARRAY_SIZE 1000000
#define NUM_THREADS 4
#define CHUNK_SIZE (ARRAY_SIZE / NUM_THREADS)

typedef struct {
    int *array;
    int start;
    int end;
    long partial_sum;
} thread_data_t;

void *compute_sum(void *arg) {
    thread_data_t *data = (thread_data_t *)arg;
    data->partial_sum = 0;

    for (int i = data->start; i < data->end; i++) {
        data->partial_sum += data->array[i];
    }

    return NULL;
}

int main() {
    // initialize the array - all elements are 1
    int *array = malloc(ARRAY_SIZE * sizeof(int));
    if (!array) {
        perror("malloc");
        return 1;
    }
    for (int i = 0; i < ARRAY_SIZE; i++) {
        array[i] = 1;
    }

    pthread_t threads[NUM_THREADS];
    thread_data_t data[NUM_THREADS];

    // create 4 threads, each handling a quarter of the array
    for (int i = 0; i < NUM_THREADS; i++) {
        data[i].array = array;
        data[i].start = i * CHUNK_SIZE;
        data[i].end = (i + 1) * CHUNK_SIZE;
        data[i].partial_sum = 0;

        int ret = pthread_create(&threads[i], NULL, compute_sum, &data[i]);
        if (ret != 0) {
            fprintf(stderr, "pthread_create failed\n");
            free(array);
            return 1;
        }
    }

    // wait for all the threads
    for (int i = 0; i < NUM_THREADS; i++) {
        pthread_join(threads[i], NULL);
    }

    // sum up the partial results
    long total = 0;
    for (int i = 0; i < NUM_THREADS; i++) {
        printf("thread %d: partial sum = %ld\n", i, data[i].partial_sum);
        total += data[i].partial_sum;
    }

    printf("total sum = %ld\n", total);
    // the result should be 1000000

    free(array);
    return 0;
}

שימו לב שבתרגיל הזה אין צורך ב-mutex, כי כל thread כותב רק ל-partial_sum שלו (שנמצא ב-struct שלו), ולא נוגע בנתונים של threads אחרים. הגישה למערך היא קריאה בלבד, אז גם היא בטוחה. race condition קורה רק כשכמה threads כותבים לאותו מקום בזכרון.