operating-system - 进程会出现饥饿吗？

Question

考虑使用非抢占式 SJF 调度的操作系统。如果给定一个假设有 10 个进程的工作负载，并且每个进程执行一个范围从 10 毫秒到 20 毫秒的 CPU 突发，然后是 500 毫秒的 I/O 突发，那么任何进程都会经历饥饿吗？

通过这个工作，我知道最短的进程首先被安排，并且无论哪个进程正在运行都会运行到完成，但我不明白如何确定是否有任何进程会因为资源从未被分配而被推迟，我想在继续之前知道，我想知道如何知道调度程序的工作量和类型？

标签： operating-systemschedulerstarvation

Answer 1

考虑使用非抢占式 SJF 调度的操作系统。如果给定一个假设有 10 个进程的工作负载，并且每个进程执行一个范围从 10 毫秒到 20 毫秒的 CPU 突发，然后是 500 毫秒的 I/O 突发，那么任何进程都会经历饥饿吗？

如果您将“饥饿”定义为“永远得不到任何 CPU 时间”；然后，使用“最短作业优先”算法：

a) 当较短的作业创建速度快于完成的速度时，较长的作业将变得饥饿（无论有多少 CPU，它们实际上都无法跟上，因为新的较短作业创建得太频繁了）。

b1）如果花费无限时间的任务数量超过了 CPU 的数量并且没有任务阻塞（例如等待 IO），或者更多的进程将缺乏 CPU 时间（除非您以某种形式增加 SJF时间共享以避免“总是相等长度”的工作之间的饥饿）。

b2）如果花费无限时间的任务数量超过了 CPU 的数量并且某些任务确实阻塞（例如等待 IO），那么是否发生饥饿取决于“每个进程未被阻塞的时间总和” ”。

如果一个 SJF 调度器被赋予 10 个进程的工作负载并且它们都不是“无限长”的，并且没有额外的新进程被创建；那么所有 10 个任务迟早必须完成，并且没有一个任务将永远等待 CPU。

当然，这并不意味着某些任务不必（暂时、短暂地）等待 CPU。

注意：对于实际系统，通常有很多无限长的任务会阻塞（例如，对于 Windows 和 Linux，通常有超过 100 个进程作为服务/守护进程和 GUI 运行）；没有人知道任何任务需要多长时间（不仅仅是因为每个 CPU 的速度由于电源管理而不断变化 - 例如，您使用的网络浏览器将运行多长时间？）；通常没有人知道一个过程是否会花费无限的时间（停止问题）；有时，由于错误，进程会意外地永远循环。换句话说; “最短的工作优先”几乎总是无法实施。