* Least laxity first (LLF) is a real-time scheduling algorithm for periodic task
ID: 3605860 • Letter: #
Question
* Least laxity first (LLF) is a real-time scheduling algorithm for periodic tasks. Slack time, or laxity, is the amount of time between when a task would complete if it started now and its next deadline. This is the size of the available scheduling window. Laxity can be expressed as: Laxity = (deadline time) – (current time) – (processor time needed) LLF assigns selects the task with the minimum laxity to execute next. If two or more tasks have the same minimum laxity value, they are served on a FCFS basis.
a. Suppose a task currently has a laxity of t. By how long may the scheduler delay starting this task and still meet its deadline?
b. Suppose a task currently has a laxity of 0. What does this mean?
c. What does it mean if a task has negative laxity?
d. Consider a set of three periodic tasks with the execution profiles of the following table. Develop scheduling diagram similar to those of Figure 10.5 for this set of tasks that compare earliest deadline first and LLF. Assume preemption may occur at 5-ms intervals.
Task
Period
Execution Time
A
6
2
B
8
2
C
12
3
Task
Period
Execution Time
A
6
2
B
8
2
C
12
3
Explanation / Answer
a) If the task has laxity t .it can be started after t time from the current time.So it van be delayed by t before the deadline.
b) Currentl has laxity 0, it means it has to start if it wants to finish before
or at deadline
c) Negative laxity means even if the task starts now it can not be finished before deadline.
d) The priority as per laxity is
C (laxity-9) --Priority - 3
B (laxity-6) --Priority - 2
A (laxity-4) --Priority - 1
0----2----4-5-6-7
A----B----C-----C (completes)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.