6.3 מתזמן התהליכים הרצאה
הקדמה¶
בפרק 2.4 למדנו על context switch - איך המעבד שומר את מצב תוכנה אחת וטוען את מצב תוכנה אחרת. ראינו איך פסיקת הטיימר (IRQ0) קוטעת את התוכנה הנוכחית ומאפשרת לקרנל להחליף לתוכנה אחרת. אמרנו ש"הscheduler בוחר תוכנה מהרשימה" - אבל לא נכנסנו לפרטים של איך הוא בוחר.
עכשיו הגיע הזמן. בהרצאה הזו נלמד בדיוק איך הscheduler של לינוקס עובד מבפנים - מהם מצבי התהליך, מהו המבנה task_struct הענק שמייצג תהליך בקרנל, ואיך אלגוריתם הCFS (Completely Fair Scheduler) מחליט מי רץ ולכמה זמן.
מצבי תהליך בלינוקס - process states¶
בפרק 5.2 למדנו שלכל תהליך יש PID ו-PPID, ושתהליכים יכולים להיות זומבים. אבל בתוך הקרנל, לכל תהליך יש מצב (state) מדויק יותר. אלו המצבים העיקריים:
| מצב | שם | הסבר |
|---|---|---|
TASK_RUNNING |
רץ / מוכן לרוץ | התהליך או רץ כרגע על המעבד, או ממתין בתור (מוכן לרוץ ברגע שהscheduler יבחר בו) |
TASK_INTERRUPTIBLE |
ישן (ניתן להפסקה) | התהליך ישן - ממתין לאירוע (קלט מהמקלדת, נתונים מהרשת, וכו'). אפשר להעיר אותו עם סיגנל |
TASK_UNINTERRUPTIBLE |
ישן (לא ניתן להפסקה) | התהליך ישן וממתין לפעולת IO קריטית (למשל קריאה מדיסק). אי אפשר להפסיק אותו עם סיגנל - אפילו SIGKILL לא יעבוד עד שהIO יסתיים. זהו המצב "D" שרואים ב-top |
TASK_STOPPED |
עצור | התהליך נעצר - בדרך כלל בגלל סיגנל SIGSTOP או כי debugger עצר אותו (ptrace) |
TASK_ZOMBIE |
זומבי | התהליך סיים לרוץ אבל תהליך האב עדיין לא קרא ל-wait() כדי לאסוף את הexit code שלו (כזכור מפרק 5.2) |
מעברים בין מצבים¶
fork()
|
v
TASK_RUNNING (מוכן)
/ \
נבחר על ידי ממתין
הscheduler לאירוע
| \
v v
TASK_RUNNING TASK_INTERRUPTIBLE
(רץ על CPU) או TASK_UNINTERRUPTIBLE
| |
טיימר/yield אירוע קרה / סיגנל
| |
v v
TASK_RUNNING TASK_RUNNING
(מוכן) (מוכן)
|
exit()
|
v
TASK_ZOMBIE
|
wait() מהאב
|
v
[נמחק]
שימו לב שTASK_RUNNING מייצג שני מצבים - גם "רץ כרגע על CPU" וגם "מוכן לרוץ, ממתין בתור". ההבדל הוא האם התהליך באמת מקושר לCPU מסוים ברגע זה.
המבנה task_struct - הייצוג של תהליך בקרנל¶
בפרק 2.4 הזכרנו את הPCB (Process Control Block) - מבנה נתונים שהקרנל שומר עבור כל תהליך. בלינוקס, הPCB הזה נקרא task_struct, והוא מבנה ענק - אלפי בתים שמכילים את כל מה שהקרנל צריך לדעת על תהליך.
הנה השדות המרכזיים (מאוד מפושט - בפועל יש הרבה יותר):
// include/linux/sched.h (מפושט מאוד)
struct task_struct {
// === מצב התהליך ===
unsigned int state; // TASK_RUNNING, TASK_INTERRUPTIBLE, ...
// === זיהוי ===
pid_t pid; // מזהה התהליך
pid_t tgid; // Thread Group ID
// === שם התהליך ===
char comm[TASK_COMM_LEN]; // שם התוכנה (למשל "bash")
// === זכרון ===
struct mm_struct *mm; // כל המידע על הזכרון של התהליך
// (טבלאות paging, VMAs, heap, stack)
// === קבצים ===
struct files_struct *files; // טבלת מתארי הקבצים (fd table)
// === סיגנלים ===
struct signal_struct *signal; // מידע על סיגנלים וhandlers
// === עץ התהליכים ===
struct task_struct *parent; // תהליך האב
struct list_head children; // רשימת תהליכי הבן
struct list_head sibling; // אחים (בני אותו אב)
// === תזמון ===
struct sched_entity se; // מידע לscheduler (כולל vruntime)
int prio; // עדיפות (priority)
// === מחסנית קרנלית ===
void *stack; // מצביע למחסנית הקרנלית של התהליך
// ... עוד מאות שדות ...
};
כמה נקודות חשובות:
pid מול tgid¶
בפרק 5.8 למדנו שתהליכונים (threads) חולקים את אותו מרחב זכרון. בתוך הקרנל, כל thread הוא task_struct נפרד עם pid משלו. אבל כל הthreads של אותו תהליך חולקים את אותו tgid (Thread Group ID). כשאנחנו קוראים ל-getpid() מיוזר מוד, מה שחוזר הוא בעצם ה-tgid - ולא ה-pid הקרנלי. ככה כל הthreads של אותו תהליך "רואים" את אותו PID.
הmm_struct¶
השדה mm מצביע למבנה שמכיל את כל המידע על הזכרון של התהליך:
- מצביע לטבלת הpaging (מה שנטען לCR3)
- רשימת כל הVMAs (Virtual Memory Areas - אזורי הזכרון: heap, stack, mmap-ים, קוד, נתונים)
- מונים וסטטיסטיקות על שימוש בזכרון
כשעושים fork, הmm_struct מועתק (עם COW - Copy On Write כזכור מפרק 5.7). כשעושים תהליכונים עם clone, ה-mm_struct משותף - וזו בדיוק הסיבה שתהליכונים רואים את אותו זכרון.
המצביע current¶
בכל רגע נתון, הקרנל צריך לדעת מי התהליך שרץ כרגע על הCPU. לשם כך יש מאקרו שנקרא current שמחזיר מצביע ל-task_struct של התהליך הנוכחי:
// בכל מקום בקוד הקרנל אפשר לעשות:
printk("current process: %s (pid=%d)\n", current->comm, current->pid);
תור הריצה - run queue¶
כל CPU במערכת מנהל תור ריצה (run queue) משלו. התור מכיל את כל התהליכים שנמצאים במצב TASK_RUNNING ומחכים לרוץ על הCPU הזה.
המבנה שמייצג את התור נקרא struct rq (run queue):
// kernel/sched/sched.h (מפושט)
struct rq {
unsigned int nr_running; // כמה תהליכים ממתינים
struct cfs_rq cfs; // תור הCFS (הscheduler הרגיל)
struct rt_rq rt; // תור הreal-time
struct task_struct *curr; // התהליך שרץ כרגע
// ...
};
לכל CPU יש rq משלו, מה שמאפשר לCPU-ים שונים לתזמן תהליכים באופן בלתי תלוי (פחות נעילות, יותר ביצועים).
הCFS - Completely Fair Scheduler¶
מאז גרסה 2.6.23 של הקרנל (2007), הscheduler ברירת המחדל של לינוקס הוא הCFS - Completely Fair Scheduler. הרעיון המרכזי שלו פשוט: לתת לכל תהליך את החלק ההוגן שלו מזמן הCPU.
הרעיון: זמן ריצה וירטואלי - vruntime¶
לכל תהליך יש מונה שנקרא vruntime (virtual runtime) שעוקב אחרי כמה זמן CPU התהליך קיבל. הכלל הוא:
התהליך עם הvruntime הנמוך ביותר רץ הבא.
למה? כי vruntime נמוך אומר שהתהליך קיבל פחות זמן CPU מאחרים - אז הוא "מגיע לו" לרוץ.
כשתהליך רץ, הvruntime שלו עולה. כשהוא ישן (ממתין לIO), הvruntime שלו לא עולה. ככה תהליכים שישנים הרבה (כמו עורך טקסט שמחכה להקלדה) יקבלו זמן CPU מיד כשהם מתעוררים - כי הvruntime שלהם נמוך יחסית.
עץ אדום-שחור - Red-Black Tree¶
אבל איך הscheduler מוצא במהירות את התהליך עם הvruntime הנמוך ביותר? הרי יכולים להיות מאות תהליכים בתור.
הCFS משתמש במבנה נתונים שנקרא עץ אדום-שחור (Red-Black Tree) - עץ חיפוש בינארי מאוזן. כל הצמתים בעץ מסודרים לפי vruntime, והצומת השמאלי ביותר (עם הvruntime הנמוך ביותר) הוא תמיד התהליך הבא שירוץ.
במבנה הזה, הצומת השמאלי ביותר (vruntime=20) הוא התהליך הבא שירוץ. מציאת הצומת השמאלי ביותר היא פעולה של O(1) כי הקרנל שומר עליו מצביע.
הוספה והסרה מהעץ הן O(log n) - מהיר מספיק גם כשיש אלפי תהליכים.
// kernel/sched/fair.c (מפושט)
struct sched_entity {
struct rb_node run_node; // הצומת בעץ האדום-שחור
u64 vruntime; // הזמן הוירטואלי שצבר
// ...
};
חלון התזמון - scheduling latency¶
בניגוד לscheduler-ים ישנים שנתנו לכל תהליך "פרוסת זמן" קבועה (time slice), הCFS עובד אחרת.
הוא מגדיר חלון תזמון (scheduling latency) - פרק זמן שבו כל תהליך מוכן-לריצה אמור לקבל לפחות הזדמנות אחת לרוץ. בדרך כלל זה בין 6 ל-24 מילישניות (תלוי בכמות התהליכים).
הזמן מחולק בין כל התהליכים המוכנים. למשל, אם חלון התזמון הוא 20ms ויש 4 תהליכים מוכנים, כל אחד יקבל 5ms. אם יש 10 תהליכים, כל אחד יקבל 2ms.
ערכי nice ועדיפות¶
לא כל התהליכים שווים. לפעמים רוצים שתהליך מסוים יקבל יותר זמן CPU. לשם כך, לכל תהליך יש ערך nice - מספר בין -20 (עדיפות הכי גבוהה) ל-19 (עדיפות הכי נמוכה). ברירת המחדל היא 0.
ערך הnice משפיע על הקצב שבו הvruntime עולה:
- תהליך עם nice נמוך (עדיפות גבוהה): הvruntime שלו עולה לאט - אז הוא נשאר עם vruntime נמוך יותר זמן ומקבל יותר CPU
- תהליך עם nice גבוה (עדיפות נמוכה): הvruntime שלו עולה מהר - אז הוא מגיע ל-vruntime גבוה מהר יותר ומקבל פחות CPU
כש-weight תלוי בערך הnice. לתהליך עם nice=-20 יש weight גבוה (vruntime עולה לאט), ולתהליך עם nice=19 יש weight נמוך (vruntime עולה מהר).
בפועל, תהליך עם nice=-20 יקבל פי 100 יותר CPU מתהליך עם nice=19 אם שניהם רצים במקביל.
תזמון בזמן אמת - Real-Time scheduling¶
מעבר לCFS, לינוקס תומך גם בתזמון בזמן אמת (real-time) לתהליכים שדורשים תגובה מהירה ומובטחת. תהליכי real-time תמיד מקבלים עדיפות גבוהה יותר מתהליכי CFS רגילים.
יש שתי מדיניות:
- SCHED_FIFO - First In First Out: התהליך רץ עד שהוא מוותר על הCPU (או שמגיע תהליך RT עם עדיפות גבוהה יותר)
- SCHED_RR - Round Robin: כמו FIFO, אבל אם יש כמה תהליכי RT באותה עדיפות, הם מתחלפים בצורה מעגלית (עם time slice קבוע)
תהליכי RT מקבלים עדיפויות בטווח 1-99, כשכל העדיפויות האלה גבוהות מכל תהליך CFS רגיל.
בפועל, רוב התוכנות הרגילות לא משתמשות בRTreal-time scheduling. זה שמור לדברים כמו מערכות שליטה בתעשייה, עיבוד אודיו בזמן אמת, וכו'.
פסיקת הטיימר וtick - scheduler_tick¶
בפרק 2.4 למדנו שהטיימר החומרתי שולח פסיקה (IRQ0) כל כמה מילישניות, וזה מה שמאפשר לscheduler לקבל שליטה. בלינוקס, כל פסיקת טיימר מפעילה את הפונקציה scheduler_tick():
// kernel/sched/core.c (מפושט)
void scheduler_tick(void)
{
struct rq *rq = this_rq(); // תור הריצה של הCPU הנוכחי
struct task_struct *curr = rq->curr; // התהליך שרץ כרגע
// מעדכן את הvruntime של התהליך הנוכחי
curr->se.vruntime += delta_exec;
// בודק אם צריך להחליף תהליך
if (need_resched(curr)) {
set_tsk_need_resched(curr);
}
}
מתי need_resched מחזיר true?
- כשהvruntime של התהליך הנוכחי גדול מהvruntime של התהליך השמאלי ביותר בעץ (כלומר, מישהו "מגיע לו" יותר לרוץ)
- כשתהליך עם עדיפות גבוהה יותר התעורר
התדירות של הטיימר (tick rate) מוגדרת בזמן קימפול הקרנל. הערכים הנפוצים הם:
- 100 Hz - tick כל 10ms (נפוץ בשרתים - פחות overhead)
- 250 Hz - tick כל 4ms (ברירת מחדל בהרבה הפצות)
- 1000 Hz - tick כל 1ms (תגובתיות גבוהה, יותר overhead)
החלפת הקשר בפועל - context switch¶
כשהscheduler מחליט להחליף תהליך, מה בדיוק קורה? הפונקציה context_switch() מבצעת את ההחלפה בפועל:
// kernel/sched/core.c (מפושט)
static void context_switch(struct rq *rq,
struct task_struct *prev,
struct task_struct *next)
{
// 1. מחליפים את מרחב הזכרון
// טוענים את טבלת הpaging של התהליך החדש
switch_mm(prev->mm, next->mm);
// 2. מחליפים את הרגיסטרים ואת המחסנית
switch_to(prev, next);
}
switch_mm - החלפת מרחב הזכרון¶
הפונקציה switch_mm מחליפה את טבלת הpaging - כלומר טוענת ערך חדש ל-CR3. זה גורם לTLB flush (כל התרגומים השמורים נמחקים, כי עכשיו אנחנו במרחב כתובות אחר).
במעבדים מודרניים יש מנגנון שנקרא PCID (Process Context ID) שמאפשר לשמור תרגומים של כמה תהליכים בTLB במקביל, ובכך להימנע מflush מלא. לינוקס משתמש בPCID כשהמעבד תומך בזה.
שימו לב: אם שני threads באותו תהליך, הם חולקים את אותו mm_struct - אז switch_mm לא צריך לעשות כלום (אין החלפת CR3). זו עוד סיבה שתהליכונים מהירים יותר מתהליכים.
switch_to - החלפת אוגרים¶
המאקרו switch_to (בארכיטקטורת x86) שומר את כל הרגיסטרים של התהליך הנוכחי על המחסנית שלו, ומשחזר את הרגיסטרים של התהליך הבא מהמחסנית שלו. בפועל, זה קוד אסמבלי שנמצא ב-arch/x86/include/asm/switch_to.h.
הפקעה - preemption¶
יש שני סוגים של החלפות:
הפקעה רצונית - voluntary preemption¶
התהליך מוותר על הCPU מרצונו. זה קורה כשהוא:
- קורא ל-sleep() או wait()
- קורא ל-sched_yield() (מוותר במפורש)
- מבצע syscall שמצריך המתנה (למשל read מdisk)
בכל המקרים האלה, התהליך עובר למצב TASK_INTERRUPTIBLE ומסיר את עצמו מתור הריצה.
הפקעה כפויה - involuntary preemption¶
הscheduler לוקח את הCPU מהתהליך בכוח. זה קורה כש:
- פסיקת הטיימר קובעת שהתהליך רץ מספיק זמן
- תהליך עם עדיפות גבוהה יותר התעורר (למשל תהליך RT)
- הדגל TIF_NEED_RESCHED נדלק (בגלל אחת מהסיבות למעלה)
בלינוקס, גם קוד קרנלי יכול להיות מופקע (preemptible kernel) - מה שמשפר את התגובתיות של המערכת. אבל יש קטעי קוד קרנליים שבהם הpreemption מושבת באופן זמני (כשמחזיקים נעילה, למשל).
כלים לצפייה בתזמון¶
אפשר להשתמש בכלים שונים כדי לראות מידע על התזמון:
top ו-htop¶
מציגים את התהליכים הרצים ואת צריכת הCPU שלהם. בעמודה NI (nice) רואים את ערך הnice.
nice ו-renice¶
משנים את ערך הnice של תהליך:
# מריצים תוכנה עם nice=10 (עדיפות נמוכה)
nice -n 10 ./my_program
# משנים nice של תהליך קיים
renice -n 5 -p 1234
הsched בproc¶
כאן אפשר לראות את הvruntime, כמה context switch-ים היו, כמה זמן התהליך רץ, ועוד.
הstat בproc¶
סיכום¶
בהרצאה הזו למדנו את הצד הפנימי של תזמון תהליכים בלינוקס:
- מצבי תהליך: TASK_RUNNING, TASK_INTERRUPTIBLE, TASK_UNINTERRUPTIBLE, TASK_STOPPED, TASK_ZOMBIE
- task_struct: המבנה הענק שמייצג תהליך - כולל pid, mm (זכרון), files (קבצים), sched_entity (תזמון)
- הCFS: נותן לכל תהליך חלק הוגן, משתמש בvruntime ובעץ אדום-שחור
- vruntime: כל תהליך צובר זמן וירטואלי, ומי שצבר הכי פחות רץ הבא
- nice: משפיע על הקצב שבו vruntime עולה - ובכך על כמות הCPU שתהליך מקבל
- פסיקת הטיימר: מפעילה את scheduler_tick שמעדכנת vruntime ובודקת אם צריך להחליף
- context switch: כולל switch_mm (החלפת paging) ו-switch_to (החלפת אוגרים)
- preemption: רצונית (התהליך ישן) או כפויה (הscheduler מחליט)
עכשיו כשאנחנו מבינים את הscheduler, אנחנו יכולים לחבר את הכל ביחד - מהרגע שתוכנה קוראת ל-fork, דרך הsyscall שיוצר task_struct חדש, דרך הscheduler שמחליט מתי להריץ את התהליך החדש, ועד הcontext switch שבאמת מחליף אליו.