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

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

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

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

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

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

כתיבה אטומית

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

השווה והחלף

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

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

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

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

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

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

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

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

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