Serialisera tokens
Inom datavetenskap är serialisering av tokens ett koncept inom samtidighetskontroll som härrör från den pågående utvecklingen av DragonFly BSD . Enligt Matthew Dillon är de mest besläktade med SPL:er , förutom att en token fungerar över flera CPU:er medan SPL:er bara fungerar inom en enda CPU:s domän.
Serialiseringstokens tillåter programmerare att skriva flerprocessorsäker kod utan att de själva eller undersystemen på lägre nivå behöver vara medvetna om varje enskild enhet som också kan ha samma token.
Jämförelse med ömsesidig uteslutning (mutex)
Tokens och mekanismer för ömsesidig uteslutning (mutex) är lås . Till skillnad från mutexes, utesluter inte tokens andra trådar från att komma åt resursen medan de är blockerade eller sover. En tråd som delar resurser med andra trådar kan stoppas och startas av olika anledningar:
- Tidsdelning: schemaläggaren för användarutrymme (US) försöker se till att alla trådar får en rimlig chans att köras, så den kör varje tråd under en kort tidsperiod (en tidsdelning) och växlar sedan till en annan tråd.
- Samtidig körning: i datorer med flera processorer kan en tråd köras exakt samtidigt som en annan tråd på en annan CPU.
- Företräde: en tråd kan föregripa en tråd med lägre prioritet, till exempel ett hårdvaruavbrott eller lätta kärntrådar .
- Frivillig blockering: en tråd kan sova om den måste vänta på något, inte har något att göra eller anropar en funktion som blockerar. Även uppmaningen att skaffa ett lås kan blockera.
Följande tabell sammanfattar egenskaperna för tokens och mutexes.
| Serialisera tokens | Mutexes | |
|---|---|---|
| Tidsklippning | Arbetar | Arbetar |
| Samtidigt utförande | Arbetar | Arbetar |
| Förköpsrätt | Arbetar | Arbetar |
| Frivillig blockering | Misslyckas | Arbetar |
| Undviker dödläge | Ja | Nej |
| Undviker prioritetsinversion | Ja | Nej |
Problem som dödläge och prioritetsinvertering kan vara mycket svåra att undvika och kräver koordinering på många nivåer av kärnan. Eftersom låsning med tokens inte låser fast och förvärvade tokens inte behöver vara atomära när senare operationer blockerar, tillåter det mycket enklare kod än mutex.
... Om du tittar på FreeBSD-5 kommer du att märka att FreeBSD-5 skickar hållna mutexer ner i subrutinstacken ganska ofta, för att tillåta en mycket djup procedurnivå att tillfälligt släppa en mutex för att byta eller blockera eller dela med dödläge. Det finns en hel del kodföroreningar i FreeBSD-5 på grund av detta (där vissa procedurer måste ges kunskap om mutexerna som innehas av andra orelaterade procedurer för att fungera korrekt).
— Matthew Dillon
Exempel
Följande pseudokod och förklaringar illustrerar hur serialisering av tokens fungerar.
| Tråd A | Tråd B | Handling |
|---|---|---|
lwkt_gettoken(T1); iter = lista1.huvud; |
... lwkt_gettoken(T1); // blockerar // väntar på token T1 |
A skaffar token T1 och använder den för att få synkroniserad åtkomst till lista1, som delas av båda trådarna. |
lwkt_gettoken(T2); // block |
// väntar på token T1 |
A:s anrop till lwkt_gettoken(T2) är en blockeringsfunktion, så A går i viloläge och förlorar tillfälligt sina tokens. Den kommer att väckas när schemaläggaren ser att både T1 och T2 är tillgängliga. |
// väntar på T1 och T2 |
list1.head = list1.head.next; lwkt_releasetoken(T1); |
B förvärvar T1 och modifierar lista1. Observera att A:s "iter" fortfarande pekar på det gamla huvudet på listan. |
// hämta den nya versionen av huvudet: iter = list1.head; // skapa ny lista: while (iter != null) { list2.tail = iter; iter = iter.next; } lwkt_releasetoken(T1); lwkt_releasetoken(T2);
|
Schemaläggaren ser att både T1 och T2 är tillgängliga, så den väcker tråd A. Eftersom A kodades korrekt, uppdaterar den sin iterator med det nya huvudet för list1 och gör några icke-blockerande operationer på den. Observera att det hade varit bättre form för A att helt enkelt fråga efter båda polletterna i början. |
Tidigare teknik i Darwin-kärnan
Mac OS X: s Darwin -kärna använder en liknande teknik (kallad tratt ) för att serialisera åtkomst till BSD- delen av kärnan.