Sannolikhet

Osäker på om detta är en kluring för vet inte om den går att lösa, men jag har en stark känsla av att den BÖR gå att lösa alt. visa varför den inte går att lösa.

$S$ processer vill ha tid på kärnan i en dator. Datorn har följande regler:

Varje process $S_{i}$ har en prioritetsnivå $P_{i}$ (konstant: hur viktig den är) och ett prioritetsvärde $V_{i}$ (varierar: om den ska få köra).

När datorn startar gäller $\forall S_{i} : P_{i} = V_{i}$ .

Efter varje tidsperiod $T$ väljer processorn den process $S_{j}$ med högst prioritetsvärde och låter den köra på kärnan.

Därefter sätter den $V_{j} = 0$ och $\forall S_{i} : V_{i} = V_{i} + P_{i}$

Exempel:
Vi har $P = {3, 5, 10}$

$\begin{matrix} T_{k} & V_{1} & V_{2} & V_{3} \\ T_{1} & 3 & 5 & 11 & - S_{3} v i n n e r \\ T_{2} & 6 & 10 & 11 & - S_{3} v i n n e r \\ T_{3} & 9 & 15 & 11 & - S_{2} v i n n e r \\ T_{4} & 12 & 5 & 22 & - S_{3} v i n n e r \\ T_{5} & 15 & 10 & 11 & - S_{1} v i n n e r \end{matrix}$

Om man ser till hur stor andel $A$ en process får av kärnan verkar det som att (när jag prövar "simuleringar" på datorn) $\lim_{k \to \infty} A_{i} = \frac{P_{i}}{\sum_{j} P_{j}}$ , vilket känns rimligt och rättvist (om en process har dubbelt så stor prioritet får den dubbelt så stor tid på kärnan.

Mitt problem/kluring är: Kan man förutse en process andel tid på kärna om man har mer än en kärna? Dvs, mer än en process kan vinna och få sin $V_{i}$ nollställd per tidsenhet. Om man t.ex. har $N$ kärnor? En sak jag ser direkt är att om $|S| \leq$ N så kommer alla processer ha andel $A = 1$ .

Tidigare exempel med $N = 2$

$\begin{matrix} T_{k} & V_{1} & V_{2} & V_{3} \\ T_{1} & 3 & 5 & 11 & - S_{3} o c h S_{2} v i n n e r \\ T_{2} & 6 & 5 & 11 & - S_{3} o c h S_{1} v i n n e r \\ T_{3} & 3 & 10 & 11 & - S_{3} o c h S_{2} v i n n e r \\ T_{4} & 6 & 5 & 11 & - S_{3} o c h S_{1} v i n n e r \\ T_{5} & 3 & 10 & 11 & - S_{3} o c h S_{2} v i n n e r \end{matrix}$

Här kan man ganska enkelt se att

$A_{1} = 0.5 A_{2} = 0.5 A_{3} = 1$

Min fråga är hade detta kunnat räknas ut utan att göra en "simulering"? Dvs:
Finns det något sätt att hitta en "formel" för hur stor andel $A$ varje process får på kärnorna?

Frågan flyttas från Matematik/Kluringar till Programmering/allmänna diskussioner. Forumdelen Kluringar är endast till för frågor där du vet svaret och vill bjuda dina medmänniskor på en rolig uppgift. /Smaragdalena, moderator

Svara