אלגוריתם תזמון
קפיצה לניווט
קפיצה לחיפוש
במדעי המחשב, אלגוריתם תזמון (באנגלית: "Scheduling discipline") הוא אלגוריתם המממש מדיניות תזמון מסוימת עבור סדרן התוכניות. מדיניות זו קובעת את דרך חלוקת המשאבים, למשל המעבד, בין תהליכים ותהליכונים. הצורך באלגוריתם תזמון נובע מהדרישה לריבוי משימות שקיימת ברוב המערכות המודרניות.
מטרותיו העיקריות של אלגוריתם תזמון הן ניצול מקסימלי של המעבדים ושמירה על זמן תגובה נמוך של המערכת לאירועים שונים. דרישות נוספות מהאלגוריתם יכולות להתבסס על אופי המערכת בה הוא מתקיים. לדוגמה:
- במערכות זמן אמת, הדרישה לזמן תגובה נמוך הוא הכרחי ביותר עבור חלק מהתהליכים. כך למשל, במערכת הטייס האוטומטי, במידה והמערכת מגלה ירידה במהירות הטיסה, נרצה שהמערכת תגביר מהירות באופן מיידי.
- במערכות שנמצאות במחשב רשת מרכזי, בו התהליכים יכולים להיות משתמשי קצה שונים, ההוגנות (חלוקת זמן שווה וזמן המתנה שווה בין התהליכים) תהיה דרישה משמעותית.
כמו כן, ניתן לבצע אופטימיזיות ספציפיות לחומרה ובכך לשפר את ניצול המעבדים. אלגוריתמי תזמון שמקיימים אופטימיזציות שכאלה הן למשל:
- תזמון כנופיות (Gang Scheduling) - במחשבים מרובי מעבדים, עבור תהליכים מרובי תהליכונים - נרצה להפעיל במקביל על מספר מעבדים את כל התהליכונים (או כמה שניתן). הסיבה נעוצה בעובדה שעל פי רוב, בין התהליכונים השונים יש סנכרון כלשהו שימנע מתהליכון אחד להמשיך לרוץ עד שאחר לא ימשיך. לכן כדי למנוע ריבוי החלפות הקשר, נפעיל את התהליכונים במקביל.
- תזמון דביק (Sticky Scheduling) - במחשבים מרובי מעבדים, נרצה בכל פעם להריץ תהליך על אותו המעבד עליו רץ בפעם האחרונה, כדי לחסוך חריגי מטמון.
על אלגוריתם תזמון להימנע ממצב בו עלולה להתקיים הרעבה של תהליכים/תהליכונים.
אלגוריתמים שונים
ישנם מספר אלגוריתמים שונים בניסיון למקסם את יעילות התזמון של התהליכים.
- FCFS - First Come First Served - תזמון התהליכים למעבד מתבצע לפי סדר הגעתם לתור המוכנים.
חסרונות עיקריים: Convoy effect - אפקט השיירה - תהליך ארוך מעכב תהליכים קצרים וגורם להמתנה ארוכה יותר. - SJF - Shortest Job First - תזמון לפי אורך הCPU הקצר ביותר, חישוב האורך הCPU הוא לפי ממוצע כללי של פרצי ה CPU שהיו לתהליך זה עד עתה.
חסרונות עיקריים: Starvation - הרעבה, תהליכים בעלי צריכה עיבוד גבוהה נדחים לסוף התור, ויתכן אפילו מצב בו תהליך בעל צריכת פרץ עיבוד גדול משמעותי ידחה שוב ושוב על ידי תהליכים אחרים. כמו כן ישנו יש קושי לחשב את משך הזמן של פרץ העיבוד הדרוש להמשך ההרצה הבאה, (החישוב עצמו הוא ממוצע של פרצי זמן מעבד שהיו לתכנית זו עד להרצה הנוכחית). - SRTF - Shortest Remaining Time First - אותה השיטה כמו SJF אולם היא מוציאה בכוח (Preemptive) תהליך באמצע ריצה במקרה שנכנס לתור המוכנים תהליך שהCPU שלה קצר יותר.
חסרונות עיקריים: Starvation, זמן נוסף שיוצר ה Context switching - Priority - שיטה שבה משייכים לכל תהליך מספר שלם המסמן את העדיפות שלו (ככל שהמספר קטן יותר העדיפות גבוה יותר). כמובן ששיטה זאת שייכת בשתי האפשרויות preemptive ו Nonpreemptive.
- SJF הוא דוגמא לשימוש בעדיפות שקרטריון העדיפות שלו הוא משך פרץ זמן העיבוד הבא של התהליך.
- החסרון בשיטה זו הוא הרעבה.
- פתרון החסרון: הוא ע"י הוספת פתרון - aging(הזדקנות) כלומר להגדיר שעם הזמן שעובר להעלות את רמת העדיפות של התהליך (ללא קשר לזמן העיבוד שלו), כך שגם אם ישנו תהליך שמן העיבוד שלו גדול באופן משמעותי מכל פרצי העיבוד של תהליכים אחרים ההמתנה בתור תעלה את עדיפותו על תהליכים אחרים כך שבאיזשהו שלב הוא בהכרח יצא להרצה.
- RR - Round Robin - לכל תהליך ניתן יחידת זמן מוקצבת מראש (quantum). במידה והתהליך הגיע לתקרת הזמן שלו אזי הוא מוצא בכוח מה CPU (מנגנון preemptive)ועובר ונכנס לסוף התור של התהליכים המוכנים להרצה.
- במידה והתהליך סיים לפני הזמן שהוקצב לו (מחכה לקלט/פלט או שסיים את הריצה) אזי הוא מועבר לתור שלו (waiting או terminated) ולא מחכה עד סוף הזמן המוקצב לו.
- זמן ההמתנה המקסימאלי של תהליך בתור המוכנים (ready queue) הוא n-1)q) כאשר n הוא מספר התהליכים שבהרצה.
- יעילות האלגוריתם תלויה בבחירה נכונה של יחידת הזמן (q), כך אם נגדיר זמן (q) ארוך זה יהיה ממש כמו FIFO, לעומת זאת אם נגדיר (q) קצר מידי נקבל הרבה מידי context switch מיותרים דבר שיגרום לתקורה גבוה. לכן השאיפה היא לקחת זמן שמפיק את את המיטב מהתהליכים כך שרוב התהליכים יסיימו את פרץ זמן העיבוד בקלט/פלט ואילו תהליכים שדורשים פרץ זמן עיבוד חריג וארוך יצאו בסוף יחידת הזמן.
- Multilevel Queue - בשיטה זו תור המוכנים לרוץ מחולק לכמה תורים נפרדים בעלי עדיפויות שונות, לדוגמה בחלוקה לשני תורים תור אחד foreground והשני background. כל תור ינוהל בעזרת שיטה שונה למשל התור הראשון (החזיתי) בשיטת RR והשני (האחורי) בשיטת FCFS.
- יש להבחין כי שיטה זו עלולה לגרום לבעיות שונות שצריך לתקן כך לדוגמה אם נקבע עדיפות לתור הראשון בעזרת priority כלומר שנשרת קודם כל את התור החזיתי כל עוד יש בתוכו תהליכים עלול הדבר לגרום ל"הרעבה".
- ניתן גם לחלק את זמן העיבוד בעזרת Time slice כלומר שכל תור מקבל חתיכה מסוימת מה cpu למשל 80% לתור החזיתי ו 20% לאחורי.
ראו גם
20210597אלגוריתם תזמון