Innehållsförteckning:
Definition - Vad betyder Dekkers algoritm?
Dekkers algoritm är den första kända algoritmen som löser problemet med ömsesidig uteslutning vid samtidig programmering. Det krediteras Th. J. Dekker, en holländsk matematiker som skapade algoritmen för ett annat sammanhang. Dekkers algoritm används i processkö och tillåter två olika trådar att dela samma engångsresurs utan konflikt genom att använda delat minne för kommunikation.
Techopedia förklarar Dekkers algoritm
Dekkers algoritm tillåter endast en enda process att använda en resurs om två processer försöker använda den samtidigt. Höjdpunkten i algoritmen är hur den löser problemet. Det lyckas förhindra konflikten genom att verkställa ömsesidig uteslutning, vilket innebär att endast en process får använda resursen åt gången och kommer att vänta om en annan process använder den. Detta uppnås med användning av två "flaggor" och ett "symbol". Flaggorna indikerar om en process vill gå in i det kritiska avsnittet (CS) eller inte; ett värde på 1 betyder SANT att processen vill ange CS, medan 0, eller FALSE, betyder det motsatta. Token, som också kan ha ett värde på 1 eller 0, indikerar prioritet när båda processerna har sina flaggor inställda till SANT.
Denna algoritm kan framgångsrikt genomföra ömsesidig uteslutning men kommer hela tiden att testa om det kritiska avsnittet är tillgängligt och förlorar därför betydande processortid. Det skapar problemet som kallas lockstep-synkronisering, där varje tråd endast kan köras i strikt synkronisering. Det är också icke-expanderbart eftersom det bara stöder maximalt två processer för ömsesidig uteslutning.
