6.3 - מתזמן התהליכים - הרצאה
הקדמה¶
בפרק 2.4 למדנו על context switch - איך המעבד שומר את מצב תוכנה אחת וטוען את מצב תוכנה אחרת. ראינו איך פסיקת הטיימר (IRQ0) קוטעת את התוכנה הנוכחית ומאפשרת לקרנל להחליף לתוכנה אחרת. אמרנו ש"הscheduler בוחר תוכנה מהרשימה" - אבל לא נכנסנו לפרטים של איך הוא בוחר.
עכשיו הגיע הזמן. בהרצאה הזו נלמד בדיוק איך הscheduler של לינוקס עובד מבפנים - מהם מצבי הprocess, מהו המבנה task_struct הענק שמייצג process בקרנל, ואיך אלגוריתם הCFS (Completely Fair Scheduler) מחליט מי רץ ולכמה זמן.
מצבי תהליך בלינוקס - process states¶
בפרק 5.2 למדנו שלכל process יש PID ו-PPID, ושprocesses יכולים להיות זומבים. אבל בתוך הקרנל, לכל process יש מצב (state) מדויק יותר. אלו המצבים העיקריים:
| מצב | שם | הסבר |
|---|---|---|
TASK_RUNNING |
רץ / מוכן לרוץ | הprocess או רץ כרגע על המעבד, או ממתין בqueue (מוכן לרוץ ברגע שהscheduler יבחר בו) |
TASK_INTERRUPTIBLE |
ישן (ניתן להפסקה) | הprocess ישן - ממתין לאירוע (קלט מהמקלדת, נתונים מהרשת, וכו'). אפשר להעיר אותו עם סיגנל |
TASK_UNINTERRUPTIBLE |
ישן (לא ניתן להפסקה) | הprocess ישן וממתין לפעולת IO קריטית (למשל קריאה מדיסק). אי אפשר להפסיק אותו עם סיגנל - אפילו SIGKILL לא יעבוד עד שהIO יסתיים. זהו המצב "D" שרואים ב-top |
TASK_STOPPED |
עצור | הprocess נעצר - בדרך כלל בגלל סיגנל SIGSTOP או כי debugger עצר אותו (ptrace) |
TASK_ZOMBIE |
זומבי | הprocess סיים לרוץ אבל process האב עדיין לא קרא ל-wait() כדי לאסוף את הexit code שלו (כזכור מפרק 5.2) |
מעברים בין מצבים¶
fork()
|
v
TASK_RUNNING (ready)
/ \
selected by waiting
the scheduler for event
| \
v v
TASK_RUNNING TASK_INTERRUPTIBLE
(running on CPU) or TASK_UNINTERRUPTIBLE
| |
timer/yield event occurred / signal
| |
v v
TASK_RUNNING TASK_RUNNING
(ready) (ready)
|
exit()
|
v
TASK_ZOMBIE
|
wait() from parent
|
v
[removed]
שימו לב שTASK_RUNNING מייצג שני מצבים - גם "רץ כרגע על CPU" וגם "מוכן לרוץ, ממתין בqueue". ההבדל הוא האם הprocess באמת מקושר לCPU מסוים ברגע זה.
המבנה task_struct - הייצוג של process בקרנל¶
בפרק 2.4 הזכרנו את הPCB (Process Control Block) - מבנה נתונים שהקרנל שומר עבור כל process. בלינוקס, הPCB הזה נקרא task_struct, והוא מבנה ענק - אלפי בתים שמכילים את כל מה שהקרנל צריך לדעת על process.
הנה השדות המרכזיים (מאוד מפושט - בפועל יש הרבה יותר):
// include/linux/sched.h (very simplified)
struct task_struct {
// === process state ===
unsigned int state; // TASK_RUNNING, TASK_INTERRUPTIBLE, ...
// === identification ===
pid_t pid; // process ID
pid_t tgid; // Thread Group ID
// === process name ===
char comm[TASK_COMM_LEN]; // program name (e.g. "bash")
// === memory ===
struct mm_struct *mm; // all the info about the process's memory
// (paging tables, VMAs, heap, stack)
// === files ===
struct files_struct *files; // file descriptor table (fd table)
// === signals ===
struct signal_struct *signal; // info about signals and handlers
// === process tree ===
struct task_struct *parent; // parent process
struct list_head children; // list of child processes
struct list_head sibling; // siblings (children of the same parent)
// === scheduling ===
struct sched_entity se; // info for the scheduler (including vruntime)
int prio; // priority
// === kernel stack ===
void *stack; // pointer to the process's kernel stack
// ... hundreds more fields ...
};
כמה נקודות חשובות:
pid מול tgid¶
בפרק 5.8 למדנו שthreads חולקים את אותו מרחב זכרון. בתוך הקרנל, כל thread הוא task_struct נפרד עם pid משלו. אבל כל הthreads של אותו process חולקים את אותו tgid (Thread Group ID). כשאנחנו קוראים ל-getpid() מיוזר מוד, מה שחוזר הוא בעצם ה-tgid - ולא ה-pid הקרנלי. ככה כל הthreads של אותו process "רואים" את אותו PID.
הmm_struct¶
השדה mm מצביע למבנה שמכיל את כל המידע על הזכרון של הprocess:
- מצביע לטבלת הpaging (מה שנטען לCR3)
- רשימת כל הVMAs (Virtual Memory Areas - אזורי הזכרון: heap, stack, mmap-ים, קוד, נתונים)
- מונים וסטטיסטיקות על שימוש בזכרון
כשעושים fork, הmm_struct מועתק (עם COW - Copy On Write כזכור מפרק 5.7). כשעושים threads עם clone, ה-mm_struct משותף - וזו בדיוק הסיבה שthreads רואים את אותו זכרון.
המצביע current¶
בכל רגע נתון, הקרנל צריך לדעת מי הprocess שרץ כרגע על הCPU. לשם כך יש מאקרו שנקרא current שמחזיר מצביע ל-task_struct של הprocess הנוכחי:
// anywhere in the kernel code you can do:
printk("current process: %s (pid=%d)\n", current->comm, current->pid);
תור הריצה - run queue¶
כל CPU במערכת מנהל queue ריצה (run queue) משלו. הqueue מכיל את כל הprocesses שנמצאים במצב TASK_RUNNING ומחכים לרוץ על הCPU הזה.
המבנה שמייצג את הqueue נקרא struct rq (run queue):
// kernel/sched/sched.h (simplified)
struct rq {
unsigned int nr_running; // how many processes are waiting
struct cfs_rq cfs; // the CFS queue (the regular scheduler)
struct rt_rq rt; // the real-time queue
struct task_struct *curr; // the process currently running
// ...
};
לכל CPU יש rq משלו, מה שמאפשר לCPU-ים שונים לתזמן processes באופן בלתי תלוי (פחות נעילות, יותר ביצועים).
הCFS - Completely Fair Scheduler¶
מאז גרסה 2.6.23 של הקרנל (2007), הscheduler ברירת המחדל של לינוקס הוא הCFS - Completely Fair Scheduler. הרעיון המרכזי שלו פשוט: לתת לכל process את החלק ההוגן שלו מזמן הCPU.
הרעיון: זמן ריצה וירטואלי - vruntime¶
לכל process יש מונה שנקרא vruntime (virtual runtime) שעוקב אחרי כמה זמן CPU הprocess קיבל. הכלל הוא:
הprocess עם הvruntime הנמוך ביותר רץ הבא.
למה? כי vruntime נמוך אומר שהprocess קיבל פחות זמן CPU מאחרים - אז הוא "מגיע לו" לרוץ.
כשprocess רץ, הvruntime שלו עולה. כשהוא ישן (ממתין לIO), הvruntime שלו לא עולה. ככה processes שישנים הרבה (כמו עורך טקסט שמחכה להקלדה) יקבלו זמן CPU מיד כשהם מתעוררים - כי הvruntime שלהם נמוך יחסית.
עץ אדום-שחור - Red-Black Tree¶
אבל איך הscheduler מוצא במהירות את הprocess עם הvruntime הנמוך ביותר? הרי יכולים להיות מאות processes בqueue.
הCFS משתמש במבנה נתונים שנקרא עץ אדום-שחור (Red-Black Tree) - עץ חיפוש בינארי מאוזן. כל הצמתים בעץ מסודרים לפי vruntime, והצומת השמאלי ביותר (עם הvruntime הנמוך ביותר) הוא תמיד הprocess הבא שירוץ.
במבנה הזה, הצומת השמאלי ביותר (vruntime=20) הוא הprocess הבא שירוץ. מציאת הצומת השמאלי ביותר היא פעולה של O(1) כי הקרנל שומר עליו מצביע.
הוספה והסרה מהעץ הן O(log n) - מהיר מספיק גם כשיש אלפי processes.
// kernel/sched/fair.c (simplified)
struct sched_entity {
struct rb_node run_node; // the node in the red-black tree
u64 vruntime; // the virtual time accumulated
// ...
};
חלון התזמון - scheduling latency¶
בניגוד לscheduler-ים ישנים שנתנו לכל process "פרוסת זמן" קבועה (time slice), הCFS עובד אחרת.
הוא מגדיר חלון תזמון (scheduling latency) - פרק זמן שבו כל process מוכן-לריצה אמור לקבל לפחות הזדמנות אחת לרוץ. בדרך כלל זה בין 6 ל-24 מילישניות (תלוי בכמות הprocesses).
הזמן מחולק בין כל הprocesses המוכנים. למשל, אם חלון התזמון הוא 20ms ויש 4 processes מוכנים, כל אחד יקבל 5ms. אם יש 10 processes, כל אחד יקבל 2ms.
ערכי nice ועדיפות¶
לא כל הprocesses שווים. לפעמים רוצים שprocess מסוים יקבל יותר זמן CPU. לשם כך, לכל process יש ערך nice - מספר בין -20 (עדיפות הכי גבוהה) ל-19 (עדיפות הכי נמוכה). ברירת המחדל היא 0.
ערך הnice משפיע על הקצב שבו הvruntime עולה:
- הprocess עם nice נמוך (עדיפות גבוהה): הvruntime שלו עולה לאט - אז הוא נשאר עם vruntime נמוך יותר זמן ומקבל יותר CPU
- הprocess עם nice גבוה (עדיפות נמוכה): הvruntime שלו עולה מהר - אז הוא מגיע ל-vruntime גבוה מהר יותר ומקבל פחות CPU
כש-weight תלוי בערך הnice. לprocess עם nice=-20 יש weight גבוה (vruntime עולה לאט), ולprocess עם nice=19 יש weight נמוך (vruntime עולה מהר).
בפועל, process עם nice=-20 יקבל פי 100 יותר CPU מprocess עם nice=19 אם שניהם רצים במקביל.
תזמון בזמן אמת - Real-Time scheduling¶
מעבר לCFS, לינוקס תומך גם בתזמון בזמן אמת (real-time) לprocesses שדורשים תגובה מהירה ומובטחת. הprocesses של real-time תמיד מקבלים עדיפות גבוהה יותר מprocesses CFS רגילים.
יש שתי מדיניות:
- SCHED_FIFO - First In First Out: הprocess רץ עד שהוא מוותר על הCPU (או שמגיע process RT עם עדיפות גבוהה יותר)
- SCHED_RR - Round Robin: כמו FIFO, אבל אם יש כמה processes RT באותה עדיפות, הם מתחלפים בצורה מעגלית (עם time slice קבוע)
הprocesses של RT מקבלים עדיפויות בטווח 1-99, כשכל העדיפויות האלה גבוהות מכל process CFS רגיל.
בפועל, רוב התוכנות הרגילות לא משתמשות בRTreal-time scheduling. זה שמור לדברים כמו מערכות שליטה בתעשייה, עיבוד אודיו בזמן אמת, וכו'.
הinterrupt הטיימר וtick - scheduler_tick¶
בפרק 2.4 למדנו שהטיימר החומרתי שולח interrupt (IRQ0) כל כמה מילישניות, וזה מה שמאפשר לscheduler לקבל שליטה. בלינוקס, כל interrupt טיימר מפעילה את הפונקציה scheduler_tick():
// kernel/sched/core.c (simplified)
void scheduler_tick(void)
{
struct rq *rq = this_rq(); // the run queue of the current CPU
struct task_struct *curr = rq->curr; // the process currently running
// updates the vruntime of the current process
curr->se.vruntime += delta_exec;
// checks if a process switch is needed
if (need_resched(curr)) {
set_tsk_need_resched(curr);
}
}
מתי need_resched מחזיר true?
- כשהvruntime של הprocess הנוכחי גדול מהvruntime של הprocess השמאלי ביותר בעץ (כלומר, מישהו "מגיע לו" יותר לרוץ)
- כשprocess עם עדיפות גבוהה יותר התעורר
התדירות של הטיימר (tick rate) מוגדרת בזמן קימפול הקרנל. הערכים הנפוצים הם:
- 100 Hz - tick כל 10ms (נפוץ בשרתים - פחות overhead)
- 250 Hz - tick כל 4ms (ברירת מחדל בהרבה הפצות)
- 1000 Hz - tick כל 1ms (תגובתיות גבוהה, יותר overhead)
החלפת הקשר בפועל - context switch¶
כשהscheduler מחליט להחליף process, מה בדיוק קורה? הפונקציה context_switch() מבצעת את ההחלפה בפועל:
// kernel/sched/core.c (simplified)
static void context_switch(struct rq *rq,
struct task_struct *prev,
struct task_struct *next)
{
// 1. switch the memory space
// load the new process's paging table
switch_mm(prev->mm, next->mm);
// 2. swap the registers and the stack
switch_to(prev, next);
}
switch_mm - החלפת מרחב הזכרון¶
הפונקציה switch_mm מחליפה את טבלת הpaging - כלומר טוענת ערך חדש ל-CR3. זה גורם לTLB flush (כל התרגומים השמורים נמחקים, כי עכשיו אנחנו במרחב כתובות אחר).
במעבדים מודרניים יש מנגנון שנקרא PCID (Process Context ID) שמאפשר לשמור תרגומים של כמה processes בTLB במקביל, ובכך להימנע מflush מלא. לינוקס משתמש בPCID כשהמעבד תומך בזה.
שימו לב: אם שני threads באותו process, הם חולקים את אותו mm_struct - אז switch_mm לא צריך לעשות כלום (אין החלפת CR3). זו עוד סיבה שthreads מהירים יותר מprocesses.
switch_to - החלפת אוגרים¶
המאקרו switch_to (בארכיטקטורת x86) שומר את כל הרגיסטרים של הprocess הנוכחי על המחסנית שלו, ומשחזר את הרגיסטרים של הprocess הבא מהמחסנית שלו. בפועל, זה קוד אסמבלי שנמצא ב-arch/x86/include/asm/switch_to.h.
הפקעה - preemption¶
יש שני סוגים של החלפות:
הפקעה רצונית - voluntary preemption¶
הprocess מוותר על הCPU מרצונו. זה קורה כשהוא:
- קורא ל-sleep() או wait()
- קורא ל-sched_yield() (מוותר במפורש)
- מבצע syscall שמצריך המתנה (למשל read מdisk)
בכל המקרים האלה, הprocess עובר למצב TASK_INTERRUPTIBLE ומסיר את עצמו מqueue הריצה.
הפקעה כפויה - involuntary preemption¶
הscheduler לוקח את הCPU מהprocess בכוח. זה קורה כש:
- הinterrupt הטיימר קובעת שהprocess רץ מספיק זמן
- הprocess עם עדיפות גבוהה יותר התעורר (למשל process RT)
- הדגל TIF_NEED_RESCHED נדלק (בגלל אחת מהסיבות למעלה)
בלינוקס, גם קוד קרנלי יכול להיות מופקע (preemptible kernel) - מה שמשפר את התגובתיות של המערכת. אבל יש קטעי קוד קרנליים שבהם הpreemption מושבת באופן זמני (כשמחזיקים נעילה, למשל).
כלים לצפייה בתזמון¶
אפשר להשתמש בכלים שונים כדי לראות מידע על התזמון:
top ו-htop¶
מציגים את הprocesses הרצים ואת צריכת הCPU שלהם. בעמודה NI (nice) רואים את ערך הnice.
nice ו-renice¶
משנים את ערך הnice של process:
# running a program with nice=10 (low priority)
nice -n 10 ./my_program
# changing the nice of an existing process
renice -n 5 -p 1234
הsched בproc¶
כאן אפשר לראות את הvruntime, כמה context switch-ים היו, כמה זמן הprocess רץ, ועוד.
הstat בproc¶
סיכום¶
בהרצאה הזו למדנו את הצד הפנימי של תזמון processes בלינוקס:
- מצבי process: TASK_RUNNING, TASK_INTERRUPTIBLE, TASK_UNINTERRUPTIBLE, TASK_STOPPED, TASK_ZOMBIE
- task_struct: המבנה הענק שמייצג process - כולל pid, mm (זכרון), files (קבצים), sched_entity (תזמון)
- הCFS: נותן לכל process חלק הוגן, משתמש בvruntime ובעץ אדום-שחור
- vruntime: כל process צובר זמן וירטואלי, ומי שצבר הכי פחות רץ הבא
- nice: משפיע על הקצב שבו vruntime עולה - ובכך על כמות הCPU שprocess מקבל
- הinterrupt הטיימר: מפעילה את scheduler_tick שמעדכנת vruntime ובודקת אם צריך להחליף
- context switch: כולל switch_mm (החלפת paging) ו-switch_to (החלפת אוגרים)
- preemption: רצונית (הprocess ישן) או כפויה (הscheduler מחליט)
עכשיו כשאנחנו מבינים את הscheduler, אנחנו יכולים לחבר את הכל ביחד - מהרגע שתוכנה קוראת ל-fork, דרך הsyscall שיוצר task_struct חדש, דרך הscheduler שמחליט מתי להריץ את הprocess החדש, ועד הcontext switch שבאמת מחליף אליו.