מבוא למערכות הפעלה

היי הבר! ברצוני להביא לידיעתכם סדרת מאמרים-תרגום של ספרות מעניינת אחת לדעתי - OSTEP. חומר זה דן באופן די עמוק בעבודה של מערכות הפעלה דמויות יוניקס, כלומר עבודה עם תהליכים, מתזמנים שונים, זיכרון ורכיבים דומים אחרים המרכיבים מערכת הפעלה מודרנית. אתה יכול לראות את המקור של כל החומרים כאן כאן. שימו לב שהתרגום נעשה בצורה לא מקצועית (די חופשי), אבל אני מקווה ששמרתי על המשמעות הכללית.

ניתן למצוא עבודת מעבדה בנושא זה כאן:

• מקורי
• מקורי
• ההתאמה האישית שלי

חלקים אחרים:

• חלק 1: מבוא
• חלק 2: הפשטה: התהליך
• חלק 3: מבוא ל- Process API
• חלק 4: מבוא למתזמן
• חלק 5: מתזמן MLFQ

אתה יכול גם לבדוק את הערוץ שלי בכתובת מִברָק =)

תכנון: תור משוב רב רמות

בהרצאה זו, נדבר על הבעיות של פיתוח אחת הגישות המפורסמות ביותר ל
תכנון, מה שנקרא תור משוב רב רמות (MLFQ). מתזמן MLFQ תואר לראשונה בשנת 1962 על ידי פרננדו ג'יי קורבאטו במערכת בשם
מערכת שיתוף זמן תואמת (CTSS). עבודות אלה (כולל עבודות מאוחרות יותר על
Multics) היו מועמדים לאחר מכן לפרס טיורינג. המתזמן היה
לאחר מכן השתפר ורכש את המראה שניתן למצוא כבר ב
כמה מערכות מודרניות.

אלגוריתם MLFQ מנסה לפתור 2 בעיות יסוד חופפות.
קודם כל, הוא מנסה לייעל את זמן האספקה, שכפי שדיברנו בהרצאה הקודמת, מותאם לפי שיטת ההתחלה בראש התור הכי הרבה
משימות קצרות. עם זאת, מערכת ההפעלה לא יודעת כמה זמן יפעל תהליך זה או אחר, וזה
ידע הכרחי לתפעול אלגוריתמי SJF, STCF. שנית, MLFQ מנסה
להפוך את המערכת לרספונסיבית עבור המשתמשים (לדוגמה, עבור אלה שיושבים ו
בוהה במסך בזמן ההמתנה להשלמת המשימה) ובכך למזער את הזמן
תְגוּבָה. למרבה הצער, אלגוריתמים כמו RR מפחיתים את זמן התגובה, אבל
יש השפעה רעה על מדד זמן האספקה. מכאן הבעיה שלנו: איך לעצב
מתזמן שיענה על הדרישות שלנו ובו זמנית לא יודע כלום
אופי התהליך, באופן כללי? כיצד יכול המתזמן ללמוד את המאפיינים של משימות,
שהוא משיק וכך לקבל החלטות תזמון טובות יותר?

מהות הבעיה: איך לתכנן את הגדרת המשימות ללא ידע מושלם?
כיצד לעצב מתזמן הממזער בו זמנית את זמן התגובה
למשימות אינטראקטיביות ובמקביל מצמצם את זמן האספקה ​​מבלי לדעת
ידע על זמן ביצוע המשימה?

הערה: למידה מאירועים קודמים

תור MLFQ הוא דוגמה מצוינת למערכת שאומנים עליה
אירועי עבר כדי לחזות את העתיד. גישות כאלה הן לעתים קרובות
נמצא במערכת ההפעלה (וענפים רבים אחרים במדעי המחשב, כולל ענפים
תחזיות חומרה ואלגוריתמי שמירה במטמון). טיולים דומים
מופעלות כאשר למשימות יש שלבים התנהגותיים ולכן הן ניתנות לחיזוי.
עם זאת, צריך להיזהר עם טכניקה זו, כי התחזיות הן קלות מאוד.
עלול להתברר כשגוי ולהוביל את המערכת לקבל החלטות גרועות יותר מאשר
יהיה ללא ידע כלל.

