Skip site navigation (1)Skip section navigation (2) 
Date:      Fri, 17 Jun 2011 12:49:28 +0000
From:      rudot@FreeBSD.org
To:        svn-soc-all@FreeBSD.org
Subject:   socsvn commit: r223336 - soc2011/rudot/kern
Message-ID:  <20110617124928.0F2891065674@hub.freebsd.org>
next in thread | raw e-mail | index | archive | help 
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);

Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20110617124928.0F2891065674>