קטע קריטי

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

דוגמה לקטע קריטי[עריכת קוד מקור | עריכה]

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

תהליכון ראשון
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 מערכו המקורי.

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

פתרון בעיית הקטע הקריטי[עריכת קוד מקור | עריכה]

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

  • מניעה הדדית (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] && turn == 1)
         {
             // busy wait
         }
         // critical section
         ...
         // end of critical section
         flag[0] = false;
P1:      flag[1] = true;
P1_gate: turn = 0;
         while (flag[0] && 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 תהליכים.

פתרון באמצעות סמפור[עריכת קוד מקור | עריכה]

Postscript-viewer-shaded.png ערך מורחב – סמפור

סֶמָפוֹר הוא מנגנון לסנכרון תהליכים, ומטרתו לפתור את בעיית הקטע הקריטי. מנגנון הסנכרון נוצר בעזרת משתנה מונה או משתנה בינארי (בסמפור בינארי) ותור, שניתן לבצע עליהם את הפעולות signal(S) ו- wait(S) כאשר כל אחת מהם נעשית בצורה אטומית.

יישום סמפור מונה[עריכת קוד מקור | עריכה]

פעולת הwait (נקראת גם P), פועלת באופן הבא:

  1. הקטנת המשתנה באחד
  2. אם ערך המונה שלילי, הוסף את התהליך שהפעיל את wait לתוך תור ו"תחסום" את התהליך.

פעולת הsignal (נקראת גם V), פועלת באופן הבא:

  1. קידום המשתנה באחד
  2. אם ערך המונה לא חיובי, הוצא תהליך מהתור ו"תעיר" אותו.

כדי שכל פעולה תתבצע באופן אטומי צריך שמערכת ההפעלה תתמוך בכך ולרוב היא מספקת את הסמפור.

שימוש בסמפור[עריכת קוד מקור | עריכה]

כאשר תהליך מכיל קטע קריטי ניתן למנוע גישה למשאב המשותף על ידי אתחול ערך הסמפור ל 1, ביצוע פעולת ה- wait לפני הקטע הקריטי ופעולת signal אחריו.

/*רק תהליך אחד מבצע פעם אחת*/
semaphore s;
s.value = 1;
wait(s);
//כאן נמצא הקטע הקריטי
signal(s);

ניתן לראות שהשימוש בסמפור ממלא את שלושת התנאים:

  • מניעה הדדית - כאשר תהליך רוצה להיכנס לקטע הקריטי שלו, הוא מבצע פעולת wait והפעולה גורמת להקטנת ערך המונה באחד. ערכו של המונה יהיה עכשיו 0 ולכן אף תהליך אחר לא יוכל להיכנס לקטע הקריטי כי כשהוא יבצע פעולת ה-wait לפני הקטע הקריטי, הוא יוריד את ערך המונה ב1 מה שיקבע את ערכו כשלילי ולכן התהליך יכנס לתור התהליכים שמחכים לפעול ובינתיים "ייחסם".
  • התקדמות - כאשר תהליך יוצא מהקטע הקריטי שלו הוא מבצע signal מה שמקדם את המונה ב1. אם עד אז אף תהליך לא ניסה להיכנס לקטע הקריטי אז זה אומר שערך המונה יהיה 1 מה שיאפשר לתהליך הבא שיבצע wait לפני הקטע הקריטי לא להיחסם ולבצע את הקטע הקריטי שלו. אם היה תהליך שניסה להיכנס לקטע הקריטי בזמן שהתהליך הראשון לא סיים, ערך המונה יהיה שלילי ולכן כאשר התהליך הראשון יבצע signal אז הוא יעיר את התהליך הבא בתור.
  • המתנה מוגבלת - כמובן שקיימת המתנה מוגבלת כיוון שיש תור של התהליכים שביקשו לרוץ.

בנוסף לשלושת התנאים האלו, השימוש בסמפור מונע "המתנה פעילה" כי הוא חוסם תהליכים שכרגע לא עובדים ומעיר אותם כשמגיע תורם.

קיפאון[עריכת קוד מקור | עריכה]

Postscript-viewer-shaded.png ערך מורחב – קיפאון

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

סוגים שונים של קטע קריטי[עריכת קוד מקור | עריכה]

בעיית היצרן-צרכן[עריכת קוד מקור | עריכה]

Postscript-viewer-shaded.png ערך מורחב – בעיית יצרן-צרכן

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

בעיית הקוראים-כותבים[עריכת קוד מקור | עריכה]

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

לקריאה נוספת[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ Dijkstra, E. W. (1965). "Solution of a problem in concurrent programming control". Communications of the ACM 8 (9): 569. doi:10.1145/365559.365617.