操作系统最短进程优先算法和抢占式最高优先级算法

### 最短进程优先 (SJF) 调度算法

最短进程优先调度算法分为两种形式：非抢占式和抢占式。对于非抢占式的 SJF，一旦某个进程开始执行，则不允许其他更短的进程打断当前正在运行的进程直到其完成。而抢占式的版本则允许新到达且预计运行时间较短的任务中断已经在 CPU 上运行的时间较长的任务。

#### 实现方式
为了实现这种策略，操作系统维护一个就绪队列，并记录每个进程中估计的服务时间。当有新的进程进入系统时，会将其加入到适当的位置以保持按预期执行时间升序排列的状态。每当处理器变得可用时，就会选择具有最小预测服务时间的那个进程来执行[^1]。

def sjf_scheduling(processes, burst_times):
    n = len(processes)
    
    # 将进程按照预估的CPU爆发时间排序
    process_data = sorted(zip(burst_times, processes))
    
    current_time = 0
    result = []
    
    while process_data:
        next_process_burst, next_process_id = process_data.pop(0)
        
        # 更新当前时间为上一进程结束加上本进程所需时间
        start_time = current_time
        end_time = start_time + next_process_burst
        
        # 添加至结果列表中
        result.append((next_process_id, start_time, end_time))
        
        # 设置下一个起始时间为本次结束时刻
        current_time = end_time
    
    return result

### 抢占式最高优先级 (RR) 调度算法

相比之下，抢占式最高优先级（通常指Round Robin轮转法而非严格意义上的最高优先级）是一种基于固定长度时间段或称为“时间片”的机制来进行任务切换的方法。在这种模式下，所有准备好的程序都被放置在一个循环队列里；每当分配给某项工作的预定周期到期后，即使它还没有完成也会被暂停并放回队尾等待下次机会继续处理未尽部分。如果在此期间出现了更高优先进入系统的请求，则可以立即获得资源使用权而不必遵循原有的排队次序[^2]。

#### 实现方式
在 Round Robin 中，除了要管理好各个线程之间的转换外还需要特别注意上下文切换开销以及合理设定时间片段大小以免造成过多不必要的状态保存恢复操作影响效率。具体来说就是通过设置定时器触发事件通知内核何时应该停止当前活动并将控制权交给下一个候选者：

#include <queue>
using namespace std;

class Process {
public:
    int id;
    int remainingTime; // 剩余需要执行的时间量
};

void round_robin_scheduler(queue<Process>& readyQueue, int timeQuantum){
    queue<Process> tempQueue = readyQueue;
    while (!tempQueue.empty()){
        Process p = tempQueue.front();
        tempQueue.pop();

        if(p.remainingTime > timeQuantum){
            cout << "Running P" << p.id << " for " << timeQuantum << endl;
            p.remainingTime -= timeQuantum;
            tempQueue.push(p); // 放回到队列末端
        }else{
            cout << "P" << p.id << " completes its execution." << endl;
        }
    }
}

### 差异分析

- **决策依据不同**：SJF 主要考虑的是即将被执行的工作负载本身所消耗的实际或估算 CPU 时间长短作为安排先后的标准之一；而 RR 则依赖于预先定义好的时间间隔——即所谓的时间片——去轮流给予各待命单元有限时段内的独享权限。

- **公平性考量**：由于采用了固定的轮询制度使得每一个参与者都能得到均等的机会接触核心设施从而体现出更强的公正性和及时响应特性，这正是实时应用场合所需要的品质所在。反之，尽管 SJF 可能带来更高的吞吐率因为它倾向于让轻量化的小型事务尽快完结释放宝贵计算力供给后续到来的大规模项目使用，但在某些极端情况下可能会导致饥饿现象的发生，特别是那些较大尺寸却始终得不到足够关注进而长期处于挂起状态下的实例身上[^3].