תרגול 5 זימון Flashcards

1
Q

מהם המטריקות לזימון תהליכים

A

לכל התהליכים
זמן תגובה ממוצע

זמן תגובה של תהליך בודד הוא הזמן שלקח לו לרוץ
ResponseTime = end - arrival

זמן המתנה
WaitTime = start - arrival

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

FCFS ראשי תיבות

A

First come first serve
סוג קל fifo

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

מהו אפקט השיירה
איך נקרא באנגלית

A

Convey effect

בעיה שיכולה לקרות בfifo fcfs
יגיע תהליך מאוד ארוך בהתחלה ואז הוא יתקע את כל התהליכים הקצרים שמגיעים אחריו ואז זמן התגובה גדל לכולם

יכול גם לקרות בsjf אם לא כולם מגיעים באותו זמן

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Sjf
ראשי תיבות ומה הוא עושה

A

Shotest job first
תהליך קצר ביותר הוא הבא

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

אם מוותרים על ההנחה שכל התהליכים רצים למשך אותו זמן מה האלגוריתם הכי טוב מבחינת זמן תגובה

A

Sjf
מוכח בהרצאה

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Srtf
ראשי תיבות
תאר בכלליות

A

Shotest remaining time first
כל פעם שנכנס תהליך חדש בודק למי נשאר הכי פחות זמן ומריץ אותו

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

מתי srtf אופטימלי

A

אם לא כולם רצים אותו זמן
לא כולם מגיעים ביחד
ואפשר לעצור תהליך באמצע

ההנחה היחידה היא
זמן הריצה ידוע מראש
תהליכים משתמשים רק במעבד ולא io

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

עוד שם לsrtf

A

Stcf
Ahortest time to comletion first

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

אם תהליכים מבצעים גם io
איל נסתכל על התהליכים אם לדומה יש תהליך שכל 10 שניות עושה io

A

נסתכל על תתי המשימות שלו באורך10 כעת משימות שיש לשבץ

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

אם זמן הריצה ידוע מראש
למה לא כדאי למשתמש להעריך שמשימה שלו תהיה הרבה יותר מדי זמן?

A

מצד אחד זה יבטיח שהמשימה שלו תתבצע
מצד שני ככל שיותר נמוך הוא יקבל תעדוף בsjf and srtf

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

איזה הנחות מניח batch scheduling?

A

תהליך רץ עד סיומו
תהליכים משתמשים רק במעבד ולא io
זמן הריצה של כל התהליכים ידוע מראש

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

איזה שני סוגי תהליכים יש
ובאיזה מדד כל אחד מהם מעוניין
מבחינה תיאורתית

A

Cpu bound חישובי
אינטרקטיבי io bound

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

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

מה אפשר להגיד על sjf and srft
מול מדד זמן המתנה

A

לא טובים בו בכלל כי כל תהליך צריך לחכות המון זמן עד שמתחיל בכלל

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

RR
ראשי תיבות ובמה מצטיין

A

Round robin
מצטיין בזמן המתנה נמוך
מחלק את הזמן לפיסות בשם קוונטום ונותן באופן שוויוני לתהליכים קוונטום אחד כל פעם

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

מה האילוץ של הקוונטום מול זמן פסיקת שעון

A

צריך להיות כפולה שלו

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

למה עדיף קוונטום נמוך
או גבוה

A

נמוך נותן זמן המתנה נמוך יותר ויותר אינטרטיביות

גבוה מקנה פחות החלפות הקשר וביצועים טובים יותר

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

איך מחשבים תקורה של אלגוריתם

A

זמן החלפת הקשר
חלקי
אורך קוונטום

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

מה sjf srtf
ומה rr מנסים להשיג
האם יודעים את זמן הריצה של כל תהליך מראש?

A

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

להביא למינימום את זמן ההמתנה הממוצע
משיג זמן תגובה גרוע
לא יודע את זמן הריצה מראש

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

דוגמה להתהליך בלינוקס זמן אמת שרץ באמת

A

תהליך בשם migration
יש אחד לכל ליבה
אחראי לפיזור של תהליכים על גבי הליבות
מעביר תהליכים בין תורי הריצה

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

איזה שני סוגים של תהליכים יש
מבחינה הגדרתית

A

זמן אמת
נדרשים לעמוד באילוץ על זמן תגובה

ורגילים
יכולים לסבול דיחוי בזמן הריצה

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

מי יכול להגיד תהליך כזמן אמת?
ואיך

A

רק root
עי שינוי העדיפות שלו

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

כמה תורי ריצה יש בלינוקס

A

אחד לכל מעבד

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

איזה תהליכים נשמרים בתור הריצה

A

כל התהליכים המוכנים לריצה
במצב task running

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

