进程调度与控制

# 1. 进程调度基础

## 1.1 进程调度的概念

进程调度是操作系统中的一个重要概念，指的是在多道程序环境下，根据一定的算法和策略，从就绪队列中选择一个进程并分配处理器给它，以使得各个进程能够有效地运行并完成各自的任务。

## 1.2 进程调度的作用

进程调度的主要作用包括提高CPU利用率、减少作业的周转时间、改善系统的响应时间、提高系统的吞吐量、提高系统的公平性等。

## 1.3 进程调度的分类

进程调度可分为如下几种类型：
- 批处理系统中的进程调度
- 交互式系统中的进程调度
- 实时系统中的进程调度

以上就是第一章的内容，接下来我们将深入探讨各种进程调度算法。

# 2. 进程调度算法

#### 2.1 先来先服务（FCFS）调度算法

先来先服务（First-Come, First-Served，FCFS）调度算法是最简单的调度算法之一，按照进程到达的先后顺序进行调度。当一个进程到达系统后，就被插入到就绪队列的末尾，一旦CPU空闲，就将队列头的进程分配给CPU执行。FCFS调度算法的优点是简单易实现，但会导致平均等待时间较长，无法适应时间片短的场景。

以下是使用Python实现的FCFS调度算法示例代码：

class Process:
    def __init__(self, name, burst_time):
        self.name = name
        self.burst_time = burst_time
    def __str__(self):
        return self.name


def fcfs_schedule(processes):
    n = len(processes)
    wait_time = [0] * n
    turn_around_time = [0] * n

    # 计算每个进程的等待时间和周转时间
    for i in range(1, n):
        wait_time[i] = processes[i-1].burst_time + wait_time[i-1]
        turn_around_time[i] = processes[i].burst_time + wait_time[i]

    # 计算平均等待时间和平均周转时间
    avg_wait_time = sum(wait_time) / n
    avg_turn_around_time = sum(turn_around_time) / n

    # 输出结果
    print("进程\t  执行时间\t等待时间\t周转时间")
    for i in range(n):
        print(f"{processes[i]}\t\t{processes[i].burst_time}\t\t{wait_time[i]}\t\t{turn_around_time[i]}")
    print(f"\n平均等待时间：{avg_wait_time:.2f}")
    print(f"平均周转时间：{avg_turn_around_time:.2f}")


# 测试样例
if __name__ == '__main__':
    processes = [Process("P1", 10), Process("P2", 5), Process("P3", 8)]
    fcfs_schedule(processes)

上述代码定义了一个`Process`类来表示进程对象，其中包括进程名称和执行时间属性。`fcfs_schedule`函数实现了FCFS调度算法，接受一个进程列表作为参数，计算每个进程的等待时间和周转时间，并输出结果。测试样例中创建了3个进程，并调用`fcfs_schedule`函数进行调度。

运行以上代码，输出结果如下：

进程	  执行时间	等待时间	周转时间
P1		10		0		10
P2		5		10		15
P3		8		15		23

平均等待时间：8.33
平均周转时间：16.00

从结果可以看出，进程P1首先执行，执行时间为10个时间单位，等待时间为0，周转时间为10。接着进程P2执行，执行时间为5个时间单位，等待时间为10，周转时间为15。最后进程P3执行，执行时间为8个时间单位，等待时间为15，周转时间为23。平均等待时间为8.33，平均周转时间为16.00。

#### 2.2 最短作业优先（SJF）调度算法

最短作业优先（Shortest Job First，SJF）调度算法是根据进程所需的执行时间进行调度，按照执行时间短的优先分配CPU。SJF调度算法可以最大限度地减少平均等待时间，但可能导致长时间的作业饥饿。

以下是使用Java实现的SJF调度算法示例代码：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Process implements Comparable<Process> {
    private String name;
    private int burstTime;

    public Process(String name, int burstTime) {
        this.name = name;
        this.burstTime = burstTime;
    }

    public String getName() {
        return name;
    }

    public int getBurstTime() {
        return burstTime;
    }

    @Override
    public int compareTo(Process other) {
        return this.burstTime - other.burstTime;
    }

    @Override
    public String toString() {
        return name;
    }
}

public class SJFScheduling {

    public static void sjfSchedule(List<Process> processes) {
        int n = processes.size();
        List<Integer> waitTime = new ArrayList<>(Collections.nCopies(n, 0));
        List<Integer> turnAroundTime = new ArrayList<>(Collections.nCopies(n, 0));

        // 计算每个进程的等待时间和周转时间
        for (int i = 1; i < n; i++) {
            waitTime.set(i, processes.get(i - 1).getBurstTime() + waitTime.get(i - 1));
            turnAroundTime.set(i, processes.get(i).getBurstTime() + waitTime.get(i));
        }

        // 计算平均等待时间和平均周转时间
        double avgWaitTime = waitTime.str