אלגוריתם הבנקאי

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

האלגוריתם

לאלגוריתם יש 2 תנאים.

1. המערכת לא נמצאת במצב קיפאון (deadlock).

2. המתזמן ידאג שתהליך ירוץ עד שיושלם.

בהתאם לכך, האלגוריתם יכול להיות באחד מתוך 3 מצבים:

1. safe - שני התנאים מתקיימים. 2. unsafe – רק התנאי הראשון מתקיים ומצב קיפאון הוא אופציונלי. 3. מצב קיפאון.

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

דרישות

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

• עבור כל תהליך: כמה התהליך יוכל לדרוש מכל משאב באופן מקסימלי [CLAIM].
• עבור כל תהליך: כמה התהליך מחזיק מכל משאב ברגע זה [ALLOCATED].
• כמה מכל משאב זמין כרגע במערכת [AVAILABLE].

משאבים יוקצו עבור תהליך רק אם הוא יעמוד בתנאים הבאים:

1. דרישה ≤ מקס', אחרת סמן שגיאת - תהליך שעבר את המקסימום שהוא הצהיר.
2. דרישה ≤ זמין, אחרת התהליך יחכה עד שהמשאבים יהיו זמינים.

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

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

ניתן ליישם את אלגוריתם הבנקאי על ידי שימוש בכמה מבני נתונים בסיסיים:

בהינתן n תהליכים במערכת ו-m סוגי משאבים, נשתמש במבני הנתונים הבאים:

• Available: ווקטור באורך m שמייצג את מספר המשאבים הזמינים מכל סוג. אם Available[j] = k, אז קיימים k מופעים של המשאב R_j במצב זמין.
• Max: מטריצה בגודל n×m שמגדירה את דרישת המשאבים המקסימלית של כל תהליך. אם Max[i,j] = k, אז P_i לא יוכל לדרוש יותר מאשר k מהמשאב מסוג R_j.
• Allocation: מטריצה בגודל n×m שמייצגת את מספר המשאבים מכל סוג שכרגע מוקצים לכל תהליך. אם Allocation[i,j] = k, אז עבור התהליך P_i מוקצים כרגע k משאבים מסוג R_j.
• Need: מטריצה בגודל n×m שמייצגת את מספר המשאבים מכל סוג שנזקקים לכל תהליך. אם Need[i,j] = k, אז P_i יזדקק לעוד k משאבים מסוג R_j כדי להשלים את המשימה שלו.

