Input queue

Key takeaways

Input queue belongs to computer science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Input queue to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Input queue from memory before moving on to harder problems.

Reference excerpt

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.

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.

Worked examples

Example 1 — a first encounter with Input queue

Start with the simplest possible case. Write down what Input queue claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In computer science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Input queue before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Input queue ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Input queue

In research: Input queue appears in computer science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Input queue in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Input queue is common in secondary-school and first-year university syllabi. It links to neighbouring topics Computing terminology, Queueing theory, so understanding it makes those chapters shorter.
In everyday life: Look for Input queue outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

How to study Input queue in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Input queue means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Input queue out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Input queue in simple terms?

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.

Why does Input queue matter?

Because it connects several computer science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Input queue?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Input queue.