מתזמן התהליכים בקרנל לינוקס - איך מחליטים מי רץ עכשיו מתוך מאות מועמדים¶
במחשב עם ארבע ליבות מעבד יכולים לרוץ בו זמנית מאות תהליכים ותהליכונים. ברור שאי אפשר שכולם ירוצו ממש באותו רגע - מישהו חייב להחליט מי מקבל את המעבד עכשיו, לכמה זמן, ומתי הוא מפנה מקום לבא בתור. ההחלטה הזאת מתקבלת אלפי פעמים בשנייה על ידי רכיב בקרנל שנקרא מתזמן - scheduler, וההיגיון שמאחוריו הוא אחד הדברים היפים ביותר בעיצוב מערכות הפעלה.
למה בכלל צריך מתזמן¶
למעבד יש מספר קבוע ומוגבל של ליבות, אבל מספר התהליכים שרוצים לרוץ כמעט תמיד גבוה בהרבה. הפתרון הוא שיתוף זמן - כל תהליך מקבל פרוסת זמן קצרה על המעבד, ואז מוחלף בתהליך אחר. ההחלפה הזאת, שנקראת החלפת הקשר - context switch, קורית כל כך מהר, שוב ושוב, שנוצרת האשליה שכל התהליכים רצים בו זמנית ממש, גם כשיש הרבה יותר תהליכים מליבות פיזיות זמינות.
CFS - האלגוריתם שמנסה להיות הוגן לגמרי¶
קרנל לינוקס המודרני משתמש במתזמן שנקרא CFS, ראשי תיבות של Completely Fair Scheduler, מתזמן הוגן לחלוטין. הרעיון המרכזי שלו הוא פשוט להסביר, גם אם המימוש מורכב - לכל תהליך יש מונה שנקרא vruntime, זמן ריצה וירטואלי, שמצטבר ככל שהתהליך מקבל זמן מעבד בפועל. המתזמן תמיד בוחר להריץ את התהליך עם ה-vruntime הנמוך ביותר - כלומר, את מי שקיבל הכי פחות זמן מעבד עד עכשיו, יחסית לאחרים.
התוצאה היא הוגנות דינמית - אם תהליך אחד רץ הרבה, ה-vruntime שלו עולה, והוא נדחק אחורה בתור, בעוד תהליכים שקיבלו פחות זמן מעבד מקבלים עדיפות. כדי לנהל את זה ביעילות, הקרנל שומר את כל התהליכים המוכנים לרוץ בעץ אדום-שחור, מבנה נתונים מאוזן שמאפשר למצוא את התהליך עם ה-vruntime הנמוך ביותר במהירות גבוהה, גם כשיש אלפי תהליכים במערכת.
עדיפויות - nice values¶
לא כל התהליכים אמורים לקבל בדיוק אותה כמות זמן מעבד. אפשר להשפיע על החלוקה עם ערך עדיפות שנקרא nice - כל תהליך מקבל ערך שנע בין מינוס עשרים לפלוס תשע עשרה, כשערך נמוך יותר אומר עדיפות גבוהה יותר. תהליך עם עדיפות גבוהה יותר צובר vruntime לאט יותר יחסית לזמן האמיתי שהוא רץ, כך שהוא נשאר לעיתים קרובות יותר בראש התור. השם "nice" הגיע מהרעיון שתהליך עם ערך גבוה "נחמד" יותר כלפי תהליכים אחרים - הוא מוותר להם על יותר זמן מעבד.
מתי בכלל מתבצעת החלפה¶
ההחלפה בין תהליכים לא קורית באקראי. היא מתבצעת כשתהליך מסיים את פרוסת הזמן שהוקצתה לו, כשתהליך נחסם כי הוא מחכה למשאב כמו קלט ופלט, או כשמגיע אירוע חיצוני כמו פסיקת טיימר - timer interrupt, שמעירה את הקרנל באופן קבוע ומזכירה לו לבדוק אם הגיע הזמן להחליף תהליך. הפסיקה הקבועה הזאת היא בדיוק מה שמבטיח שאף תהליך לא יוכל להשתלט על המעבד לנצח, גם אם הוא נכנס בטעות ללולאה אינסופית.
מה קורה בפועל בהחלפת הקשר¶
כשהמתזמן מחליט להחליף תהליך, הוא צריך לשמור את כל מצב הרגיסטרים של התהליך היוצא, ולטעון את מצב הרגיסטרים של התהליך הנכנס - כתובת ההוראה הבאה שלו, ערכי המשתנים שהיו ברגיסטרים, ומצב המחסנית שלו. הפעולה הזאת לא חינמית - היא לוקחת זמן מעבד יקר, וזו בדיוק הסיבה שתהליכונים, שחולקים מרחב זיכרון, זולים יותר להחלפה מתהליכים מלאים, שדורשים גם החלפת טבלאות זיכרון.
למה כדאי להבין את זה¶
הבנה של איך המתזמן עובד משנה איך חושבים על ביצועים - למה תוכנית שיוצרת יותר מדי תהליכונים בלי צורך אמיתי דווקא מאטה את המערכת, ולמה עדיפות nice יכולה לפתור בעיות עומס בלי לשנות שורת קוד. זה אחד הרכיבים הכי מרתקים בכל קרנל מערכת הפעלה.
זה בדיוק מה שאנחנו מפרקים בקורס ליבת המחשב - איך המתזמן באמת מקבל החלטות, ולא רק מה קורה כשמסתכלים על תוצאה סופית של תהליכים שרצים.
ואם ניתוח ביצועים של תהליכים מבלבל אתכם, יש קהילה שכבר עברה את זה.
לסיכום¶
המתזמן של קרנל לינוקס מחליט כל הזמן מי רץ עכשיו על המעבד, ומנסה לעשות את זה בהוגנות באמצעות מעקב אחר vruntime של כל תהליך. עדיפויות nice מטות את החלוקה הזאת לכיוון תהליכים חשובים יותר, ופסיקות טיימר קבועות מבטיחות שההחלפה תמיד תקרה בזמן. כל זה קורה כל כך מהר, שהאשליה של ריצה מקבילה אמיתית נשמרת בשלמותה, גם על מעבד עם מספר ליבות מוגבל בהרבה ממספר התהליכים שרצים עליו.