~vonfry/lift-dfa

ref: 8385a869a1e07b87517830bbd7c9559df25603c3 lift-dfa/doc/report.tex -rw-r--r-- 15.3 KiB
8385a869Vonfry test & main loop 2 years ago
                                                                                
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
\documentclass{ctexrep}
\usepackage{fontspec,xltxtra,xunicode,hyperref}
%\usepackage[nofonts]{ctex}

\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{mathtools}
\usepackage{ulem}
\allowdisplaybreaks

\usepackage{float}
\usepackage{tabularx}
\usepackage{diagbox}
\usepackage{booktabs}
\usepackage{longtable}
\usepackage{enumitem}

\usepackage{graphicx}
\usepackage{tikz}
\usetikzlibrary{arrows.meta,automata}

% 英文字体,linux
\setmainfont{Liberation Serif}
\setsansfont{Liberation Sans}
\setmonofont{Liberation Mono}

% 中文字体,linux
\setCJKmainfont{Source Han Serif SC}
\setCJKsansfont{Source Han Sans SC}
\setCJKmonofont{Source Han Sans SC}

\usepackage[a4paper]{geometry}
\geometry{a4paper,left=2cm,right=2cm,top=2cm,bottom=2cm,includehead,includefoot}
\linespread{1}

\usepackage{verbatim}
\usepackage{listings}
\lstset{
  float=H,
  breaklines=true,
  basicstyle=\ttfamily,
  mathescape=true,
  numbers=left,
  numbersep=5pt,
  xleftmargin=20pt,
  frame=tb,
  framexleftmargin=20pt
}
\renewcommand{\lstlistingname}{代码}

% 页眉脚
\usepackage{fancyhdr}
\fancyhead[L]{\leftmark}
\fancyhead[C]{}
\fancyhead[R]{形式语言与自动机作业}
\fancyfoot[L]{}
\fancyfoot[C]{}
\fancyfoot[R]{\thepage}
\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}

\ctexset{
  section/format += \raggedright
}

% 信息
\title{使用自动机求解电梯问题 设计及使用说明书}
\author{冯若禹,201930310076}
\date{\today}

\begin{document}
\maketitle

\pagestyle{fancy}
\pagenumbering{roman}

\newpage

\tableofcontents

\newpage
\pagenumbering{arabic}
% 正文

\chapter{引言}
本文档为《形式语言与自动机》课程作业,包含设计与使用说明。相应的程序代码实现不在本文档内,请见额外的文件。

\section{题目}

电梯模拟程序,要求如下:
\begin{enumerate}
\item 分析电梯运行中的多种状态,设计一下有穷状态自动机来模拟电梯的运行过程
\item 实现电梯模拟程序并写出设计说明与使用说明
\end{enumerate}

\section{有穷状态机}
有限状态机(finite-state machine,FSM)又称有限状态自动机(finite-state automation,FSA),简称状态机,是表示有限个状态以及在这些状态之间的转移和动作等行为的数学计算模型。 它是一种抽象的机器。在一组有限的状态中,任何时间都有一个明确的状态。有限动态机可以通过一系列输入从一个状态变为另外一个状态,称为转移。一个有穷自动状态机包含一组状态、一个初始状态和一些引起转移的输入。有穷自动机有两种类型,确定有穷状态机和非确定有穷状态机。

\section{固定式升降梯}
用于楼层间的升降移动。其操作可大体分为电梯箱外部输入与电梯箱内部输入。

\subsection{箱内输入}
箱内输入主要为到达特定的楼层。输入后移动到指定的楼层。

此外还包含紧急停止、紧急呼叫、快速关门、保持开门等输入。

\subsection{箱外输入}
箱外输入向上或向下。代表本楼层的人意途向上或向下移动。

电梯未运行时(即等待),会移动到本楼层。

电梯在移动时,会在运行的方向,进行停靠。

\subsection{升降移动}
箱内与箱外所有楼层请求,以当前移动方向为正,根据距离大小进行优先级排序,距离小的优先级高。按优先级顺序进行楼层的停靠。相移动方向相反时,则执行完当前方向上所有移动后再进行反向移动。

\chapter{设计说明}
在引言中,说明了问题及与之相关的两个主要元素。本章根据上述描述设计模拟程序。

