首先看看题目描述的场景

image.png

一、题目的场景遇到的问题

Note：做题的时候，把这四点都写上，对于某个单一对象（TEL1 / LINE1）的状态图和时序图也画出来，因为后面用得着.

1、Deadlock（死锁）：一共N个电话，N根Line，因为每个TEL连接都需要先连接第I根Line，然后接着连接第i+1根Line，所以当N个电话同时被拿起时，他们没有一个人能获得第i+1根线的连接（因为当前N根线都被占用了），这就导致死锁（彼此等待但是互相不释放）

2、Sequence diagram for one telephone is not useful for identifying these problems

image.png

3、State machine of one object is not useful either.（一个状态图或时序图只能描述单一对象或过程，不能描述系统所有对象的相互作用，所以无法发现和解决死锁问题）

image.png

4、State machine for all objects is too complex.

二、怎么解决：使用CSP

2.1 CSP的基本语法（这里拿奶茶贩卖机举例）

• TEA_MACHINE = (coinslot.$5 -> maketea -> hatch.tea)
  我觉得 TEA_MACHINE 可以理解成一个对象或一个过程或一个状态，反正怎么都成，知道公式是这样的就好解释，后面大括号括起来了三个 Event，表示从 TEA_MACHINE 购买奶茶的过程是：coinslot.$5 -> maketea -> hatch.tea

• TEA_MACHINE = (coinslot.$5 -> maketea -> hatch.tea -> TEA_MACHINE)
  第一个表达式只是描述了一次贩卖奶茶的过程，这里在表达式的末尾加上了 TEA_MACHINE，表示这个过程可以被无限重复

• TEA_MACHINE = (coinslot.$5→hatch.tea→MACHINE | coinslot.$10 → hatch.cappucino → MACHINE )
  | ，被竖线分开的两组过程表示可选路径，类似时序图的ALT，上面的表达式意思是，如果投币5元，就可以购买 tea，如果投币10元，就可以购买 cappucino.

• 下面这个方框符号跟竖线的作用类似，下面看到TEL例子就知道什么意思了
  

  image.png

• MACHINE || GREEDY_CUST
  双竖线表示 MACHINE（贩卖机） 和 GREEDY_CUST（顾客） 相互影响和作用，这里就是为了解决题目中 N 台电话 N 根线时时序图没办法描述 N 个对象相互作用的问题，下面会说昨晚的 TEL 的题怎么做。

三、怎么使用 CSP 解决 Teleconferencing System 的问题

• 1、对于任意一个 TEL 对象有如下表达式：
  我们先自定义一个符号⊕，假设当i<N时， i⊕1 等价于 i+1 ；但是当 i=N 时，i⊕1为1（这是为了处理一个圈只有N台电话的问题，第N台电话应该连接第N和第1根线）

TELi = ( i.lifthandset → i.connectline.i → i.connectline.i⊕1 
→ i.hangup → i.disconnectline.i → i.disconnectline.i⊕1 → TELi )

• 2、那么要表达所有 TEL 相互所用的场景，应该这样写：

TELS = TEL1 || TEL2 || ... || TELN

• 3、对于任意一个 LINE 对象有如下表达式：
  我们再定义一个符号⊖，假设当 i>1 时 i⊖1 等价于 i-1；但是当 i=1 时，i⊖1 为 N（这也是为了处理上述⊕类似的情况）

LINEi = ( i.connectline.i → i.disconnectline.i → LINEi □ i⊖1.connectline.i → i⊖1.disconnectline.i → LINEi )

• 4、那么要表达所有 LINE 相互作用的场景，应该这样写：

LINES = LINE1 || LINE2 || ... || LINEN

• 5、我们把电话网络取名为NETWORK，有如下表达式

// 因为电话接入网络，是需要 TEL 和 LINE 共同完成
 NETWORK = TELS || LINES

下面的步骤是为了解决死锁问题

6、首先，死锁是当N个电话同时被拿起时，把N根线都占用了，导致等待不了另一根 LINE 释放而导致互相等待的死锁，所以需要有一个类似计数器的东西，这个计数器用记录当前正在使用的 TEL 的数量，当当前同时在使用的 TEL 数量到 N-1时候，禁止新的电话发起连接请求，这样就能避免死锁（避免N根 LINE 同时被占用而且互相等待得不到释放）

定义：GUARDi

所以，我们定义一个 GUARDi有如下含义：GUARD0 表示当前没有 TEL 在使用，GUARD1 表示当前有一个 TEL 在使用，GUARDi 表示当前有 i 个 TEL 在使用.

7、找出会影响 GUARDi 数量变化的事件集合
我们想一下，是不是只有电话被 lifthandset 和 hangup 的时候，正在使用的 TEL 数量的会发生变化，lifthandset 使得 GUARD 加1，hangup 使得 GUARD 减1，所以应该定义如下事件集合：

// 集合 L 中的元素分别表示从第 1-N 个电话被拿起的事件
 Let L = {1.lifthandset, 2.lifthandset, ..., N.lifthandset}
// x:L 可以表示 L 中的任何一个元素
x:L

// 集合 H 中的元素分别表示从第 1-N 个电话被挂断的事件
 Let H = {1.hangup, 2.hangup, ..., N.hangup}
// x:H 可以表示 H 中的任何一个元素
x:H

8、将GUARDi 和 L、H连接起来

// 下面这句话的意思是，当GUARD=0时，如果发生了L中的任何一个事件，GUARD 都会变成1
GUARD0 = ( x : L → GUARD1 )

// 下面这句话的意思也很明确，当GUARD=1时，如果发生L中的事件，GUARD会变成2；
// 如果发生H中的事件，GUARD会变成0；
GUARD1 = ( x : L → GUARD2 | x:H → GUARD0 )

然后我们会推断出下面这个表达式

GUARDi=( x : L → GUARDi + 1 | x : H → GUARDi − 1 )

9、现在 TEL、LINE、GUARD 都有了，我们就可以用下面的表达式描述整个系统的交互场景：

// 为什么要写 GUARD0，因为系统刚开始没有电话被使用，这时候GUARD的数量就是0
NEW_NETWORK = TELS || LINES || GUARD0