Subversion Repositories shark

Rev

Details | Last modification | View Log | RSS feed

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