Input queue

In computer science, an input queue is a collection of processes in storage that are waiting to be brought into memory to run a program. Input queues are mainly used in Operating System Scheduling which is a technique for distributing resources among processes. Input queues, not only apply to Operating System (OS), it may be applied to scheduling which is used for networking devices. The purpose of scheduling is to ensure resources are being distributed fairly and effectively; therefore, it improves the performance of the system.

Essentially, a queue is a collection which has data added in the rear position and removed from the front position. There are many different types of queues, and the ways they operate maybe totally different. Operating System’s use First-Come-First-Serve queue,Shortest remaining time, Fixed priority pre-emptive scheduling, Round-robin scheduling, and Multilevel queue scheduling. Network devices use First-In-First-Out queue, Weighted fair queue, Priority queue and Custom queue.

Operating System

In Operating System’s processes are loading into memory, and wait for their turn to be executed by the Central Processing Unit (CPU). CPU scheduling manages process states and decides when a process will be executed next by using the input queue.

First-Come-First-Serve

First-Come-First-Serve processes are taken out from the queue in consecutive order that they are put into the queue. This method is simple causing poor performance because every process is treated equally. If process A that takes 5 minutes to execute and comes into the queue before process B, which is extremely important, B still has to wait until A finished its job. This method is fair, but it takes long time to process.
Shortest remaining time

Shortest remaining time method tries to predict the processing time of developments and places them into the queue from the smallest to largest processing time. This method estimates and predicts based on prior history records. In term, its performance is not stable but better improves process waiting time than First-Come-First-Serve.
Fixed priority pre-emptive scheduling

Fixed priority pre-emptive scheduling method assigns different priorities to the processes based on their processing time and arranges them into the queue in order of their priorities. CPU server processes from higher to lower priority, and processes which have the same priority are served as First-Come-First-Serve. The CPU will temporary stop serving low priority process when higher priority process coming into the queue.
Round-robin scheduling

Round-robin scheduling method will give a same amount of time for each process and cycle through them. This method is heavily bases on allot time giving to each process. Too short allot time will fragment the processes, and too long allot time will increase waiting time for each process to be executed. Choosing right allot time is the foundation for this method.
Multilevel queue scheduling

Many queues are used in Multilevel queue scheduling method and each queue has its own scheduling algorithm. Multilevel queue scheduling is more complex compare to other methods, but it provides flexibility for OS to serve different data in complicated situation.

Networking

In networking, packets are the key foundation for scheduling. There are many different types of packet travelling around network core every day, and they are treated totally different. For example, voice and video packets have higher priority than normal packets. In order to manage and distribute packet effectively, network devices are also use input queue to determine which packet will be transmit first.
First in, first out queue (FIFO)

In this mode, packets are taken out from the queue in the order that they are coming from the queue. Every data is treated the same priority. If a large packet A comes before a small packet B, B still has to wait until A is completely served. If a system treats every packet the same, users can experience the delay in transmitting such as: voice packets.
Weighted fair queue (WFQ)

Weighted fair queue uses the min-max-fair-share algorithm to distribute packet. The min fair-share means the network OS will distribute equally minimum resource for each type of packet. The max fair-share means the network OS will provide more resource for packet that need to transfer large amount of date at that moment, but it will take the resource back after transferring. “Weighted” means the scheduler will assign weight for each type of packet. Base on the weight, it will determine how to put packet into the queue and serve them. Usually, each packet will be weighted base on IP Precedence field from IP header of each packet.

Fair allocation = (resource capacity – resource already allocated) / number of packets

Priority queue (PQ)

Priority queue is divided into 4 sub queues with different priorities. Data in each queue are only served when the higher priority queues are empty. If data come into the empty higher priority queue while the network OS is transferring data of lower priority queue, network OS will hold data of the lower priority queue and process data in higher priority queue first. The network OS does not care how long lower priority queues have to wait for their turn because eventually data will finishes each queue from highest to lowest priority first before moving the next queue. Within each queue, data are forwarded based on First-In-First-Out basis.
Custom queue (CQ)

Custom queue is divided into 17 different sub queues. The first queue, queue 0, is reserved for the OS to transmit system data, the other 16 queues are for user-defined data. User can define various important data and assign them into each queue. Each queue has limited size and it will drop all coming data if it reaches that limit. Each queue is serviced based on how much data is served in each queue. If that limit is met, the network OS will hold data of current queue and services the next queue until that queue is empty or it reaches its data limit. If one queue is empty, the iOS will skip that queue and service the next queue.

References

Stallings, William (2003). CCIE Practical Studies Volume II. Cisco Press. ISBN 1-58705-072-2.
Operating System Scheduling