קטע קריטי – הבדלי גרסאות

מתוך ויקיפדיה, האנציקלופדיה החופשית
תוכן שנמחק תוכן שנוסף
מאין תקציר עריכה
אחידות במיקום הערות שוליים
שורה 1: שורה 1:
'''קטע קריטי''' הוא מושג ב[[מחשב|מחשבים]] ובפרט מתחום [[מערכת הפעלה|מערכות הפעלה]] אשר מתייחס למערכות [[עיבוד מקבילי|מקביליות]], שעושות שימוש ב[[משאב מערכת|משאב]] משותף. השימוש במשאב המשותף מבלי שהמערכות מתואמות ביניהם, יכול להביא לתוצאות לא רצויות. [[מדען מחשב|מדען המחשב]] [[אדסחר דייקסטרה]] תיאר זאת במאמרו משנת 1965 - "פתרון בעיית השליטה בתכנות מקבילי"{{הערה|{{cite journal|last=Dijkstra|first=E. W.|title=Solution of a problem in concurrent programming control|journal=Communications of the ACM|volume=8|issue=9|pages=569|doi=10.1145/365559.365617|year=1965}}}}, כבעיה שמוכרת כבר משנת 1962 והוא אף מנסה להתמודד איתה במאמר הזה.
'''קטע קריטי''' הוא מושג{{הבהרה|סיבה=מה ההגדרה של קטע קריטי?}} ב[[מחשב]]ים ובפרט מתחום [[מערכת הפעלה|מערכות הפעלה]] אשר מתייחס למערכות [[עיבוד מקבילי|מקביליות]], שעושות שימוש ב[[משאב מערכת|משאב]] משותף. השימוש במשאב המשותף מבלי שהמערכות מתואמות ביניהם, יכול להביא לתוצאות לא רצויות. [[מדען מחשב|מדען המחשב]] [[אדסחר דייקסטרה]] תיאר זאת במאמרו משנת 1965  "פתרון בעיית השליטה בתכנות מקבילי",{{הערה|{{cite journal|last=Dijkstra|first=E. W.|title=Solution of a problem in concurrent programming control|journal=Communications of the ACM|volume=8|issue=9|pages=569|doi=10.1145/365559.365617|year=1965}}}} כבעיה שמוכרת כבר משנת 1962 והוא אף מנסה להתמודד איתה במאמר הזה.


== דוגמה לקטע קריטי ==
== דוגמה לקטע קריטי ==
כדוגמה ניתן לקחת בתור קטע קריטי, קטע קוד של [[תהליכון]] (המערכת) שמקדם [[משתנה (תכנות)|משתנה]] משותף (המשאב) באחד, והגורם הנוסף יהיה תהליכון שני שמפחית מהמשתנה אחד.{{ש}}
כדוגמה ניתן לקחת בתור קטע קריטי, קטע קוד של [[תהליכון]] (המערכת) שמקדם [[משתנה (תכנות)|משתנה]] משותף (המשאב) באחד, והגורם הנוסף יהיה תהליכון שני שמפחית מהמשתנה אחד.

