From d0598c54028251a018650665043156266664e0bf Mon Sep 17 00:00:00 2001 From: Jonathan Herman Date: Sat, 7 May 2011 19:38:51 -0400 Subject: Changed candidate queue logic --- litmus/sched_edf_hsb.c | 50 ++++++++++--------- litmus/sched_edf_hsb_noslack.c | 107 +++++++++++++++++++++-------------------- 2 files changed, 84 insertions(+), 73 deletions(-) diff --git a/litmus/sched_edf_hsb.c b/litmus/sched_edf_hsb.c index fd2070c6f94d..d74f4337ac2b 100644 --- a/litmus/sched_edf_hsb.c +++ b/litmus/sched_edf_hsb.c @@ -243,7 +243,7 @@ static void remove_slack(server_t *slack) if (!slack) return; TRACE_SERVER_SUB(slack, "slack removed"); - //sched_trace_action(NULL, SLACK_EXPIRED_ACTION); + //////sched_trace_action(NULL, SLACK_EXPIRED_ACTION); if (head_in_list(&slack->list)) list_del_init(&slack->list); @@ -288,6 +288,13 @@ static inline struct task_struct* get_candidate(struct list_head *pos) return task; } +static inline lt_t real_deadline(struct task_struct *task) +{ + server_t *server = task_srt_server(task); + int job_diff = server->job_no - task_job_no(task); + return get_deadline(task) - job_diff * get_rt_period(task); +} + /* * Candidate queue is EDF. */ @@ -300,7 +307,7 @@ static void add_slack_candidate(struct task_struct *task) list_for_each_prev(pos, &slack_candidates) { queued = get_candidate(pos); - if (lt_before_eq(get_deadline(queued), get_deadline(task))) { + if (lt_before_eq(real_deadline(queued), real_deadline(task))) { __list_add(&task_data(task)->candidate_list, pos, pos->next); return; @@ -321,8 +328,6 @@ static void donate_slack(server_t *donator) BUG_ON(!hrt_server->ready); } - BUG_ON(head_in_list(&slack->list)); - slack->wcet = donator->budget; slack->budget = donator->budget; slack->deadline = donator->deadline; @@ -373,7 +378,7 @@ static noinline void check_donate_slack(server_t *donator, struct task_struct *w if (!donate) return; - sched_trace_action(was_scheduled, SLACK_DONATED_ACTION); + ////sched_trace_action(was_scheduled, SLACK_DONATED_ACTION); donate_slack(donator); } @@ -664,7 +669,7 @@ static void requeue_server(server_t *server, lt_t now) hrt_server->ready = 1; remove_slack(server_slack(server)); hrt_server->no_slack = 0; - sched_trace_action(NULL, SERVER_RELEASED_ACTION); + ////sched_trace_action(NULL, SERVER_RELEASED_ACTION); } else if (server->type == S_BE) { TRACE_SERVER_SUB(server, "BE added to ready"); bheap_insert(server_order, &be_ready_servers, server->hn); @@ -686,7 +691,7 @@ static void reclaim_slack(server_t *slack) return; /* SRT servers do not ever reclaim slack */ - sched_trace_action(NULL, SLACK_RECLAIM_ACTION); + ////sched_trace_action(NULL, SLACK_RECLAIM_ACTION); exec = slack->wcet - slack->budget; TRACE_SERVER_SUB(donator, "reclaiming %llu slack", TIME(exec)); @@ -726,7 +731,7 @@ static noinline void link_server(cpu_entry_t *entry, /* Should have already been removed from slack list */ BUG_ON(head_in_list(&task_data(entry->linked)->candidate_list)); BUG_ON(is_be(entry->linked) && is_queued(entry->linked)); - sched_trace_action(entry->linked, SLACK_RUN_ACTION); + ////sched_trace_action(entry->linked, SLACK_RUN_ACTION); BUG_ON(is_srt(entry->linked) && task_srt_server(entry->linked)->job_no <= task_job_no(entry->linked)); @@ -734,7 +739,7 @@ static noinline void link_server(cpu_entry_t *entry, /* Should have already been removed from ready heap */ BUG_ON(bheap_node_in_heap(next_server->hn)); BUG_ON(is_queued(entry->linked)); - sched_trace_action(entry->linked, next_server->id); + ////sched_trace_action(entry->linked, next_server->id); } if (next_server->type != S_SLACK && @@ -773,7 +778,7 @@ static noinline void unlink_server(cpu_entry_t *entry, int requeue) if (server->type == S_SLACK && server->deadline) { add_slack(server); - sched_trace_action(entry->linked, SLACK_STOP_ACTION); + ////sched_trace_action(entry->linked, SLACK_STOP_ACTION); /* Donator needs to absorb slack execution time */ reclaim_slack(server); @@ -1004,7 +1009,7 @@ static noinline int catchup_srt_server(struct task_struct *task) rv = 1; - sched_trace_action(task, SERVER_RELEASED_ACTION); + ////sched_trace_action(task, SERVER_RELEASED_ACTION); } else if (lt_before(srt_server->deadline, now) && srt_server->job_no <= 1) { @@ -1053,7 +1058,7 @@ static noinline struct task_struct* next_eligible_hrt(hrt_server_t *hrt_server) slack = lt_subtract(hrt_server->server.deadline, hrt_server->server.budget); - sched_trace_action(task, SERVER_RELEASED_ACTION); + ////sched_trace_action(task, SERVER_RELEASED_ACTION); } /* If the slack timer is active, this is not necessary */ @@ -1063,7 +1068,7 @@ static noinline struct task_struct* next_eligible_hrt(hrt_server_t *hrt_server) TRACE_SERVER_SUB(&hrt_server->server, "no slack: %llu", TIME(slack)); hrt_server->no_slack = 1; - sched_trace_action(task, NO_SLACK_ACTION); + ////sched_trace_action(task, NO_SLACK_ACTION); } else { slack_timer_arm(hrt_server); } @@ -1173,7 +1178,8 @@ static noinline server_t* next_eligible_be_server(void) if (is_server_linked(be_server)) { TRACE_SERVER_SUB(be_server, "linked"); - continue; + be_server = next_be_server(); + return NULL; } catchup_server(be_server, now); @@ -1182,7 +1188,7 @@ static noinline server_t* next_eligible_be_server(void) be_server->hn); be_server = next_be_server(); TRACE_SERVER_SUB(be_server, "catching up BE server"); - sched_trace_action(NULL, SERVER_RELEASED_ACTION); /* Release */ + ////sched_trace_action(NULL, SERVER_RELEASED_ACTION); /* Release */ } if (be_server && lt_before(now, be_server->release)) { @@ -1692,7 +1698,7 @@ static enum hrtimer_restart slack_timer_fire(struct hrtimer *timer) TRACE_TIMER("slack timer fired for P%d", entry->cpu); BUG_ON(!server->ready); - sched_trace_action(entry->linked, NO_SLACK_ACTION); + ////sched_trace_action(entry->linked, NO_SLACK_ACTION); /* Set new state of entry */ server->no_slack = 1; @@ -1729,9 +1735,7 @@ static void job_completion(cpu_entry_t *entry, struct task_struct* task) "rel: %llu, dead: %llu", TIME(get_release(task)), TIME(get_deadline(task))); - } - - if (server->type == S_SRT) { + } else if (server->type == S_SRT) { /* If the task is behind the server it must release immediately, * leaving its release time and deadline unchanged. */ @@ -1803,9 +1807,10 @@ static void server_completed(server_t *server, struct task_struct *task) if (server->type != S_SLACK) { server_release(server); - sched_trace_action(task, SERVER_COMPLETED_ACTION); } + sched_trace_action(task, SERVER_COMPLETED_ACTION); + unlink(task); requeue(task, get_rt_domain(entry, task)); @@ -1853,7 +1858,7 @@ static void servers_released(struct list_head *servers) raw_spin_lock_irqsave(global_lock, flags); - sched_trace_action(NULL, SERVER_RELEASED_ACTION); + ////sched_trace_action(NULL, SERVER_RELEASED_ACTION); TRACE_TIMER("Servers released"); list_for_each_safe(pos, safe, servers) { @@ -2151,7 +2156,8 @@ static void edf_hsb_task_block(struct task_struct *task) struct task_struct *linked; server_t *linked_server; - TRACE_TASK(task, "block at %llu\n", litmus_clock()); + TRACE_TASK(task, "block at %llu in state %llu\n", + litmus_clock(), task->state); set_rt_flags(task, RT_F_BLOCK); raw_spin_lock_irqsave(global_lock, flags); diff --git a/litmus/sched_edf_hsb_noslack.c b/litmus/sched_edf_hsb_noslack.c index 545588dbc915..4d91f99d4094 100644 --- a/litmus/sched_edf_hsb_noslack.c +++ b/litmus/sched_edf_hsb_noslack.c @@ -243,7 +243,7 @@ static void remove_slack(server_t *slack) if (!slack) return; TRACE_SERVER_SUB(slack, "slack removed"); - //sched_trace_action(NULL, SLACK_EXPIRED_ACTION); + //////sched_trace_action(NULL, SLACK_EXPIRED_ACTION); if (head_in_list(&slack->list)) list_del_init(&slack->list); @@ -288,6 +288,13 @@ static inline struct task_struct* get_candidate(struct list_head *pos) return task; } +static inline lt_t real_deadline(struct task_struct *task) +{ + server_t *server = task_srt_server(task); + int job_diff = server->job_no - task_job_no(task); + return get_deadline(task) - job_diff * get_rt_period(task); +} + /* * Candidate queue is EDF. */ @@ -300,7 +307,7 @@ static void add_slack_candidate(struct task_struct *task) list_for_each_prev(pos, &slack_candidates) { queued = get_candidate(pos); - if (lt_before_eq(get_deadline(queued), get_deadline(task))) { + if (lt_before_eq(real_deadline(queued), real_deadline(task))) { __list_add(&task_data(task)->candidate_list, pos, pos->next); return; @@ -321,8 +328,6 @@ static void donate_slack(server_t *donator) BUG_ON(!hrt_server->ready); } - BUG_ON(head_in_list(&slack->list)); - slack->wcet = donator->budget; slack->budget = donator->budget; slack->deadline = donator->deadline; @@ -373,7 +378,7 @@ static noinline void check_donate_slack(server_t *donator, struct task_struct *w if (!donate) return; - sched_trace_action(was_scheduled, SLACK_DONATED_ACTION); + ////sched_trace_action(was_scheduled, SLACK_DONATED_ACTION); donate_slack(donator); } @@ -439,10 +444,9 @@ static noinline server_t* next_eligible_slack_server(void) */ static noinline struct task_struct* next_eligible_slack(void) { - struct task_struct *next = NULL; + struct task_struct *next = get_candidate(slack_candidates.next); - next = get_candidate(slack_candidates.next); - while (next && tsk_rt(next)->linked_on != NO_CPU) { + while (next && task_srt_server(next)->job_no <= task_job_no(next)) { list_del_init(&task_data(next)->candidate_list); next = get_candidate(slack_candidates.next); } @@ -454,8 +458,6 @@ static noinline struct task_struct* next_eligible_slack(void) next = __peek_ready(&be_domain); } - BUG_ON(next && tsk_rt(next)->linked_on != NO_CPU); - return next; } @@ -667,7 +669,7 @@ static void requeue_server(server_t *server, lt_t now) hrt_server->ready = 1; remove_slack(server_slack(server)); hrt_server->no_slack = 0; - sched_trace_action(NULL, SERVER_RELEASED_ACTION); + ////sched_trace_action(NULL, SERVER_RELEASED_ACTION); } else if (server->type == S_BE) { TRACE_SERVER_SUB(server, "BE added to ready"); bheap_insert(server_order, &be_ready_servers, server->hn); @@ -685,11 +687,11 @@ static void reclaim_slack(server_t *slack) lt_t exec; server_t *donator = server_slack(slack); - if (!donator) + if (!donator || lt_before_eq(slack->deadline, litmus_clock())) return; /* SRT servers do not ever reclaim slack */ - sched_trace_action(NULL, SLACK_RECLAIM_ACTION); + ////sched_trace_action(NULL, SLACK_RECLAIM_ACTION); exec = slack->wcet - slack->budget; TRACE_SERVER_SUB(donator, "reclaiming %llu slack", TIME(exec)); @@ -721,7 +723,6 @@ static noinline void link_server(cpu_entry_t *entry, BUG_ON(next_server->job_no + 1 < task_job_no(entry->linked)); BUG_ON(lt_after(get_deadline(entry->linked), next_server->deadline)); - BUG_ON(head_in_list(&task_data(entry->linked)->candidate_list)); } else if (next_server->type == S_HRT) { /* HRT servers should never, ever migrate */ BUG_ON(entry->cpu != task_cpu(entry->linked)); @@ -730,12 +731,15 @@ static noinline void link_server(cpu_entry_t *entry, /* Should have already been removed from slack list */ BUG_ON(head_in_list(&task_data(entry->linked)->candidate_list)); BUG_ON(is_be(entry->linked) && is_queued(entry->linked)); - sched_trace_action(entry->linked, SLACK_RUN_ACTION); + ////sched_trace_action(entry->linked, SLACK_RUN_ACTION); + BUG_ON(is_srt(entry->linked) && + task_srt_server(entry->linked)->job_no <= + task_job_no(entry->linked)); } else { /* BE */ /* Should have already been removed from ready heap */ BUG_ON(bheap_node_in_heap(next_server->hn)); BUG_ON(is_queued(entry->linked)); - sched_trace_action(entry->linked, next_server->id); + ////sched_trace_action(entry->linked, next_server->id); } if (next_server->type != S_SLACK && @@ -774,7 +778,7 @@ static noinline void unlink_server(cpu_entry_t *entry, int requeue) if (server->type == S_SLACK && server->deadline) { add_slack(server); - sched_trace_action(entry->linked, SLACK_STOP_ACTION); + ////sched_trace_action(entry->linked, SLACK_STOP_ACTION); /* Donator needs to absorb slack execution time */ reclaim_slack(server); @@ -940,6 +944,7 @@ static noinline void unlink(struct task_struct* t) if (head_in_list(&task_data(t)->candidate_list)) { list_del_init(&task_data(t)->candidate_list); } + } /* @@ -1004,7 +1009,7 @@ static noinline int catchup_srt_server(struct task_struct *task) rv = 1; - sched_trace_action(task, SERVER_RELEASED_ACTION); + ////sched_trace_action(task, SERVER_RELEASED_ACTION); } else if (lt_before(srt_server->deadline, now) && srt_server->job_no <= 1) { @@ -1053,7 +1058,7 @@ static noinline struct task_struct* next_eligible_hrt(hrt_server_t *hrt_server) slack = lt_subtract(hrt_server->server.deadline, hrt_server->server.budget); - sched_trace_action(task, SERVER_RELEASED_ACTION); + ////sched_trace_action(task, SERVER_RELEASED_ACTION); } /* If the slack timer is active, this is not necessary */ @@ -1063,7 +1068,7 @@ static noinline struct task_struct* next_eligible_hrt(hrt_server_t *hrt_server) TRACE_SERVER_SUB(&hrt_server->server, "no slack: %llu", TIME(slack)); hrt_server->no_slack = 1; - sched_trace_action(task, NO_SLACK_ACTION); + ////sched_trace_action(task, NO_SLACK_ACTION); } else { slack_timer_arm(hrt_server); } @@ -1173,7 +1178,8 @@ static noinline server_t* next_eligible_be_server(void) if (is_server_linked(be_server)) { TRACE_SERVER_SUB(be_server, "linked"); - continue; + be_server = next_be_server(); + return NULL; } catchup_server(be_server, now); @@ -1182,7 +1188,7 @@ static noinline server_t* next_eligible_be_server(void) be_server->hn); be_server = next_be_server(); TRACE_SERVER_SUB(be_server, "catching up BE server"); - sched_trace_action(NULL, SERVER_RELEASED_ACTION); /* Release */ + ////sched_trace_action(NULL, SERVER_RELEASED_ACTION); /* Release */ } if (be_server && lt_before(now, be_server->release)) { @@ -1279,10 +1285,6 @@ static void next_global_task(cpu_entry_t *entry, next_slack = next_eligible_slack(); slack_server = next_eligible_slack_server(); - BUG_ON(next_slack && tsk_rt(next_slack)->linked_on != NO_CPU); - BUG_ON(next_srt && tsk_rt(next_srt)->linked_on != NO_CPU); - BUG_ON(next_be && tsk_rt(next_be)->linked_on != NO_CPU); - TRACE_SUB("be_server: %d, next_be: %d, next_srt: %d, slack_server: %d " "next_slack: %d", (be_server) ? be_server->id : -1, (next_be) ? next_be->pid : -1, @@ -1359,6 +1361,12 @@ static void remove_from_ready(server_t *server, struct task_struct *task, TRACE_TASK_SUB(task, "BE removed from ready"); remove(&be_domain, task); } + + /* Remove from consideration of slack servers */ + if (head_in_list(&task_data(task)->candidate_list)) { + TRACE_TASK_SUB(task, "deleting candidate"); + list_del_init(&task_data(task)->candidate_list); + } } else { slack = server_slack(server); if (slack && head_in_list(&slack->list)) { @@ -1379,13 +1387,6 @@ static void remove_from_ready(server_t *server, struct task_struct *task, } BUG_ON(!task_data(task)); - - /* Remove from consideration of slack servers */ - if (head_in_list(&task_data(task)->candidate_list)) { - TRACE_TASK_SUB(task, "deleting candidate"); - list_del_init(&task_data(task)->candidate_list); - } - } static void check_for_slack_preempt(struct task_struct*,server_t*,cpu_entry_t*, int); @@ -1469,11 +1470,21 @@ static noinline void check_for_slack_preempt(struct task_struct *task, server_t *slack = server_slack(server); struct task_struct *slack_task; - /* Bad! There is no use trying to move the link of this task as it - * is almost always scheduled on another CPU. - */ - BUG_ON(tsk_rt(task)->linked_on != NO_CPU && - tsk_rt(task)->linked_on != next_entry->cpu); + /* The task is currently being run by another server */ + if (tsk_rt(task)->linked_on != NO_CPU) { + entry = task_linked_entry(task); + + if (entry != next_entry) { + TRACE_TASK_SUB(task, "was on P%d", entry->cpu); + + unlink(task); + + /* if (resched) { */ + /* edf_hsb_pick_next(entry); */ + /* preempt_if_preemptable(entry->scheduled, entry->cpu); */ + /* } */ + } + } /* The server's slack is currently being run */ if (slack && is_server_linked(slack)) { @@ -1687,7 +1698,7 @@ static enum hrtimer_restart slack_timer_fire(struct hrtimer *timer) TRACE_TIMER("slack timer fired for P%d", entry->cpu); BUG_ON(!server->ready); - sched_trace_action(entry->linked, NO_SLACK_ACTION); + ////sched_trace_action(entry->linked, NO_SLACK_ACTION); /* Set new state of entry */ server->no_slack = 1; @@ -1724,15 +1735,7 @@ static void job_completion(cpu_entry_t *entry, struct task_struct* task) "rel: %llu, dead: %llu", TIME(get_release(task)), TIME(get_deadline(task))); - check_slack_candidate(task); - sched_trace_task_completion(task, 1); - - return; - } - - BUG_ON(is_queued(task)); - - if (server->type == S_SRT) { + } else if (server->type == S_SRT) { /* If the task is behind the server it must release immediately, * leaving its release time and deadline unchanged. */ @@ -1804,9 +1807,10 @@ static void server_completed(server_t *server, struct task_struct *task) if (server->type != S_SLACK) { server_release(server); - sched_trace_action(task, SERVER_COMPLETED_ACTION); } + sched_trace_action(task, SERVER_COMPLETED_ACTION); + unlink(task); requeue(task, get_rt_domain(entry, task)); @@ -1854,7 +1858,7 @@ static void servers_released(struct list_head *servers) raw_spin_lock_irqsave(global_lock, flags); - sched_trace_action(NULL, SERVER_RELEASED_ACTION); + ////sched_trace_action(NULL, SERVER_RELEASED_ACTION); TRACE_TIMER("Servers released"); list_for_each_safe(pos, safe, servers) { @@ -2152,7 +2156,8 @@ static void edf_hsb_task_block(struct task_struct *task) struct task_struct *linked; server_t *linked_server; - TRACE_TASK(task, "block at %llu\n", litmus_clock()); + TRACE_TASK(task, "block at %llu in state %llu\n", + litmus_clock(), task->state); set_rt_flags(task, RT_F_BLOCK); raw_spin_lock_irqsave(global_lock, flags); -- cgit v1.2.2