מניעה הדדית
מניעה הדדית (Mutual exclusion) הוא מונח במדעי המחשב, בעיקר בתחום מערכות ההפעלה שאומר שלכל היותר תהליך אחד משתמש במשאב מסוים בכל רגע נתון בקטע קריטי. זו היא דרישה בסיסית בבקרת מקביליות, שמטרתה היא למנוע מצב של מרוץ תהליכים.
בעיית הקטע הקריטי
ערך מורחב – קטע קריטי
קטע קריטי הוא קטע קוד שעושה שימוש במשאב שמשותף לגורם נוסף והשימוש במשאב המשותף בזמן שקטע הקוד לא סיים לרוץ יכול להביא לתוצאות לא רצויות. מדען המחשב אדסחר דייקסטרה תיאר זאת במאמרו משנת 1965 - "פתרון בעיית השליטה בתכנות מקבילי"[1], כבעיה שמוכרת כבר משנת 1962 והוא אף מנסה להתמודד איתה במאמר הזה.
דוגמה פשוטה לבעיה עולה מהתבוננות על שני תהליכים הניגשים למקום בזיכרון שבו מאוחסנת רשימה מקושרת (ראה ציור 1) ורוצים למחוק בה שני צמתים שונים באמצע הרשימה שנסמן בתור הצומת ה-i והצומת ה-i+1. בזמן המחיקה המצביע לצומת הבא של הצומת i-1 ישתנה מ-i ל-i+1, והמצביע לתא הבא של הצומת i ישתנה ל-i+2. אמנם שתי הפעולות התבצעו בהצלחה אך בסוף הפעולות הצומת ה-i+1 עדיין חלק מהרשימה, כיוון שהצומת ה-i-1 עדיין מצביע עליו, ולמעשה נמחק רק תא אחד ולא שני תאים. את הבעיה הזאת (הנקראת לרוב "מרוץ תהליכים") היה ניתן למנוע באמצעות מניעה הדדית אשר הייתה מונעת מפעולה על הרשימה להתבצע לפני שהקודמת הייתה מסתיימת.
בנוסף למניעה הדדית בדרך כלל גם דורשים מהפתרון שימנע הרעבה של תהליכים ושהמשאב ישתחרר כמה שיותר מהר לאחר סיום הקטע הקריטי.
אכיפת מניעה הדדית
במחשבים ניתן לממש מניעה הדדית בשני רבדים: חומרה ותוכנה.
פתרונות חומרתיים
במערכות בעלות יחידת עיבוד מרכזית אחת (למשל ליבה אחת במעבד של מחשב), הפתרון הפשוט ביותר למימוש מניעה הדדית הוא על ידי ניטרול פסיקות בזמן שתהליך נמצא בקטע קוד קריטי. כך בקר הפסיקות לא יפסיק את פעולת התהליך באמצע ויאפשר לשגרה אחרת לשנות קטע זיכרון משותף. אף על פי שפתרון זה מאוד פשוט הוא יכול להוביל לבעיות רבות. אם הקטע הקריטי של התהליך הוא ארוך, שעון המערכת (המקודם על ידי פסיקות מבקר הפסיקות) יאבד דיוק בכל פעם שהשגרה תרוץ, כיוון שהשגרה המקדמת את השעון לא תופעל בזמן, ולכן מעקב אחר הזמן לא יהיה אפשרי בזמן ריצת התהליך. בנוסף, אם התהליך יעצור בזמן ריצת הקטע הקריטי, השליטה על יחידת העיבוד לא תועבר לתהליך אחר, מה שלמעשה יעצור את פעולת המערכת.
פתרונות תוכנתיים
מלבד פתרונות חומרתיים, קיימים מס' פתרונות תוכנתיים שבהם כל קוד שרוצה להיכנס לקטע קריטי נכנס לפונקציית כניסה שגורמת לו לחכות עד שמכניסה אותו ללא שיש עוד קודים אחרים בקטע הקריטי, וכשהוא יוצא משם הוא נכנס לפונקציית יציאה שבה הוא מסמל שהוא כבר לא בקטע הקריטי.
פתרונות אלו ממומשים על ידי פעולות אטומיות כגון סמפור או מנעול.
כמו כן ישנם אלגוריתמים שלא דורשים פעולות אטומיות מיוחדות, דוגמאות לכך ניתן למצוא באלגוריתמים הבאים:
- האלגוריתם של דקר (באנגלית "Dekker")
- האלגוריתם של פטרסון
- אלגוריתם המאפייה של למפורט
ועוד.
לרוב עדיף לתוכנות להסתמך על פתרונות המניעה ההדדית הניתנים על ידי החומרה או מערכת ההפעלה כגון הפעולות האטומיות. שימוש במנעולים אלו יאפשר לתהליך לבדוק האם המשאב פנוי. אם המנעול "פתוח" המשאב פנוי, והתהליך ינעל את המנעול ובכך יסמן לכל תהליך אחר שהמשאב אינו פנוי. אם המנעול "סגור", אזי תהליך אחר משתמש במשאב בזמן זה, ולכן לרוב הוא יאפשר החלפת הקשר ובכך יפנה את המעבד לתהליכים אחרים שיכולים לרוץ.
ראו גם
הערות שוליים
- ^ Dijkstra, E. W. (1965). "Solution of a problem in concurrent programming control". Communications of the ACM. 8 (9): 569. doi:10.1145/365559.365617.
29743392מניעה הדדית