OS作业-电梯调度 | WWD’s Blog

type

status

date

slug

summary

电梯调度设计方案

一、项目简介

项目内容：本项目旨在实现一个电梯调度系统，模拟调度一栋20层楼的5部电梯，能够根据用户的上行和下行需求自动分配电梯并控制电梯运行。该系统采用多线程技术，有效地提高了程序的运行效率。系统通过图形用户界面(GUI)展示电梯的实时状态，并允许用户通过点击楼层按钮来发出上行和下行请求。

开发环境

系统：Windows 11 家庭中文版

IDE：PyCharm Community Edition 2022.2

Python 解释器：Python版本为3.8.16，且已通过pip安装了PyQt5

二、系统架构

根据任务需求，将电梯调度程序分为以下几个模块（类）：

主程序入口：负责初始化变量、创建对象和启动线程。

图形用户界面（MainWindow 类）：展示电梯的实时状态，并允许用户通过点击电梯内外部楼层按钮来发出上行和下行请求，同时可以通过警报键来紧急制动电梯。同时，该类每隔一段时间会刷新一次界面，实现界面的实时更新。在开发时，在QtDesigner上进行设计，之后使用PyUIC导出至ui_mainwindow中，并在该类中直接调用。

电梯线程（Elevator类）：负责根据任务队列控制电梯的运行状态（上行、下行或停止）以及开关门操作。

外部任务处理线程（Outer类）：负责接收和处理用户的上行和下行请求，通过寻找距离最近的电梯来分配任务。

类名	作用
MainWindow	继承自QtWidgets.QMainWindow，并实现了一个电梯调度系统的用户界面。这个界面包含了电梯内部按钮、电梯楼层显示、电梯运行状态指示、外部上下楼请求按钮以及电梯报警按钮等组件。
Elevator	继承自QThread，使得电梯可以作为一个独立的线程运行。类中包含了多个方法，分别用于处理电梯的运行状态、楼层移动、门的开关以及故障处理。
Outer	继承自 QThread，是一个外部任务处理线程。这个类主要负责处理电梯系统中外部任务（即用户在楼层按上行或下行按钮时产生的任务），并将任务分配给最合适的电梯。

三、核心算法

系统的核心算法为寻找距离最近的电梯，其思路如下：

为了寻找距离最近的电梯，我们需要考虑电梯的运行状态、当前楼层和任务队列。综合FCFS（先来先服务算法）算法与LOOK算法进行设计，其具体算法如下：

遍历所有电梯，跳过故障状态的电梯。

根据电梯运行状态和任务队列计算到目标楼层的距离：

如果电梯没有任务，直接计算当前楼层与目标楼层的绝对值。
如果电梯运行方向与任务需求相同，且任务楼层在电梯运行方向上，计算当前楼层与目标楼层的绝对值。
其他情况下，计算当前楼层与最远任务楼层的绝对值，再加上目标楼层与最远任务楼层的绝对值。

选择距离最小的电梯作为目标电梯。

该算法优先考虑运行方向与任务需求相同的电梯，并在多个电梯之间选择距离最近的电梯以减少等待时间。具体代码如下：

此外，elevator_up_target_list 与 elevator_down_target_list 是两个优先级队列，分别为升序和降序排列，在访问这两个二维队列时，通过pop便可以得知下一任务的位置。

四、线程同步

在本项目中，使用了多个线程来处理不同任务，例如外部任务处理线程（Outer）和电梯运行线程（Elevator）。在这种情况下，线程同步就显得尤为重要，以防止数据竞争和保持系统的正确性。我们主要通过使用互斥锁（mutex）来实现线程同步。

互斥锁是一种同步原语，用于解决多线程中的临界区问题。当一个线程拥有互斥锁时，其他线程必须等待，直到锁被释放。通过使用互斥锁，我们可以确保同一时间只有一个线程能够访问和修改共享数据。

4.1 项目中用到的全局常量与变量

全局常量

全局变量

变量名	作用
elevator_up_target_list	每台电梯需要向上运行处理的目标楼层列表
elevator_down_target_list	每台电梯需要向下运行处理的目标楼层列表
elevator_cur_floor	每台电梯的当前楼层
elevator_states	每台电梯的状态
outer_tasks_list	用户产生的外部任务列表

枚举类

此外，为了使得代码的可读性更强，使用ELEVATOR_STATE、MOVE_STATE、TASK_STATE三个枚举类分别表示电梯状态、电梯移动状态和任务状态。

4.2 线程同步的关键部分

以下是涉及线程同步的关键部分：

Outer 线程

Outer 线程负责处理外部任务，如用户在楼层按下上行或下行按钮。在这个线程中，需要访问和修改以下共享数据：outer_tasks_list、elevator_states、elevator_cur_floor、elevator_up_target_list、elevator_down_target_list

在访问和修改这些共享数据时，需要使用互斥锁来确保线程同步。具体实现如下：

在这个示例中，当线程进入 run 方法时，首先锁定互斥锁。在互斥锁被锁定期间，其他试图访问共享资源的线程将被阻塞。接下来，线程执行一系列操作，如找到距离最短的电梯编号、将任务加入队列等。在完成这些操作之后，线程解锁互斥锁，允许其他线程访问共享资源。