-
-
[分享]作业调度算法举例
-
发表于: 2小时前 48
-
AI模型:Deepseek
仅供参考
一、生活类:
作业调度是从后备队列中选作业装入内存。下面用常见生活场景类比四种算法:
1. 先来先服务(FCFS)
例子:食堂打饭、银行取号、打印店按提交顺序打印。
说明:谁先到谁先服务。简单公平,但短作业可能被长作业堵在后面,平均等待时间较长。
2. 短作业优先(SJF)
例子:超市“10件以下快速通道”、银行“简单业务快速窗口”、快递站先分拣小件。
说明:优先选估计运行时间短的作业。平均周转时间短,但长作业可能一直排不上,产生“饥饿”。
3. 响应比高者优先(HRRN)
例子:打印店老板既想先打小文件,又不想让等了很久的大文件一直排不上。于是算响应比:
响应比 = 1 + 等待时间 / 服务时间
等待越久、文件越小,响应比越高,越先被处理。
说明:兼顾等待时间和运行时间,避免长作业饥饿,但每次要计算响应比。
4. 优先级调度
例子:医院急诊危重病人优先、客服 VIP 优先、操作系统中系统进程优先于普通用户进程。
说明:按优先级高低调度。灵活,但低优先级作业可能饥饿,可用“老化”(等待越久优先级越高)缓解。
简单对比:
| 算法 | 常见例子 | 特点 |
|---|---|---|
| 先来先服务 | 食堂排队 | 公平简单,短作业吃亏 |
| 短作业优先 | 快速窗口 | 平均等待短,长作业可能饥饿 |
| 响应比高者优先 | 打印店兼顾小文件和久等任务 | 兼顾长短和等待,避免饥饿 |
| 优先级调度 | 急诊、VIP | 重要任务先做,低优先级可能饥饿 |
二、计算机类:
在计算机中,严格意义的“作业调度”多用于批处理系统,现代操作系统更多是进程/线程调度,但算法思想相同。常见例子如下:
1. 先来先服务(FCFS)
计算机例子:Windows 打印后台处理程序按提交顺序打印;消息队列 FIFO;批处理系统按作业到达先后装入内存。
表现:先到的先服务,简单公平,但前面一个长作业会堵住后面一堆短作业。
2. 短作业优先(SJF)
计算机例子:CPU 调度中优先运行预计执行时间短的进程;Web 服务器优先处理小文件请求;数据库优先执行小查询。
表现:平均等待时间短,但长作业可能一直排不上,产生“饥饿”。
3. 响应比高者优先(HRRN)
计算机例子:批处理作业调度中,系统计算每个作业的响应比:
响应比 = 1 + 等待时间 / 服务时间
一个长作业等得越久,响应比越高,最终会被调度;短作业服务时间短,响应比也高。
表现:兼顾短作业和久等长作业,避免饥饿,但每次要计算响应比。
4. 优先级调度
计算机例子:Windows 线程优先级(0~31),系统进程高于普通用户进程;Linux 的 nice 值;实时操作系统如 VxWorks 按任务优先级调度;中断处理优先于普通任务。
表现:重要任务先执行,灵活;但低优先级任务可能饥饿,常用“老化”缓解。
简单对比:
| 算法 | 计算机中常见例子 | 特点 |
|---|---|---|
| 先来先服务 | 打印队列、FIFO 消息队列 | 公平简单,短作业吃亏 |
| 短作业优先 | CPU 短进程优先、Web 小请求优先 | 平均等待短,长作业可能饥饿 |
| 响应比高者优先 | 批处理作业调度、老化机制 | 兼顾长短和等待,避免饥饿 |
| 优先级调度 | Windows 线程优先级、实时任务 | 重要任务先做,低优先级可能饥饿 |
冰与火的战歌:Windows内核攻防实战高级班!从零到实战,融合AI与Windows内核攻防全技术栈,打造具备自动化能力的内核开发高手。