אלגוריתם חסר נעילות

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

מגבלות על תהליכונים[עריכת קוד מקור | עריכה]

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

נושאים במימוש[עריכת קוד מקור | עריכה]

פעולות אטומיות[עריכת קוד מקור | עריכה]

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

כתיבה אטומית[עריכת קוד מקור | עריכה]

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

השווה והחלף[עריכת קוד מקור | עריכה]

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

מחסומי זיכרון[עריכת קוד מקור | עריכה]

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

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

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

תחביר שחרור (בלעז Release Semantics)[עריכת קוד מקור | עריכה]

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

תחביר ניכוס (בלעז Acquire Semantics)[עריכת קוד מקור | עריכה]

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

מחסום זיכרון מלא (בלעז Full Memory Barrier)[עריכת קוד מקור | עריכה]

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

שיטות פעולה[עריכת קוד מקור | עריכה]

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

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

דוגמאות[עריכת קוד מקור | עריכה]

כותב אחד קורא אחד[עריכת קוד מקור | עריכה]

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

מבנה נתונים:

  • מצביע לחדש
  • מצביע לישן
  • אובייקט
    • מצביע לאובייקט הבא (כתיבה למצביע זה צריכה להיות אטומית)

איתחול:

  • יצירת אובייקט ראשון
  • קביעת 'מצביע לחדש' שיצביע לאובייקט הזה.
  • קביעת 'מצביע לישן' שיצביע גם הוא לאובייקט הזה.

כותב:

  • יוצר אובייקט חדש עם כל המידע הדרוש (קורא מ'מצביע לחדש' את האובייקט הנוכחי ועושה את השינויים הדרושים באובייקט חדש).
  • גורם לאובייקט המוצבע כעת על ידי 'מצביע לחדש' שה-'מצביע לאובייקט הבא' שלו יצביע לאובייקט החדש.
  • מחליף את ה'מצביע לחדש' להצביע גם הוא על האובייקט החדש.

קורא:

  • בלולאה:
    • במידה ובאובייקט המוצבע על ידי 'מצביע לישן', ה-'מצביע לאובייקט הבא' אכן מצביע לאובייקט נוסף:
      • קרא את ה-'מצביע לאובייקט הבא' ל-A (משתנה פרטי לתהליכון)
      • הרוס את האובייקט המוצבע על ידי 'מצביע לישן'.
      • קבע את 'מצביע לישן' ל-A.
    • במידה ובאובייקט המוצבע על ידי 'מצביע לישן', ה-'מצביע לאובייקט הבא' אינו מצביע לאובייקט נוסף, צא מן הלולאה.
  • קרא מהאובייקט המוצבע על ידי 'מצביע לישן' והשתמש במידע.

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

קישורים חיצוניים[עריכת קוד מקור | עריכה]