ബാങ്കറുടെ അൽഗോരിതം

ഓപ്പറേറ്റിങ്ങ് സിസ്റ്റത്തിൽ റിസോഴ്സുകൾ അനുവദിക്കുന്നതിനും, ഡെഡ് ലോക്ക് ഒഴിവാക്കുന്നതിനുമായി കമ്പ്യൂട്ടർ ശാസ്ത്രജ്ഞനായ എഡ്സ്ഗർ ഡിജ്ക്സ്ട്ര 1965 കാലഘട്ടത്തിൽ വികസിപ്പിച്ചെടുത്ത ഒരു അൽഗോരിതമാണ് ബാങ്കറുടെ അൽഗോരിതം. ഒരു ബാങ്കർ തന്റെ പക്കൽ ലോണിനായി അപേക്ഷിക്കുന്നവർക്ക് ലോൺ അനുവദിക്കാവുന്നതാണോ എന്ന് തന്റെ പക്കൽ ലഭ്യമായ ഫണ്ട് അനുസരിച്ച് പരിശോധിക്കുകയും, ലോൺ അനുവദിക്കുന്നത് തന്റെ മുന്നോട്ടുള്ള പ്രവർത്തനങ്ങളെ ബാധിക്കില്ല എന്ന് പരിശോധിച്ച് മാത്രം ലോൺ അനുവദിക്കുന്നതിനു തുല്യമായ പ്രവർത്തനമാണ് ഈ അൽഗോരിതം ചെയ്യുന്നത് എന്നത് കൊണ്ടാണ് ഇതിനെ ബാങ്കറുടെ അൽഗോരിതം എന്ന് വിളിക്കുന്നത്. ബാങ്കറുടെ കാര്യത്തിൽ റിസോഴ്സ് 'പണവും', ഉപഭോക്താവ് ലോൺ ആവശ്യമുള്ള വ്യക്തിയുമാണെങ്കിൽ, ഓപ്പറേറ്റിംഗ് സിസ്റ്റങ്ങളുടെ കാര്യത്തിൽ റിസോഴ്സ് കമ്പ്യൂട്ടർ മെമ്മറി, പ്രോസസ്സർ, പ്രിന്റർ, ഫയൽ എന്നിങ്ങനെയുള്ളവയും, ഉപഭോക്താവ് ഈ റിസോഴ്സുകൾ ആവശ്യമായ പ്രോസസ്സുകളുമാണ്.

അൽഗോരിതം

ബാങ്കറുടെ അൽഗോരിതം പ്രവർത്തിക്കണമെങ്കിൽ, മൂന്ന് വിവരങ്ങൾ ലഭ്യമാകേണ്ടതുണ്ട്:

ഓരോ പ്രോസസ്സും പരമാവധി എത്ര റിസോഴ്സുകൾ ആവശ്യപ്പെടാം (MAX)
ഓരോ പ്രോസസ്സുിനും നിലവിൽ എത്ര റിസോഴ്സുകൾ അനുവദിച്ചിട്ടുണ്ട് (ALLOCATED)
നിലവിൽ ഓരോ റിസോഴ്സും എത്ര മാത്രം ലഭ്യമാണ് (AVAILABLE)

ഓരോ പ്രോസസ്സും ആവശ്യപ്പെടുന്ന റീസോഴ്സുകളുടെ അളവ് നിലവിൽ ലഭ്യമായ റിസോഴ്സുകളേക്കാൾ കുറവോ തുല്യമോ ആണെങ്കിൽ മാത്രമേ ആ പ്രോസസ്സിന് ആവശ്യപ്പെട്ട റിസോഴ്സ് അനുവദിക്കൂ അനുവദിക്കുകയുള്ളു. അല്ലാത്തപക്ഷം, റിസോഴ്സുകൾ ലഭ്യമാകുന്നതുവരെ പ്രോസസ്സിന് കാത്തിരിക്കേണ്ടി വരും.

