Samschemaläggning
Coscheduling är principen för samtidiga system för schemaläggning av relaterade processer för att köras på olika processorer samtidigt ( parallellt ). Det finns olika specifika implementeringar för att förverkliga detta.
Om en applikation består av en samling processer som arbetar nära varandra, och om några men inte alla processer är schemalagda för exekvering, kan de exekverande processerna försöka kommunicera med de som inte körs, vilket kommer att få dem att blockeras. Så småningom kommer de andra processerna att schemaläggas för exekvering, men vid det här laget kan situationen vara omvänd så att dessa processer också blockerar väntan på interaktioner med andra. Som ett resultat av detta gör programmet framsteg med en hastighet av högst en interprocessinteraktion per tidssegment och kommer att ha låg genomströmning och hög latens .
Genomförande
Coscheduling består av två idéer:
- När du schemalägger någon av processerna i den relaterade gruppen, schemalägg alla för exekvering så att de kan kommunicera effektivt.
- När en process i gruppen blockerar medan den kommunicerar med en annan process i gruppen, ta inte bort den från dess processor. Låt istället dess tillstånd vara laddat på sin processor under en kort tid, under antagandet att den kommer att få ett svar inom kort. Om denna tid går ut och processen fortfarande inte har blivit körbar, anta att den kommer att vila länge och schemalägga om processorn.
Vissa samschemaläggningstekniker uppvisar fragment av processer som inte körs samtidigt med resten av den samschemalagda uppsättningen. Förekomsten av dessa fragment minimeras vanligtvis av dessa algoritmer. Gängschemaläggning är en striktare variant av coscheduling som inte tillåter fragment helt.
Typer av coscheduling
Forskare har klassificerat tre typer av coscheduling: explicit coscheduling , lokal scheduling och implicit eller dynamisk coscheduling .
Explicit samschemaläggning kräver att all bearbetning faktiskt äger rum samtidigt, och implementeras vanligtvis genom global schemaläggning över alla processorer. En specifik algoritm är känd som gängschemaläggning .
Lokal samschemaläggning tillåter individuella processorer att schemalägga behandlingen oberoende.
Dynamisk (eller implicit) coscheduling är en form av coscheduling där enskilda processorer fortfarande kan schemalägga bearbetning oberoende, men de fattar schemaläggningsbeslut i samarbete med andra processorer.
Historia
Termen "coscheduling" introducerades av Ousterhout (1982) . Den ursprungliga definitionen är att processarbetsuppsättningen måste samschemaläggas (schemalagd för exekvering samtidigt) för att parallellprogrammet ska göra framsteg .
Se även
Anteckningar
- Ousterhout, JK (1982). "Schemaläggningstekniker för samtidiga system" (PDF) . Proceedings of Third International Conference on Distributed Computing Systems : 22–30.