模拟队列打印问题

• Python数据结构——队列 模拟队列打印问题
• • 1. 问题描述
  • 2. 模拟步骤
  • 3. 程序实现
  • • 3.1 Printer类
    • 3.2 Task类
    • 3.3 主程序
  • 4. 完整程序
  • 5. 程序运行
  • 6. 讨论

Python数据结构——队列 模拟队列打印问题

本文旨在用Python模拟打印任务队列。

1. 问题描述

学生向共享打印机发送打印请求，这些打印任务被存在一个队列中，并且按照先到先得的顺序执行。这样的设定可能导致很多问题。其中最重要的是，打印机能否处理一定量的工作。如果不能，学生可能会由于等待过长时间而错过要上的课。

考虑计算机科学实验室里的这样一个场景：在任何给定的一小时内，实验室里都有约10个学生。他们在这一小时内最多打印2 次，并且打印的页数从1到20不等。实验室的打印机比较老旧，每分钟只能以低质量打印10页。可以将打印质量调高，但是这样做会导致打印机每分钟只能打印5页。降低打印速度可能导致学生等待过长时间。那么，应该如何设置打印速度呢？

可以通过构建一个实验室模型来解决该问题。我们需要为学生、打印任务和打印机构建对象。当学生提交打印任务时，我们需要将它们加入等待列表中，该列表是打印机上的打印任务队列。当打印机执行完一个任务后，它会检查该队列，看看其中是否还有需要处理的任务。我们感兴趣的是学生平均需要等待多久才能拿到打印好的文章。这个时间等于打印任务在队列中的平均等待时间。

在模拟时，需要应用一些概率学知识。举例来说，学生打印的文章可能有1-20页。如果各页数出现的概率相等，那么打印任务的实际时长可以通过1-20的一个随机数来模拟。

如果实验室里有10个学生，并且在一小时内每个人都打印两次，那么每小时平均就有20个打印任务。在任意一秒，创建一个打印任务的概率是多少？回答这个问题需要考虑任务与时间的比值。每小时20个任务相当于每180秒1个任务。

20 个任务 1 小时 ∗ 1 小时 60 分 ∗ 1 分 60 秒 = 1 个任务 180 秒 \frac{20\text{个任务}}{1\text{小时}} * \frac{1\text{小时}}{60\text{分}} * \frac{1\text{分}}{60\text{秒}} = \frac{1\text{个任务}}{180\text{秒}} 1小时20个任务​∗60分1小时​∗60秒1分​=180秒1个任务​

可以通过1-180的一个随机数来模拟每秒内产生打印任务的概率。如果随机数正好是180，那么就认为有一个打印任务被创建。注意，可能会出现多个任务接连被创建的情况，也可能很长一段时间内都没有任务。这就是模拟的本质。我们希望在常用参数已知的情况下尽可能准确地模拟。

2. 模拟步骤

下面是主要的模拟步骤。

(1) 创建一个打印任务队列。每一个任务到来时都会有一个时间戳。一开始，队列是空的。

(2) 针对每一秒(currentSecond)，执行以下操作。

• 是否有新创建的打印任务？如果是，以currentSecond 作为其时间戳并将该任务加入到队列中。
• 如果打印机空闲，并且有正在等待执行的任务，执行以下操作：
  • 从队列中取出第一个任务并提交给打印机；
  • 用currentSecond减去该任务的时间戳，以此计算其等待时间；
  • 将该任务的等待时间存入一个列表，以备后用；
  • 根据该任务的页数，计算执行时间。
• 打印机进行一秒的打印，同时从该任务的执行时间中减去一秒。

• 如果打印任务执行完毕，或者说任务需要的时间减为0，则说明打印机回到空闲状态。

  (3) 当模拟完成之后，根据等待时间列表中的值计算平均等待时间。

3. 程序实现

创建3个类：Printer、Task和PrintQueue。它们分别模拟打印机、打印任务和队列。

3.1 Printer类

Printer类需要检查当前是否有待完成的任务。如果有，那么打印机就处于工作状态，并且其工作所需的时间可以通过要打印的页数来计算。其构造方法会初始化打印速度，即每分钟打印多少页。tick方法会减量计时，并且在执行完任务之后将打印机设置成空闲状态。

class Printer:
    def __init__(self, ppm):
        self.pagerate = ppm
        self.currentTask = None
        self.timeRemaining = 0

    def tick(self):
        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

           

3.2 Task类

Task类代表单个打印任务。当任务被创建时，随机数生成器会随机提供页数，取值范围是1-20。

