סוגי תהליכים בו זמנית: 1. עצמאיים- בלתי תלויים בהרצת תהליכים אחרים. מ"ה מקצה בזהירות משאבים ומבודדת תהליכים אחד מהשני.
2. משתפי פעולה- יכולים להשפיע או להיות מושפעים מריצת אחרים. מ"ה מאפשרת שיתוף משאבים בדרכים מסויימות ואינטרקציה ביניהם. יש משתפי פעולה באופן ישיר (החלפת מסרים) או באופן לא ישיר (שיתוף זיכרון). יתרונות שיתוף הפעולה: שיתוף מידע, העלאת זמן מיחשוב, מודולציה, נוחות. אנו נעסוק באופן הלא ישיר.
Process A Process B concurrent access
A = 1; B = 2;does not matter
A = B + 1;B = B * 2;important!
Race Condition-מס' תהליכים ניגשים ומשנים מידע משותף בו זמנית הערך הסופי של המידע המשותף תלוי בסדר הביצוע- בתהליך שסיים אחרון. Printer Spooler- כולל וקטור של תאים, כאשר בכל תא יכול להמצא קובץ להדפסה.מ"ה מחזיקה משתנה המכונה next_free_slot המורה מהו התא הפנוי הבא. כאשר תהליך מסוים רוצה להדפיס הוא בודק את ערכו של next_free_slot, מאחסן בתוכו את הקובץ המתאים ומקדם את next_free_slotבהתאם. Printer Daemon – תהליך של מ"ה הסורק כל כמה זמן את המערך ומדפיס קובץ. מקרה אפשרי-דריסת נתונים. מצב של שני תהליכים שרוצים להדפיס. האחד מסתכל על הפוינטר של התא הפנוי הבא מתבצעת פסיקה שמוציאה אותו מריצה. מכניסה תהליך אחר שמשנה את הפוינטר. כשהתהליך הראשון מוחזר הוא פועל לפי המצב שהיה לפני שהופסק שכבר השתנה מבלי שידע על כך.
האזור הקריטי- קיימים n תהליכים המתחרים על משאב (קטע) משותף. האיזור המשותף לתהליכים (קטע הקוד) הוא האיזור הקריטי, הקטע שנכנס לאזור המשותף הוא הקטע הקריטי. כדי לפתור בעיה זו נדרש: 1. Mutual Exclusion – במידה ותהליך מסוים נכנס לאיזור הקריטי תהליך אחר לא יכול להמצא בו. 2. Progress – תהליך אחד שיצא מהאזור הקריטי לא מונע מתהליך שממתין מלהיכנס לאזור.
שיטות לפתרון הבעייה:1. חומרה- ביטול פסיקות של מ"ה: כאשר תהליך נכנס לאזור הקריטי הוא מורה על ביטול פסיקות של מ"ה, כאשר הוא מסיים הוא מאפשר למ"ה לחזור ולבצע פסיקות. היתרון: פשטות ; חסרון: מסוכן מאחר ומ"ה מאבדת את השליטה. 2. משתנה נעילה: נגדיר משתנה נעילה. כאשר תהליך רוצה להיכנס לאזור הקריטי הוא בודק את ערכו של משתנה הנעילה. אם הוא לא נעול (אפס) הוא נכנס לאזור הקריטי ומשנה את ערכו של המשתנה לאחד. בסיום האיזור הקריטי הוא מחזיר את ערכו של המשתנה לאפס. לא יעיל -נוצרת אותה בעייה רק שכעת התחרות היא על משתנה הנעילה.
3. משתנה תור: כל עוד לא תור התהליך להיכנס – ממתין; ברגע שתורו להיכנס, הוא נועל את האיזור הקריטי, מעביר את התור לבא
אחריו, מבצע את הפעולה ומשחרר את האזור הקריטי. הפתרון עומד בתנאי הראשון – אין שני תהליכים שנמצאים באזור הקריטי בו"ז. אבל התנאי השני לא מתקיים. כדי שתהליך שהיה יכנס שוב לאזור הקריטי התהליך שאחריו חייב להיכנס לאזור הקריטי, במידה והוא לא יכנס גם התהליך שרוצה להיכנס לא יוכל להיכנס שוב. הפתרון מאלץ את התהליכים להיכנס לאזור הקריטי לסירוגין-לא תמיד רצוי.
4. Peterson Algorithm- אנחנו חוסמים כניסת תהליך לאזור הקריטי רק כאשר קיים תהליך אחר שמעוניין להיכנס וזה תורו של אותו תהליך. במידה וזה התור שלי או שהתור השני לא מעוניין להיכנס – אכנס לאזור הקריטי. בכך עמדנו בשני התנאים. פתרון זה לא כ"כ שימושי מאחר ובמידה ונרצה לנהל יותר משני תהליכים, צריך לדעת בדיוק כמה תהליכים ישנם ומספר זה יהיה קבוע. מסובך ויקר מדי.
5. Bakery Algorithm- כאשר תהליך רוצה להיכנס לאיזור הקריטי ניתן לו מספר (ייחודי ומונוטוני עולה), נכניס את התהליכים לאזור הקריטי לפי סדר המספרים.אלגוריתם זה עובד לכל מספר (גם לא ידוע) של תהליכים. האלגוריתם: כאשר תהליך רוצה להיכנס לאזור הקריטי הוא משנה את הchoosing שלו ל-true. הוא יקבל מספר (המספר המקסימלי שקיים +1), מערך number מחזיק את מספרים התהליכים, כעת ישנה את הchoosing שלו לfalse. לאחר קבלת המספר, עובר על כל התהליכים ומוודא שהם לא במצב של בחירת מספר. כל עוד המספר שלהם שונה מאפס (=יש להם מספר) מוודא שהמספר של כל השאר קטן משלו. במידה ואף תהליך לא מקבל כרגע מספר והתהליך הנבדק הוא הבא בתור – יכנס לאזור הקריטי. האלגוריתם מוודא שאם שני תהליכים קיבלו את אותו מספר- התהליך שהגיע קודם יכנס קודם. כאשר תהליך ירצה להיכנס שוב לאזור הקריטי – יקח מספר חדש. תהליך שלוקח מספר עוצר את כל התהליכים עד שיסיים.
6. Hardware support- יש מעבדים הכוללים את הפעולה test and set lock פעולה זו פועלת כך: קוראת תוכן של כתובת מסוימת בזכרון ושמה באוגר. מציבה באותה כתובת בזכרון ערך שונה מאפס. מכיוון שזו פעולה אטומית מובטח כי לא ניתן להפריע לפעולה זו, מכיוון שהמעבד חוסם את הגישה לזכרון עד לסיום הפעולה ובכך חוסם מתהליכים אחרים מלהפריע לפעולה. מאחר ששתי הפעולות מתבצעות ביחד זה מונע את הבעיה שכמה תהליכים יגשו לאותו זכרון בו זמנית.האלגוריתם: ניגש לכתובת בזכרון עליה נבצע את הפעולה-משתנה flag; לוקח את מה שרשום בכתובת של flag ושם באוגר שנמצא במעבד; מציב ערך שאינו 0 באותה כתובת; בודק שהערך באוגר (שנלקח מה-flag) שונה מאפס ; במידה והוא לא אפס אז מותר להיכנס לאזור הקריטי- הכתובת שפנינו אליה בהתחלה. כשתהליך יוצא מהאיזור הקריטי הוא מכניס לflag את הערך אפס. כך תהליך אחר שרוצה להיכנס לאישור הקריטי ידע שיכול.
בעיות ב-3 האלגוריתמים הנ"ל: Busy waiting – התהליך שאיננו באזור הקריטי נמצא בלולאה שחוזר על עצמה, גורם: 1. לבזבוז CPU 2. אם לתהליך הנמצא בלולאת הסרק יש עדיפות גבוהה, כל יתר התהליכים ימתינו זמן רב. פתרון: שימוש בפעולות sleep ו-wakeup על תהליכים.