This post introduces the core concepts and implementation methods of CPU scheduling in operating systems.

Basic Concepts

CPU-I/O Burst Cycle

• Preemptive scheduling: running->ready, waiting->ready
  • The CPU is allocated to a process for a limited time
  • The process is preempted once its time slice runs out
• Non-preemptive scheduling: running->waiting, terminate
  • A process voluntarily gives up the CPU when it does I/O or waits for an event
  • A process runs on the CPU until it finishes or blocks voluntarily

Dispatch

• Switching context
• Switching to user mode
• Jumping to the proper location in the user program to restart that program

Latency: the time it takes to stop one process and start another

Scheduling Criteria / Metrics

• CPU Utilization
• Throughput
• Turnaround Time
  • Formula: $T_{i}=W_{i}+t_{i}$
  • $T_{i}$ is the turnaround time of process i, $W_{i}$ is the waiting time of process i, and $t_{i}$ is the running time of process i
• Waiting Time
  • Formula: $W_{i}=\sum_{j=1}^{i-1} t_{j}$
  • $W_{i}$ is the waiting time of process i, and $t_{j}$ is the running time of process j
• Response Time
  • Formula: $R_{i}=W_{i}+t_{i}$
  • $R_{i}$ is the response time of process i, $W_{i}$ is the waiting time of process i, and $t_{i}$ is the running time of process i

Scheduling Algorithms

First-Come, First-Served Scheduling (FCFS)

• Non-preemptive scheduling
• Processes are scheduled in the order in which they arrive

Shortest-Job-First Scheduling (SJF)

• Pick the process with the shortest estimated running time to execute
• Minimizes the average waiting time
• Can be done by using the length of previous CPU bursts, using exponential moving average

• Shortest Remaining Time First Scheduling(SRT): Preemptive version of SJF

Priority Scheduling (PS)

• Processes are scheduled according to their priority
• May lead to starvation: Low priority processes may never be executed
• Solution: Aging – as time progresses increase the priority of the process

Round-Robin Scheduling (RR)

• Each process runs on the CPU for one time slice
• When the time slice runs out, the process is moved to the end of the queue
• Preemptive scheduling

Multilevel Queue Scheduling (MQS)

• Processes are divided into multiple queues
• Each queue has its own scheduling algorithm
• Queues are scheduled according to their priority

Multilevel Feedback Queue Scheduling (MFQS)

• Processes are divided into multiple queues
• Each queue has its own scheduling algorithm
• Queues are scheduled according to their priority
• If a process runs for too long in its current queue, it is moved to a higher-priority queue

Thread Scheduling

• User-Level Threads
  • Implemented by a user-level thread library, independent of the kernel
  • Scheduling takes place in user space
  • PCS: process-contention scope
• Kernel-Level Threads
  • Implemented by the kernel, dependent on the kernel
  • Scheduling takes place in kernel space
  • SCS: system-contention scope

Pthread Scheduling

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

#include <pthread.h> 
#include <stdio.h> 
#define NUM_THREADS 5 
int main(int argc, char *argv[]) 
{ 
int i, scope; pthread_t tid[NUM THREADS]; 
pthread_attr_t attr; 
/* get the default attributes */ 
pthread_attr_init(&attr); 
/* first inquire on the current scope */ 
if (pthread_attr_getscope(&attr, &scope) != 0) 
fprintf(stderr, "Unable to get scheduling scope\n"); 
else 
{ 
if (scope == PTHREAD_SCOPE_PROCESS) 
printf("PTHREAD_SCOPE_PROCESS"); 
else if (scope == PTHREAD_SCOPE_SYSTEM) 
printf("PTHREAD_SCOPE_SYSTEM"); 
else
fprintf(stderr, "Illegal scope value.\n");
}
/* set the scheduling algorithm to PCS */ 
pthread_attr_setscope(&attr, PTHREAD_SCOPE_PROCESS); 
/* create the threads */ 
for (i = 0; i < NUM_THREADS; i++) 
pthread_create(&tid[i], &attr, runner, NULL); 


/* set the scheduling algorithm to PCS or SCS */ 
pthread_attr_setscope(&attr, PTHREAD_SCOPE_SYSTEM); 
/* create the threads */
for (i = 0; i < NUM_THREADS; i++) 
pthread_create(&tid[i], &attr, runner, NULL); 
for (i = 0; i < NUM_THREADS; i++) /* now join on each thread */
pthread_join(tid[i], NULL); 
/* Each thread will begin control in this function */ 
void *runner(void *param)
{ 
/* do some work ... */ 
pthread_exit(0); 
}

Multi-Processor Scheduling

• Asymmetric multiprocessing
  • One master processor is dedicated to scheduling
  • The other processors are used to execute processes
• Symmetric multiprocessing(SMP)
  • Every processor can take part in scheduling
  • Requires more complex scheduling algorithms

Multiple-Processor Scheduling – Load Balancing

• Push migration: pushes a process from one processor to another
• Pull migration: pulls a process from one processor over to another

Processor Affinity

• A process tends to run on a particular processor
• Reduces cache invalidation
• Reduces context switches

Real-Time CPU Scheduling

For real-time scheduling, scheduler must support preemptive, priority-based scheduling

• Hard real-time systems
  • Deadlines must be met
• Soft real-time systems
  • Deadlines are met as far as possible

Rate Monotonic Scheduling (RMS)

• Priorities are assigned according to the inverse of each process’s period
• The shorter the period, the higher the priority
• If a process’s period is less than or equal to its time slice, it will not be preempted

Earliest Deadline First (EDF)

• Priorities are assigned according to each process’s deadline
• The earlier the deadline, the higher the priority
• If a process’s deadline is less than or equal to its time slice, it will not be preempted

Algorithm Evaluation: Deterministic Modeling

Scheduling algorithm criteria:
(1) CPU utilization, (2) throughput, (3) turnaround time, (4) waiting time, and (5) response time.

Translated from the Chinese original.