MLFQ: כללים בסיסיים

שקול את הכללים הבסיסיים של אלגוריתם MLFQ. ולמרות המימושים של אלגוריתם זה
יש כמה, הגישות הבסיסיות דומות.
ביישום אותו נשקול, ל-MLFQ יהיו כמה
תורים נפרדים, שלכל אחד מהם תהיה עדיפות שונה. בכל עת,
המשימה המוכנה לביצוע נמצאת באותו תור. MLFQ משתמש בסדרי עדיפויות,
להחליט איזו משימה להפעיל לביצוע, כלומר. משימה עם גבוה יותר
priority (משימה מהתור עם העדיפות הגבוהה ביותר) תושק בהתחלה
תוֹר.
כמובן, יכולה להיות יותר ממשימה אחת בתור מסוים, אז
אז תהיה להם אותה עדיפות. במקרה זה, המנגנון ישמש
RR לתכנון השקה בין המשימות הללו.
כך אנו מגיעים לשני כללים בסיסיים עבור MLFQ:

• כלל 1: אם עדיפות (A) > עדיפות (B), משימה A תפעל (B לא תפעל)
• כלל 2: אם עדיפות (A) = עדיפות (B), A&B מתחילים באמצעות RR

בהתבסס על האמור לעיל, מרכיבי המפתח לתכנון MLFQ הם
הם סדרי עדיפויות. במקום לתת עדיפות קבועה לכל אחד
משימה, MLFQ משנה את העדיפות שלו בהתאם להתנהגות הנצפית.
לדוגמה, אם משימה נפסקת כל הזמן במעבד בזמן ההמתנה לקלט מקלדת,
MLFQ ישמור על עדיפות התהליך גבוהה כי ככה
תהליך אינטראקטיבי אמור לעבוד. אם, להיפך, המשימה היא כל הזמן ו
מעבד אינטנסיבי לתקופה ארוכה, MLFQ ישדרג אותו לאחור
עדיפות. לפיכך, MLFQ תלמד את התנהגות התהליכים בזמן שהם פועלים.
ולהשתמש בהתנהגויות.
בואו נצייר דוגמה איך התורים עשויים להיראות בשלב מסוים
זמן ואז אתה מקבל משהו כזה:


בסכימה זו, 2 תהליכים A ו-B נמצאים בתור עם העדיפות הגבוהה ביותר. תהליך
C נמצא איפשהו באמצע, ותהליך D נמצא ממש בסוף התור. לפי האמור לעיל
תיאורים של אלגוריתם MLFQ, המתזמן יבצע רק משימות עם הגבוהים ביותר
עדיפות לפי RR, ומשימות C, D יהיו ללא עבודה.
באופן טבעי, תמונת מצב סטטית לא תיתן תמונה מלאה של אופן הפעולה של MLFQ.
חשוב להבין בדיוק איך התמונה משתנה עם הזמן.

ניסיון 1: כיצד לשנות את העדיפות

בשלב זה, עליך להחליט כיצד MLFQ ישנה את רמת העדיפות
משימה (וכך מיקום המשימה בתור) במהלך מחזור החיים שלה. ל
מתוך זה, אתה צריך לזכור את זרימת העבודה: כמות מסוימת
משימות אינטראקטיביות עם זמני ריצה קצרים (ולכן שחרור תכוף
CPU) וכמה משימות ארוכות המשתמשות במעבד כל זמן העבודה שלהן, תוך כדי
זמן התגובה למשימות כאלה אינו חשוב. וכך אתה יכול לעשות את הניסיון הראשון
ליישם את אלגוריתם MLFQ עם הכללים הבאים:

• כלל 3: כאשר משימה נכנסת למערכת, היא ממוקמת בתור עם הגבוה ביותר
• עדיפות.
• Rule4a: אם משימה משתמשת בכל חלון הזמן שלה, אז היא
• עדיפות מופחתת.
• כלל 4ב: אם משימה משחררת את ה-CPU לפני תום חלון הזמן שלה, אז היא
• נשאר עם אותה עדיפות.

