这是在工作中遇到的实际问题和解决过程。问题已经被抽象成并发任务的分配问题。
问题
如果有 n 组数据均分给 m 个处理器处理，那么每个处理器分到的数据是 \(\lceil \frac{n}{m} \rceil\) 。如果n组数据的类型有差异，其中有a组是一类数据，剩余 n-a 组是另一类数据。只有同类数据才能被一次性处理，那么该如何分配？
这个问题在现实中是存在的。比如HTTP并发请求处理一些数据。数据被批量送来，但类型不一样。为了节省耗时，我们希望并发处理这些不同的数据。并发数是确定好的。现在需要计算每个请求处理的数量，以便我们能给每一个请求打包数据。
求解
n 组数据交给 m 个处理器处理，每个处理器最多分到 \(\lceil \frac{n}{m} \rceil\) 组数据，这是毫无疑问的。如果 n 组数据中有a组是一类数据，n-a组是另一类数据。同类数据必须分配到同一个处理器。那么a类数据得到的处理器的数量是 \(\lceil \frac {a} {\lceil \frac{n}{m} \rceil} \rceil \)，b类得到的处理器的数量是 \(\lceil \frac {n-a} {\lceil \frac{n}{m} \rceil} \rceil \)。我们现在其实需要考虑它们总共需要的处理器数量和m的关系。原有的m个处理器是否满足这种需求？如果不满足，需要多少个处理器才能满足？
即，求 \(( \lceil \frac {a}{\lceil \frac{n}{m} \rceil} \rceil +\lceil \frac {n-a} {\lceil \frac{n}{m} \rceil} \rceil ) \) 和 m的关系。
对于上面的问题，我们的存在一些已知的前提条件：
- m, m 为正整数
- \(n \leq m\)
根据上面已知的条件，我们可以得出一些引理：
- \(\lceil \frac {n}{m} \rceil \geq \frac {n}{m} \)
- \( \lceil \frac {n}{m} \rceil \leq \frac {n}{m} + \frac {m-1}{m} \)
因此，容易得出\(( \lceil \frac {a}{\lceil \frac{n}{m} \rceil} \rceil +\lceil \frac {n-a} {\lceil \frac{n}{m} \rceil} \rceil ) \geq \lceil \frac {n}{\lceil \frac {n}{m} \rceil} \rceil \geq m \)
即数据类型分成两种的时候所需要的处理器数量是大于等于m的，原先的处理器个数可能不够用了。那么多少才够用？这是现在需要考虑的问题。
容易得出，\( ( \lceil \frac {a}{\lceil \frac{n}{m} \rceil} \rceil +\lceil \frac {n-a} {\lceil \frac{n}{m} \rceil} \rceil ) \leq \lceil \frac {am}{n}\rceil + \lceil \frac {(n-a)m} {n} \rceil \)
根据上面的引理可以得出 \( \lceil \frac {am}{n}\rceil + \lceil \frac {(n-a)m} {n} \rceil \leq \frac {am}{n} + \frac {n-1}{n} + \frac {(n-a)m} {n} + \frac {n-1}{n} = n+2-\frac{2}{n} \)
由已知条件可以知道，\( ( \lceil \frac {a}{\lceil \frac{n}{m} \rceil} \rceil +\lceil \frac {n-a} {\lceil \frac{n}{m} \rceil} \rceil )\) 是正整数，因此可以将 \( n+2-\frac{2}{n} \)向下取整为\(n+1\)。
即需要n+1个处理器才能满足要求。
因此遇到这种问题的时候，要么增加一个处理器，要么计算每个处理器能处理的数量的时候在原先处理器数量减一的基础上计算。
赞赏
微信赞赏
支付宝赞赏
