本文介绍了操作系统中CPU调度的核心概念和实现方法。

Basic Concepts

CPU-I/O Burst Cycle

• 抢占式调度：running->ready, waiting->ready
  • CPU分配给进程有限时间
  • 进程在时间片用完后被抢占
• 非抢占式调度：running->waiting, terminate
  • 进程在 I/O 或等待事件时自愿放弃 CPU
  • 进程在 CPU 上运行直到完成或自愿阻塞

Dispatch

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

Latency: 停止一个进程到启动另一个进程花费时间

Scheduling Criteria / Metrics

• CPU Utilization
• Throughput
• Turnaround Time
  • 计算：$T{i}=W{i}+t_{i}$
  • $T{i}W{i}t_{i}$ 是进程i的运行时间
• Waiting Time
  • 计算：$W{i}=\sum{j=1}^{i-1} t_{j}$
  • $W{i}t{j}$ 是进程j的运行时间
• Response Time
  • 计算：$R{i}=W{i}+t_{i}$
  • $R{i}W{i}t_{i}$ 是进程i的运行时间

Scheduling Algorithms

First-Come, First-Served Scheduling (FCFS)

• 非抢占式调度
• 按照进程到达的顺序来调度

Shortest-Job-First Scheduling (SJF)

• 选择估计运行时间最短的进程来执行
• 最小化平均等待时间
• 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)

• 根据进程的优先级来调度
• 可能导致饥饿: Low priority processes may never be executed
• Solution: Aging – as time progresses increase the priority of the process

Round-Robin Scheduling (RR)

• 每个进程在CPU上运行一个时间片
• 如果时间片用完，则将进程放到队列末尾
• 抢占式调度

Multilevel Queue Scheduling (MQS)

• 将进程划分为多个队列
• 每个队列有不同的调度算法
• 按照队列的优先级来调度

Multilevel Feedback Queue Scheduling (MFQS)

• 将进程划分为多个队列
• 每个队列有不同的调度算法
• 按照队列的优先级来调度
• 如果进程在当前队列中运行时间过长，则将其转移到更高优先级的队列中

Thread Scheduling

• User-Level Threads
  • 由用户级线程库实现，不依赖于内核
  • 调度在用户空间进行
  • PCS 进程竞争范围
• Kernel-Level Threads
  • 由内核实现，依赖于内核
  • 调度在内核空间进行
  • SCS 系统竞争范围

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
  • 一个主处理器专门用于调度
  • 其他处理器用于执行进程
• Symmetric multiprocessing(SMP)
  • 所有处理器都可以用于调度
  • 需要复杂的调度算法

Multiple-Processor Scheduling – Load Balancing

• Push migration: 将进程从一个处理器推送到另一个处理器
• Pull migration: 将进程从一个处理器拉到另一个处理器

Processor Affinity

• 进程倾向于在特定的处理器上运行
• 减少缓存失效
• 减少上下文切换

Real-Time CPU Scheduling

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

• Hard real-time systems
  • 必须满足截止时间
• Soft real-time systems
  • 尽可能满足截止时间

Rate Monotonic Scheduling (RMS)

• 根据进程的周期倒数分配优先级
• 周期越短，优先级越高
• 如果进程的周期小于等于其时间片，则不会被抢占

Earliest Deadline First (EDF)

• 根据进程的截止时间分配优先级
• 截止时间越早，优先级越高
• 如果进程的截止时间小于等于其时间片，则不会被抢占

Algorithm Evaluation: Deterministic Modeling

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