-
CPU Scheduling
CPU Scheduling is the process in which one process is allowed to utilize the CPU while another process is put into a waiting stage due to the unavailability of a resource (such as I/O devices, etc.). Therefore, the working process is allowed full use of the CPU. CPU scheduling is an important process that allows the OS to be more efficient, fast, and fair. The CPU scheduler will select one process from the ready queue every time the CPU is in an idle state and the selected process is ready to be executed.
- Dispatchers
Dispatchers are components of the machine that are involved in CPU scheduling functions. They are modules that allocate CPU control to the selected process mentioned in the previous point. The dispatcher will allow the process to:
- Switch context,
- Switch user modes,
- Jump to the proper location in the user program to restart the program from where it last left off.
The dispatcher should be made to work as fast as possible, since they are involved in every process switching. Each time the process switches, the dispatcher will need to stop the first process and then start the second process. The time taken by the dispatcher to do so is referred to as the dispatch latency.
- Types of CPU Scheduling
CPU Scheduling will occur in four different occasions:
- Switching process state from a running state into a waiting state (non-preemptive scheduling scheme).
- Switching process state from a running state into the ready state (preemptive scheduling scheme).
- Switching process state from a waiting state into the ready state (preemptive scheduling scheme).
- Terminating a process (non-preemptive scheduling scheme).
-
Non-preemptive scheduling schemes
The non-preemptive scheduling will keep the CPU allocated to a process until the process is either terminated or switched into the waiting state. Being non-preemptive means that the scheduling will not need special hardwares (e.g. timers, etc.) to work. This method is mainly used by MacOS and Microsoft Windows 3.1 OS.
-
Preemptive scheduling schemes
This type of scheduling will assign priorities to processes. The process will higher priority will be executed prior to processes with lower priority. In cases where a process with low priority is being executed, and a process with high priority is suddenly switched to a running state, then the first process will be interrupted and control of the CPU will be handed to the second process. The first task will then continue its execution after the second is done being executed.
- Scheduling algorithms
There are preset algorithms to determine which process goes first in an attempt to optimise CPU utilization, such as:
- First Come First Serve (FCFS) scheduling. The simplest algorithm, in which the first process to be executed will be finished first before moving on to the next.
- Shortest-Job-First (SJF) scheduling. Provides the shortest average waiting time, is difficult to implement, however.
- Round-Robin (RR) scheduling. Allocates the CPU to a process for a certain time quantum before moving on to the next until every process is done.
- Priority scheduling. Each process is assigned a priority value, and the process with highest priority is given control of the CPU, before the process with the next highest priority, and so on.
- Multilevel queue scheduling. Processes are partitioned into several distinct queues arranged by priority. The processes in the highest priority queue will then be executed by the scheduler.
- Multilevel feedback queue scheduling. Similar to the above, except that each process can migrate between different queues.
- Scheduling criteria
To pick the most optimal criteria, we need to pay attention to several requirements, such as:
- CPU utilization. The CPU has to work as much as possible (ideally 100% of the time).
- Throughput. The total number of processes being completed in a certain unit of time.
- Turnaround time. The amount of time taken to execute a process.
- Waiting time. The total amount of time in which the processes spend waiting in the ready queue.
- Load average. The average number of processes in the ready queue waiting.
- Response time. The amount of time taken first from when the request is posted until the response is given.
For optimal execution, the CPU utilization and Throughput is maximized, while turnaround time, waiting time, load average, and response time is made as little as possible.
- Real-time CPU schedulings
- Soft real-time scheduling. Prioritizes real-time tasks over non-real-time tasks.
- Hard real-time scheduling. Real-time tasks are given timing guarantees.
- Rate-monotonic real-time scheduling. Periodic tasks are scheduled using a static priority policy with preemption.
- Earliest-Deadline-First (EDF) scheduling. Prioritizes processes with the earliest deadline.
- Proportional Share scheduling. Allocates T shares among all apps.
- etc.
-
CPU-I/O burst cycles
Each time a process is being executed, it will cycle between CPU execution and I/O wait states. The execution process will first start with a CPU burst that perform calculations, followed by an I/O burst to wait for data transfer in or out of the system, before cycling back to a CPU burst, so on and so forth. When selecting scheduling algorithms, we need to take into account these bursts, as the type of program being executed may result in different lengths of bursts.
- Multicore processors
Multicore processors are processors that contain either two or more distinct processing units, which are called cores. Each core is able to read and perform instructions on their own, independent of the other cores. Recent multicore processors put all of the cores into a single chip, which will then appear on the system as multiple processors.