---

Hej alle,

ja, endnu et kerne-spørgsmål - denne gang specifikt til 2.6 kernen af
Linux

scheduleren som er så populær er jeg ved at prøve at forstå.
Så vidt jeg kan se er det meget smart at køre med to runqueue's for hver
cpu, men der er noget jeg ikke rigtig kan få til at stemme overens.
(fortæl hvad jeg har misforstået)

Der anvendes en round-robin schedulering på selve den aktive runqueue.
Selvom der angiveligt kun skulle være en runqueue for hver cpu, kan jeg
ikke rigtig forstå hvori prioritetsscheduleren kommer ind i billedet?
Der er i alt 140 prioritets-niveauer. nice-værdier går fra -20 til 19 og
kan variere med plus minus 5 alt efter interaktivitet og cpu-bunden.
Hvis en proces er I/O-bunden (interaktiv) vil den ikke miste sin
time-slice ved at schedulere sig selv frivilligt væk, idet der evalueres
på hhv. interaktivitet af processen og starvation i expired-køen.

Er der en eller flere runqueue's for hver cpu eller er der faktisk en
for hver prioritet! Ellers er round-robin jo ikke en prioriteret
schedulering.
Der må på en eller anden måde være en kø (både expired og active) for
hver prioritet der er!

Hvordan med starvation i andre prioriteter? En ting er, at man tjekker
for starvation på expired-køen som sådan, men hvad med andre lavere
prioriterede køer? Vil de ikke komme til at lide af starvation på en
eller anden måde?

Måske jeg har misforstået noget om de runqueue's der er i systemet!

Hvordan beregnes de 140 prioritetsniveauer egentlig? Der er jo to
grundlag for det - den dynamiske prioritet baseret på nice-værdien og
realtime prioriteten!


Mvh / Preben Holm

---

On 2004-06-03, Preben <64bitNOnoNOSPAM@mailme.dk> wrote:

> Er der en eller flere runqueue's for hver cpu eller er der faktisk en
> for hver prioritet! Ellers er round-robin jo ikke en prioriteret
> schedulering.

Der er en runkø for hver prioritet som du så rigtigt har gættet (Faktisk 2
som du også selv nævner, en aktiv og en expired).

> Hvordan med starvation i andre prioriteter? En ting er, at man tjekker
> for starvation på expired-køen som sådan, men hvad med andre lavere
> prioriterede køer? Vil de ikke komme til at lide af starvation på en
> eller anden måde?

Midlertidigt måske, men højprioriterede processer mister jo deres ticks på
et et eller andet tidspunkt, og så kommer mindre prioriterede til. Når alle
har brugt deres ticks får alle en ny omgang idet aktiv og expired køerne
byttes rundt. Som du også selv skriver, så foregår der en løbende evaulering
af hvilke processer der har brugt CPU tid og IO tid, og en bonus/straf på +-
5 tildeles.

I princippet kan man dog godt tænke sig en højprioritetsprocess der er kodet
med kendskab til kernens scheduler som forker sig selv lige før den løber
tør for ticks i håb om at den får en ny portion, men det her man også tænkt
på. Det gør den ikke! Den nedarver sin forfaders mængde ticks-1, så den slags
julelege går ikke.

> Hvordan beregnes de 140 prioritetsniveauer egentlig? Der er jo to

Alle processer har en statisk prioritet (19 -> -20) og får så yderliger den
bonus/straf du taler om.

Thomas

---

Hej igen

Tror næsten at jeg har fået terminologien korrekt:
- en run-kø for hver processor
- et prioritetsarray for hver priritet

Så mangler jeg bare helt forståelsen af hvorledes expired og
active-arrayet er defineret - for jeg er noget i tvivl (se længere nede).


>>Er der en eller flere runqueue's for hver cpu eller er der faktisk en
>>for hver prioritet! Ellers er round-robin jo ikke en prioriteret
>>schedulering.
>
>
> Der er en runkø for hver prioritet som du så rigtigt har gættet (Faktisk 2
> som du også selv nævner, en aktiv og en expired).
>

