进程调度算法对并发性能的影响
2022-10-021.6k 阅读
进程调度算法概述
在操作系统中，进程调度算法决定了哪个进程将获得 CPU 时间片来执行。由于 CPU 资源有限，而系统中可能同时存在多个可运行进程，进程调度算法就像是交通指挥员，合理安排各个进程对 CPU 的使用，以提高系统的并发性能。
常见的进程调度算法有先来先服务（FCFS）、最短作业优先（SJF）、最高响应比优先（HRRN）、时间片轮转（RR）、多级反馈队列（MLFQ）等。不同的调度算法基于不同的设计理念和目标，对系统并发性能有着迥异的影响。
先来先服务（FCFS）算法及其对并发性能的影响
FCFS 算法原理
先来先服务算法按照进程进入就绪队列的先后顺序来分配 CPU。即最先进入就绪队列的进程优先获得 CPU 资源进行执行，直到该进程完成或者因某种原因阻塞，才会将 CPU 分配给下一个进程。
代码示例（以简单模拟 FCFS 调度为例，使用 Python）
class Process:
def __init__(self, pid, arrival_time, burst_time):
self.pid = pid
self.arrival_time = arrival_time
self.burst_time = burst_time
def fcfs(processes):
processes.sort(key=lambda p: p.arrival_time)
current_time = 0
waiting_times = []
turn_around_times = []
for process in processes:
if current_time < process.arrival_time:
current_time = process.arrival_time
waiting_time = current_time - process.arrival_time
turn_around_time = waiting_time + process.burst_time
waiting_times.append(waiting_time)
turn_around_times.append(turn_around_time)
current_time += process.burst_time
avg_waiting_time = sum(waiting_times) / len(waiting_times)
avg_turn_around_time = sum(turn_around_times) / len(turn_around_times)
return avg_waiting_time, avg_turn_around_time
# 示例进程数据
processes = [Process(1, 0, 24), Process(2, 0, 3), Process(3, 0, 3)]
avg_waiting_time, avg_turn_around_time = fcfs(processes)
print(f"平均等待时间: {avg_waiting_time}")
print(f"平均周转时间: {avg_turn_around_time}")
对并发性能的影响
- 优点：算法简单，易于实现和理解。在单道批处理系统中，由于进程按顺序执行，系统资源管理相对简单。
- 缺点：对于长作业有利，而对短作业不利。如果长作业先进入就绪队列，短作业可能需要等待很长时间才能执行，导致系统整体的平均等待时间和平均周转时间较长，降低了系统的并发性能。例如，若有一个长作业运行时间为 100 个时间单位，后续有多个短作业，每个运行时间为 1 个时间单位，这些短作业需要等待长作业完成后才能执行，这会使得短作业的等待时间大幅增加。
最短作业优先（SJF）算法及其对并发性能的影响
SJF 算法原理
最短作业优先算法选择预计运行时间最短的进程优先执行。它可以是抢占式的（当有更短作业进入就绪队列时，可中断当前执行的作业），也可以是非抢占式的（当前作业执行完毕才调度下一个作业）。
代码示例（以非抢占式 SJF 调度为例，使用 Python）
class Process:
def __init__(self, pid, arrival_time, burst_time):
self.pid = pid
self.arrival_time = arrival_time
self.burst_time = burst_time
def sjf(processes):
processes.sort(key=lambda p: p.arrival_time)
current_time = 0
completed = []
waiting_times = []
turn_around_times = []
while processes or completed:
ready = [p for p in processes if p.arrival_time <= current_time]
if ready:
next_process = min(ready, key=lambda p: p.burst_time)
processes.remove(next_process)
waiting_time = current_time - next_process.arrival_time
turn_around_time = waiting_time + next_process.burst_time
waiting_times.append(waiting_time)
turn_around_times.append(turn_around_time)
current_time += next_process.burst_time
completed.append(next_process)
else:
current_time += 1
avg_waiting_time = sum(waiting_times) / len(waiting_times)
avg_turn_around_time = sum(turn_around_times) / len(turn_around_times)
return avg_waiting_time, avg_turn_around_time
# 示例进程数据
processes = [Process(1, 0, 6), Process(2, 0, 8), Process(3, 0, 7), Process(4, 0, 3)]
avg_waiting_time, avg_turn_around_time = sjf(processes)
print(f"平均等待时间: {avg_waiting_time}")
print(f"平均周转时间: {avg_turn_around_time}")
对并发性能的影响
- 优点：理论上可以获得最小的平均等待时间和平均周转时间，能有效提高系统的吞吐量。因为它优先执行短作业，使得短作业可以快速完成，减少了在系统中的停留时间。
- 缺点：需要预先知道每个进程的运行时间，这在实际系统中往往难以做到。而且，如果不断有短作业进入系统，长作业可能会被无限期推迟，出现“饥饿”现象，影响系统的公平性，从整体上也可能影响并发性能。例如，在一个服务器系统中，如果不断有短的网络请求任务进入，而一些长的后台处理任务可能长时间得不到执行，导致系统部分功能无法正常运转。
最高响应比优先（HRRN）算法及其对并发性能的影响
HRRN 算法原理
最高响应比优先算法综合考虑了进程的等待时间和预计运行时间。响应比 R 的计算公式为：R = (等待时间 + 预计运行时间) / 预计运行时间。每次调度时，选择响应比最高的进程执行。这样既照顾了等待时间长的进程，又兼顾了短作业优先的原则。
代码示例（以 HRRN 调度为例，使用 Python）
class Process:
def __init__(self, pid, arrival_time, burst_time):
self.pid = pid
self.arrival_time = arrival_time
self.burst_time = burst_time
def hrrn(processes):
processes.sort(key=lambda p: p.arrival_time)
current_time = 0
completed = []
waiting_times = []
turn_around_times = []
while processes or completed:
ready = [p for p in processes if p.arrival_time <= current_time]
if ready:
for p in ready:
p.response_ratio = (current_time - p.arrival_time + p.burst_time) / p.burst_time
next_process = max(ready, key=lambda p: p.response_ratio)
processes.remove(next_process)
waiting_time = current_time - next_process.arrival_time
turn_around_time = waiting_time + next_process.burst_time
waiting_times.append(waiting_time)
turn_around_times.append(turn_around_time)
current_time += next_process.burst_time
completed.append(next_process)
else:
current_time += 1
avg_waiting_time = sum(waiting_times) / len(waiting_times)
avg_turn_around_time = sum(turn_around_times) / len(turn_around_times)
return avg_waiting_time, avg_turn_around_time
# 示例进程数据
processes = [Process(1, 0, 6), Process(2, 0, 8), Process(3, 0, 7), Process(4, 0, 3)]
avg_waiting_time, avg_turn_around_time = hrrn(processes)
print(f"平均等待时间: {avg_waiting_time}")
print(f"平均周转时间: {avg_turn_around_time}")
对并发性能的影响
- 优点：既考虑了进程的等待时间，避免了长作业“饥饿”现象，又能优先处理短作业，在一定程度上平衡了系统的公平性和效率，有助于提高系统的并发性能。对于一些交互性较强的系统，能较好地满足用户需求，因为用户往往希望自己提交的任务能尽快得到响应。
- 缺点：每次调度都需要计算响应比，增加了系统开销。而且，由于需要预先知道进程的运行时间，实际应用中也存在一定局限性。如果对运行时间的预估不准确，可能会影响调度效果，进而影响并发性能。
时间片轮转（RR）算法及其对并发性能的影响
RR 算法原理
时间片轮转算法将 CPU 时间划分为固定大小的时间片。就绪队列中的进程轮流获得一个时间片的 CPU 使用权。如果在时间片结束时进程还未完成，它将被送回到就绪队列末尾，等待下一轮调度。
代码示例（以简单的 RR 调度为例，使用 Python）
class Process:
def __init__(self, pid, burst_time):
self.pid = pid
self.burst_time = burst_time
self.remaining_time = burst_time
def round_robin(processes, time_quantum):
current_time = 0
waiting_times = [0] * len(processes)
turn_around_times = [0] * len(processes)
completed = 0
while completed < len(processes):
for i in range(len(processes)):
if processes[i].remaining_time > 0:
if processes[i].remaining_time <= time_quantum:
current_time += processes[i].remaining_time
processes[i].remaining_time = 0
completed += 1
turn_around_times[i] = current_time
waiting_times[i] = turn_around_times[i] - processes[i].burst_time
else:
current_time += time_quantum
processes[i].remaining_time -= time_quantum
avg_waiting_time = sum(waiting_times) / len(waiting_times)
avg_turn_around_time = sum(turn_around_times) / len(turn_around_times)
return avg_waiting_time, avg_turn_around_time
# 示例进程数据
processes = [Process(1, 24), Process(2, 3), Process(3, 3)]
time_quantum = 4
avg_waiting_time, avg_turn_around_time = round_robin(processes, time_quantum)
print(f"平均等待时间: {avg_waiting_time}")
print(f"平均周转时间: {avg_turn_around_time}")
对并发性能的影响
- 优点：公平性好，每个进程都能在一定时间内获得 CPU 时间，适用于分时系统和交互式系统，能为用户提供较好的交互体验。因为它可以快速响应各个进程的请求，避免某个进程长时间占用 CPU 而导致其他进程得不到及时处理。
- 缺点：时间片大小的选择至关重要。如果时间片过大，RR 算法就退化为 FCFS 算法，失去了公平性和快速响应的优势；如果时间片过小，进程上下文切换过于频繁，会增加系统开销，降低 CPU 利用率，从而影响并发性能。例如，在一个多用户的操作系统中，如果时间片设置过小，频繁的上下文切换会使得系统忙于处理进程切换，而真正用于执行用户任务的时间减少。
多级反馈队列（MLFQ）算法及其对并发性能的影响
MLFQ 算法原理
多级反馈队列算法有多个就绪队列，每个队列有不同的优先级和时间片。新进程首先进入最高优先级队列，按照 FCFS 原则执行。如果在一个时间片内未完成，进程将被移到下一级队列。优先级越高的队列，时间片越小。较低优先级队列的进程只有在较高优先级队列为空时才会被调度。
代码示例（以简单模拟 MLFQ 调度为例，使用 Python）
class Process:
def __init__(self, pid, burst_time):
self.pid = pid
self.burst_time = burst_time
self.remaining_time = burst_time
def mlfq(processes, time_quantums):
queues = [[] for _ in range(len(time_quantums))]
current_time = 0
waiting_times = [0] * len(processes)
turn_around_times = [0] * len(processes)
completed = 0
for process in processes:
queues[0].append(process)
while completed < len(processes):
for i in range(len(queues)):
while queues[i]:
process = queues[i].pop(0)
if process.remaining_time <= time_quantums[i]:
current_time += process.remaining_time
process.remaining_time = 0
completed += 1
turn_around_times[process.pid - 1] = current_time
waiting_times[process.pid - 1] = turn_around_times[process.pid - 1] - process.burst_time
else:
current_time += time_quantums[i]
process.remaining_time -= time_quantums[i]
if i < len(queues) - 1:
queues[i + 1].append(process)
else:
queues[i].append(process)
avg_waiting_time = sum(waiting_times) / len(waiting_times)
avg_turn_around_time = sum(turn_around_times) / len(turn_around_times)
return avg_waiting_time, avg_turn_around_time
# 示例进程数据
processes = [Process(1, 24), Process(2, 3), Process(3, 3)]
time_quantums = [2, 4, 8]
avg_waiting_time, avg_turn_around_time = mlfq(processes, time_quantums)
print(f"平均等待时间: {avg_waiting_time}")
print(f"平均周转时间: {avg_turn_around_time}")
对并发性能的影响
- 优点：结合了多种调度算法的优点，能根据进程的行为动态调整其优先级。对于短作业，可能在高优先级队列中快速完成；对于长作业，也不会被无限期推迟，能在较低优先级队列中逐步执行。这种灵活性使得系统在处理不同类型进程时都能有较好的并发性能，既保证了交互性进程的快速响应，又能处理计算密集型的长作业。
- 缺点：算法相对复杂，实现难度较大。而且队列数量、时间片大小以及优先级调整策略等参数的设置需要根据系统负载和应用场景进行精心调优，否则可能无法达到最佳的并发性能。例如，如果队列划分不合理，可能导致某些进程长时间处于低优先级队列，影响系统整体效率。
不同调度算法在实际场景中的应用
- 批处理系统：在批处理系统中，由于对响应时间要求相对不高，更注重系统的吞吐量。FCFS 和 SJF 算法在这种场景下有一定应用。FCFS 简单易实现，而 SJF 能有效减少平均作业周转时间，提高系统吞吐量。但由于 SJF 需要预知作业运行时间，实际应用可能受限，可结合一些预估方法或对作业进行分类来近似实现 SJF 的效果。
- 分时系统：分时系统强调交互性，RR 算法是常用的调度算法。它能保证每个用户进程都能及时获得 CPU 时间，提供良好的交互体验。不过，为了进一步优化性能，也可以结合其他算法，如多级反馈队列算法，既能快速响应交互性进程，又能处理后台的长作业。
- 实时系统：实时系统对任务的响应时间和截止时间有严格要求。在实时系统中，需要采用能满足这些要求的调度算法，如最早截止时间优先（EDF）算法等。EDF 算法根据任务的截止时间来调度，确保任务在截止时间前完成，保证系统的实时性和并发性能。
调度算法与系统资源的关系
进程调度算法不仅影响 CPU 的使用效率，还与系统其他资源（如内存、I/O 设备等）的使用密切相关。
- 与内存资源的关系：不同调度算法下，进程的执行顺序和时间分配不同，这会影响内存中进程的驻留时间和内存的使用模式。例如，若采用 SJF 算法优先执行短作业，短作业快速完成后能及时释放内存，使得内存资源可以更快地被其他进程使用，提高内存的利用率。而如果采用 FCFS 算法，长作业长时间占用内存，可能导致内存紧张，影响其他进程的加载和执行，降低并发性能。
- 与 I/O 设备的关系：进程在执行过程中往往会有 I/O 操作。调度算法需要考虑进程的 I/O 特性，以避免 I/O 设备空闲等待。例如，若一个进程频繁进行 I/O 操作，采用时间片轮转算法时，在其进行 I/O 操作时可以将 CPU 调度给其他进程，提高 CPU 的利用率。同时，对于 I/O 密集型进程和 CPU 密集型进程，合理的调度算法可以平衡它们对系统资源的竞争，提高整体并发性能。
调度算法的发展趋势
随着计算机系统的发展，尤其是多核处理器、分布式系统等的广泛应用，进程调度算法也在不断演进。
- 多核调度：在多核处理器系统中，需要考虑如何将进程合理分配到不同核心上执行，以充分发挥多核的性能。一些调度算法会结合任务的亲和性（如数据局部性等）来进行核心分配，提高缓存命中率，进而提升并发性能。
- 分布式调度：在分布式系统中，进程调度需要考虑节点之间的资源差异、网络延迟等因素。分布式调度算法旨在实现跨节点的任务分配和协调，以提高整个分布式系统的并发处理能力。例如，通过动态感知节点的负载情况，将任务调度到负载较轻的节点上执行。
- 智能化调度：利用机器学习、人工智能等技术，让调度算法能够根据系统运行状态和历史数据进行自适应调整。例如，通过分析进程的行为模式，预测进程的运行时间和资源需求，从而更合理地进行调度，提高系统的并发性能。
不同的进程调度算法对系统的并发性能有着显著的影响。在实际应用中，需要根据系统的类型和需求，综合考虑各种因素，选择合适的调度算法，并不断优化调度策略，以提高系统的整体性能和并发处理能力。