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

במדעי המחשב תופעה כזו נקראת ״הרעבה״, בויקיפדיה הם מתארים את זה במשפט:

הרעבה (באנגלית: Starvation) היא בעיה הנוצרת בסביבה המאפשרת ריבוי משימות (Multitasking), כאשר מתהליך מסוים נמנעת גישה לאחד ממשאבי המערכת כך שהתהליך לעולם לא יצליח לסיים את משימתו.

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

1. מעלית עם הרעבה

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

$waiting_at = [0, 2, 0, 0, 1, 0, 3, 0]
ticks = 0
loop do
  tick
  break if $waiting_at.all?(&:zero?)

  ticks += 1
end

puts "took #{ticks} seconds"

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

LIFT_SIZE = 4
$waiting_at = [0] * 10
$people_in_lift = 0
$lift_at = 0
$destination = 0
$left_to_wait = [0] * 10

def tick
  if $lift_at.zero?
    puts "#{$people_in_lift} people exited to the lobby"
    $people_in_lift = 0
    if $destination > 0
      $lift_at += 1
    elsif (destination = $waiting_at.rindex(&:positive?)) > 0
      $destination = destination
    end
  else # lift not at zero
    if $lift_at == $destination
      $destination = $waiting_at[..$lift_at-1].rindex(&:positive?) || 0
      # pick up the people from $destination
      picked_up = [$waiting_at[$lift_at], LIFT_SIZE - $people_in_lift].min
      left_to_wait = $waiting_at[$lift_at] - picked_up

      puts "picked up #{picked_up} people from floor #{$lift_at}; #{left_to_wait} people left to wait there"

      $people_in_lift += picked_up
      $waiting_at[$lift_at] = left_to_wait
    else # lift not at zero and not at destination
      $lift_at += ($destination - $lift_at) / ($destination - $lift_at).abs
    end
  end
end

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

כך נראה הפלט:

0 people exited to the lobby
0 people exited to the lobby
picked up 3 people from floor 6; 0 people left to wait there
picked up 1 people from floor 4; 0 people left to wait there
picked up 0 people from floor 1; 2 people left to wait there
4 people exited to the lobby
0 people exited to the lobby
picked up 2 people from floor 1; 0 people left to wait there
took 18 seconds

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

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

loop do
  tick
  $waiting_at[7] += 1 if (ticks % 4).zero?

  break if $waiting_at.all?(&:zero?)
  ticks += 1

  pp $waiting_at
end

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

התוכנית עכשיו לא תסתיים אבל כך נראה הפלט אחרי כמה שניות שהיא רצה:

[0, 2, 0, 0, 0, 0, 0, 174] at second 11446
[0, 2, 0, 0, 0, 0, 0, 174]
[0, 2, 0, 0, 0, 0, 0, 174] at second 11447
[0, 2, 0, 0, 0, 0, 0, 174]
[0, 2, 0, 0, 0, 0, 0, 174] at second 11448

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

2. איך זה יעבוד בלי הרעבה

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

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

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

def tick_no_starvation
  if $lift_at.zero?
    puts "#{$people_in_lift} people exited to the lobby"
    $people_in_lift = 0
    if $destination > 0
      $lift_at += 1
    elsif $waiting_at.rindex(&:positive?) > 0
      $destination = $left_to_wait.rindex(&:positive?) || $waiting_at.rindex(&:positive?)
    end
  else # lift not at zero
    if $lift_at == $destination
      $destination = $waiting_at[..$lift_at-1].rindex(&:positive?) || 0
      # pick up the people from $destination
      picked_up = [$waiting_at[$lift_at], LIFT_SIZE - $people_in_lift].min
      left_to_wait = $waiting_at[$lift_at] - picked_up

      $left_to_wait[$lift_at] = left_to_wait

      puts "picked up #{picked_up} people from floor #{$lift_at}; #{left_to_wait} people left to wait there"

      $people_in_lift += picked_up
      $waiting_at[$lift_at] = left_to_wait
    else # lift not at zero and not at destination
      $lift_at += ($destination - $lift_at) / ($destination - $lift_at).abs
    end
  end
end

והרצה אחרי כמה שניות נראית הרבה יותר טוב:

[0, 0, 0, 0, 0, 0, 0, 6] at second 45782
[0, 0, 0, 0, 0, 0, 0, 6]
[0, 0, 0, 0, 0, 0, 0, 6] at second 45783
[0, 0, 0, 0, 0, 0, 0, 6]
[0, 0, 0, 0, 0, 0, 0, 6] at second 45784
[0, 0, 0, 0, 0, 0, 0, 7]
[0, 0, 0, 0, 0, 0, 0, 7] at second 45785
[0, 0, 0, 0, 0, 0, 0, 7]
[0, 0, 0, 0, 0, 0, 0, 7] at second 45786

כן עדיין מחכים אנשים בקומה 7 (תמיד יחכו כי תמיד באים לשם עוד אנשים), אבל שאר הקומות ריקות. בקומה 7 עצמה אין יותר מדי אנשים כי המעלית יכולה לנסוע יותר מהר ולא צריכה לעצור בקומות התחתונות.

3. נ.ב.

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

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