men hvis man yield'er sig selv skriver Robert Love (Linux Kernel
Development), at man ryger helt bagerst - ikke kun i forhold til sin
egen prioritet, men faktisk indtil at alle andre processer i systemet
har kørt (selv dem med lavere prioritet).
Så vidt jeg indtil nu har forstået det, gælder der, at når man ryger i
expired array'et, så kører man ikke igen, før alle andre processer
faktisk har kørt mindst een gang.


>>Hvordan med starvation i andre prioriteter? En ting er, at man tjekker
>>for starvation på expired-køen som sådan, men hvad med andre lavere
>>prioriterede køer? Vil de ikke komme til at lide af starvation på en
>>eller anden måde?
>
>
> Midlertidigt måske, men højprioriterede processer mister jo deres ticks på
> et et eller andet tidspunkt, og så kommer mindre prioriterede til. Når alle
> har brugt deres ticks får alle en ny omgang idet aktiv og expired køerne
> byttes rundt. Som du også selv skriver, så foregår der en løbende evaulering
> af hvilke processer der har brugt CPU tid og IO tid, og en bonus/straf på +-
> 5 tildeles.
>
> I princippet kan man dog godt tænke sig en højprioritetsprocess der er kodet
> med kendskab til kernens scheduler som forker sig selv lige før den løber
> tør for ticks i håb om at den får en ny portion, men det her man også tænkt
> på. Det gør den ikke! Den nedarver sin forfaders mængde ticks-1, så den slags
> julelege går ikke.
>
>
>>Hvordan beregnes de 140 prioritetsniveauer egentlig? Der er jo to
>
>
> Alle processer har en statisk prioritet (19 -> -20) og får så yderliger den
> bonus/straf du taler om.

Okay, nice-værdien skulle angiveligt være fra 100-140, hvor realtime
prioriteten er de 1-99.
Hvad er højest prioritet i denne terminologi (når vi arbejder med
prioritetsmatricen)? Er det 99 der er den højeste prioritet, fordi det
er højeste realtime prioritet eller er det f.eks. 1 der er højeste
prioritet og så 140 der er mindste prioritet - eller?



Mvh / Preben Holm

---

On 2004-06-04, Preben <64bitNOnoNOSPAM@mailme.dk> wrote:

> Tror næsten at jeg har fået terminologien korrekt:
> - en run-kø for hver processor
> - et prioritetsarray for hver priritet

Jeps det er rigtigt.

> Så mangler jeg bare helt forståelsen af hvorledes expired og
> active-arrayet er defineret - for jeg er noget i tvivl (se længere nede).

ok

> men hvis man yield'er sig selv skriver Robert Love (Linux Kernel
> Development), at man ryger helt bagerst - ikke kun i forhold til sin
> egen prioritet, men faktisk indtil at alle andre processer i systemet
> har kørt (selv dem med lavere prioritet).

Ja det er næsten rigtigt. Når man yielder sig selv (= siger, lad en anden
køre), så kan der ske følgende:

1. Hvis man er en interaktiv process, så ryger man bagerst i det prioarray
man tilhører og må vente indtil alle andre med højere prioritet og alle
andre med samme prioritet (round robin) har kørt.
2. Hvis man ikke er en interaktiv process, så ryger man i expired listen.
Der venter man så indtil alle andre processer med timeslice tilbage (dem i
aktiv listen) har kørt. Derefter byttes der om på aktiv og expired listn og
vi kører en tur mere.

> Så vidt jeg indtil nu har forstået det, gælder der, at når man ryger i
> expired array'et, så kører man ikke igen, før alle andre processer
> faktisk har kørt mindst een gang.

