מודל הזכרון - memory model and volatile

הקדמה

בפרק 5.8 למדנו על threads ועל הבעיות שנוצרות כשכמה threads ניגשים לאותו זכרון - race conditions, צורך במנעולים, וכו'. בפרק 8 למדנו על ארכיטקטורת מעבד מודרנית - pipeline, out-of-order execution, ו-cache.

בהרצאה הזו נחבר את שני הנושאים ונבין שאלה קריטית: כשthread אחד כותב לזכרון, מתי thread אחר רואה את הכתיבה? התשובה היא לא פשוטה כמו שנדמה, כי גם הקומפיילר וגם המעבד מסדרים מחדש גישות לזכרון.

---

הבעיה: סידור מחדש - reordering

יש שני מקורות לסידור מחדש של פעולות זכרון:

1. סידור מחדש של הקומפיילר - compiler reordering

הקומפיילר רשאי לסדר מחדש פעולות קריאה וכתיבה לזכרון, כל עוד התוצאה זהה מנקודת המבט של thread בודד:

int a = 0, b = 0;

void thread1(void) {
    a = 1;  // write to a
    b = 1;  // write to b
}

הקומפיילר רשאי להחליף את סדר השורות! כי מנקודת המבט של thread1, אין הבדל אם כותבים קודם ל-a או קודם ל-b.

אבל מה אם thread אחר מסתמך על הסדר?

void thread2(void) {
    if (b == 1) {
        // we expect a == 1 because thread1 wrote to a *before* b
        // but if the compiler reordered things, a might be 0!
        assert(a == 1); // could fail!
    }
}

2. סידור מחדש של המעבד - CPU reordering

גם אם הקומפיילר שומר על הסדר, המעבד עצמו יכול לבצע פעולות בסדר שונה. למדנו בפרק 8 על out-of-order execution - המעבד מבצע פקודות בסדר שונה מסדר התוכנית כדי לנצל את הpipeline בצורה מיטבית.

ב-x86, המעבד נותן הבטחה חזקה יחסית (total store ordering), אבל עדיין יכול לסדר מחדש כתיבה-ואז-קריאה (store-load reordering). בארכיטקטורות אחרות כמו ARM, ההבטחה חלשה הרבה יותר.

---

מילת המפתח volatile

מה volatile עושה

volatile אומר לקומפיילר: אל תבצע אופטימיזציות על הגישות למשתנה הזה. כל קריאה חייבת לקרוא מהזיכרון, וכל כתיבה חייבת לכתוב לזיכרון.

בלי volatile:

int x = 0;

void wait_for_x(void) {
    while (x == 0) {
        // the compiler can read x once, store it in a register,
        // and check the register in the loop - and never exit!
    }
}

עם volatile:

volatile int x = 0;

void wait_for_x(void) {
    while (x == 0) {
        // the compiler must read from memory on every iteration
    }
}

מתי להשתמש ב-volatile

1. רגיסטרים של חומרה - memory-mapped I/O:

// a hardware register mapped to a fixed address
volatile uint32_t *status_reg = (volatile uint32_t *)0x40000000;
volatile uint32_t *data_reg   = (volatile uint32_t *)0x40000004;

void wait_and_read(void) {
    // waiting for the READY bit to turn on
    while (!(*status_reg & READY_BIT))
        ;

    // reading the data
    uint32_t data = *data_reg;
}

בלי volatile, הקומפיילר עשוי:
- לקרוא את status_reg פעם אחת ולהשתמש בערך הישן בלולאה
- לסדר מחדש את הקריאה מ-data_reg לפני שstatus_reg מוכן
- להסיר את הכתיבה ל-status_reg אם "לא משתמשים בתוצאה"

2. משתנים שמשתנים ב-signal handler:

volatile sig_atomic_t got_signal = 0;

void handler(int sig) {
    got_signal = 1;
}

int main(void) {
    signal(SIGINT, handler);

    while (!got_signal) {
        do_work();
    }
    printf("caught signal!\n");
    return 0;
}

למדנו על signal handlers בפרק 5.4. בלי volatile, הקומפיילר לא יודע שהhandler משנה את got_signal ועלול לבצע אופטימיזציה.

מתי volatile לא מספיק

volatile לבד לא מספיק לthread safety!

volatile int counter = 0;

// two threads run this
void increment(void) {
    counter++;  // this is not atomic! (read-modify-write)
}

למרות ש-volatile מבטיח שהגישה תהיה לזיכרון, counter++ הוא עדיין שלוש פעולות: קריאה, הגדלה, כתיבה. שני threads יכולים לקרוא את אותו ערך, להגדיל, ולכתוב - ולאבד עדכון אחד.

volatile גם לא מונע סידור מחדש של המעבד ולא נותן ערבויות סדר בין משתנים שונים.

---

מודל הזכרון של C11 ופעולות אטומיות - atomics

