Co-operativt Multitask

Tags:    c++ single-threaded multitask async

Jeg har faaet til opgave at lave en co-operative multitask i en single threaded program skrevet i C++. Den skal kunne anvendes som kernen i en mini-operativ styresystem. Man skal kunne tilfoeje nogle opgaver til den som vil blive eksekveret naar manageren/scheduler'en priorterer tid til den. Efter noget research kan jeg godt forstaa de store hoved traek. Dere er dog et problem jeg ikke kan forstaa. Manageren skal kunne saette en opgave i pause tilstand og starte en ny opgave for derefter at kunne vende tilbage og faerdiggoere opgaven som den var igang med. Som eksempel skal opgaverne finde ud af om nogle binaere traeer er balancerede eller ubalancerede. Til det bliver man naesten noedt til at lave en recursive soegning. Saa jeg gaar ud fra at i hver recursion skal funktionen spoerge manageren om den kan fortsette med sin soegningen eller den skal saettes i pause tilstand, saa manageren kan begynde paa en ny opgave. Men hvordan kan man vende tilbage til sin recursive soegning efter at havde udfoert en anden opgave? Som sagt saa er det hele single-threaded. Er der nogle herinde der kan kaste lys paa dette for mig?

Med andre ord, I det store hele saa skal man altsaa lave et single-threaded system som kan udfoerer opgaver (asynkronisk) uden at blokere systemet paa noget tidspunkt.




5 svar postet i denne tråd vises herunder
3 indlæg har modtaget i alt 14 karma
Sorter efter stemmer Sorter efter dato
Du kan prøve at kigge på coroutiner: http://www.boost.org/doc/libs/1_57_0/libs/coroutine/doc/html/index.html

Som eksempel skal opgaverne finde ud af om nogle binaere traeer er balancerede eller ubalancerede. Til det bliver man naesten noedt til at lave en recursive soegning.

En løsning med rekursive funktionskald er helt klart den nemmeste løsning at forstå, men det kan godt gøres på en anden måde. Man kunne gøre call-stacken explicit, dvs. gemme de knuder man mangler at besøge i en stak-datastruktur (som kun behøver at være log(n) dyb). Men det vil ikke hjælpe dig med andre opgaver.

Med andre ord, I det store hele saa skal man altsaa lave et single-threaded system som kan udfoerer opgaver (asynkronisk) uden at blokere systemet paa noget tidspunkt.

Lyder som om at preemptive multitasking med tråde er nemmere end at skulle garantere alle sin små-opgaver ikke bruger for lang tid. Eventuelt justere trådes prioritetsniveau sådan at dine opgaver har lavere priority end hvad systemet som ikke må blokeres på noget tidspunkt.



Spændende opgave. Måske et dumt spørgsmål, men hvorfor skal den være single threaded? Er den ene task afhængig af resultatet fra en anden i køen?


Ps! Måske skal du finde et andet forum at spørge. Udvikleren er efterhånden mest til folk der søger partnere der skal arbejde gratis (skrevet med et alvorligt smil).



Hej Søren,

Du skal kigge efter contex switching af processor under operativ systemer. Her skulle du meget gerne finde lige det du skal bruge :)



Jeg har loest opgaven nu.
Mange tak for jeres hjaelp.



Det behøver ikke nødvendigvis at være rekursivt. Du kan selv styre "rekursionsstakken" med f.eks. en linked list.

Dvs. når du ellers ville rekursere (kalde dig selv), med en ny node som argument, så smider du den nuværende øverst på stakken og sætter næste node til at være nuværende. Når du ville returnere fra kaldet, så popper du øverste node fra stakken, medmindre den er tom i hvilket tilfælde din algoritme har kørt færdig.

Cooperative multitasking fungerer jo ved at processen selv lader andre komme til, så det kan den gøre ved at gemme sin tilstand og så genskabe den, når den selv får lov at køre igen.



t