Det er ikke rigtigt. Man kører ikke før alle andre i aktiv listen har brugt
deres timeslice. Derefter laves der en o(1) operation idet man bytter om på
expired og aktiv listen og alle får mulighed for at køre igen. Man kan godt
forestille sig 2 processer i aktiv, din og en vens. Din ryger i expired
(fordi du har brugt dit tidskvantum), hvorefter din vens ryger i lidt
senere. Derefter skiftes expired og aktiv. Da I begge er (antaget)
højprioritets, så kommer din process hurtigt til igen, altså længe før
_alle_ andre har kørt.

> Okay, nice-værdien skulle angiveligt være fra 100-140, hvor realtime
> prioriteten er de 1-99.
> Hvad er højest prioritet i denne terminologi (når vi arbejder med
> prioritetsmatricen)? Er det 99 der er den højeste prioritet, fordi det
> er højeste realtime prioritet eller er det f.eks. 1 der er højeste
> prioritet og så 140 der er mindste prioritet - eller?

Højesteprioritet er først i priomatricen, så 1 er højeste prioritet.

Thomas

---

Hej igen

>>men hvis man yield'er sig selv skriver Robert Love (Linux Kernel
>>Development), at man ryger helt bagerst - ikke kun i forhold til sin
>>egen prioritet, men faktisk indtil at alle andre processer i systemet
>>har kørt (selv dem med lavere prioritet).
>
>
> Ja det er næsten rigtigt. Når man yielder sig selv (= siger, lad en anden
> køre), så kan der ske følgende:
>
> 1. Hvis man er en interaktiv process, så ryger man bagerst i det prioarray
> man tilhører og må vente indtil alle andre med højere prioritet og alle
> andre med samme prioritet (round robin) har kørt.
> 2. Hvis man ikke er en interaktiv process, så ryger man i expired listen.
> Der venter man så indtil alle andre processer med timeslice tilbage (dem i
> aktiv listen) har kørt. Derefter byttes der om på aktiv og expired listn og
> vi kører en tur mere.

hmm. er det ikke kun den automatiske scheduler_tick() der gør det
ovenstående? (som vist nok kører for hver 1ms)

Robert Love skriver:
"... . It also provides the possibility that an interactive task can
become runnable, but fail to to run again until the array switch occurs,
because the task is stuck in the expired array. Reinserting interactive
tasks back into the active array alleviates this problem. Note that the
task will not run immediately, but will be scheduled round robin with
the other tasks at its priority. The logic to provide this feature is
implemented in scheduler_tick(), which is called via the timer interrupt."

struct task_struct *task = current;
struct runqueue *rq = this_rq();

if (!--task->time_slice) {
if (!TASK_INTERACTIVE(task) || EXPIRED_STARVING(rq))
enqueue_task(task, rq->expired);
else
enqueue_task(task, rq->active);
}



men senere skriver han om systemkaldet:
"Linux provides the sched_yield() system call as a mechanism for a
process to explicitly yield the processor to other waiting processes. It
works by removing the process from the active array (where it currently
is, because it is running) and inserting it into the expired array. This
has the effect of not only preempting the process and putting it at the
end of its priority list, bu putting it on the expired list -
guaranteeing it will not run for a while. ... realtime halløj ... In
earlier versions of Linux, the semantics of the sched_yield() call where
quite different; at best, the task was only moved to the end of their
priority list. The yielding was often not for a very long time.
Nowadays, applications and even kernel code should be certain they truly
want to give up the processor before calling sched_yield()."


Jeg må ærligt indrømme at jeg ikke helt kan se ideen i, at lave
ovenstående, med mindre man også har mulighed for at lave et mini-yield
som bare gør en tilgængelig for en endnu kortere tid. Man skal jo huske,
at man har som standard har 100ms pr. proces i time-slice.

Jeg synes dog også det modstrider lidt denne teori som han skriver endnu
tidligere i sin bog (som ellers lyder rigtig smart):

"Note that a proces does not have to use all its timeslice at once. For
example, a process with a 100 millisecond timeslice does not have to run
for 100 milliseconds in one go or risk losing the remaining timeslice.
Instead, the process can run on five different reschedules for 20
milliseconds each. Thus, a large timeslice also benefits interactive
tasks - while they do not need such a large timeslice all at once, it
ensures they remain runnable for as long as possible"

