13、数据结构与算法Python：队列的应用（打印任务）-程序员快看-教程，程序员编程资料站

模拟算法：打印任务

多人共享一台打印机，采取“先到先服务”的队列策略来执行打印任务

在这种设定下，一个首要的问题就是：这种打印作业系统的容量有多大？在能够接受的等待时间内，系统能容纳多少用户以多高频率提交多少打印任务？

一个具体的实例配置如下：

一个实验室，在任意的一个小时内，大约有10名学生在场，这一小时中，每人会发起2次左右的打印，每次1～20页

打印机的性能是：

以草稿模式打印的话，每分钟10页，以正常模式打印的话，打印质量好，但速度下降为每分钟5页。

问题是：怎么设定打印机的模式，让大家都不会等太久的前提下尽量提高打印质量？

这是一个典型的决策支持问题，但无法通过规则直接计算

我们要用一段程序来模拟这种打印任务场景，然后对程序运行结果进行分析，以支持对打印机模式设定的决策。

如何对问题建模？

首先对问题进行抽象，确定相关的对象和过程

抛弃那些对问题实质没有关系的学生性别、年龄、打印机型号、打印内容、纸张大小等等众多细节

对象：打印任务、打印队列、打印机

打印任务的属性：提交时间、打印页数
打印队列的属性：具有FIFO性质的打印任务队列
打印机的属性：打印速度、是否忙

过程：生成和提交打印任务

确定生成概率：实例为每小时会有10个学生提交的20个作业，这样，概率是每180秒会有1个作业生成并提交，概率为每秒1/180。确定打印页数：实例是1～20页，那么就是1～20页之间概率相同

过程：实施打印

当前的打印作业：正在打印的作业
打印结束倒计时：新作业开始打印时开始倒计时
，回0表示打印完毕，可以处理下一个作业

模拟时间：

统一的时间框架：以最小单位（秒）均匀流逝的
时间，设定结束时间
同步所有过程：在一个时间单位里，对生成打印
任务和实施打印两个过程各处理一次

打印任务问题：模拟流程

创建打印队列对象

时间按照秒的单位流逝

按照概率生成打印作业，加入打印队列
如果打印机空闲，且队列不空，则取出队首作业
打印，记录此作业等待时间
如果打印机忙，则按照打印速度进行1秒打印
如果当前作业打印完成，则打印机进入空闲

时间用尽，开始统计平均等待时间

作业的等待时间

生成作业时，记录生成的时间戳
开始打印时，当前时间减去生成时间即可

作业的打印时间

生成作业时，记录作业的页数
开始打印时，页数除以打印速度即可

class Printer:
    def __init__(self, ppm):
        # 打印速度
        self.pagerate = ppm
        # 打印任务
        self.currentTask = None
        # 任务倒计时
        self.timeRemaining = 0

    def tick(self):
        # 打印1秒
        if self.currentTask != None:
            self.timeRemaining = self.timeRemaining - 1
            if self.timeRemaining <= 0:
                self.currentTask = None

    def busy(self):
        if self.currentTask != None:
            return True
        else:
            return False

    def startNext(self, newtask):
        self.currentTask = newtask
        self.timeRemaining = newtask.getPages() * 60 / self.pagerate
class Task:
    def __init__(self, time):
        self.timestamp = time
        self.pages = random.randrange(1, 21)

    def getStamp(self):
        return self.timestamp

    def getPages(self):
        return self.pages

    def waitTime(self, currenttime):
        return currenttime - self.timestamp
def newPrintTask():
    num = random.randrange(1, 181)
    if num == 180:
        return True
    else:
        return False
def simulation(numSeconds, pagesPerMinute):
    labprinter = Printer(pagesPerMinute)
    printQueue = Queue()
    waitingtimes = []

    for currentSecond in range(numSeconds):
        if newPrintTask():
            task = Task(currentSecond)
            printQueue.enqueue(task)

        if (not labprinter.busy()) and (not printQueue.isEmpty()):
            nexttask = printQueue.dequeue()
            waitingtimes.append(nexttask.waitTime(currentSecond))
            labprinter.startNext(nexttask)
        labprinter.tick()

    averageWait = sum(waitingtimes)/len(waitingtimes)
    print("Average Wait %6.2f secs %3d tasks remaining." % (averageWait, printQueue.size()))
for i in range(10):
    simulation(3600, 5)

为了对打印模式设置进行决策，我们用模拟程序来评估任务等待时间

通过两种情况模拟仿真结果的分析，我们认识到如果有那么多学生要拿着打印好的程序源代码赶
去上课的话那么，必须得牺牲打印质量，提高打印速度。

模拟系统对现实的仿真

在不耗费现实资源的情况下——有时候真实的实验是无法进行的可以以不同的设定，反复多次模拟来帮助我们进行决策。

13、数据结构与算法Python：队列的应用（打印任务）