../sos-code-article6.5/sos/ksynch.c (2005-01-04 04:13:49.000000000 +0100 )	../sos-code-article6.75/sos/ksynch.c (2005-01-04 04:13:53.000000000 +0100 )
Line 24	Line 24
sos_ret_t sos_ksema_init(struct sos_ksema *sema, const char *name,	sos_ret_t sos_ksema_init(struct sos_ksema *sema, const char *name,
int initial_value)	int initial_value,
	sos_kwaitq_ordering_t ordering)
sema->value = initial_value;	sema->value = initial_value;
return sos_kwaitq_init(& sema->kwaitq, name);	return sos_kwaitq_init(& sema->kwaitq, name, ordering);
Line 105	Line 106
}	}
sos_ret_t sos_kmutex_init(struct sos_kmutex *mutex, const char *name)	sos_ret_t sos_kmutex_init(struct sos_kmutex *mutex, const char *name,
	sos_kwaitq_ordering_t ordering)
mutex->owner = NULL;	mutex->owner = NULL;
return sos_kwaitq_init(& mutex->kwaitq, name);	return sos_kwaitq_init(& mutex->kwaitq, name, ordering);

 

../sos-code-article6.5/sos/ksynch.h (2005-01-04 04:13:49.000000000 +0100 )	../sos-code-article6.75/sos/ksynch.h (2005-01-04 04:13:53.000000000 +0100 )
Line 54	Line 54
* @param initial_value The value of the semaphore before any up/down	* @param initial_value The value of the semaphore before any up/down
*/	*/
sos_ret_t sos_ksema_init(struct sos_ksema *sema, const char *name,	sos_ret_t sos_ksema_init(struct sos_ksema *sema, const char *name,
int initial_value);	int initial_value,
	sos_kwaitq_ordering_t ordering);
/*	/*
Line 121	Line 122
*	*
* @param initial_value The value of the mutex before any up/down	* @param initial_value The value of the mutex before any up/down
*/	*/
sos_ret_t sos_kmutex_init(struct sos_kmutex *mutex, const char *name);	sos_ret_t sos_kmutex_init(struct sos_kmutex *mutex, const char *name,
	sos_kwaitq_ordering_t ordering);
/*	/*

 

../sos-code-article6.5/sos/kthread.c (2005-01-04 04:13:49.000000000 +0100 )	../sos-code-article6.75/sos/kthread.c (2005-01-04 04:13:53.000000000 +0100 )
Line 105	Line 105
/* Initialize the thread attributes */	/* Initialize the thread attributes */
strzcpy(myself->name, "[kinit]", SOS_KTHR_MAX_NAMELEN);	strzcpy(myself->name, "[kinit]", SOS_KTHR_MAX_NAMELEN);
myself->state           = SOS_KTHR_CREATED;	myself->state           = SOS_KTHR_CREATED;
	myself->priority        = SOS_SCHED_PRIO_LOWEST;
myself->stack_base_addr = init_thread_stack_base_addr;	myself->stack_base_addr = init_thread_stack_base_addr;
myself->stack_size      = init_thread_stack_size;	myself->stack_size      = init_thread_stack_size;
Line 126	Line 127
struct sos_kthread *sos_kthread_create(const char *name,	struct sos_kthread *sos_kthread_create(const char *name,
sos_kthread_start_routine_t start_func,	sos_kthread_start_routine_t start_func,
void *start_arg)	void *start_arg,
	sos_sched_priority_t priority)
__label__ undo_creation;	__label__ undo_creation;
struct sos_kthread *new_thread;	struct sos_kthread *new_thread;
if (! start_func)	if (! start_func)
return NULL;	return NULL;
	if (! SOS_SCHED_PRIO_IS_VALID(priority))
	return NULL;
/* Allocate a new kthread structure for the current running thread */	/* Allocate a new kthread structure for the current running thread */
new_thread	new_thread
Line 144	Line 148
/* Initialize the thread attributes */	/* Initialize the thread attributes */
strzcpy(new_thread->name, ((name)?name:"[NONAME]"), SOS_KTHR_MAX_NAMELEN);	strzcpy(new_thread->name, ((name)?name:"[NONAME]"), SOS_KTHR_MAX_NAMELEN);
new_thread->state    = SOS_KTHR_CREATED;	new_thread->state    = SOS_KTHR_CREATED;
	new_thread->priority = priority;
/* Allocate the stack for the new thread */	/* Allocate the stack for the new thread */
new_thread->stack_base_addr = sos_kmalloc(SOS_KTHREAD_STACK_SIZE, 0);	new_thread->stack_base_addr = sos_kmalloc(SOS_KTHREAD_STACK_SIZE, 0);
Line 223	Line 228
}	}
	sos_sched_priority_t sos_kthread_get_priority(struct sos_kthread *thr)
	{
	if (! thr)
	thr = (struct sos_kthread*)current_kthread;
	return thr->priority;
	}
