UNISA Chatter – Operating System Concepts: Part 5 … Scheduling
See UNISA – Summary of 2010 Posts for a list of related UNISA posts. this post we briefly investigates scheduling, which is important when we want to operate in a multi-process and multi-thread backyard.
The Central Processing Unit (CPU) scheduling is concerned with selecting the right process from a ready queue of waiting processes and allocating CPU time to the processes. What is the right process? This is a complex topic and apart from saying that the ingredients to the decision includes CPU utilisation, throughput, latency, turn-around time, waiting tome and response time, we will probably be better off skimming the basics and leaving the decision to the experts. We could also run a number of simulations, but again these are extremely expensive and require immense hardware and processing time.
Process Scheduling Algorithms
The illustration below shows some of the typical scheduling algorithms, the execution of the following three processes and both wait and turnaround time. Wait time defines the sum of periods waiting on the ready queue and turnaround time is the sum of periods waiting and executing.
| Process | Arrival Time | Burst Time |
| P1 | 0.0 | 8 |
| P2 | 0.4 | 4 |
| P3 | 1.0 | 1 |
| Algorithm | Description | Pre-emptive | Challenges |
| First-Come, First-Served (FCFS) | The process that requests the CPU is serviced first. | No | Starvation Average waiting time can be long |
| Shortest-Job-First (SJF) | The process with the shortest “next CPU burst” time is scheduled first. In pre-emptive mode, this algorithm is also known as the shortest-remaining-time-first scheduling algorithm. | Yes|No | Starvation Difficult to determine next burst time |
| Round-Robin (RR) | Processing is split up into time quantum's or time slice, ranging from 10 to 100 milliseconds. | Yes | Difficult to determine correct quantum If quantum is large we get FCFS, If quantum too small, overhead is huge. |
| Priority | Each process has an associated priority and the highest priority processes are scheduled first. In pre-emotive mode, a lower priority process will be interrupted to make place for a higher priority process. | Yes|No | |
| Multilevel Queue | Allows use of different algorithms for different types of processes, such as interactive, system, batch and guest. | Yes|No | |
| Multilevel Feedback Queue | Unlike in Multilevel, this algorithm allows processes to move between queues, typically separating processes according to their CPU burst characteristics. | Yes|No | Complex algorithm |
Thread Scheduling
Two more acronyms we trip over are concerned with thread scheduling, namely PCS and SCS.
- Process-contention scheduling (PCS) … is done local to the process and determines how the thread library schedules threads onto available lightweight process (LWP), which appears as a virtual processor.
- System-contention scheduling (SCS) … is done at kernel level, when the operating system decides which kernel thread to schedule for CPU time.
Multi Processor Scheduling
Multiple processors typically each have their own scheduling queue . With the new trend of multi-core processors, where multiple processors cores are places on the same chip. Challenges such as memory stall, which can occur due to cache miss, can potentially cause a a significant wait time. One of the resolutions is to run two or more hardware threads per core, ensuring that is one thread stalls with a memory stall, the core can switch to one of the other threads as shown:
Well, after a quick, yet interesting peek at scheduling, we will prepare ourselves for synchronization, a crucial watchdog in a multi-processing environment. See you soon.
Acronyms Used
| CPU – Central Processing Unit | FCFS – First Come First Served | LPW – Lightweight Process | PCS – Process Contention Scheduling | RR – Round Robin | SJF – Shortest-Job First | SCS – System Contention Scheduling |