Reading Time: 15 minutes

In October 2020 I took Dave Beazley’s Advanced Programming with Python course. Since I wrote a series about his SICP course and the Raft course, I figured I’d write about this one too :).

In the first elevator post, I tried (and failed) to implement a functioning elevator control system by changing the state on an elevator class. Then I tried (and failed again) with a publish-subscribe implementation. Finally I busted out threads and got the sucker working by treating each move of the elevator as a discrete unit of time and spinning off a new thread for each, so they didn’t block listening for new requests.

I told you to hang onto that idea of discrete time. I said we’d need it again. You’re about to find out why. But first, I wanna answer a burning question:

Chelsea, what was the problem with the thread implementation?

I mean, first of all, the thing didn’t work perfectly in all circumstances. That wasn’t because of threads: it was because even on three lattes, I can’t replicate an entire niche industry’s worth of software in six hours yet.

However, I did not like the thread implementation for a few reasons:

1. Python is not designed for multithreading. This, like functional programming, is one of those things Python can do, but it’s not really for. Python has a global interpreter lock. Threading is stuffed into a separate library. Once you start a thread, you have limited control over it.
2. Even in general, threading code can be tough to reason about. This means that a robust solution takes longer to implement and becomes harder to communicate.
3. When you have multiple threads modifying the same data store, it’s easy to screw it up.

This is why we lock rows in databases while they’re being modified: so some other thread doesn’t come along and edit the same row, and the next thing we know, someone is mid-edit and the row changes out from under them.

My elevator implementation keeps track of floor requests, not with a fancy database, but with a lowly set. It’s a set because multiple people requesting a floor should not result in multiple elevator visits: the elevator can pick up everyone by stopping there one time.

But suppose that, as my elevator doors close to leave floor 3, an additional person presses the 3rd floor button. One thread might add the 3 to the set for them (which does nothing since 3 is already in there) while another thread removes 3 from the set, since the elevator is now leaving that floor. Now, the person on floor 3 is stranded.

And anyway, in Python in particular, I see a lot of convoluted and unsafe solutions to concurrency problems.

Using separate threads to manipulate a single set object should be an extreme example, but it isn’t. Last week I reviewed an assignment that taught students to launch four instances of Python on the same machine to run Pong on four cores. You do not need four cores to run Pong.

asyncio, a popular Python concurrency library that comes with the standard distribution, is lighter weight and probably more appropriate for both of the above problems than threads or this:

asyncio works manages queues of tasks to be completed (async) and then pulls them off those queues at the appropriate time (await). It does this, essentially, with generators.

A generator, like a collection such as a list or dictionary, allows us to iterate through its elements. Unlike those collections, though, it allows us to tightly control when the iterations happen by explicitly forcing us to call the next() method on it for each item. asyncio‘s code routine relies on the construct to stop, start, and interleave collections of tasks.

We could use asyncio, but that wouldn’t be much fun. We’re trying to learn how Python works, and asyncio abstracts away all the details.

So instead of using asyncio, I’ll take inspiration from its implementation and go from scratch.

First up: that thrilling, terrifying, titillating code change you knew we’d be making:

Now, let’s make a generator.

Here’s the full implementation of the Elevator class with a generator, but the important pieces that I changed from the first post are as follows:

class Elevator:
    ...

    def keep_it_moving(self):
        while True:
            yield self.next_move()

    def next_move(self):
        if self.floors_to_visit:
            if len(self.floors_to_visit) == 1 and self.current_floor in self.floors_to_visit:
                self.stay_on_floor()
            elif self.going_up and max(self.floors_to_visit) > self.current_floor:
                self.move_floors(1)
            else:
                self.going_up == False
                self.move_floors(-1)
    ...

    def go_to_floor(self, floor):
        self.log(f"Stop requested for floor {floor}")
        self.floors_to_visit.add(floor)
        next(self.keep_it_moving())
        time.sleep(1)

1. The function called keep_it_moving keeps a continuous stream (while True) that yields the result of the next_move method. The yield keyword marks this as a generator, and next_move will only be called when next() is called on keep_it_moving.
2. next_move delineates the three discrete tasks an elevator can do: go up 1 floor, go down 1 floor, and stay on the current floor. These are the tasks we will manage with our generator.
3. We call the next() method on keep_it_moving in the go_to_floor method, which gets called every time someone requests a floor. So each time a floor is requested, the elevator will do one task. No more waiting for the elevator to do all its existing tasks before it even registers a new floor request. (I put the time.sleep call there so I could watch the elevator in action).

If we call our Elevator class like this:

elevator = Elevator()
panel = ElevatorButtonPanel(elevator)

panel.request_button_pressed(5)
panel.request_button_pressed(3)
panel.request_button_pressed(4)
panel.request_button_pressed(2)
panel.request_button_pressed(1)
panel.request_button_pressed(5)

time.sleep(5)
panel.request_button_pressed(4)

time.sleep(6)
panel.request_button_pressed(4)
panel.request_button_pressed(1)

We get…this.