sos_kthread_state_t sos_kthread_get_state(struct sos_kthread *thr)	sos_kthread_state_t sos_kthread_get_state(struct sos_kthread *thr)
{	{
if (! thr)	if (! thr)
Line 284	Line 298
}	}
	/**
	* Helper function to change the thread's priority in all the
	* waitqueues associated with the thread.
	*/
	static sos_ret_t _change_waitq_priorities(struct sos_kthread *thr,
	sos_sched_priority_t priority)
	{
	struct sos_kwaitq_entry *kwq_entry;
	int nb_waitqs;
	list_foreach_forward_named(thr->kwaitq_list, kwq_entry, nb_waitqs,
	prev_entry_for_kthread, next_entry_for_kthread)
	{
	SOS_ASSERT_FATAL(SOS_OK == sos_kwaitq_change_priority(kwq_entry->kwaitq,
	kwq_entry,
	priority));
	}
	return SOS_OK;
	}
	sos_ret_t sos_kthread_set_priority(struct sos_kthread *thr,
	sos_sched_priority_t priority)
	{
	__label__ exit_set_prio;
	sos_ui32_t flags;
	sos_ret_t retval;
	if (! SOS_SCHED_PRIO_IS_VALID(priority))
	return -SOS_EINVAL;
	if (! thr)
	thr = (struct sos_kthread*)current_kthread;
	sos_disable_IRQs(flags);
	/* Signal kwaitq subsystem that the priority of the thread in all
	the waitq it is waiting in should be updated */
	retval = _change_waitq_priorities(thr, priority);
	if (SOS_OK != retval)
	goto exit_set_prio;
	/* Signal scheduler that the thread, currently in a waiting list,
	should take into account the change of priority */
	if (SOS_KTHR_READY == thr->state)
	retval = sos_sched_change_priority(thr, priority);
	/* Update priority */
	thr->priority = priority;
	exit_set_prio:
	sos_restore_IRQs(flags);
	return retval;
	}