\section{问题分析}\label{sec:dfa}
电梯运行可以分解为两个子状态机,分别为运行状态和楼层状态。两组状态分别管理着不同的部分,共同运作使得电梯正常工作。

在实际开发过程中,将二者聚合为一个结构(状态集合),使代码结构更加易读。

\subsection{运行状态}
电梯运行,可以分为四种状态,异常/紧急停止、装载、升降、待机。输入为紧急停止、到达任务楼层、无就绪任务。其状态转移图如\ref{fig:running-dfa}\begin{figure}[H]
  \centering
  \begin{tikzpicture}[->,>={Stealth[round]},circle,auto,node distance=3cm]
    \node (S) {$S$};
    \node [draw,right of=S,node distance=1.5cm] (idle) {待机}
      edge[<-] (S);
    \node [draw,right of=idle] (move) {升降}
      edge[<-] node [above] {就绪任务} (idle);
    \node [draw,above of=move] (load) {装载}
      edge[<-,bend left]  node [right,scale=.8] {到达任务楼层} (move)
      edge[->,bend right] node [left, scale=.8] {就绪任务} (move)
      edge[->,bend right] node [above left, scale=.8] {无就绪任务} (idle);
    \node [draw, below of=move] (es) {紧急}
       edge[<-] node [right] {异常/紧急停止} (move)
       edge[<-] node [left] {异常/紧急停止} (idle)
       edge[<-,bend right=60] node [right] {异常/紧急停止} (load);
  \end{tikzpicture}
  \caption{\label{fig:running-dfa}运行状态转移图}
\end{figure}

其中,升降又分为两个状态,上升与下降,其状态转移由外部输入的任务与当前停留楼层进行决定。如果输入与停留层相同,则由上述自动机立刻转移至下一状态。

\subsection{楼层状态}
楼层状态为当前电梯所在楼层,在电梯运行中,则为上一个经过的楼层。其状态数与楼层数相同。输入包含上升与下降两种。其状态转移图如\ref{fig:floor-dfa}

\begin{figure}[H]
  \centering
  \begin{tikzpicture}[->,>={Stealth[round]},circle,auto,node distance=3cm]
    \node (S) {$S$};
    \node [right of=S,draw,node distance=1.5cm] (F0) {F0}
      edge[<-] (S);
    \node [draw,below of=F0, node distance=3cm]  (B1) {B1}
        edge[bend left] node [left] {上升} (F0)
        edge[<-,bend right] node [right] {下降} (F0);
    \node [draw,right of=F0]  (F1) {F1}
        edge[<-,bend left] node [below] {上升} (F0)
        edge[bend right] node [above] {下降} (F0);
    \node [draw,right of=F1]  (F2) {F2}
        edge[<-,bend left] node [below] {上升} (F1)
        edge[bend right] node [above] {下降} (F1);
    \node [right of=F2] (dots) {$\dots$}
        edge[<-,bend left] node [below] {上升} (F2)
        edge[bend right] node [above] {下降} (F2);
    \node [draw,right of=dots] (Fn) {Fn}
        edge[<-,bend left] node [below] {上升} (dots)
        edge[bend right] node [above] {下降} (dots);
  \end{tikzpicture}
  \caption{\label{fig:floor-dfa}楼层状态转移图}
\end{figure}

\section{软件环境}\label{sec:env}

\paragraph{编程语言}
Haskell2010/ghc 8

\paragraph{构建工具}
cabal、nix

\paragraph{测试系统}
macOS

\paragraph{可运行系统}
ghc/cabal支持的系统

\paragraph{执行类型}
CLI

\section{总体设计}
使用cli进行输入与输出必要的参数和运行结果。输入必要参数后,将任务请求交由任务队列,调度器根据当前状态进行优先级排序。再由调度器根据队列任务进行调度,执行相应的电梯状态转换模块函数,完成电梯的运作。

其中输入输出模块与执行队列模块应该是并行的。因为输入输出应该是实时接收,进入队列,而这一过程中,电梯仍处于运行过程。但由于本课程主要任务为使用自动机解决电梯调度,而非关注异步执行,所以简化为单一输入和输出。

