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 systems (OS), but may also be applied to scheduling inside 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 may be totally different. Operating systems use First-Come, First-Served queues, 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 systems, processes are loaded 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-in, First-out

First-in, First-out processes are taken out from the queue in consecutive order that they are put into the queue. With this method, every process is treated equally. If there are two processes of different priority and the lower priority process enters the queue first, it will be executed first. This approach may not be ideal if different processes have different priorities, especially if the processes are long running.

Shortest remaining time

The 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-Served.

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-Served. 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 a lot of time consuming to each process. Too short a lot time will fragment the processes, and too long a lot time will increase waiting time for each process to be executed. Choosing right a lot time is the foundation for this method.^{[clarification needed]}

Multilevel queue scheduling

The Multilevel queue scheduling method employs several queues, and each queue may have its own scheduling algorithm. Multilevel queue scheduling is more complex compared to other methods, but it provides flexibility for OS to serve different response time requirements in complicated situations.

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 also use input queue to determine which packet will be transmitted 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 packet 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 packets. 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 packets 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 based 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 it always finishes each queue from highest to lowest priority first before moving to the next queue. Within each queue, packets 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 network OS to transmit system packet, the other 16 queues are for user-defined packets. User can define various important packets and assign them into each queue. Each queue has limited size and it will drop all coming packets if it reaches that limit. Each queue is serviced based on how much packets are served in each queue. If that limit is met, the network OS will hold packets of current queue and services the next queue until that queue is empty or it reaches its packet limit. If one queue is empty, the network OS 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
Operating System - Scheduling
OS Scheduling and Buffering