תרגול 5 זימון Flashcards
מהם המטריקות לזימון תהליכים
לכל התהליכים
זמן תגובה ממוצע
זמן תגובה של תהליך בודד הוא הזמן שלקח לו לרוץ
ResponseTime = end - arrival
זמן המתנה
WaitTime = start - arrival
FCFS ראשי תיבות
First come first serve
סוג קל fifo
מהו אפקט השיירה
איך נקרא באנגלית
Convey effect
בעיה שיכולה לקרות בfifo fcfs
יגיע תהליך מאוד ארוך בהתחלה ואז הוא יתקע את כל התהליכים הקצרים שמגיעים אחריו ואז זמן התגובה גדל לכולם
יכול גם לקרות בsjf אם לא כולם מגיעים באותו זמן
Sjf
ראשי תיבות ומה הוא עושה
Shotest job first
תהליך קצר ביותר הוא הבא
אם מוותרים על ההנחה שכל התהליכים רצים למשך אותו זמן מה האלגוריתם הכי טוב מבחינת זמן תגובה
Sjf
מוכח בהרצאה
Srtf
ראשי תיבות
תאר בכלליות
Shotest remaining time first
כל פעם שנכנס תהליך חדש בודק למי נשאר הכי פחות זמן ומריץ אותו
מתי srtf אופטימלי
אם לא כולם רצים אותו זמן
לא כולם מגיעים ביחד
ואפשר לעצור תהליך באמצע
ההנחה היחידה היא
זמן הריצה ידוע מראש
תהליכים משתמשים רק במעבד ולא io
עוד שם לsrtf
Stcf
Ahortest time to comletion first
אם תהליכים מבצעים גם io
איל נסתכל על התהליכים אם לדומה יש תהליך שכל 10 שניות עושה io
נסתכל על תתי המשימות שלו באורך10 כעת משימות שיש לשבץ
אם זמן הריצה ידוע מראש
למה לא כדאי למשתמש להעריך שמשימה שלו תהיה הרבה יותר מדי זמן?
מצד אחד זה יבטיח שהמשימה שלו תתבצע
מצד שני ככל שיותר נמוך הוא יקבל תעדוף בsjf and srtf
איזה הנחות מניח batch scheduling?
תהליך רץ עד סיומו
תהליכים משתמשים רק במעבד ולא io
זמן הריצה של כל התהליכים ידוע מראש
איזה שני סוגי תהליכים יש
ובאיזה מדד כל אחד מהם מעוניין
מבחינה תיאורתית
Cpu bound חישובי
אינטרקטיבי io bound
חישובי מעוניין בזמן תגובה נמוך
לסיים כמה שיותר מהר
בדרך כלל לא מוותר על המעבד
אינטרקטיבי מעוניין בזין המתנה נמוך
לדוגמה נגן סרטים שמחליף תמונה 60 פעמים בשנייה
בדרך כלל יוותר בעצמו על המעבד בעת המתנה לio
מה אפשר להגיד על sjf and srft
מול מדד זמן המתנה
לא טובים בו בכלל כי כל תהליך צריך לחכות המון זמן עד שמתחיל בכלל
RR
ראשי תיבות ובמה מצטיין
Round robin
מצטיין בזמן המתנה נמוך
מחלק את הזמן לפיסות בשם קוונטום ונותן באופן שוויוני לתהליכים קוונטום אחד כל פעם
מה האילוץ של הקוונטום מול זמן פסיקת שעון
צריך להיות כפולה שלו
למה עדיף קוונטום נמוך
או גבוה
נמוך נותן זמן המתנה נמוך יותר ויותר אינטרטיביות
גבוה מקנה פחות החלפות הקשר וביצועים טובים יותר
איך מחשבים תקורה של אלגוריתם
זמן החלפת הקשר
חלקי
אורך קוונטום
מה sjf srtf
ומה rr מנסים להשיג
האם יודעים את זמן הריצה של כל תהליך מראש?
להביא למינימום זמן תגובה
מקבלים זמן המתנה גרוע
מניחים שיודעים את זמן הריצה של כל תהליך מראש
להביא למינימום את זמן ההמתנה הממוצע
משיג זמן תגובה גרוע
לא יודע את זמן הריצה מראש
דוגמה להתהליך בלינוקס זמן אמת שרץ באמת
תהליך בשם migration
יש אחד לכל ליבה
אחראי לפיזור של תהליכים על גבי הליבות
מעביר תהליכים בין תורי הריצה
איזה שני סוגים של תהליכים יש
מבחינה הגדרתית
זמן אמת
נדרשים לעמוד באילוץ על זמן תגובה
ורגילים
יכולים לסבול דיחוי בזמן הריצה
מי יכול להגיד תהליך כזמן אמת?
ואיך
רק root
עי שינוי העדיפות שלו
כמה תורי ריצה יש בלינוקס
אחד לכל מעבד
איזה תהליכים נשמרים בתור הריצה
כל התהליכים המוכנים לריצה
במצב task running
איך עובד המספר שמייצג את עדיפות התהליך
0 הכי עדיף
99 אחרון בעדיפות
איך בנוי תור הריצה
יש 100 כניסות
הכניסה הראשונה 0 הכי עדיפה וכך הלאה
כל כניסה מצביעה לתור של תהליכים מוכנים לריצה
איזה סוגי מדניות זימון יש להתהליכי זמן אמת
הסבר על כל אחד מהם
ואיך משנים אותם
Sched_fifo
זימון לפי סדר הגעה
Sched_rr
חלוקת זמן בין כל התהליכים עם העדיפות הטובה ביותר
נקבע עי קריאת המערכת
Sched_setscheduler()
מה יכול לקרות בין תהליכי
Sched rr
ותהליך
Sched fifo
הם יכולים להתקע מאחורי תהליך fifo שלא מוותר על המעבד
אם הם כמובן באותה עדיפות
מתי
Sched fifo
מוותר על הריצה שלו
או שנגמרת לו
יוצא להמתנה
למשל io
או שיוזם החלפת הקשר
Sched_yeild
או שהגיע תהליך זמן אמת עדיף עליו
לאיפה מכנסים תהליכים חדשים ותהליכים שחזרו מהמתנה בתור הריצה
ולמה
לסוף שלו
כדי לשמור על הוגנות
וכדי למנוע הרעבה
איך עובד הtome slice בsched rr
איך מגידים אותו
לכל תהליך יש time slice
שמוגדר במספר פסיקות שעון
כל פסיקת שעון המספר יורד ב1 עד 0
מוגדר במקרו RR_Timeslice
תאר את אבולוציית זימון התהליכים בלינוקס
ב2.4
מה שנלמד בהרצאה
רץ בO n
לא סקלבילי
2.6
לא למדנו
אבל רץ בO1
בפועל מאוד איטי בגלל חישובים כבדים
2.6.23
Cfs
רץ בO logn
מהיר בפועל
מה שבתרגולים
בקצרה
מהו cfs
מה מנסה להשיג
ואיך עושה זאת
מנסה להיות הוגן מאוד ולתת לכל התהליכים זמן ריצה שווה עד כדי העדיפות שלהם
מגדיר מושג חדש בשם זמן ריצה ווירטואלי
זה באמת מה שמשומש בלינוקס
איך עובד cfs בפעל
האלגוריתם קובע זמן שהוא ינסה להריץ בו את כל תהליכים
Sched_letency = 48 ms
כל תהליך יקבל חלק שווה מהזמן הזה זה יהיה הקוונטום
כל תהליך צובר זמן ריצה וירטואלי בכל זמן שהוא במעבד
כאשר תהליך מסיים את הקוונטום שלו
הוא לוקח את התהליך הבא בעל זמן הריצה הנמוך ביותר
האם זו בעיה שcfs
יכול לקבל זמן שלא מתחלק בזמן פסיקת שעון לכל תהליך?
לא
כי זה בסוף נצבר לזמן הריצה הוירטואלי של כל תהליך
וזה נמדד ברזולוציה של ננו שניות עם השעון של המעבד לכן זה לא משנה
איך cfs מתגברת על בעיה שיכולה להוןצר עם הקוונטום השיש הרבה תהליכים?
בתיאוריה יכול להיות שזמן החלפת ההקשר יהווה חלק גדול מהקוונטום של כל תהליך
Cfs
מגדירה קוונטום מינימלי לכל תהליך כדי למנוע זו
6 ms
מה ההבדלים בין
Rr
ל
Cfs
קוונטום סטטי ברר
ואילו בcfs הוא דינאמי לפי מספר התהליכים
כשתהליך מסיים ברר מזמנים את הבא בתור במעגל
בcfs מזמנים את בעל הכי קצת זמן ריצה
באיזה מבנה נתונים משתמשים בcfs
ומי נשמר בו
עת שחור אדום
המפתח הוא זמן הריצה הוירטואלי
שומרים בו רק תהליכים מוכנים לריצה
אם תהליך עשה io יוצא ממנו לתור ריצה
מה קורה להתליך חדש שנכנס בcfs
ולמה
הןא מקבל את
זמן הריצה המקסימלי
כדי למנוע הרעבה של התהליכים האחרים
וכדי לשמור על הוגנות
איזה בעיה יכולה לצוץ בעץ של cfs
שתהליך יוצא להמתנה ארוכה
אם תהליך יוצא להמתנה ארוכה ואז חוזר יהיה לו זמן ריצה וירטואלי נמוך משמעותית משאר התהליכים מה שיגרום להרעבה של השאר
הפתרון הוא שתהליך חוזר הוא מקבל את זמן הריצה המינימלי בעץ
איזה תהליכים cfs מתעדף
אינטרקטיבים או חישוביים
אינטרקטיבים
כי זמן ההמתנה לא נחשב להם והם תמיד יהיו עם זמן ריצה וירטואלי נמוך
מהם ערכי nice האפריים
מה הדיפולט
ומה עדיף
-20
עד 19
דיפולט 0
ככל שתהליך נחמד יותר ידפק ויקבל פחות זמן ריצה ווירטואלי
קוונטום קטן יותר
איך משפיע בפועל ערך nice של תהליך
ערך nice
משנה את ההתסכלות על כמה זמן הריצה הוירטואלי השתנה
הקוונטום שכל תהליך יקבל
יהיה הקוונטופ הקבוע
כפול היחס בין המשקל של התהליך חלקי המשקל של כולם
כשהמשקל מתקבל לפי הערך נחמדות
מה זה slowdown
היחס בין
זמן ההמתנה וזמן הריצה ביחד
מול זמן הריצה
האידיאל הוא שזה יהיה 1
כלומר שזמן ההמתנה יהיה אפסי ביחס לזמן הריצה
ב
Batch scheduling
איך עובד fifo
לפי סדר ההגעה
כל פעם נחכה עד שיהיה מספיק ליבות בשביל להריץ את התהליך ונמתים ונמתין עד שיתפנה
Batch scheduling
יתרונות וחסרונות ב
Fifo
קל למימוש
פייר מאוד כי לא מכניס תהליכים קצרים וגורם להרעבה
חסרונות
מייצר פרגמנטציה כלומר ליבות לא בשימוש
משימות קצרות פשוט יחכו המון זמן עד שיכנסו
Easy
איפה ומה זה
שיפור של fifo בbatch seceduling
משתמש ברעיון שנקרא back filling
לאחר שמשבץ
רואה שיש חור
ומנסה לשבץ שם את שאר המשימות הבאות כדי למלא את החור
יתרונות וחסרונות של
Easy
יתרון
מקטין בזבוז של מעבדים
למשימות קטנות יש יותר סיכוי להיות משובצות ולא לחכות הרבה זמן
חסרונות
חייב לדעת זמני ריצה מבעוד מועד של שאר המשימןת בעתיד
מה המשתמש צריך לעשות בשביל easy
ומה משפיע על בחירתו
צריך להעריך מה אורך המשימה שהוא רוצה להריץ
אם יבחר זמן קצר יהיה יותר סיכוי שישובץ עם
back filling
אבל בסיכון שאם לא יגמר בזמן הזה המערת פשוט תהרוג אותו
אם יבחר זמן גדול מידי המערכת לא תתעדף אותו
איפה משתמשים ב
Batch scheduling
Super computers
האם
Easy
סובל מאפקט השיירה
כן אבל פחות
כי בפועל יהיו חורים קטנים שיהיה אפשר לשבץ משימות קצרות
איזה שיפורים יותר פיירים יש לeasy
Sjbf
Sj backfired first
בדיוק כמו easy בכך שמשבץ בfcfs
אבל את החורים הוא ממלא בsjf
Lxf
Largest exponential factor
Exponential = slowdown
בכל פעם שיש חור ממלא אותו לפי התהליך עם הslowdown הכי גבוה
צריך לחשב כל פעם לפני החלטה כי slowdowb השתנה
ככל מה אפשא להגיד על הזמן והעדיפות שיקבל תהליך חישובי מול אינטרקטיבי
בתיאוריה מההרצה
אינטרקטיבי יקבל פחות זמן אבל עדיפות יותר גדולה
חישובי יקבל יותר זמן אבל עדיפות יותר נמוכה
מה זה rr עם קוונטום אינסוף
Fcfs
איך נקרא rr במערכת מרובת מעבדים מקבילה
הסבר עליו
Gang scheduling
הזמן מחלק לtimeslots של דקות או שניות
לכל משימה יש slots דיפולטי שהלך אליה
(משימות שלוקחת כמה ליבות ישובצו על כל אותן ליבות)
ואז כל משימה רואה לאיפה היא יכולה לעבור
והיא עוברת אם זה יוצר רצף גדול יותר של מקום
פנוי
זה אלגוריתם חמדני
ואז כרגיל rr על הסידור
בעצם ההבדל היה השיבוץ מחדש שמייצר יותר מקום פנוי שאיתו נוכל לשבץ עוד משימות
מתי gang scheduling יכול להיות טוב לנו
ומתי פחות
כשאנחנו לא יודעים את זמן הריצה מראש זה יהיה מתאים
הבעיה היא שאם יש משימות שהרבה מידע מדופדף מהם בעת החלפת הקשר החלפת ההקשר תיקח המון זמן
הסבר על
Selfish rr
כמו פזמ
תהליכים חדשים לא מתוזמנים אלה נכנסים לרשימת המתנה
כאשר יהיו מספיק וותיקים או שכל הוותיקים יסתיימו
רק אז הם יתוזמנו
Selfish rr
עם aging מהיר הוא כמו?
ואיטי?
מהיר מאוד הוא כמו rr רגיל
איטי מאוד הוא כמו fcfs
מהו עקרון
Negative feedback
מערכת ההפעלה מתגמלת משימות ככל שהן רצות פחות זמן
כלומר עלה להן עדיפות
ודופקת משימות שרצות הרבה זמן
מורידה עדיפות