איך עובד המספר שמייצג את עדיפות התהליך

A

0 הכי עדיף
99 אחרון בעדיפות

25
Q

איך בנוי תור הריצה

A

יש 100 כניסות
הכניסה הראשונה 0 הכי עדיפה וכך הלאה
כל כניסה מצביעה לתור של תהליכים מוכנים לריצה

26
Q

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

A

Sched_fifo
זימון לפי סדר הגעה

Sched_rr
חלוקת זמן בין כל התהליכים עם העדיפות הטובה ביותר

נקבע עי קריאת המערכת
Sched_setscheduler()

27
Q

מה יכול לקרות בין תהליכי
Sched rr
ותהליך
Sched fifo

A

הם יכולים להתקע מאחורי תהליך fifo שלא מוותר על המעבד
אם הם כמובן באותה עדיפות

28
Q

מתי
Sched fifo
מוותר על הריצה שלו
או שנגמרת לו

A

יוצא להמתנה
למשל io

או שיוזם החלפת הקשר
Sched_yeild

או שהגיע תהליך זמן אמת עדיף עליו

29
Q

לאיפה מכנסים תהליכים חדשים ותהליכים שחזרו מהמתנה בתור הריצה
ולמה

A

לסוף שלו
כדי לשמור על הוגנות
וכדי למנוע הרעבה

30
Q

איך עובד הtome slice בsched rr
איך מגידים אותו

A

לכל תהליך יש time slice
שמוגדר במספר פסיקות שעון
כל פסיקת שעון המספר יורד ב1 עד 0
מוגדר במקרו RR_Timeslice

31
Q

תאר את אבולוציית זימון התהליכים בלינוקס

A

ב2.4
מה שנלמד בהרצאה
רץ בO n
לא סקלבילי

2.6
לא למדנו
אבל רץ בO1
בפועל מאוד איטי בגלל חישובים כבדים

2.6.23
Cfs
רץ בO logn
מהיר בפועל
מה שבתרגולים

32
Q

בקצרה
מהו cfs
מה מנסה להשיג
ואיך עושה זאת

A

מנסה להיות הוגן מאוד ולתת לכל התהליכים זמן ריצה שווה עד כדי העדיפות שלהם

מגדיר מושג חדש בשם זמן ריצה ווירטואלי

זה באמת מה שמשומש בלינוקס

33
Q

איך עובד cfs בפעל

A

האלגוריתם קובע זמן שהוא ינסה להריץ בו את כל תהליכים

Sched_letency = 48 ms

כל תהליך יקבל חלק שווה מהזמן הזה זה יהיה הקוונטום

כל תהליך צובר זמן ריצה וירטואלי בכל זמן שהוא במעבד

כאשר תהליך מסיים את הקוונטום שלו
הוא לוקח את התהליך הבא בעל זמן הריצה הנמוך ביותר

34
Q

האם זו בעיה שcfs
יכול לקבל זמן שלא מתחלק בזמן פסיקת שעון לכל תהליך?

A

לא
כי זה בסוף נצבר לזמן הריצה הוירטואלי של כל תהליך
וזה נמדד ברזולוציה של ננו שניות עם השעון של המעבד לכן זה לא משנה

35
Q

איך cfs מתגברת על בעיה שיכולה להוןצר עם הקוונטום השיש הרבה תהליכים?

A

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

Cfs
מגדירה קוונטום מינימלי לכל תהליך כדי למנוע זו
6 ms

36
Q

מה ההבדלים בין
Rr
ל
Cfs

A

קוונטום סטטי ברר
ואילו בcfs הוא דינאמי לפי מספר התהליכים

כשתהליך מסיים ברר מזמנים את הבא בתור במעגל
בcfs מזמנים את בעל הכי קצת זמן ריצה

37
Q

באיזה מבנה נתונים משתמשים בcfs
ומי נשמר בו

A

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

38
Q

מה קורה להתליך חדש שנכנס בcfs
ולמה

A

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

39
Q

איזה בעיה יכולה לצוץ בעץ של cfs
שתהליך יוצא להמתנה ארוכה

A

אם תהליך יוצא להמתנה ארוכה ואז חוזר יהיה לו זמן ריצה וירטואלי נמוך משמעותית משאר התהליכים מה שיגרום להרעבה של השאר

הפתרון הוא שתהליך חוזר הוא מקבל את זמן הריצה המינימלי בעץ

40
Q

איזה תהליכים cfs מתעדף
אינטרקטיבים או חישוביים

A

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

41
Q

מהם ערכי nice האפריים
מה הדיפולט
ומה עדיף

A

-20
עד 19
דיפולט 0

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

42
Q

איך משפיע בפועל ערך nice של תהליך