hvis poller på et eller andet som en interaktiv proces og for hver gang
man konstaterer at noget ikke er opfyldt, så virker det da latterligt,
at man ved at lave den frivillige schedulering mister sin time-slice men
hvordan skulle man ikke miste sin timeslice hvis man laver f.eks. I/O.
Forestil dig at man har bedt om at vente på et keyboard input eller
noget i den stil, og er den sidste i active array'et. Det er nu
registreret at man har brugt f.eks. 5ms af sit timeslice, men har 95ms
tilbage. Imellemtiden bliver active arrayet byttet med expired array'et.
Nu kommer man så tilbage i active-arrayet og har nu faktisk mistet 5ms
af det næste time-slice i forhold til de andre processer?

Efter at have læst mere om scheduleren synes jeg det virker mindre
logisk med de store time-slices! Nogen der kan forklare hvorfor?


>>Så vidt jeg indtil nu har forstået det, gælder der, at når man ryger i
>>expired array'et, så kører man ikke igen, før alle andre processer
>>faktisk har kørt mindst een gang.
>
>
> Det er ikke rigtigt. Man kører ikke før alle andre i aktiv listen har brugt
> deres timeslice. Derefter laves der en o(1) operation idet man bytter om på
> expired og aktiv listen og alle får mulighed for at køre igen. Man kan godt
> forestille sig 2 processer i aktiv, din og en vens. Din ryger i expired
> (fordi du har brugt dit tidskvantum), hvorefter din vens ryger i lidt
> senere. Derefter skiftes expired og aktiv. Da I begge er (antaget)
> højprioritets, så kommer din process hurtigt til igen, altså længe før
> _alle_ andre har kørt.
>
>
>>Okay, nice-værdien skulle angiveligt være fra 100-140, hvor realtime
>>prioriteten er de 1-99.
>>Hvad er højest prioritet i denne terminologi (når vi arbejder med
>>prioritetsmatricen)? Er det 99 der er den højeste prioritet, fordi det
>>er højeste realtime prioritet eller er det f.eks. 1 der er højeste
>>prioritet og så 140 der er mindste prioritet - eller?
>
>
> Højesteprioritet er først i priomatricen, så 1 er højeste prioritet.

Ok. Du lyder til at have styr på det, håber du kan forklare de ting jeg
har skrevet ovenfor.


Mvh / Preben Holm

---

On 2004-06-05, Preben <64bitNOnoNOSPAM@mailme.dk> wrote:

> hmm. er det ikke kun den automatiske scheduler_tick() der gør det
> ovenstående? (som vist nok kører for hver 1ms)

Nu har jeg kun 2.6.5 liggende på mit system, men

