What is Run Queue

Every processor in a CPU has queue called runqueue associated with it. Each runqueue has 2 priority arrays, the active and the expired. Active array stores the processes that still have some time slice. Once this time finished, they go to the expired array. Each array has 140 entries (queues), one for each privilege level (So 140 + 140 ).

Run queue has priority values for each process, which will be used by the scheduler to determine which process to run next. To ensure each program has a fair share of resources, each one is run for some time period (quantum) before it is paused and placed back into the run queue. When a program is stopped to let another run, the program with the highest priority in the run queue is then allowed to execute. Active processes are placed in an array called a run queue

Processes are also removed from the run queue when they ask to sleep, are waiting on a resource to become available, or have been terminated.

In the Linux operating system (prior to kernel 2.6.23), each CPU in the system is given a run queue, which maintains both an active and expired array of processes.The scheduler selects the next process from the active array with highest priority. When a process' quantum expires, it is placed into the expired array with some priority.

How to Check 

a) sar -q command is used to check the run queue.

runq-sz : Run queue length (number of tasks waiting for run time)

plist-sz : Number of tasks in the task list.

b) vmstat can also be used to determine the number of processes that are queued to run or waiting to run. These appear in the 'r' column.

What is Ready Queue and Run Queue

In operating system , Process that are ready to execute when given the opportunity to execute are sent to ready queue.

Whenever there is a space in run queue, for running the process, Process from ready state in ready queue is sent to run queue.

What is Thread, Core and Socket

The central processing unit (CPU) in your computer does the computational work — running programs. But one single-core CPU can only perform one task at a time, which is   where multiple CPUs, hyper-threading, and multi-core CPUs come into play.

Having more than a single CPU allows multiple programs to run at the same time, ensuring your computer stays responsive — especially while multitasking or performing computationally-demanding tasks like video encoding.

Thread - Logical CPU
Core - Physical CPU core unit

Multiple CPUs

Before hyper-threading and multi-core CPUs came around, people attempted to add additional processing power to computers by adding additional CPUs. This requires a motherboard with more than one CPU socket — multiple CPUs are inserted into different sockets. The motherboard also needs additional hardware to connect those CPU sockets to the RAM and other resources. There’s a lot of overhead here — there’s additional latency if the CPUs need to communicate with each other, systems with multiple CPU will consume more power,  and the motherboard needs more sockets and hardware.

This isn’t very common among home-user PCs today. Even a high-powered gaming desktop with multiple graphics cards will generally only have a single CPU. You’ll find multi-CPU systems among supercomputers, servers, and similar high-end systems that need as much number-crunching power as they can get.

cpu-socket-on-motherboard

Hyper-Threading Technology

Hyper-threading was Intel’s first attempt to bring parallel computation to consumer PCs. It debuted on desktop CPUs with the Pentium 4 HT back in 2002. The original Pentium 4 had just a single CPU core, so it could only do one thing at a time — but hyper-threading attempted to make up for that.

A single physical CPU core with hyper-threading appears as two logical CPUs to an operating system. The CPU is still a single CPU, so it’s “cheating” a bit — while the operating system sees two CPUs for each core, the actual CPU hardware only has a single set of execution resources for each core. The CPU pretends it has more cores than it does, and it uses its own logic to speed up program execution. Hyper-threading allows the two logical CPU cores to share physical execution resources. This can speed things up somewhat — if one virtual CPU is stalled and waiting, the other virtual CPU can borrow its execution resources. Hyper-threading can help speed your system up, but it’s nowhere near as good as having additional cores.

Thankfully, hyper-threading is now a “bonus.” While the original consumer processors with hyper-threading only had a single core that masqueraded as multiple cores, modern Intel CPUs now have both multiple cores and hyper-threading technology. Your dual-core CPU with hyper-threading appears as four cores to your operating system, while your quad-core CPU with hyper-threading appears as eight cores. Hyper-threading is no substitute for additional cores, but a dual-core CPU with hyper-threading should perform better than a dual-core CPU without hyper-threading.