由上所述,将软件分为三个模块,输入输出模块、状态转换模块、调度模块。其关系如图\ref{fig:module}\begin{figure}[H]
  \centering
  \begin{tikzpicture}[>={Stealth[round]},auto, node distance=3cm,every node/.style={draw,rectangle}]
    \node (io) {输入/输出};
    \node [right of=io] (call) {调度模块};
    \node [right of=call] (lift) {状态转换模块};

    \draw (call.175) edge[<-] (io.5);
    \draw (call.185) edge[->] (io.355);
    \draw (lift.176) edge[<-] (call.5);
    \draw (lift.183) edge[->] (call.355);
  \end{tikzpicture}
  \caption{\label{fig:module}系统模块}
\end{figure}

输入输出负责必要的参数。根据运行结果打印相应的值。在正常的电梯程序中,输出应为控制信号以及显示在电梯内外屏幕或者按钮指示灯亮起。但这里只是一个模拟程序,以打印字符为基准。

调试模块管理任务队列和状态转换。在输入输出中将参数交由任务队列,并控制调试器根据任务队列的值进行相应的操作。

状态转换模块即本程序的核心,以DFA来管理电梯的运行状态。其分析见\ref{sec:dfa}\section{模块设计}

\subsection{输入输出}\label{subsec:io}
设计cli输入参数,交由调度模块,取得返回值,输出运行结果。在实际中,输入输出应是异步执行,且输出为电梯的电机等执行器件,输入为按钮的电子信号,这里简化为文本输入与输出。如果需要对异步操作进行实现,对其模块进行重构,独立线程运行调度器。调度器设计与IO完全分离,故不包含主循环控制,循环控制由IO模块进行实现。

输入参数设计结构如\ref{lst:arguments}\begin{lstlisting}[language=Haskell,label=lst:arguments,caption=参数结构]
newtype Arguments = Arguments
  { floorsName :: String -- ^ a list of string for floors name, which are splited
                         -- by "," or spaces . Its count is used to create state mathine
  }
\end{lstlisting}

使用库\verb~optparse-applicative~,通过应用函子定义参数解析器,由IO单子调用完成参数的解析。

除参数外,输入输出模块还管理计算结果的输出,如电子控制信号的发送,以及等待执行元件返回工部的信号。这里模拟程序以此化简。以打印楼层名和相关执行动作来描绘运作工况。同时,以主循环每次循问输入的方法来获取输入的任务。同时,以进程的睡眠(0.5s)来模拟执行元件的运行时间。为了简化设计,不使用多线程管理主循环。

接收参数后,初始化各子模块,启动主循环。在主循环中,每一个循环内进行任务的输入、任务列表的检查、下一任务的执行等。

\subsection{调度模块}
调度模块包含一个任务队列,根据当前的楼层状态选取状态变更的操作,调用状态转换模块中的转移函数完成状态的转移。

其主要包含如\ref{lst:call}。调度模块与IO操作完全分离,如\ref{subsec{io}}所述,此模块不包含循环控制等功能。需要由IO模块进行实现并调用的主调度函数。

\begin{lstlisting}[language=Haskell,label=lst:call,caption=调度函数]
onFloor :: String -> Lift -> TaskQueue -> TaskQueue

doTask :: LiftFloor
       -> Lift
       -> Either Lift (LiftFloor, Lift)  

doFloorUp :: Lift -> Lift

doFloorDown :: Lift -> Lift

onOpen :: Lift -> Lift

onClose :: Lift -> Lift

doIdle :: Lift -> Lift

doLoad :: Lift -> Lift

onExcept :: Lift -> Lift

doExcept :: Lift -> Lift
\end{lstlisting}

\subsection{状态转换模块}
基于haskell标准库的\verb~State~单子进行设计。\verb~State~用于结构用于描述状态的转移。而\verb~State~单子可以非常便利的对转移函数进行组合。在本模块中,会对所有的操作进行细分,而后通过组合的方式来实现实际的调用需求。
\footnote{由于本课题较为简单,也可以使用\verb~Reader~单子进行实现,但\verb~State~单子更加符合语义。}

首先我们需要先定义状态结构,一共包含两个,分别为楼层状态与执行状态,由于结构简单,使用\verb~newtype~进行语法层面的打包,在运行期不会产生额外的打包与解包。其具体结构如\ref{lst:state}

\begin{lstlisting}[language=Haskell,label=lst:state,caption=状态结构]
type LiftFloor = Int

data LiftState = LiftIdle
               | LiftMove LiftMoveT
               | LiftLoad
               | LiftException
               deriving (Eq, Show, Read)