sos_ret_t sos_kthread_yield()	sos_ret_t sos_kthread_yield()
{	{
sos_ui32_t flags;	sos_ui32_t flags;

 

../sos-code-article6.5/sos/kthread.h (2005-01-04 04:13:49.000000000 +0100 )	../sos-code-article6.75/sos/kthread.h (2005-01-04 04:13:53.000000000 +0100 )
Line 62	Line 62
char name[SOS_KTHR_MAX_NAMELEN];	char name[SOS_KTHR_MAX_NAMELEN];
sos_kthread_state_t  state;	sos_kthread_state_t  state;
	sos_sched_priority_t priority;
/* The hardware context of the thread */	/* The hardware context of the thread */
struct sos_cpu_kstate *cpu_kstate;	struct sos_cpu_kstate *cpu_kstate;
Line 73	Line 74
{	{
struct	struct
{	{
	struct sos_sched_queue *rdy_queue;
struct sos_kthread     *rdy_prev, *rdy_next;	struct sos_kthread     *rdy_prev, *rdy_next;
} ready;	} ready;
}; /* Anonymous union (gcc extenion) */	}; /* Anonymous union (gcc extenion) */
Line 117	Line 119
*/	*/
struct sos_kthread *sos_kthread_create(const char *name,	struct sos_kthread *sos_kthread_create(const char *name,
sos_kthread_start_routine_t start_func,	sos_kthread_start_routine_t start_func,
void *start_arg);	void *start_arg,
	sos_sched_priority_t priority);
/**	/**
Line 135	Line 138
/**	/**
	* If thr == NULL, set the priority of the current thread. Trivial
	* function.
	*
	* @note NOT protected against interrupts
	*/
	sos_sched_priority_t sos_kthread_get_priority(struct sos_kthread *thr);
	/**
* If thr == NULL, get the state of the current thread. Trivial	* If thr == NULL, get the state of the current thread. Trivial
* function.	* function.
*	*
Line 144	Line 156
/**	/**
	* If thr == NULL, set the priority of the current thread
	*
	* @note NO context-switch ever occurs in this function !
	*/
	sos_ret_t sos_kthread_set_priority(struct sos_kthread *thr,
	sos_sched_priority_t priority);
	/**
* Yield CPU to another ready thread.	* Yield CPU to another ready thread.
*	*
* @note This is a BLOCKING FUNCTION	* @note This is a BLOCKING FUNCTION

 

../sos-code-article6.5/sos/kwaitq.c (2005-01-04 04:13:49.000000000 +0100 )	../sos-code-article6.75/sos/kwaitq.c (2005-01-04 04:13:53.000000000 +0100 )
Line 25	Line 25
sos_ret_t sos_kwaitq_init(struct sos_kwaitq *kwq,	sos_ret_t sos_kwaitq_init(struct sos_kwaitq *kwq,
const char *name)	const char *name,
	sos_kwaitq_ordering_t ordering)
memset(kwq, 0x0, sizeof(struct sos_kwaitq));	memset(kwq, 0x0, sizeof(struct sos_kwaitq));
Line 34	Line 35
name = "<unknown>";	name = "<unknown>";
strzcpy(kwq->name, name, SOS_KWQ_DEBUG_MAX_NAMELEN);	strzcpy(kwq->name, name, SOS_KWQ_DEBUG_MAX_NAMELEN);
#endif	#endif
	kwq->ordering = ordering;
list_init_named(kwq->waiting_list,	list_init_named(kwq->waiting_list,
prev_entry_in_kwaitq, next_entry_in_kwaitq);	prev_entry_in_kwaitq, next_entry_in_kwaitq);
Line 81	Line 83
/** Internal helper function equivalent to sos_kwaitq_add_entry(), but	/** Internal helper function equivalent to sos_kwaitq_add_entry(), but
without interrupt protection scheme, and explicit priority	without interrupt protection scheme */
ordering */	inline static sos_ret_t
inline static sos_ret_t _kwaitq_add_entry(struct sos_kwaitq *kwq,	_kwaitq_add_entry(struct sos_kwaitq *kwq,
struct sos_kwaitq_entry *kwq_entry)	struct sos_kwaitq_entry *kwq_entry,
	sos_sched_priority_t prio)
	struct sos_kwaitq_entry *next_entry = NULL, *entry;
	int nb_entries;
/* This entry is already added in the kwaitq ! */	/* This entry is already added in the kwaitq ! */
SOS_ASSERT_FATAL(NULL == kwq_entry->kwaitq);	SOS_ASSERT_FATAL(NULL == kwq_entry->kwaitq);
Line 96	Line 102
kwq_entry->wakeup_triggered = FALSE;	kwq_entry->wakeup_triggered = FALSE;
kwq_entry->wakeup_status    = SOS_OK;	kwq_entry->wakeup_status    = SOS_OK;
/* Add the thread in the list */	/* Insert this entry in the kwaitq waiting list */
list_add_tail_named(kwq->waiting_list, kwq_entry,	switch (kwq->ordering)
prev_entry_in_kwaitq, next_entry_in_kwaitq);	{
	case SOS_KWQ_ORDER_FIFO:
	/* Insertion in the list in FIFO order */
	{
	/* Add the thread in the list */
	list_add_tail_named(kwq->waiting_list, kwq_entry,
	prev_entry_in_kwaitq, next_entry_in_kwaitq);
	}
	break;
	case SOS_KWQ_ORDER_PRIO:
	/* Priority-driven insertion in the list */
	{
	/* Look for the place where to insert the thread in the queue (we
	want to order them in order of increasing priorities) */
	list_foreach_forward_named(kwq->waiting_list, entry, nb_entries,
	prev_entry_in_kwaitq, next_entry_in_kwaitq)
	{
	/* Does the thread we want to insert have higher priority than
	the given thread in the queue ? */
	if (SOS_SCHED_PRIO_CMP(prio,
	sos_kthread_get_priority(entry->kthread))
	> 0)
	{
	/* Yes: we insert before this given thread */
	next_entry = entry;
	break;
	}
	}
	/* Actually insert the entry in the list */
	if (next_entry != NULL)
	{
	list_insert_before_named(kwq->waiting_list, kwq_entry, next_entry,
	prev_entry_in_kwaitq,
	next_entry_in_kwaitq);
	}
	else
	{
	/* The thread we want to insert has less priority than any
	other in the list */
	list_add_tail_named(kwq->waiting_list, kwq_entry,
	prev_entry_in_kwaitq, next_entry_in_kwaitq);
	}
	}
	break;
	default:
	SOS_FATAL_ERROR("Invalid kwq ordering %d !\n", kwq->ordering);
	break;
	}
/* Update the list of waitqueues for the thread */	/* Update the list of waitqueues for the thread */
list_add_tail_named(kwq_entry->kthread->kwaitq_list, kwq_entry,	list_add_tail_named(kwq_entry->kthread->kwaitq_list, kwq_entry,
prev_entry_for_kthread, next_entry_for_kthread);	prev_entry_for_kthread, next_entry_for_kthread);
kwq_entry->kwaitq = kwq;	kwq_entry->kwaitq = kwq;
}	}
Line 117	Line 173
sos_ret_t retval;	sos_ret_t retval;
sos_disable_IRQs(flags);	sos_disable_IRQs(flags);
retval = _kwaitq_add_entry(kwq, kwq_entry);	retval = _kwaitq_add_entry(kwq, kwq_entry,
	sos_kthread_get_priority(kwq_entry->kthread));
