התכוונתי לכתוב פוסט על שגיאות דיזיין נפוצות במערכות RT/Embedded, אבל הבנתי שנדרש רקע במושגים שלא כל מפתח מכיר, לפעמים גם לא כל מפתח זמן-אמת.
אז החלטתי להתחיל לפני כן בפוסט קצר כרקע – על נושא כללי יותר, אבל לא פחות מעניין, וחשוב לכל מי שעוסק במערכות Hard Realtime.
תזמון משימות
אחד התפקידים החשובים של כל מערכת הפעלה, אולי החשוב ביותר, הוא תזמון המשימות.
במערכות הבסיסיות ביותר, כמו בחלק ממערכות ההפעלה לזמן-אמת, ישנו מספר לא גדול של "משימות" (Tasks) שביניהן מערכת ההפעלה צריכה לבחור מי תרוץ בכל רגע נתון. במערכות הפעלה מורכבות יותר, כמו אלו שרצות על המחשב האישי שלנו, ישנו מגוון רחב יותר של ישויות, כמו תהליכים (Processes), תהליכונים (Threads), ואחרים כמו Services או Daemons. לכל משימה, תהליך או ישות אחרת ישנה "קדימות" או "עדיפות" (Priority) הקובעת כמה חשוב שהיא תקבל זמן ריצה על המעבד ביחס לאחרות. הדבר הזה נכון לכמעט כל מערכת הפעלה; אבל מה המשמעות בפועל של חשיבות זמן ריצה ביחס לאחרים? כאן התשובה כבר יכולה להשתנות מאוד, בהתאם לאופי ולדרישות של מערכת ההפעלה.
מערכות הפעלה גנריות
מערכות ההפעלה העיקריות המוכרות לנו, כמו ווינדוס, לינוקס או MacOS, צריכות לתמוך במגוון אינסופי של יישומים ויכולות. חלקם משתייכים למערכת ההפעלה עצמה. אחרים הם אפליקציות שמופעלות דרך ממשק משתמש. כאלו שממתינות בסבלנות ללחיצה על כפתור, או צרכניות משאבים שלא עוצרות לרגע כמו משחקי וידאו. יכולים לרוץ ברקע תהליכים שמבצעים חישובים או ניתוחים; תהליכים שממתינים לתקשורת או יוזמים כזו; דרייברים שמתקשרים מול מסך, עכבר או מדפסת. מערכת הפעלה כזו צריכה להיות יעילה מצד אחד וגמישה מצד שני. אסור לה לגרום לתהליך כלשהו הרעבה מתמשכת. היא צריכה לנצל את המשאבים באופן יעיל. היא צריכה להקפיד על אינטראקטיביות עם המשתמש. והיא צריכה לעמוד בעוד הרבה מאוד דרישות ואילוצים. מערכות הפעלה כאלו מחלקות את זמן הריצה בין המשימות השונות באופן שייתן פתרון גנרי סביר לכל מצב. בדרך כלל, ניתן גם במערכות הפעלה כאלה להגדיר Priority לתהליך ספציפי. זה יגרום למערכת להעדיף אותו על פני אחרים ולתת לו יותר זמן מכפי שהיתה נותנת ללא ההגדרה הזו (או להיפך — בהתאם ל-Priority), באופן שישתלב באלגוריתם הכללי של חלוקת הזמן. ניתן לשלוט בפרמטרים רבים של חלוקת הזמן בין ישויות שונות במערכת. אבל בסופו של דבר, קשה עד בלתי אפשרי לוודא שפונקציות כאלה ואחרות ירוצו מיד ברגע הנדרש ויסתיימו בוודאות תוך פרק זמן נתון. זה פחות מפריע אם האפליקציה שלנו צריכה להגיב תוך פחות משניה. זה קצת יותר בעייתי אם היא צריכה להגיב תוך פחות ממילישניה. אולי גם הרבה פחות.
מערכות הפעלה עם "תזמון קוטע" (Preemptive Scheduling)
במערכות בהן נדרש זמן תגובה מיידי וחסום — מערכות Hard-RT — אלגוריתמים גנריים של חלוקת זמני ריצה אינם אופציה אפשרית. במערכות כאלו, נדרשת משמעות אבסולוטית ל-Priority: אם משימה בקדימות גבוהה צריכה לרוץ ברגע מסויים — היא תקבל את זמן המעבד מייד באותו הרגע. המשימה שרצה על המעבד עד לאותו רגע תעצור באופן מיידי ותפנה את מקומה למשימה הקריטית יותר. מערכת תזמון כזו מכונה Preemptive Scheduling. במערכת כזו ניתן להבטיח זמן תגובה חסום למשימות בעלות קדימות גבוהה. מצד שני, אין ארוחות חינם, ושימוש במערכת כזו מביא איתו גם בעיות מסוגים שונים.
פגיעה בביצועים
מערכת שבה זמן התגובה (Latency) מהיר יותר, היא מערכת שבה הביצועים הכוללים (Throughput) בדרך כלל נמוכים יותר. זה לא בהכרח אינטואיטיבי, ולכן אנשים רבים מבלבלים בין שני המושגים. למשל, אם יש צורך לבצע חישובים רבים מאוד בזמן קצר, קיימת לעתים נטייה לחשוב שמדובר במערכת שדורשת "יותר רילטיימיות". אבל פעמים רבות, ההיפך הוא הנכון. מערכת הפועלת ב-Preemptive Scheduling יכולה להבטיח ביצוע פעולות מסויימות — קצרות, בדרך כלל — בפרק זמן ידוע וחסום; אך הדרך להבטיח זאת, היא ביצוע הרבה יותר Context Switches, גם בנקודות בקוד שבהן יש לזה עלות גבוהה. כל Context Switch דורש מהמעבד והזכרון עבודה נוספת; כל Context Switch הופך את ה-Cache ברמות השונות ללא רלוונטי; משימה שרצה באופן בלעדי וממתינה לאירועים שונים מבלי לשחרר את ה-CPU מבזבזת זמן יקר על Cycles שאינם מועילים. ולכן, מערכת כזו דווקא מגבילה את הביצועים ביחס למערכות עם תזמון יותר מתוחכם וגמיש. אם מערכת כלשהי צריכה לבצע הרבה number-crunching במהירות לאורך זמן, והיא פחות רגישה למילישנייה יותר או פחות — כמעט בוודאות מערכת הפעלה ללא Preemption תספק ביצועים טובים יותר.
הרעבה
במערכות הפעלה רגילות, קשה מאוד להגיע למצב של הרעבה. מנגנון התזמונים דואג שכל יחידה תקבל זמן מעבד, גם אם מדובר בתהליך או תהליכון בעל Priority נמוך מאוד. במערכות שבהן מתבצע Preemption (וגם תחת קונפיגורציות דומות ללא Preemption מלא), ה-Priority היא מוחלטת: משימה או תהליך שיש לו עדיפות על פני אחרים, יקטעו כל משימה אחרת ויקבלו את זמן המעבד ללא הגבלה. הם יפנו את זמן המעבד רק כאשר יסיימו את העבודה הנוכחית שלהם, או במקרה שמישהו בעל עדיפות גבוהה משלהם יבצע גם להם Preemption. ההבדל בין thread שמתקדם לאט לבין thread שמורעב לחלוטין הוא אקוטי. בעיקר אם הוא צריך לבצע רק מעט מאוד עבודה מפעם לפעם (כמו לקרוא ערך כלשהו או לדווח "Keepalive"), ועוד יותר, אם הוא מחזיק לרגע במשאב קריטי — ואינו יכול יותר לשחרר אותו.
היפוך עדיפות
היפוך עדיפות, או Priority Inversion, הוא מקרה מיוחד שנובע מהתופעה שתוארה בסעיף הקודם.
נניח שיש לנו מערכת עם שלוש "משימות" — tasks: משימה A בעדיפות 10 (גבוהה), משימה B בעדיפות 6 (בינונית), ומשימה C בעדיפות 2 (נמוכה).
אנו מצפים שבכל רגע נתון, אם משימה A צריכה לרוץ — היא תעצור את המשימה הנוכחית ותתחיל לבצע את עבודתה. משימה B תתבצע רק לאחר ש-A סיימה את עבודתה הנוכחית ובינתיים אינה זקוקה למעבד. משימה C תתבצע אך ורק בזמנים שבהם גם A אינה צריכה את המעבד וגם B אינה צריכה אותו.
נניח מצב בו משימה C התחילה לרוץ. כחלק מעבודתה, היא לקחה לעצמה משאב, למשל — נעלה Mutex. כעת (למשל, כתוצאה מפסיקה או קבלת מסר) משימה B צריכה לעבוד, ולכן המערכת עוצרת את C באותו הרגע, ומפנה את המעבד לטובת B. בעוד B עושה את עבודתה, מתעוררת גם משימה A. המעבד, כמובן, עוצר את משימה B ומאפשר למשימה A להתחיל לרוץ. על מנת להשלים את המשימה, A צריכה גם היא את ה-Mutex, ולכן היא מנסה לקחת אותו; אך הוא נעול כרגע, ולכן A אינה יכולה להמשיך בינתיים. המעבד ייתן בינתיים למשימה B לרוץ, עד שה-Mutex ישוחרר. כל עוד B רצה, משימה C מורעבת; כתוצאה מכך, היא אינה יכולה לשחרר את ה-Mutex.
לכן, בפועל, הריצה של B, בעלת העדיפות הבינונית, מרעיבה לא רק את C הנמוכה, אלא גם את משימה A, בעלת העדיפות הגבוהה, שממתינה לשווא ל-Mutex הנעול. רק לאחר ש-B תסיים ותפנה את המעבד, משימה C תוכל להמשיך לרוץ, וברגע בו היא תשחרר את ה-Mutex, ניתן יהיה לעצור אותה ולתת שוב למשימה A להמשיך את עבודתה. המצב הזה, בו משימה בעלת עדיפות גבוהה (A) נאלצת להמתין ומורעבת עד שתסתיים משימה בעלת עדיפות נמוכה יותר (B), מכונה Priority Inversion. ככל שהמערכת מורכבת יותר, והתלויות במשאבים משותפים רבות יותר, כך גדל הסיכוי לסיטואציה כזו.
הורשת עדיפות
אחת הדרכים בהן מערכות הפעלה שיש להן Preemptive Scheduling מתמודדות עם סיטואציה של Priority Inversion היא באמצעות "הורשת עדיפות", או Priority Inheritance.
מהי הורשת עדיפות?
נחזור למקרה שתואר קודם לכן: משימה C נעלה Mutex, ולכן משימה A אינה יכולה לרוץ כרגע, ומשימה B, בעלת העדיפות הבינונית, היא זו שרצה וכך הופכת בפועל לבעלת עדיפות גבוהה יותר. במערכת בעלת Priority Inheritance, כאשר משימה A תנסה לקחת את ה-Mutex שנעול כרגע, מערכת ההפעלה תזהה את המקרה. במצב כזה, משימה C תקבל באופן זמני את אותה העדיפות של משימה A שממתינה לה. לכן, מי שתרוץ בפועל ברגע בו A נעצרת בגלל ה-Mutex אינה B אלא C, שקיבלה עדיפות גבוהה יותר. משימה C תמשיך לרוץ עד שתשחרר את ה-Mutex; בשלב הזה, העדיפות המקורית והנמוכה תוחזר לה, ומשימה A תוכל להמשיך לרוץ. משימה B תמתין עד לסיום הריצה של C ואז A, ורק לאחר מכן תקבל זמן ריצה. באופן הזה, נמנע מצב של Priority Inversion.
מרבית מערכות ההפעלה המודרניות שהן RTOS מבצעות הורשת עדיפות, אך חשוב לשים לב כי מדובר בסיטואציה שאינה תמיד פשוטה, ובפתרונות שהם מורכבים יחסית למערכות הפעלה אלה, שבדרך כלל הן "רזות" ופשוטות מאוד. ייתכנו מצבים מורכבים יותר, למשל, כאלו בהם גם משימה C אינה יכולה להמשיך בשל משאב שמחזיקה משימה אחרת D, ושרשרת של תלויות מסוג זה יכולה להיות מורכבת יותר ויותר. כמו כן, לא כל משאב הוא דו-צדדי; ישנם משאבים בהם יכולים להיות מעורבים יותר מאשר שתי משימות בלבד. לכן, חשוב בכל מקרה לנסות ולהיזהר ממצבים שעלולים לגרור Priority Inversion, כיוון שלא בכל מצב מערכת ההפעלה תדע לבוא לעזרתנו. למשל, ב-FreeRTOS, קיים מנגנון של Priority Inheritance במצב שתואר בו המשאב המשותף הוא Mutex, אך המנגנון אינו נכנס לפעולה כאשר מדובר במשאבים אחרים, למשל Binary Semaphore. בנוסף, מנגנון ההורשה אינו הדוק, ועל מנת לפשט את המימוש, ייתכן ששינויי העדיפויות לא יתבצעו בדיוק בזמן הנדרש באופן אופטימלי.
הבנת מנגנוני התזמון
הבנה של מנגנונני התזמון של מערכת ההפעלה לא תמיד מעניינת את מרבית המפתחים, אך היא קריטית לאלו שכותבים קוד על מערכות Realtime (בין אם Hard-RT או Soft-RT) כדי לוודא שהמערכת תתפקד באופן הרצוי.
ישנם כמובן עוד נושאים רבים הנוגעים לתזמון משימות, אולם אלו שהוזכרו כאן הם החשובים ביותר להבנה במערכות מסוג זה, ואי הבנה של דרך פעולתם עלולה לגרום למערכות ליפול בנקודות הקריטיות שלהן.
זהו בסיס נדרש להבנה של נושאים מורכבים יותר, שבהם אגע בפוסטים הבאים.