Chelseas-MacBook-Pro:5_elevator chelseatroy$ python elevator.py
Stop requested for floor 5
On floor 2
Chelseas-MacBook-Pro:5_elevator chelseatroy$ python elevator.py

What happened? Well, since a single elevator task only goes up or down a single floor, the single request from floor 5 only entitled the elevator to one move in the five-ward direction. Once the list of tasks is complete, the program finishes. Clearly, this isn’t going to work. The elevator needs to be entitled to as many moves as it needs to fulfill existing requests.

So it’s time to introduce the Null Object Pattern.

We need the elevator to be able to make the necessary moves with or without a new request for another floor. But the last time we implemented elevator tasks separately from floor requests, we exposed ourselves to runaway threads and possible data corruption. So this time, rather than hacking in that direction, we hack in the other direction by introducing a Null Floor Request that requests no additional floors but entitles the elevator to another move.

A few changes:

    #from the Elevator Button Panel class
    def request_button_pressed(self, floor=None):
        self.elevator.go_to_floor(floor)

    #from the Elevator class
    def go_to_floor(self, floor):
        self.log(f"Stop requested for floor {floor}")
        if floor is not None:
            self.floors_to_visit.add(floor)
        next(self.keep_it_moving())
        time.sleep(1)

1. Previously, the elevator button panel called the request_button_pressed function only to request a floor. Now, it has a default of requesting no floor.
2. When the floor request reaches the elevator, the elevator checks for the null floor request. If it finds a null floor request, it doesn’t add anything to the set of floors to visit. But it does summon another task of the elevator.

This buys our elevator the tasks it needs to get to the penthouse:

elevator = Elevator()
panel = ElevatorButtonPanel(elevator)

panel.request_button_pressed(5)
panel.request_button_pressed()
panel.request_button_pressed()
panel.request_button_pressed()
panel.request_button_pressed()

Ta-da!

Chelseas-MacBook-Pro:5_elevator chelseatroy$ python elevator.py
Stop requested for floor 5
On floor 2
Stop requested for floor None
On floor 3
Stop requested for floor None
On floor 4
Stop requested for floor None
On floor 5
Stopping at floor 5
Opening doors at floor 5
DOORS CLOSING
...

In this example, I manually make the null requests. For an unsupervised elevator, we’d need some automated process to add these for us.

But how will we know how many null requests to add?

In theory, we could subtract the requested floor number from the current floor number. In practice, this doesn’t work because the requests aren’t serviced in order of the time they were made. If the elevator is on floor 1 and someone requests floor 5, and then as the elevator is on the way up at floor 2 someone requests floor 4, it should open at floor 4 first, even though 5 was requested first. Now the number of extra moves required changes, because we have one more request and need one less “free move.”

So instead of trying to keep track of that, we ensure that we don’t have to. If the elevator doesn’t have a destination (that is, when self.floors_to_visit is empty), the elevator doesn’t go anywhere. So “extra moves” don’t cause a problem:

panel.request_button_pressed(5)
panel.request_button_pressed()
panel.request_button_pressed()
panel.request_button_pressed()
panel.request_button_pressed()
panel.request_button_pressed()
panel.request_button_pressed()
panel.request_button_pressed()
panel.request_button_pressed()
panel.request_button_pressed()
panel.request_button_pressed()
panel.request_button_pressed()
panel.request_button_pressed()
panel.request_button_pressed(3)
panel.request_button_pressed(4)
panel.request_button_pressed(2)
panel.request_button_pressed(1)
panel.request_button_pressed(5)

It works in spite of “extra” requests! Those requests get logged and ignored, and the elevator goes where it needs to go.

Chelseas-MacBook-Pro:5_elevator chelseatroy$ python elevator.py
Stop requested for floor 5
On floor 2
Stop requested for floor None
On floor 3
Stop requested for floor None
On floor 4
Stop requested for floor None
On floor 5
Stopping at floor 5
Opening doors at floor 5
DOORS CLOSING
Stop requested for floor None
Stop requested for floor None
Stop requested for floor None
Stop requested for floor None
Stop requested for floor None
Stop requested for floor None
Stop requested for floor None
Stop requested for floor None
Stop requested for floor None
Stop requested for floor 3
On floor 4
On floor 3
Stopping at floor 3
Opening doors at floor 3
DOORS CLOSING
Stop requested for floor 4
On floor 4
Stopping at floor 4
Opening doors at floor 4
DOORS CLOSING
...

We interleave discrete requests with discrete tasks to move the elevator, step by step, to the right locations.

We can automate this by inserting, for every floor request, 4 null requests: the maximum number of moves it would take the elevator in this 5 floor building to fulfill any request:

def idle_requests_to(panel):
    for n in range(4):
        panel.request_button_pressed()

panel.request_button_pressed(5)
idle_requests_to(panel)
panel.request_button_pressed(3)
idle_requests_to(panel)
panel.request_button_pressed(1)
idle_requests_to(panel)
panel.request_button_pressed(4)
idle_requests_to(panel)
panel.request_button_pressed(2)
idle_requests_to(panel)
panel.request_button_pressed(1)
idle_requests_to(panel)
panel.request_button_pressed(5)
idle_requests_to(panel)

