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

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

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

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

חלקים אחרים:

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

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

מבוא למתזמן

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

הנחות עומס עבודה

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

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

1. כל משימה פועלת במשך אותו פרק זמן,
2. כל המשימות נקבעות בו זמנית,
3. המשימה שהוקצתה פועלת עד להשלמתה,
4. כל המשימות משתמשות במעבד בלבד,
5. זמן הריצה של כל משימה ידוע.

מדדי מתזמן

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

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

Tturnaround=השלמה-הגעה

מכיוון שהנחנו שכל המשימות הגיעו באותו זמן, אז Ta=0 וכך Tt=Tc. ערך זה ישתנה באופן טבעי כאשר נשנה את ההנחות לעיל.

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

ראשון נכנס ראשון יוצא (FIFO)

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

בואו נסתכל על דוגמה פשוטה. נניח שנקבעו 3 משימות בו זמנית. אבל נניח שמשימה א' הגיעה קצת יותר מוקדם מכל האחרות, אז היא תופיע ברשימת הביצוע מוקדם יותר מהאחרות, בדיוק כמו B ביחס ל-C. נניח שכל אחת מהן תתבצע למשך 10 שניות. מה יהיה הזמן הממוצע להשלמת משימות אלו במקרה זה?

על ידי ספירת הערכים - 10+20+30 וחלוקה ב-3, נקבל את זמן ביצוע התוכנית הממוצע השווה ל-20 שניות.
עכשיו בואו ננסה לשנות את ההנחות שלנו. בפרט, הנחה 1 ולכן לא נניח עוד שלוקח לכל משימה את אותו פרק זמן לביצוע. איך יפעל FIFO הפעם?

כפי שמתברר, לזמני ביצוע שונים של משימות יש השפעה שלילית ביותר על הפרודוקטיביות של אלגוריתם FIFO. נניח שמשימה A ייקח 100 שניות להשלמת, בעוד B ו-C ימשיכו 10 שניות כל אחת.

כפי שניתן לראות מהאיור, הזמן הממוצע למערכת יהיה (100+110+120)/3=110. אפקט זה נקרא אפקט השיירה, כאשר חלק מהצרכנים לטווח קצר של משאב יעמדו בתור אחרי צרכן כבד. זה כמו בתור במכולת כשיש מולך לקוח עם עגלה מלאה. הפתרון הטוב ביותר לבעיה הוא לנסות להחליף קופה או להירגע ולנשום עמוק.

העבודה הקצרה ביותר תחילה

האם אפשר איכשהו לפתור מצב דומה עם תהליכים כבדי משקל? בְּהֶחלֵט. סוג אחר של תכנון נקראהעבודה הקצרה ביותר תחילה (SJF). גם האלגוריתם שלו די פרימיטיבי - כפי שהשם מרמז, המשימות הקצרות ביותר יושקו תחילה, בזו אחר זו.

בדוגמה זו, התוצאה של הפעלת אותם תהליכים תהיה שיפור בזמן אספקת התוכנית הממוצע והוא יהיה שווה ל- 50 במקום 110, שהוא כמעט פי 2 טוב יותר.

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

בואו נדמיין שמשימה A (100c) מגיעה ראשונה ומתחילה להתבצע. ב-t=10 מגיעות משימות B ו-C, שכל אחת מהן תארך 10 שניות. אז זמן הביצוע הממוצע הוא (100+(110-10)+(120-10))3 = 103. מה המתזמן יכול לעשות כדי לשפר זאת?

הזמן הקצר ביותר עד להשלמת תחילה (STCF)

על מנת לשפר את המצב, אנו משמיטים הנחה 3 שהתוכנית מופעלת ופועלת עד לסיום. בנוסף, נזדקק לתמיכת חומרה, וכפי שאתה יכול לנחש, נשתמש таймер כדי להפריע למשימה רצה ו החלפת הקשר. לפיכך, המתזמן יכול לעשות משהו ברגע שהמשימות ב', ג' מגיעות - להפסיק את ביצוע משימה א' ולהכניס את המשימות ב' ו-ג' לעיבוד ולאחר השלמתן להמשיך בביצוע תהליך א'. מתזמן כזה נקרא STCFאו עבודה מונעת תחילה.

