പീറ്റേഴ്സൻ്റെ അൽഗോരിതം
പീറ്റേഴ്സൻ്റെ അൽഗോരിതം (അല്ലെങ്കിൽ പീറ്റേഴ്സൻ്റെ പരിഹാരം ) പരസ്പര ഒഴിവാക്കലിനുള്ള ഒരു കൺകറൻ്റ് പ്രോഗ്രാമിംഗ് അൽഗോരിതം ആണ്. രണ്ടോ അതിലധികമോ പ്രോസസ്സുകൾക്ക് പൊതുവായി ഉപയോഗിക്കേണ്ടി വരുന്ന വിഭവങ്ങൾ പങ്കിടുമ്പോൾ പ്രശ്നങ്ങൾ സൃഷ്ടിക്കപ്പെടാതെ ഇരിക്കുന്നതിന് ഈ അൽഗോരിതം ഉപയോഗിക്കാം. 1981 ൽ ഗാരി എൽ പീറ്റേഴ്സൺ എന്ന ഗണിത ശാസ്ത്രജ്ഞനാണ് ഇത് രൂപകൽപ്പന ചെയ്തത്[1]. പീറ്റേഴ്‌സണിൻ്റെ യഥാർത്ഥ അൽഗോരിതം രണ്ട് പ്രോസസ്സുകൾ ഉൾപ്പെടുമ്പോൾ മാത്രമേ ഉപയോക്കുവാൻ സാധിച്ചിരുന്നുള്ളൂവെങ്കിലും, രണ്ടിൽ കൂടുതൽ പ്രോസസ്സുകൾക്കു വേണ്ടിയും സാമാന്യവൽക്കരിച്ച് ഉപയോഗിക്കുവാൻ കഴിയും. [2]
അൽഗോരിതം
തിരുത്തുക
അൽഗോരിതം രണ്ട് വേരിയബിളുകളാണ് ഉപയോഗിക്കുന്നത്: flag[n], turn. flag[n] ഒരു ബൂളിയൻ വേരിയബിൾ ആണ്. flag[n] ൻ്റെ വില true ആണെങ്കിൽ അത് സൂചിപ്പിക്കുന്നത്, n എന്ന പ്രോസസ്സ് നിർണ്ണായക ഭാഗത്തിൽ (ക്രിട്ടിക്കൽ സെഷൻ) പ്രവേശിക്കാൻ ആഗ്രഹിക്കുന്നു എന്നാണ്. turn എന്ന വേരിയബിൾ ക്രിട്ടിക്കൽ സെഷൻ ഉപയോഗിക്കുന്നതിന് ഏതു പ്രൊസസ്സിനാണ് മുൻഗണന നൽകേണ്ടത് എന്ന് രേഖപ്പെടുത്തുന്നതിനാണ് ഉപയോഗിക്കുന്നത്. turn = n ആണെങ്കിൽ n എന്ന പ്രോസസ്സിനായിരിക്കും മുൻഗണന. ഉദാഹരണത്തിന്, P0, P1 എന്നിവ രണ്ട് പ്രോസസ്സുകൾ ആണെന്നിരിക്കട്ടെ. turn = 0 ആണെങ്കിൽ P0-ക്കും turn=1 ആണെങ്കിൽ P1-നുമായിരിക്കും മുൻഗണന. flag[0] = true ആണെങ്കിൽ P0 ക്രിട്ടിക്കൽ സെഷനിലേക്ക് പ്രവേശിക്കുവാൻ ആഗ്രഹിക്കുന്നു എന്നും മനസ്സിലാക്കാം.
ഒരു പ്രോസസ്സിന് ക്രിട്ടിക്കൽ സെഷനിലേക്ക് പ്രവേശിക്കണമെങ്കിൽ അതിന് turn ലഭിക്കുകയും, മറ്റ് പ്രോസസ്സുകൾ എല്ലാം flag[] false ആയി സെറ്റ് ചെയ്തിരിക്കുകയും വേണം. ഇത് പ്രകാരം P0 എന്ന പ്രോസസ്സിന് ക്രിട്ടിക്കൽ സെഷനിലേക്ക് പ്രവേശിക്കണമെങ്കിൽ turn = 0 -യും, flag[1] = false -ഉം ആയിരിക്കണം.
പീറ്റേഴ്സൻ്റെ അൽഗോരിതം ഉപയോഗിക്കുന്ന രണ്ട് പ്രോസസ്സുകളുടെ പ്രോഗ്രാമിൽ നിന്നുള്ള ഭാഗങ്ങളാണ് ചുവടെ കൊടുത്തിരിക്കുന്നത്. തുടക്കത്തിൽ flag[] വേരിയബിളുകൾ false ആക്കിയിരിക്കുന്നു. രണ്ടു പ്രോസസ്സുകൾക്കും നിർണ്ണായക ഭാഗത്തിൽ പ്രവേശിക്കാൻ താൽപ്പര്യമില്ല എന്നർത്ഥം.
P0, P1 എന്നിവയ്ക്ക് പൊതുവായ ഭാഗംbool flag[2] = {false, false};
int trun;
| |
P0 എന്ന പ്രോസസ്സ്flag[0] = true;
turn = 1;
while (flag[1] == true && turn == 1); //കാത്തിരിക്കുന്നു
// നിർണായക ഭാഗം
flag[0] = false;
|
P1 എന്ന പ്രോസസ്സ്flag[1] = true;
turn = 0;
while (flag[0] == true && turn == 0); //കാത്തിരിക്കുന്നു
// നിർണായക ഭാഗം
flag[1] = false;
|
P0 എന്ന പ്രോസസ്സ് നിർണ്ണായക ഭാഗത്തിൽ പ്രവേശിക്കുന്നതിനു മുൻപായി തൻ്റെ flag, true ആക്കി മാറ്റുന്നു. തുടർന്ന് turn = 1 ആക്കുക വഴി P1 എന്ന പ്രോസസ്സിന് നിർണ്ണായക ഭാഗത്തിൽ പ്രവേശിക്കുന്നതിനു ഊഴം നൽകുന്നു. അതിനു ശേഷം ഒരു while() ലൂപ്പ് ഉപയോഗിച്ച് P1-ൻ്റെ flag , turn എന്നിവ തുടർച്ചയായി നിരീക്ഷിക്കുന്നു. flag[1] = true ,turn = 1 എന്നീ വിലകളിൽ ഏതെങ്കിലും ഒന്ന് മാറുന്നതു വരെ ഇത് തുടരുന്നു. ഇവയിൽ എതെങ്കിലും മാറുമ്പോൾ ലൂപ്പ് ബ്രേക്ക് ആവുകയും P0 അതിൻ്റെ നിർണ്ണായക ഭാഗത്തിൽ പ്രവേശിക്കുകയും ചെയ്യുന്നു. അതായത്, ഒന്നുകിൽ flag[1] = false ആകണം (P1-ന് നിർണ്ണായക ഭാഗത്തിൽ പ്രവേശിക്കുന്നതിനു താൽപര്യം ഇല്ല എന്നർത്ഥം) , അല്ലെങ്കിൽ turn = 0 ആകണം (P1 അടുത്ത ഊഴം P0-ക്ക് നൽകി എന്നർത്ഥം). നിർണ്ണായക ഭാഗം കഴിഞ്ഞതിനു ശേഷം P0 തൻ്റെ flag, false ആക്കി മാറ്റുന്നു. P1-ൻ്റെ പ്രവർത്തനവും ഇതേപോലെയാണ്.
ഒരു പ്രോസസ്സ് നിർണ്ണായക ഭാഗത്തിൽ പ്രവേശിക്കുന്നതിനു മുൻപ് turn രണ്ടാമത്തെ പ്രോസസ്സിനു നൽകുന്നത് വഴിയും, നിർണ്ണായക ഭാഗത്തിനു ശേഷം തൻ്റെ flag false ആക്കുന്നതു വഴിയും, രണ്ടാമത്തെ പ്രോസസ്സിന് നിർണ്ണായക ഭാഗത്തിൽ പ്രവേശിക്കുന്നതിനു ഊഴം ലഭിക്കുമെന്ന് ഉറപ്പ് വരുത്തുന്നതായി കാണാം.
തുടക്കത്തിൽ എല്ലാ flag -കളും false ആയി വെക്കുക വഴി ഏതെങ്കിലും ഒരു പ്രോസസ്സ് മാത്രമേ നിലവിൽ നിർണ്ണായക ഭാഗത്തിൽ പ്രവേശിക്കുന്നതിനു ശ്രമിക്കുന്നുള്ളൂവെങ്കിൽ അതിന് തടസ്സം നേരിടുകയില്ല. while() ലൂപ്പ് പ്രവർത്തിക്കുമ്പോൾ flag[n] == true എന്ന കണ്ടീഷൻ തെറ്റുകയും അതുവഴി ലൂപ്പ് ഉടൻ തന്നെ ബ്രേക്ക് ചെയ്ത് നിർണ്ണായക ഭാഗത്തിൽ പ്രവേശിക്കുന്നതിനു കാരണമാകും.