In our first VIOTW we discussed PUSH and POP; stack instructions. This week's instructions are INSQUE and REMQUE; queue instructions. So the first thing we need to do is define a queue. You may think you already know what a queue is, but a VAX queue doesn't necessarily work like the queue on another platform. The standard definition of a queue is a data structure for storing data that is accessible in FIFO order; First In First Out. If you've already read PUSH and POP then you know how a stack allows you to put data on it's top , and retreive it off of the same end (the top). A standard queue allows you to put data on the top, but access it only from the bottom; first in first out. A data queue on an IBM AS/400 (IBM designation *DTAQ) is a classical queue; IBM allows you to define a LIFO queue and create a stack out of a data queue, but we're interested in the queue version for this VIOTW. When you retrieve data from an AS/400 data queue you are retrieving the first data element put in it, but you can't retreive it again unless you put it back on the queue.
A VAX queue is a circular, doubly linked list.
| Head Forward Link |
| Head Backwards Link |
| . |
| . |
| . |
| Tail Forward Link |
| Tail Backwards Link |
If you're not familiar with linked lists then I recommend you look up a description of one in a book on data structures and algorithms; Robert Sedgwick has written several of these. As said earlier, a VAX queue is circular; the forward link of the tail points to th head, and the backwards link of the head points to the tail. As you traverse the queue you keep running in a circle, but you know you are at the last element when it points to the tail; likewise, you are at the tail when the element is pointing at the head. You know you are at the head when the element has a backwards pointer to the tail; the first data element has a backward pointer to the head. So we always have all the data we need for knowing when we are at the end points of the queue; we can always put elements at the front or back of the queue. As far as inserting elements into the queue, we can always put an element after the element we are currently pointing to (we have full info to perform this task. What are these tasks?
These four tasks (complicated tasks) can be performed by one machine
statement!
INSQUE entry, predecessor
These two steps (once again, complex steps) can be performed by another
single instruction!
REMQUE entry, destination
VMS was developed alongside VAX architecture, so it was possible for DEC to created machine instructions that performed complex operating system tasks. A processor that can perform complex instructions is called a CISC processor; Complex Instruction Set Computer. To perform these complex instructions, a CISC requires microcode. Microcode can be thought as subroutines stored in the CPU that are called up when a complex instruction is executed. Since complex instructions involve a subroutine call they require more processor time then simple instruction like MOVL. Another type of processor only performs simple instructions; RISC - Reduced Instruction Set Computer. RISC processors boast more MIPS then CISC processors, but they require more instructions to perform tasks like insert into a queue. So even though VAX computers can't claim the high megahertz numbers of a RISC processor they still deliver high throughput