התוצאה של מתכנן זה תהיה התוצאה הבאה: ((120-0)+(20-10)+(30-10))/3=50. לפיכך, מתזמן כזה הופך לאופטימלי עוד יותר עבור המשימות שלנו.

זמן תגובה מטרי

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

זמן התגובה מחושב באופן הבא:

Tresponse=Tfirstrun−Tarrival

לפיכך, עבור הדוגמה הקודמת, זמן התגובה יהיה: A=0, B=0, C=10 (abg=3,33).

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

אז אנחנו עומדים בפני בעיה נוספת – איך אפשר לבנות מתזמן רגיש לזמן תגובה?

רובין עגול

פותח אלגוריתם כדי לפתור בעיה זו רובין עגול (RR). הרעיון הבסיסי הוא די פשוט: במקום להריץ משימות עד להשלמתן, נריץ את המשימה לפרק זמן מסוים (נקרא פרוסת זמן) ואז נעבור למשימה אחרת מהתור. האלגוריתם חוזר על עבודתו עד להשלמת כל המשימות. במקרה זה, זמן הריצה של התוכנית חייב להיות כפול של הזמן שאחריו הטיימר יפריע לתהליך. לדוגמה, אם טיימר מפריע לתהליך כל x=10ms, אז גודל חלון ביצוע התהליך צריך להיות כפולה של 10 ולהיות 10,20 או x*10.

בואו נסתכל על דוגמה: משימות ABC מגיעות בו זמנית למערכת וכל אחת מהן רוצה לרוץ במשך 5 שניות. אלגוריתם SJF ישלים כל משימה לפני שתתחיל אחרת. לעומת זאת, אלגוריתם RR עם חלון השקה = 1s יעבור את המשימות באופן הבא (איור 4.3):

(SJF שוב (רע לזמן תגובה)

(Round Robin (טוב לזמן תגובה)

זמן התגובה הממוצע עבור אלגוריתם RR הוא (0+1+2)/3=1, ואילו עבור SJF (0+5+10)/3=5.

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

RR הוא מתזמן מצוין אם היינו מדברים רק על מדד זמן התגובה. אבל איך יתנהג מדד זמן אספקת המשימות עם האלגוריתם הזה? שקול את הדוגמה למעלה, כאשר זמן הפעולה של A, B, C = 5s ומגיעים באותו זמן. משימה א' תסתיים ב-13, ב' ב-14, ג' ב-15 שניות וזמן ההתמודדות הממוצע יהיה 14 שניות. לפיכך, RR הוא האלגוריתם הגרוע ביותר עבור מדד המחזור.

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

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

ערבוב עם I/O

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

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

בואו נסתכל על דוגמה למספר בעיות. כל אחד מהם דורש 50ms של זמן מעבד. עם זאת, הראשון ייגש ל-I/O כל 10ms (שגם יבוצע כל 10ms). ותהליך B פשוט משתמש במעבד של 50ms ללא I/O.

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

הגישה המסורתית לפתרון בעיה זו היא להתייחס לכל תת-משימה של 10 אלפיות השנייה של תהליך A כמשימה נפרדת. לפיכך, כאשר מתחילים עם אלגוריתם STJF, הבחירה בין משימה של 50 אלפיות השנייה למשימה של 10 אלפיות השנייה ברורה. לאחר מכן, כאשר תת-משימה א' תושלם, תהליך B ו-I/O יופעלו. לאחר סיום ה-I/O, יהיה נהוג להתחיל שוב את תהליך A של 10ms במקום תהליך B. כך ניתן ליישם חפיפה, כאשר ה-CPU משמש תהליך אחר בזמן שהראשון ממתין ל- I/O. וכתוצאה מכך, המערכת מנוצלת טוב יותר - ברגע שבו תהליכים אינטראקטיביים ממתינים ל-I/O, ניתן לבצע תהליכים אחרים על המעבד.

האורקל כבר לא

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

סך הכל

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

מקור: www.habr.com