Multi-Core CPUs

Originally, CPUs had a single core. That meant the physical CPU had a single central processing unit on it. To increase performance, manufacturers add additional “cores,” or central processing units. A dual-core CPU has two central processing units, so it appears to the operating system as two CPUs. A different process can be using each core at the same time. This speeds up your system, because your computer can do multiple things at once.

Unlike hyper-threading, there are no tricks here — a dual-core CPU literally has two central processing units on the CPU chip. A quad-core CPU has four central processing units, an octa-core CPU has eight central processing units, and so on.

This helps dramatically improve performance while keeping the physical CPU unit small so it fits in a single socket. There only needs to be a single CPU socket with a single CPU unit inserted into it — not four different CPU sockets with four different CPUs, each needing their own power, cooling, and other hardware. There’s less latency because the cores can communicate more quickly, as they’re all on the same chip.

Most computers now have multi-core CPUs, which is the most efficient option here. However, Intel CPUs also have hyper-threading as a bonus. Some computers that need a large amount of CPU power may have multiple CPUs, but it’s much less efficient than it sounds. Multi-core CPUs are also found on smartphones and tablets, and they’re useful for the same reason.

The more CPUs or cores a computer has, the more things it can do at once. This helps improve performance across everything you do — even if you’re just doing one thing at a time, the computer needs to perform background tasks. With a multi-core CPU, it can use other cores for such background tasks to avoid slowing your programs down. The advent of dual-core CPUs offered a dramatically better desktop experience to PC users.

To find the number of socket's:

$ cat /proc/cpuinfo | grep "^physical id" | sort | uniq | wc -l

2

To find the number of cores per CPU:

$ cat /proc/cpuinfo | grep "^cpu cores" | uniq

cpu cores       : 4

The total number of processors available is the number of physical CPUs multiplied by the number of cores per CPU.

To find the total number of processors:

$ cat /proc/cpuinfo | grep "^processor" | wc -l

16

To find the threads per socket

$ lscpu | grep -i thread

About Real time, User time and SYS time

In OS CPU Real, User and Sys process time statistics

One of these things is not like the other. Real refers to actual elapsed time; User and Sys refer to CPU time used only by the process.

1) What is Real Time

Real time is wall clock time - It's the time taken to start and finish the entire execution. 

2) What is User Time

It is the  the amount of CPU time spent in user-mode code (outside the kernel) within the process. This is only actual CPU time used in executing the process. Other processes and time the process spends blocked do not count towards this figure. If you want to know more about CPU time there is separate post where CPU time is well explained.

2) What is System Time

System time is the amount of CPU time spent in the kernel within the process. Which means executing CPU time spent in system calls within the kernel, as opposed to library code, which is still running in user-space. Like 'user', this is only CPU time used by the process. See below for a brief description of kernel mode (also known as 'supervisor' mode) and the system call mechanism.

User+Sys -  will tell you how much actual CPU time your process used. Note that this is across all CPUs, so if the process has multiple threads (and this process is running on a computer with more than one processor) it could potentially exceed the wall clock time reported by Real (which usually occurs). 

The rule of thumb is:

real < user: The process is CPU bound and takes advantage of parallel execution on multiple cores/CPUs.

real ≈ user: The process is CPU bound and takes no advantage of parallel exeuction.

real > user: The process is I/O bound. Execution on multiple cores would be of little to advantage

http://stackoverflow.com/questions/556405/what-do-real-user-and-sys-mean-in-the-output-of-time

A program is CPU bound if it would go faster if the CPU were faster, i.e. it spends the majority of its time simply using the CPU (doing calculations). A program that computes new digits of π will typically be CPU-bound, it's just crunching numbers.

A program is I/O bound if it would go faster if the I/O subsystem was faster. Which exact I/O system is meant can vary; I typically associate it with disk. A program that looks through a huge file for some data will often be I/O bound, since the bottleneck is then the reading of the data from disk.

CPU Bound means the rate at which process progresses is limited by the speed of the CPU. A task that performs calculations on a small set of numbers, for example multiplying small matrices, is likely to be CPU bound.