ניתן להציג את הקוד כך:
ניתן להציג את הקוד כך:
:{|
:{|
|
|
{| class="wikitable"
{| class="wikitable"
!
!
! <span style="color: red">תהליכון ראשון</span>
! <span style="color: red">תהליכון ראשון</span>
|-
|-
שורה 19: שורה 20:
| שמירת התוצאה בזיכרון המשותף
| שמירת התוצאה בזיכרון המשותף
|}
|}
|
|
:{| class="wikitable"
:{| class="wikitable"
!
!
! <span style="color: green">תהליכון שני</span>
! <span style="color: green">תהליכון שני</span>
|-
|-
שורה 34: שורה 35:
|}
|}
|}
|}
התוצאה שאנחנו מצפים לה היא הערך הראשוני של המשתנה, מאחר שהוספת 1 והורדת 1 משאירה את המשתנה ללא שינוי בערכו.
התוצאה שאנחנו מצפים לה היא הערך הראשוני של המשתנה, מאחר שהוספת 1 והורדת 1 משאירה את המשתנה ללא שינוי בערכו.
אולם, אם התהליכון השני ירוץ במהלך ריצת קטע הקוד הראשון, ייתכן שהתוצאה תהיה שונה כמו בדוגמת ההרצה הזאת:
אולם, אם התהליכון השני ירוץ במהלך ריצת קטע הקוד הראשון, ייתכן שהתוצאה תהיה שונה כמו בדוגמת ההרצה הזאת:
:{| class="wikitable"
:{| class="wikitable"
!
!
! תהליכון - מספר פקודה
! תהליכון מספר פקודה
! פקודה
! פקודה
! ערך המשתנה אחרי
! ערך המשתנה אחרי
|-
|-
! 1
! 1
| <span style="color: red">ראשון - 1</span>
| <span style="color: red">ראשון 1</span>
| <span style="color: red">קריאת המשתנה מהזיכרון המשותף</span>
| <span style="color: red">קריאת המשתנה מהזיכרון המשותף</span>
| משותף = k, מקומי = k
| משותף = k, מקומי = k
|-
|-
! 2
! 2
| <span style="color: red">ראשון - 2</span>
| <span style="color: red">ראשון 2</span>
| <span style="color: red">הוספת אחד למספר</span>
| <span style="color: red">הוספת אחד למספר</span>
| משותף = k, מקומי = k+1
| משותף = k, מקומי = k+1
|-
|-
! 3
! 3
| <span style="color: green">שני - 1</span>
| <span style="color: green">שני 1</span>
| <span style="color: green">קריאת המשתנה מהזיכרון המשותף</span>
| <span style="color: green">קריאת המשתנה מהזיכרון המשותף</span>
| משותף = k, מקומי = k
| משותף = k, מקומי = k
|-
|-
! 4
! 4
| <span style="color: green">שני - 2</span>
| <span style="color: green">שני 2</span>
| <span style="color: green">הורדת אחד מהמספר</span>
| <span style="color: green">הורדת אחד מהמספר</span>
| משותף = k, מקומי = k-1
| משותף = k, מקומי = k-1
|-
|-
! 5
! 5
| <span style="color: red">ראשון - 3</span>
| <span style="color: red">ראשון 3</span>
| <span style="color: red">שמירת התוצאה בזיכרון המשותף</span>
| <span style="color: red">שמירת התוצאה בזיכרון המשותף</span>
| משותף = k+1, מקומי = k+1
| משותף = k+1, מקומי = k+1
|-
|-
! 6
! 6
| <span style="color: green">שני - 3</span>
| <span style="color: green">שני 3</span>
| <span style="color: green">שמירת התוצאה בזיכרון המשותף</span>
| <span style="color: green">שמירת התוצאה בזיכרון המשותף</span>
| משותף = k-1, מקומי = k-1
| משותף = k-1, מקומי = k-1
שורה 74: שורה 75:
כפי שניתן לראות, בניגוד למצופה, ערכו של המשתנה המשותף בסוף הרצת הקטע הקריטי קטן ב–1 מערכו המקורי.
כפי שניתן לראות, בניגוד למצופה, ערכו של המשתנה המשותף בסוף הרצת הקטע הקריטי קטן ב–1 מערכו המקורי.


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


== פתרון בעיית הקטע הקריטי ==
== פתרון בעיית הקטע הקריטי ==
ישנם מספר גורמים שיש להקפיד עליהם כאשר ניגשים לפתרון בעיית הקטע הקריטי כדי לפתור את הבעיה ולא ליצור בעיות אחרות.
ישנם מספר גורמים שיש להקפיד עליהם כאשר ניגשים לפתרון בעיית הקטע הקריטי כדי לפתור את הבעיה ולא ליצור בעיות אחרות.
* '''[[מניעה הדדית]]''' (Mutual exclusion)- כאשר הקטע הקריטי רץ, יש למנוע שימוש במשאב המשותף על ידי גורם אחר שיכול להפריע לפעולה התקינה של הקטע הקריטי. כיוון שכך, כדאי להכניס לקטע הקריטי רק קוד שהכרחי שיהיה בו כדי שהשימוש במשאב לא יהיה חסום ללא צורך.
* '''[[מניעה הדדית]]''' (Mutual exclusion) כאשר הקטע הקריטי רץ, יש למנוע שימוש במשאב המשותף על ידי גורם אחר שיכול להפריע לפעולה התקינה של הקטע הקריטי. כיוון שכך, כדאי להכניס לקטע הקריטי רק קוד שהכרחי שיהיה בו כדי שהשימוש במשאב לא יהיה חסום ללא צורך.
* '''התקדמות''' (Progress) - כאשר מונעים שימוש של גורמים נוספים במשאב, יש לוודא שלאחר שהקטע הקריטי סיים לרוץ, לא תישאר המניעה על השימוש במשאב.
* '''התקדמות''' (Progress) כאשר מונעים שימוש של גורמים נוספים במשאב, יש לוודא שלאחר שהקטע הקריטי סיים לרוץ, לא תישאר המניעה על השימוש במשאב.
* '''[[הרעבה (מדעי המחשב)|המתנה מוגבלת]]''' (Bounded Waiting) - יש לוודא שכל גורם שמבקש לרוץ, יעשה את זה תוך מספר מוגבל של קטעים קריטיים שירוצו לפניו.
* '''[[הרעבה (מדעי המחשב)|המתנה מוגבלת]]''' (Bounded Waiting) יש לוודא שכל גורם שמבקש לרוץ, יעשה את זה תוך מספר מוגבל של קטעים קריטיים שירוצו לפניו.


קיימים מספר פתרונות לבעיית הקטע הקריטי. חלקם משתמשים בכלים שמערכת ההפעלה מספקת (מנעול, סמפור וכולי) וחלקם לא.
קיימים מספר פתרונות לבעיית הקטע הקריטי. חלקם משתמשים בכלים שמערכת ההפעלה מספקת (מנעול, סמפור וכולי) וחלקם לא.


=== האלגוריתם של פטרסון ===
=== האלגוריתם של פטרסון ===
בשנת 1981 ניסח גארי פטרסון אלגוריתם לפתרון בעיית הקטע הקריטי עבור 2 [[תהליך (מדעי המחשב)|תהליכים]]\תהליכונים. האלגוריתם משתמש בשני משתנים משותפים, flag ו-turn. ערך חיובי עבור {{משמאל לימין|flag[n]}} מראה על כך שתהליך n מעוניין להיכנס לקטע הקריטי שלו. הכניסה לקטע הקריטי ניתנת לתהליך P0 אם תהליך P1 לא מעוניין להיכנס לקטע הקריטי שלו או אם P1 נתן קדימות לתהליך P0 על ידי השמת הערך 0 במשתנה turn.
בשנת 1981 ניסח גארי פטרסון אלגוריתם לפתרון בעיית הקטע הקריטי עבור 2 [[תהליך (מדעי המחשב)|תהליכים]]\תהליכונים. האלגוריתם משתמש בשני משתנים משותפים, flag ו־turn. ערך חיובי עבור {{משמאל לימין|flag[n]}} מראה על כך שתהליך n מעוניין להיכנס לקטע הקריטי שלו. הכניסה לקטע הקריטי ניתנת לתהליך P0 אם תהליך P1 לא מעוניין להיכנס לקטע הקריטי שלו או אם P1 נתן קדימות לתהליך P0 על ידי השמת הערך 0 במשתנה turn.


{| style="width:70%"
{| style="width:70%"
שורה 123: שורה 124:
|}
|}


האלגוריתם של פטרסון לא משתמש בכלים מיוחדים לפתרון בעיית הקטע הקריטי אלא עושה זאת באמצעים הרגילים שעומדים בפני המתכנת ובעזרתם הוא מתמודד עם כל הגורמים שדורשים טיפול:{{ש}}
האלגוריתם של פטרסון לא משתמש בכלים מיוחדים לפתרון בעיית הקטע הקריטי אלא עושה זאת באמצעים הרגילים שעומדים בפני המתכנת ובעזרתם הוא מתמודד עם כל הגורמים שדורשים טיפול:
* מניעה הדדית - כאשר אחד התהליכים נמצא בקטע הקריטי שלו, לא משנה איפה תתבצע החלפת הקשר וכמה פעמים, התהליך השני לא יוכל להיכנס לקטע הקריטי שלו, כלומר לגשת למשאב המשותף בזמן שהתהליך הראשון לא סיים להשתמש בו. הסיבה לכך היא שתהליך P<sub>i</sub> נכנס לקטע הקריטי שלו רק כאשר <code>flag[i] = true</code> ובנוסף הוא לא יעבור את [[לולאה|לולאת]] ה-<code>while</code> אלא אם כן התהליך השני לא הראה רצון להיכנס לקטע הקריטי (בתווית P0 או P1) או שהתהליך השני נמצא לפני הקטע הקריטי שלו ובדיוק עכשיו הציע לתהליך הראשון להקדים אותו (בתווית P1_gate או P0_gate). כמובן שתהליך P<sub>i</sub> לא משנה את <code>turn</code> בזמן שהוא בקטע הקריטי, מה שמביא למסקנה ש- <code>turn = i</code> כאשר התהליך השני רוצה להיכנס לקטע הקריטי ולכן, כל עוד תהליך P<sub>i</sub> נמצא בקטע הקריטי שלו, התהליך השני לא יוכל לעבור את לולאת ה-<code>while</code>.
* מניעה הדדית כאשר אחד התהליכים נמצא בקטע הקריטי שלו, לא משנה איפה תתבצע החלפת הקשר וכמה פעמים, התהליך השני לא יוכל להיכנס לקטע הקריטי שלו, כלומר לגשת למשאב המשותף בזמן שהתהליך הראשון לא סיים להשתמש בו. הסיבה לכך היא שתהליך P<sub>i</sub> נכנס לקטע הקריטי שלו רק כאשר <code>flag[i] = true</code> ובנוסף הוא לא יעבור את [[לולאה|לולאת]] ה־<code>while</code> אלא אם כן התהליך השני לא הראה רצון להיכנס לקטע הקריטי (בתווית P0 או P1) או שהתהליך השני נמצא לפני הקטע הקריטי שלו ובדיוק עכשיו הציע לתהליך הראשון להקדים אותו (בתווית P1_gate או P0_gate). התהליך P<sub>i</sub> לא משנה את <code>turn</code> בזמן שהוא בקטע הקריטי, מה שמביא למסקנה ש־<code>turn = i</code> כאשר התהליך השני רוצה להיכנס לקטע הקריטי ולכן, כל עוד תהליך P<sub>i</sub> נמצא בקטע הקריטי שלו, התהליך השני לא יוכל לעבור את לולאת ה־<code>while</code>.
* התקדמות - כאשר תהליך P<sub>i </sub>סיים את הקטע הקריטי, הוא מבצע <code>flag[i] = false</code> ולכן אם התהליך השני יוכל לעבור את ה-<code>while</code>.
* התקדמות כאשר תהליך P<sub>i</sub> סיים את הקטע הקריטי, הוא מבצע <code>flag[i] = false</code> ולכן אם התהליך השני יוכל לעבור את ה־<code>while</code>.
* המתנה מוגבלת - כאשר P<sub>i </sub>נמצא ב-<code>while</code> אז התהליך השני לא יוכל להריץ את הקטע הקריטי שלו יותר מפעם אחת בגלל שהוא יהיה חייב לשנות <code>turn = i</code> ו P<sub>i</sub> כבר סימן <code>flag[i] = true</code> ולכן הוא לא יעבור את ה-<code>while</code> עד ש P<sub>i</sub> לא יבצע את הקטע הקריטי שלו.
* המתנה מוגבלת כאשר P<sub>i </sub>נמצא ב־<code>while</code> אז התהליך השני לא יוכל להריץ את הקטע הקריטי שלו יותר מפעם אחת מכיוון שהוא יהיה חייב לשנות <code>turn = i</code> ו־P<sub>i</sub> כבר סימן <code>flag[i] = true</code> ולכן הוא לא יעבור את ה־<code>while</code> עד ש־P<sub>i</sub> לא יבצע את הקטע הקריטי שלו.


יש לציין שהאלגוריתם עובד בשיטה של [[המתנה (מדעי המחשב)|המתנה פעילה]] (busy waiting) כלומר, כאשר הקטע הקריטי לא סיים לרוץ, כל זמן שלא הגיע תור התהליך השני להריץ את הקטע הקריטי הוא יהיה תקוע בלולאת ה-<code>while</code> וידרוש זמן מעבד. יש להזכיר גם שניתן ליישם רעיון דומה עבור N תהליכים.
האלגוריתם עובד בשיטה של [[המתנה (מדעי המחשב)|המתנה פעילה]] (busy waiting) כלומר, כאשר הקטע הקריטי לא סיים לרוץ, כל זמן שלא הגיע תור התהליך השני להריץ את הקטע הקריטי הוא יהיה תקוע בלולאת ה־<code>while</code> וידרוש זמן מעבד. יש להזכיר גם שניתן ליישם רעיון דומה עבור N תהליכים.


=== פתרון באמצעות סמפור ===
=== פתרון באמצעות סמפור ===
{{ערך מורחב|ערך=[[סמפור (מדעי המחשב)|סמפור]]}}
{{ערך מורחב|ערך=[[סמפור (מדעי המחשב)|סמפור]]}}
סֶמָפוֹר הוא מנגנון ל[[סנכרון (מדעי המחשב)|סנכרון]] [[תהליך (מדעי המחשב)|תהליכים]], ומטרתו לפתור את בעיית הקטע הקריטי.
סֶמָפוֹר הוא מנגנון ל[[סנכרון (מדעי המחשב)|סנכרון]] [[תהליך (מדעי המחשב)|תהליכים]], ומטרתו לפתור את בעיית הקטע הקריטי.
מנגנון הסנכרון נוצר בעזרת משתנה מונה או משתנה בינארי (בסמפור בינארי) ו[[תור (מבנה נתונים)|תור]], שניתן לבצע עליהם את הפעולות <code>{{משמאל לימין|1=signal(S)}}</code> ו- <code>{{משמאל לימין|1=wait(S)}}</code> כאשר כל אחת מהם נעשית בצורה [[פעולה אטומית|אטומית]].
מנגנון הסנכרון נוצר בעזרת משתנה מונה או משתנה בינארי (בסמפור בינארי) ו[[תור (מבנה נתונים)|תור]], שניתן לבצע עליהם את הפעולות <code>{{משמאל לימין|1=signal(S)}}</code> ו־<code>{{משמאל לימין|1=wait(S)}}</code> כאשר כל אחת מהם נעשית בצורה [[פעולה אטומית|אטומית]].


==== יישום סמפור מונה ====
==== יישום סמפור מונה ====
פעולת ה-wait (נקראת גם P), פועלת באופן הבא:
פעולת ה־wait (נקראת גם P), פועלת באופן הבא:
# חכה עד שערך המונה גדול מאפס.
# חכה עד שערך המונה גדול מאפס.
# הקטן את ערך המונה באחד.
# הקטן את ערך המונה באחד.


פעולת ה-signal (נקראת גם V),פועלת באופן הבא:
פעולת ה־signal (נקראת גם V),פועלת באופן הבא:
# קדם את המשתנה באחד.
# קדם את המשתנה באחד.


שורה 146: שורה 147:


==== שימוש בסמפור ====
==== שימוש בסמפור ====
כאשר תהליך מכיל קטע קריטי ניתן למנוע גישה למשאב המשותף על ידי אתחול ערך הסמפור ל-1, ביצוע פעולת ה-wait לפני הקטע הקריטי ופעולת signal אחריו.
כאשר תהליך מכיל קטע קריטי ניתן למנוע גישה למשאב המשותף על ידי אתחול ערך הסמפור ל־1, ביצוע פעולת ה־wait לפני הקטע הקריטי ופעולת signal אחריו.
{| style="width:40%"
{| style="width:40%"
|-
|-
שורה 164: שורה 165:
|}
|}
ניתן לראות שהשימוש בסמפור ממלא את שלושת התנאים:
ניתן לראות שהשימוש בסמפור ממלא את שלושת התנאים:
* מניעה הדדית - כאשר תהליך רוצה להיכנס לקטע הקריטי שלו, הוא מבצע פעולת wait והפעולה גורמת להקטנת ערך המונה באחד. ערכו של המונה יהיה עכשיו 0 ולכן אף תהליך אחר לא יוכל להיכנס לקטע הקריטי כי כשהוא יבצע פעולת ה-wait לפני הקטע הקריטי, הוא יוריד את ערך המונה ב-1 מה שיקבע את ערכו כשלילי ולכן התהליך יכנס לתור התהליכים שמחכים לפעול ובינתיים "ייחסם".
* מניעה הדדית כאשר תהליך רוצה להיכנס לקטע הקריטי שלו, הוא מבצע פעולת wait והפעולה גורמת להקטנת ערך המונה באחד. ערכו של המונה יהיה עכשיו 0 ולכן אף תהליך אחר לא יוכל להיכנס לקטע הקריטי כי כשהוא יבצע פעולת ה־wait לפני הקטע הקריטי, הוא יוריד את ערך המונה ב־1 מה שיקבע את ערכו כשלילי ולכן התהליך יכנס לתור התהליכים שמחכים לפעול ובינתיים "ייחסם".
* התקדמות - כאשר תהליך יוצא מהקטע הקריטי שלו הוא מבצע signal מה שמקדם את המונה ב-1. אם עד אז אף תהליך לא ניסה להיכנס לקטע הקריטי אז זה אומר שערך המונה יהיה 1 מה שיאפשר לתהליך הבא שיבצע wait לפני הקטע הקריטי לא להיחסם ולבצע את הקטע הקריטי שלו. אם היה תהליך שניסה להיכנס לקטע הקריטי בזמן שהתהליך הראשון לא סיים, ערך המונה יהיה שלילי ולכן כאשר התהליך הראשון יבצע signal אז הוא יעיר את התהליך הבא בתור.
* התקדמות כאשר תהליך יוצא מהקטע הקריטי שלו הוא מבצע signal מה שמקדם את המונה ב־1. אם עד אז אף תהליך לא ניסה להיכנס לקטע הקריטי אז זה אומר שערך המונה יהיה 1 מה שיאפשר לתהליך הבא שיבצע wait לפני הקטע הקריטי לא להיחסם ולבצע את הקטע הקריטי שלו. אם היה תהליך שניסה להיכנס לקטע הקריטי בזמן שהתהליך הראשון לא סיים, ערך המונה יהיה שלילי ולכן כאשר התהליך הראשון יבצע signal אז הוא יעיר את התהליך הבא בתור.
* המתנה מוגבלת - כמובן שקיימת המתנה מוגבלת כיוון שיש תור של התהליכים שביקשו לרוץ.
* המתנה מוגבלת קיימת המתנה מוגבלת כיוון שיש תור של התהליכים שביקשו לרוץ.
בנוסף לשלושת התנאים האלו, השימוש בסמפור מונע "המתנה פעילה" כי הוא חוסם תהליכים שכרגע לא עובדים ומעיר אותם כשמגיע תורם.
בנוסף לשלושת התנאים האלו, השימוש בסמפור מונע "המתנה פעילה" כי הוא חוסם תהליכים שכרגע לא עובדים ומעיר אותם כשמגיע תורם.


שורה 174: שורה 175:


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


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

תתכן כאן בעיה של [[הרעבה (מדעי המחשב)|הרעבת]] הכותבים כי ברגע שיהיו הרבה קוראים אז הכותב לא יצליח לגשת אל המידע כי סביר שיהיה לפחות קורא אחד שמשתמש כרגע במידע.
תתכן כאן בעיה של [[הרעבה (מדעי המחשב)|הרעבת]] הכותבים כי ברגע שיהיו הרבה קוראים אז הכותב לא יצליח לגשת אל המידע כי סביר שיהיה לפחות קורא אחד שמשתמש כרגע במידע.


שורה 191: שורה 193:


==קישורים חיצוניים==
==קישורים חיצוניים==
* [https://web.archive.org/web/20150209061750/http://codex.cs.yale.edu/avi/os-book/OS8/os8c/slide-dir/PDF-dir/ch6.pdf פרק 6] - "סנכרון תהליכים", [https://web.archive.org/web/20140917143458/http://codex.cs.yale.edu/avi/os-book/OS8/os8c/slide-dir/ מהמצגות של זילברשטץ, גלווין וגגנה]
* [https://web.archive.org/web/20150209061750/http://codex.cs.yale.edu/avi/os-book/OS8/os8c/slide-dir/PDF-dir/ch6.pdf פרק 6] "סנכרון תהליכים", [https://web.archive.org/web/20140917143458/http://codex.cs.yale.edu/avi/os-book/OS8/os8c/slide-dir/ מהמצגות של זילברשטץ, גלווין וגגנה]


==הערות שוליים==
==הערות שוליים==
שורה 197: שורה 199:


{{ביקורת עמיתים}}
{{ביקורת עמיתים}}

[[קטגוריה:תהליכים (מדעי המחשב)]]
[[קטגוריה:תהליכים (מדעי המחשב)]]

גרסה מ־22:11, 18 באוגוסט 2021

קטע קריטי הוא מושג[דרושה הבהרה] במחשבים ובפרט מתחום מערכות הפעלה אשר מתייחס למערכות מקביליות, שעושות שימוש במשאב משותף. השימוש במשאב המשותף מבלי שהמערכות מתואמות ביניהם, יכול להביא לתוצאות לא רצויות. מדען המחשב אדסחר דייקסטרה תיאר זאת במאמרו משנת 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]==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), פועלת באופן הבא:

  1. חכה עד שערך המונה גדול מאפס.
  2. הקטן את ערך המונה באחד.

פעולת ה־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 אז הוא יעיר את התהליך הבא בתור.
  • המתנה מוגבלת – קיימת המתנה מוגבלת כיוון שיש תור של התהליכים שביקשו לרוץ.

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

קיפאון

ערך מורחב – קיפאון

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

סוגים שונים של קטע קריטי

בעיית היצרן־צרכן

ערך מורחב – בעיית יצרן-צרכן

בעיית היצרן־צרכן (נקראת גם "בעיית החוצץ־המוגבל") הוא מצב שקיימים שני תהליכים כאשר אחד מהם מייצר מידע ושם אותו בחוצץ (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.
  2. ^ oracle counter semaphore