KERNEL DESIGN ISSUES - Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications - page 370

head index

p q

NIL

to

first last

remove

NIL

Figure 10.13 Extracting a TCB from a queue.

The major advantage of using bidirectional pointers is in the implementation of the
extraction operation, which can be realized in one step without scanning the whole
queue. Figure 10.13 illustrates the extraction of a generic element, whereas Fig-
ure 10.14 shows the extraction of the element at the head of the queue.

/*-----------------------------------------------------------*/
/* extract -- a task from a queue */
/*-----------------------------------------------------------*/
proc

extract (proc i, queue *que)

int

p, q; /* auxiliary pointers */

p = vdes[i].prev;
q = vdes[i].next;
if (p == NIL) *que = q; /* first element */

else vdes[p].next = vdes[i].next;
if (q != NIL) vdes[q].prev = vdes[i].prev;
return(i);

}