EDF POLLING SERVER
Harish Chetty
Lots of Problems!
• Had to read about 20,000 Lines of Code Spread across 7 unrelated files.
• Had to read through 2000 mor...
IMAGINE A CLOCK!
Rings Bell Every 60 Seconds Period : 60 sec
Must Ring Bell for 5 Seconds Budget: 5 sec
Complete Ringing i...
Submit
Task
Setup
Deadline
& Budget
Enqueue
Task
Dequeue
Task
Budget Exhausted
Budget Left
When the task must end!
How muc...
Submit
Task
Setup
Deadline (D),
Budget (B)
& Replenishment
Timer (RT)
Enqueue
Task
Dequeue
Task
B = Cap
RT Timeout
B = 0
?...
Submit
Task
Setup(D), (B)
& (RT)
Enqueue
Task
Dequeue
Task
B = (RQ TIME – START TIME)
RT Timeout
B = 0
Task
Dead
TASK COMP...
Submit
Task
Setup(D), (B)
& (RT)
Enqueue
Task
Dequeue
Task
B = (RQ TIME – START TIME)
RT Timeout
B = 0
Task
Dead
TASK COMP...
Submit
Task
Setup(D), (B)
& (RT)
Enqueue
Task
Dequeue
Task
B = (RQ TIME – START TIME)
RT Timeout
B = 0
Task
Dead
TASK COMP...
WHAT IF MORE THAN ONE TASK?
WHAT IF MORE THAN ONE TYPE OF TASK?
SCHED_OTHER
(CFS)
SCHED_RT SCHED_DEADLINE
BATCH IDLE
NORMAL EDFFIFO
ROUND
ROBIN
IDLE TASK SCHED_POLL
99 to 0132 to 100> 13...
Submit
Task
Setup(D), (B)
& (RT)
Enqueue
Task
P = -2
Dequeue
Task
B = (RQ TIME – START TIME)
RT Timeout
B = 0
Task
Dead
TA...
Submit
Task
Setup(D), (B)
& (RT)
Enqueue
Task
P = -2
Dequeue
Task
B = (RQ TIME – START TIME)
RT Timeout
B = 0
Task
Dead
TA...
WHAT IF MORE THAN ONE CPU?
Submit
Task
Setup(D), (B)
& (RT)
Enqueue
Task
P = -2
Dequeue
Task
B = (RQ TIME – START TIME)
RT Timeout
B = 0
Task
Dead
TA...
Submit
Task
Setup(D), (B)
& (RT)
Enqueue
Task
P = -2
Dequeue
Task
B = (RQ TIME – START TIME)
RT Timeout
B = 0
Task
Dead
TA...
WHAT IF MORE THAN ONE SCHED_POLL TASK?
Submit
Task
Setup(D), (B)
& (RT)
Enqueue
Task
P = -2
Dequeue
Task
B = (RQ TIME – START TIME)
RT Timeout
B = 0
Task
Dead
TA...
volatile long long int count =0;
while(1){
if(count<1000000){
count++;
printf("Printing number %lld n", count);
}
else{
br...
I WILL STOP BORING YOU AND END!
EXTRAS
Data Structures
• Pick Next Tasks use RB Trees based on Deadlines.
• Leftmost Node is cached (smallest Deadline)
• CPU’s w...
Submit
Task
Setup
Deadline
& Budget
Enqueue
Task
Dequeue
Task
Budget Left = 0
Budget Left != 0
When the task must end!
How...
Submit
Task
Setup(D), (B)
& (RT)
Enqueue
Task
P = -2
Dequeue
Task
B = (RQ TIME – START TIME)
RT Timeout
B = 0
Task
Dead
TA...
Polling server
Polling server
Polling server
of 26

Polling server

The project is a polling server for aperiodic tasks (SCHED_POLL) based on Earliest Deadline First (SCHED_DEADLINE) on Linux Kernel v3.15.1. The scheduler uses various threshold limiters for each tasks based on RB trees and also stores address of the leftmost element/node (to determine earliest task ). Currently it does extremely quick task scheduling (due to storing of leftmost element) but has an error ratio of 5% w.r.t. to ideal conditions.
Published on: Mar 4, 2016
Published in: Technology      
Source: www.slideshare.net


Transcripts - Polling server

  • 1. EDF POLLING SERVER Harish Chetty
  • 2. Lots of Problems! • Had to read about 20,000 Lines of Code Spread across 7 unrelated files. • Had to read through 2000 more lines to interpret Mark’s Sporadic server! • Understood about 20% code (which I thought was 80% at the beginning). • Reinstalled Kernel about 500 Times. • Found out limitations of printk’s! • Some crash caused Disk(or something to corrupt) forcing use of TTY. • SMP’s made life hell. • CBS ensured PS to always fail! • Finally the last phase was carried out on kernel which took 20 minutes to compile. • HAD TO FINALLY UNDERSTAND ABOUT 50% TO GET STUFF DONE!
  • 3. IMAGINE A CLOCK! Rings Bell Every 60 Seconds Period : 60 sec Must Ring Bell for 5 Seconds Budget: 5 sec Complete Ringing in 10 Second Deadline: 10 sec
  • 4. Submit Task Setup Deadline & Budget Enqueue Task Dequeue Task Budget Exhausted Budget Left When the task must end! How much time the task should run? ? Task Dead TASK COMPLETE/KILL KILL Wakeup task, Run the task, Update Runqueues etc. Schedule task, Block the task, Push task in wating queue etc.
  • 5. Submit Task Setup Deadline (D), Budget (B) & Replenishment Timer (RT) Enqueue Task Dequeue Task B = Cap RT Timeout B = 0 ? Task Dead TASK COMPLETE/KILL KILL INIT Task Release Replenishment Timer (RT)
  • 6. Submit Task Setup(D), (B) & (RT) Enqueue Task Dequeue Task B = (RQ TIME – START TIME) RT Timeout B = 0 Task Dead TASK COMPLETE/KILL KILL INIT Task Task Running Update Status B = Cap B = Cap B = 0 CPU RUNQUEUE TIME INITIAL BUDGET Release (RT)
  • 7. Submit Task Setup(D), (B) & (RT) Enqueue Task Dequeue Task B = (RQ TIME – START TIME) RT Timeout B = 0 Task Dead TASK COMPLETE/KILL KILL INIT Task Task Running Update Status B = 0 / B = Cap B = Cap B = 0 Release (RT)
  • 8. Submit Task Setup(D), (B) & (RT) Enqueue Task Dequeue Task B = (RQ TIME – START TIME) RT Timeout B = 0 Task Dead TASK COMPLETE/KILL KILL INIT Task Task Running Update Status B = 0 / B >= Cap B = Cap B = (0 + P) OVERRUN TIME (Penalty (P)) Release (RT)
  • 9. WHAT IF MORE THAN ONE TASK? WHAT IF MORE THAN ONE TYPE OF TASK?
  • 10. SCHED_OTHER (CFS) SCHED_RT SCHED_DEADLINE BATCH IDLE NORMAL EDFFIFO ROUND ROBIN IDLE TASK SCHED_POLL 99 to 0132 to 100> 132 -1 -2
  • 11. Submit Task Setup(D), (B) & (RT) Enqueue Task P = -2 Dequeue Task B = (RQ TIME – START TIME) RT Timeout B = 0 Task Dead TASK COMPLETE/KILL KILL INIT Task Task Running Update Status B = 0 / B >= Cap B = Cap B = (0 + P) Release (RT)
  • 12. Submit Task Setup(D), (B) & (RT) Enqueue Task P = -2 Dequeue Task B = (RQ TIME – START TIME) RT Timeout B = 0 Task Dead TASK COMPLETE/KILL KILL INIT Task Task Running Update Status B = 0 / B >= Cap B = Cap B = (0 + P) Release (RT) Forward RQ TIME == Deadline! D = D + D Why NOT 2D ?? Here comes Periods!
  • 13. WHAT IF MORE THAN ONE CPU?
  • 14. Submit Task Setup(D), (B) & (RT) Enqueue Task P = -2 Dequeue Task B = (RQ TIME – START TIME) RT Timeout B = 0 Task Dead TASK COMPLETE/KILL KILL INIT Task Task Running Update Status B = 0 / B >= Cap B = Cap B = (0 + P) Release (RT) Forward RQ TIME == Deadline! D = D + D SMP Enqueue Task P = -2 SMP Dequeue Task RT Timeout B = 0 B = (0 + P) N(CPU) > 1
  • 15. Submit Task Setup(D), (B) & (RT) Enqueue Task P = -2 Dequeue Task B = (RQ TIME – START TIME) RT Timeout B = 0 Task Dead TASK COMPLETE/KILL KILL INIT Task Task Running Update Status B = 0 / B >= Cap B = Cap B = (0 + P) Release (RT) Forward RQ TIME == Deadline! D = D + D SMP Enqueue Task P = -2 SMP Dequeue Task RT Timeout B = 0 B = (0 + P) N(CPU) > 1 Select CPU
  • 16. WHAT IF MORE THAN ONE SCHED_POLL TASK?
  • 17. Submit Task Setup(D), (B) & (RT) Enqueue Task P = -2 Dequeue Task B = (RQ TIME – START TIME) RT Timeout B = 0 Task Dead TASK COMPLETE/KILL KILL INIT Task Task Running Update Status B = 0 / B >= Cap B = Cap B = (0 + P) Release (RT) Forward RQ TIME == Deadline! D = D + D SMP Enqueue Task P = -2 SMP Dequeue Task RT Timeout B = 0 B = (0 + P) N(CPU) > 1 Select CPU Pick Next Task Preempt verifier
  • 18. volatile long long int count =0; while(1){ if(count<1000000){ count++; printf("Printing number %lld n", count); } else{ break; } }
  • 19. I WILL STOP BORING YOU AND END!
  • 20. EXTRAS
  • 21. Data Structures • Pick Next Tasks use RB Trees based on Deadlines. • Leftmost Node is cached (smallest Deadline) • CPU’s work using Max Heaps based on task deadlines. • Root Node has CPU with a task with the largest Deadline. Preempt this first if necessary • Must be a Queue for more efficiency?? • Waiting Tasks use RB Trees based on Deadlines. • Leftmost Node is cached (smallest Deadline)
  • 22. Submit Task Setup Deadline & Budget Enqueue Task Dequeue Task Budget Left = 0 Budget Left != 0 When the task must end! How much time the task should run? ? Wakeup task, Run the task, Update Runqueues etc. Schedule task, Block the task, Push task in wating queue etc.
  • 23. Submit Task Setup(D), (B) & (RT) Enqueue Task P = -2 Dequeue Task B = (RQ TIME – START TIME) RT Timeout B = 0 Task Dead TASK COMPLETE/KILL KILL INIT Task Task Running Update Status B = 0 / B >= Cap B = Cap B = (0 + P) Release (RT) Forward RQ TIME == Deadline! D = D + D SMP Enqueue Task P = -2 SMP Dequeue Task RT Timeout B = 0 B = (0 + P) N(CPU) > 1 Select CPU Pick Next Task

Related Documents