data LiftMoveT = LiftMoveUp | LiftMoveDown
    deriving (Eq, Show, Read)

caseMoveT :: f           -- ^ return if Up
          -> f           -- ^ return if Down
          -> LiftMoveT
          -> f
caseMoveT a _ LiftMoveUp   = a
caseMoveT _ b LiftMoveDown = b

data Lift = Lift { curFloor   :: LiftFloor
                 , curState   :: LiftState
                 , floorNames :: FloorName
                 }
            deriving (Eq, Show, Read)
\end{lstlisting}

根据需求,定义如\ref{lst:state-trans}的转移函数,具体实现此处略去。

\begin{lstlisting}[language=Haskell,label=lst:state-trans,caption=转移函数]
moveLUp :: State Lift LiftFloor

moveLDown :: State Lift LiftFloor

idleS :: State Lift LiftFloor

loadS :: State Lift LiftFloor

exceptS :: State Lift LiftFloor

moveSUp :: State Lift LiftFloor

moveSDown :: State Lift LiftFloor
\end{lstlisting}

\chapter{使用说明}
本文档包含本软件 (电梯模拟程序)的使用说明。主要从运行环境、编译及参数进行说明。

本软件是一个cli程序。

\section{运行环境}

参考\ref{sec:env}

\section{编译、安装}
没有外部依赖,可以使用nix或者cabal进行编译。

\subsection{cabal}
使用\verb~cabal build~及\verb~cabal install~进行编译与安装,安装过程可省略,在编译目录下执行文件即可。

\subsection{nix}
使用\verb~nix build~进行编译,安装可以使用\verb~nix-env~完成,运行文件在生成的\verb~result~目录下。

\section{开发文档}

使用\verb~cabal haddock~,根据需要的文档类型进行生成。

\section{软件运行}
在CLI下运行执行文件即可。

\subsection{CLI参数}
\begin{lstlisting}[label=lst:cli-args,caption=cli参数]
Lift simulator.

Usage: lift [LIST]
  Lift simulator by DFA for my homework.

Available options:
  LIST                     a list of strting for floors name, which are splited
                           by , or space. (default: "B1,F0,F1,F2,F3,F4")
  -h,--help                Show this help text
\end{lstlisting}

\subsection{运行实例}
\begin{lstlisting}[label=lst:instance,caption=运行样例]
Your floors: ["B1","F0","F1","F2","F3","F4"]

------
Input tasks(floor name/(c)lose/(o)pen//(s)top/(e)xception)/[_]:
F4,F2,F1,B1,F4
do task
Current floor: "B1"
MoveTo: "B1"
Open
Close

------
Input tasks(floor name/(c)lose/(o)pen//(s)top/(e)xception)/[_]:

do task
Current floor: "B1"
MoveTo: "F1"

------
Input tasks(floor name/(c)lose/(o)pen//(s)top/(e)xception)/[_]:

do task
Current floor: "F0"
MoveTo: "F1"

------
Input tasks(floor name/(c)lose/(o)pen//(s)top/(e)xception)/[_]:

do task
Current floor: "F1"
MoveTo: "F1"
Open
Close

------
Input tasks(floor name/(c)lose/(o)pen//(s)top/(e)xception)/[_]:

do task
Current floor: "F1"
MoveTo: "F2"

------
Input tasks(floor name/(c)lose/(o)pen//(s)top/(e)xception)/[_]:

do task
Current floor: "F2"
MoveTo: "F2"
Open
Close

------
Input tasks(floor name/(c)lose/(o)pen//(s)top/(e)xception)/[_]:

do task
Current floor: "F2"
MoveTo: "F4"

------
Input tasks(floor name/(c)lose/(o)pen//(s)top/(e)xception)/[_]:

do task
Current floor: "F3"
MoveTo: "F4"

------
Input tasks(floor name/(c)lose/(o)pen//(s)top/(e)xception)/[_]:

do task
Current floor: "F4"
MoveTo: "F4"
Open
Close

------
Input tasks(floor name/(c)lose/(o)pen//(s)top/(e)xception)/[_]:

do task
Current floor: "F4"
MoveTo: "F4"
Open
Close

------
Input tasks(floor name/(c)lose/(o)pen//(s)top/(e)xception)/[_]:

Finish
\end{lstlisting}

\end{document}