WebSVN - shark - Blame - Rev 3 - /shark/trunk/kernel/queue.c

Rev	Author	Line No.	Line
2	pj	1	/*
		2	* Project: S.Ha.R.K.
		3	*
		4	* Coordinators:
		5	* Giorgio Buttazzo <giorgio@sssup.it>
		6	* Paolo Gai <pj@gandalf.sssup.it>
		7	*
		8	* Authors :
		9	* Paolo Gai <pj@gandalf.sssup.it>
		10	* (see the web pages for full authors list)
		11	*
		12	* ReTiS Lab (Scuola Superiore S.Anna - Pisa - Italy)
		13	*
		14	* http://www.sssup.it
		15	* http://retis.sssup.it
		16	* http://shark.sssup.it
		17	*/
		18
		19	/**
		20	------------
		21	CVS : $Id: queue.c,v 1.1.1.1 2002-03-29 14:12:52 pj Exp $
		22
		23	File: $File$
		24	Revision: $Revision: 1.1.1.1 $
		25	Last update: $Date: 2002-03-29 14:12:52 $
		26	------------
		27
		28	This file contains the system queues function management
		29	The functions use the general process descriptor table entries,
		30	particularly the next & prev to mantain the queues order;
		31	the insertion is based on the field priority, inserted in generic process
		32	descriptor to simplify the implementation of many schedulers (like EDF,
		33	RM, DM, etc.)
		34
		35	There are 2 queue types:
		36	QUEUE -> a simple queue with only head.
		37	QQUEUE -> a queue that manage the head and the tail of the queue
		38
		39	... and 2 queue function sets, beginning with q_ if related to the type
		40	QUEUE, qq_ if related to the other type.
		41
		42	The queue insertion is made by the following functions:
		43	q_insert, qq_insert -> insertion based on the priority field.
		44	q_timespec_insert, qq_timespec_insert -> same as above but use
		45	the timespec_priority field
		46	q_insertfirst, qq_insertfirst -> insert in the first position of the queue
		47
		48	**/
		49
		50	/*
		51	* Copyright (C) 2000 Paolo Gai
		52	*
		53	* This program is free software; you can redistribute it and/or modify
		54	* it under the terms of the GNU General Public License as published by
		55	* the Free Software Foundation; either version 2 of the License, or
		56	* (at your option) any later version.
		57	*
		58	* This program is distributed in the hope that it will be useful,
		59	* but WITHOUT ANY WARRANTY; without even the implied warranty of
		60	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
		61	* GNU General Public License for more details.
		62	*
		63	* You should have received a copy of the GNU General Public License
		64	* along with this program; if not, write to the Free Software
		65	* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
		66	*
		67	*/
		68
		69
		70	#include <kernel/const.h>
		71	#include <sys/types.h>
		72	#include <kernel/var.h>
		73
		74	/*
		75	*
		76	* QUEUE Functions
		77	*
		78	*/
		79
		80	/*+
		81	This function insert the task with PID p in the queue que.
		82	The insertion is made respecting the priority field.
		83	(the first item in the queue have the less priority)
		84	+*/
		85
		86	void q_insert(PID i, QUEUE *que)
		87	{
		88	DWORD prio;
		89	PID p,q;
		90
		91	p = NIL;
		92	q = *que;
		93	prio = proc_table[i].priority;
		94
		95	while ((q != NIL) && (prio >= proc_table[q].priority)) {
		96	p = q;
		97	q = proc_table[q].next;
		98	}
		99
		100	if (p != NIL)
		101	proc_table[p].next = i;
		102	else
		103	*que = i;
		104
		105	if (q != NIL) proc_table[q].prev = i;
		106
		107	proc_table[i].next = q;
		108	proc_table[i].prev = p;
		109	}
		110
		111	/*+
		112	This function insert the task with PID p in the queue que.
		113	The insertion is made respecting the timespec_priority field.
		114	(the first item in the queue have the less priority)
		115	+*/
		116
		117	void q_timespec_insert(PID i, QUEUE *que)
		118	{
		119	struct timespec prio;
		120	PID p,q;
		121
		122	p = NIL;
		123	q = *que;
		124
		125	TIMESPEC_ASSIGN(&prio, &proc_table[i].timespec_priority);
		126
		127
		128	while ((q != NIL) &&
		129	!TIMESPEC_A_LT_B(&prio, &proc_table[q].timespec_priority)) {
		130	p = q;
		131	q = proc_table[q].next;
		132	}
		133
		134	if (p != NIL)
		135	proc_table[p].next = i;
		136	else
		137	*que = i;
		138
		139	if (q != NIL) proc_table[q].prev = i;
		140
		141	proc_table[i].next = q;
		142	proc_table[i].prev = p;
		143	}
		144
		145
		146	/*+
		147	This function extract the task i from the queue que.
		148	It not check if the task i is REALLY IN the queue que...
		149	so make attention!!!
		150	+*/
		151	void q_extract(PID i, QUEUE *que)
		152	{
		153	PID p,q;
		154
		155	p = proc_table[i].prev;
		156	q = proc_table[i].next;
		157
		158	if (p == NIL) *que = q;
		159	else proc_table[p].next = proc_table[i].next;
		160
		161	if (q != NIL) proc_table[q].prev = proc_table[i].prev;
		162	}
		163
		164	/*+
		165	This function returns the first task in the queue que, or NIL if the
		166	queue is empty... (it extracts the task from the queue...)
		167	+*/
		168	PID q_getfirst(QUEUE *que)
		169	{
		170	QUEUE q = *que;
		171	if (*que == NIL) return(NIL);
		172	*que = proc_table[q].next;
		173	if (que != NIL) proc_table[que].prev = NIL;
		174	return(q);
		175	}
		176
		177	/*+
		178	This function insert the task with PID p in the first position
		179	of the queue que redardless of the priority field
		180	+*/
		181
		182	void q_insertfirst(PID i, QUEUE *que)
		183	{
		184	if (que != NIL) proc_table[que].prev = i;
		185	proc_table[i].next = *que;
		186	proc_table[i].prev = NIL;
		187	*que = i;
		188	}
		189
		190
		191

Subversion Repositories shark

(root)/shark/trunk/kernel/queue.c - Rev 3