使用random模块中的randrange函数来生成随机数。

每一个任务都需要保存一个时间戳，用于计算等待时间。这个时间戳代表任务被创建并放入打印任务队列的时间。waitTime方法可以获得任务在队列中等待的时间。

import random

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

           

3.3 主程序

主模拟程序实现了之前描述的算法。printQueue对象是队列抽象数据类型的实例。布尔辅助函数newPrintTask判断是否有新创建的打印任务。我们再一次使用random模块中的randrange函数来生成随机数，不过这一次的取值范围是1-180。平均每180秒有一个打印任务。通过从随机数中选取180，可以模拟这个随机事件。该模拟程序允许设置总时间和打印机每分钟打印多少页。

import random

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()))


def newPrintTask():
    num = random.randrange(1, 181)
    if num == 180:
        return True
    else:
        return False

           

4. 完整程序

import random

class Queue:
    def __init__(self):
        self.items = []
    
    def isEmpty(self):             # 判断是否为空
        return self.items == []
    
    def enqueue(self, item):       # 压入队列（这里将列表位置0作为队列尾部）
        self.items.insert(0, item)

    def dequeue(self):             # 弹出（这里将列表末尾作为队列头部）
        return self.items.pop()

    def size(self):                # 返回队列中元素数目
        return len(self.items)


class Printer:
    def __init__(self, ppm):
        self.pagerate = ppm
        self.currentTask = None
        self.timeRemaining = 0

    def tick(self):
        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 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()))


def newPrintTask():
    num = random.randrange(1, 181)
    if num == 180:
        return True
    else:
        return False

           

5. 程序运行

首先，模拟60分钟（3600秒）内打印速度为每分钟5页。并且，我们进行10次这样的模拟。由于模拟中使用了随机数，因此每次返回的结果都不同。

>>> for i in range(10):
        simulation(3600, 5)

Average Wait  23.85 secs   0 tasks remaining.
Average Wait 164.55 secs   3 tasks remaining.
Average Wait  36.53 secs   0 tasks remaining.
Average Wait 211.04 secs   3 tasks remaining.
Average Wait  65.12 secs   0 tasks remaining.
Average Wait 114.25 secs   5 tasks remaining.
Average Wait 126.95 secs   3 tasks remaining.
Average Wait 313.94 secs   6 tasks remaining.
Average Wait  50.41 secs   0 tasks remaining.
Average Wait 109.14 secs   1 tasks remaining.
           

现在把打印速度改成每分钟10页，然后再模拟10次。由于加快了打印速度，因此我们希望一小时内能完成更多打印任务。

>>> for i in range(10):
        simulation(3600, 10)

Average Wait  18.12 secs   2 tasks remaining.
Average Wait  14.25 secs   0 tasks remaining.
Average Wait  21.76 secs   0 tasks remaining.
Average Wait  12.29 secs   2 tasks remaining.
Average Wait  24.60 secs   0 tasks remaining.
Average Wait  63.46 secs   0 tasks remaining.
Average Wait   4.86 secs   0 tasks remaining.
Average Wait  40.50 secs   1 tasks remaining.
Average Wait  11.96 secs   1 tasks remaining.
Average Wait  20.46 secs   0 tasks remaining.
           

6. 讨论

在之前的内容中，我们试图解答这样一个问题：如果提高打印质量并降低打印速度，打印机能否及时完成所有任务？我们编写了一个程序来模拟随机提交的打印任务，待打印的页数也是随机的。

上面的输出结果显示，按每分钟5页的打印速度，任务的等待时间在23.85秒和313.94秒之间，相差约5分钟。提高打印速度之后，等待时间在4.86秒和63.46秒之间。此外，在每分钟5页的速度下，10次模拟中有6次没有按时完成所有任务。

可见，降低打印速度以提高打印质量，并不是明智的做法。学生不能等待太长时间，当他们要赶去上课时尤其如此。5分钟的等待时间实在是太长了。

这种模拟分析能帮助我们回答很多“如果”问题。只需改变参数，就可以模拟感兴趣的任意行为。以下是几个例子。

• 如果实验室里的学生增加到20个，会怎么样？
• 如果是周六，学生不需要上课，他们是否愿意等待？
• 如果每个任务的页数变少了，会怎么样？

这些问题都能通过修改本例中的模拟程序来解答。但是，模拟的准确度取决于它所基于的假设和参数。真实的打印任务数量和学生数目是准确构建模拟程序必不可缺的数据。