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

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

מגבלות על תהליכונים

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

נושאים במימוש

פעולות אטומיות

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

כתיבה אטומית

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

השווה והחלף

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

מחסומי זיכרון

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

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

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

תחביר שחרור (בלעז Release Semantics)

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

תחביר ניכוס (בלעז Acquire Semantics)

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

מחסום זיכרון מלא (בלעז Full Memory Barrier)

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

שיטות פעולה

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

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

דוגמאות

כותב אחד קורא אחד

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

מבנה נתונים:

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

אתחול:

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

כותב:

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

קורא:

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

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