return retval;	return retval;
Line 168	Line 225
sos_disable_IRQs(flags);	sos_disable_IRQs(flags);
retval = _kwaitq_add_entry(kwq, & kwq_entry);	retval = _kwaitq_add_entry(kwq, & kwq_entry,
	sos_kthread_get_priority(kwq_entry.kthread));
/* Wait for wakeup or timeout */	/* Wait for wakeup or timeout */
sos_kthread_sleep(timeout);	sos_kthread_sleep(timeout);
Line 203	Line 261
sos_disable_IRQs(flags);	sos_disable_IRQs(flags);
/* Wake up as much threads waiting in waitqueue as possible (up to	/* Wake up as much threads waiting in waitqueue as possible (up to
nb_kthreads), scanning the list in FIFO order */	nb_kthreads), scanning the list in FIFO/decreasing priority order
	(depends on the kwaitq ordering) */
prev_entry_in_kwaitq, next_entry_in_kwaitq))	prev_entry_in_kwaitq, next_entry_in_kwaitq))
{	{
Line 247	Line 306
return SOS_OK;	return SOS_OK;
}	}
	/* Internal function (callback for kthread subsystem) */
	sos_ret_t sos_kwaitq_change_priority(struct sos_kwaitq *kwq,
	struct sos_kwaitq_entry *kwq_entry,
	sos_sched_priority_t priority)
	{
	/* Reorder the waiting list */
	_kwaitq_remove_entry(kwq, kwq_entry);
	_kwaitq_add_entry(kwq, kwq_entry, priority);
	return SOS_OK;
	}

 

../sos-code-article6.5/sos/kwaitq.h (2005-01-04 04:13:49.000000000 +0100 )	../sos-code-article6.75/sos/kwaitq.h (2005-01-04 04:13:53.000000000 +0100 )
Line 21	Line 21
#include <sos/errno.h>	#include <sos/errno.h>
#include <sos/kthread.h>	#include <sos/kthread.h>
#include <sos/time.h>	#include <sos/time.h>
#include <sos/sched.h>
/**	/**
* @kwaitq.h	* @kwaitq.h
*	*
* Low-level functions to manage queues of threads waiting for a	* Low-level functions to manage queues of threads waiting for a
* resource. These functions are public. For higher-level	* resource. These functions are public, except
* synchronization primitives such as mutex, semaphores, conditions,	* sos_kwaitq_change_priority() that is a callback for the kthread
* ... prefer looking at the corresponding libraries.	* subsystem. However, for higher-level synchronization primitives
	* such as mutex, semaphores, conditions, ... prefer to look at the
	* corresponding libraries.
Line 45	Line 46
/**	/**
* Definition of a waitqueue. In a kwaitq, the threads are ordererd in	* The threads in the kwaitqs can be ordered in FIFO or in decreasing
* FIFO order.	* priority order.
	*/
	typedef enum { SOS_KWQ_ORDER_FIFO, SOS_KWQ_ORDER_PRIO } sos_kwaitq_ordering_t;
	#include <sos/sched.h>
	/**
	* Definition of a waitqueue. In a kwaitq, the threads can be ordererd
	* either in FIFO order (SOS_KWQ_ORDER_FIFO) or in decreasing priority
	* order (SOS_KWQ_ORDER_PRIO ; with FIFO ordering for same-prio
	* threads).
	*
	* A more efficient method to store the threads ordered by their
	* priority would have been to use 1 list for each priority level. But
	* we have to be careful to the size of a kwaitq structure here:
	* potentially there are thousands of kwaitq in a running system
	* (basically: 1 per opened file !). The algorithm we use to order the
	* threads in the kwaitq in this case is highly under-optimal (naive
	* linear insertion): as an exercise, one can implement a more
	* efficient algorithm (think of a heap).
struct sos_kwaitq	struct sos_kwaitq
{	{
Line 54	Line 76
# define SOS_KWQ_DEBUG_MAX_NAMELEN 32	# define SOS_KWQ_DEBUG_MAX_NAMELEN 32
char name[SOS_KWQ_DEBUG_MAX_NAMELEN];	char name[SOS_KWQ_DEBUG_MAX_NAMELEN];
#endif	#endif
	sos_kwaitq_ordering_t ordering;
struct sos_kwaitq_entry *waiting_list;	struct sos_kwaitq_entry *waiting_list;
};	};
Line 91	Line 114
* copied])	* copied])
*/	*/
sos_ret_t sos_kwaitq_init(struct sos_kwaitq *kwq,	sos_ret_t sos_kwaitq_init(struct sos_kwaitq *kwq,
const char *name);	const char *name,
	sos_kwaitq_ordering_t ordering);