ഒരു സിസ്റ്റത്തിൽ n എണ്ണം പ്രോസസ്സുകളും, m എണ്ണം റിസോഴ്സുകളുമാണ് ഉള്ളത് എന്ന് കരുതുക. ഇങ്ങനെയിരിക്കേ ബാങ്കറുടെ അൽഗോരിതം നടപ്പിലാക്കുന്നതിനായി മേൽപ്പറഞ്ഞ വിവരങ്ങൾ കൈകാര്യം ചെയ്യുന്നതിന് 5 അടിസ്ഥാന ഡാറ്റ സ്ട്രക്ചറുകൾ ആവശ്യമായി വരും.

TOTAL_AVAILABLE[m]: ഇത് m വിവരങ്ങൾ സൂക്ഷിക്കാൻ സാധിക്കുന്ന ഒരു വെക്ടർ (അറേ) ആണ്. ഓരോ ഇനത്തിലുമുള്ള റിസോഴ്സുകളുടെ എത്ര പകർപ്പുകൾ ആകെ ലഭ്യമാണ് എന്ന വിവരമാണ് ഈ അറേ കൈകാര്യം ചെയ്യുന്നത്. അതായത് TOTAL_AVAILABLE[i] = k ആണെങ്കിൽ i എന്ന ഇനം റിസോഴ്സിന്റെ k എണ്ണം പകർപ്പുകൾ ആകെ ലഭ്യമാണ് എന്ന് മനസിലാക്കാം.
AVAILABLE[m]: ഇത് m വിവരങ്ങൾ സൂക്ഷിക്കാൻ സാധിക്കുന്ന ഒരു വെക്ടർ (അറേ) ആണ്. ഓരോ ഇനത്തിലുമുള്ള റിസോഴ്സുകളുടെ എത്ര പകർപ്പുകൾ നിലവിൽ ലഭ്യമാണ് എന്ന വിവരമാണ് ഈ അറേ കൈകാര്യം ചെയ്യുന്നത്. അതായത് AVAILABLE[i] = k ആണെങ്കിൽ i എന്ന ഇനം റിസോഴ്സിന്റെ k എണ്ണം പകർപ്പുകൾ നിലവിൽ ലഭ്യമാണ് എന്ന് മനസിലാക്കാം.
MAX[n × m]: ഇത് ഒരു n × m മാട്രിക്സ് ആണ്. ഓരോ പ്രോസസ്സും പരമാവധി ആവശ്യപ്പെടാവുന്ന ഓരോ ഇനം റിസോഴ്സുകളുടെയും എണ്ണമാണ് ഈ മാട്രിക്സ് കൈകാര്യം ചെയ്യുന്നത്. അതായത്, MAX[i, j] = k ആണെങ്കിൽ, i എന്ന പ്രോസസ്സിന് j എന്ന റിസോഴ്സിന്റെ പരമാവധി k പക‍ർപ്പുകളേ ആവശ്യമായി വരൂ എന്ന് മനസിലാക്കാം.
ALLOCATION[n × m]: ഇത് ഒരു n × m മാട്രിക്സ് ആണ്. ഓരോ പ്രോസസ്സിനും നിലവിൽ അനുവദിച്ചിട്ടുള്ള ഓരോ ഇനം റിസോഴ്സുകളുടെയും എണ്ണമാണ് ഈ മാട്രിക്സിൽ സൂക്ഷിക്കുന്നത്. അതായത്, ALLOCATiON[i, j] = k ആണെങ്കിൽ, i എന്ന പ്രോസസ്സിന് j എന്ന റിസോഴ്സിന്റെ k പക‍ർപ്പുകൾ അനുവദിച്ചിട്ടുണ്ട് എന്ന് മനസിലാക്കാം.
NEED[n × m]: ഇത് ഒരു n × m മാട്രിക്സ് ആണ്. ഓരോ പ്രോസസ്സിനും തന്റെ പ്രവർത്തി പൂർത്തീകരിക്കാൻ ശേഷിക്കുന്ന ഓരോ ഇനം റിസോഴ്സുകളുടെയും എണ്ണമാണ് ഈ മാട്രിക്സിൽ സൂക്ഷിക്കുന്നത്. അതായത്, NEED[i, j] = k ആണെങ്കിൽ, i എന്ന പ്രോസസ്സിന് j എന്ന റിസോഴ്സിന്റെ k പക‍ർപ്പുകൾ കൂടി ലഭിച്ചാൽ തന്റെ പ്രവർത്തി പൂർത്തീകരിക്കാം എന്ന് മനസിലാക്കാം. NEED മാട്രിക്സ് കണക്കാക്കുന്നത് താഴെ പറയും വിധമാണ്: NEED[i,j] = MAX[i,j] - ALLOCATION[i,j].

