סנכרון בקרנל - kernel synchronization¶
מבוא¶
בסעיף 5.8 למדנו על מנעולים (mutexes) במרחב המשתמש - ראינו איך processes ו-threads יכולים לסנכרן גישה למשאבים משותפים. עכשיו נצלול לתוך מנגנוני הסנכרון של הקרנל עצמו, ונגלה שהם הרבה יותר מורכבים.
למה? כי הקרנל מתמודד עם אתגרים שלא קיימים ב-user space:
- מספר מעבדים (CPUs) מריצים קוד קרנל בו-זמנית
- פסיקות (interrupts) יכולות לקטוע קוד קרנל בכל רגע
- חלק מההקשרים בקרנל לא יכולים לישון (interrupt handlers, softirqs)
- דדלוק בקרנל = הקפאה מוחלטת של המערכת
אין פה מנגנון הגנה שיציל אתכם - אם הקרנל נתקע, כל המערכת נתקעת. לכן הסנכרון בקרנל הוא נושא קריטי.
למה סנכרון בקרנל קשה יותר¶
ריבוי מעבדים - SMP¶
במערכת עם מספר מעבדים (SMP - Symmetric Multiprocessing), שני מעבדים שונים יכולים להריץ קוד קרנל באותו רגע ממש. למשל, שני processes על שני מעבדים שונים יכולים לקרוא לאותו syscall ולגשת לאותו מבנה נתונים בקרנל.
ב-user space, ה-scheduler מחליף בין threads, אבל בכל רגע נתון רק thread אחד רץ (על CPU אחד). בקרנל, המצב שונה לגמרי - קוד קרנל רץ במקביל אמיתי.
פסיקות - interrupts¶
נניח שקוד קרנל מעדכן מבנה נתונים, ובדיוק באמצע - מגיעה interrupt מכרטיס הרשת. ה-interrupt handler רץ על אותו CPU, ואם הוא ניגש לאותו מבנה נתונים - יש לנו בעיה.
הקשרים שלא יכולים לישון¶
ב-user space, mutex פשוט שולח את ה-thread לישון אם המנעול תפוס. אבל בקרנל, יש הקשרים שבהם אסור לישון:
- הקשר interrupt - interrupt handler: לא שייך לשום process, אז אי אפשר לשים אותו ב-sleep queue
- הקשר softirq ו-tasklet: מטפלים בinterrupts "רכות", גם הם לא יכולים לישון
- כשמחזיקים spinlock: כי spinlock משבית preemption, ואם נירדם נתקע
פעולות אטומיות - atomic operations¶
הרמה הבסיסית ביותר של סנכרון. עבור פעולות פשוטות כמו הגדלת מונה, אין צורך במנעול מלא - מספיקה פעולה אטומית.
הטיפוס atomic_t¶
הפעולות העיקריות:
int val = atomic_read(&counter); // atomic read
atomic_set(&counter, 42); // atomic write
atomic_add(5, &counter); // counter += 5
atomic_sub(3, &counter); // counter -= 3
atomic_inc(&counter); // counter++
atomic_dec(&counter); // counter--
// operations that also return a value
int old = atomic_inc_return(&counter); // ++counter, returns the new value
if (atomic_dec_and_test(&counter)) // --counter, returns true if the result is 0
מימוש ברמת החומרה¶
על ארכיטקטורת x86, פעולות אטומיות מומשות באמצעות הפקודה LOCK prefix:
הפקודה LOCK נועלת את ה-memory bus (או cache line ספציפי) למשך הפעולה, ומבטיחה שאף CPU אחר לא יגש לאותו כתובת באמצע.
על ארכיטקטורות אחרות, משתמשים ב-compare-and-swap (cmpxchg) או ב-load-linked/store-conditional (LL/SC).
מתי להשתמש¶
פעולות אטומיות מתאימות לדברים פשוטים:
- מוני התייחסות (reference counters)
- דגלים (flags)
- סטטיסטיקות פשוטות
אם צריך לעדכן מבנה נתונים מורכב - צריך מנעול אמיתי.
מנעולי סיבוב - spinlocks¶
ה-spinlock הוא המנעול הפשוט ביותר בקרנל, והשימוש הנפוץ ביותר בהקשרים שלא יכולים לישון.
העיקרון¶
כשprocess מנסה לקבל spinlock שתפוס, הוא מסתובב בלולאה (spins) ובודק שוב ושוב אם המנעול התפנה. הוא לא הולך לישון - הוא פשוט ממתין בפעילות (busy-wait).
#include <linux/spinlock.h>
DEFINE_SPINLOCK(my_lock); // static definition
// or
spinlock_t my_lock;
spin_lock_init(&my_lock); // dynamic definition
spin_lock(&my_lock);
// ... critical section ...
spin_unlock(&my_lock);
למה busy-wait ולא sleep?¶
כי spinlock משמש בהקשרים שבהם אסור לישון (interrupt handlers, softirqs). בנוסף, אם הקטע הקריטי קצר מאוד (כמה שורות קוד), ה-overhead של הרדמה והקצה מחדש גדול יותר מאשר לסובב קצת.
spinlock וinterrupts¶
נניח את התרחיש הבא:
1. process A לוקח spinlock
2. מגיעה interrupt על אותו CPU
3. ה-interrupt handler מנסה לקחת את אותו spinlock
4. דדלוק! - ה-handler מסתובב, אבל process A לא יכול לשחרר כי ה-handler רץ על אותו CPU
הפתרון - להשבית interrupts ביחד עם לקיחת ה-lock:
unsigned long flags;
spin_lock_irqsave(&my_lock, flags); // locks + disables interrupts + saves state
// ... critical section ...
spin_unlock_irqrestore(&my_lock, flags); // unlocks + restores interrupt state
// if we know for certain that interrupts are enabled:
spin_lock_irq(&my_lock); // locks + disables interrupts
// ... critical section ...
spin_unlock_irq(&my_lock); // unlocks + enables interrupts
השיטה irqsave בטוחה יותר כי היא שומרת את מצב הinterrupts המקורי (אולי הן כבר היו מושבתות).
spinlock על מעבד יחיד¶
על מערכת עם CPU אחד, אין צורך ב-spinning אמיתי - הרי אין CPU אחר שמחזיק את המנעול. במקום זה, spinlock פשוט משבית preemption על ה-CPU המקומי, מה שמבטיח שאף קוד אחר לא ירוץ עד ששוחררים את המנעול.
כללים חשובים¶
- החזיקו spinlock לזמן קצר ככל האפשר - כל מי שמחכה מבזבז CPU cycles
- לעולם אל תישנו בתוך spinlock - אסור לקרוא לפונקציות שעלולות לישון (kmalloc עם GFP_KERNEL, copy_from_user, וכו')
- אם צריכים לישון - השתמשו ב-mutex
מנעולים בקרנל - kernel mutexes¶
ה-mutex בקרנל דומה למה שראינו ב-user space, אבל עם כמה הבדלים חשובים.
#include <linux/mutex.h>
DEFINE_MUTEX(my_mutex); // static definition
// or
struct mutex my_mutex;
mutex_init(&my_mutex); // dynamic definition
mutex_lock(&my_mutex); // locks, sleeps if the lock is held
// ... critical section (can sleep!) ...
mutex_unlock(&my_mutex); // unlocks
// non-blocking version:
if (mutex_trylock(&my_mutex)) {
// we managed to lock
mutex_unlock(&my_mutex);
}
// version that can be interrupted by a signal:
if (mutex_lock_interruptible(&my_mutex) == 0) {
// we managed to lock
mutex_unlock(&my_mutex);
}
מתי mutex ומתי spinlock?¶
| מאפיין | spinlock | mutex |
|---|---|---|
| התנהגות כשתפוס | מסתובב (busy-wait) | הולך לישון |
| שימוש ב-interrupt handler | כן | לא! |
| מותר לישון בתוכו | לא! | כן |
| קטע קריטי ארוך | לא מומלץ | כן |
| overhead כשהמנעול פנוי | מינימלי | קצת יותר |
תכונות מיוחדות¶
ל-mutex בקרנל יש כמה תכונות שאין ל-spinlock:
- מעקב בעלות (owner tracking) - רק מי שנעל יכול לשחרר
- תמיכה ב-lockdep - מערכת הדיבאג של הקרנל יכולה לזהות סדרי נעילה שגויים
- אופטימיזציה של fast path - אם המנעול פנוי, הנעילה היא פעולה אטומית אחת בלבד
מנעולי קריאה-כתיבה - read-write locks¶
לפעמים יש מבנה נתונים שנקרא הרבה אבל נכתב מעט. למשל, טבלת ניתוב (routing table) - כל חבילת רשת צריכה לקרוא ממנה, אבל עדכונים מגיעים לעיתים רחוקות.
במצב כזה, אין סיבה שקוראים יחסמו אחד את השני. מנעולי קריאה-כתיבה מאפשרים:
- מספר קוראים במקביל - כל עוד אין כותב
- כותב בלעדי - חוסם את כל הקוראים והכותבים האחרים
גרסת spinlock - rwlock_t¶
#include <linux/rwlock.h>
DEFINE_RWLOCK(my_rwlock);
// read:
read_lock(&my_rwlock);
// ... read from the structure ...
read_unlock(&my_rwlock);
// write:
write_lock(&my_rwlock);
// ... update the structure ...
write_unlock(&my_rwlock);
כמו spinlock רגיל - לא ישן, מסתובב. יש גם גרסאות עם irqsave.
גרסת semaphore - rw_semaphore¶
#include <linux/rwsem.h>
DECLARE_RWSEM(my_rwsem);
// read:
down_read(&my_rwsem);
// ... reading (can sleep) ...
up_read(&my_rwsem);
// write:
down_write(&my_rwsem);
// ... writing (can sleep) ...
up_write(&my_rwsem);
בעיות אפשריות¶
- הרעבת כותבים (writer starvation) - אם כל הזמן יש קוראים חדשים, הכותב לעולם לא מקבל תור
- ב-Linux הבעיה מטופלת - כשכותב מחכה, קוראים חדשים נחסמים גם הם
RCU - Read-Copy-Update¶
זהו מנגנון הסנכרון המתקדם ביותר ב-Linux, והוא משמש באופן נרחב ברחבי הקרנל. הרעיון הבסיסי גאוני בפשטותו.
העיקרון¶
- קוראים לא צריכים מנעול בכלל - אפס overhead!
- כותבים יוצרים עותק, מעדכנים אותו, ואז מחליפים את המצביע בפעולה אטומית
- הנתונים הישנים משוחררים רק אחרי שכל הקוראים סיימו (תקופת חסד - grace period)
איך זה עובד¶
reader 1: [----reads old data----]
reader 2: [----reads old/new data----]
writer: copy -> update -> pointer swap
|--- grace period ---|
release old data
- הכותב מקצה עותק חדש של מבנה הנתונים
- מעדכן את העותק החדש
- מחליף את המצביע (פעולה אטומית -
rcu_assign_pointer()) - מחכה שכל הקוראים שהחלו לפני ההחלפה יסיימו (grace period)
- משחרר את הנתונים הישנים
הinterface קריאה¶
#include <linux/rcupdate.h>
rcu_read_lock();
struct my_data *p = rcu_dereference(global_ptr); // safe read of the pointer
// ... use p ...
// sleeping is forbidden here!
rcu_read_unlock();
מה עושים rcu_read_lock() ו-rcu_read_unlock() בפועל? רק משביתים ומפעילים preemption! זה כל מה שצריך כדי להגן על הקורא. ה-overhead הוא אפסי - שתי פקודות מעבד פשוטות.
הinterface כתיבה¶
// pointer swap (atomic):
rcu_assign_pointer(global_ptr, new_data);
// releasing old data - two options:
// 1. synchronous - blocks until all readers finish:
synchronize_rcu();
kfree(old_data);
// 2. asynchronous - calls a callback when safe:
call_rcu(&old_data->rcu_head, my_rcu_callback);
דוגמה מלאה¶
struct my_entry {
int key;
int value;
struct rcu_head rcu;
};
struct my_entry __rcu *global_entry;
// read (very fast):
int read_value(void)
{
int val;
rcu_read_lock();
struct my_entry *p = rcu_dereference(global_entry);
if (p)
val = p->value;
else
val = -1;
rcu_read_unlock();
return val;
}
// callback for releasing:
static void free_entry_rcu(struct rcu_head *head)
{
struct my_entry *entry = container_of(head, struct my_entry, rcu);
kfree(entry);
}
// write:
void update_value(int new_key, int new_value)
{
struct my_entry *new = kmalloc(sizeof(*new), GFP_KERNEL);
struct my_entry *old;
new->key = new_key;
new->value = new_value;
old = rcu_dereference_protected(global_entry, lockdep_is_held(&update_mutex));
rcu_assign_pointer(global_entry, new);
if (old)
call_rcu(&old->rcu, free_entry_rcu);
}
איפה משתמשים ב-RCU¶
ב-Linux RCU משמש בכל מקום:
- טבלאות ניתוב ברשת
- חיפוש קבצים במערכת הקבצים (dcache)
- רשימת מודולים טעונים
- טבלאות processes
- ועוד הרבה - יש אלפי שימושים בקרנל
סמפורים - semaphores¶
#include <linux/semaphore.h>
struct semaphore sem;
sema_init(&sem, 1); // initial value 1 = binary semaphore (like mutex)
sema_init(&sem, 5); // initial value 5 = allows 5 concurrent locks
down(&sem); // waits (sleeps) until the value > 0, then decrements
// ... critical section ...
up(&sem); // increments the value
down_interruptible(&sem); // can be interrupted by a signal
down_trylock(&sem); // non-blocking
סמפורים הם מנגנון ישן יותר שהיה בקרנל לפני ש-mutex נוסף. כיום, ברוב המקרים עדיף להשתמש ב-mutex (שיש לו אופטימיזציות ומעקב טובים יותר). סמפורים עדיין שימושיים כש-counting semaphore נדרש (מספר נועלים במקביל).
משתנים לכל מעבד - per-CPU variables¶
הגישה הטובה ביותר לסנכרון היא... להימנע ממנו!
אם לכל CPU יש עותק משלו של משתנה, אין צורך בנעילה בכלל. זה בדיוק מה ש-per-CPU variables עושים.
#include <linux/percpu.h>
// static definition:
DEFINE_PER_CPU(int, my_counter);
// usage:
int cpu = get_cpu(); // disables preemption and returns the CPU number
per_cpu(my_counter, cpu)++; // access the current CPU's variable
put_cpu(); // enables preemption
// or in short form:
get_cpu_var(my_counter)++;
put_cpu_var(my_counter);
// dynamic allocation:
int __percpu *dynamic_counter = alloc_percpu(int);
int *ptr = per_cpu_ptr(dynamic_counter, cpu);
*ptr = 42;
free_percpu(dynamic_counter);
שימושים נפוצים¶
- מוני סטטיסטיקות - כל CPU מעדכן את המונה שלו, ורק כשרוצים את הסכום הכולל קוראים מכל ה-CPUs
- מטמונים (caches) - כל CPU שומר עותק מקומי של נתונים שנגישים תכופות
- מקצי זיכרון - ה-slab allocator משתמש ב-per-CPU caches
למה זה עובד¶
get_cpu() משבית preemption - מה שמבטיח שהprocess לא יעבור ל-CPU אחר באמצע הגישה למשתנה. זה מספיק כי CPU אחר לא ניגש למשתנה הזה (לכל CPU יש עותק משלו).
מניעת דדלוקים בקרנל¶
דדלוק בקרנל הוא אסון - המערכת קופאת ואין דרך להתאושש (חוץ מ-restart). לכן הקרנל מספק כלים וכללים למניעת דדלוקים.
כללי ברזל¶
1. תמיד תנעלו מנעולים באותו סדר
// correct - always A before B:
spin_lock(&lock_a);
spin_lock(&lock_b);
// ...
spin_unlock(&lock_b);
spin_unlock(&lock_a);
// wrong - can create a deadlock!
// thread 1: lock_a -> lock_b
// thread 2: lock_b -> lock_a
2. לעולם אל תישנו כשמחזיקים spinlock
spin_lock(&my_lock);
kmalloc(size, GFP_ATOMIC); // correct - GFP_ATOMIC doesn't sleep
// kmalloc(size, GFP_KERNEL); // wrong! GFP_KERNEL can sleep
spin_unlock(&my_lock);
3. אל תנסו לנעול spinlock שכבר מחזיקים (non-recursive)
lockdep - גילוי דדלוקים בזמן ריצה¶
ה-Linux kernel כולל מערכת גאונית בשם lockdep (מופעלת עם CONFIG_PROVE_LOCKING) שמזהה פוטנציאל לדדלוק עוד לפני שהוא קורה.
איך? lockdep עוקב אחרי סדר הנעילות. אם הוא רואה שב-thread אחד נעלתם A ואז B, ואז ב-thread אחר נעלתם B ואז A - הוא מתריע מיד, גם אם דדלוק עדיין לא קרה בפועל.
=============================================
WARNING: possible circular locking dependency detected
5.10.0 #1 Not tainted
---------------------------------------------
process/1234 is trying to acquire lock:
(&lock_b){+.+.}-{2:2}, at: my_function+0x42/0x100
but task is already holding lock:
(&lock_a){+.+.}-{2:2}, at: my_function+0x20/0x100
which lock already depends on the new lock.
...
הודעות lockdep הן שלא יסולא בפז לפיתוח קרנל - הן מגלות באגי סנכרון לפני שהם הופכים לקריסות בייצור.
סיכום - מתי להשתמש במה¶
| מנגנון | ישן? | הקשר interrupt? | ביצועים | שימוש טיפוסי |
|---|---|---|---|---|
| פעולות אטומיות - atomic operations | לא | כן | הכי מהיר | מונים, דגלים |
| spinlock | לא | כן | מהיר | קטעים קריטיים קצרים |
| mutex | כן | לא | טוב | קטעים קריטיים ארוכים |
| rwlock | לא | כן | מהיר לקוראים | נתונים שנקראים הרבה |
| RCU | לא (קוראים) | כן (קוראים) | הכי מהיר לקוראים | רשימות, טבלאות |
| משתנים per-CPU | לא | כן | הכי מהיר (אין נעילה) | מונים, caches |
הכלל הפשוט: השתמשו במנגנון הקל ביותר שמספיק. אם מספיק atomic - אל תשתמשו ב-spinlock. אם מספיק spinlock - אל תשתמשו ב-mutex. ואם אפשר per-CPU - זו האפשרות הטובה ביותר.