/**	/**
Line 166	Line 190
/**	/**
* Wake up as much as nb_kthread threads (SOS_KWQ_WAKEUP_ALL to wake	* Wake up as much as nb_kthread threads (SOS_KWQ_WAKEUP_ALL to wake
* up all threads) in the kwaitq kwq, in FIFO order.	* up all threads) in the kwaitq kwq, in FIFO or decreasing priority
	* order (depends on the ordering scheme selected at kwaitq
	* initialization time).
* @param wakeup_status The value returned by sos_kwaitq_wait() when	* @param wakeup_status The value returned by sos_kwaitq_wait() when
* the thread will effectively woken up due to this wakeup.	* the thread will effectively woken up due to this wakeup.
Line 177	Line 203
#define SOS_KWQ_WAKEUP_ALL (~((unsigned int)0))	#define SOS_KWQ_WAKEUP_ALL (~((unsigned int)0))
	/**
	* @note INTERNAL function (in particular: interrupts not disabled) !
	*
	* @note: The use of this function is RESERVED (to kthread.c). Do not
	* call it directly: use sos_kthread_set_priority() for that !
	*/
	sos_ret_t sos_kwaitq_change_priority(struct sos_kwaitq *kwq,
	struct sos_kwaitq_entry *kwq_entry,
	sos_sched_priority_t priority);
#endif /* _SOS_KWAITQ_H_ */	#endif /* _SOS_KWAITQ_H_ */

 

../sos-code-article6.5/sos/main.c (2005-01-04 04:13:49.000000000 +0100 )	../sos-code-article6.75/sos/main.c (2005-01-04 04:13:53.000000000 +0100 )
Line 261	Line 261
sos_disable_IRQs(flags);	sos_disable_IRQs(flags);
arg_b = (struct thr_arg) { .character='b', .col=0, .row=21, .color=0x14 };	arg_b = (struct thr_arg) { .character='b', .col=0, .row=21, .color=0x14 };
sos_kthread_create("YO[b]", demo_thread, (void*)&arg_b);	sos_kthread_create("YO[b]", demo_thread, (void*)&arg_b, SOS_SCHED_PRIO_TS_LOWEST);
arg_c = (struct thr_arg) { .character='c', .col=46, .row=21, .color=0x14 };	arg_c = (struct thr_arg) { .character='c', .col=46, .row=21, .color=0x14 };
sos_kthread_create("YO[c]", demo_thread, (void*)&arg_c);	sos_kthread_create("YO[c]", demo_thread, (void*)&arg_c, SOS_SCHED_PRIO_TS_LOWEST);
arg_d = (struct thr_arg) { .character='d', .col=0, .row=20, .color=0x14 };	arg_d = (struct thr_arg) { .character='d', .col=0, .row=20, .color=0x14 };
sos_kthread_create("YO[d]", demo_thread, (void*)&arg_d);	sos_kthread_create("YO[d]", demo_thread, (void*)&arg_d, SOS_SCHED_PRIO_TS_LOWEST-1);
arg_e = (struct thr_arg) { .character='e', .col=0, .row=19, .color=0x14 };	arg_e = (struct thr_arg) { .character='e', .col=0, .row=19, .color=0x14 };
sos_kthread_create("YO[e]", demo_thread, (void*)&arg_e);	sos_kthread_create("YO[e]", demo_thread, (void*)&arg_e, SOS_SCHED_PRIO_TS_LOWEST-2);
arg_R = (struct thr_arg) { .character='R', .col=0, .row=17, .color=0x1c };	arg_R = (struct thr_arg) { .character='R', .col=0, .row=17, .color=0x1c };
sos_kthread_create("YO[R]", demo_thread, (void*)&arg_R);	sos_kthread_create("YO[R]", demo_thread, (void*)&arg_R, SOS_SCHED_PRIO_RT_LOWEST);
arg_S = (struct thr_arg) { .character='S', .col=0, .row=16, .color=0x1c };	arg_S = (struct thr_arg) { .character='S', .col=0, .row=16, .color=0x1c };
sos_kthread_create("YO[S]", demo_thread, (void*)&arg_S);	sos_kthread_create("YO[S]", demo_thread, (void*)&arg_S, SOS_SCHED_PRIO_RT_LOWEST-1);
sos_restore_IRQs(flags);	sos_restore_IRQs(flags);
}	}
Line 432	Line 432
sos_sched_subsystem_setup();	sos_sched_subsystem_setup();
/* Declare the IDLE thread */	/* Declare the IDLE thread */
SOS_ASSERT_FATAL(sos_kthread_create("idle", idle_kthread, NULL) != NULL);	SOS_ASSERT_FATAL(sos_kthread_create("idle", idle_kthread, NULL,
	SOS_SCHED_PRIO_TS_LOWEST) != NULL);