I/O Bound means the rate at which a process progresses is limited by the speed of the I/O subsystem. A task that processes data from disk, for example, counting the number of lines in a file is likely to be I/O bound.

Memory bound means the rate at which a process progresses is limited by the amount memory available and the speed of that memory access. A task that processes large amounts of in memory data, for example multiplying large matrices, is likely to be Memory Bound.

Cache bound means the rate at which a process progress is limited by the amount and speed of the cache available. A task that simply processes more data than fits in the cache will be cache bound.

I/O Bound would be slower than Memory Bound would be slower than Cache Bound would be slower than CPU Bound.

How to Calculate CPU Usage and What are the States of CPU

List of Topics

1) How to Calculate CPU Usage
2) What is CPU Time
3) States of CPU

1) How to Calculate CPU Usage

Normally in Operation System CPU usage is calculated based on CPU time. 

2) What is CPU time

CPU time is allocated in discrete time slices (ticks). For a certain number of time slices, the CPU is busy, other times it is not (which is represented by the idle process). In the picture below the CPU is busy for 5 of the 10 CPU slices. 5/10 = .50 = 50% of busy time (and there would therefore be 40% idle time).

Will explain in breif with the help sample top command output

Top Output  : Cpu(s):  0.7%us,  0.7%sy,  0.0%ni, 98.7%id,  0.0%wa,  0.0%hi,  0.0%si,  0.0%st

In the above line 0.7% is the CPU time in user space. CPU time is calculated based on ticks. For eg: 1 sec = 100 ticks then out of 100 ticks 0.7 is used for user programs. similarly 0.7 for sytem process and 98%7 for idle 

In case if a process is showing usage more than 100 then we need to check the number of cores and based on that we need to calculate it.

Since CPUs operate in GHz (billionths of cycles a second). The operating system slices that time in smaller units called ticks. They are not really 1/10 of a second. The tick rate in windows is 10 million ticks in a second and in Linux it is sysconf(_SC_CLK_TCK) (usually 100 ticks per second).

In something like top, the busy cpu cycles are then further broken down into percentages of things like user time and system time. In top on Linux and perfmon in Windows, you will often get a display that goes over 100%, that is because the total is 100% * the_number_of_cpu_cores.

In an operating system, it is the scheduler's job to allocate these precious slices to processes, so the scheduler is what reports this.

3) States of CPU

CPU time is occupied  by one of the below stated of CPU, Below are the states of CPU with some explanation.

a) id - Idle, which means it has nothing to do

b) us - Running a user space program, like a command shell, an email server, or a 

c) sy - Running the kernel, servicing interrupts or managing resources.

d) ni - shows the amount of CPU spent running user space processes that have been niced. When no processes have been niced then the number will be 0.

e) wa - Input and output operations, like reading or writing to a disk, are slow compared to the speed of a CPU. Although this operations happen very fast compared to everyday human activities, they are still slow when compared to the performance of a CPU. There are times when the processor has initiated a read or write operation and then it has to wait for the result, but has nothing else to do. In other words it is idle while waiting for an I/O operation to complete. The time the CPU spends in this state is shown by the wa statistic.

f) hi & si - These two statistics show how much time the processor has spent servicing interrupts. hi is for hardware interrupts, and si is for software interrupts. Hardware interrupts are physical interrupts sent to the CPU from various peripherals like disks and network interfaces. Software interrupts come from processes running on the system. A hardware interrupt will actually cause the CPU to stop what it is doing and go handle the interrupt. A software interrupt doesn't occur at the CPU level, but rather at the kernel level.

g) st - This last number only applies to virtual machines. When Linux is running as a virtual machine on a hypervisor, the st (short for stolen) statistic shows how long the virtual CPU has spent waiting for the hypervisor to service another virtual CPU running on a different virtual machine. Since in the real-world these virtual processors are sharing the same physical processor(s) then there will be times when the virtual machine wanted to run but the hypervisor scheduled another virtual machine instead.