Questions for Q/A Session on Monday

Dear all,

a successful and healthy summer term to all of you also from my side!

Please post your questions for the Q/A session on Monday under this topic.
It would be great for me to have the questions already at Friday noon in case
I should plan to prepare some slides etc. for the answer.
The Q/A session on Monday will take place via zoom as announced.

By the way, you have to register for this forum with an arbitrary login and an arbitrary
password before posting your contributions.

Best regards
Christoph Scholl

Dear Prof. Scholl,

I have some questions regarding the last lecture:

- I haven't studied "partial order" before (discussed in Week2_rtos-3_rtos_schedule_part2), and I would like to know if it is fundamental to understand the lectures.

- In Week2_rtos-3_rtos_schedule_part2, you present some algorithms to deal with overload, and I'm unsure about into which category these algorithms fall. I understood that guarantee-based algorithms are optimal algorithms, while best-effort algorithms are heuristic ones; or am I wrong? And also, what would algorithms based on imprecise computation be?

- Graham theorem says that certain conditions can increase schedule length. But there are other cases in which the schedule length can be the same or even improve? I mean, it's not a rule for all cases, right?

Regards,

David

Dear Prof. Scholl,
in your additional theoreme to Graham`s you don´t mention that the tasks need fix prioritys or prioritys at all, your example does make this requirement, if I see this correct. Would there be an example found if all task have the same priority?
Regards,
Franziska Gerhards

Dear DavidBM,

I will be available for live answers on Monday, but I am
going to start giving some answers::-)

> - I haven't studied "partial order" before
> (discussed in Week2_rtos-3_rtos_schedule_part2),
> and I would like to know if it is fundamental to
> understand the lectures.

It is fundamental to understand what precedence constraints are.
Precedence constrarints are special case for partial orders on the
set of tasks and for computer science in general it would be good to
know what partial orders are (not for this lecture in particular).
Anyway - it is not a difficult concept. I can add some remarks on Monday.

> - In Week2_rtos-3_rtos_schedule_part2, you present
> some algorithms to deal with overload, and I'm
> unsure about into which category these algorithms
> fall. I understood that guarantee-based algorithms
> are optimal algorithms, while best-effort
> algorithms are heuristic ones; or am I wrong? And
> also, what would algorithms based on imprecise
> computation be?

Hm, the main difference between guarantee-based and best-effort is that
for guarantee-based you admit a task only if you can guarantee under
worst-case conditions that the task set remains schedulable after admitting the new task.
A best-effort algorithm admits tasks even if it is not *guaranteed* that the new task
causes scheduling problems, i.e. best-effort is just optimistic.
Guarantee-based and best-effort algorithms are for hard deadlines,
imprecise computation for soft deadlines with mandatory and optional parts.
The notion "imprecise" may result from the intuition that the algorithm
computes a preliminary, imprecise result during the mandatory part which
is further optimized during the optional part (think of an algorithm iteratively improving
the result).


> - Graham theorem says that certain conditions can
> increase schedule length. But there are other
> cases in which the schedule length can be the same
> or even improve? I mean, it's not a rule for all
> cases, right?

Yes, you are right. As the name "scheduling anomalies" suggests:
You would "normally" assume that adding ressources improves the schedules
and in most cases this will also happen. But as shown: Not in all cases.

Best regards
Christoph Scholl

Dear F. Gerhards,

> in your additional theoreme to Graham`s you don´t
> mention that the tasks need fix prioritys or
> prioritys at all, your example does make this
> requirement, if I see this correct. Would there be
> an example found if all task have the same
> priority?

I have two additional theorems going beyond Graham's theorem.
I think you refer to the first one.
For the first one, I introduced a fixed allocation of tasks to processors
and precedence constraints which bring the tasks on a single processor
in a total order. Thus, priorities would not have any additional effect for this example.

Best regards
Christoph Scholl

Dear Mr. Scholl,
Ah, yes. I have overseen (do you even say this in english? Haven´t used english in a while...) the first part saying "some fixed priority assignment".
So if I see this correct in the examples given these fixed prioritys and the condition of not having any idle time on a processor are the main "problems" why the behavior isn´t as expected?
(I will be in the live lesson on Monday, so you can answer the question there)
Best regards,
Franziska Gerhards
(Sorry, just heared the discussion about the theorem at the end of the lesson "Schedule Teil 2" and what you say there is exactly what I mentioned above)



2 mal bearbeitet. Zuletzt am 23.05.2020 09:03 von F. Gerhards.

Dear Mr. Scholl,
I have a question regarding the last lecture "aperiodic scheduling part2" slide 24:
I don´t quite get the point of this slide. Do we want to show that EDF is helpfull for consindering wether a new task should be accepted by fulfilling quaranteed-based scheduling conditions? And why don`t we have to check wether the following tasks after the new task was queued into the new schedule will miss their deadlines now?
Maybe you could briefly recapitulate this slide in the q/a session on monday.
Best regards,
Franziska Gerhards

Dear Mr.Scholl,
I have a question regarding lecture 5b from this week 9: In the end it is said that "Under the Priority Ceiling Protocol, a job Ji can be blocked for at most the duration of one critical section." So this means the response time of a job Ji would increase by at most bmax= lenght of the longest critical section requested by Ji? So how would you compute this Response time? We just always had the example with periodic task (maybe we had examples befor for no-periodic tasks and I just don´t remeber...?) Ji can be interupted by tasks with higher priority, but we can not say when which task will interrupt at which time in advance, do we?
Maybe you could briefly talk about this at mondays session? Or is this something that will be discussed in the wcet-part?
Best regards,
Franziska Gerhards



1 mal bearbeitet. Zuletzt am 07.07.2020 13:45 von F. Gerhards.