דוגמה 1: משימה אחת לטווח ארוך

כפי שניתן לראות בדוגמה זו, המשימה בעת הקבלה מוגדרת עם הגבוהה ביותר
עדיפות. לאחר חלון זמן של 10 אלפיות השנייה, התהליך יורד בעדיפות.
מתזמן. לאחר חלון הזמן הבא, המשימה משודרגת לבסוף ל
העדיפות הנמוכה ביותר במערכת, שם היא נשארת.


דוגמה 2: הרים משימה קצרה

כעת נראה דוגמה כיצד MLFQ ינסה להתקרב ל-SJF. בתוך זה
לדוגמה, שתי משימות: A, שהיא משימה ארוכת טווח כל הזמן
תופסת CPU ו-B, שזו משימה אינטראקטיבית קצרה. לְהַנִיחַ
שא' כבר רצה זמן מה כשהגיעה משימה ב'.


גרף זה מציג את תוצאות התרחיש. משימה א', כמו כל משימה,
השימוש במעבד היה ממש בתחתית. משימה ב' תגיע בזמן T=100 ותגיע
ממוקמים בתור בעדיפות הגבוהה ביותר. מאחר וזמן הריצה קצר,
זה יסתיים לפני שיגיע לתור האחרון.

מהדוגמה הזו, אתה צריך להבין את המטרה העיקרית של האלגוריתם: מכיוון שהאלגוריתם לא
יודע משימה ארוכה או קצרה, אז קודם כל הוא מניח שהמשימה
קצר ונותן לו את העדיפות הגבוהה ביותר. אם זו באמת משימה קצרה, אז
זה יבוצע במהירות, אחרת אם זו משימה ארוכה היא תנוע לאט
בעדיפות למטה ובקרוב תוכיח שהיא אכן משימה ארוכה שלא
דורש תגובה.

דוגמה 3: מה לגבי I/O?

כעת נסתכל על דוגמה ל-I/O. כאמור בכלל 4ב,
אם תהליך משחרר את המעבד מבלי שניצל את זמן המעבד שלו במלואו,
אז זה נשאר באותה רמת עדיפות. הכוונה של כלל זה היא די פשוטה.
- אם העבודה האינטראקטיבית מבצעת הרבה I/O, למשל, מחכה
מהקלדות המשתמש או העכבר, משימה כזו תשחרר את המעבד
לפני החלון המוקצה. לא נרצה לוותר על משימה עדיפות כזו,
וכך הוא יישאר באותה רמה.


דוגמה זו מראה כיצד האלגוריתם יעבוד עם תהליכים כאלה - משימה אינטראקטיבית ב', אשר זקוקה למעבד רק 1ms לפני ביצוע
תהליך קלט/פלט ועבודה ארוכה A, שמשתמשת במעבד כל הזמן.
MLFQ שומר על תהליך B בעדיפות הגבוהה ביותר ככל שהוא ממשיך
לשחרר את המעבד. אם B היא משימה אינטראקטיבית, אז האלגוריתם במקרה זה הגיע
מטרתו היא להפעיל משימות אינטראקטיביות במהירות.

בעיות באלגוריתם MLFQ הנוכחי

בדוגמאות הקודמות, בנינו גרסה בסיסית של MLFQ. ונראה שהוא
עושה את עבודתו בצורה טובה והוגנת, מחלק את זמן המעבד בצורה הוגנת בין לבין
משימות ארוכות ומאפשרות משימות קצרות או משימות שהגישה אליהן כבדה
ל-I/O לעיבוד מהיר. למרבה הצער, גישה זו מכילה כמה
בעיות רציניות.
קודם כל, בעיית הרעב: אם למערכת יהיו אינטראקטיביות רבות
משימות, הם יצרכו את כל זמן ה-CPU ובכך אף לא ארוך אחד
המשימה לא תקבל הזדמנות לצאת להורג (הם גוועים ברעב).

