Process Scheduling
Last updated
Was this helpful?
Low Level Computing
Last updated
Was this helpful?
the objective of multiprogramming is to have some process running at all times to maximize CPU utilization. Time-sharing operating systems switch between processes at very short intervals (microseconds), creating the illusion of concurrency.
The scheduler selects an available process from a pool of processes in a the READY state. Each core can run a single process (or process thread). Schedulers must consider the behavior of a process as well; I/O-bound processes are those that spend a majority of its time doing I/O, while CPU-bound spend the majority of time doing computations.
Processes that are ready to be scheduled are placed in a ready queue--typically a linked list. The queue header contains a pointer to the first PCB in the list; each PCB in the list contains a pointer to the next PCB.
Additional queues such as a wait queue are used by the system to keep track of processes waiting for I/O interrupt, termination, or resumed execution after preemption.
I/O devices run much slower than the processor, making wait queues essential for optimal performance.
The following Queueing diagram shows the typical flow of a process. Processes in the ready queue are eventually scheduled to use a CPU core; afterwards, they are either complete or placed into one of the wait queues to continue operation.
The first wait queue is an I/O queue, which contains processes that issued an I/O request. Once the I/O device is ready, the process is removed from the queue and placed back into the ready queue.
Another possibility is that the process forks (or, creates) another, child, process. In such cases, the process is stored in a wait queue to wait for the child process to terminate.
Other possibilities include time slice expiration or waiting for an interrupt.
It may be helpful to view this information in the context of the Linux operating system. The PCB structure in Linux is call task_struct. Unfortunately, it's too large to copy to this page; however, you can easily view the structure online--the struct is defined in <include/linux/sched.h> (see lines 748 - 1568).
The following diagrams provide a nice visual for files_struct and mm_struct, respectively.
The CPU scheduler is responsible for scheduling processes in the ready queue to a CPU core. On Time-sharing OS's, the CPU scheduler will limit the amount of time any process has ownership of the core; this is known as time slicing. The CPU scheduler frequently switches between processes on a system (millisecond intervals). CPU-bound processes typically need more CPU time; nevertheless, slicing ensures other processes are able to access CPU and move through their life-cycle.
Swapping, whereby inactive processes (or those selected algorithmically) are removed from memory and thus do not compete for cpu, reduces the number of processes available for cpu scheduling and those in memory.