/* Enabling the HW interrupts here, this will make the timer HW	/* Enabling the HW interrupts here, this will make the timer HW

 

../sos-code-article6.5/sos/mouse_sim.c (2005-01-04 04:13:49.000000000 +0100 )	../sos-code-article6.75/sos/mouse_sim.c (2005-01-04 04:13:53.000000000 +0100 )
Line 139	Line 139
void MouseSim(void)	void MouseSim(void)
{	{
//Creation du semaphore de protection de la carte	//Creation du semaphore de protection de la carte
SOS_ASSERT_FATAL(SOS_OK == sos_ksema_init(& SemMap, "SemMap", 1));	SOS_ASSERT_FATAL(SOS_OK == sos_ksema_init(& SemMap, "SemMap", 1,
	SOS_KWQ_ORDER_FIFO));
//Creation du semaphore de creation de souris	//Creation du semaphore de creation de souris
SOS_ASSERT_FATAL(SOS_OK == sos_ksema_init(& SemMouse, "SemMouse", 2));	SOS_ASSERT_FATAL(SOS_OK == sos_ksema_init(& SemMouse, "SemMouse", 2,
	SOS_KWQ_ORDER_FIFO));
//Creation de la carte	//Creation de la carte
SOS_ASSERT_FATAL(SOS_OK == CreateMap());	SOS_ASSERT_FATAL(SOS_OK == CreateMap());
Line 150	Line 152
//Creation du thread createur de souris	//Creation du thread createur de souris
SOS_ASSERT_FATAL(sos_kthread_create("MouseCreator",	SOS_ASSERT_FATAL(sos_kthread_create("MouseCreator",
(sos_kthread_start_routine_t)MouseCreator,	(sos_kthread_start_routine_t)MouseCreator,
0) != NULL);	0, SOS_SCHED_PRIO_TS_LOWEST-1) != NULL);
}	}
Line 778	Line 780
pElement->Color = SOS_X86_VIDEO_FG_LTRED;	pElement->Color = SOS_X86_VIDEO_FG_LTRED;
pElement->P = p;	pElement->P = p;
pElement->Way = 0;	pElement->Way = 0;
pElement->ThreadID = sos_kthread_create("Mouse", (sos_kthread_start_routine_t)Mouse, pElement);	pElement->ThreadID = sos_kthread_create("Mouse", (sos_kthread_start_routine_t)Mouse, pElement, SOS_SCHED_PRIO_TS_LOWEST-1);
{	{
sos_kfree((sos_vaddr_t)pElement);	sos_kfree((sos_vaddr_t)pElement);

 

../sos-code-article6.5/sos/sched.c (2005-01-04 04:13:49.000000000 +0100 )	../sos-code-article6.75/sos/sched.c (2005-01-04 04:13:53.000000000 +0100 )
Line 25	Line 25
/**	/**
* The definition of the scheduler queue. We could have used a normal	* The definition of the scheduler queue. We could have used a normal
* kwaitq here, it would have had the same properties. But, in the	* kwaitq here, it would have had the same properties (regarding
* definitive version (O(1) scheduler), the structure has to be a bit	* priority ordering mainly). But we don't bother with size
* more complicated. So, in order to keep the changes as small as	* considerations here (in kwaitq, we had better make the kwaitq
* possible between this version and the definitive one, we don't use	* structure as small as possible because there are a lot of kwaitq in
* kwaitq here.	* the system: at least 1 per opened file), so that we can implement a
	* much faster way of handling the prioritized jobs.
static struct	struct sos_sched_queue
unsigned int nr_threads;	unsigned int nr_threads;
struct sos_kthread *kthread_list;	struct sos_kthread *kthread_list[SOS_SCHED_NUM_PRIO];
} ready_queue;	};
	/**
	* 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()	sos_ret_t sos_sched_subsystem_setup()
{	{
memset(& ready_queue, 0x0, sizeof(ready_queue));	memset(sched_queue, 0x0, sizeof(sched_queue));
	active_queue  = & sched_queue[0];
	expired_queue = & sched_queue[1];
return SOS_OK;	return SOS_OK;
}	}
Line 53	Line 70
* @param insert_at_tail TRUE to tell to add the thread at the end of	* @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.	* the ready list. Otherwise it is added at the head of it.
*/	*/
static sos_ret_t add_in_ready_queue(struct sos_kthread *thr,	static sos_ret_t add_in_ready_queue(struct sos_sched_queue *q,
	struct sos_kthread *thr,
{	{
	sos_sched_priority_t prio;
SOS_ASSERT_FATAL( (SOS_KTHR_CREATED == thr->state)	SOS_ASSERT_FATAL( (SOS_KTHR_CREATED == thr->state)
|| (SOS_KTHR_RUNNING == thr->state) /* Yield */	|| (SOS_KTHR_RUNNING == thr->state) /* Yield */
|| (SOS_KTHR_BLOCKED == thr->state) );	|| (SOS_KTHR_BLOCKED == thr->state) );
/* Add the thread to the CPU queue */	/* Add the thread to the CPU queue */
	prio = sos_kthread_get_priority(thr);
if (insert_at_tail)	if (insert_at_tail)
list_add_tail_named(ready_queue.kthread_list, thr,	list_add_tail_named(q->kthread_list[prio], thr,
else	else
list_add_head_named(ready_queue.kthread_list, thr,	list_add_head_named(q->kthread_list[prio], thr,
ready_queue.nr_threads ++;	thr->ready.rdy_queue = q;
	q->nr_threads ++;
/* Ok, thread is now really ready to be (re)started */	/* Ok, thread is now really ready to be (re)started */
thr->state = SOS_KTHR_READY;	thr->state = SOS_KTHR_READY;
Line 85	Line 106
if (SOS_KTHR_READY == thr->state)	if (SOS_KTHR_READY == thr->state)
return SOS_OK;	return SOS_OK;
/* Real-time thread: schedule it for the present turn */	if (SOS_SCHED_PRIO_IS_RT(sos_kthread_get_priority(thr)))
retval = add_in_ready_queue(thr, TRUE);	{
	/* 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;	return retval;
}	}
	sos_ret_t sos_sched_change_priority(struct sos_kthread *thr,
	sos_sched_priority_t priority)
	{
	struct sos_kthread *kthread_list;
	SOS_ASSERT_FATAL(SOS_KTHR_READY == thr->state);
	/* Temp variable */
	kthread_list
	= thr->ready.rdy_queue->kthread_list[sos_kthread_get_priority(thr)];
	list_delete_named(kthread_list, thr, ready.rdy_prev, ready.rdy_next);
	/* Update lists */
	kthread_list = thr->ready.rdy_queue->kthread_list[priority];
	list_add_tail_named(kthread_list, thr, ready.rdy_prev, ready.rdy_next);
	thr->ready.rdy_queue->kthread_list[priority] = kthread_list;
	return SOS_OK;
	}
struct sos_kthread * sos_reschedule(struct sos_kthread *current_kthread,	struct sos_kthread * sos_reschedule(struct sos_kthread *current_kthread,
sos_bool_t do_yield)	sos_bool_t do_yield)
{	{
	sos_sched_priority_t prio;
if (SOS_KTHR_ZOMBIE == current_kthread->state)	if (SOS_KTHR_ZOMBIE == current_kthread->state)
{	{
Line 107	Line 158
/* Take into account the current executing thread unless it is	/* Take into account the current executing thread unless it is
marked blocked */	marked blocked */
if (do_yield)	if (do_yield)
/* Ok, reserve it for next turn */	{
add_in_ready_queue(current_kthread, TRUE);	/* Ok, reserve it for next turn */
	if (SOS_SCHED_PRIO_IS_RT(sos_kthread_get_priority(current_kthread)))
	add_in_ready_queue(active_queue, current_kthread, TRUE);
	else
	add_in_ready_queue(expired_queue, current_kthread, TRUE);
	}
/* Put it at the head of the active list */	{
add_in_ready_queue(current_kthread, FALSE);	/* Put it at the head of the active list */
	add_in_ready_queue(active_queue, current_kthread, 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;
/* The next thread is that at the head of the ready list */	/* Now loop over the priorities in the active queue, looking for a
if (ready_queue.nr_threads > 0)	non-empty queue */
	for (prio = SOS_SCHED_PRIO_HIGHEST ; prio <= SOS_SCHED_PRIO_LOWEST ; prio ++)
struct sos_kthread *next_thr;	struct sos_kthread *next_thr;
	if (list_is_empty_named(active_queue->kthread_list[prio],
	ready.rdy_prev, ready.rdy_next))
	continue;
/* Queue is not empty: take the thread at its head */	/* Queue is not empty: take the thread at its head */
next_thr = list_pop_head_named(ready_queue.kthread_list,	next_thr = list_pop_head_named(active_queue->kthread_list[prio],
ready_queue.nr_threads --;	active_queue->nr_threads --;
return next_thr;	return next_thr;
}	}
SOS_FATAL_ERROR("No kernel thread ready ?!");	SOS_FATAL_ERROR("No kernel thread ready ?!");
return NULL;	return NULL;
}	}

 

../sos-code-article6.5/sos/sched.h (2005-01-04 04:13:49.000000000 +0100 )	../sos-code-article6.75/sos/sched.h (2005-01-04 04:13:53.000000000 +0100 )
Line 22	Line 22
/**	/**
* @file sched.h	* @file sched.h
*	*
* A basic scheduler with simple FIFO threads' ordering.	* A basic scheduler inspired from the O(1) Linux scheduler. Supports
	* 2 classes of thread priorities:
	*  - so-called 'real-time' threads scheduled according to a simple
	*    traditional static priority real-time scheduler. "Real-time" round
	*    robin scheduling is not supported.
	* - "fair" time-sharing scheduling for non real-time threads. "fair"
	*    because no starvation among the non real-time threads is
	*    possible. Contrary to the original O(1) Linux scheduler, the
	*    on-line adjustment of the scheduling priorities to cope with
	*    interactive/non interactive threads discrimination is not
	*    supported: threads keep having the same priority as long as the
	*    user does not change it.
* The functions below manage CPU queues, and are NEVER responsible	* The functions below manage CPU queues, and are NEVER responsible
* for context switches (see kthread.h for that) or synchronizations	* for context switches (see kthread.h for that) or synchronizations
Line 39	Line 50
#include <sos/errno.h>	#include <sos/errno.h>
	/**
	* The definition of a priority
	*/
	typedef unsigned char sos_sched_priority_t;
#include <sos/kthread.h>	#include <sos/kthread.h>
/**	/**
	* Valid priority interval ("real-time" and non real-time threads altogether)
	*/
	#define SOS_SCHED_PRIO_HIGHEST 0
	#define SOS_SCHED_PRIO_LOWEST  63
	#define SOS_SCHED_NUM_PRIO     64
	/**
	* Class-specific priorities
	*/
	#define SOS_SCHED_PRIO_RT_HIGHEST 0  /**< Highest 'real-time' static prio. */
	#define SOS_SCHED_PRIO_RT_LOWEST  15 /**< Lowest 'real-time' static priority */
	#define SOS_SCHED_PRIO_TS_HIGHEST 16 /**< Highest time-sharing priority */
	#define SOS_SCHED_PRIO_TS_LOWEST  63 /**< Lowest time-sharing priority */
	#define SOS_SCHED_PRIO_DEFAULT 40    /**< Default priority */
	/**
	* Helper macros (Yes, priorities ordered in decreasing numerical value)
	*
	* @note: The use of this function is RESERVED
	*/
	#define SOS_SCHED_PRIO_CMP(prio1,prio2)  ((prio1) - (prio2))
	#define SOS_SCHED_PRIO_IS_VALID(prio) \
	({ int __prio = (int)(prio); \
	((__prio) <= SOS_SCHED_PRIO_LOWEST) \
	&& \
	((__prio) >= SOS_SCHED_PRIO_HIGHEST); })
	#define SOS_SCHED_PRIO_IS_RT(prio)    \
	({ int __prio = (int)(prio); \
	((__prio) <= SOS_SCHED_PRIO_RT_LOWEST) \
	&& \
	((__prio) >= SOS_SCHED_PRIO_RT_HIGHEST); })
	/**
* Initialize the scheduler	* Initialize the scheduler
*	*
* @note: The use of this function is RESERVED	* @note: The use of this function is RESERVED
Line 72	Line 128
struct sos_kthread * sos_reschedule(struct sos_kthread * current_kthread,	struct sos_kthread * sos_reschedule(struct sos_kthread * current_kthread,
sos_bool_t do_yield);	sos_bool_t do_yield);
	/**
	* Called by kthread subsystem each time a READY thread's priority is
	* changed
	*
	* @note: The use of this function is RESERVED (to kthread.c)
	*/
	sos_ret_t sos_sched_change_priority(struct sos_kthread * thr,
	sos_sched_priority_t priority);
#endif /* _SOS_WAITQUEUE_H_ */	#endif /* _SOS_WAITQUEUE_H_ */

 

../sos-code-article6.5/VERSION (2005-01-04 04:13:47.000000000 +0100 )	../sos-code-article6.75/VERSION (2005-01-04 04:13:51.000000000 +0100 )
Line 1	Line 1
SOS -- Simple OS	SOS -- Simple OS
Copyright (C) 2003,2004,2005 The SOS Team (David Decotigny & Thomas Petazzoni)	Copyright (C) 2003,2004,2005 The SOS Team (David Decotigny & Thomas Petazzoni)
Version "Article 6 (2nd part [FIFO])" -- Basic kernel thread and	Version "Article 6 (2nd part)" -- Basic kernel thread and synchronization API
synchronization API with basic	with priority ordering and O(1)-style
FIFO scheduler	scheduler (Linux)
This program is free software; you can redistribute it and/or	This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License	modify it under the terms of the GNU General Public License

File list:
    ../sos-code-article6.75/sos/ksynch.c
    ../sos-code-article6.75/sos/ksynch.h
    ../sos-code-article6.75/sos/kthread.c
    ../sos-code-article6.75/sos/kthread.h
    ../sos-code-article6.75/sos/kwaitq.c
    ../sos-code-article6.75/sos/kwaitq.h
    ../sos-code-article6.75/sos/main.c
    ../sos-code-article6.75/sos/mouse_sim.c
    ../sos-code-article6.75/sos/sched.c
    ../sos-code-article6.75/sos/sched.h
    ../sos-code-article6.75/VERSION