מערכות הפעלה — מרחב למידה אישי

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

תזמון מעבד - עקרונות יסוד

מערכת הפעלה מנהלת את המעבד כיחידת משאב יקרה. כאשר מספר תהליכים מוכנים לביצוע, מתזמן המעבד (CPU Scheduler) בוחר איזה תהליך יקבל את המעבד ומתי. מטרות התזמון כוללות מקסום ניצול המעבד, מקסום תפוקה (Throughput), מזעור זמן ההמתנה (Waiting Time), מזעור זמן מחזור (Turnaround Time) ומזעור זמן תגובה (Response Time).

תזמון מקדים (Preemptive Scheduling)

בשיטה זו, תהליך יכול להיקטע באמצע ביצועו על ידי המערכת (למשל, כאשר תהליך בעל עדיפות גבוהה יותר מגיע, או כאשר חלף פרק הזמן שהוקצה לו). שיטה זו מאפשרת גמישות רבה יותר, תגובתיות טובה יותר למערכות אינטראקטיביות, ומונעת מצב של "הרעבה" (Starvation) של תהליכים בעלי עדיפות נמוכה.

תזמון לא מקדים (Non-Preemptive Scheduling)

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

אלגוריתמי תזמון נפוצים

FCFS (First-Come, First-Served): אלגוריתם תזמון לא מקדים, שבו התהליך הראשון שמגיע לתור המוכנים הוא הראשון שמקבל את המעבד.

FCFS

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

SJF (Shortest Job First): אלגוריתם תזמון המקצה את המעבד לתהליך בעל זמן הביצוע הקצר ביותר מבין התהליכים המוכנים.

SJF

עיקרון: בחירת התהליך עם זמן הביצוע הקצר ביותר. יכול להיות מקדים (נקרא אז Shortest Remaining Time First - SRTF) או לא מקדים.
יתרונות: אופטימלי מבחינת זמן ההמתנה הממוצע וזמן המחזור הממוצע.
חסרונות: קשה ליישום בפועל מכיוון שזמן הביצוע העתידי של תהליך אינו ידוע מראש. דורש הערכה או חיזוי. עלול לגרום להרעבה של תהליכים ארוכים אם תהליכים קצרים ממשיכים להגיע.

Round Robin (RR): אלגוריתם תזמון מקדים, שבו כל תהליך מקבל פרק זמן קבוע לביצוע (Quantum), ולאחר מכן הוא נקטע ומועבר לסוף תור המוכנים.

Round Robin

עיקרון: הקצאת המעבד לפרקי זמן קצרים וקבועים (Quantum) לכל תהליך בתור, בסבב.
יתרונות: הוגן, מספק זמני תגובה טובים, מתאים למערכות אינטראקטיביות ולמערכות שיתוף זמן.
חסרונות: דורש החלפות הקשר (Context Switches) רבות, מה שמוסיף תקורה. הביצועים תלויים מאוד בגודל ה-Quantum.

גודל ה-Quantum באלגוריתם Round Robin: בחירת גודל ה-Quantum היא קריטית ומשפיעה באופן מהותי על ביצועי המערכת. Quantum קטן מדי יגרום לתקורה גבוהה של החלפות הקשר (Context Switches), ויבזבז זמן מעבד יקר על פעולות ניהוליות במקום על ביצוע תהליכים. לעומת זאת, Quantum גדול מדי יגרום לאלגוריתם להתנהג בדומה ל-FCFS, ויפגע בזמני התגובה ובהגינות. המטרה היא למצוא איזון שיאפשר תגובתיות טובה עם תקורה סבירה.

תזמון מרובה תורים (Multilevel Queue Scheduling): אלגוריתם תזמון המארגן תהליכים למספר תורים נפרדים, כאשר לכל תור עשויה להיות מדיניות תזמון משלו ועדיפות שונה.

תזמון מרובה תורים

עיקרון: חלוקת התהליכים לקבוצות (תורים) על בסיס מאפיינים שונים (למשל, תהליכי מערכת, תהליכים אינטראקטיביים, תהליכי אצווה). לכל תור יכול להיות אלגוריתם תזמון משלו (לדוגמה, RR לתהליכים אינטראקטיביים ו-FCFS לתהליכי אצווה).
יתרונות: גמישות רבה, מאפשר להתאים את מדיניות התזמון לסוגים שונים של תהליכים, יכול למנוע הרעבה באמצעות מנגנוני הזדקנות (Aging) או העברת תהליכים בין תורים (Multilevel Feedback Queue).
חסרונות: מורכב יותר ליישום ולניהול. דורש הגדרת עדיפויות בין התורים ומנגנונים להעברת תהליכים.

שאלות לדיון

השווה בין אלגוריתם FCFS לאלגוריתם Round Robin בהיבטים של הגינות, זמן תגובה, ותקורה. באילו מצבים עדיף להשתמש בכל אחד מהם?
מדוע אלגוריתם SJF נחשב לאופטימלי אך קשה ליישום במערכות אמיתיות? כיצד ניתן להתמודד עם אתגר זה?
הסבר את ההשפעה של בחירת גודל ה-Quantum באלגוריתם Round Robin על ביצועי המערכת. מהם הסיכונים בבחירת Quantum קטן מדי או גדול מדי?
תאר מצב שבו תזמון לא מקדים עלול לפגוע באופן משמעותי בחווית המשתמש, והסבר כיצד תזמון מקדים פותר בעיה זו.
כיצד תזמון מרובה תורים (Multilevel Queue Scheduling) מאפשר למערכת הפעלה להתמודד עם דרישות שונות של סוגי תהליכים מגוונים? תן דוגמה.

נקודות לתשובת מודל

השוואת FCFS ו-RR: FCFS פשוט אך לא הוגן ועם זמני תגובה ארוכים (אפקט השיירה), מתאים למערכות אצווה. RR הוגן, זמני תגובה טובים, מתאים למערכות אינטראקטיביות, אך עם תקורה של החלפות הקשר.
אתגרי SJF: אופטימלי תיאורטית (מזעור זמן המתנה/מחזור ממוצע) אך דורש ידע מוקדם על זמן הריצה של תהליכים. פתרונות כוללים חיזוי (למשל, ממוצע אקספוננציאלי) או שימוש בגרסה המקדימה (SRTF).
השפעת Quantum ב-RR: Quantum קטן מדי = תקורה גבוהה של החלפות הקשר, בזבוז משאבים. Quantum גדול מדי = התנהגות דמוית FCFS, פגיעה בזמני תגובה. יש למצוא איזון.
תזמון מקדים מול לא מקדים: תזמון לא מקדים עלול לגרום לתהליך ארוך "לתקוע" את המעבד ולפגוע בתגובתיות (למשל, תהליך חישוב ארוך מונע מתהליך ממשק משתמש להגיב). תזמון מקדים מאפשר למערכת להחליף תהליכים ולשמור על תגובתיות.
גמישות תזמון מרובה תורים: מאפשר למערכת להגדיר מדיניות תזמון שונה לתהליכים שונים (לדוגמה, תור עדיפות גבוהה לתהליכי מערכת עם RR, תור עדיפות בינונית לתהליכים אינטראקטיביים עם RR, ותור עדיפות נמוכה לתהליכי אצווה עם FCFS). זה מספק מענה מותאם לצרכים מגוונים ומגביר את יעילות המערכת.

מצאתם טעות או שחסר משהו?