Bashar Kokash

Computer data structures: Stacks and Queues

Stacks and Queues are common computer data structures in almost all operating systems, if not all computer programs heavily rely on at least one of them. In abstract, both are a type of linked-lists; a linked list is a dynamic data structure, unlike arrays that have limited capacity and few inefficient data manipulation techniques. The linked list consists of multiple linked items or nodes; each contains the item’s value and a pointer to the next node in the list.

Linked list

The list is considered dynamic compared to an array because it is easier to manipulate its items. Inserting an item at a certain location requires updating only two pointers. First, the new node is created, and it is allocated in the memory, its next node pointer is pointed to the next note in the inserted location, and the previous node should update its next node to point to this new node address.

That means list nodes are not necessary to be allocated in a sequence in the physical memory. In contrast, an array of 5 items will allocate five sequential spaces in the memory. Still, lists do not support random access to nodes; so, in a ten nodes list, to access the 6th node, we will have to traverse through the list starting from the first node until we reach the requested node.

In general, a stack is a group of items on top of each other like a pile of plates; any new plate is added only on top. To use any plate, we start by the plate on top, so to use the first plate at the bottom, we must remove all the plates starting from the top one by one until we reach the required plate. This approach is called last in first out (LIFO).

Stack and queue operations, Algorithms and data structures (2008)

A queue, in turn, is as simple as people waiting at a bus station, any new person will join the waiting and will stand at the end of the queue. When the bus arrives, people at the beginning of the line will get on the bus; first in first out (FIFO).

In both cases, stack and queue have the basic common features of a linked list, but it is their independent functionalities that make the distinction between a FIFO and a LIFO list.

Now, representing those data structures in linked lists will be as below; a queue will have a front and rear node; applying the FIF concept, new items are inserted at the rear node, and nodes are removed from the first node. Similarly, a stack will have top and bottom nodes; a FIFO stack will add new nodes to the top and removes items also from the top.

Queue using a linked list, Art of Computer Programming (1997)
Queue using a linked list, Art of Computer Programming (1997)

Now we know what are linked lists, queues, and stacks, but what do they do?

How operating systems use Queues?

Memory Management

Multiprogramming computer operating systems use queues in almost all its main components, including memory and process management. For example, in a fixed memory partitioning management approach, by default, the operating system will assign the process to the smallest partition that can fit the partition. However, what will happen when a process comes and the memory as several available small partitions? Alternatively, what will happen to a new process if all the partitions are occupied?

To solves this issue, operating systems use a single queue as per the figure below; when new processes enter, the queue is waiting for a suitable memory partition to be assigned. A stack, in this case, will not work, using a LIFO stack, the operating system will keep serving the newly coming processing, while old processes must wait until a suitable partition is available and no more additional processes are available.

Memory Assignment for fixed partitioning, operating systems (2011)

Process Management

Operating systems use queues also in process management, especially when managing process status between ready, waiting, running. The diagram below shows how the operating system manages several queues to handle processes; queues can be categories as short term; those that store processes that are ready to be processed. While the long-term queues are to store processes that are waiting for external events or other processes. Each input/output device has his queue as well; if two processes are waiting for the printer to use, both processes will be waiting in the printer queue.

Key Elements of an Operating System for Multiprogramming, Operating Systems (2011)

Also, the Unix operating system uses queues in Pipes as one of the techniques for interposes communication, which allows a process to write to the queue while another process reads its content.

Issues in memory and process management are sources for deadlocks.

How Operating Systems use Stacks?

The general use of stack data structure in operating systems is to keep track of branches and subroutine calls. Each process has one or more last-in-first-out (LIFO) stacks that are used to store parameters and calling addresses for procedure and system calls.

For example, let’s consider the following pseudo-code: The main process calls PrepareCoffee() routine that in turn, calls the GetSugar() subroutine. Before this call, the process must save the instruction address so it can get back to the same location and continue execution, the address of this instruction is pushed to the stack, so now it has only one item.

The execution context switches to the GetSugar() subroutine, which in turn calls PurchaseSugare(), again the process should save the caller location, so the address eight is pushed to the stack.

Then the execution context also switches to the PurchaseSugar() subroutine, which calls OrderOnline(), again the process saves the caller location, so the address 11 is pushed to the stack

Stack example step 3

When the call OrderOnline() subroutine finishes execution, the process will pop the stack and will use address 11 to continue the execution of PurchaseSugar() subroutine. Again, when PurchaseSugar() finishes execution, the process will pop the stack again to get the value 8, so it can continue the execution or GetSugar() subroutine. In turn, when it finishes the process will pop the stack and return to the instruction at address 2, the stack will be empty now, and execution context will be back to where it started at PrepareCoffee routine.

To understand more how the operating system uses stacks and queues inprocess and memory management I would recommend reading the Operating Systems book for William Stallings.

Exit mobile version