החל מ-C11, יש לשפת C מודל זכרון רשמי ותמיכה בפעולות אטומיות:

#include <stdatomic.h>

atomic_int counter = 0;

פעולות אטומיות בסיסיות

atomic_int val = 0;

atomic_store(&val, 42);            // atomic write
int x = atomic_load(&val);         // atomic read
atomic_fetch_add(&val, 1);         // atomic increment (val++)
atomic_fetch_sub(&val, 1);         // atomic decrement (val--)

השוואה והחלפה - compare and swap

int expected = 5;
int desired = 10;

if (atomic_compare_exchange_strong(&val, &expected, desired)) {
    // the swap succeeded: val was 5, now it's 10
} else {
    // the swap failed: val was not 5
    // expected now contains the actual value of val
}

זה שקול ל-cmpxchg שראינו בפרק 10.1, אבל בinterface C סטנדרטי.

---

סדרי זכרון - memory orderings

כל פעולה אטומית יכולה לקבל פרמטר שמציין את סדר הזכרון הנדרש. זה אומר לקומפיילר ולמעבד איזה סידור מחדש מותר:

memory_order_seq_cst - עקביות רציפה (ברירת מחדל)

הסדר הכי חזק. מבטיח שכל הפעולות האטומיות נראות בסדר קבוע ומוסכם לכל הthreads:

atomic_store_explicit(&val, 42, memory_order_seq_cst);
int x = atomic_load_explicit(&val, memory_order_seq_cst);

זו ברירת המחדל - כשכותבים atomic_store(&val, 42) זה שקול ל-seq_cst. הכי קל לחשוב עליו, אבל הכי איטי.

memory_order_acquire ו-memory_order_release

release (לכתיבה): מבטיח שכל הקריאות והכתיבות לפני הפעולה הזו נראות לthreads אחרים לפני שהם רואים את הכתיבה הזו:

// thread 1: prepares data and then "releases"
data = 42;
ready_flag = 1;  // if this is release, thread 2 will see data=42
atomic_store_explicit(&flag, 1, memory_order_release);

acquire (לקריאה): מבטיח שכל הקריאות והכתיבות אחרי הפעולה הזו מתבצעות אחרי שהערך נקרא:

// thread 2: "acquires" and then reads data
if (atomic_load_explicit(&flag, memory_order_acquire) == 1) {
    // guaranteed that data == 42
    printf("%d\n", data);
}

acquire/release יוצרים "סינכרון" בין הthread שכותב (release) לthread שקורא (acquire). כל מה שthread 1 כתב לפני הrelease מובטח שייראה על ידי thread 2 אחרי הacquire.

דוגמה מעשית - producer/consumer:

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

int data;
atomic_int ready = 0;

void *producer(void *arg) {
    data = 42;                                              // preparing the data
    atomic_store_explicit(&ready, 1, memory_order_release); // publishing
    return NULL;
}

void *consumer(void *arg) {
    while (atomic_load_explicit(&ready, memory_order_acquire) == 0)
        ;  // waiting
    printf("data = %d\n", data);  // guaranteed 42
    return NULL;
}

memory_order_relaxed - ללא הבטחות סדר

הפעולה אטומית (לא ייגרם data race), אבל אין שום הבטחות על סדר מול פעולות אחרות:

atomic_fetch_add_explicit(&counter, 1, memory_order_relaxed);

שימושי כשצריך רק מונה מדויק ולא אכפת מהסדר - למשל, ספירת אירועים.

מתי להשתמש בכל סדר

סדר	שימוש טיפוסי
seq_cst	כשלא בטוחים, ברירת מחדל בטוחה
acquire/release	Producer/consumer, מנעולים, פרסום נתונים
relaxed	מונים פשוטים, סטטיסטיקות

---

מחסומי קומפיילר - compiler barriers

מחסום קומפיילר מונע מהקומפיילר לסדר מחדש פעולות זכרון מעבר לנקודה הזו:

asm volatile("" ::: "memory");

זה inline assembly ריק (למדנו בפרק 10.1), אבל ה-clobber "memory" אומר לקומפיילר: "הזיכרון עשוי להשתנות כאן - אל תניח שום דבר על ערכים שנשמרו ברגיסטרים."

a = 1;
asm volatile("" ::: "memory");  // the compiler won't move a=1 past this point
b = 1;

שימו לב: מחסום קומפיילר מונע רק סידור מחדש של הקומפיילר. המעבד עדיין יכול לסדר מחדש.

---

מחסומי מעבד - CPU memory barriers

כדי למנוע סידור מחדש של המעבד, צריך פקודות מעבד מיוחדות:

// x86 memory barriers
asm volatile("mfence" ::: "memory");  // full barrier - all types of accesses
asm volatile("lfence" ::: "memory");  // read barrier - loads
asm volatile("sfence" ::: "memory");  // write barrier - stores

