Questions and remarks about modeling of probabilistic schedulers

AlexanderF
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 140
Registriert: 2. Mai 2010 17:55

Questions and remarks about modeling of probabilistic schedulers

Beitrag von AlexanderF » 1. Nov 2017 15:37

hello,

on slide 25 of Module 1, a scheduler is defined as a triple (St, Sin, lambda),
consisting of a set of possible scheduler states, a set of possible scheduler inputs, and a scheduling algorithm.
Is it not necessary to specify also a start state or a set of possible start states,
for example for the modeling of a (deterministic) round robin scheduler?

The function lambda is defined on slide 24 as a function from St x Sin to D(N x St).

Is D here the set of all probability distribution?
Does this definition includes that the sum of all probabilities is 1?

On slide 25, the function lambda is required to "deterministically store information about its decision",
which, I think, essentially says that there are no two successor states for one possible scheduler selection.

Could this requirement be omitted by a modeling
that does not use a single function lambda from St x Sin to D(N x St), to present the scheduling algorithm,
but that uses two functions,
one function from St x Sin to D(N), to represent the selection,
and another one from St x Sin x N to St, to represent the state change depending also on the selection?

best regards,
Alexander

ximl
Erstie
Erstie
Beiträge: 12
Registriert: 4. Okt 2017 17:12

Re: Questions and remarks about modeling of probabilistic schedulers

Beitrag von ximl » 8. Nov 2017 17:34

Hi Alexander,

Your idea on having initial states for schedulers is sensible --
scheduler definitions along this line exist in the literature.
An alternative design choice is to impose the initial state
for a (deterministic) scheduler in the definition of a notion
of "derivation sequences under scheduling" -- the scheduler
does not have a built-in notion of initial state, but we always
specify from which scheduler state each derivation sequence
starts. Note that we did not cover derivation sequences under
scheduling, or their probabilities (in the probabilistic case)
in the module.

D(A) is written for the set of all probability distributions over A.
For each probability distribution, the sum of all probabilities is 1.

Your alternative modeling of the scheduling algorithm with
two functions instead of one separates the selection and the
state transition more, but I agree that it also captures the
intuition of "scheduler deterministically stores information
about its decision".

Best regards,
Ximeng

AlexanderF
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 140
Registriert: 2. Mai 2010 17:55

Re: Questions and remarks about modeling of probabilistic schedulers

Beitrag von AlexanderF » 10. Nov 2017 21:14

Thank you for the answer!

best regards,
Alexander

Antworten

Zurück zu „Archiv“