Now, you’ll notice something wonky about this implementation: it goes wherever the next request asks it to, rather than economizing on stops.

I messed with this for a while, figuring it had something to do with my concurrency implementation. But when I slowed down and started printing the floor request set, I realized that the issue really came from my strategy for deciding what the elevator should do next.

Where does an in-demand elevator go?

Worth noting at this juncture: real elevator request panels usually have both up and down buttons, which help identify which direction riders intend to head. This implementation does not have that: there’s just a button on each floor, and buttons in the elevator, and requests from those various buttons all get registered to the same place. Under those circumstances, our limited information might mean someone gets on going the wrong direction, if that’s the most efficient route for the elevator as a whole.

I sent a Twitter DM to Dave, who recommended I take a look at the SCAN algorithm for operating systems:

This algorithm is also known, apparently, as “the elevator algorithm.” How it works: it sets its direction from A to B, fulfills all the requests it encounters on the way from A to B, then turns around and heads from B to A, fulfilling all the requests it encounters in that direction. Repeat.

So, something like this in our Elevator’s next_move function:

    def next_move(self):
        if self.floors_to_visit:
            if self.going_up:
                if max(self.floors_to_visit) > self.current_floor:
                    self.move_floors(1)
                else:
                    self.going_up = False
            elif not self.going_up:
                if min(self.floors_to_visit) < self.current_floor:
                    self.move_floors(-1)
                else:
                    self.going_up = True

*I could have said else instead of elif not self.going_up, but I wanted to be explicit.

We got a teeny tiny bit fancy here: instead of marching from 1 to 5, then from 5 back to 1, and so on, we check the current floor against the extreme requested floor in the direction the elevator is heading. If the highest floor requested is 4, the elevator will turn around and come down after 4. If all the suits on the higher floors just want to pop down to the speakeasy on the second floor and 2 is the minimum floor requested, the elevator will turn around and go back up after 2.

I thought the elevator was still acting weird going up to 5, then down to 3, then up to 4, until I realized that, when 4 got requested, 3 was the lowest floor requested. So it wasn’t a glitch: no one had asked to go to floor 1, so the elevator wasn’t going. Adding a request to floor 1 got the elevator to save the request to return to floor 4 until after it had deposited its fifth floor and third floor entrants on the first floor.

Lo and behold, our elevator is movin’ and groovin’, with in-house concurrency and no danger to the integrity of the floor requests data store:

• 

• 

• 

Here’s how the log looks if I remove the statements for the null requests:

Stop requested for floor 5
On floor 2
On floor 3
On floor 4
On floor 5
Stopping at floor 5
Opening doors at floor 5
DOORS CLOSING
Stop requested for floor 3
On floor 4
On floor 3
Stopping at floor 3
Opening doors at floor 3
DOORS CLOSING
Stop requested for floor 1
On floor 2
On floor 1
Stopping at floor 1
Opening doors at floor 1
DOORS CLOSING
Stop requested for floor 4
On floor 2
On floor 3
On floor 4
Stopping at floor 4
Opening doors at floor 4
DOORS CLOSING
Stop requested for floor 2
On floor 3
On floor 2
Stopping at floor 2
Opening doors at floor 2
DOORS CLOSING
Stop requested for floor 1
On floor 1
Stopping at floor 1
Opening doors at floor 1
DOORS CLOSING
Stop requested for floor 5
On floor 2
On floor 3
On floor 4
On floor 5
Stopping at floor 5
Opening doors at floor 5
DOORS CLOSING
Stop requested for floor 4
On floor 4
Stopping at floor 4
Opening doors at floor 4
DOORS CLOSING
Stop requested for floor 4
Stop requested for floor 1
On floor 3
On floor 2
On floor 1
Stopping at floor 1
Opening doors at floor 1
DOORS CLOSING

I’m sure there’s edge cases that this doesn’t address. That’s not really the point of the exercise. The point of the exercise is to explore the use of Python constructs for scheduling concurrent requests that get addressed out of order. Elevators work especially great for this because most folks are familiar with elevators—and that familiarity masquerades as simplicity until you’re waist-deep in the implementation 😈.

We’ll do a similar trick in the next (and I believe, final) installment of the Advanced Programming with Python series. We’re going back to the grade school textbook and adding a twist.

Until then, I leave you with this:

Baker, Cooper, Fletcher, Miller, and Smith live on different floors of an apartment house that contains only five floors. Baker does not live on the top floor. Cooper does not live on the bottom floor. Fletcher does not live on either the top or the bottom floor. Miller lives on a higher floor than does Cooper. Smith does not live on a floor adjacent to Fletcher’s. Fletcher does not live on a floor adjacent to Cooper’s. Where does everyone live?

You’re welcome to solve it. If you do, please take note of how you solve it.

If you liked this piece, you might also like:

The Philosophy of Software Design series

How to Jump-Start a New Programming Language, or maybe, even, gain a more concrete mental model of the one you already use!

Lessons from Space: Edge-Free Programming, which also explores an Android app’s design and the engineering choices behind it (plus, cool pictures of rockets!)