[OS] Operation System Process Scheduling

General

CPU and I/O Bursts

CPU Burst

the amount of time the process uses the processor before it is no longer ready (for example I/O request)

I/O Burst

CPU-I/O Burst Cycle

process execution consists of a cycle of CPU execution and I/0 wait. Processes alternate between these two states. Process execution begins with a CPU burst. That is followed by an I/O burst, which is followed by another CPU burst, then another I/0 burst, and so on. Eventually, the final CPU burst ends with a system request to terminate execution. ([Operation System Concept])

I/O-bound program

has many short CPU bursts.

CPU-bound program

has a few long CPU bursts.

Scheduler

Long-term Scheduler

or job scheduler, selects processes from the pool and loads them into memory for execution. The long-term scheduler controls the degree of multiprogramming (the number of processes in memory) and is performed when new process is created

Medium-term Scheduler

controls processes to be swapped out of memory and be swapped in later, namely swapping. The decision to add to the number of processes that are partially or fully in main memory.

Short-term Scheduler

or CPU scheduler, selects from among the processes that are ready to execute and allocates the CPU to one of them. It controls which ready process to be executed in CPU next.

Dispatcher

The dispatcher is the module that gives control of the CPU to the process selected by the short-term scheduler. It involves

• switching context
  
  • context switching is expensive
  • context is a snapshot of the values of the general-purpose, memory management, and other special registers.
• switching to user mode
• jumping to the proper location in the user program to restart that program

Dispatch Latency

- time it takes for the dispatcher to stop one process and start another running.

Scheduling Diagram

Linux Kernel

General States

 

Ready

the process is competing for the processor or could be executed, but another process is currently being executed.

Running

the process is active and running

Suspend

the process is blocked and sleeping

Stopped

the process is suspended by a signal or a debugger

Zombie

the process has finished executed, but it is still references in the system. The process is exiting but has not yet been waited for by its parent

Process States defined in sched.h of Linux 2.6.31

Process states:

TASK_RUNNING

the process is either executing on a CPU or waiting to be executed.

TASK_INTERRUPTIBLE

the process is suspended (sleeping) or blocked, and waiting for a signal or explicit wakeup (such as wakeup_process()). Raising a hardware interrupt, releasing a system resource the process is waiting for, or delivering a signal are examples of conditions that might wake up the process (put its state back to TASK_RUNNING).

TASK_UNINTERRUPTIBLE

like TASK_INTERRUPTIBLE, but a signal won’t wake it up. It is valuable, however, under certain specific conditions in which a process must wait until a given event occurs without being interrupted. For instance, this state may be used when a process opens a device file and the corresponding device driver starts probing for a corresponding hardware device. The device driver must not be interrupted until the probing is complete, or the hardware device could be left in an unpredictable state.

TASK_STOPPED

process execution has been stopped; the process enters this state after receiving a SIGSTOP, SIGTSTP, SIGTTIN, or SIGTTOU signal.

TASK_TRACED

process execution has been stopped by a debugger. For example, each signal during ptrace system call with PTRACE_ request may put process in this state, and it will be put back to TASK_RUNNING state only after debug process executes ptrace system call with PTRACE_CONT or PTRACE_DETACH request.

TASK_DEAD

the process is being cleaned up and the task is being deleted. It’s the state of process in exiting. Finally the exit state will be one of EXIT_ZOMBIE or EXIT_DEAD.

Process exit states:

EXIT_ZOMBIE

process execution is terminated, but the parent process has not yet issued a wait4() or waitpid() system call to return information about the dead process. Before the wait()-like call is issued, the kernel cannot discard the data contained in the dead process descriptor because the parent might need it.

EXIT_DEAD

the final state: the process is being removed by the system because the parent process has just issued a wait4() or waitpid() system call for it.

References

Operation System Concept, 8th Edition
Understanding Linux Kernel, 3rd Edition
Linux 2.6.31 Kernel Source Code