/ riteme.github.io Public

## History

170 lines (113 loc) · 12.4 KB

# srtf.md

170 lines (113 loc) · 12.4 KB
title description create modified tags location index template

2020.5.22
2020.5.22

.
true
template

[TOC]

# 两个简单调度算法的最优性

• 程序只会进行运算，不会有其它请求（例如读写文件）。因此每个程序在执行过程中除了退出程序外不会由其它的中断。
• 每个程序的提交时刻和所需的运行时间是已知的。

## SJF 算法

\begin{aligned} {x_i} &= 3, 1, 1, 1, 0, 0, ... \\ {y_i} &= 2, 2, 2, 0, 0, 0,... \end{aligned}

$$X_i \leqslant Y_i,\quad \forall i\in\mathbb{N}^+$$

(1) $i, j &lt; k$

$$X'k = X{k-1} \leqslant Y_{k-1} = Y'_k$$

(2) $i &lt; k \leqslant j$：此时 $t = x'_i \geqslant x'k = x{k - 1}$。

$$X'k = X{k-1} = x_{k-1} + X_k\leqslant t + X_k \leqslant t + Y_k = Y'_k$$

(3) $j &lt; k \leqslant i$：此时 $x_{k-1}=x'_{k-1}\geqslant x'_i = t$

$$X'k = t + X_k \leqslant x{k-1} + X_k = X_{k-1} \leqslant Y_{k-1} = Y'_k$$

(4) $k \leqslant i, j$

$$X'_k = t + X_k \leqslant t + Y_k = Y'_k$$

## Footnotes

1. "Shortest job next," Wikipedia, https://en.wikipedia.org/wiki/Shortest_job_next.

2. "Rearrangement inequality," Wikipedia, https://en.wikipedia.org/wiki/Rearrangement_inequality.

3. "Shortest remaining time," Wikipedia, https://en.wikipedia.org/wiki/Shortest_remaining_time.

4. L. Schrage, "A Proof of the Optimality of the Shortest Remaining Service Time Discipline," Opns. Res. 16, 687-690 (1968).

5. Donald R. Smith, "A New Proof of the Optimality of the Shortest Remaining Processing Time Discipline," Oper. Res, 197–199 (1978).

6. 主要是为了避免讨论序列长度。