ഉദാഹരണം

സിസ്റ്റത്തിൽ ലഭ്യമായ റിസോഴ്സുകൾ A,B,C,D എന്നിവയാണെന്നു കരുതുക. ഇവയുടെ ആകെ ലഭ്യത ചുവടെ ചേർത്ത പ്രകാരമാണ് (TOTAL_AVAILABILITY).

A   B  C   D
6   5   7   6

ഈ സിസ്റ്റത്തിൽ നിലവിൽ P1,P2,P3,P4 എന്നിങ്ങനെ 4 പ്രോസസ്സുകൾ പ്രവർത്തിക്കുന്നുണ്ട് എന്നും കരുതുക. ഓരോ പ്രോസസ്സുകൾക്കും പരമാവധി ആവശ്യമായി വരാവുന്ന റിസോഴ്സുകളുടെ വിവരം ചുവടെ ചേർത്ത പ്രകാരമാണ് (MAX):

      A   B  C   D
P1    3   3   2   2
P2    1   2   3   4
P3    1   3   5   0

ഓരോ പ്രോസസ്സുകൾക്കും നിലവിൽ അനുവദിച്ചിട്ടുള്ള റിസോഴ്സുകളുടെ വിവരം ചുവടെ ചേർത്ത പ്രകാരമാണ് (ALLOCATION):

          A   B   C   D
P1        1    2   2   1
P2       1    0   3   3
P3       1    2   1    0
-----------------
ആകെ 3   4   6   4

മേൽ വിവരങ്ങളിൽ നിന്നും ആകെ ലഭ്യമായ റിസോഴ്സുകളിൽ നിന്നും ആകെ അനുവദിച്ച റിസോഴ്സുകൾ കുറച്ചാൽ നിലവിൽ ലഭ്യമായ ബാക്കി റിസോഴ്സുകളുടെ വിവരം ചുവടെ ചേർത്ത പ്രകാരമാണെന്ന് കാണാം (AVAILABILE).

A   B  C   D
3    1   1   2

പ്രോസസ്സുകൾക്ക് നിലവിൽ ഇനിയും ആവശ്യമായ ററിസോഴ്സുകളുടെ വിവരം ചുവടെ ചേർത്ത പ്രകാരവും (NEED).

       A   B  C   D
P1     2   1    0   1
P2    0   2   0   1
P3    0   1   4   0

സുരക്ഷിതവും സുരക്ഷിതമല്ലാത്തതുമായ സ്ഥിതികൾ

തൽസ്ഥിതിയിൽ നിന്നും എല്ലാ പ്രോസസ്സുകളും പൂർത്തിയാക്കാൻ സാധിക്കുന്ന പ്രകാരം റിസോഴ്സുകളെ ഏതെങ്കിലും ഒരു രീതിയിലെങ്കിലും വിതരണം ചെയ്യാൻ സാധിച്ചാൽ തൽസ്ഥിതി സുരക്ഷിതമാണെന്ന് കണക്കാക്കാം (safe state). നിലവിൽ ഒരു സുരക്ഷിത സ്ഥിതിയിൽ ആയിരിക്കേ പ്രോസസ്സുകൾ ആവശ്യപ്പെടുന്ന പ്രകാരം റിസോഴ്സുകൾ അനുവദിച്ചാൽ മറ്റൊരു സുരക്ഷിത സ്ഥിതിയിലേക്കാണോ മാറുക എന്നാണ് ബാങ്കറുടെ അൽഗോരിതം പരിശോധിക്കുന്നത്.