339 lines
9.0 KiB
C
339 lines
9.0 KiB
C
/* 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 <sos/errno.h>
|
|
#include <sos/klibc.h>
|
|
#include <sos/assert.h>
|
|
#include <sos/list.h>
|
|
#include <sos/calcload.h>
|
|
|
|
#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];
|
|
|
|
|
|
/**
|
|
* The array giving the timeslice corresponding to each priority level
|
|
*/
|
|
struct sos_time time_slice[SOS_SCHED_NUM_PRIO];
|
|
|
|
|
|
sos_ret_t sos_sched_subsystem_setup()
|
|
{
|
|
sos_sched_priority_t prio;
|
|
|
|
memset(sched_queue, 0x0, sizeof(sched_queue));
|
|
active_queue = & sched_queue[0];
|
|
expired_queue = & sched_queue[1];
|
|
|
|
/* pre-compute time slices */
|
|
for (prio = SOS_SCHED_PRIO_TS_HIGHEST ;
|
|
prio <= SOS_SCHED_PRIO_TS_LOWEST ;
|
|
prio ++)
|
|
{
|
|
unsigned int ms;
|
|
ms = SOS_TIME_SLICE_MIN
|
|
+ (SOS_TIME_SLICE_MAX - SOS_TIME_SLICE_MIN)
|
|
* (prio - SOS_SCHED_PRIO_TS_HIGHEST)
|
|
/ (SOS_SCHED_PRIO_TS_LOWEST - SOS_SCHED_PRIO_TS_HIGHEST);
|
|
time_slice[prio].sec = ms / 1000;
|
|
time_slice[prio].nanosec = 1000000UL * (ms % 1000);
|
|
}
|
|
|
|
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;
|
|
|
|
/* Reset the CPU time used in the quantuum */
|
|
memset(& thr->user_time_spent_in_slice, 0x0, sizeof(struct sos_time));
|
|
|
|
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;
|
|
}
|
|
|
|
|
|
/**
|
|
* Helper function to determine whether the current thread expired its
|
|
* time quantuum
|
|
*/
|
|
static sos_bool_t
|
|
thread_expired_its_quantuum(struct sos_thread *thr)
|
|
{
|
|
sos_sched_priority_t prio = sos_thread_get_priority(thr);
|
|
|
|
/* No timesharing/round-robin for "real-time" threads */
|
|
if (SOS_SCHED_PRIO_IS_RT(prio))
|
|
return FALSE;
|
|
|
|
/* Current (user) thread expired its time quantuum ? A kernel
|
|
thread never expires because sos_sched_do_timer_tick() below
|
|
won't update its user_time_spent_in_slice */
|
|
if (sos_time_cmp(& thr->user_time_spent_in_slice,
|
|
& time_slice[prio]) >= 0)
|
|
return TRUE;
|
|
|
|
return FALSE;
|
|
}
|
|
|
|
|
|
struct sos_thread * sos_reschedule(struct sos_thread *current_thread,
|
|
sos_bool_t do_yield)
|
|
{
|
|
sos_sched_priority_t prio;
|
|
|
|
/* Force the current thread to release the CPU if it expired its
|
|
quantuum */
|
|
if (thread_expired_its_quantuum(current_thread))
|
|
{
|
|
/* Reset the CPU time used in the quantuum */
|
|
memset(& current_thread->user_time_spent_in_slice,
|
|
0x0, sizeof(struct sos_time));
|
|
|
|
do_yield = TRUE;
|
|
}
|
|
|
|
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;
|
|
}
|
|
|
|
|
|
sos_ret_t sos_sched_do_timer_tick()
|
|
{
|
|
struct sos_thread *interrupted_thread = sos_thread_get_current();
|
|
struct sos_time tick_duration;
|
|
sos_bool_t cur_is_user;
|
|
sos_ui32_t nb_user_ready = 0;
|
|
sos_ui32_t nb_kernel_ready = 0;
|
|
int prio;
|
|
|
|
sos_time_get_tick_resolution(& tick_duration);
|
|
|
|
/* Update the timing statistics */
|
|
if (sos_cpu_context_is_in_user_mode(interrupted_thread->cpu_state))
|
|
{
|
|
cur_is_user = TRUE;
|
|
|
|
/* User time */
|
|
sos_time_inc(& interrupted_thread->rusage.ru_utime,
|
|
& tick_duration);
|
|
|
|
/* Update time spent is current timeslice ONLY for a user thread */
|
|
sos_time_inc(& interrupted_thread->user_time_spent_in_slice,
|
|
& tick_duration);
|
|
}
|
|
else
|
|
{
|
|
cur_is_user = FALSE;
|
|
|
|
/* System time */
|
|
sos_time_inc(& interrupted_thread->rusage.ru_stime,
|
|
& tick_duration);
|
|
}
|
|
|
|
|
|
/* Update load stats */
|
|
for (prio = SOS_SCHED_PRIO_HIGHEST ; prio <= SOS_SCHED_PRIO_LOWEST ; prio ++)
|
|
{
|
|
struct sos_thread *thr;
|
|
int nb_thrs;
|
|
|
|
list_foreach_forward_named(active_queue->thread_list[prio],
|
|
thr, nb_thrs,
|
|
ready.rdy_prev, ready.rdy_next)
|
|
{
|
|
if (sos_cpu_context_is_in_user_mode(thr->cpu_state))
|
|
nb_user_ready ++;
|
|
else
|
|
nb_kernel_ready ++;
|
|
}
|
|
|
|
list_foreach_forward_named(expired_queue->thread_list[prio],
|
|
thr, nb_thrs,
|
|
ready.rdy_prev, ready.rdy_next)
|
|
{
|
|
if (sos_cpu_context_is_in_user_mode(thr->cpu_state))
|
|
nb_user_ready ++;
|
|
else
|
|
nb_kernel_ready ++;
|
|
}
|
|
}
|
|
|
|
sos_load_do_timer_tick(cur_is_user,
|
|
nb_user_ready,
|
|
nb_kernel_ready);
|
|
|
|
return SOS_OK;
|
|
}
|