计算n个进程下载到可用存储的磁盘已满的时间

Question

我正在解决办公室主任给出的难题以找出解决方案。

难题是：

n个进程正在计算机上运行。它们永远运行，永不消亡，并且不会产生新的进程。每个进程以恒定的，独立的速率占用内存-进程p_i（0 <= i

计算以秒为单位的可用存储空间用尽的时间。

我在下面编写的裸露逻辑似乎不是正确的解决方案；我对进程可以充满磁盘的不同速率感到困惑。

number_of_processes = 3
available_storage = 6 # in bytes
write_speed_x = 1 #(byte/ p_i second)
write_speed_y = 3
write_speed_z = 2
timeTaken = 0

pr_i = [write_speed_x, write_speed_y, write_speed_z]

for i in pr_i:
    timeTaken += available_storage/i


print timeTaken

Answer 1

似乎您错误地理解了内存消耗的定义。每个进程（索引为i）每d[i]秒就会多吃一个字节，因此它在k秒后消耗了k*d[i]个字节。可以说，在较长的时间间隔内，内存消耗的速度为1/d[i] bytes/second，但是内存消耗的增长是离散的。

time     0   di   2di   3di
mem      0    1    2     3 

例如，具有d = [1,3,2]秒/字节内存消耗的三个进程取决于时间，如下所示：

 process  p0   p1  p2  overall
 time
 0         0   0   0   0
 1         1   0   0   1 
 2         2   0   1   3 
 3         3   1   1   5
 4         4   1   2   7  
 5         5   1   2   8  
 6         6   2   3   11  

每个过程占用的内存会逐步增加，但是这些步骤会在不同的时间出现（想象一下台阶不均匀的楼梯）。

我们可以计算任意时刻t的内存消耗-只需对所有进程的内存求和

OverallMem(t) = t//d[0] + t//d[1] + t//[d[2]+...

其中//是整数除法（div，floor(t/d[i])）

[简单方法：使用上面的t=1, t=2, t=3...公式来计算内存消耗，依此类推，直到超过X。适用于小X，但适用于大X缓慢。Python3示例：

def timetodie(lst, x):
    mem = 0
    t = 0
    while (mem < x):
        t += 1
        mem = sum(t//v for v in lst)
              #mem = 0
              #for v in lst:
                   #mem += t // v
    return t

print(timetodie([1,3,2], 6))
print(timetodie([2,5,7], 11))
>>4
>>14

因为内存消耗没有减少，所以我们可以应用binary search方法来查找t大于OverallMem(t)时的时刻X。

开始条件：二进制搜索的左边界为0粗边框的右边界是X * Min(d[i])

@ AJNeufeld提出的更多最佳左边界：X//sum(1/v for v in lst)。可能采用以下形式：math.floor(x / sum(1/v for v in lst))

我希望这个线索足以阐明解决方案