asmlinkage long sys_sched_yield(void)
{
runqueue_t *rq = this_rq_lock();
prio_array_t *array = current->array;

/*
* We implement yielding by moving the task into the expired
* queue.
*
* (special rule: RT tasks will just roundrobin in the active
* array.)
*/

Læg mærke til parantesen.

> noget i den stil, og er den sidste i active array'et. Det er nu
> registreret at man har brugt f.eks. 5ms af sit timeslice, men har 95ms
> tilbage. Imellemtiden bliver active arrayet byttet med expired array'et.
> Nu kommer man så tilbage i active-arrayet og har nu faktisk mistet 5ms
> af det næste time-slice i forhold til de andre processer?

Det er vel ligegyldigt hvor stort tidskvant du har ved skiftet. Har du brug
for mere vil den dynamiske heuristik (forhåbenligt) tildele dig mere! Hvis
din process får 100ms ad gangen og den kun bruger 5ms før skift, så vil den
dynamiske prioritet bliver opdateret så du får mindre næste gang (regner jeg
med efter at have læst Loves beskrivelse, jeg har ikke selv nærlæst koden
endnu).

> Efter at have læst mere om scheduleren synes jeg det virker mindre
> logisk med de store time-slices! Nogen der kan forklare hvorfor?

Det er et kompromi. Små timeslices giver hurtige skift mellem CPU bound
processer, men da kontekst skift tager pænt med tid er små timeslices ikke
hensigtsmæssigt set fra en throuhgput situation. For lange timeslices går ud
over interaktiviteten. 100ms er så et kompromi mellem de 2, idet interaktive
processer kan dele deres timeslice op i "bidder" uden at ryge fra aktiv til
expired listen. Derved opnås at dine cpubounds processer bruger alt deres
cpu tid og venter på en ny portion, mens man samtidig skifter hurtigt mellem realtime
processerne idet de hele tiden riger tilbage i aktiv arrayet hvis de er
realtime "nok".

Dyk ned i sourcen Preben, den er skam ganske læsbar!

Mvh Thomas

---

Hej igen

>>hmm. er det ikke kun den automatiske scheduler_tick() der gør det
>>ovenstående? (som vist nok kører for hver 1ms)
>
>
> Nu har jeg kun 2.6.5 liggende på mit system, men
>
> asmlinkage long sys_sched_yield(void)
> {
> runqueue_t *rq = this_rq_lock();
> prio_array_t *array = current->array;
>
> /*
> * We implement yielding by moving the task into the expired
> * queue.
> *
> * (special rule: RT tasks will just roundrobin in the active
> * array.)
> */
>
> Læg mærke til parantesen.

Ja, men netop kun realtime tasks!


>>noget i den stil, og er den sidste i active array'et. Det er nu
>>registreret at man har brugt f.eks. 5ms af sit timeslice, men har 95ms
>>tilbage. Imellemtiden bliver active arrayet byttet med expired array'et.
>>Nu kommer man så tilbage i active-arrayet og har nu faktisk mistet 5ms
>>af det næste time-slice i forhold til de andre processer?
>
>
> Det er vel ligegyldigt hvor stort tidskvant du har ved skiftet. Har du brug
> for mere vil den dynamiske heuristik (forhåbenligt) tildele dig mere! Hvis
> din process får 100ms ad gangen og den kun bruger 5ms før skift, så vil den
> dynamiske prioritet bliver opdateret så du får mindre næste gang (regner jeg
> med efter at have læst Loves beskrivelse, jeg har ikke selv nærlæst koden
> endnu).

Nope, desto mere interaktiv man er, desto større time-slice får man. Op
til 200ms.

Så jeg kan kun se, at det er når man venter på I/O, at man faktisk
bliver sat direkte tilbage i active array'et - og så faktisk også når
ens time-slice er opbrugt!


>>Efter at have læst mere om scheduleren synes jeg det virker mindre
>>logisk med de store time-slices! Nogen der kan forklare hvorfor?
>
>
> Det er et kompromi. Små timeslices giver hurtige skift mellem CPU bound
> processer, men da kontekst skift tager pænt med tid er små timeslices ikke
> hensigtsmæssigt set fra en throuhgput situation. For lange timeslices går ud
> over interaktiviteten. 100ms er så et kompromi mellem de 2, idet interaktive
> processer kan dele deres timeslice op i "bidder" uden at ryge fra aktiv til
> expired listen. Derved opnås at dine cpubounds processer bruger alt deres
> cpu tid og venter på en ny portion, mens man samtidig skifter hurtigt mellem realtime
> processerne idet de hele tiden riger tilbage i aktiv arrayet hvis de er
> realtime "nok".

Men den eneste måde de kan dele deres timeslice op i små bidder, er ved
at lave I/O og vente på I/O.
Man kan vel sige, at bare en proces er interaktiv nok, vil den altid
ryge direkte tilbage i aktiv array'et


> Dyk ned i sourcen Preben, den er skam ganske læsbar!

Er ikke ligefrem den store C-haj, men vil da også prøve på et tidspunkt


Mvh / Preben Holm