שנית, משתמשים חכמים יכולים לכתוב את התוכניות שלהם כך
להטעות את המתזמן. ההונאה טמונה בעשיית משהו כדי לכפות
מתזמן כדי לתת לתהליך יותר זמן CPU. האלגוריתם ש
המתואר לעיל הוא די פגיע להתקפות כאלה: לפני חלון הזמן הוא כמעט
לאחר מכן, עליך לבצע פעולת קלט/פלט (לחלק, לא משנה איזה קובץ)
ובכך לשחרר את המעבד. התנהגות כזו תאפשר לך להישאר באותו אופן
התור עצמו ושוב לקבל אחוז גדול יותר מזמן המעבד. אם נעשה
זה נכון (למשל, הפעל 99% מזמן החלון לפני שחרור המעבד),
משימה כזו יכולה פשוט לעשות מונופול על המעבד.

לבסוף, תוכנית יכולה לשנות את התנהגותה לאורך זמן. המשימות האלה
שהשתמש במעבד יכול להפוך לאינטראקטיבי. בדוגמה שלנו, דומה
משימות לא יקבלו טיפול הולם מהמתזמן, כפי שאחרות יקבלו
משימות אינטראקטיביות (מקוריות).

שאלה לקהל: אילו התקפות על המתזמן אפשר לעשות בעולם המודרני?

ניסיון 2: הגדל את העדיפות

בואו ננסה לשנות את הכללים ולראות אם נוכל למנוע בעיות עם
רָעָב. מה אנחנו יכולים לעשות כדי להבטיח שזה קשור
משימות מעבד יקבלו את הזמן שלהן (גם אם לא ארוך).
כפתרון פשוט לבעיה, אתה יכול להציע מעת לעת
להגביר את העדיפות של כל המשימות הללו במערכת. יש הרבה דרכים
כדי להשיג זאת, בואו ננסה ליישם משהו פשוט כדוגמה: תרגם
כל המשימות בבת אחת בעדיפות הגבוהה ביותר, ומכאן הכלל החדש:

• Rule5: לאחר תקופה S, העבר את כל המשימות במערכת לתור הגבוה ביותר.

הכלל החדש שלנו פותר שתי בעיות בבת אחת. ראשית, התהליכים
מובטח שלא יגווע ברעב: משימות בתור הגבוה ביותר יחלקו
זמן מעבד לפי אלגוריתם RR וכך כל התהליכים יקבלו
זמן מעבד. שנית, אם תהליך כלשהו שהשתמש בו בעבר
רק המעבד הופך לאינטראקטיבי, הוא יישאר בתור עם הגבוה ביותר
עדיפות לאחר קבלת דחיפה לעדיפות הגבוהה ביותר פעם אחת.
בואו נשקול דוגמה. בתרחיש זה, שקול תהליך יחיד באמצעות


CPU ושני תהליכים אינטראקטיביים וקצרים. בצד שמאל באיור, האיור מציג את ההתנהגות ללא קידום עדיפות, וכך המשימה הארוכה מתחילה לגווע ברעב לאחר ששתי משימות אינטראקטיביות מגיעות למערכת. באיור מימין, כל 50ms מתבצעת העלאת עדיפות וכך מובטח לכל התהליכים לקבל זמן מעבד ויופעלו מעת לעת. 50ms במקרה זה נלקחים כדוגמה, במציאות המספר הזה גבוה במקצת.
ברור שהוספת זמן העלייה התקופתי S מובילה אליו
שאלה הגיונית: איזה ערך צריך להגדיר? אחד הנכבדים
מהנדסי המערכות ג'ון אוסטרהוט התייחס לכמויות דומות במערכות כ-vo-doo
קבוע, מכיוון שהם דרשו בדרך כלשהי קסם שחור בשביל הנכון
חשיפה. ולמרבה הצער, ל-S יש טעם כזה. אם תגדיר גם את הערך
גדול - משימות ארוכות יגוועו ברעב. ואם אתה מגדיר את זה נמוך מדי,
משימות אינטראקטיביות לא יקבלו זמן מעבד מתאים.

