From 165e6bed506f9fddd7e9da8ad1f4c7f186e29b00 Mon Sep 17 00:00:00 2001
From: Patrick Williams <iawillia@us.ibm.com>
Date: Wed, 9 Jun 2010 16:14:11 -0500
Subject: Change scheduler to locked queue instead of stack-pair.

---
 src/include/kernel/scheduler.H  |  8 +++--
 src/include/kernel/task.H       |  1 +
 src/include/util/locked/queue.H | 73 +++++++++++++++++++++++++++++++++++++++++
 src/kernel/scheduler.C          | 13 ++------
 4 files changed, 81 insertions(+), 14 deletions(-)
 create mode 100644 src/include/util/locked/queue.H

(limited to 'src')

diff --git a/src/include/kernel/scheduler.H b/src/include/kernel/scheduler.H
index 31cdde70e..76034af48 100644
--- a/src/include/kernel/scheduler.H
+++ b/src/include/kernel/scheduler.H
@@ -2,6 +2,9 @@
 #define __KERNEL_SCHEDULER_H
 
 #include <kernel/types.h>
+#include <kernel/spinlock.H>
+#include <util/locked/queue.H>
+
 #include <util/lockfree/stack.H>
 
 class Scheduler
@@ -16,15 +19,14 @@ class Scheduler
 
     protected:
 	Scheduler(cpu_t* cpu) : 
-		iv_direction(false), iv_idleTask(NULL), iv_cpu(cpu) {};
+		iv_taskList(), iv_idleTask(NULL), iv_cpu(cpu) {};
 	~Scheduler() {};
 
 	void setIdleTask(task_t* t) { iv_idleTask = t; };
 	task_t* getIdleTask() { return iv_idleTask; };
 
     private:
-	bool iv_direction;
-	Util::Lockfree::Stack<task_t> iv_taskList[2];
+	Util::Locked::Queue<task_t, true, Spinlock> iv_taskList;
 
 	task_t* iv_idleTask;
 	cpu_t* iv_cpu;
diff --git a/src/include/kernel/task.H b/src/include/kernel/task.H
index 4cd19bd04..c27c7e8ce 100644
--- a/src/include/kernel/task.H
+++ b/src/include/kernel/task.H
@@ -20,6 +20,7 @@ struct task_t
     context_t context;
     
     tid_t tid;
+    task_t* prev;
     task_t* next;
 };
 
diff --git a/src/include/util/locked/queue.H b/src/include/util/locked/queue.H
new file mode 100644
index 000000000..2f230819e
--- /dev/null
+++ b/src/include/util/locked/queue.H
@@ -0,0 +1,73 @@
+#ifndef __UTIL_LOCKED_QUEUE_H
+#define __UTIL_LOCKED_QUEUE_H
+
+namespace Util
+{
+    namespace Locked
+    {
+	template <typename _T, bool locked = false, typename _S = int>
+	class Queue
+	{
+	    public:
+		Queue() : head(NULL), tail(NULL), lock() {};
+		~Queue() {};
+
+		_T* remove();
+		void insert(_T*);
+
+	    private:
+		_T* head;
+		_T* tail;
+
+		_S lock;
+
+	};
+
+	template <typename _T, bool locked, typename _S>
+	_T* Queue<_T,locked,_S>::remove()
+	{
+	    _T* item = NULL;
+
+	    if (locked)
+		lock.lock();
+	    
+	    if (tail != NULL)
+	    {
+		item = tail;
+		if (head == tail)
+		    head = tail = NULL;
+		else
+		    tail = item->prev;
+	    }
+
+	    if (locked)
+		lock.unlock();
+
+	    return item;
+	}
+
+	template <typename _T, bool locked, typename _S>
+	void Queue<_T,locked,_S>::insert(_T* item)
+	{
+	    if (locked)
+		lock.lock();
+	    
+	    if (head == NULL)
+	    {
+		item->next = item->prev = NULL;
+		head = tail = item;
+	    }
+	    else
+	    {
+		item->prev = NULL;
+		item->next = head;
+		head = head->prev = item;
+	    }
+
+	    if (locked)
+		lock.unlock();
+	}
+    };
+};
+
+#endif
diff --git a/src/kernel/scheduler.C b/src/kernel/scheduler.C
index b96dd7c7b..c7c26448c 100644
--- a/src/kernel/scheduler.C
+++ b/src/kernel/scheduler.C
@@ -6,7 +6,7 @@ void Scheduler::addTask(task_t* t)
 {
     if (iv_idleTask != t)
     {
-	iv_taskList[iv_direction ? 0 : 1].push(t);
+	iv_taskList.insert(t);
     }
 }
 
@@ -17,16 +17,7 @@ void Scheduler::returnRunnable()
 
 void Scheduler::setNextRunnable()
 {
-    task_t* t = NULL;
-
-    bool direction = iv_direction;
-    t = iv_taskList[direction ? 1 : 0].pop();
-
-    if (NULL == t)
-    {
-	t = iv_taskList[direction ? 0 : 1].pop();
-	__sync_bool_compare_and_swap(&iv_direction, direction, !direction);
-    }
+    task_t* t = iv_taskList.remove();
 
     if (NULL == t)
     {
-- 
cgit v1.2.1