A

ערך nice
משנה את ההתסכלות על כמה זמן הריצה הוירטואלי השתנה

הקוונטום שכל תהליך יקבל
יהיה הקוונטופ הקבוע
כפול היחס בין המשקל של התהליך חלקי המשקל של כולם

כשהמשקל מתקבל לפי הערך נחמדות

43
Q

מה זה slowdown

A

היחס בין
זמן ההמתנה וזמן הריצה ביחד
מול זמן הריצה

האידיאל הוא שזה יהיה 1
כלומר שזמן ההמתנה יהיה אפסי ביחס לזמן הריצה

44
Q

ב
Batch scheduling

איך עובד fifo

A

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

45
Q

Batch scheduling

יתרונות וחסרונות ב
Fifo

A

קל למימוש
פייר מאוד כי לא מכניס תהליכים קצרים וגורם להרעבה

חסרונות
מייצר פרגמנטציה כלומר ליבות לא בשימוש

משימות קצרות פשוט יחכו המון זמן עד שיכנסו

46
Q

Easy
איפה ומה זה

A

שיפור של fifo בbatch seceduling

משתמש ברעיון שנקרא back filling
לאחר שמשבץ
רואה שיש חור
ומנסה לשבץ שם את שאר המשימות הבאות כדי למלא את החור

47
Q

יתרונות וחסרונות של
Easy

A

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

חסרונות
חייב לדעת זמני ריצה מבעוד מועד של שאר המשימןת בעתיד

48
Q

מה המשתמש צריך לעשות בשביל easy
ומה משפיע על בחירתו

A

צריך להעריך מה אורך המשימה שהוא רוצה להריץ
אם יבחר זמן קצר יהיה יותר סיכוי שישובץ עם
back filling
אבל בסיכון שאם לא יגמר בזמן הזה המערת פשוט תהרוג אותו

אם יבחר זמן גדול מידי המערכת לא תתעדף אותו

49
Q

איפה משתמשים ב
Batch scheduling

A

Super computers

50
Q

האם
Easy
סובל מאפקט השיירה

A

כן אבל פחות
כי בפועל יהיו חורים קטנים שיהיה אפשר לשבץ משימות קצרות

51
Q

איזה שיפורים יותר פיירים יש לeasy

A

Sjbf
Sj backfired first
בדיוק כמו easy בכך שמשבץ בfcfs
אבל את החורים הוא ממלא בsjf

Lxf
Largest exponential factor
Exponential = slowdown
בכל פעם שיש חור ממלא אותו לפי התהליך עם הslowdown הכי גבוה
צריך לחשב כל פעם לפני החלטה כי slowdowb השתנה

52
Q

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

בתיאוריה מההרצה

A

אינטרקטיבי יקבל פחות זמן אבל עדיפות יותר גדולה

חישובי יקבל יותר זמן אבל עדיפות יותר נמוכה

53
Q

מה זה rr עם קוונטום אינסוף

A

Fcfs

54
Q

איך נקרא rr במערכת מרובת מעבדים מקבילה
הסבר עליו

A

Gang scheduling

הזמן מחלק לtimeslots של דקות או שניות
לכל משימה יש slots דיפולטי שהלך אליה
(משימות שלוקחת כמה ליבות ישובצו על כל אותן ליבות)

ואז כל משימה רואה לאיפה היא יכולה לעבור
והיא עוברת אם זה יוצר רצף גדול יותר של מקום
פנוי
זה אלגוריתם חמדני

ואז כרגיל rr על הסידור
בעצם ההבדל היה השיבוץ מחדש שמייצר יותר מקום פנוי שאיתו נוכל לשבץ עוד משימות

55
Q

מתי gang scheduling יכול להיות טוב לנו
ומתי פחות

A

כשאנחנו לא יודעים את זמן הריצה מראש זה יהיה מתאים

הבעיה היא שאם יש משימות שהרבה מידע מדופדף מהם בעת החלפת הקשר החלפת ההקשר תיקח המון זמן

56
Q

הסבר על
Selfish rr

A

כמו פזמ
תהליכים חדשים לא מתוזמנים אלה נכנסים לרשימת המתנה

כאשר יהיו מספיק וותיקים או שכל הוותיקים יסתיימו
רק אז הם יתוזמנו

57
Q

Selfish rr
עם aging מהיר הוא כמו?
ואיטי?

A

מהיר מאוד הוא כמו rr רגיל
איטי מאוד הוא כמו fcfs

58
Q

מהו עקרון
Negative feedback

A

מערכת ההפעלה מתגמלת משימות ככל שהן רצות פחות זמן
כלומר עלה להן עדיפות

ודופקת משימות שרצות הרבה זמן
מורידה עדיפות