• mfence (memory fence): מבטיח שכל הקריאות והכתיבות לפני הmfence מסתיימות לפני שפעולות אחרי הmfence מתחילות
• sfence (store fence): מבטיח שכל הכתיבות לפניו מסתיימות לפני כתיבות אחריו
• lfence (load fence): מבטיח שכל הקריאות לפניו מסתיימות לפני קריאות אחריו

בלינוקס, הקרנל מגדיר מאקרואים נוחים:

// from the kernel (simplified)
#define smp_mb()  asm volatile("mfence" ::: "memory")
#define smp_rmb() asm volatile("lfence" ::: "memory")
#define smp_wmb() asm volatile("sfence" ::: "memory")

---

ההבדל בין מחסום קומפיילר למחסום מעבד

חשוב להבין את ההבדל:

	מחסום קומפיילר	מחסום מעבד
מונע מ...	קומפיילר לסדר מחדש	מעבד לסדר מחדש
פקודת אסמבלי	ריקה (אין פקודה)	mfence/lfence/sfence
עלות ביצועים	אפס (רק מגביל קומפיילר)	גבוהה (flush של buffers)
מספיק ל...	thread בודד, signal handlers	ריבוי threads, ריבוי ליבות

כלל אצבע: כשצריך סינכרון בין threads, השתמשו ב-atomics עם הסדר המתאים. הatomics כוללים את שני סוגי המחסומים אוטומטית.

---

דוגמה מעשית: הqueue חד-יצרן חד-צרכן - lock-free SPSC queue

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

#define QUEUE_SIZE 1024

struct spsc_queue {
    int buffer[QUEUE_SIZE];
    atomic_int head;  // the consumer reads from here
    atomic_int tail;  // the producer writes to here
};

void queue_init(struct spsc_queue *q) {
    atomic_store(&q->head, 0);
    atomic_store(&q->tail, 0);
}

// called only from the producer thread
int queue_push(struct spsc_queue *q, int value) {
    int tail = atomic_load_explicit(&q->tail, memory_order_relaxed);
    int next_tail = (tail + 1) % QUEUE_SIZE;

    // checks if the queue is full
    if (next_tail == atomic_load_explicit(&q->head, memory_order_acquire))
        return -1;  // the queue is full

    q->buffer[tail] = value;

    // publishes the new tail - release guarantees that the write to buffer is visible
    atomic_store_explicit(&q->tail, next_tail, memory_order_release);
    return 0;
}

// called only from the consumer thread
int queue_pop(struct spsc_queue *q, int *value) {
    int head = atomic_load_explicit(&q->head, memory_order_relaxed);

    // checks if the queue is empty
    if (head == atomic_load_explicit(&q->tail, memory_order_acquire))
        return -1;  // the queue is empty

    *value = q->buffer[head];

    // publishes the new head - release guarantees that the read from buffer completed
    atomic_store_explicit(&q->head, (head + 1) % QUEUE_SIZE,
                         memory_order_release);
    return 0;
}

שימו לב: הqueue הזה עובד בלי מנעולים! הacquire/release מבטיחים שהנתונים ב-buffer נראים בסדר הנכון:

• כשהיצרן כותב ל-buffer ואז עושה release store ל-tail, הצרכן שעושה acquire load מ-tail מובטח שיראה את הנתונים שהיצרן כתב
• כשהצרכן קורא מ-buffer ואז עושה release store ל-head, היצרן שעושה acquire load מ-head מובטח שהקריאה הסתיימה

---

למה זה חשוב

בלי הבנה של מודל הזכרון, קוד מרובה threads יכול "לעבוד" על מכונה אחת ולהיכשל על אחרת, או לעבוד בגרסה אחת של הקומפיילר ולהישבר בגרסה הבאה.

הנה תקציר של מה להשתמש במה:

מצב	כלי
משתנה שנקרא/נכתב על ידי signal handler	volatile sig_atomic_t
רגיסטר חומרה	volatile
מונה משותף בין threads	atomic_int עם relaxed
דגל "מוכן" בין threads	atomic_int עם acquire/release
כשלא בטוחים	atomic_int עם seq_cst (ברירת מחדל)
שיתוף מבנים מורכבים	מנעול (pthread_mutex)

---

סיכום

• גם הקומפיילר וגם המעבד יכולים לסדר מחדש גישות לזיכרון
• volatile מונע אופטימיזציות קומפיילר אבל לא מספיק ל-thread safety
• C11 atomics (<stdatomic.h>) מספקים פעולות אטומיות עם ערבויות סדר
• סדרי זכרון: seq_cst (חזק, ברירת מחדל) > acquire/release (בינוני) > relaxed (חלש)
• מחסום קומפיילר מונע סידור מחדש של הקומפיילר, מחסום מעבד מונע סידור מחדש של החומרה
• atomics כוללים את שני סוגי המחסומים אוטומטית
• כשלא בטוחים, השתמשו ב-seq_cst או במנעול