מערכות הפעלה - חלק 2

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

  1. תהליכים (Processes)
  2. תהליכונים (Threads)
  3. תקשורת בין תהליכים
  4. תזמון תהליכים
  5. בעיות IPC קלאסיות
  6. סיכום

 

1. תהליכים (Processes)

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

תהליך כלשהו יכול להיות אך ורק באחד משלושת המצבים: ‘מצב חסום’, ‘מצב מוכן לריצה’, מצב ריצה’. ובמצב ריצה יכול להיות רק תהליך אחד בכל זמן נתון.

 

מבנה המעבד בקצרה:

Interrupt Processor

אוגרים מהווים סוג של זיכרון קטן, אך מהיר, המשמש לצמצום מספר הפניות לזיכרון הראשי ולצורך בקרה על פעולות המעבד. בין אוגרי הזיכרון נמצאים data registers (היכולים לשמש מתכנתים למטרות שונות. לדוג’, בשפת C אפשר להציע למהדר (compiler) לשמור משתנה באוגר (במקום בזיכרון הרגיל) על ידי המילה השמורה register בזמן הצהרת המשתנה), ו address registers (שומרים כתובת של הוראות מכונה או של data). לקבוצה של אוגרי הבקרה שייכים בין השאר PC (ראשי תיבות: program counter), ה IR (ראשי תיבות: instruction register), וה PSW (ראשי תיבות: program status word).

הכתובת של ההוראה הבאה מחזקת באוגר בשם program counter, לאחר ביצוע ההוראה הנוכחית, המעבד מעדכן את ה program counter ומורה לו להצביע לכתובת של ההוראה הבאה (הבאה שאחריו). לאחר מכן, המעבד שולף את ההוראה ומאכסן אותה באוגר בשם instruction register (שם הוא מחזיק את ההוראה הנוכחית, שמתבצעת). ולבסוף המעבד מפרש את ההוראה (לפי קוד ההוראה) ומבצע אותה.

באוגר PSW מוחזקת סיבית המידע המציינת אם המעבד נמצא במצב מיוחס (kernel mode) או במצב משתמש (user mode), ובמעבדים מסויימים יש יותר מסיבית אחת המשמשת למטרה זו (כדי לאפשר יותר רמות אבטחה שונות).

 

פסיקות חומרה נועדו, בעיקר, להגדיל את ניצולת ה CPU. למשל, בעת ביצוע I/O. תוכנית שמבקשת לבצע I/O, קריאה או כתיבה, מושהית ע”י מערכת ההפעלה עד לסיום פעולת ה I/O. בזמן ההשהיה תתבצע תכנית אחרת ב CPU. כאשר ההתקן שעליו התבצעה פעולת ה I/O יסיים את המשימה, יישלח סיגנל (signal) בקשה לפסיקה ל CPU. עם קבלת הסיגנל, המעבד משהה מיד את הביצוע של ההוראות שהוא מבצע כעת, ומפעיל שגרה מיוחדת הנקראת ‘שגרה לטיפול בפסיקות’ (או interrupt handler routine). השגרה לטיפול בפסיקות היא בדרך כלל חלק ממערכת ההפעלה. לאחר סיום השגרה לטיפול בפסיקות, ה CPU יכול לחזור לביצוע של התכנית המקורית שביצע לפי שקיבל את הסיגנל (למרות שייתכן והעניינים יתנהלו לפי תסריט אחר. השגרה לטיפול בפסיקות יכולה להורות להפעיל מתזמן תהליכים שיכול “לתת” את ה CPU לתכנית אחרת).

המעבר הזה, לביצוע של השגרה לטיפול בפסיקות, יוצר תקורה, מכיוון שצריך לבצע שמירת תוכן של התהליך על מנת לאפשר שחזור של ביצוע התוכנית מהנקודה שבה הופסקה. שמירת התוכן מתבצעת ע”י החומרה ותלויה במעבד (שלב 6 באיור משמאל). שמירת ה PSW וה PC מתבצעת גם ע”י המעבד עצמו (שלב 4) אשר קורא לשגרה לטיפול בפסיקות (בשלב 5). תהליך השמירה עצמו מתואר בצורה סכמתית באיור משמאל (בעקבות ריבוי הארכיטקטורות השונות של המעבד, ייתכנו גם אפשרויות נוספות).

 

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

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

 

מבוא לתהליכים:

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

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

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

 

