קטע קריטי
במחשבים, קטע קריטי הוא קטע בפעילותן של מערכות מקביליות, שבמהלכו הן משתמשות ללא תיאום במשאב משותף, באופן העלול לגרום לתוצאות לא רצויות.
במערכות הפעלה, התוצאות הלא רצויות יכולות להיווצר בזמן שמערכת ההפעלה שמריצה את קטעי הקוד מבצעות החלפת הקשר (באנגלית – Context switch) במהלך הרצת הקטע הקריטי או משום שהקטע הקריטי רץ במקביל לַגורם הנוסף (בעזרת עיבוד מקבילי או חישוב מבוזר). כיוון שהשליטה בתזמון בין הקטע הקריטי לגורם הנוסף, נעשית על ידי גורם שלישי – לרוב מערכת ההפעלה. נדרשים אמצעים כדי לוודא שהקוד יבצע את מטרתו.
מדען המחשב אדסחר דייקסטרה סקר את הנושא לראשונה במאמרו משנת 1965 – "פתרון בעיית השליטה בתכנות מקבילי".[1]
דוגמה לקטע קריטי
כדוגמה לקטע קריטי ניתן לקחת קטע מפעולתם של שני תהליכונים (המערכות), שמשתמשים ללא תיאום במשתנה משותף (המשאב). תהליכון ראשון יוסיף 1 למשתנה, ואחר יפחית ממנו אחד.
ניתן להציג את קטע פעולתם בפסאודו קוד, כך:
תהליכון ראשון 1 קריאת המשתנה מהזיכרון המשותף 2 הוספת אחד למספר 3 שמירת התוצאה בזיכרון המשותף תהליכון שני 1 קריאת המשתנה מהזיכרון המשותף 2 הורדת אחד מהמספר 3 שמירת התוצאה בזיכרון המשותף
התוצאה שאנחנו מצפים לה היא שערך המשתנה ישאר כפי שהיה, מאחר שהוספת 1 והורדת 1 הן פעולות שמבטלות זו את זו, ומחזירות את המשתנה לערכו המקורי.
אולם, אם התהליכון השני ירוץ במהלך ריצת הראשון, ייתכן שהתוצאה תהיה שונה, כבדוגמת ההרצה הזאת:
תהליכון – מספר פקודה פקודה ערך המשתנה אחרי 1 ראשון – 1 קריאת המשתנה מהזיכרון המשותף משותף = k, מקומי = k 2 ראשון – 2 הוספת אחד למספר משותף = k, מקומי = k+1 3 שני – 1 קריאת המשתנה מהזיכרון המשותף משותף = k, מקומי = k 4 שני – 2 הורדת אחד מהמספר משותף = k, מקומי = k-1 5 ראשון – 3 שמירת התוצאה בזיכרון המשותף משותף = k+1, מקומי = k+1 6 שני – 3 שמירת התוצאה בזיכרון המשותף משותף = k-1, מקומי = k-1
כך, בניגוד למצופה, ערכו של המשתנה המשותף בסוף הרצת הקטע הקריטי קטן ב–1 מערכו המקורי.
פתרון בעיית הקטע הקריטי
ישנם מספר גורמים שיש להקפיד עליהם כאשר ניגשים לפתרון בעיית הקטע הקריטי כדי לפתור את הבעיה ולא ליצור בעיות אחרות.
- מניעה הדדית (Mutual exclusion) – כאשר הקטע הקריטי רץ, יש למנוע שימוש במשאב המשותף על ידי גורם אחר שיכול להפריע לפעולה התקינה של הקטע הקריטי. כיוון שכך, כדאי להכניס לקטע הקריטי רק קוד שהכרחי שיהיה בו כדי שהשימוש במשאב לא יהיה חסום ללא צורך.
- התקדמות (Progress) – כאשר מונעים שימוש של גורמים נוספים במשאב, יש לוודא שלאחר שהקטע הקריטי סיים לרוץ, לא תישאר המניעה על השימוש במשאב.
- המתנה מוגבלת (Bounded Waiting) – יש לוודא שכל גורם שמבקש לרוץ, יעשה את זה תוך מספר מוגבל של קטעים קריטיים שירוצו לפניו.
קיימים מספר פתרונות לבעיית הקטע הקריטי. חלקם משתמשים בכלים שמערכת ההפעלה מספקת (מנעול, סמפור וכדומה) וחלקם לא.
חסימת פסיקות
במעבדים יש אפשרות לחסום את הפסיקות, מה שיכול לשמש לצורך מניעת החלפת הקשר באותו המעבד בקטע הקריטי. פעמים רבות משתמשים בחסימת פסיקות על מנת לייצר פעולה אטומית קטנה שתשמש כסמפור או לחסימת החלפת הקשר לוגית של מערכת ההפעלה.
האלגוריתם של פטרסון
בשנת 1981 ניסח גארי פטרסון אלגוריתם לפתרון בעיית הקטע הקריטי עבור 2 תהליכים\תהליכונים. האלגוריתם משתמש בשני משתנים משותפים, flag ו־turn. ערך חיובי עבור flag[n] מראה על כך שתהליך n מעוניין להיכנס לקטע הקריטי שלו. הכניסה לקטע הקריטי ניתנת לתהליך P0 אם תהליך P1 לא מעוניין להיכנס לקטע הקריטי שלו או אם P1 נתן קדימות לתהליך P0 על ידי השמת הערך 0 במשתנה turn.
bool flag[0] = false;
bool flag[1] = false;
int turn;
| |
P0: flag[0] = true;
P0_gate: turn = 1;
while (flag[1]==true && turn == 1)
{
// busy wait
}
// critical section
...
// end of critical section
flag[0] = false;
|
P1: flag[1] = true;
P1_gate: turn = 0;
while (flag[0]==true && turn == 0)
{
// busy wait
}
// critical section
...
// end of critical section
flag[1] = false;
|
האלגוריתם של פטרסון לא משתמש בכלים מיוחדים לפתרון בעיית הקטע הקריטי אלא עושה זאת באמצעים הרגילים שעומדים בפני המתכנת ובעזרתם הוא מתמודד עם כל הגורמים שדורשים טיפול:
- מניעה הדדית – כאשר אחד התהליכים נמצא בקטע הקריטי שלו, לא משנה איפה תתבצע החלפת הקשר וכמה פעמים, התהליך השני לא יוכל להיכנס לקטע הקריטי שלו, כלומר לגשת למשאב המשותף בזמן שהתהליך הראשון לא סיים להשתמש בו. הסיבה לכך היא שתהליך Pi נכנס לקטע הקריטי שלו רק כאשר
flag[i] = trueובנוסף הוא לא יעבור את לולאת ה־whileאלא אם כן התהליך השני לא הראה רצון להיכנס לקטע הקריטי (בתווית P0 או P1) או שהתהליך השני נמצא לפני הקטע הקריטי שלו ובדיוק עכשיו הציע לתהליך הראשון להקדים אותו (בתווית P1_gate או P0_gate). התהליך Pi לא משנה אתturnבזמן שהוא בקטע הקריטי, מה שמביא למסקנה ש־turn = iכאשר התהליך השני רוצה להיכנס לקטע הקריטי ולכן, כל עוד תהליך Pi נמצא בקטע הקריטי שלו, התהליך השני לא יוכל לעבור את לולאת ה־while. - התקדמות – כאשר תהליך Pi סיים את הקטע הקריטי, הוא מבצע
flag[i] = falseולכן אם התהליך השני יוכל לעבור את ה־while. - המתנה מוגבלת – כאשר Pi נמצא ב־
whileאז התהליך השני לא יוכל להריץ את הקטע הקריטי שלו יותר מפעם אחת מכיוון שהוא יהיה חייב לשנותturn = iו־Pi כבר סימןflag[i] = trueולכן הוא לא יעבור את ה־whileעד ש־Pi לא יבצע את הקטע הקריטי שלו.
האלגוריתם עובד בשיטה של המתנה פעילה (busy waiting) כלומר, כאשר הקטע הקריטי לא סיים לרוץ, כל זמן שלא הגיע תור התהליך השני להריץ את הקטע הקריטי הוא יהיה תקוע בלולאת ה־while וידרוש זמן מעבד. יש להזכיר גם שניתן ליישם רעיון דומה עבור N תהליכים.
פתרון באמצעות סמפור
ערך מורחב – סמפור
סֶמָפוֹר הוא מנגנון לסנכרון תהליכים, ומטרתו לפתור את בעיית הקטע הקריטי.
מנגנון הסנכרון נוצר בעזרת משתנה מונה או משתנה בינארי (בסמפור בינארי) ותור, שניתן לבצע עליהם את הפעולות signal(S) ו־wait(S) כאשר כל אחת מהם נעשית בצורה אטומית.
יישום סמפור מונה
פעולת ה־wait (נקראת גם P), פועלת באופן הבא:
- חכה עד שערך המונה גדול מאפס.
- הקטן את ערך המונה באחד.
פעולת ה־signal (נקראת גם V),פועלת באופן הבא:
- קדם את המשתנה באחד.
כדי שכל פעולה תתבצע באופן אטומי צריך שמערכת ההפעלה תתמוך בכך ולרוב היא מספקת את הסמפור.[2]
שימוש בסמפור
כאשר תהליך מכיל קטע קריטי ניתן למנוע גישה למשאב המשותף על ידי אתחול ערך הסמפור ל־1, ביצוע פעולת ה־wait לפני הקטע הקריטי ופעולת signal אחריו.
/*רק תהליך אחד מבצע פעם אחת*/
semaphore s;
s.value = 1;
| |
wait(s);
//כאן נמצא הקטע הקריטי
signal(s);
| |
ניתן לראות שהשימוש בסמפור ממלא את שלושת התנאים:
- מניעה הדדית – כאשר תהליך רוצה להיכנס לקטע הקריטי שלו, הוא מבצע פעולת wait והפעולה גורמת להקטנת ערך המונה באחד. ערכו של המונה יהיה עכשיו 0 ולכן אף תהליך אחר לא יוכל להיכנס לקטע הקריטי כי כשהוא יבצע פעולת ה־wait לפני הקטע הקריטי, הוא יוריד את ערך המונה ב־1 מה שיקבע את ערכו כשלילי ולכן התהליך יכנס לתור התהליכים שמחכים לפעול ובינתיים "ייחסם".
- התקדמות – כאשר תהליך יוצא מהקטע הקריטי שלו הוא מבצע signal מה שמקדם את המונה ב־1. אם עד אז אף תהליך לא ניסה להיכנס לקטע הקריטי אז זה אומר שערך המונה יהיה 1 מה שיאפשר לתהליך הבא שיבצע wait לפני הקטע הקריטי לא להיחסם ולבצע את הקטע הקריטי שלו. אם היה תהליך שניסה להיכנס לקטע הקריטי בזמן שהתהליך הראשון לא סיים, ערך המונה יהיה שלילי ולכן כאשר התהליך הראשון יבצע signal אז הוא יעיר את התהליך הבא בתור.
- המתנה מוגבלת – קיימת המתנה מוגבלת כיוון שיש תור של התהליכים שביקשו לרוץ.
בנוסף לשלושת התנאים האלו, השימוש בסמפור מונע "המתנה פעילה" כי הוא חוסם תהליכים שכרגע לא עובדים ומעיר אותם כשמגיע תורם.
קיפאון
- ערך מורחב – קיפאון
קיפאון (באנגלית: Deadlock) היא בעיה שיכולה להיווצר בגלל העיקרון של המניעה ההדדית. כאשר קיימים שני תהליכים שכל אחד מהם משתמש במשאב משותף שונה והם גם רוצים להשתמש במשאב שהשני מחזיק, אז נוצר מצב של קיפאון כלומר, אף תהליך לא יכול לבצע את מטרתו כי הראשון מחכה עד שהוא יקבל את המשאב שהשני משתמש בו כרגע. והשני לא יסיים להשתמש במשאב כי הוא צריך את המשאב שהראשון משתמש בו כדי לסיים לעשות את מטרתו.
סוגים שונים של קטע קריטי
בעיית היצרן־צרכן
- ערך מורחב – בעיית יצרן-צרכן
בעיית היצרן־צרכן (נקראת גם "בעיית החוצץ־המוגבל") הוא מצב שקיימים שני תהליכים כאשר אחד מהם מייצר מידע ושם אותו בחוצץ (buffer) בעל גודל מוגבל והתהליך השני שולף אותו מהחוצץ ומשתמש בו. החוצץ הוא משאב משותף והיצרן והצרכן לא יכולים לגשת אליו בו זמנית כדי שלא יתקבל מידע פגום. הבעיה היא שהיצרן יכול לשים בחוצץ כמות מוגבלת של מידע ואילו הצרכן יכול לצרוך רק כאשר קיים מידע בחוצץ. כדי לפתור את הבעיה הזאת יש להשתמש בפתרון שלא יאפשר גישה למידע בזמן שאחד התהליכים עדיין משתמש בו ובנוסף שלא ייווצר קיפאון כשהיצרן מנסה לייצר יותר מידע ממה שהחוצץ יכול להכיל וכשהצרכן מנסה לצרוך מידע כאשר החוצץ ריק.
בעיית הקוראים־כותבים
בעיית הקוראים כותבים נוצרת כאשר יש מידע ושני סוגי תהליכים שנגשים למידע. תהליך קורא – קורא את המידע מבלי לשנות אותו. תהליך כותב – יכול לקרוא את המידע וגם לשנות אותו. כאשר הכותב ניגש למידע אז אסור לשום תהליך אחר לגשת למידע במקביל כדי שלא יתקבל מידע שגוי. כאשר הקורא ניגש למידע אז ניתן לאפשר גם לקוראים אחרים לגשת למידע והקריאה לא מהווה קטע קריטי ביחס לקוראים אחרים.
תתכן כאן בעיה של הרעבת הכותבים כי ברגע שיהיו הרבה קוראים אז הכותב לא יצליח לגשת אל המידע כי סביר שיהיה לפחות קורא אחד שמשתמש כרגע במידע.
ראו גם
קישורים חיצוניים
- פרק 6 – "סנכרון תהליכים", מהמצגות של זילברשטץ, גלווין וגגנה
הערות שוליים
- ^ Dijkstra, E. W. (1965). "Solution of a problem in concurrent programming control". Communications of the ACM. 8 (9): 569. doi:10.1145/365559.365617.
- ^ oracle counter semaphore
33821492קטע קריטי