From owner-svn-soc-all@FreeBSD.ORG Fri Jun 17 12:49:30 2011 Return-Path: Delivered-To: svn-soc-all@FreeBSD.org Received: from socsvn.FreeBSD.org (unknown [IPv6:2001:4f8:fff6::2f]) by hub.freebsd.org (Postfix) with SMTP id 0F2891065674 for ; Fri, 17 Jun 2011 12:49:28 +0000 (UTC) (envelope-from rudot@FreeBSD.org) Received: by socsvn.FreeBSD.org (sSMTP sendmail emulation); Fri, 17 Jun 2011 12:49:28 +0000 Date: Fri, 17 Jun 2011 12:49:28 +0000 From: rudot@FreeBSD.org To: svn-soc-all@FreeBSD.org MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Message-Id: <20110617124928.0F2891065674@hub.freebsd.org> Cc: Subject: socsvn commit: r223336 - soc2011/rudot/kern X-BeenThere: svn-soc-all@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: SVN commit messages for the entire Summer of Code repository List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 17 Jun 2011 12:49:30 -0000 Author: rudot Date: Fri Jun 17 12:49:27 2011 New Revision: 223336 URL: http://svnweb.FreeBSD.org/socsvn/?view=rev&rev=223336 Log: time-sharing threads are selected based on their virtual deadline Modified: soc2011/rudot/kern/sched_fbfs.c Modified: soc2011/rudot/kern/sched_fbfs.c ============================================================================== --- soc2011/rudot/kern/sched_fbfs.c Fri Jun 17 11:13:37 2011 (r223335) +++ soc2011/rudot/kern/sched_fbfs.c Fri Jun 17 12:49:27 2011 (r223336) @@ -125,6 +125,9 @@ static void sched_priority(struct thread *td, u_char prio); static void sched_setup(void *dummy); +static struct thread *edf_choose(struct rqhead * rqh); +static struct thread *runq_choose_bfs(struct runq * rq); + SYSINIT(sched_setup, SI_SUB_RUN_QUEUE, SI_ORDER_FIRST, sched_setup, NULL); /* @@ -135,7 +138,7 @@ /* * Priority ratios for virtual deadline per nice value calculations. */ -static int prio_ratios[PRIO_MAX - PRIO_MIN]; +static int prio_ratios[PRIO_MAX - PRIO_MIN + 1]; static void setup_runqs(void) @@ -260,7 +263,7 @@ int i; prio_ratios[0] = 128; - for (i = 1; i < PRIO_MAX - PRIO_MIN; ++i) { + for (i = 1; i <= PRIO_MAX - PRIO_MIN; ++i) { prio_ratios[i] = prio_ratios[i - 1] * 11 / 10; } @@ -348,7 +351,8 @@ prio_ratios[td->td_proc->p_nice - PRIO_MIN], ts->ts_vdeadline ); - + + CTR1(KTR_SCHED, "queue number: %d", td->td_rqindex); } } @@ -747,6 +751,60 @@ TD_SET_CAN_RUN(td); } +static struct thread * +edf_choose(struct rqhead * rqh) +{ + struct thread *td; + struct thread *td_min; + struct td_sched *ts; + int deadline_min; + + td = td_min = TAILQ_FIRST(rqh); + deadline_min = td_min->td_sched->ts_vdeadline; + + td = TAILQ_NEXT(td, td_runq); + while (td != NULL) { + ts = td->td_sched; + if (ts->ts_vdeadline < deadline_min) { + deadline_min = ts->ts_vdeadline; + td_min = td; + } + td = TAILQ_NEXT(td, td_runq); + } + + return (td_min); +} + +static struct thread * +runq_choose_bfs(struct runq * rq) +{ + struct rqhead *rqh; + struct thread *td; + struct rqbits * rqb; + int pri; + int i; + + rqb = &rq->rq_status; + for (i = 0; i < RQB_LEN; i++) { + if (rqb->rqb_bits[i] == 0) + continue; + pri = RQB_FFS(rqb->rqb_bits[i]) + (i << RQB_L2BPW); + if (pri == RQ_TIMESHARE) { + td = edf_choose(&rq->rq_queues[pri]); + return (td); + } + rqh = &rq->rq_queues[pri]; + td = TAILQ_FIRST(rqh); + KASSERT(td != NULL, "runq_choose_bfs: no thread on busy queue"); + CTR3(KTR_RUNQ, + "runq_choose_bfs: pri=%d thread=%p rqh=%p", pri, td, rqh); + return (td); + } + CTR1(KTR_RUNQ, "runq_choose_bfs: idlethread pri=%d", pri); + + return (NULL); +} + /* * Select threads to run. Note that running threads still consume a * slot. @@ -760,7 +818,7 @@ mtx_assert(&sched_lock, MA_OWNED); rq = &runq; - td = runq_choose(&runq); + td = runq_choose_bfs(&runq); if (td) { runq_remove(rq, td);