Going Up?

A Multi-Threaded Elevator Simulator in Perl

by Sam Tregar
September 04, 2002

Perl 5.8.0 is the first version of Perl with a stable threading implementation. Threading has the potential to change the way we program in Perl, and even the way we think about programming. This article explores Perl's new threading support through a simple toy application - an elevator simulator.

Until now, Perl programmers have had a single mechanism for parallel processing - the venerable fork(). When a program forks, an entirely new process is created. It runs the same code as the parent process, but exists in its own memory space with no access to the parent process' memory. Communication between forked processes is possible but it's not at all convenient, requiring pipes, sockets, shared memory or other clumsy mechanisms.

In contrast, multiple threads exist inside a single process, in the same memory space as the creating thread. This allows threads to communicate much more easily than separate processes. The potential exists for threads to work together in ways that are virtually impossible for normal processes.

Additionally, threads are faster to create and use less memory than full processes (to what degree depends on your operating system). Perl's current threading implementation doesn't do a good job of realizing these gains, but improvements are expected. If you learn to thread now, then you'll be ready to take advantage of the extra speed when it arrives. But even if it never gets here, thread programming is still a lot of fun!

Building a Threading Perl

To get started with threads you'll need to compile Perl 5.8.0 (http://cpan.org/src/stable.tar.gz) with threads enabled. You can do that with this command in the unpacked source directory:

  sh Configure -Dusethreads

Also, it's a good idea to install your thread-capable Perl someplace different than your default install as enabling threading will slow down even nonthreaded programs. To do that, use the -Dprefix argument to configure. You'll also need to tell Configure not to link this new Perl as /usr/bin/perl with -Uinstallusrbinperl. Thus, a good Configure line for configuring a threaded Perl might be:

  sh Configure -Dusethreads -Dprefix=~/myperl -Uinstallusrbinperl

Now you can make and make install. The resulting Perl binary will be ready to run the simulator in Listing 1, so go ahead and give it a try. When you get back, I'll explain how it works.

An Elevator Simulator

The elevator simulator's design was inspired by an assignment from Professor Robert Dewar's class in programming languages at New York University. The objective of that assignment was to learn how to use the threading features of Ada. The requirements are simple:

• Each elevator and each person must be implemented as a separate thread.
• People choose a random floor and ride up to it from the ground floor. They wait there for a set period of time and then ride back down to the ground floor.
• At the end of the simulation, the user receives a report showing the efficiency of the elevator algorithm based on the waiting and riding time of the passengers.
• Basic laws of physics must be respected. No teleporting people allowed!

The class assignment also required students to code a choice of elevator algorithms, but I've left that part as an exercise for the reader. (See how lazy I can get without a grade hanging over my head?)

When you run the simulator you'll see output like:

  $ ./elevator.pl 
  Elevator 0 stopped at floor 0.
  Elevator 1 stopped at floor 0.
  Elevator 2 stopped at floor 0.
  Person 0 waiting on floor 0 for elevator to floor 11.
  Person 0 riding elevator 0 to floor 11.
  Elevator 0 going up to floor 11.
  Person 1 waiting on floor 0 for elevator to floor 1.
  Person 2 waiting on floor 0 for elevator to floor 14.
  Person 2 riding elevator 1 to floor 14.
  Person 1 riding elevator 1 to floor 1.
  Elevator 1 going up to floor 1.

And when the simulation finishes, you'll get some statistics:

  Average Wait Time:   1.62s
  Average Ride Time:   4.43s

  Longest Wait Time:   3.95s
  Longest Ride Time:  10.09s

Perl's Threading Flavor

Related Reading Programming Perl, 3rd Edition By Larry Wall, Tom Christiansen, Jon Orwant Table of Contents Index Sample Chapter Read Online--Safari

Before jumping headlong into the simulator code I would like to introduce you to Perl's particular threading flavor. There are a wide variety of threading models living in the world today - POSIX threads, Java threads, Linux threads, Windows threads, and many more. Perl's threads are none of these; they are of an entirely new variety. This means that you may have to set aside some of your assumptions about how threads work before you can truly grok Perl threads.

Note that Perl's threads are not 5.005 threads. In Perl 5.005 an experimental threading model was created. Now known as 5.005 threads, this system is deprecated and should not be used by new code.

In Perl's threading model, variables are not shared by default unless explicitly marked to be shared. This is important, and also different from most other threading models, so allow me to repeat myself. Unless you mark a variable as shared it will be treated as a private thread-local variable. The downside of this approach is that Perl has to clone all of the nonshared variables each time a new thread is created. This takes memory and time. The upside is that most nonthreaded Perl code will ``just work'' with threads. Since nonthreaded code doesn't declare any shared variables there's no need for locking and little possibility for problems.

Perl's threading model can be described as low-level, particularly compared to the threading models of Java and Ada. Perl offers you the ability to create threads, join them and yield processor time to other threads. For communication between threads you can mark variables as shared, lock shared variables, wait for signals on shared variables, and send signals on shared variables. That's it!

Most higher-level features, like Ada's entries or Java's synchronized methods, can be built on top of these basic features. I expect to see plenty of development happening on CPAN in this direction as more Perl programmers get into threads.

Preamble

Enough abstraction, let's see this stuff work! The elevator simulator in Listing 1 starts with a section of POD documentation describing how to use the program. After that comes a block of use declarations:

  use 5.008;             # 5.8 required for stable threading
  use strict;            # Amen
  use warnings;          # Hallelujah
  use threads;           # pull in threading routines
  use threads::shared;   # and variable sharing routines

The first line makes sure that Perl version 5.8.0 or later is used to run the script. It isn't written use 5.8.0 because that's a syntax error with older Perls and the whole point is to produce a friendly message telling the user to upgrade. The next lines are the obligatory strict and warnings lines that will catch many of the errors to which my fingers are prone.

Next comes the use threads call that tells Perl I'll be using multiple threads. This must come as early as possible in your programs and always before the next line, use threads::shared. The threads::shared module allows variables to be shared between threads, making communication between threads possible.

Finally, GetOpt::Long is used to load parameters from the command line. Once extracted, the parameter values are stored in global variables with names in all caps ($NUM_ELEVATORS, $PEOPLE_FREQ, and so on).

Pages: 1, 2, 3, 4

Next Page