diff options
author | Zelin Tong <ztong@ludwig.cs.unc.edu> | 2020-03-05 18:22:27 -0500 |
---|---|---|
committer | Zelin Tong <ztong@ludwig.cs.unc.edu> | 2020-03-05 18:22:27 -0500 |
commit | 1cf95dfd3e5be213d598abdf927c317a1b621b99 (patch) | |
tree | ac1d9aff01c0980073028f5e162413f9aa0aae82 | |
parent | 2a258b89af94406f23a1d93cc097de0bf91c45ff (diff) |
changes to budget tracking and scheduling
consolidated container budget tracking
properly excluded fully provisioned containers and their cpus from gedf
gschedule no longer returns non-rt tasks
-rw-r--r-- | litmus/sched_edfsc.c | 94 |
1 files changed, 44 insertions, 50 deletions
diff --git a/litmus/sched_edfsc.c b/litmus/sched_edfsc.c index 218123d99514..754891b8c12f 100644 --- a/litmus/sched_edfsc.c +++ b/litmus/sched_edfsc.c | |||
@@ -64,9 +64,9 @@ static rt_domain_t gsched_domain; | |||
64 | u64 m_util, future_m_util; | 64 | u64 m_util, future_m_util; |
65 | u64 sys_util, future_sys_util; | 65 | u64 sys_util, future_sys_util; |
66 | 66 | ||
67 | // FIXME something's fishy here -- is_migrating shouldn't be stronger than is_container right? | ||
68 | #define is_container(task) ((task) && tsk_rt(task)->edfsc_params.domain != NULL && tsk_rt(task)->domain == &gsched_domain) | 67 | #define is_container(task) ((task) && tsk_rt(task)->edfsc_params.domain != NULL && tsk_rt(task)->domain == &gsched_domain) |
69 | #define is_fixed(task) ((task) && tsk_rt(task)->edfsc_params.container_task != NULL) | 68 | #define is_fixed(task) ((task) && tsk_rt(task)->edfsc_params.container_task != NULL) |
69 | //migrating task can temporarily have a container_task when it is being background scheduled | ||
70 | #define is_migrating(task) ((task) && tsk_rt(task)->edfsc_params.domain == NULL && tsk_rt(task)->domain == &gsched_domain) | 70 | #define is_migrating(task) ((task) && tsk_rt(task)->edfsc_params.domain == NULL && tsk_rt(task)->domain == &gsched_domain) |
71 | 71 | ||
72 | #define FP_SHIFT 20 | 72 | #define FP_SHIFT 20 |
@@ -145,7 +145,7 @@ static int cpu_lower_prio(struct bheap_node *_a, struct bheap_node *_b) | |||
145 | /* Note that a and b are inverted: we want the lowest-priority CPU at | 145 | /* Note that a and b are inverted: we want the lowest-priority CPU at |
146 | * the top of the heap. | 146 | * the top of the heap. |
147 | */ | 147 | */ |
148 | return (is_container(b->linked) && get_rt_utilization(b->linked) == to_fp(1)) || edf_higher_prio(b->linked, a->linked); | 148 | return edf_higher_prio(b->linked, a->linked); |
149 | } | 149 | } |
150 | 150 | ||
151 | /* caller must hold g_lock */ | 151 | /* caller must hold g_lock */ |
@@ -340,7 +340,6 @@ static void g_preempt_check(void) | |||
340 | edf_preemption_needed(&gsched_domain, last->linked); | 340 | edf_preemption_needed(&gsched_domain, last->linked); |
341 | last = lowest_prio_cpu()) { | 341 | last = lowest_prio_cpu()) { |
342 | target = last; | 342 | target = last; |
343 | BUG_ON(is_container(last->linked) && get_rt_utilization(last->linked) == to_fp(1)); | ||
344 | 343 | ||
345 | /* preemption necessary */ | 344 | /* preemption necessary */ |
346 | task = __take_ready(&gsched_domain); | 345 | task = __take_ready(&gsched_domain); |
@@ -439,8 +438,6 @@ static noinline void g_job_completion(struct task_struct* t, int forced) | |||
439 | BUG_ON(!t); | 438 | BUG_ON(!t); |
440 | sched_trace_task_completion(t, forced); | 439 | sched_trace_task_completion(t, forced); |
441 | 440 | ||
442 | cpu_entry_t* entry; | ||
443 | |||
444 | TRACE_TASK(t, "job_completion(forced=%d).\n", forced); | 441 | TRACE_TASK(t, "job_completion(forced=%d).\n", forced); |
445 | 442 | ||
446 | /* set flags */ | 443 | /* set flags */ |
@@ -478,17 +475,21 @@ static noinline void g_job_completion(struct task_struct* t, int forced) | |||
478 | tsk_rt(t)->edfsc_params.can_release = 0; | 475 | tsk_rt(t)->edfsc_params.can_release = 0; |
479 | tsk_rt(t)->task_params.exec_cost = from_fp(get_rt_utilization(t) * get_rt_period(t)); | 476 | tsk_rt(t)->task_params.exec_cost = from_fp(get_rt_utilization(t) * get_rt_period(t)); |
480 | prepare_for_next_period(t); | 477 | prepare_for_next_period(t); |
478 | cpu_entry_t* entry = &per_cpu(edfsc_cpu_entries, tsk_rt(t)->edfsc_params.id); | ||
481 | if (is_early_releasing(t) || is_released(t, litmus_clock())) | 479 | if (is_early_releasing(t) || is_released(t, litmus_clock())) |
482 | sched_trace_task_release(t); | 480 | sched_trace_task_release(t); |
483 | if (get_rt_utilization(t) == to_fp(1)) { | 481 | if (get_rt_utilization(t) == to_fp(1)) { |
484 | cpu_entry_t* entry = &per_cpu(edfsc_cpu_entries, tsk_rt(t)->edfsc_params.id); | 482 | if (bheap_node_in_heap(entry->hn)) |
485 | remove_cpu_from_global(entry); | 483 | remove_cpu_from_global(entry); |
486 | entry->linked = t; | 484 | entry->linked = t; |
487 | tsk_rt(t)->linked_on = entry->cpu; | 485 | tsk_rt(t)->linked_on = entry->cpu; |
488 | cancel_idle_enforcement_timer(t); | 486 | if (is_queued(t)) |
487 | remove(&gsched_domain, t); | ||
488 | manage_idle_enforcement_timer(t); | ||
489 | preempt(entry); | 489 | preempt(entry); |
490 | } | 490 | } |
491 | else { | 491 | else { |
492 | update_cpu_position(entry); | ||
492 | if (is_current_running()) { | 493 | if (is_current_running()) { |
493 | if (tsk_rt(t)->edfsc_params.domain->scheduled) { | 494 | if (tsk_rt(t)->edfsc_params.domain->scheduled) { |
494 | requeue(tsk_rt(t)->edfsc_params.domain->scheduled); | 495 | requeue(tsk_rt(t)->edfsc_params.domain->scheduled); |
@@ -518,6 +519,7 @@ static void c_job_completion(struct task_struct* t, int forced) | |||
518 | } | 519 | } |
519 | } else { | 520 | } else { |
520 | prepare_for_next_period(t); | 521 | prepare_for_next_period(t); |
522 | requeue(t); | ||
521 | } | 523 | } |
522 | } | 524 | } |
523 | 525 | ||
@@ -527,13 +529,18 @@ static void g_finish_switch(struct task_struct *prev) | |||
527 | cpu_entry_t* entry = this_cpu_ptr(&edfsc_cpu_entries); | 529 | cpu_entry_t* entry = this_cpu_ptr(&edfsc_cpu_entries); |
528 | BUG_ON(is_realtime(current) && tsk_rt(current)->domain == NULL); | 530 | BUG_ON(is_realtime(current) && tsk_rt(current)->domain == NULL); |
529 | 531 | ||
530 | if (!is_container(entry->linked)) { | 532 | entry->scheduled = is_realtime(current) ? current : NULL; |
531 | entry->scheduled = is_realtime(current) ? current : NULL; | 533 | if (entry->scheduled) { |
532 | if (entry->scheduled) | 534 | // when a task is being scheduled under a container, container_task exists |
533 | entry->scheduled = (is_fixed(current)) ? tsk_rt(current)->edfsc_params.container_task : current; | 535 | struct task_struct* t = tsk_rt(current)->edfsc_params.container_task; |
536 | entry->scheduled = (t) ? t : current; | ||
534 | } | 537 | } |
535 | else | 538 | // occurs when current is non-rt, and linked is a container |
539 | // this happens when an empty container "task" is supposed to be current | ||
540 | // but because it's not a real task, a non-rt task is current instead | ||
541 | else if (is_container(entry->linked)) { | ||
536 | entry->scheduled = entry->linked; | 542 | entry->scheduled = entry->linked; |
543 | } | ||
537 | #ifdef WANT_ALL_SCHED_EVENTS | 544 | #ifdef WANT_ALL_SCHED_EVENTS |
538 | TRACE_TASK(prev, "switched away from\n"); | 545 | TRACE_TASK(prev, "switched away from\n"); |
539 | #endif | 546 | #endif |
@@ -549,9 +556,8 @@ static int fifo_prio(struct bheap_node* _a, struct bheap_node* _b) | |||
549 | * Called with g_lock already held | 556 | * Called with g_lock already held |
550 | * @param cedf Pointer to tsk_rt(container)->edfsc_params->domain | 557 | * @param cedf Pointer to tsk_rt(container)->edfsc_params->domain |
551 | * @param prev Previous task running on this processor before schedule was called | 558 | * @param prev Previous task running on this processor before schedule was called |
552 | * @returns `cedf->container` if no fixed task is next | ||
553 | */ | 559 | */ |
554 | static struct task_struct* edfsc_cschedule(cont_domain_t* cedf, struct task_struct * prev) | 560 | static void edfsc_cschedule(cont_domain_t* cedf, struct task_struct * prev) |
555 | { | 561 | { |
556 | rt_domain_t *edf = &cedf->domain; | 562 | rt_domain_t *edf = &cedf->domain; |
557 | 563 | ||
@@ -577,7 +583,7 @@ static struct task_struct* edfsc_cschedule(cont_domain_t* cedf, struct task_stru | |||
577 | && budget_exhausted(cedf->scheduled); | 583 | && budget_exhausted(cedf->scheduled); |
578 | np = exists && is_np(cedf->scheduled); | 584 | np = exists && is_np(cedf->scheduled); |
579 | sleep = exists && is_completed(cedf->scheduled); | 585 | sleep = exists && is_completed(cedf->scheduled); |
580 | preempt = !is_realtime(prev) || is_migrating(prev) || edf_preemption_needed(edf, prev); | 586 | preempt = (is_migrating(prev) && __peek_ready(edf)) || edf_preemption_needed(edf, prev); |
581 | 587 | ||
582 | /* If we need to preempt do so. | 588 | /* If we need to preempt do so. |
583 | * The following checks set resched to 1 in case of special | 589 | * The following checks set resched to 1 in case of special |
@@ -620,9 +626,6 @@ static struct task_struct* edfsc_cschedule(cont_domain_t* cedf, struct task_stru | |||
620 | * release queue (if it completed). requeue() picks | 626 | * release queue (if it completed). requeue() picks |
621 | * the appropriate queue. | 627 | * the appropriate queue. |
622 | */ | 628 | */ |
623 | if (cedf->scheduled && !blocks) | ||
624 | requeue(cedf->scheduled); | ||
625 | |||
626 | next = __take_ready(edf); | 629 | next = __take_ready(edf); |
627 | } else | 630 | } else |
628 | /* Only override Linux scheduler if we have a real-time task | 631 | /* Only override Linux scheduler if we have a real-time task |
@@ -650,28 +653,15 @@ static struct task_struct* edfsc_cschedule(cont_domain_t* cedf, struct task_stru | |||
650 | } | 653 | } |
651 | } | 654 | } |
652 | 655 | ||
653 | //XXX possible error in logic here | ||
654 | // FIXME definite error: next can be NULL (it definitely is when there are | ||
655 | // no real tasks in the system). | ||
656 | if (next) { | ||
657 | cedf->changed_budget = (budget_remaining(next) > budget_remaining(cedf->container)) | ||
658 | ? budget_remaining(cedf->container) - budget_remaining(next) : 0; | ||
659 | cedf->scheduled_last_exec_time = get_exec_time(next); | ||
660 | tsk_rt(next)->job_params.exec_time -= cedf->changed_budget; | ||
661 | } | ||
662 | |||
663 | cedf->scheduled = next; | 656 | cedf->scheduled = next; |
664 | |||
665 | return (next) ? next : cedf->container; | ||
666 | } | 657 | } |
667 | 658 | ||
668 | |||
669 | //assuming prev is previous task running on the processor before calling schedule | 659 | //assuming prev is previous task running on the processor before calling schedule |
670 | static struct task_struct *edfsc_gschedule(struct task_struct *prev) | 660 | static struct task_struct *edfsc_gschedule(struct task_struct *prev) |
671 | { | 661 | { |
672 | cpu_entry_t* entry = this_cpu_ptr(&edfsc_cpu_entries); | 662 | cpu_entry_t* entry = this_cpu_ptr(&edfsc_cpu_entries); |
673 | int out_of_time, sleep, preempted, np, exists, blocks, is_cont; | 663 | int out_of_time, sleep, preempted, np, exists, blocks, is_cont; |
674 | struct task_struct* next = NULL; | 664 | struct task_struct* next; |
675 | unsigned long flags; | 665 | unsigned long flags; |
676 | 666 | ||
677 | raw_spin_lock_irqsave(&g_lock, flags); | 667 | raw_spin_lock_irqsave(&g_lock, flags); |
@@ -767,7 +757,7 @@ static struct task_struct *edfsc_gschedule(struct task_struct *prev) | |||
767 | // make container only be scheduled on cores with same id | 757 | // make container only be scheduled on cores with same id |
768 | if (!entry->linked) { | 758 | if (!entry->linked) { |
769 | struct task_struct* task = __take_ready(&gsched_domain); | 759 | struct task_struct* task = __take_ready(&gsched_domain); |
770 | cpu_entry_t* target = entry; | 760 | cpu_entry_t* target = entry; |
771 | if (is_container(task)) { | 761 | if (is_container(task)) { |
772 | target = &per_cpu(edfsc_cpu_entries, tsk_rt(task)->edfsc_params.id); | 762 | target = &per_cpu(edfsc_cpu_entries, tsk_rt(task)->edfsc_params.id); |
773 | } | 763 | } |
@@ -781,17 +771,17 @@ static struct task_struct *edfsc_gschedule(struct task_struct *prev) | |||
781 | } | 771 | } |
782 | 772 | ||
783 | BUG_ON(entry->linked && budget_exhausted(entry->linked)); | 773 | BUG_ON(entry->linked && budget_exhausted(entry->linked)); |
774 | BUG_ON(!bheap_node_in_heap(entry->hn) && tsk_rt(entry->linked)->edfsc_params.id != entry->cpu); | ||
784 | 775 | ||
785 | /* The final scheduling decision. Do we need to switch for some reason? | 776 | /* The final scheduling decision. Do we need to switch for some reason? |
786 | * If linked is different from scheduled, then select linked as next. | 777 | * If linked is different from scheduled, then select linked as next. |
787 | */ | 778 | */ |
779 | next = NULL; | ||
788 | if ((!np || blocks) && entry->linked != entry->scheduled) { | 780 | if ((!np || blocks) && entry->linked != entry->scheduled) { |
789 | /* Schedule a linked job? */ | 781 | /* Schedule a linked job? */ |
790 | if (entry->linked) { | 782 | if (entry->linked) { |
791 | entry->linked->rt_param.scheduled_on = entry->cpu; | 783 | entry->linked->rt_param.scheduled_on = entry->cpu; |
792 | next = entry->linked; | 784 | next = entry->linked; |
793 | if (is_container(next)) | ||
794 | next = edfsc_cschedule(tsk_rt(next)->edfsc_params.domain, prev); | ||
795 | TRACE_TASK(next, "scheduled_on = P%d\n", smp_processor_id()); | 785 | TRACE_TASK(next, "scheduled_on = P%d\n", smp_processor_id()); |
796 | } | 786 | } |
797 | if (entry->scheduled) { | 787 | if (entry->scheduled) { |
@@ -800,11 +790,13 @@ static struct task_struct *edfsc_gschedule(struct task_struct *prev) | |||
800 | TRACE_TASK(entry->scheduled, "scheduled_on = NO_CPU\n"); | 790 | TRACE_TASK(entry->scheduled, "scheduled_on = NO_CPU\n"); |
801 | } | 791 | } |
802 | } else { | 792 | } else { |
803 | BUG_ON(entry->linked != entry->scheduled); | 793 | if (exists) |
804 | if (is_container(entry->scheduled)) | 794 | next = prev; |
805 | next = edfsc_cschedule(tsk_rt(entry->scheduled)->edfsc_params.domain, prev); | ||
806 | } | 795 | } |
807 | 796 | ||
797 | if (is_container(next)) | ||
798 | edfsc_cschedule(tsk_rt(next)->edfsc_params.domain, prev); | ||
799 | |||
808 | sched_state_task_picked(); | 800 | sched_state_task_picked(); |
809 | 801 | ||
810 | raw_spin_unlock_irqrestore(&g_lock, flags); | 802 | raw_spin_unlock_irqrestore(&g_lock, flags); |
@@ -818,15 +810,11 @@ static struct task_struct *edfsc_gschedule(struct task_struct *prev) | |||
818 | TRACE("becomes idle at %llu.\n", litmus_clock()); | 810 | TRACE("becomes idle at %llu.\n", litmus_clock()); |
819 | #endif | 811 | #endif |
820 | 812 | ||
821 | // If next is a container, then edfsc_cschedule() found nothing to schedule | 813 | // if no fixed tasks to be scheduled by the container, then container->scheduled |
814 | // should be the previous non-rt task if any | ||
822 | if (is_container(next)) { | 815 | if (is_container(next)) { |
823 | manage_idle_enforcement_timer(next); | 816 | manage_idle_enforcement_timer(next); |
824 | return NULL; | 817 | return tsk_rt(next)->edfsc_params.domain->scheduled; |
825 | } | ||
826 | // XXX: Maybe this should be entry->linked | ||
827 | else if (next == prev && is_container(entry->scheduled)) { | ||
828 | manage_idle_enforcement_timer(entry->scheduled); | ||
829 | return next; | ||
830 | } | 818 | } |
831 | else | 819 | else |
832 | return next; | 820 | return next; |
@@ -857,8 +845,10 @@ static enum hrtimer_restart container_boundary(struct hrtimer *timer) | |||
857 | 845 | ||
858 | for (i = 0; i < num_cpus; i++) { | 846 | for (i = 0; i < num_cpus; i++) { |
859 | t = container_list[i]->container; | 847 | t = container_list[i]->container; |
860 | if (tsk_rt(t)->linked_on != NO_CPU && container_list[i]->scheduled == NULL) | 848 | if (container_list[i]->timer_armed) |
861 | tsk_rt(t)->job_params.exec_time += now - container_list[i]->scheduled_last_exec_time; | 849 | tsk_rt(t)->job_params.exec_time += now - container_list[i]->scheduled_last_exec_time; |
850 | else | ||
851 | tsk_rt(t)->job_params.exec_time = get_exec_cost(t); | ||
862 | } | 852 | } |
863 | 853 | ||
864 | t = NULL; | 854 | t = NULL; |
@@ -987,9 +977,12 @@ static enum hrtimer_restart container_boundary(struct hrtimer *timer) | |||
987 | sched_trace_task_release(t); | 977 | sched_trace_task_release(t); |
988 | if (get_rt_utilization(t) == to_fp(1)) { | 978 | if (get_rt_utilization(t) == to_fp(1)) { |
989 | cpu_entry_t* entry = &per_cpu(edfsc_cpu_entries, tsk_rt(t)->edfsc_params.id); | 979 | cpu_entry_t* entry = &per_cpu(edfsc_cpu_entries, tsk_rt(t)->edfsc_params.id); |
990 | remove_cpu_from_global(entry); | 980 | if (bheap_node_in_heap(entry->hn)) |
981 | remove_cpu_from_global(entry); | ||
991 | entry->linked = t; | 982 | entry->linked = t; |
992 | tsk_rt(t)->linked_on = entry->cpu; | 983 | tsk_rt(t)->linked_on = entry->cpu; |
984 | if (is_queued(t)) | ||
985 | remove(&gsched_domain, t); | ||
993 | cancel_idle_enforcement_timer(t); | 986 | cancel_idle_enforcement_timer(t); |
994 | preempt(entry); | 987 | preempt(entry); |
995 | } | 988 | } |
@@ -1008,8 +1001,7 @@ static enum hrtimer_restart container_boundary(struct hrtimer *timer) | |||
1008 | // Otherwise let it release itself when it completes | 1001 | // Otherwise let it release itself when it completes |
1009 | } else { | 1002 | } else { |
1010 | tsk_rt(t)->edfsc_params.can_release = 1; | 1003 | tsk_rt(t)->edfsc_params.can_release = 1; |
1011 | if (tsk_rt(t)->edfsc_params.domain->scheduled == NULL) | 1004 | manage_idle_enforcement_timer(t); |
1012 | manage_idle_enforcement_timer(t); | ||
1013 | } | 1005 | } |
1014 | } | 1006 | } |
1015 | 1007 | ||
@@ -1328,6 +1320,8 @@ static int __init init_edfsc(void) | |||
1328 | tsk_rt(&container_tasks[i])->edfsc_params.domain = &container_domains[i]; | 1320 | tsk_rt(&container_tasks[i])->edfsc_params.domain = &container_domains[i]; |
1329 | tsk_rt(&container_tasks[i])->edfsc_params.can_release = 0; | 1321 | tsk_rt(&container_tasks[i])->edfsc_params.can_release = 0; |
1330 | 1322 | ||
1323 | tsk_rt(&container_tasks[i])->sporadic_release = 0; | ||
1324 | |||
1331 | tsk_rt(&container_tasks[i])->heap_node = kmalloc(sizeof(struct bheap_node), GFP_KERNEL); | 1325 | tsk_rt(&container_tasks[i])->heap_node = kmalloc(sizeof(struct bheap_node), GFP_KERNEL); |
1332 | bheap_node_init(&tsk_rt(&container_tasks[i])->heap_node, &container_tasks[i]); | 1326 | bheap_node_init(&tsk_rt(&container_tasks[i])->heap_node, &container_tasks[i]); |
1333 | requeue(&container_tasks[i]); | 1327 | requeue(&container_tasks[i]); |