סדרן תוכניות

במדעי המחשב, סדרן תוכניות או זַמְנָן^[1] (Scheduler) הוא כלי מרכזי במערכות התומכות בריבוי משימות ובמערכות זמן אמת. במערכות מחשב מודרניות, יש בדרך כלל יותר תהליכים שמופעלים בו זמנית מאשר מעבדים במחשב. סדרן התוכניות היא תוכנית שאחראית על חלוקת זמן המעבד בין התהליכים השונים.

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

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

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

מטרות נוספות עומדות בפני סדרן התוכניות:

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

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

ערך מורחב – אלגוריתם תזמון

קיימים אלגוריתמים שונים לתזמון הבאים להשיג מטרות שונות בהתאם לדרישות המערכת. דוגמאות לאלגוריתמי תזמון:

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

• Operating Systems: Three Easy Pieces by Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau. Arpaci-Dusseau Books, 2014. Relevant chapters: Scheduling: Introduction Multi-level Feedback Queue Proportional-share Scheduling Multiprocessor Scheduling
• Brief discussion of Job Scheduling algorithms
• Understanding the Linux Kernel: Chapter 10 Process Scheduling
• Kerneltrap: Linux kernel scheduler articles
• AIX CPU monitoring and tuning
• Josh Aas' introduction to the Linux 2.6.8.1 CPU scheduler implementation
• Peter Brucker, Sigrid Knust. Complexity results for scheduling problems
• TORSCHE Scheduling Toolbox for Matlab is a toolbox of scheduling and graph algorithms.
• A survey on cellular networks packet scheduling
• Large-scale cluster management at Google with Borg