Loading AI tools
מוויקיפדיה, האנציקלופדיה החופשית
במחשבים, קטע קריטי הוא קטע בפעילותן של מערכות מקביליות, שבמהלכו הן משתמשות ללא תיאום במשאב משותף, באופן העלול לגרום לתוצאות לא רצויות.
במערכות הפעלה, התוצאות הלא רצויות יכולות להיווצר בזמן שמערכת ההפעלה שמריצה את קטעי הקוד מבצעות החלפת הקשר (באנגלית – Context switch) במהלך הרצת הקטע הקריטי או משום שהקטע הקריטי רץ במקביל לַגורם הנוסף (בעזרת עיבוד מקבילי או חישוב מבוזר). כיוון שהשליטה בתזמון בין הקטע הקריטי לגורם הנוסף נעשית על ידי גורם שלישי (לרוב מערכת ההפעלה), נדרשים אמצעים כדי לוודא שהקוד יבצע את מטרתו.
מדען המחשב אדסחר דייקסטרה סקר את הנושא לראשונה במאמרו משנת 1965 – "פתרון בעיית השליטה בתכנות מקבילי".[1]
כדוגמה לקטע קריטי ניתן לקחת קטע מפעולתם של שני תהליכונים (המערכות), שמשתמשים ללא תיאום במשתנה משותף (המשאב). תהליכון ראשון יוסיף 1 למשתנה, ואחר יפחית ממנו אחד.
ניתן להציג את קטע פעולתם בפסאודו קוד, כך:
|
|
התוצאה שאנחנו מצפים לה היא שערך המשתנה יישאר כפי שהיה, מאחר שהוספת 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 מערכו המקורי.
ישנם מספר גורמים שיש להקפיד עליהם כאשר ניגשים לפתרון בעיית הקטע הקריטי כדי לפתור את הבעיה ולא ליצור בעיות אחרות.
קיימים מספר פתרונות לבעיית הקטע הקריטי. חלקם משתמשים בכלים שמערכת ההפעלה מספקת (מנעול, סמפור וכדומה) וחלקם לא.
במעבדים יש אפשרות לחסום את הפסיקות, מה שיכול לשמש לצורך מניעת החלפת הקשר באותו המעבד בקטע הקריטי. פעמים רבות משתמשים בחסימת פסיקות על מנת לייצר פעולה אטומית קטנה שתשמש כסמפור או לחסימת החלפת הקשר לוגית של מערכת ההפעלה.
בשנת 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;
|
האלגוריתם של פטרסון לא משתמש בכלים מיוחדים לפתרון בעיית הקטע הקריטי אלא עושה זאת באמצעים הרגילים שעומדים בפני המתכנת ובעזרתם הוא מתמודד עם כל הגורמים שדורשים טיפול:
flag[i] = true
ובנוסף הוא לא יעבור את לולאת ה־while
אלא אם כן התהליך השני לא הראה רצון להיכנס לקטע הקריטי (בתווית P0 או P1) או שהתהליך השני נמצא לפני הקטע הקריטי שלו ובדיוק עכשיו הציע לתהליך הראשון להקדים אותו (בתווית P1_gate או P0_gate). התהליך Pi לא משנה את turn
בזמן שהוא בקטע הקריטי, מה שמביא למסקנה ש־turn = i
כאשר התהליך השני רוצה להיכנס לקטע הקריטי ולכן, כל עוד תהליך Pi נמצא בקטע הקריטי שלו, התהליך השני לא יוכל לעבור את לולאת ה־while
.flag[i] = false
ולכן אם התהליך השני יוכל לעבור את ה־while
.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);
|
ניתן לראות שהשימוש בסמפור ממלא את שלושת התנאים:
בנוסף לשלושת התנאים האלו, השימוש בסמפור מונע "המתנה פעילה" כי הוא חוסם תהליכים שכרגע לא עובדים ומעיר אותם כשמגיע תורם.
קיפאון (באנגלית: Deadlock) היא בעיה שיכולה להיווצר בגלל העיקרון של המניעה ההדדית. כאשר קיימים שני תהליכים שכל אחד מהם משתמש במשאב משותף שונה והם גם רוצים להשתמש במשאב שהשני מחזיק, אז נוצר מצב של קיפאון כלומר, אף תהליך לא יכול לבצע את מטרתו כי הראשון מחכה עד שהוא יקבל את המשאב שהשני משתמש בו כרגע. והשני לא יסיים להשתמש במשאב כי הוא צריך את המשאב שהראשון משתמש בו כדי לסיים לעשות את מטרתו.
בעיית היצרן־צרכן (נקראת גם "בעיית החוצץ־המוגבל") הוא מצב שקיימים שני תהליכים כאשר אחד מהם מייצר מידע ושם אותו בחוצץ (buffer) בעל גודל מוגבל והתהליך השני שולף אותו מהחוצץ ומשתמש בו. החוצץ הוא משאב משותף והיצרן והצרכן לא יכולים לגשת אליו בו זמנית כדי שלא יתקבל מידע פגום. הבעיה היא שהיצרן יכול לשים בחוצץ כמות מוגבלת של מידע ואילו הצרכן יכול לצרוך רק כאשר קיים מידע בחוצץ. כדי לפתור את הבעיה הזאת יש להשתמש בפתרון שלא יאפשר גישה למידע בזמן שאחד התהליכים עדיין משתמש בו ובנוסף שלא ייווצר קיפאון כשהיצרן מנסה לייצר יותר מידע ממה שהחוצץ יכול להכיל וכשהצרכן מנסה לצרוך מידע כאשר החוצץ ריק.
בעיית הקוראים כותבים נוצרת כאשר יש מידע ושני סוגי תהליכים שנגשים למידע. תהליך קורא – קורא את המידע מבלי לשנות אותו. תהליך כותב – יכול לקרוא את המידע וגם לשנות אותו. כאשר הכותב ניגש למידע אז אסור לשום תהליך אחר לגשת למידע במקביל כדי שלא יתקבל מידע שגוי. כאשר הקורא ניגש למידע אז ניתן לאפשר גם לקוראים אחרים לגשת למידע והקריאה לא מהווה קטע קריטי ביחס לקוראים אחרים.
תתכן כאן בעיה של הרעבת הכותבים כי ברגע שיהיו הרבה קוראים אז הכותב לא יצליח לגשת אל המידע כי סביר שיהיה לפחות קורא אחד שמשתמש כרגע במידע.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.