בכל מערכת הפעלה קיימים מספר מקרים שבהם אפשר או צריך ליצור תהליכים חדשים:

  1. בעת האתחול של מערכת ההפעלה נוצרים תהליכים שמטרתם לבצע משימות עבור מערכת ההפעלה. תהליכי רקע (daemons) כגון שרת web או spooler של מדפסת.
  2. תהליכים קיימים יכולים ליצור תהליכים חדשים. המטרה יכולה להיות שיפור המודולריות של תוכנית או ניצול של ריבוי מעבדים לשיפור המקביליות.
  3. עבודות אצווה - מערכת ההפעלה מקבלת דרך ה batch control stream את ההוראות ויוצרת תהליכים חדשים לפיהם. ניתן לראות צורה זו של יצירת תהליכים במחשבי Mainframe כאשר משתמשים רבים מגישים עבודות אצווה כגון indexing של בסיסי נתונים.

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

  1. סיום רגיל - תהליך שמסתיים בעקבות סיום של תוכנית ומפה את המשאבים שתפס.
  2. סיום בעקבות שגיאה - סיום מתוכנן של תהליך בעקבות שגיאה במהלך ריצה.
  3. סיום בעקבות שגיאטה פטאלית - תהליך שמסתיים בעקבות שגיאה שלא נצפתה מראש ולא היה קיים מענה לתרחיש בעייתי בקוד התוכנית. סיום מסוג זה גורם לקריסה של התוכנית (crash).
  4. סיום בעקבות הריגת תהליך - תהליך שמתסיים בעקבות הבקשה המפורשת ממערכת ההפעלה לסיים את ריצתו. מערכת ההפעלה שמקבלת בקשה כזאת בוחנת את הרשאות המבקש (המבקש יכול להיות תהליך אחר, ובפרט תהליך של מערכת ההפעלה עצמה), ואם קיימות הרשאות מתאימות, היא מסיימת את ריצתו של התהליך המבוקש.
Finite-state Machine

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

  1. התהליך חסום לקלט.
  2. המתזמן בוחר תהליך אחר.
  3. המתזמן בוחר את התהליך הזה.
  4. הקלט הופך לזמין.

המעבר ממצב Running למצב Blocked מתבצע כאשר התהליך אינו יכול עוד להתקדם. תהליך במצב חסום יחכה לאירוע חיצוני שיגרום לו להשתחרר מהחסימה (לדוג’ תהליך שמבקש לקרוא קובץ מהדיסק הקשיח - I/O, יכול להיחסם ע”י מערכת ההפעלה עד אשר תתבצע קריאת הקובץ. עם קריאת הקובץ, ישלח בקר הדיסק הקשיח בקשה לפסיקה אשר תביא לשחרור התהליך ממצב Blocked).

המעבר ממצב Blocked למצב Ready יתבצע כאשר מתרחש האירוע החיצוני אשר בגללו התהליך מחכה במצב Blocked. (לדוג’ כאשר בקר הדיסק הקשיח ישלח בקשה לפסיקה, הפסיקה מטופלת ע”י מערכת ההפעלה שגורמת לשינוי של מצב התהליך והפעלת מתזמן המערכת). המעברים ממצב Running למצב Ready ולהיפך מתרחשים כתוצאה מהחלטת מתזמן המערכת להפקיע את ה CPU מתהליך רץ ולהקצותו לאחד התהליכים הממתין לו במצב Ready.

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

 

המבנים הדרושים למימוש המודל

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

כל מערכת הפעלה מנהלת מבני נתונים רבים כדי לאפשר החלפת תהליכים וכדי לאפשר קיום מעברים בין מצב משתמש (user mode) למצב מיוחס (kernel mode). אז כיצד מתבצע הקוד של מערכת ההפעלה? (האם המערכת היא אוסף של תהליכים? או אולי היא חלק מתהליכי המשתמש?) השאלות האלו מגדירות גישות שונות (גישת השרת – לקוח עליה דיברנו בפוסט הראשון ממומשת כאוסף של תהליכים. לעומת זאת מערכות הפעלה במחשבים ביתיים רצות במרחב הכתובות של תהליכי המשתמש).

CPU Utilization

כמו שאמרנו, העלאת רמת המקביליות של המערכת מביאה לניצול טוב יותר של המשאבים. נניח שתהליך מבלה חלק מזמנו בפעולת קלט / פלט (ז”א 0 < p וגם 1 > p). כאשר n תהליכים נמצאים בזיכרון בבת אחת, ההסתברות לכך שכל התהליכים מבצעים פעולת קלט / פלט היא p^n (בהנחה שהתהליכים אינם תלויים זה בזה). בתנאים אלה, ההסתברות לכך שהמעבד פעיל היא 1 פחות p^n (וזאת הנוסחה לחישוב הניצולת של המעבד).

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

 

2. תהליכונים (Threads)

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

במערכת הפעלה שתומכת בתהליכונים, יש לכל תהליך במערכת מרחב זיכרון מדומה משלו, וכל תהליך כזה מחזיק במשאבים שהוקצו לו ע”י מערכת ההפעלה. בכל תהליך יכולים להימצא מס’ תהליכונים, ולכל אחד מהם יש את המאפיינים:

  • מצב התהליכון (Running, Ready, Blocked).
  • מצב הרגיסטרים (Registers) של המעבד.
  • מחסנית (Stack) נפרדת עבור כל תהליכון.
  • אפשרות גישה לזיכרון ולמשאבים המשותפים בתוך התהליך.

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

