多线程的内存调度

多线程的内存调度本文主要考虑以下这个问题：给定一台服务器,如何调度同时递交到该服务器的多个请求。具体地,每个用户递交的请求包含一系列的任务。在同一个请求序列中的不同任务需要根据到达的先后顺序来处理。每一个任务既有可能在同一个用户的请求序列中反复出现,也有可能在其他用户的请求序列中反复出现。此外,该服务器带有一个容量有限的内存,它可以用来存储任务。不同的任务需要的处理时间可能不同,其占用的空间也可能不同。当服务某个任务时,假如该任务已经在内存中,则不产生任何费用；否则,产生相应的处理时间,并且这个处理过的任务可以存放到内存中(存放任务不需要时间)。因为这个内存空间有限,这个存放过程可能导致内存中其它的任务被删除(删除任务也不需要时间)。本文的目的是设计一个调度方案,来优化某个目标函数。首先,我们考虑微小化全部的请求的完工时间,这个问题是经典的只有一个用户的内存调度问题的一个推广。此外,我们还考虑了微小化全部请求链的平均完工时间。对于这两个问题,我们兼顾了两个模型：强制模型,选择模型。对于前者,当完成一个任务后,假如它不在内存中,必须把它放进内存中；对于后者,则没有这个要求。我们证明了所有的问题事实上都是 NP 难。对于这些模型,我们设计了动态规划。此外,我们提出几个近似算法,并分析它们的近似比。最后,我们设计了一些启发式算法,并模拟运行。事实上,从资源利用的角度上看,内存也是一种资源。这样,除了讨论内存的使用,我们也讨论带有一个加速资源的两台平行机调度问题。具体地,每个工件都有一个处理时间。假如分配了这个加速资源的话,那么其所需的处理时间就会变小。然而,在任何时刻,最多只有一个工件可以使用这个资源。我们的目标函数是微小化全部工件的完工时间。对于离线模型(NP 难),我们设计了一个 FPTAS。对于在线模型,我们设计一个竞争比是 1.781 的在线算法,并证明任何在线算法的竞争比不可能小于 1.686。