【操作系统】进程调度算法（FCFS/SJF/优先级/时间片轮转）

考点频率★★★★★必考常结合计算题考查难度⭐⭐建议掌握各算法的核心思想、特点、优缺点能计算平均周转时间1️⃣ 为什么需要进程调度算法当多个进程同时处于就绪状态时操作系统需要决定让哪个进程先占用CPU。这个决策规则就是进程调度算法。简单说就是CPU就一个进程一大堆先让谁上软考中常考查四种经典调度算法FCFS、SJF、优先级调度、时间片轮转。要求能计算平均周转时间理解各自的适用场景。2️⃣ 先来先服务FCFS2.1 核心思想按照进程进入就绪队列的先后顺序分配CPU先请求的先服务。与日常生活中的排队类似公平性极强。2.2 优点实现最简单公平2.3 缺点长作业会阻塞后面的短作业“ convoy effect”护航效应导致平均等待时间较长对短作业不友好用户体验差2.4 示例进程到达时间均为0服务时间如下P1: 10ms, P2: 2ms, P3: 3ms执行顺序P1 → P2 → P3完成时间P110, P212, P315平均周转时间 (101215)/3 ≈ 12.33ms2.5 软考提示FCFS属于非抢占式算法只要进程获得CPU就会一直运行到结束或主动阻塞。3️⃣ 短作业优先SJF3.1 核心思想选择预计运行时间最短的进程先执行。3.2 优点平均等待时间最小理论最优对短作业友好3.3 缺点需要预知进程的运行时间实际很难准确预估可能导致长作业饥饿长作业永远排不上3.4 两种变体非抢占式 SJF进程一旦获得CPU运行完才能让出。对应示例顺序P2(2ms)→P3(3ms)→P1(10ms)。抢占式 SJF又称 SRTN最短剩余时间优先若新到达的进程剩余时间比当前进程的剩余时间更短则立即抢占CPU。实际系统中更常用。3.5 示例非抢占式进程到达时间均为0服务时间同上P1:10, P2:2, P3:3执行顺序P2 → P3 → P1平均周转时间 (2515)/3 ≈ 7.33ms 12.33ms性能优于FCFS。4️⃣ 优先级调度4.1 核心思想为每个进程分配一个优先级CPU总是选择优先级最高的进程运行。4.2 优先级的确定静态优先级创建时固定如系统进程 用户进程动态优先级运行过程中动态调整如等待时间越长优先级越高防止饥饿4.3 两种变体非抢占式高优先级进程来了也要等当前进程运行完抢占式高优先级进程一来立即抢占CPU4.4 缺点低优先级进程可能饥饿特别是静态优先级低优先级可能永远等不到4.5 实际系统现代操作系统通常采用动态优先级兼顾I/O型和CPU型进程防止低优先级任务饿死。5️⃣ 时间片轮转RRRound Robin5.1 核心思想将CPU时间划分为固定大小的时间片如10ms按顺序分配给就绪队列中的每个进程。进程用完时间片后无论是否执行完都必须让出CPU回到就绪队列末尾重新排队。5.2 优点响应时间短所有用户都能在较短时间内得到响应公平适合分时操作系统5.3 缺点时间片太小上下文切换频繁系统开销大时间片太大退化为FCFS响应变慢5.4 时间片大小的权衡通常设为10ms ~ 100ms一般为数毫秒到数十毫秒大于上下文切换时间保证切换开销占比可控6️⃣ 四种算法对比表算法调度方式优点缺点适用场景FCFS非抢占简单公平长作业阻塞短作业批处理系统SJF非抢占/抢占平均等待时间最短难以预估时间可能饥饿批处理系统需预估时间优先级非抢占/抢占可区分重要性低优先级可能饥饿实时/分时系统时间片轮转抢占响应快公平切换开销分时系统SJF的平均等待时间最短是理论结论但实际中无法准确预知运行时间因此常用近似方案如基于历史统计。7️⃣ 经典例题例题1某单CPU系统三个进程P1、P2、P3同时到达运行时间分别为 24ms、3ms、4ms。若采用非抢占式短作业优先调度则平均周转时间为 。解析执行顺序P2(3ms) → P3(4ms) → P1(24ms)完成时间P23P37P131平均周转时间 (3731)/3 41/3 ≈ 13.67ms答案13.67ms例题2以下关于时间片轮转调度的叙述中正确的是 。A. 时间片越大响应时间越短B. 时间片越小上下文切换越少C. 时间片大小不会影响系统性能D. 时间片过大时时间片轮转会退化为FCFS解析时间片越大响应变慢切换减少时间片越小响应变快切换增多。时间片过大每个进程都能在一个时间片内执行完变成FCFS。选D。例题3某系统采用动态优先级调度下列措施中能有效防止低优先级进程饥饿的是 。A. 采用静态优先级B. 允许进程抢占CPUC. 随着进程等待时间增长而提高其优先级D. 每次总是选择优先级最高的进程运行解析动态提高等待时间长的进程优先级等待时间越长优先级越高可以避免饥饿。选C。8️⃣ 记忆口诀FCFS先来先服务长作业堵短进度。SJF最短先执行平均等待时间最优。优先级高先上CPU低优先级可能饿肚。时间片轮转最公平响应快但切换多。9️⃣ 小测验评论区对答案某系统采用先来先服务FCFS调度算法有4个进程同时到达所需CPU时间分别为 8ms、4ms、10ms、6ms则这些进程的平均周转时间为 。A. 7msB. 14msC. 17msD. 28ms本专栏日更2篇点击头像 → 专栏《软考中级高频考点》订阅第一时间接收新内容#软考中级 #软件设计师 #进程调度 #FCFS #SJF #优先级调度 #时间片轮转 #操作系统