Elevator Control System using ZIO

Modern Elevator system

Scenario: The passengers in a floor “a” choose their destination “b” then the elevator system decides which elevators are convenient to serve their requests and the passengers will be guided to the assigned elevator.

Analyse

1. Every elevator has its state which contains the current floor, and a set of the next stops.
2. The elevators will be moved step by step to their destination, and every step takes a duration depending to the elevator speed.
3. A passenger send a Pickup request on the floor “a” to a destination floor “b”.
4. the system will search which elevator is the nearest to “a” and is moving at the same direction to the floor “b”.
5. The chosen elevator will add in its stops the floor of the pickup request and its destination and continue to move step by step to the pickup request floor.
6. If the elevator is at its next stop floor, this stop should be deleted from the elevator state.
7. The request should be deleted when the elevator arrive to the requested floor.

Data Structure

It’s clear that we have:

• ElevatorState that contains floor and set[Stop].
• PickupRequest that has floor and destination.
• ElevatorSystem that has elevators and requests.

It seems like this:

case class ElevatorState(floor: Int, stops: Set[Int])
case class PickupRequest(floor: Int, destinationFloor: Int)
class ElevatorSystem(elevators: List[ElevatorState],
                     requests : immutable.Queue[PickupRequest])

But wait !

1. we need to preserve the elevators state and to update the current floor in every step also every step takes a duration.
2. For requests, I thought about a Queue because when the elevator consumes the first request that request would be removed from the queue but there are those problems:

• If two or more persons send the same pickup request and they are on the same floor at the same time and they are waiting together, while the closest elevator is not yet arrived, a search process should be executed for the concurrent requests.
• We need an asynchronous queue because every request will wait until finding a close elevator to pick up.
• Remember that the elevators should take always the pickup requests to add new stops. But what if there is no requests and the elevators want to take a request in an empty queue? Or what if the requests are waiting and all elevators are busy? We need a Back pressure strategy 🤔

Which library can we use to solve this problem ?

Scalaz-zio is an open source scala library which lets developers build high-performance, type-safe, concurrent, asynchronous applications that don’t leak resources or deadlock, and are easy to reason about compositionally, test, and refactor using purely functional code.

Data Structure using ZIO

Which data structures in ZIO can solve the problems above?

1. We need a mutable data structure, the elevators will be moved step by step to their next stops but if there is a pickup request to the next stop?! 🤯 So we will have a mutable data structure + concurrency. We should avoid race conditions when threads are updating the same state! 😱 We can use zio-Ref so we can atomically update the state.
2. We can use the asynchronous zio-Queue which provides a composable back-pressure. We can run the producers/consumers concurrently in different fibers.

But how can the elevators move continuously and take some duration between each floor? And how could the elevators consume the pickup requests forever?

In ZIO, we can repeat our actions using different strategies which are defined at the Schedule type.

class ElevatorSystem(elevators: scalaz.zio.Ref[List[ElevatorState]],
                     requests : scalaz.zio.Queue[PickupRequest])

Sounds great!

Implementation

• Create the ElevatorSystem with n elevators

def apply(n: Int): IO[Nothing, ElevatorSystem] = {
  val elevators =
      List.fill(capacity(initialElevatorState)
  for {
    queue <- Queue.bounded[PickupRequest](n)
    state <- Ref(elevators)
  } yield new ElevatorSystem(state, queue)
}

• Send pickup request

def request(pickupRequest: PickupRequest): IO[Nothing, Unit] =
  requests.offer(pickupRequest)

• Search the closest elevator

def search(elevators: List[ElevatorState],
           request  : PickupRequest): Option[Int] =
  elevators.zipWithIndex
    .filter(_._1.isOnWay(request.floor, request.destinationFloor))
    .sortBy(_._1.distanceFrom(request.floor))
    .headOption
    .map(_._2)

• Move the elevatorState with Time-stepping:

val moveElevator: IO[Nothing, Unit] = elevators
  .update(ElevatorSystem.step)
  .repeat(Schedule.fixed(duration))
  .void

• add the pickup request’s floor and its destination to the stops of the chosen elevator:

val processRequests: IO[Nothing, Unit] = (for {
  consumer <- requests.take
  _ <- elevators.update { state =>
    ElevatorSystem.search(state, consumer) match {
      case None => state
      case Some(index) =>
        state.updated(index,
                      state(index)
                        .addStop(consumer.floor)
                        .addStop(consumer.destinationFloor))
    }
  }
} yield ()).repeat(Schedule.forever).void

• Run the elevatorSystem:

def run(duration: Duration): IO[Nothing, Unit] = 
     moveElevator.fork *> processRequests

moveElevator is called in a different fiber and processRequest will be computed using the updated Elevator state.

The whole implementation is here.

Conclusion

You can improve this implementation and add more features like openLiftDoor, closeLiftDoor that will be called when the elevator is on its next stop, then it will wait some duration, and sometimes if someone want to enter without sending pickupRequest and the elevator’s door is still opened, we can create a new scalaz.zio.Promise when the lift door is opened which will be suspended until the door would be closed.

With Scalaz-zio we can solve a real world problem, with a testable and simple code.