תזמון ראונד-רובין

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

שם האלגוריתם מגיע מעקרון ראונד-רובין המוכר מתחומים אחרים, שבו כל אדם לוקח חלק שווה ממשהו בתורו.

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

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

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

לדוגמה, אם משבצת הזמן היא 100 מילישניות, ומשימה 1 אורכת זמן כולל של 250 מילישניות להשלמתה, מתזמן הראונד-רובין יעצור את המשימה לאחר 100 מילישניות ויעניק למשימות אחרות את הזמן שלהן על המעבד. לאחר שהמשימות האחרות קיבלו את חלקן השווה (100 מילישניות כל אחת), משימה 1 תקבל הקצאה נוספת של זמן מעבד והמחזור יחזור על עצמו. תהליך זה נמשך עד שהמשימה תסתיים ואינה זקוקה לזמן נוסף על המעבד.
 משימה 1 = זמן כולל להשלמה 250 אלפיות שנייה (קוונטי 100 אלפיות שנייה) .

 הקצאה ראשונה = 100 אלפיות השנייה.
 הקצאה שנייה = 100 אלפיות השנייה.
 הקצאה שלישית = 100 אלפיות השנייה אך משימה 1 מסתיימת מעצמה לאחר 50 אלפיות השנייה.
 זמן המעבד הכולל של משימה 1 = 250 מילישניות

שם התהליך זמן הגעה זמן ביצוע P0 0 250 עמוד 1 50 170 P2 130 75 P3 190 100 P4 210 130 P5 350 50
טקסט=Round Robin Scheduling|מרכז|607x607 פיקסלים|תזמון סאונד רובין
גישה נוספת היא לחלק את כל התהליכים למספר שווה של קוונטות תזמון כך שגודל הקוונטים יהיה פרופורציונלי לגודל התהליך. לפיכך, כל התהליכים מסתיימים באותו הזמן.

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

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

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

אם מוצעת איכות שירות מובטחת או מובחנת, ולא רק תקשורת לפי המאמץ הטוב ביותר, ניתן לשקול תזמון סבבי-רובין של גירעון (DRR), תזמון סבבי-רובין משוקלל (WRR), או קביעת תורים הוגנים משוקלל (WFQ).

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

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

קישורים חיצוניים

הערות שוליים

קטגוריה:דפים עם תרגומים שלא נסקרו