בסופו של דבר, מודל התהליכונים הינו הרחבה של מודל התהליכים. היתרונות שמספק המודל מורחב הם:

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

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

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

 

מימוש תהליכונים

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

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

יתרונות השיטה:

  • החלפת תהליכונים ברמת המשתמש איננה דורשת מעבר למצב ראשוני, כפי שנדרש בהחלפת תהליכים. להבדיל מהחלפת תהליכים שדורשת את הפעלת המתזמן (scheduler) של מערכת ההפעלה, בעוד החלפת תהליכונים מתבצעת ע”י המתזמן שנמצא במרחב הזיכרון של התהליך המארח.
  • שימוש ברמת משתמש מאפשר את התאמת אלוגריתם התזמון של ספריית התהליכונים לצרכים של כל יישום בנפרד.
  • חבילת תוכנה שממשת תהליכונים ברמת המשתמש יכולה לרוץ ללא שום תמיכה מצד גרעין המערכת (kernel), ולכן זה נותן אפשרות לממש אפליקציות העושות שימוש בתהליכונים גם במערכת הפעלה שאינן תומכות בתהליכונים.

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

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

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

 

3. תקשורת בין תהליכים

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

 

מירוץ קריטי

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

deleteFirst(){
   //TmpNodePtr is a local variable, ListHeadPtr is global
    Node * TmpNodePtr=ListHeadPtr;
    ListHeadPtr=TmpHeadPtr-&gt;next;
    delete(TmpNodePtr(;
}
Critical Race

התוצאה הרצויה היא ששני התהליכונים ימחקו מראש הרשימה שני איברים ראשונים. אך נניח שבתור ישנם ארבעה עצמים. תהליכון 1 מגיע לפרוצדורה ()deleteFirst ומבצע את השורה הראשונה. לאחר ביצוע השורה, מתרחשת החלפת תהליכונים ותהליכון 2 מגיע לפונ’ ()deleteFirst שלו ומבצע גם כן את השורה הראשונה. נניח שהתלהיכונים ממשיכים להתחלף כל שורה. באיור משמאל (חלק b) ניתן לראות מה מתרחש בתור לאחר שהתהליכונים ביצעו את השורה השנייה. ובחלק האחרון, c, ניתן לראות כי לאחר שהתהליכונים סיימו לבצע (כל אחד את העותק שלו של ()deleteFirst. הרי לכל תהליכון יש מחסנית נפרדת, ולכן עותקים נפרדים של הפרוצדורה רצים במקביל, המשתנה TmpNodePtr הוא משתנה מקומי ולכן בתמונה משמאל אנו רואים 2 כאלו -עותקים נפרדים שלו יפיעו בכל מחסנית. המשתנה ListNodePtr הוא משתנה גלובלי בספרייה ולכן הוא משותף לשני התהליכונים), רק איבר אחד נמחק מהרשימה.

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

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

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

  • שני תהליכים לא ישהו בו זמנית בתוך קטע קריטי.
  • הפתרון לא יסתמך על השערות הקשורות למהירות או למס’ מעבדים.
  • תהליך מחוץ לקטע קריטי לא ימנע מתהליך אחר להיכנס לקטע קריטי.
  • תהליך לא ימתין לנצח כדי להיכנס לקטע קריטי (בעיית הרעבה).

 

מניעת הפסיקות

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

אך לשיטה יש כמה חסרונות מהותיים:

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

לכן, נראה שלא סביר להשתמש בשיטה זו עבור תהליכי משתמש.

 

משתני נעילה – Lock Variables

נניח שיש לנו משתנה משותף, lock, מאותחל ל 0. והפתרון המוצע הוא כזה:

while(true){
    ... // non critical section
    while (lock == 1)
        ; // loop
    lock = 1;
    CriticalSection();
    lock = 0;
    ... // non critical section
}

כאשר תהליך מנסה להיכנס לקטע הקריטי הוא בודק תחילה האם המשתנה lock, המשותף, שווה ל-1 ז”א נעול. אם המנעול הוא 0 (ז”א לא נעול) הוא משנה אותו ל-1 ונכנס לקטע הקריטי. ואם הוא כבר נעול (ז”א 1) התהליך ימתין עד אשר ערך המנעול ישתנה חזרה ל-0.

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

 

פתרון התור

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

while(true){
    ... // non critical section
    while (turn != 0)
        ; // loop
    CriticalSection_0();
    turn = 1;
    ... // non critical section
}

הקוד לתהליך 1:

while(true){
    ... // non critical section
    while (turn != 1)
        ; // loop
    CriticalSection_1();
    turn = 0;
    ... // non critical section
}

אך פתרון זה אינוו פתרון סביר מכיוון שהוא מפר את אחד מארבעת התנאים שהזכרנו למעלה (“תהליך מחוץ לקטע קריטי לא ימנע מהתליך אחר להיכנס לקטע הקריטי”). כי כמו שניתן לראות, המשתנה המשותף, turn, מאותחל ל-0 בהתחלה וערכו משקף את מס’ התהליך שתורו להיכנס לקטע הקריטי. בהתחלה תהליך 0 בודק את turn ונכנס לקטע קריטי. תהליך 1 בודק את turn ומכיוון שהוא שונה מ-1 הוא נכנס לולאה עד שהערך של turn משתנה ל-1. תהליך 1 בנתיים נמצאה במצב המכונה המתנה פעילה (Busy Waiting), מצב בו תהליך מקבל את המעבד ומנצל את מלוא הזמן המוקצב לו, איך איננו מתקדם כלל. אם ההמתנה נמשכת זמן רב נוצרת תופעת ההרעבה (Starvation), בה התהליך השני אינו מקבל זמן מעבד.

אם נחזור לדוג’, כאשר תהליך 0 עוזב את הקטע הקריטי ומשנה את turn ל-1, נשים לב שעכשיו תהליך 0 אינו יכול להיכנס שוב לקטע הקריטי עד שתהליך 1 לא יאפשר זאת ע”י שינוי ערכו של turn (תנאי 3).

 

הפתרוונת של דקר ופטרסון

ב 1965 הציע המתמטיקאי דקר (Dekker) פתרון ששילב במובן מסוים את פתרון התור והפתרון באמצעות משתנה נעילה. הפתרון דורש 2 משתני נעילה ומשתנה תור אחד, כאשר כולם משותפים לשני התהליכים. אך ב 1981 הוצע ע”י פטרסון (Peterson) פתרון קצת יותר אלגנטי ופשוט, שגם דורש 3 משתנים משותפים. להלן הפתרון של פטרסון:

המשתנים:

boolean interested[2];
in turn;
interested[0] = interested[1] = FALSE;
turn = 1;

הקוד של תהליך 0:

while (TRUE){
    ... // non critical section
    interested[0] = TRUE;
    turn = 0;
    while(interested[1] == TRUE && turn == 0){
        ; // loop
    }
    CriticalSection_0();
    interested[0] = FALSE;
    ... // non critical section
}

הקוד של תהליך 1:

while (TRUE){
    ... // non critical section
    interested[1] = TRUE;
    turn = 1;
    while(interested[0] == TRUE && turn == 1){
        ; // loop
    }
    CriticalSection_1();
    interested[1] = FALSE;
    ... // non critical section
}

התהליכים מצהירים, ע”י שינוי התא במערך interested בשורה 3, על רצונם להיכנס לקטע הקריטי. הבדיקה בשורה 5 בודקת האם התהליך השני מעוניין להיכנס והאם זה תורו של התהליך הנוכחי (turn), ואם התהליך השני מעוניין להיכנס אז התהליך הנוכחי נכנס ללולאה. לכן פתרון זה נקרא גם הפתרון הנדיב, מכיוון שאם התהליך השני הצהיר כי הוא מעוניין להיכנס לקטע הקריטי, התהליך הנוכחי יתנדב להמתין.

 

TSL

ניזכר כי בסעיף של מניעת פסיקות, השימוש בביטול הפסיקות היה תקף רק למעבד אחד, כשיש מס’ מעבדים המעבד חייב להציע מספר הוראות שחייבות להיות אטומיות (הוראה המתבצעת כצעד אחד שלא ניתן להפרידו לשלבים, על מנת שהמערכת לא תוכל להעביר את משאבי המעבד באמצע ההוראה). דוגמה להוראה כזאת היא TSL (ראשי תיבות של Test and Set Lock). נציין בנוסף, כי ביצוע של הוראת TSL נועל את ערוץ הזיכרון (memory bus) למשך זמן הביצוע של ההוראה, מה שפותר את בעית המירוץ במחשבים אלו.

הקוד של תהליך 0:

while(TRUE){
    ... // non critical section
    while (TSL (lock) != 0)
        ; // loop
    CriticalSection_0();
    lock = 0;
    ... // non critical section
}

הקוד של תהליך 1:

while(TRUE){
    ... // non critical section
    while (TSL (lock) != 0)
        ; // loop
    CriticalSection_1();
    lock = 0;
    ... // non critical section
}

נשים לב רק שהפתרון באמצעות הוראת TSL משתמש במשתנה זיכרון משותף בשם lock.

הפסאודו קוד של הוראת TSL נראה כך:

int TSL (int lock){
    if (lock == 0){
        lock = 1;
        return 0;
    }
    return lock;
}

אם שני תהליכים מעוניינים להיכנס לקטע הקריטי, אז הראשון שייכנס יהיה זה שקרא ראשון ל TSL. לאחר סיום של קטע קריטי התהליך פשוט מציב ב lock ערך 0 ובכך משחרר את המנעול. במקרה של 2 תהליכים הפתרון עובד, אך הפתרון הנל אינו מסדיר את אופן הכניסה של תהליכים שרצו להיכנס לקטע הקריטי ולא יכלו לעשות זאת מכיוון שהקטע היה תפוס. אותם תהליכים מטופלים ע”י המתזמן תהליכים כתהליכים מהשורה והמתזמן אינו יודע על רצונם להיכנס לקטע הקריטי. לכן יכול לקרות מצב שבו תהליך יורעב – כלומר לא יצליח להיכנס לקטע הקריטי במשך פרק זמן ארוך.

 

הרדמה והערה

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

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

 

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

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

#define N 100     /* number of slots in the buffer */
int count = 0;    /* number of items in the buffer */

void producer(void)
{
  int item;

  while (TRUE) {                      /* repeat forever */
    item = produce_item();            /* generate next item */
    if (count == N) sleep();          /* if buffer is full, go to sleep */
    insert_item(item);                /* put item in buffer */
    count = count + 1;                /* increment count of item in buffer */
    if (count == 1) wakeup(consumer); /* was buffer empty? */
  }
}

void consumer(void)
{
  int item;

  while (TRUE) {                          /* repeat forever */
    if (count == 0) sleep();              /* if buffer is empty, go to sleep */
    item = remove_item();                 /* take item out of buffer */
    count = count - 1;                    /* decrement count of items in buffer */
    if (count == N -1) wakeup(producer);  /* was buffer full? */
    consume_item(item);                   /* print item */
  }
}

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

הצרכן מצדו הולך לישון כאשר הוא מגלה ש count שווה ל 0. אחרת הוא מפנה פריטים מהמאגר ודואג להעיר את היצרן אם יש מקום פנוי במאגר. הפרימיטיבם SLEEP ו WAKEUP אכן מונעים את בעיית ההמתנה הפעילה. אך הפתרון בכל זאת סובל מבעיית מירוץ (מצב זה יכול לקרות מכיוון שהגישה למשתנה של המונה אינה מבוקרת ולכן עקב המרוץ שנוצר על המשתנה, יתכן שאחת מהקריאות של WAKEUP תאבד).

 

Semaphores

בשנת 1965 הציע דייקסטרה (Dijkstra) להשתמש במשתנה מיוחד, s, שישמש כמונה של מספר כלשהו של WAKEUP וגם יבדוק אם תהליך אחד התעורר. הוא הציע שתי פעולות, up ו down (אשר מהוות הכללה של SLEEP ו WAKEUP שתיארנו למעלה), הפעולות על המשתנה המיוחד שמסוגל למנות את מספר ה WAKEUPS:

down(s){
    if (s == 0)
        // place the process on the semaphore queue and move it to the block state;
    if (s &gt; 0)
        s--;
}

up(s){
    if (there is at least one process sleeping in the semaphore queue){
        wake him up;
        return;
    }
    s++;
}

המשתנה המיוחד s  מכונה סמפור (באנגלית: Semaphore). סמפור איננו משתנה רגיל אלא מנגנון מיוחד המסופק ע”י מערכת הפעלה או שפת תכנות. המנגנון משתמש בתור (queue) המנהל את התהליכים הממתינים על הסמפור במצב רדום (כך ניתן לדעת אם תהליך שאמור היה להתעורר אכן עשה זאת). נשים לב כי ערך אתחול הסמפור משמש לקביעה של מספר התהליכים שיכולים להיות ערים באותו הסמפור. ונציין גם כי פעולות ה up וה down חייבות להיות אטומיות (אחרת, יכולים להיווצר מצבי מירוץ בעת עדכון התור של תהליכים הממתינים על הסמפור). להלן הקוד שפותר את בעיית המניעה ההדדית ע”י שימוש פשוט ביותר בסמפור (נאתחל סמפור S בעל ערך 1).

תהליך 0:

while (TRUE) {
    ... // non critical section;
    down(S);
    critical_section_0();
    up(S);
    ... // non critical section;
}

תהליך 1:

while (TRUE) {
    ... // non critical section;
    down(S);
    critical_section_1();
    up(S);
    ... // non critical section;
}

סמפורים המאותחלים תמיד בערך 1 נקראים סמפורים בינאריים והם מספקים מניעה הדדית למספר שרירותי של תהליכים שרצים במעבד אחד (סמפורים שמאותחלים לערך שונה מ 1 מכונים לעיתים סמפורים כלליים).

אם נשתמש ב-3 סמפורים (שניים מהם משמשים לסנכרון, והשלישי משמש להגנה על קטע קריטי), נפתור את בעיית היצרן-צרכן. סמפור בשם full ימנה את מס’ המקומות במאגר שכבר תפוסים ע”י הפריטים, סמפור empty מונה את מס’ המקומות הפנויים במאגר, וסמפור בינארי mutex משמש למניעה הדדית כדי שהיצרן והצרכן לא יכנסו למירוץ בעץ העדכון של המאגר ושאר הנתונים המשותפים (סמפור full יאותחל ל 0, סמפור empty יאותחל ל N – מס’ המקומות הפנויים במאגר, והסמפור הבינארי mutex יאותחל ל 1).

 

מנעולים

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

 

מבני פיקוח – Monitors

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

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

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

  • פעולת (signal(c מעירה אחד מהתהליכים שהיה חסום ע”י מבנה פיקוח על התנאי c.
  • פעולת (wait(c גורמת להשהיית תהליך כל עוד התנאי c לא יתקיים. מבנה פיקוח מבטיח שלאחר הקריאה ל wait אחד מהתהליכים שהיה חסום על קטע קריטי יוכל להיכנס אליו.

לדוג’ בבעית היצרן-צרכן נשתמש בשני מתשנים בשם full ו empty כדי לבצע סנכרון. המשתנה full יסמל כי המאגר מלא, והמשתנה empty מסמל כי המאגר ריק. הפונ’ insert  שמופעלת ע”י היצרן מבצעת קריאה ל (wait(full כאשר מתגלה שאין עוד מקום לאכסון פריטים והדבר משהה כמובן את תהליך היצרן (השימוש במבנה פיקוח פוטר אותנו מהצורך לשחרר את הנעילה על הקטע הקריטי).

הפונ’ (signal(empty מופעלת ע”י היצרן לאחר שיצר פריט והכניסו למחסן אשר היה ריק לפני כן. הפעלת הפונ’ מעירה את הצרכן שהיה רדום עקב המחסור בפריטים במחסן (שימו לב כי היצרן יעיר את תהליך הצרכן רק כאשר (בשורה בקוד) סיים לעדכן את המאגר ונמצא בסיומו של הקטע הקריטי).

כדי להימנע משני תהליכים פעילים בתוך מבנה פיקוח, אפשר לנקוט בגישות האלה:

  • לתת לתהליך ש (signal(c העיר אותו לרוץ, תוך כדי השהיה של תהליך שקרא ל signal.
  • לתת לתהליך שקרא ל (signal(c לסיים את הפונ’ של מבנה הפיקוח ורק אז להעיר את אחד התהליכים שממתינים על c.
  • לדרוש, ברמת התחביר של שפת התכנות, שהקריאה ל (signal(c תתבצע רק בסוף הפונ’ של מבנה הפיקוח.

  • יש לציין כי להבדיל מסמפורים שמשמים כמונים. condition variables אינם זוכרים את כמות הפעמים שנקרא signal עליהם. בנוסף, נזכור שמבני פיקוח, בדיוק כמו סמפורים, הם מנגנונים שפועלים בארכיטקטורה של מעבד אחד עם זיכרון אחד, או מס’ מעבדים בעלי זיכרון משותף.

 

העברת הודעות (Message Passing)

שיטת העברת הודעות מספקת שני פרימיטיבים, send ו receive, המשמשים לשליחה וקבלה של הודעות.

  • הפונ’ (send(destination, &message שולחת את ההודעה message ליעד נתון.
  • הפונ’ (receive(source, &message מקבלת הודעה ממקור נתון.

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

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

להלן פתרון של בעיית המניעה ההדדית באמצעות העברת הודעות בשיטת מיעון עקיף:

תהליך 0:

meesage msg;
while (true){
	... // non critical section
	receive(message_box, msg);
	CriticalSection_0();
	send(message_box, msg);
	... // non critical section
}

תהליך 1:

meesage msg;
while (true){
	... // non critical section
	receive(message_box, msg);
	CriticalSection_1();
	send(message_box, msg);
	... // non critical section
}

מבנה ראשי:

main(){
	message token;
	SetUpMessageBox(message_box);	// create mailbox named message_box
	PutMessage(message_boxm token);	// send token to message_box
	CreateAndShedulePeocesses(P1, P2);
}

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

 

4. תזמון תהליכים

תזמון תהליכים הוא נושא מורכב מאוד ויש לו השפעה על כל מרכיבי המערכת (ניהול זיכרון, מערכת קבצים וכ’ו). במהלך הסעיף הנל נתמקד באלוגריתמים לתזמון תהליכים שנמצאים במצב מוכן לריצה (ז”א בהינתן קבוצה של תהליכים מוכנים לריצה, המשימה תיהיה לבחור מתוכה איזה מן התהליכים יהיה התהליך הבא שמקבל זמן CPU ומתי תהליך שרץ ב CPU עובר למצב מוכן, ז”א במעברים בין מצב Ready למצב Running). אלוגריתמים אלה נקראים אלוגריתמי תזמון לטווח קצר (Short-time Scheduling Algorithms) ונראה בהמשך כיצד הם משתלבים במנגון התזמון שלוקח החלטות תזמון לטווח ארוך.

 

קריטריונים להערכה של אלוגריתמי תזמון לזמן קצר

כדי קבוע מדד לטיב התזמון לטווח קצר, הונהגו הקריטריונים האלה בכל סוגי המערכות:

  • הגינות (Fairness) – דאגה לכך שכל תהליך יקבל אותו זמן CPU.
  • אכיפת מדיניות (Policy Enforcement) – אפשרות לקבוע מדיניות לקבוצות שונות של תהליכים שנמצאים במצב מוכן לריצה (פעמים רבות קיימת קבוצה של תהליכים שחשוב להריץ אותם לפני תהליכים אחרים).
  • איזון (Balance) – איזון עומסים בין מעבדים.

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

  • קצב עבודה (Throughput) – כמות התהליכים שמסיימים ביחידת זמן (חשוב לבחור באלוג’ תזמון בעל קצב עבודה גבוה).
  • זמן השהייה (Turnaround Time) – הזמן שחלף מהרגע שהתהליך התקבל למערכת ועד הרגע שסיים לרוץ (אלוג’ תזמון טוב ממזער את זמן השהייה הממוצע של התהליכים).
  • ניצולת המעבד (CPU Utilization) – האלוג’ צריך לדאוג לכך שהמעבד יהיה עסוק רוב הזמן.

במערכות אינטראקטיביות:

  • זמן תגובה (Response Time) – ממוצע הזמנים שחלפו מרגע מתן הפקודה (כגון לחיצת כפתור העכבר או הקלדה במקלדת) ועד לקבלת התגובה הראשונה (האלוג’ צריך לשאוף להביא את זמן התגובה למינימום).
  • יחסיות (Proportionality) – ההגדרה של זמן תגובה טוב הינו יחסי בין משימות אינטראקטיביות שונות.

במערכות בזמן אמת:

  • עמידה בזמנים (Meeting Deadlines) – במערכות זמן אמת זהו אחד הקריטריונים החשובים ביותר (לדוג’ מערכת מחשב במטוס קרב שצריכה לבצע תמרון נגד יירוט).
  • ניתנות לחיזוי (Predictability) – מדד למשימות זמן אמת עם אילוצים פחות נוקשים מהדוג’ למעלה. למשל, בשיחת סקייפ חשוב להשיג העברה רציפה של האודיו גם על חשבון משימת ההעברה הרציפה של הווידיאו (קפיצה של פריים אחד בווידיאו אינה קריטית כמו קפיצה של האודיו).

 

תזמון במערכות אצווה (Batch)

האלוגריתם הראשון לתזמון לזמן קצר במערכות אצווה נקרא FCFS (ראשי תיבות של First-Come First-Served), ומכונה לעיתים FIFO (ראשי תיבות של First In First Out). המתזמן מנהל תור של תהליכים מוכנים לריצה. כאשר תהליך שרץ ב CPU מבצע קריאת מערכת שגורמת לחסימה, המתזמן מקצה את ה CPU להתליך הבא בתור. כאשר התהליך חוזר ממצב רדום, הוא מוכנס לסוף התור. היתרון של האלוגריתם הוא כמובן בפשטות המימוש שלו. אך החיסרון שלו הוא זמן השהייה הארוך שלו בתהליכים עתירי קלט / פלט, אם במערכת קיימים הרבה תהליכים עתירי חישוב.

האלוגריתם השני נקרא SJF (ראשי תיבות של Shortest Job First), והוא יכול להתגבר על החיסרון של FSFC בתנאי שזמני הריצה של התהליכים ידועים מראש ושמפעילים אותו על קבוצה של תהליכים שנקבעו מראש. האלוג’ בוחר לתת זמן CPU לתהליך בעל זמן הריצה הקצר ביותר ומריץ אותו עד לסיום. 

נחשב את 2 האלוגריתמים: נניח שהמחשב שלנו מקבל 4 תהליכים, כאשר תהליך A דורש 8 יחידות זמן, תהליך B דורש 4 יח’ זמן, תהליך C דורש 4 יח’ זמן, ותהליך D דורש 4 יח’ זמן. ומנגד נניח שהמחשב שלנו שוב מקבל 4 תהליכים, כאשר הפעם הסדר שבו הוא מקבל אותם שונה – קודם תהליך B, תהליך C, תהליך D, ורק בסוף תהליך A (שדורש הכי הרבה יח’ זמן – 8).

להלן החישוב לאגוריתם FSFC:

תזמוןתהליךזמן הגעהCPUהתחלהסיוםזמן שהייהזמן שהייה ממוצע
1A 8 8856 / 4 = 14
2B 48121214
3C 412161614
4D 416202014

להלן החישוב לאגוריתם SJF:

תזמוןתהליךזמן הגעהCPUהתחלהסיוםזמן שהייהזמן שהייה ממוצע
4A 812202044 / 4 = 11
1B 4 4411
2C 448811
3D 48121211

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

תזמוןתהליךזמן הגעהCPUהתחלהסיוםזמן שהייהזמן שהייה ממוצע
1A 2 2217 / 4 = 4.25
2B 42664.25
3C316744.25
4D317854.25
תזמוןתהליךזמן הגעהCPUהתחלהסיוםזמן שהייהזמן שהייה ממוצע
1A 2 2214 / 4 = 3.5
4B 45993.5
2C313413.5
3D314523.5

 

האלוגריתם השלישי הינו שינוי על אלוג’ SJF ונקרא SRTN (רשי תיבות של Shortest Remaining Time Next), והוא מבטיח שאם זמני הריצה של תהליכים ידועים מראש וקבוצות התהליכים שהאלוגריתם פועל עליה היא קבועה, אזי זמן השהייה יהיה מזערי, ללא הנחות על זמני קלט / פלט.

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

תזמוןתהליךזמן הגעהCPUהתחלהסיוםזמן שהייהזמן שהייה ממוצע
1A 2 2213 / 4 = 3.25
4B 42883.25
2C313413.25
3D314523.25

 

ברמת ה CPU Scheduler מתבצע תזמון לטווח קצר. תזמון ברמה הזו גורם למעברים בין מצב Ready למצב Running (ולהפך). החלטות תזמון ברמה הזו מתבצעת בכפוף למדיניות המתזמן, והמקרים בהם בדר”כ תתבצע הפעלת מתזמן CPU הם כאשר תהליך רץ הקורא לפונקציית מערכת שגורמת להרדמתו, או תהליך שהיה במצב רדום חוזר למצב מוכן בזיכרון, או תהליך מוכן לריצה המגיע לזיכרון הראשי (בשאר המקרים הפעלת המתזמן תלויה במדיניותו).

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

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

 

תזמון במערכות אינטראקטיביות

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

האלוג’ הראשון נקרא RR (ראשי תיבות של Round Robin), והרעיון שעומד ביסודו הוא פשוט: מחלקים את זמן ה CPU לאינטרוולים שווים ולכל תהליך שמוכן לריצה מקצים את ה CPU לפרק זמן קצוב (אינטרוול אחד). פרק זמן זה מכונה time quantum ולאחר סיום אותו quantum מפקיעים את ה CPU ונותנים אותו לתהליך אחר. התהליכים מנוהלים בתור מעגלי (ומכאן שם האלוג’) וחלוקת זמן ה CPU לאינטרוולים שווים נקראת time slicing.

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

מכיוון שהחלפת תהליכים דורשת זמן, קביעת אורך ה quantum הוא נושא חשוב מאוד. קביעת “פרוסת זמן” קצרה גורמת לתקורה גבוהה עקב הזמן המתבזבז על החלפת תהליכים. מנגד, קביעת פרוסת זמן ארוכה יכולה להביא לזמן תגובה ארוך, דבר הפוגע אנושות בזמן התגובה של תהליכים אינטראקטיביים. לכן נהוג, ככלל אצבע, לקבוע את ה quantum למשך הזמן של ה CPU burst (משך הזמן שלוקח לפעולה אינטראקטיבית להסתיים). אך עבור פעולות אינטראקטיביות שונות, משך הזמן הזה יכול להיות שונה, ולכן גם נשתמש בריבוי תורים (נרחיב על כך בהמשך).

 

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

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

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

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

 

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

  • נסמן ב (T(i את זמן הפעולה האינטראקטיבית ה-Iית שלקח לבצע בפועל.
  • נסמן ב (E(i את הניחוש לזמן הפעולה האינטראקטיבית ה-Iית.
  • והניחוש ההתחלתי למשך הזמן של הפעולה האינטראקטיבית הראשונה צריך להיות נתון, והוא (E(1.

לכן, הניבוי לזמן הפעולה האינטראקטיבית הבאה מחושב לפי הנוסחה: (E(i+1) = a T(i) + (1-a) E(i, כאשר a גדול מ-0 וגם קטן מ-1. ובעצם הנוסחה מבצעת שקלול של זמני הפעולה שהיו בעבר.

ע”י בחירת ערכו של a אפשר לייחס חשיבות רבה יותר (או פחותה) להיסטוריה. למשל, ע”י בחירת a = 0.5, נקבל את סדרת הניבויים:

E(1)

E(2) = 0.5T(1) + 0.5E(1)

E(3) = 0.5T(2) + 0.25T(1) + 0.25E(1)

E(4) = 0.5T(3) + 0.25T(2) + 0.125T(1) + 0.125E(1)

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

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

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

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

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

5. בעיות IPC קלאסיות

ניזכר כי בסעיף בו דיברנו על סמאפורים הבנו שהפרוטוקול לפתרון בעיית הקטע הקריטי לזוג תהליכים בעזרת סמפור בינארי כולל 3 כללים: קיים סמפור בינארי S המאותחל למצב S=1, תהליך הנכנס לקטע קריטי מבצע (DOWN(S, תהליך היוצא מקטע קריטי מבצע (UP(S. ושלושת כללים אלה יוצרים את הפרוטוקול המבוקש.

 

בעיית הפילוסופים הסועדים

Dining Philosophers

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

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

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

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

 

לסיכום

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