Deadlock prevention algorithms
કોમ્પ્યુટર વિજ્ઞાનમાં, મડાગાંઠ નિવારણ અલ્ગોરિધમ્સનો ઉપયોગ સહવર્તી પ્રોગ્રામિંગમાં થાય છે જ્યારે બહુવિધ પ્રક્રિયાઓએ એક કરતાં વધુ વહેંચાયેલ સંસાધનો પ્રાપ્ત કરવા પડે છે. જો બે અથવા વધુ સહવર્તી પ્રક્રિયાઓ આડેધડ બહુવિધ સંસાધનો મેળવે છે, તો એવી પરિસ્થિતિ ઊભી થઈ શકે છે કે જ્યાં દરેક પ્રક્રિયામાં બીજી પ્રક્રિયા માટે જરૂરી સંસાધન હોય. પરિણામે, કોઈ પણ પ્રક્રિયા તેને જરૂરી તમામ સંસાધનો મેળવી શકતી નથી, તેથી તમામ પ્રક્રિયાઓ આગળના અમલથી અવરોધિત થાય છે. આ સ્થિતિને મડાગાંઠ કહેવામાં આવે છે. ડેડલોક પ્રિવેન્શન અલ્ગોરિધમ દરેક પ્રક્રિયા દ્વારા સંસાધન ઉપયોગનું આયોજન કરે છે જેથી ઓછામાં ઓછી એક પ્રક્રિયા હંમેશા તેના માટે જરૂરી તમામ સંસાધનો મેળવી શકે. ડેડલોક અલ્ગોરિધમનું આવું જ એક ઉદાહરણ બેન્કરનું અલ્ગોરિધમ છે. ઝાંખી ડિસ્ટ્રિબ્યુટેડ ડેડલોક ડિસ્ટ્રિબ્યુટેડ ડેડલોક ડિસ્ટ્રિબ્યુટેડ સિસ્ટમોમાં થઈ શકે છે જ્યારે ડિસ્ટ્રિબ્યુટેડ ટ્રાન્ઝેક્શન અથવા સમવર્તી નિયંત્રણનો ઉપયોગ કરવામાં આવે છે. ડિસ્ટ્રિબ્યુટેડ ડેડલોક્સને વૈશ્વિક વેઇટ-ફોર ગ્રાફ બનાવીને, ડેડલોક ડિટેક્ટર પર સ્થાનિક વેઇટ-ફોર ગ્રાફમાંથી અથવા એજ ચેઝિંગ જેવા ડિસ્ટ્રિબ્યુટેડ અલ્ગોરિધમ દ્વારા શોધી શકાય છે. ફેન્ટમ ડેડલોક્સ એ ડેડલોક્સ છે જે સિસ્ટમના આંતરિક વિલંબને કારણે ડિસ્ટ્રિબ્યુટેડ સિસ્ટમમાં શોધાય છે પરંતુ શોધના સમયે વાસ્તવમાં અસ્તિત્વમાં નથી. ડેડલોક નિવારણ સમાંતરતા વધારવાની ઘણી જુદી જુદી રીતો છે જ્યાં પુનરાવર્તિત તાળાઓ અન્યથા ડેડલોકનું કારણ બનશે. પરંતુ ત્યાં એક કિંમત છે. અને તે કિંમત ક્યાં તો પ્રદર્શન/ઓવરહેડ છે, ડેટા ભ્રષ્ટાચારને મંજૂરી આપે છે, અથવા બંને. કેટલાક ઉદાહરણોમાં નીચેનાનો સમાવેશ થાય છેઃ લોક પદાનુક્રમ, લોક સંદર્ભ-ગણતરી અને પ્રિએમ્પશન (ક્યાં તો સંસ્કરણનો ઉપયોગ કરીને અથવા જ્યારે પ્રિએમ્પશન થાય ત્યારે ડેટા ભ્રષ્ટાચારને મંજૂરી આપવી); વેઇટ-ફોર-ગ્રાફ (ડબલ્યુએફજી) અલ્ગોરિધમ્સ, જે તમામ ચક્રોને ટ્રેક કરે છે જે ડેડલોકનું કારણ બને છે (કામચલાઉ ડેડલોક સહિત); અને હ્યુરિસ્ટિક્સ અલ્ગોરિધમ્સ કે જે ડેડલોક શક્ય હોય તેવા સ્થાનોના 100% માં સમાંતરતામાં વધારો કરે તે જરૂરી નથી, પરંતુ તેના બદલે તેમને પૂરતી જગ્યાએ હલ કરીને સમાધાન કરે છે જેથી પ્રદર્શન/ઓવરહેડ વિરુદ્ધ સમાંતરતા સ્વીકાર્ય હોય. "જ્યારે બે ટ્રેનો ક્રોસિંગ પર એકબીજાની નજીક આવે છે" એવી પરિસ્થિતિનો વિચાર કરો. જસ્ટ-ઇન-ટાઇમ નિવારણ ક્રોસિંગ (ક્રોસિંગ ગાર્ડ) પર ઊભેલી વ્યક્તિને સ્વીચ સાથે રાખવા જેવું કામ કરે છે જે ફક્ત એક જ ટ્રેનને "સુપર ટ્રેક" પર જવા દેશે જે અન્ય રાહ જોનારી ટ્રેન (ઓ) ની ઉપર અને ઉપર દોડે છે. બિન-પુનરાવર્તિત તાળાઓ માટે, તાળું માત્ર એક જ વાર દાખલ કરી શકાય છે (જ્યાં એક થ્રેડ ખોલ્યા વિના બે વાર દાખલ કરવાથી મડાગાંઠ સર્જાશે, અથવા પરિપત્ર રાહ નિવારણ લાગુ કરવા માટે અપવાદ ફેંકશે). પુનરાવર્તિત તાળાઓ માટે, તાળાઓમાંથી પસાર થવા માટે માત્ર એક જ દોરીની મંજૂરી છે. જો કોઈ અન્ય થ્રેડ લોકમાં પ્રવેશ કરે છે, તો તેણે ત્યાં સુધી રાહ જોવી પડશે જ્યાં સુધી પ્રારંભિક થ્રેડ કે જે તેમાંથી પસાર થાય છે તે n વખત દાખલ થાય છે. તેથી પ્રથમ સાથેનો મુદ્દો એ છે કે તે કોઈ મડાગાંઠ અટકાવતું નથી. બીજું ડિસ્ટ્રિબ્યુટેડ ડેડલોક પ્રિવેન્શન કરતું નથી. પરંતુ બીજાને ડેડલોક દૃશ્યને રોકવા માટે પુનઃવ્યાખ્યાયિત કરવામાં આવે છે જે પ્રથમ સંબોધતું નથી. પુનરાવર્તિત રીતે, માત્ર એક જ દોરાને તાળામાંથી પસાર થવાની મંજૂરી આપવામાં આવે છે. જો અન્ય થ્રેડો લોકમાં પ્રવેશ કરે છે, તો તેમણે ત્યાં સુધી રાહ જોવી પડશે જ્યાં સુધી તેમાંથી પસાર થતો પ્રારંભિક થ્રેડ n વખત પૂર્ણ ન થાય. પરંતુ જો લોકિંગમાં પ્રવેશતા થ્રેડોની સંખ્યા લોક કરેલા નંબરની બરાબર હોય, તો એક થ્રેડને સુપર-થ્રેડ તરીકે સોંપો, અને જ્યાં સુધી તે પૂર્ણ ન થાય ત્યાં સુધી તેને ચલાવવાની મંજૂરી આપો (તે કેટલી વાર લોકિંગમાં પ્રવેશ કરે છે/બહાર નીકળે છે તેના પર નજર રાખો). સુપર-થ્રેડ સમાપ્ત થયા પછી, શરત રિકર્સિવ લોકમાંથી તર્કનો ઉપયોગ કરવા માટે બદલાઈ જાય છે, અને બહાર નીકળતો સુપર-થ્રેડ પોતાને સુપર-થ્રેડ ન હોવા તરીકે સુયોજિત કરે છે જે લોકરને સૂચિત કરે છે કે અન્ય લૉક કરેલા, રાહ જોઈ રહેલા થ્રેડોને આ શરત ફરીથી તપાસવાની જરૂર છે જો ડેડલોક દૃશ્ય અસ્તિત્વમાં હોય, તો નવો સુપર-થ્રેડ સેટ કરો અને તે તર્કને અનુસરો. નહિંતર, નિયમિત લોકિંગ ફરી શરૂ કરો. ઉપર સંબોધવામાં ન આવેલા મુદ્દાઓ ઘણી બધી મૂંઝવણ અટકાવવાની સમસ્યાની આસપાસ ફરે છે. પરંતુ આ તર્ક અટકાવવાની સમસ્યાનું સમાધાન કરતું નથી કારણ કે જે પરિસ્થિતિઓમાં લોકીંગ થાય છે તે જાણીતી છે, જે ચોક્કસ ઉકેલ આપે છે (અન્યથા જરૂરી સામાન્ય ઉકેલને બદલે જે અટકાવવાની સમસ્યાને જરૂરી છે). તેમ છતાં, આ લોકર આ તર્કનો ઉપયોગ કરીને માત્ર તાળાઓને ધ્યાનમાં રાખીને તમામ મડાગાંઠને અટકાવે છે. પરંતુ જો તેનો ઉપયોગ અન્ય લોકીંગ મિકેનિઝમ્સ સાથે કરવામાં આવે, તો જે તાળું શરૂ થાય છે તે ક્યારેય ખોલતું નથી (અપવાદ તરીકે, તાળું ખોલ્યા વગર જમ્પિંગ આઉટ ફેંકવું, તાળું અંદર અનિશ્ચિત સમય માટે લૂપિંગ કરવું, અથવા કોડિંગ ભૂલ દ્વારા તાળું ખોલવાનું ભૂલી જવું), ડેડલોકિંગ ખૂબ જ શક્ય છે. આનો સમાવેશ કરવા માટે શરત વધારવા માટે અટકાવવાના મુદ્દાને ઉકેલવાની જરૂર પડશે, કારણ કે કોઈ એવી પરિસ્થિતિઓ સાથે વ્યવહાર કરશે કે જેના વિશે કોઈને કંઈ ખબર નથી અને તે બદલવામાં અસમર્થ છે. બીજો મુદ્દો એ છે કે તે કામચલાઉ મડાગાંઠના મુદ્દાને સંબોધતો નથી (ખરેખર મડાગાંઠ નથી, પરંતુ એક પ્રદર્શન કિલર), જ્યાં બે અથવા વધુ થ્રેડો એકબીજા પર તાળું મારે છે જ્યારે અન્ય અસંબંધિત થ્રેડ ચાલી રહ્યું છે. આ કામચલાઉ ડેડલોક્સમાં ફક્ત તેમની અંદર એક દોરી ચાલી શકે છે, જે સમાંતરતામાં વધારો કરે છે. પરંતુ ડિસ્ટ્રિબ્યુટેડ ડેડલોક ડિટેક્શન તમામ તાળાઓ માટે કેવી રીતે કામ કરે છે, અને તેમાંના સબસેટ્સ નહીં, તેના કારણે કામચલાઉ ડેડલોકને દૂર કરવા માટે સુપર-થ્રેડ લોજિક કરતા પહેલા અસંબંધિત ચાલી રહેલા થ્રેડને પૂર્ણ કરવું આવશ્યક છે. ઉપરોક્તમાં અસ્થાયી લાઇવ-લોક દૃશ્ય જોઈ શકાય છે. જો પ્રથમ અસંબંધિત થ્રેડ બહાર નીકળે તે પહેલાં અન્ય અસંબંધિત ચાલી રહેલો થ્રેડ શરૂ થાય, તો કામચલાઉ ડેડલોકિંગનો બીજો સમયગાળો થશે. જો આવું સતત થાય (અત્યંત દુર્લભ), તો કામચલાઉ મડાગાંઠ કાર્યક્રમ બહાર નીકળે તે પહેલાં સુધી લંબાવી શકાય છે, જ્યારે અન્ય અસંબંધિત થ્રેડો સમાપ્ત થવાની બાંયધરી આપવામાં આવે છે (બાંયધરીને કારણે કે એક થ્રેડ હંમેશા પૂર્ણ થવા સુધી ચાલશે). વધુ વિસ્તરણ સમાંતરતા વધારવા માટે વધારાના તર્કને સામેલ કરવા માટે આને વધુ વિસ્તૃત કરી શકાય છે જ્યાં કામચલાઉ ડેડલોક અન્યથા થઈ શકે છે. પરંતુ વધુ તર્ક ઉમેરવાના દરેક પગલા માટે, આપણે વધુ ઓવરહેડ ઉમેરીએ છીએ. કેટલાક ઉદાહરણોમાં નીચેનાનો સમાવેશ થાય છેઃ હાલના તાળાઓના દરેક સબસેટને ધ્યાનમાં લેવા માટે વિતરિત સુપર-થ્રેડ લોકિંગ મિકેનિઝમનું વિસ્તરણ; વેઇટ-ફોર-ગ્રાફ (ડબલ્યુએફજી) અલ્ગોરિધમ્સ, જે ડેડલોકનું કારણ બને છે તે તમામ ચક્રોને ટ્રેક કરે છે (કામચલાઉ ડેડલોક સહિત); અને હ્યુરિસ્ટિક્સ અલ્ગોરિધમ્સ કે જે કામચલાઉ ડેડલોક શક્ય હોય તેવા સ્થાનોના 100% માં સમાંતરતામાં વધારો કરે તે જરૂરી નથી, પરંતુ તેના બદલે તેમને પૂરતા સ્થળોએ હલ કરીને સમાધાન કરે છે જેથી પ્રદર્શન/ઓવરહેડ વિરુદ્ધ સમાંતરતા સ્વીકાર્ય હોય (દા. ત. WFG). ઉપલબ્ધ દરેક પ્રોસેસર માટે, પ્રોસેસરોની સંખ્યા + 1 ઊંડા કરતાં ઓછા ડેડલોક ચક્ર શોધવા તરફ કામ કરો). સંદર્ભો વિતરિત કમ્પ્યુટિંગ