חישוב מבוזר

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

רקע:

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

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

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

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

סנכרון:

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

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

בעיית הלחם (יותר מידי לחם):

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

אליס ובוב צריכים להחליט בניהם על אלגוריתם שיבטיח ששני התנאים הבאים יתקיימו:1. אדם אחד בלבד קונה לחם כשאין לחם.2. תמיד יש מישהו שקונה לחם כאשר אין לחם.

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

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

לאיזה סרט נלך?

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

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

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

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

תודה לאריאל מיכאל ואורן ניסים