ניסיון 3: הנהלת חשבונות טובה יותר

עכשיו יש לנו עוד בעיה אחת לפתור: איך לא
לאפשר לרמות את המתזמן שלנו? האשמים לאפשרות הזו הם
כללים 4a, 4b, המאפשרים לעבודה לשמור על עדיפות, ומשחררים את המעבד
לפני תום הזמן המוקצב. איך להתמודד עם זה?
הפתרון במקרה זה יכול להיחשב כחשבון טוב יותר של זמן המעבד בכל אחד מהם
רמת MLFQ. במקום לשכוח את הזמן שבו השתמשה התוכנית
מעבד עבור המרווח המוקצב, אתה צריך לקחת בחשבון ולשמור אותו. לאחר
התהליך מיצה את הזמן המוקצב לו, יש להוריד אותו לשלב הבא
רמת עדיפות. עכשיו זה לא משנה איך התהליך ינצל את הזמן שלו - איך
מחשוב כל הזמן על המעבד או כקבוצה של שיחות. לכן,
יש לשכתב את כלל 4 באופן הבא:

• Rule4: לאחר שמשימה מיצתה את הזמן שהוקצה לה בתור הנוכחי (ללא קשר לכמה פעמים היא שחררה את ה-CPU), העדיפות של משימה כזו מצטמצמת (היא זזה למטה בתור).

בואו נסתכל על דוגמה:
»

האיור מראה מה קורה אם תנסה לרמות את המתזמן, כמו
אם זה היה עם הכללים הקודמים 4a, 4b הייתה התוצאה משמאל. עם חדש
הכלל הוא שהתוצאה נמצאת בצד ימין. לפני ההגנה, כל תהליך יכול להתקשר ל-I/O לפני השלמתו ו
ובכך לשלוט במעבד, לאחר הפעלת הגנה, ללא קשר להתנהגות
I/O, הוא עדיין יירד בתור ובכך לא יוכל בצורה לא ישרה
להשתלט על משאבי המעבד.

שיפור MLFQ ונושאים אחרים

עם השיפורים לעיל, צצות בעיות חדשות: אחת העיקריות
שאלות - איך מפרמטרים מתזמן כזה? הָהֵן. כמה צריך להיות
תורים? מה צריך להיות גודל חלון התוכנית בתוך התור? אֵיך
לעתים קרובות יש לתעדף את התוכנית כדי למנוע רעב ו
לקחת בחשבון את השינוי בהתנהגות התוכנית? לשאלות אלו, אין פשוט
תגובה ורק ניסויים עם עומסים ותצורה שלאחר מכן
מתזמן יכול להוביל לאיזון משביע רצון כלשהו.

לדוגמה, רוב יישומי MLFQ מאפשרים לך להקצות שונות
משבצות זמן לתורים שונים. תורים בעדיפות גבוהה הם בדרך כלל
מרווחים קצרים. התורים האלה מורכבים ממשימות אינטראקטיביות,
המעבר ביניהם הוא די רגיש וצריך לקחת 10 או פחות
גברת. לעומת זאת, תורים בעדיפות נמוכה מורכבים ממשימות ארוכות טווח המשתמשות
מעבד. ובמקרה זה, מרווחי זמן ארוכים מתאימים מאוד (100ms).


בדוגמה זו, ישנן 2 משימות שעבדו בתור 20 בעדיפות גבוהה
MS מחולקת לחלונות של 10ms. 40ms בתור האמצעי (חלון 20ms) ובתור בעדיפות נמוכה
חלון זמן התור הפך ל-40ms כאשר המשימות השלימו את עבודתן.

