j0444170See 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.
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 |