אלגוריתם המעלית (Elevator algorithm)

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


11 תגובות:

תמר שביט אמר/ה...

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

lior אמר/ה...

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

אוהד ברזילי אמר/ה...

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

אני אקדיש את אחד הסרטונים הבאים לבעיה זו ולפתרונה (יותר נכון - לאי פתרונה). אם אין לך סבלנות תוכלי בינתיים לקרוא עוד ב- http://en.wikipedia.org/wiki/Packing_problem (לצערי ערך זה עוד לא תורגם לעברית). וגם תוכלי להתנחם בנקודה.

אוהד ברזילי אמר/ה...

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

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

בדיסקים זמן הטיפול בבקשה, כלומר הגעה לסקטור הנכון, הוא של כ-2 מילישניות (בהשוואה לכ-4 מילישניות שלוקח לזרוע להגיע לטרק המבוקש). הדבר אנלוגי לנוסע אשר לוקח לו להיכנס או לצאת ממעלית כ-20 שניות, כאשר התנועה שלה בין הקומות ארכה כ-40 שניות.

גם אתה זוכה בנקודה!

אנונימי אמר/ה...

חביב ומעניין, האם אפשר לתמצת וקצר? חלק מהסברים ארוך מדי.

Assaf Zaritsky אמר/ה...

אתה משתפר מפוסט לפוסט.

ההוספה של תמונות \ סרטונים במהלך הפוסט מאוד מוסיף (בכל זאת לא פשוט להסתכל עליך 7 דקות)

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

אוהד ברזילי אמר/ה...

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

אוהד ברזילי אמר/ה...

אסף, תודה!

איליה אמר/ה...

אהבתי את ההסבר דרך דוגמא שמובנת בפשטות (מעליות).
ימשיך לעקוב...
איליה (מהנדס תוכנה)

תגל שקד אמר/ה...

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

דני אמר/ה...

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