היישום של MLFQ במערכת ההפעלה Solaris הוא סוג של מתזמנים משותפים בזמן.
המתזמן יספק קבוצה של טבלאות שמגדירות בדיוק איך הוא צריך
לשנות את סדר העדיפויות של התהליך במהלך חייו, מה צריך להיות הגודל
חלון שיש להקצות ובאיזו תדירות להעלות את סדר העדיפויות של המשימות. מנהל
מערכות יכולות לקיים אינטראקציה עם טבלה זו ולגרום למתזמן להתנהג
באופן שונה. כברירת מחדל, בטבלה זו יש 60 תורים עם עלייה הדרגתית
גודל חלון מ-20 אלפיות השנייה (בעדיפות גבוהה) לכמה מאות אלפיות השנייה (בעדיפות הנמוכה ביותר), וכן
גם עם חיזוק של כל המשימות פעם בשנייה.

מתזמני MLFQ אחרים אינם משתמשים בטבלה או כל ספציפי
הכללים המתוארים בפרק זה, להיפך, הם מחשבים סדרי עדיפויות באמצעות
נוסחאות מתמטיות. לדוגמה, המתזמן ב- FreeBSD משתמש בנוסחה עבור
חישוב עדיפות המשימה הנוכחית בהתבסס על מידת התהליך
השתמש במעבד. בנוסף, השימוש במעבד נרקב עם הזמן, וכך
לפיכך, העלאת העדיפות שונה במקצת מהמתואר לעיל. זה נכון
שנקראים אלגוריתמי דעיכה. החל מגרסה 7.1, FreeBSD משתמשת במתזמן ULE.

לבסוף, למתכננים רבים יש תכונות אחרות. למשל, כמה
מתזמנים שומרים רמות גבוהות יותר לתפעול מערכת ההפעלה וכך
לפיכך, אף תהליך משתמש לא יכול לקבל את העדיפות הגבוהה ביותר
מערכת. מערכות מסוימות מאפשרות לך לתת עצות כדי לעזור
המתזמן לתעדף נכון. לדוגמה, שימוש בפקודה נחמד
אתה יכול להגדיל או להקטין את העדיפות של משימה ובכך להגדיל או להקטין
להפחית את הסיכויים של התוכנית לזמן CPU.

MLFQ: סיכום

תיארנו גישה תכנונית בשם MLFQ. השם שלו
סגור בעקרון הפעולה - יש לו מספר תורים ומשתמש במשוב
לתעדף משימה.
הצורה הסופית של הכללים תהיה כדלקמן:

• Rule1: אם עדיפות (A) > עדיפות (B), משימה A תפעל (B לא תפעל)
• Rule2: אם priority(A) = Priority(B), A&B מתחילים באמצעות RR
• Rule3: כאשר משימה נכנסת למערכת, היא ממוקמת בתור בעדיפות הגבוהה ביותר.
• Rule4: לאחר שמשימה מיצתה את הזמן שהוקצה לה בתור הנוכחי (ללא קשר לכמה פעמים היא שחררה את ה-CPU), העדיפות של משימה כזו מצטמצמת (היא זזה למטה בתור).
• Rule5: לאחר תקופה S, העבר את כל המשימות במערכת לתור הגבוה ביותר.

MLFQ מעניין מהסיבה הבאה - במקום לדרוש ידע על
אופי המשימה מראש, האלגוריתם לומד את התנהגות העבר של המשימה וקבוצות
סדרי עדיפויות בהתאם. לפיכך, הוא מנסה לשבת על שני כיסאות בבת אחת - להשיג ביצועים למשימות קטנות (SJF, STCF) ולרוץ בכנות ארוכות,
עבודות טעינת מעבד. לכן, מערכות רבות, כולל BSD ונגזרותיהן,
Solaris, Windows, Mac משתמשים בצורה כלשהי של אלגוריתם בתור מתזמן
MLFQ כבסיס.

מאפייני מידע:

1. manpages.debian.org/stretch/manpages/sched.7.en.html
2. en.wikipedia.org/wiki/Scheduling_(מחשוב)
3. pages.lip6.fr/Julia.Lawall/atc18-bouron.pdf
4. www.usenix.org/legacy/event/bsdcon03/tech/full_papers/roberson/roberson.pdf
5. chebykin.org/freebsd-process-scheduling

מקור: www.habr.com