אלגוריתם תזמון
במדעי המחשב, אלגוריתם תזמון (באנגלית: "Scheduling discipline") הוא אלגוריתם המממש מדיניות תזמון מסוימת עבור סדרן התוכניות. מדיניות זו קובעת את דרך חלוקת המשאבים, למשל המעבד, בין תהליכים ותהליכונים. הצורך באלגוריתם תזמון נובע מהדרישה לריבוי משימות שקיימת ברוב המערכות המודרניות.
מטרותיו העיקריות של אלגוריתם תזמון הן ניצול מקסימלי של המעבדים ושמירה על זמן תגובה נמוך של המערכת לאירועים שונים. דרישות נוספות מהאלגוריתם יכולות להתבסס על אופי המערכת בה הוא מתקיים. לדוגמה:
- במערכות זמן אמת, הדרישה לזמן תגובה נמוך הוא הכרחי ביותר עבור חלק מהתהליכים. כך למשל, במערכת הטייס האוטומטי, במידה והמערכת מגלה ירידה במהירות הטיסה, נרצה שהמערכת תגביר מהירות באופן מיידי.
- במערכות שנמצאות במחשב רשת מרכזי, בו התהליכים יכולים להיות משתמשי קצה שונים, ההוגנות (חלוקת זמן שווה וזמן המתנה שווה בין התהליכים) תהיה דרישה משמעותית.
כמו כן, ניתן לבצע אופטימיזציות ספציפיות לחומרה ובכך לשפר את ניצול המעבדים. אלגוריתמי תזמון שמקיימים אופטימיזציות שכאלה הן למשל:
- תזמון כנופיות (Gang Scheduling) - במחשבים מרובי מעבדים, עבור תהליכים מרובי תהליכונים - נרצה להפעיל במקביל על מספר מעבדים את כל התהליכונים (או כמה שניתן). הסיבה נעוצה בעובדה שעל פי רוב, בין התהליכונים השונים יש סנכרון כלשהו שימנע מתהליכון אחד להמשיך לרוץ עד שאחר לא ימשיך. לכן כדי למנוע ריבוי החלפות הקשר, נפעיל את התהליכונים במקביל.
- תזמון דביק (Sticky Scheduling) - במחשבים מרובי מעבדים, נרצה בכל פעם להריץ תהליך על אותו המעבד עליו רץ בפעם האחרונה, כדי לחסוך חריגי מטמון.
על אלגוריתם תזמון להימנע ממצב בו עלולה להתקיים הרעבה של תהליכים/תהליכונים.