From acb5161d7384e6b6352c0a9f3cc067621fbf28ad Mon Sep 17 00:00:00 2001 From: Alex AUVOLAT Date: Fri, 28 Mar 2014 17:16:09 +0100 Subject: Import and compile article 6.75 --- sos-code-article6.75/sos/sched.c | 208 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 208 insertions(+) create mode 100644 sos-code-article6.75/sos/sched.c (limited to 'sos-code-article6.75/sos/sched.c') diff --git a/sos-code-article6.75/sos/sched.c b/sos-code-article6.75/sos/sched.c new file mode 100644 index 0000000..2788be0 --- /dev/null +++ b/sos-code-article6.75/sos/sched.c @@ -0,0 +1,208 @@ +/* Copyright (C) 2004 David Decotigny + + This program is free software; you can redistribute it and/or + modify it under the terms of the GNU General Public License + as published by the Free Software Foundation; either version 2 + of the License, or (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, + USA. +*/ + +#include +#include +#include +#include + +#include "sched.h" + + +/** + * The definition of the scheduler queue. We could have used a normal + * kwaitq here, it would have had the same properties (regarding + * priority ordering mainly). But we don't bother with size + * considerations here (in kwaitq, we had better make the kwaitq + * structure as small as possible because there are a lot of kwaitq in + * the system: at least 1 per opened file), so that we can implement a + * much faster way of handling the prioritized jobs. + */ +struct sos_sched_queue +{ + unsigned int nr_threads; + struct sos_thread *thread_list[SOS_SCHED_NUM_PRIO]; +}; + + +/** + * We manage 2 queues: a queue being scanned for ready threads + * (active_queue) and a queue to store the threads the threads having + * expired their time quantuum. + */ +static struct sos_sched_queue *active_queue, *expired_queue; + + +/** + * The instances for the active/expired queues + */ +static struct sos_sched_queue sched_queue[2]; + + +sos_ret_t sos_sched_subsystem_setup() +{ + memset(sched_queue, 0x0, sizeof(sched_queue)); + active_queue = & sched_queue[0]; + expired_queue = & sched_queue[1]; + + return SOS_OK; +} + + +/** + * Helper function to add a thread in a ready queue AND to change the + * state of the given thread to "READY". + * + * @param insert_at_tail TRUE to tell to add the thread at the end of + * the ready list. Otherwise it is added at the head of it. + */ +static sos_ret_t add_in_ready_queue(struct sos_sched_queue *q, + struct sos_thread *thr, + sos_bool_t insert_at_tail) +{ + sos_sched_priority_t prio; + + SOS_ASSERT_FATAL( (SOS_THR_CREATED == thr->state) + || (SOS_THR_RUNNING == thr->state) /* Yield */ + || (SOS_THR_BLOCKED == thr->state) ); + + /* Add the thread to the CPU queue */ + prio = sos_thread_get_priority(thr); + if (insert_at_tail) + list_add_tail_named(q->thread_list[prio], thr, + ready.rdy_prev, ready.rdy_next); + else + list_add_head_named(q->thread_list[prio], thr, + ready.rdy_prev, ready.rdy_next); + thr->ready.rdy_queue = q; + q->nr_threads ++; + + /* Ok, thread is now really ready to be (re)started */ + thr->state = SOS_THR_READY; + + return SOS_OK; +} + + +sos_ret_t sos_sched_set_ready(struct sos_thread *thr) +{ + sos_ret_t retval; + + /* Don't do anything for already ready threads */ + if (SOS_THR_READY == thr->state) + return SOS_OK; + + if (SOS_SCHED_PRIO_IS_RT(sos_thread_get_priority(thr))) + { + /* Real-time thread: schedule it for the present turn */ + retval = add_in_ready_queue(active_queue, thr, TRUE); + } + else + { + /* Non real-time thread: schedule it for next turn */ + retval = add_in_ready_queue(expired_queue, thr, TRUE); + } + + return retval; +} + + +sos_ret_t sos_sched_change_priority(struct sos_thread *thr, + sos_sched_priority_t priority) +{ + struct sos_thread *thread_list; + SOS_ASSERT_FATAL(SOS_THR_READY == thr->state); + + /* Temp variable */ + thread_list + = thr->ready.rdy_queue->thread_list[sos_thread_get_priority(thr)]; + + list_delete_named(thread_list, thr, ready.rdy_prev, ready.rdy_next); + + /* Update lists */ + thread_list = thr->ready.rdy_queue->thread_list[priority]; + list_add_tail_named(thread_list, thr, ready.rdy_prev, ready.rdy_next); + thr->ready.rdy_queue->thread_list[priority] = thread_list; + + return SOS_OK; +} + + +struct sos_thread * sos_reschedule(struct sos_thread *current_thread, + sos_bool_t do_yield) +{ + sos_sched_priority_t prio; + + if (SOS_THR_ZOMBIE == current_thread->state) + { + /* Don't think of returning to this thread since it is + terminated */ + /* Nop */ + } + else if (SOS_THR_BLOCKED != current_thread->state) + { + /* Take into account the current executing thread unless it is + marked blocked */ + if (do_yield) + { + /* Ok, reserve it for next turn */ + if (SOS_SCHED_PRIO_IS_RT(sos_thread_get_priority(current_thread))) + add_in_ready_queue(active_queue, current_thread, TRUE); + else + add_in_ready_queue(expired_queue, current_thread, TRUE); + } + else + { + /* Put it at the head of the active list */ + add_in_ready_queue(active_queue, current_thread, FALSE); + } + } + + + /* Active queue is empty ? */ + if (active_queue->nr_threads <= 0) + { + /* Yes: Exchange it with the expired queue */ + struct sos_sched_queue *q; + q = active_queue; + active_queue = expired_queue; + expired_queue = q; + } + + /* Now loop over the priorities in the active queue, looking for a + non-empty queue */ + for (prio = SOS_SCHED_PRIO_HIGHEST ; prio <= SOS_SCHED_PRIO_LOWEST ; prio ++) + { + struct sos_thread *next_thr; + + if (list_is_empty_named(active_queue->thread_list[prio], + ready.rdy_prev, ready.rdy_next)) + continue; + + /* Queue is not empty: take the thread at its head */ + next_thr = list_pop_head_named(active_queue->thread_list[prio], + ready.rdy_prev, ready.rdy_next); + active_queue->nr_threads --; + + return next_thr; + } + + + SOS_FATAL_ERROR("No kernel thread ready ?!"); + return NULL; +} -- cgit v1.2.3