הערה: [Need[i,j] = Max[i,j] - Allocation[i,j.

דוגמה

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

סך כל המשאבים במערכת:
A B C D
6 7 5 6

משאבי מערכת זמינים(Available):
A B C D
2 1 1 3

משאבים שמוקצים כרגע עבור כל תהליך(Allocation):
A B C D
P1 1 2 2 1
P2 1 0 3 3
P3 1 2 1 0

מקסימום מכל משאב עבור כל תהליך(Max):
A B C D
P1 3 3 2 2
P2 1 2 3 4
P3 1 3 5 0

נצרכים = מוקצים כרגע - מקסימום עבור תהליך
משאבים שעדיין נצרכים עבור כל תהליך(Need):
A B C D
P1 2 1 0 1
P2 0 2 0 1
P3 0 1 4 0

"מצב בטוח" ו"מצב לא בטוח"

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

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

דוגמה

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

1. המשאבים הנדרשים כדי למלא את הדרישה המקסימלית של P1 הם: 2 A,‏ 1 B, ו-1 D.
   • המשאבים שכרגע זמינים במערכת הם: 3 A,‏ 1 B,‏ 1 C, ו-2 D.
   • במערכת עדיין יש מספיק משאבים זמינים: [<1 1 0 1> = <1 0 1 2> - <2 1 1 3>].
2. P1 יסיים לרוץ ויחזיר למערכת את המשאבים: 3 A,‏ 3 B,‏ 2 C, ו-2 D.
   • המשאבים שזמינים במערכת לפני שP1 מחזיר משאבים הם: 1 A,‏ 0 B‏, 1 C, ו-1 D.
   • המשאבים הזמינים שיהיו במערכת אחרי שP1 יחזיר משאבים הם: [<3 3 3 4> = <2 2 3 3> + <1 1 0 1>].
3. המשאבים ש-P2 צריך הם עוד 2 B, ו-1 D ואז הוא יוכל לסיים ולהחזיר את כל המשאבים שלו.
   • המשאבים שכרגע זמינים במערכת הם: 4 A,‏ 3 B‏, 3 C, ו-3 D.
   • המשאבים הזמינים שיהיו במערכת לאחר מכן: [<6 6 3 5> = <4 3 2 1> + <1 0 2 0> - <3 3 3 4>].
4. המשאבים ש-P3 צריך הם 1 B ו-4 C ואז הוא יוכל להסתיים.
   • המשאבים שכרגע זמינים במערכת הם: 5 A,‏ 3 B‏, 6 C, ו-6 D.
   • המשאבים הזמינים שיהיו במערכת לאחר מכן: [<6 7 5 6> = <0 5 3 1> + <0 4 1 0> - <6 6 3 5>
5. כיוון שכל התהליכים מסוגלים לסיים לרוץ, המצב הזה הוא "מצב בטוח".

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

דוגמה למצב לא בטוח, היא הדוגמה הראשונה בשינוי תהליך P2 כך שיחזיק בהתחלה עוד יחידה מהמשאב B.

בקשות הקצאה

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

1. האם ניתן להיענות לבקשה?
   • אם לא, לא ניתן לבצע את ההקצאה וצריך לדחות אותה או להעביר את התהליך לרשימת המתנה.
   • אחרת, נניח שהבקשה התקבלה.
2. האם המצב החדש הוא בטוח?
   • אם כן, הקצה את המשאבים.
   • אם לא, דחה את הבקשה או שים אותה בתור ברשימת המתנה.

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

דוגמה

נתחיל באותו מצב שבו הדוגמה הקודמת מתחילה בשינוי תהליך P3 שדורש 2 מהמשאב C.

1. אין מספיק משאבים זמינים מהמשאב C כדי להיענות לבקשה.
2. הבקשה נדחית.

כדוגמה נוספת נוכל להניח שתהליך P3 דורש רק יחידה אחת מהמשאב C.

1. ישנם מספיק משאבים כדי להיענות לבקשה.
2. נניח שהבקשה נענתה.
   • המצב החדש של המערכת יהיה:

משאבי מערכת זמינים:
A B C D
2 0 1 3

משאבים שמוקצים כרגע עבור כל תהליך:
A B C D
P1 1 2 2 1
P2 1 0 3 3
P3 1 2 2 0

מקסימום מכל משאב עבור כל תהליך:
A B C D
P1 3 3 2 2
P2 1 2 3 4
P3 1 3 5 0

1. נבדוק האם המצב החדש שנוצר הוא בטוח.
   1. P1 יכול לקבל את המשאבים: 2 A,
      1 B, ו1 D ולהסתיים.
   2. אחר כך P2 יוכל לקבל את המשאבים: 2 B ו1 D ולהסתיים.
   3. לבסוף, P3 יוכל לקבל את המשאבים: 1 B ו3 C ולהסתיים.
   4. לכן המצב החדש הוא מצב בטוח.
2. מאחר שהמצב החדש הוא מצב בטוח, נקצה את המשאבים.

ולדוגמה אחרונה שתתחיל גם היא באותו מצב למעט העובדה שתהליך P2 דורש רק יחידה אחת של המשאב B.

1. ישנם מספיק משאבים כדי להיענות לבקשה.
2. נניח שהבקשה נענתה.
   • המצב החדש של המערכת יהיה:

משאבי מערכת זמינים:
A B C D
2 1 0 3

משאבים שמוקצים כרגע עבור כל תהליך:
A B C D
P1 1 2 2 1
P2 1 1 3 3
P3 1 2 1 0

מקסימום מכל משאב עבור כל תהליך:
A B C D
P1 3 3 2 2
P2 1 2 3 4
P3 1 3 5 0

1. האם זה מצב בטוח? נניח שP1
   P2 וP3, ידרשו מהמשאב B
   • אין מספיק מהמשאב B כדי לספק את בקשת P1.
   • אין מספיק מהמשאב B כדי לספק את בקשת P2.
   • אין מספיק מהמשאב B כדי לספק את בקשת P3.
   • שום תהליך לא יוכל לקבל מספיק משאבים כדי להסתיים ולכן זהו מצב לא בטוח
2. כיוון שהמצב לא בטוח, דחה את הבקשה.

/*PROGRAM TO IMPLEMENT BANKER'S ALGORITHM
  *   --------------------------------------------*/
#include <stdio.h>
int curr[5][5], maxclaim[5][5], avl[5];
int alloc[5] = {0,0,0,0,0};
int maxres[5], running[5], safe=0;
int count = 0, i, j, exec, r, p,k=1;

int main()
{
    printf("\nEnter the number of processes: ");
    scanf("%d",&p);

    for(i=0;i<p;i++)
    {
        running[i]=1;
        count++;
    }

    printf("\nEnter the number of resources: ");
    scanf("%d",&r);

    for(i=0;i<r;i++)
    { 
        printf("\nEnter the resource for instance %d: ",k++);
        scanf("%d",&maxres[i]);
    }

    printf("\nEnter maximum resource table:\n");
    for(i=0;i<p;i++)
    {
        for(j=0;j<r;j++)
        {
            scanf("%d",&maxclaim[i][j]);
        }
    }

    printf("\nEnter allocated resource table:\n");
    for(i=0;i<p;i++)
    {
        for(j=0;j<r;j++)
        {
            scanf("%d",&curr[i][j]);
        }
    }

    printf("\nThe resource of instances: ");
    for(i=0;i<r;i++)
    {
        printf("\t%d",maxres[i]);
    }

    printf("\nThe allocated resource table:\n");
    for(i=0;i<p;i++)
    {
        for(j=0;j<r;j++)
        {
            printf("\t%d",curr[i][j]);
        }

        printf("\n");
    }

    printf("\nThe maximum resource table:\n");
    for(i=0;i<p;i++)
    {
        for(j=0;j<r;j++)
        {
            printf("\t%d",maxclaim[i][j]);
        }

        printf("\n");
    }

    for(i=0;i<p;i++)
    {
        for(j=0;j<r;j++)
        {
            alloc[j]+=curr[i][j];
        }
    }

    printf("\nAllocated resources:");
    for(i=0;i<r;i++)
    {
        printf("\t%d",alloc[i]);
    }

    for(i=0;i<r;i++)
    {
        avl[i]=maxres[i]-alloc[i];
    }

    printf("\nAvailable resources:");
    for(i=0;i<r;i++)
    {
        printf("\t%d",avl[i]);
    }
    printf("\n");

    //Main procedure goes below to check for unsafe state.
    while(count!=0)
    {
        safe=0;
        for(i=0;i<p;i++)
        {
            if(running[i])
            {
                exec=1;
                for(j=0;j<r;j++)
                {
                    if(maxclaim[i][j] - curr[i][j] > avl[j]){
                        exec=0;
                        break;
                    }
                }
                if(exec)
                {
                    printf("\nProcess%d is executing\n",i+1);
                    running[i]=0;
                    count--;
                    safe=1;

                    for(j=0;j<r;j++) {
                        avl[j]+=curr[i][j];
                    }

                    break;
                }
            }
        }
        if(!safe)
        {
            printf("\nThe processes are in unsafe state.\n");
            break;
        }
        else
        {
            printf("\nThe process is in safe state");
            printf("\nSafe sequence is:");

            for(i=0;i<r;i++)
            {
                printf("\t%d",avl[i]);
            }

            printf("\n");
        }
    }
}


/*SAMPLE  OUTPUT
-----------------
Enter the number of resources:4

Enter the number of processes:5

Enter  Claim Vector:8 5 9 7

Enter Allocated Resource Table:
2 0 1 1
0 1 2 1
4 0 0 3
0 2 1 0
1 0 3 0

Enter Maximum Claim table:
3 2 1 4
0 2 5 2
5 1 0 5
1 5 3 0
3 0 3 3

The Claim Vector is:	8	5	9	7
The Allocated Resource Table:
	2	0	1	1
	0	1	2	1
	4	0	0	3
	0	2	1	0
	1	0	3	0

The  Maximum Claim Table:
	3	2	1	4
	0	2	5	2
	5	1	0	5
	1	5	3	0
	3	0	3	3

 Allocated resources:	7	3	7	5
 Available resources:	1	2	2	2

Process3 is executing

 The process is in safe state
 Available vector:	5	2	2	5
Process1 is executing

 The process is in safe state
 Available vector:	7	2	3	6
Process2 is executing

 The process is in safe state
 Available vector:	7	3	5	7
Process4 is executing

 The process is in safe state
 Available vector:	7	5	6	7
Process5 is executing

 The process is in safe state
 Available vector:	8	5	9	7

 ---------------------------------------------------------*/

מגבלות

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