הבדלים בין גרסאות בדף "קטע קריטי"

נוספו 57 בתים ,  לפני חודש
אחידות במיקום הערות שוליים
מ
(אחידות במיקום הערות שוליים)
'''קטע קריטי''' הוא מושג{{הבהרה|סיבה=מה ההגדרה של קטע קריטי?}} ב[[מחשב|מחשבים]]ים ובפרט מתחום [[מערכת הפעלה|מערכות הפעלה]] אשר מתייחס למערכות [[עיבוד מקבילי|מקביליות]], שעושות שימוש ב[[משאב מערכת|משאב]] משותף. השימוש במשאב המשותף מבלי שהמערכות מתואמות ביניהם, יכול להביא לתוצאות לא רצויות. [[מדען מחשב|מדען המחשב]] [[אדסחר דייקסטרה]] תיאר זאת במאמרו משנת 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"
!
! <span style="color: red">תהליכון ראשון</span>
|-
| שמירת התוצאה בזיכרון המשותף
|}
|
:{| class="wikitable"
!
! <span style="color: green">תהליכון שני</span>
|-
|}
|}
התוצאה שאנחנו מצפים לה היא הערך הראשוני של המשתנה, מאחר שהוספת 1 והורדת 1 משאירה את המשתנה ללא שינוי בערכו.
אולם, אם התהליכון השני ירוץ במהלך ריצת קטע הקוד הראשון, ייתכן שהתוצאה תהיה שונה כמו בדוגמת ההרצה הזאת:
:{| class="wikitable"
!
! תהליכון - מספר פקודה
! פקודה
! ערך המשתנה אחרי
|-
! 1
| <span style="color: red">ראשון - 1</span>
| <span style="color: red">קריאת המשתנה מהזיכרון המשותף</span>
| משותף = k, מקומי = k
|-
! 2
| <span style="color: red">ראשון - 2</span>
| <span style="color: red">הוספת אחד למספר</span>
| משותף = k, מקומי = k+1
|-
! 3
| <span style="color: green">שני - 1</span>
| <span style="color: green">קריאת המשתנה מהזיכרון המשותף</span>
| משותף = k, מקומי = k
|-
! 4
| <span style="color: green">שני - 2</span>
| <span style="color: green">הורדת אחד מהמספר</span>
| משותף = k, מקומי = k-1
|-
! 5
| <span style="color: red">ראשון - 3</span>
| <span style="color: red">שמירת התוצאה בזיכרון המשותף</span>
| משותף = k+1, מקומי = k+1
|-
! 6
| <span style="color: green">שני - 3</span>
| <span style="color: green">שמירת התוצאה בזיכרון המשותף</span>
| משותף = k-1, מקומי = k-1
כפי שניתן לראות, בניגוד למצופה, ערכו של המשתנה המשותף בסוף הרצת הקטע הקריטי קטן ב–1 מערכו המקורי.
 
התוצאות הלא רצויות יכולות להיווצר בזמן [[מערכת הפעלה|שמערכת ההפעלה]] שמריצה את קטעי הקוד מבצעות [[החלפת הקשר]] (באנגלית - Context switch) במהלך הרצת הקטע הקריטי או בגללמשום שהקטע הקריטי רץ במקביל לַגורם הנוסף (בעזרת [[עיבוד מקבילי]] או [[חישוב מבוזר]]). כיוון שהשליטה בתזמון בין הקטע הקריטי לגורם הנוסף, נעשית על ידי גורם שלישי - לרוב מערכת ההפעלה. נדרשים אמצעים כדי לוודא שהקוד יבצע את מטרתו.
 
== פתרון בעיית הקטע הקריטי ==
ישנם מספר גורמים שיש להקפיד עליהם כאשר ניגשים לפתרון בעיית הקטע הקריטי כדי לפתור את הבעיה ולא ליצור בעיות אחרות.
* '''[[מניעה הדדית]]''' (Mutual exclusion)- כאשר הקטע הקריטי רץ, יש למנוע שימוש במשאב המשותף על ידי גורם אחר שיכול להפריע לפעולה התקינה של הקטע הקריטי. כיוון שכך, כדאי להכניס לקטע הקריטי רק קוד שהכרחי שיהיה בו כדי שהשימוש במשאב לא יהיה חסום ללא צורך.
* '''התקדמות''' (Progress) - כאשר מונעים שימוש של גורמים נוספים במשאב, יש לוודא שלאחר שהקטע הקריטי סיים לרוץ, לא תישאר המניעה על השימוש במשאב.
* '''[[הרעבה (מדעי המחשב)|המתנה מוגבלת]]''' (Bounded Waiting) - יש לוודא שכל גורם שמבקש לרוץ, יעשה את זה תוך מספר מוגבל של קטעים קריטיים שירוצו לפניו.
 
קיימים מספר פתרונות לבעיית הקטע הקריטי. חלקם משתמשים בכלים שמערכת ההפעלה מספקת (מנעול, סמפור וכולי) וחלקם לא.
 
=== האלגוריתם של פטרסון ===
בשנת 1981 ניסח גארי פטרסון אלגוריתם לפתרון בעיית הקטע הקריטי עבור 2 [[תהליך (מדעי המחשב)|תהליכים]]\תהליכונים. האלגוריתם משתמש בשני משתנים משותפים, flag ו-turnו־turn. ערך חיובי עבור {{משמאל לימין|flag[n]}} מראה על כך שתהליך n מעוניין להיכנס לקטע הקריטי שלו. הכניסה לקטע הקריטי ניתנת לתהליך P0 אם תהליך P1 לא מעוניין להיכנס לקטע הקריטי שלו או אם P1 נתן קדימות לתהליך P0 על ידי השמת הערך 0 במשתנה turn.
 
{| style="width:70%"
|}
 
האלגוריתם של פטרסון לא משתמש בכלים מיוחדים לפתרון בעיית הקטע הקריטי אלא עושה זאת באמצעים הרגילים שעומדים בפני המתכנת ובעזרתם הוא מתמודד עם כל הגורמים שדורשים טיפול:{{ש}}
* מניעה הדדית - כאשר אחד התהליכים נמצא בקטע הקריטי שלו, לא משנה איפה תתבצע החלפת הקשר וכמה פעמים, התהליך השני לא יוכל להיכנס לקטע הקריטי שלו, כלומר לגשת למשאב המשותף בזמן שהתהליך הראשון לא סיים להשתמש בו. הסיבה לכך היא שתהליך 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>while</code> אז התהליך השני לא יוכל להריץ את הקטע הקריטי שלו יותר מפעם אחת בגללמכיוון שהוא יהיה חייב לשנות <code>turn = i</code> ו Pו־P<sub>i</sub> כבר סימן <code>flag[i] = true</code> ולכן הוא לא יעבור את ה-ה־<code>while</code> עד ש Pש־P<sub>i</sub> לא יבצע את הקטע הקריטי שלו.
 
יש לציין שהאלגוריתםהאלגוריתם עובד בשיטה של [[המתנה (מדעי המחשב)|המתנה פעילה]] (busy waiting) כלומר, כאשר הקטע הקריטי לא סיים לרוץ, כל זמן שלא הגיע תור התהליך השני להריץ את הקטע הקריטי הוא יהיה תקוע בלולאת ה-ה־<code>while</code> וידרוש זמן מעבד. יש להזכיר גם שניתן ליישם רעיון דומה עבור N תהליכים.
 
=== פתרון באמצעות סמפור ===
{{ערך מורחב|ערך=[[סמפור (מדעי המחשב)|סמפור]]}}
סֶמָפוֹר הוא מנגנון ל[[סנכרון (מדעי המחשב)|סנכרון]] [[תהליך (מדעי המחשב)|תהליכים]], ומטרתו לפתור את בעיית הקטע הקריטי.
מנגנון הסנכרון נוצר בעזרת משתנה מונה או משתנה בינארי (בסמפור בינארי) ו[[תור (מבנה נתונים)|תור]], שניתן לבצע עליהם את הפעולות <code>{{משמאל לימין|1=signal(S)}}</code> ו- ו־<code>{{משמאל לימין|1=wait(S)}}</code> כאשר כל אחת מהם נעשית בצורה [[פעולה אטומית|אטומית]].
 
==== יישום סמפור מונה ====
פעולת ה-waitה־wait (נקראת גם P), פועלת באופן הבא:
# חכה עד שערך המונה גדול מאפס.
# הקטן את ערך המונה באחד.
 
פעולת ה-signalה־signal (נקראת גם V),פועלת באופן הבא:
# קדם את המשתנה באחד.
 
 
==== שימוש בסמפור ====
כאשר תהליך מכיל קטע קריטי ניתן למנוע גישה למשאב המשותף על ידי אתחול ערך הסמפור ל-1ל־1, ביצוע פעולת ה-waitה־wait לפני הקטע הקריטי ופעולת signal אחריו.
{| style="width:40%"
|-
|}
ניתן לראות שהשימוש בסמפור ממלא את שלושת התנאים:
* מניעה הדדית - כאשר תהליך רוצה להיכנס לקטע הקריטי שלו, הוא מבצע פעולת wait והפעולה גורמת להקטנת ערך המונה באחד. ערכו של המונה יהיה עכשיו 0 ולכן אף תהליך אחר לא יוכל להיכנס לקטע הקריטי כי כשהוא יבצע פעולת ה-waitה־wait לפני הקטע הקריטי, הוא יוריד את ערך המונה ב-1ב־1 מה שיקבע את ערכו כשלילי ולכן התהליך יכנס לתור התהליכים שמחכים לפעול ובינתיים "ייחסם".
* התקדמות - כאשר תהליך יוצא מהקטע הקריטי שלו הוא מבצע signal מה שמקדם את המונה ב-1ב־1. אם עד אז אף תהליך לא ניסה להיכנס לקטע הקריטי אז זה אומר שערך המונה יהיה 1 מה שיאפשר לתהליך הבא שיבצע wait לפני הקטע הקריטי לא להיחסם ולבצע את הקטע הקריטי שלו. אם היה תהליך שניסה להיכנס לקטע הקריטי בזמן שהתהליך הראשון לא סיים, ערך המונה יהיה שלילי ולכן כאשר התהליך הראשון יבצע signal אז הוא יעיר את התהליך הבא בתור.
* המתנה מוגבלת - כמובן שקיימתקיימת המתנה מוגבלת כיוון שיש תור של התהליכים שביקשו לרוץ.
בנוסף לשלושת התנאים האלו, השימוש בסמפור מונע "המתנה פעילה" כי הוא חוסם תהליכים שכרגע לא עובדים ומעיר אותם כשמגיע תורם.
 
 
== סוגים שונים של קטע קריטי ==
=== בעיית היצרן-צרכןהיצרן־צרכן ===
{{ערך מורחב|בעיית יצרן-צרכן}}
בעיית היצרן-צרכןהיצרן־צרכן (נקראת גם "בעיית החוצץ-המוגבלהחוצץ־המוגבל") הוא מצב שקיימים שני תהליכים כאשר אחד מהם מייצר מידע ושם אותו ב[[חוצץ|בחוצץ]] (buffer) בעל גודל מוגבל והתהליך השני שולף אותו מהחוצץ ומשתמש בו. החוצץ הוא משאב משותף והיצרן והצרכן לא יכולים לגשת אליו בו זמנית כדי שלא יתקבל מידע פגום. הבעיה היא שהיצרן יכול לשים בחוצץ כמות מוגבלת של מידע ואילו הצרכן יכול לצרוך רק כאשר קיים מידע בחוצץ.
כדי לפתור את הבעיה הזאת יש להשתמש בפתרון שלא יאפשר גישה למידע בזמן שאחד התהליכים עדיין משתמש בו ובנוסף שלא ייווצר קיפאון כשהיצרן מנסה לייצר יותר מידע ממה שהחוצץ יכול להכיל וכשהצרכן מנסה לצרוך מידע כאשר החוצץ ריק.
 
=== בעיית הקוראים-כותביםהקוראים־כותבים ===
{{ערך מורחב|בעיית הקוראים כותבים}}
בעיית הקוראים כותבים נוצרת כאשר יש מידע ושני סוגי תהליכים שנגשים למידע. תהליך קורא - קורא את המידע מבלי לשנות אותו. תהליך כותב - יכול לקרוא את המידע וגם לשנות אותו. כאשר הכותב ניגש למידע אז אסור לשום תהליך אחר לגשת למידע במקביל כדי שלא יתקבל מידע שגוי. כאשר הקורא ניגש למידע אז ניתן לאפשר גם לקוראים אחרים לגשת למידע והקריאה לא מהווה קטע קריטי ביחס לקוראים אחרים.
 
תתכן כאן בעיה של [[הרעבה (מדעי המחשב)|הרעבת]] הכותבים כי ברגע שיהיו הרבה קוראים אז הכותב לא יצליח לגשת אל המידע כי סביר שיהיה לפחות קורא אחד שמשתמש כרגע במידע.
 
 
==קישורים חיצוניים==
* [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/ מהמצגות של זילברשטץ, גלווין וגגנה]
 
==הערות שוליים==
 
{{ביקורת עמיתים}}
 
[[קטגוריה:תהליכים (מדעי המחשב)]]