משתמש:Turingstine/מניעה הדדית

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

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

ציור 1: שני הצמתים, i ו-i+1, מוסרים במקביל, אך בסוף הצומת i+1 לא הוסר

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

אכיפת מניעה הדדית

במחשבים ניתן לממש מניעה הדדית בשני רבדים: חומרה ותוכנה.

פתרונות חומרתיים

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

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

פתרונות תוכנתיים

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

• האלגוריתם של דקר (באנגלית "Dekker")
• האלגוריתם של פיטרסון
• אלגוריתם המאפייה של למפורט

ועוד.

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

ראו גם

• הרעבה (מדעי המחשב)
• קיפאון (מדעי המחשב)
• עיבוד מקבילי
• בקרת מקביליות
• סמפור (מדעי המחשב)
• מנעול (תוכנה)

הערות שוליים

קטגוריה:מדעי המחשב