Non-blocking algorithm
કોમ્પ્યુટર વિજ્ઞાનમાં, અલ્ગોરિધમને નોન-બ્લૉકિંગ કહેવામાં આવે છે જો કોઈ થ્રેડની નિષ્ફળતા અથવા સસ્પેન્શન અન્ય થ્રેડની નિષ્ફળતા અથવા સસ્પેન્શનનું કારણ ન બની શકે; કેટલીક કામગીરીઓ માટે, આ અલ્ગોરિધમ્સ પરંપરાગત અવરોધિત અમલીકરણ માટે ઉપયોગી વિકલ્પ પ્રદાન કરે છે. જો સિસ્ટમ-વ્યાપી પ્રગતિની બાંયધરી હોય તો બિન-અવરોધિત અલ્ગોરિધમ લોક-મુક્ત હોય છે, અને જો થ્રેડ દીઠ પ્રગતિની બાંયધરી પણ હોય તો રાહ-મુક્ત હોય છે. 2003માં અવરોધ-સ્વતંત્રતાની શરૂઆત ન થઈ ત્યાં સુધી સાહિત્યમાં "નોન-બ્લૉકિંગ" નો ઉપયોગ "લોક-ફ્રી" ના સમાનાર્થી તરીકે થતો હતો. "નોન-બ્લૉકિંગ" શબ્દનો ઉપયોગ પરંપરાગત રીતે ટેલિકોમ્યુનિકેશન નેટવર્કનું વર્ણન કરવા માટે થતો હતો જે "હાલના કૉલ્સને ફરીથી ગોઠવ્યા વિના" રિલેના સમૂહ દ્વારા જોડાણને રૂટ કરી શકે છે (ક્લોસ નેટવર્ક જુઓ). ઉપરાંત, જો ટેલિફોન એક્સચેન્જ "ખામીયુક્ત ન હોય, તો તે હંમેશા જોડાણ કરી શકે છે" (નોનબ્લોકિંગ મિનિમલ સ્પૅનિંગ સ્વીચ જુઓ). પ્રેરણા મલ્ટી-થ્રેડેડ પ્રોગ્રામિંગનો પરંપરાગત અભિગમ વહેંચાયેલ સંસાધનોની ઍક્સેસને સુમેળ કરવા માટે તાળાઓનો ઉપયોગ કરવાનો છે. મ્યુટેક્સ, સેમાફોર્સ અને ક્રિટિકલ સેક્શન જેવા સિંક્રોનાઇઝેશન પ્રિમિટિવ્સ એ તમામ પદ્ધતિઓ છે જેના દ્વારા પ્રોગ્રામર ખાતરી કરી શકે છે કે કોડના અમુક વિભાગો વારાફરતી એક્ઝિક્યુટ ન થાય, જો આમ કરવાથી વહેંચાયેલ મેમરી સ્ટ્રક્ચર્સ દૂષિત થશે. જો એક થ્રેડ પહેલેથી જ બીજા થ્રેડ દ્વારા પકડાયેલ તાળું મેળવવાનો પ્રયાસ કરે છે, તો તાળું મુક્ત ન થાય ત્યાં સુધી થ્રેડ બ્લોક થઈ જશે. દોરાને અવરોધિત કરવો ઘણા કારણોસર અનિચ્છનીય હોઈ શકે છે. એક સ્પષ્ટ કારણ એ છે કે જ્યારે દોરડું અવરોધિત હોય, ત્યારે તે કંઈપણ પૂર્ણ કરી શકતું નથીઃ જો અવરોધિત દોરડું ઉચ્ચ-પ્રાથમિકતા અથવા વાસ્તવિક-સમયનું કાર્ય કરી રહ્યું હોત, તો તેની પ્રગતિને અટકાવવી અત્યંત અનિચ્છનીય હોત. અન્ય સમસ્યાઓ ઓછી સ્પષ્ટ છે. ઉદાહરણ તરીકે, તાળાઓ વચ્ચેની ચોક્કસ ક્રિયાપ્રતિક્રિયાઓ ડેડલોક, લિવલોક અને પ્રાયોરિટી ઇન્વર્ઝન જેવી ભૂલની સ્થિતિ તરફ દોરી શકે છે. તાળાઓના ઉપયોગમાં બરછટ-દાણાદાર તાળાઓ વચ્ચેનો વિનિમય પણ સામેલ છે, જે સમાંતરતા માટેની તકોને નોંધપાત્ર રીતે ઘટાડી શકે છે, અને બારીક-દાણાદાર તાળાઓ, જેમાં વધુ સાવચેતીપૂર્વક ડિઝાઇનની જરૂર પડે છે, તાળાઓ પર તાળાઓ લગાવવાનું વધે છે અને ભૂલો થવાની શક્યતા વધુ હોય છે. અવરોધિત અલ્ગોરિધમ્સથી વિપરીત, બિન-અવરોધિત અલ્ગોરિધમ્સ આ ડાઉનસાઇડ્સથી પીડાતા નથી, અને વધુમાં વિક્ષેપ હેન્ડલર્સમાં ઉપયોગ માટે સલામત છેઃ ભલે પૂર્વનિર્ધારિત થ્રેડ ફરી શરૂ કરી શકાતો નથી, તેમ છતાં તેના વિના પ્રગતિ શક્ય છે. તેનાથી વિપરીત, મ્યુચ્યુઅલ એક્સક્લૂઝન દ્વારા સુરક્ષિત વૈશ્વિક ડેટા સ્ટ્રક્ચર્સને ઇન્ટરપ્ટ હેન્ડલરમાં સુરક્ષિત રીતે એક્સેસ કરી શકાતા નથી, કારણ કે પ્રિએમ્પ્ટેડ થ્રેડ લોકને પકડી રાખે છે-પરંતુ નિર્ણાયક વિભાગ દરમિયાન ઇન્ટરપ્ટ વિનંતીને માસ્ક કરીને આને સરળતાથી સુધારી શકાય છે. કાર્યક્ષમતામાં સુધારો કરવા માટે લોક-ફ્રી ડેટા સ્ટ્રક્ચરનો ઉપયોગ કરી શકાય છે. લોક-ફ્રી ડેટા સ્ટ્રક્ચર સીરીયલ એક્ઝેક્યુશનને બદલે સમાંતર એક્ઝેક્યુશનમાં વિતાવેલા સમયની માત્રામાં વધારો કરે છે, મલ્ટી-કોર પ્રોસેસર પર પ્રદર્શનમાં સુધારો કરે છે, કારણ કે સુસંગત રહેવા માટે વહેંચાયેલ ડેટા સ્ટ્રક્ચરની ઍક્સેસને શ્રેણીબદ્ધ કરવાની જરૂર નથી. અમલીકરણ થોડા અપવાદો સાથે, બિન-અવરોધિત અલ્ગોરિધમ્સ અણુ રીડ-મોડિફાય-રાઈટ પ્રિમિટિવ્સનો ઉપયોગ કરે છે જે હાર્ડવેર પ્રદાન કરવું આવશ્યક છે, જેમાંથી સૌથી નોંધપાત્ર સરખામણી અને સ્વેપ (CAS) છે. ક્રિટિકલ વિભાગો લગભગ હંમેશા આ પ્રિમિટિવ્સ પર પ્રમાણભૂત ઇન્ટરફેસનો ઉપયોગ કરીને અમલમાં મૂકવામાં આવે છે (સામાન્ય કિસ્સામાં, ક્રિટિકલ વિભાગો અવરોધિત થશે, પછી ભલે તે આ પ્રિમિટિવ્સ સાથે અમલમાં મૂકવામાં આવે). 1990 ના દાયકામાં તમામ બિન-અવરોધિત અલ્ગોરિધમ્સને સ્વીકાર્ય કામગીરી હાંસલ કરવા માટે અંતર્ગત આદિમ સાથે "મૂળ રૂપે" લખવું પડ્યું હતું. જો કે, સોફ્ટવેર ટ્રાન્ઝેક્શનલ મેમરીનું ઊભરતું ક્ષેત્ર કાર્યક્ષમ બિન-અવરોધિત કોડ લખવા માટે પ્રમાણભૂત અમૂર્તતાનું વચન આપે છે. સ્ટેક્સ, કતારો, સમૂહો અને હેશ કોષ્ટકો જેવા મૂળભૂત માહિતી માળખાં પ્રદાન કરવા માટે પણ ઘણું સંશોધન કરવામાં આવ્યું છે. આ પ્રોગ્રામ્સને અસિંક્રોનસ રીતે થ્રેડો વચ્ચે ડેટાની સરળતાથી આપ-લે કરવાની મંજૂરી આપે છે. વધુમાં, કેટલાક બિન-અવરોધિત ડેટા સ્ટ્રક્ચર્સ એટલા નબળા છે કે વિશેષ અણુ પ્રિમિટિવ્સ વિના અમલમાં મૂકી શકાય. આ અપવાદોમાં નીચેનાનો સમાવેશ થાય છેઃ સિંગલ-રીડર સિંગલ-રાઇટર રિંગ બફર એફઆઇએફઓ, જે કદ સાથે ઉપલબ્ધ સહી વગરના પૂર્ણાંક પ્રકારોમાંથી એકના ઓવરફ્લોને સમાનરૂપે વિભાજિત કરે છે, તેને એક જ લેખક અને કોઈપણ સંખ્યામાં વાચકો સાથે માત્ર મેમરી અવરોધ રીડ-કોપી-અપડેટનો ઉપયોગ કરીને સુરક્ષિત રીતે અમલમાં મૂકી શકાય છે. (વાચકો રાહ-મુક્ત હોય છે; જ્યાં સુધી તેને યાદશક્તિ પુનઃપ્રાપ્ત કરવાની જરૂર ન પડે ત્યાં સુધી લેખક સામાન્ય રીતે તાળું-મુક્ત હોય છે). બહુવિધ લેખકો અને કોઈપણ સંખ્યામાં વાચકો સાથે વાંચન-નકલ-અપડેટ કરો. (વાચકો રાહ-મુક્ત હોય છે; બહુવિધ લેખકો સામાન્ય રીતે તાળા સાથે શ્રેણીબદ્ધ થાય છે અને અવરોધ-મુક્ત નથી). કેટલીક લાઈબ્રેરીઓ આંતરિક રીતે લોક-ફ્રી તકનીકોનો ઉપયોગ કરે છે, પરંતુ લૉક-ફ્રી કોડ લખવો મુશ્કેલ છે જે સાચો છે. બિન-અવરોધિત અલ્ગોરિધમ્સમાં સામાન્ય રીતે કાળજીપૂર્વક રચાયેલ ક્રમમાં વાંચન, વાંચન-ફેરફાર-લેખન અને સૂચનાઓ લખવાની શ્રેણીનો સમાવેશ થાય છે. કમ્પાઇલર્સનું ઓપ્ટિમાઇઝિંગ આક્રમક રીતે કામગીરીને ફરીથી ગોઠવી શકે છે. જ્યારે તેઓ ન કરે ત્યારે પણ, ઘણા આધુનિક CPU ઘણીવાર આવી કામગીરીઓને ફરીથી ગોઠવે છે (તેમની પાસે "નબળા સુસંગતતા મોડેલ" હોય છે), સિવાય કે CPU ને ફરીથી ક્રમ ન આપવા માટે મેમરી અવરોધનો ઉપયોગ કરવામાં આવે. C + + 11 પ્રોગ્રામરો <atomic> માં std:: atomic નો ઉપયોગ કરી શકે છે, અને C11 પ્રોગ્રામરો <stdatomic.h> નો ઉપયોગ કરી શકે છે, જે બંને એવા પ્રકારો અને કાર્યો પૂરા પાડે છે જે કમ્પાઇલરને આવી સૂચનાઓને ફરીથી ગોઠવવાનું અને યોગ્ય મેમરી અવરોધો દાખલ કરવાનું કહે છે. રાહ જોવાની સ્વતંત્રતા રાહ જોવાની સ્વતંત્રતા એ પ્રગતિની સૌથી મજબૂત બિન-અવરોધક બાંયધરી છે, જે ભૂખમરો-સ્વતંત્રતા સાથે બાંયધરીકૃત સિસ્ટમ-વ્યાપી થ્રુપુટને જોડે છે. એક અલ્ગોરિધમ રાહ-મુક્ત હોય છે જો દરેક કામગીરીમાં કામગીરી પૂર્ણ થાય તે પહેલાં અલ્ગોરિધમ કેટલા પગલાં લેશે તેની મર્યાદા હોય. આ મિલકત રીઅલ-ટાઇમ સિસ્ટમો માટે મહત્વપૂર્ણ છે અને જ્યાં સુધી પ્રદર્શન ખર્ચ ખૂબ ઊંચો ન હોય ત્યાં સુધી તે હંમેશા સરસ છે. તે 1980 ના દાયકામાં દર્શાવવામાં આવ્યું હતું કે તમામ અલ્ગોરિધમ્સને રાહ-મુક્ત અમલમાં મૂકી શકાય છે, અને સીરીયલ કોડમાંથી ઘણા પરિવર્તન, જેને સાર્વત્રિક રચનાઓ કહેવાય છે, તે દર્શાવવામાં આવ્યા છે. જો કે, પરિણામી પ્રદર્શન સામાન્ય રીતે નિષ્કપટ અવરોધિત ડિઝાઇન સાથે પણ મેળ ખાતું નથી. ત્યારથી કેટલાક કાગળોએ સાર્વત્રિક બાંધકામોની કામગીરીમાં સુધારો કર્યો છે, પરંતુ તેમ છતાં, તેમનું પ્રદર્શન અવરોધક ડિઝાઇનથી ઘણું ઓછું છે. કેટલાક કાગળોએ રાહ-મુક્ત અલ્ગોરિધમ્સ બનાવવાની મુશ્કેલીની તપાસ કરી છે. ઉદાહરણ તરીકે, એવું દર્શાવવામાં આવ્યું છે કે વ્યાપકપણે ઉપલબ્ધ અણુ શરતી આદિમ, CAS અને LL/SC, થ્રેડોની સંખ્યામાં રેખીય રીતે વધતા મેમરી ખર્ચ વિના ઘણા સામાન્ય ડેટા માળખાઓનું ભૂખમરો મુક્ત અમલીકરણ પ્રદાન કરી શકતા નથી. પરંતુ વ્યવહારમાં આ નીચલી સીમાઓ વાસ્તવિક અવરોધ રજૂ કરતી નથી કારણ કે વહેંચાયેલ મેમરીમાં થ્રેડ દીઠ સ્ટોરની કેશ લાઇન અથવા વિશિષ્ટ આરક્ષણ ગ્રાન્યુલ (એઆરએમ પર 2 KB સુધી) ખર્ચ કરવો એ વ્યવહારુ સિસ્ટમો માટે ખૂબ ખર્ચાળ માનવામાં આવતું નથી (સામાન્ય રીતે તાર્કિક રીતે જરૂરી સ્ટોરની માત્રા એક શબ્દ છે, પરંતુ ભૌતિક રીતે સમાન કેશ લાઇન પર CAS કામગીરી ટકરાશે, અને સમાન વિશિષ્ટ આરક્ષણ ગ્રાન્યુલમાં LL/SC કામગીરી ટકરાશે, તેથી ભૌતિક રીતે જરૂરી સ્ટોરની માત્રા વધારે છે). સંશોધન અને વ્યવહારમાં, 2011 સુધી રાહ-મુક્ત અલ્ગોરિધમ્સ દુર્લભ હતા. જો કે, 2011 માં કોગન અને પેટ્રેંકે CAS આદિમ પર રાહ-મુક્ત કતારની ઇમારત રજૂ કરી હતી, જે સામાન્ય રીતે સામાન્ય હાર્ડવેર પર ઉપલબ્ધ છે. તેમના બાંધકામથી માઇકલ અને સ્કોટની લોક-ફ્રી કતારનું વિસ્તરણ થયું, જે વ્યવહારમાં ઘણીવાર ઉપયોગમાં લેવાતી કાર્યક્ષમ કતાર છે. કોગન અને પેટ્રેંકના ફોલો-અપ પેપરમાં રાહ-મુક્ત અલ્ગોરિધમ્સને ઝડપી બનાવવા માટે એક પદ્ધતિ પ્રદાન કરવામાં આવી હતી અને રાહ-મુક્ત કતારને તેના લોક-મુક્ત પ્રતિરૂપની જેમ વ્યવહારીક રીતે ઝડપી બનાવવા માટે આ પદ્ધતિનો ઉપયોગ કર્યો હતો. ટિમનેટ અને પેટ્રેંકના અનુગામી પેપરમાં લોક-ફ્રીમાંથી રાહ-મુક્ત ડેટા સ્ટ્રક્ચર્સ બનાવવા માટે સ્વચાલિત પદ્ધતિ પ્રદાન કરવામાં આવી હતી. આમ, રાહ-મુક્ત અમલીકરણ હવે ઘણા ડેટા-માળખાઓ માટે ઉપલબ્ધ છે. લોક-ફ્રીડમ લોક-ફ્રીડમ વ્યક્તિગત થ્રેડોને ભૂખ્યા રહેવાની મંજૂરી આપે છે પરંતુ સિસ્ટમ-વાઇડ થ્રુપુટની બાંયધરી આપે છે. અલ્ગોરિધમ લૉક-ફ્રી હોય છે જો, જ્યારે પ્રોગ્રામ થ્રેડો પૂરતા લાંબા સમય સુધી ચલાવવામાં આવે છે, ત્યારે ઓછામાં ઓછો એક થ્રેડ પ્રગતિ કરે છે (પ્રગતિની કેટલીક સમજદાર વ્યાખ્યા માટે). બધા રાહ-મુક્ત અલ્ગોરિધમ્સ લોક-મુક્ત છે. ખાસ કરીને, જો એક થ્રેડ સસ્પેન્ડ કરવામાં આવે, તો લોક-ફ્રી અલ્ગોરિધમ ખાતરી આપે છે કે બાકીના થ્રેડો હજુ પણ પ્રગતિ કરી શકે છે. તેથી, જો બે થ્રેડો એક જ મ્યુટેક્સ લોક અથવા સ્પિનલોક માટે સ્પર્ધા કરી શકે, તો એલ્ગોરિધમ લોક-ફ્રી નથી. (જો આપણે એક દોરીને લટકાવીશું જે તાળું ધરાવે છે, તો બીજી દોરી અવરોધિત થશે.) અલ્ગોરિધમ લોક-ફ્રી હોય છે જો કેટલાક પ્રોસેસરો દ્વારા અનંત વાર કામગીરી મર્યાદિત સંખ્યામાં પગલાંઓમાં સફળ થાય છે. દાખલા તરીકે, જો પ્રોસેસરો કોઈ કામગીરીને અમલમાં મૂકવાનો પ્રયાસ કરી રહ્યા હોય, તો કેટલીક પ્રક્રિયાઓ મર્યાદિત સંખ્યામાં કામગીરીને પૂર્ણ કરવામાં સફળ થશે અને અન્ય નિષ્ફળ થઈ શકે છે અને નિષ્ફળતા પર ફરીથી પ્રયાસ કરી શકે છે. રાહ-મુક્ત અને લોક-મુક્ત વચ્ચેનો તફાવત એ છે કે દરેક પ્રક્રિયા દ્વારા રાહ-મુક્ત કામગીરી મર્યાદિત સંખ્યામાં પગલાંઓમાં સફળ થવાની ખાતરી આપે છે, અન્ય પ્રોસેસરોને ધ્યાનમાં લીધા વગર. સામાન્ય રીતે, લોક-ફ્રી અલ્ગોરિધમ ચાર તબક્કામાં ચાલી શકે છેઃ પોતાની કામગીરી પૂર્ણ કરવી, અવરોધક કામગીરીમાં મદદ કરવી, અવરોધક કામગીરીને રદ કરવી અને રાહ જોવી. પોતાની શસ્ત્રક્રિયા પૂર્ણ કરવી એ સહવર્તી સહાય અને ગર્ભપાતની શક્યતાને કારણે જટિલ છે, પરંતુ તે હંમેશા પૂર્ણ થવાનો સૌથી ઝડપી માર્ગ છે. જ્યારે અવરોધ પૂરો થાય ત્યારે ક્યારે મદદ કરવી, સ્થગિત કરવી અથવા રાહ જોવી તે અંગેનો નિર્ણય વિવાદ વ્યવસ્થાપકની જવાબદારી છે. આ ખૂબ જ સરળ હોઈ શકે છે (ઉચ્ચ પ્રાથમિકતાની કામગીરીમાં મદદ કરવી, ઓછી પ્રાથમિકતાની કામગીરીને અટકાવવી), અથવા વધુ સારા થ્રુપુટ હાંસલ કરવા માટે વધુ અનુકૂળ હોઈ શકે છે, અથવા પ્રાથમિકતાની કામગીરીમાં વિલંબ ઘટાડી શકાય છે. યોગ્ય સહવર્તી સહાય એ સામાન્ય રીતે લોક-ફ્રી અલ્ગોરિધમનો સૌથી જટિલ ભાગ છે, અને ઘણીવાર અમલમાં મૂકવા માટે ખૂબ જ ખર્ચાળ છેઃ સહાયક થ્રેડ માત્ર ધીમું જ નથી કરતું, પરંતુ વહેંચાયેલ મેમરીના મિકેનિક્સને આભારી છે, જો તે હજુ પણ ચાલી રહ્યું હોય તો સહાય કરવામાં આવતો થ્રેડ પણ ધીમો થઈ જશે. અવરોધ-સ્વતંત્રતા અવરોધ-સ્વતંત્રતા એ સૌથી નબળી કુદરતી બિન-અવરોધક પ્રગતિની ગેરંટી છે. અલ્ગોરિધમ અવરોધ મુક્ત હોય છે જો કોઈ પણ સમયે, મર્યાદિત સંખ્યામાં પગલાઓ માટે અલગથી ચલાવવામાં આવેલ એક જ થ્રેડ (એટલે કે, તમામ અવરોધક થ્રેડો સસ્પેન્ડ સાથે) તેની કામગીરી પૂર્ણ કરશે. તમામ લોક-ફ્રી અલ્ગોરિધમ્સ અવરોધ-મુક્ત છે. અવરોધ-સ્વતંત્રતાની માંગ માત્ર એ જ છે કે કોઈપણ આંશિક રીતે પૂર્ણ થયેલ કામગીરીને રદ કરી શકાય અને કરવામાં આવેલા ફેરફારોને પાછા ખેંચી શકાય. સહવર્તી સહાય છોડવાથી ઘણીવાર વધુ સરળ અલ્ગોરિધમ્સમાં પરિણમી શકે છે જે માન્ય કરવા માટે સરળ હોય છે. સિસ્ટમને સતત લાઇવ-લોકિંગથી અટકાવવી એ વિવાદ વ્યવસ્થાપકનું કાર્ય છે. કેટલાક અવરોધ-મુક્ત અલ્ગોરિધમ્સ ડેટા સ્ટ્રક્ચરમાં "સુસંગતતા માર્કર્સ" ની જોડીનો ઉપયોગ કરે છે. ડેટા સ્ટ્રક્ચરને વાંચતી પ્રક્રિયાઓ પહેલા એક સુસંગતતા માર્કરને વાંચે છે, પછી સંબંધિત ડેટાને આંતરિક બફરમાં વાંચે છે, પછી અન્ય માર્કરને વાંચે છે, અને પછી માર્કર્સની તુલના કરે છે. જો બે માર્કર્સ સમાન હોય તો ડેટા સુસંગત છે. જ્યારે ડેટા સ્ટ્રક્ચરને અપડેટ કરવાની અન્ય પ્રક્રિયા દ્વારા વાંચનમાં વિક્ષેપ આવે છે ત્યારે માર્કર્સ બિન-સમાન હોઈ શકે છે. આવા કિસ્સામાં, પ્રક્રિયા આંતરિક બફરમાં ડેટાને કાઢી નાખે છે અને ફરીથી પ્રયાસ કરે છે. આ પણ જુઓ ડેડલોક જાવા ConcurrentMap#Lock-મુક્ત અણુતા જીવંતતા લોક (કોમ્પ્યુટર વિજ્ઞાન) પરસ્પર બાકાત પ્રાથમિકતા વ્યુત્ક્રમ સંસાધન ભૂખમરો સંદર્ભો બાહ્ય કડીઓ લોક-મુક્ત પ્રોગ્રામિંગનો પરિચય બિન-અવરોધિત અલ્ગોરિધમ્સ સિંક્રોનાઇઝેશન સમવર્તી નિયંત્રણ સમવર્તી નિયંત્રણ અલ્ગોરિધમ્સ