Cutting Queues at
a barber shop

A SIMULATION

of course, go no further. This enables the screen to be used simply as text and places no FORTH syntactical constraints on you.

  When the page is completed there is a choice of things you can do. You can edit it by insertion and deletion. If what you have produced are FORTH definitions, and you want to put them on disc, then CONTRL-E does that. To put them into dictionary for running a programme you type 42 LOAD, and this will take your programme off disc into the buffer and then into dictionary. There are control commands for missing out the disc-save, if you just want to try out your definitions to see if they work. If they don't you will get error messages and can go back to screen for editing. When you've got it right you can save on disc. If what you have put in dictionary is of a sufficiently global nature so that you feel you will want it available in most future programmes - for example, arithmetic routines or display-mode routines such as INVERSE or FLASH - then SAVESYSTEM will put the current dictionary in compiled form on to disc; either this one, or any other that has been initiated.

  At any time (unless you are in EDIT, mode) you can put out the displayed text to printer by CNTRL-P which opens the printer, prints out, and closes it again. This has the advantage of not printing irrelevancies such as LIST. Furthermore, the printer is off at the end, which is something I usually forget to do.

  An important advantage of the 1.7 version over the 1.5 I was using previously is the FORTH Assembler. This enables you to define words using the 6502 mnemonics. Words so defined may be entered into dictionary and used in other definitions just as any other FORTH words

   Here is a simple example of a programme to find the larger of the contents of two memory locations and to store the result The locations are 40 and 41 (HEX) and the result is stored in 42.

  Fig 1 shows the conventional assembler listing, (excluding symbol tables and the like), containing a'single branch.

The discussion which follows has been inspired by a book the author was given to review. A FORTH tutorial series appeared in earlier issues.

The news this month is that I have been experimenting with a new version of FORTH namely FIG FORTH 1.7. FIG stands for FORTH Interest Group (Computer Age, July, 1980). V 1.7 is based very closely on the new FIG model and is a fully disc-based system. It is designed to run on Apple II but does not use the normal BASIC-oriented DOS. Any disc can be initialised and formatted by means of the disc supplied. It formats into "screens" of 1024 bytes each, and in the standard system there are about 60 such screens available to the user for programmes.

   The disc is then acting as virtual memory. If you are not used to BASIC this, represents more disc space then it would appear since all screens are available to all others. In FORTH, where programmes consist of defined words, any words previously defined may be used in the current programme by first loading the screen on which they appear into the dictionary. A command to do this can be written on the current screen and a very powerful editor is available when writing screens in the EDIT mode.

   On this version variable names and FORTH words can be any combination of symbols up to 63 in number; and all symbols count. There is no time-penalty for this. So the procedure is this. You first

( SCREEN 70 CONVENTIAL ASSEMBLER )

       LDA  $40
       CMP  $41
       BCS  LARGER
       LDR  $41
LARGER STA  $42
       BRK

Fig. 1

( SCREEN 71 FORTH ASSEMBLER )
( FINDS AND STORES LARGER OF THE )
( CONTENTS OF TWO LOCATIONS )

HEX
CODE

FIND   40 LDA,
       41 CMP, CS NOT IF. (CARRY NOT?)
       41 LDA, ENDIF,
     NEXT JMP,
     END CODE

Fig. 2

EXAMPLE OF THE USE OF 'FIND'


    3F 40 C!  28 41 C!
    FIND
    42 C@ . 3F OK


    3F 40 C! A8 41 C!
    FIND
    42 C@ . A8 OK

Fig. 3

Fig 2 is the FORTH assembler in which the word FIND is defined. Typing FIND executes the programme.

Now here is the programme in action (Fig 3). The number 3F is first stored in location 40 as a single byte and 2B is stored in 41. Then FIND is executed and the contents of 42 are examined and tum out to be, as expected, 3F. The second example is one in which the larger number is in 41, namely A8.

You will notice the use of IF, ENDIT, in the FORTH Assembler, There is a large number of such structures available; these enable the proper use of structured assembler programming. In fact, except by the use of low cunning, you can't write unstructured assembler programmes. There is no need to use the particular format shown. I wrote it like that for clarity. You needn't't write in HEX either if you prefer not to. NEXT JMP,is a re-entry to FORTH and END-CODE is the terminator.

I intend to include an article on the assembler in a later issue, and will also enlarge on the merits of the 1.7 version. 4

A book review

I have been reading a new book on simulation, and the rest of this article is a review of it together with a FORTH programme to solve one of the simulation problems included in the book. There is an interesting and stimulating foreword by Gerald Weinberg, who is general editor of the series, (see later part of the article), issuing

a warning on the misuse and abuse of simulation as a technique for solving real problems. I would like to add some of my own. The problem "solved" here in FORTH is the problem as posed in the book.

  It is an elementary queuing problem. A single queue of the first-come first-served variety (FIFO) with a single server. For realism the server is a barber and the queue is his customers. The factors we are asked to take into account are:

1 Customers arrive with the Poissonian distribution at the average rate of five per hour ("Poissonian" will imply that whilst arrivals are random the expected number in "any time interval is proportional to the length of that interval).

2 The barber shaves at an average rate of four per hour with a negative exponential distribution.

3 A number of chairs is provided for the convenience of waiting customers. If the chairs are all full it is assumed the new arrival doesn't stay

( SCREEN 42 BARBSHOP FIRST )
45 LOAD
0 VARIABLE Q 0 VARIABLE SHAVETIME
0 VARIABLE CHAIRS
0 VARIABLE SUMSHAVE 0 VARIABLE CUSTOMERS
: QFULL? @ CHAIRS @ = ;
: QOK? Q @ 0 > ;
: INC 1 SWAP +! ;
: DEC -1 SWAP +! ;
: STARTSHAVE 1 SHAVETIME ! Q DEC
  SHAVES INC ;
: STOP 0 SHAVETIME ! ;
: IDLE? SHAVETIME @ 0 = ;
: STARTDRY 0 SHAVES ! 0 ARRIVALS ! 0 Q !
  0 SHAVETIME ! ;
: HEADER HOME CHAIRS @ . ." CHAIRS"
  CR ." ARRIVALS " ." SHAVES ". " QUEUE "
   CR ;
: FINISHED? RGET 17 < ;
: CUSTOMER? RGET 21 < ;
    43 LOAD 44 LOAD

( SCREEN 43 BARBSHOP  )
: BARBSHOP 480 0 ( MINS/DAY )
  DO
    IDLE?              ( NOT SHAVING )
     IF QOK? RANDOM
      IF STARTSHAVE    ( GET CRACKING )
      ENDIF
     ELSE FINISHED?    ( DOES THE ROULETTE )
       IF STOP     ( WHEEL SAY 'TIME'S UP? )
       ENDIF
     ENDIF
    CUSTOMER?    (THE WHEEL SAYS 'ARRIVAL' )
     IF ARRIVALS INC QFULL? NOT
       IF Q INC              ( TAKE A SEAT )
     ENDIF
    ENDIF
  LOOP ;

: SHOW ARRIVALS @ 4 .R SHAVES @ 10 .R
  Q @ 7 .R CR ;

( SCREEN 44 BARBSHOP  )
: START INIT 1000 0 DO RANDOM  LOOP ;
: 15DAYS 0 SUMSHAVE ! 0 CUSTOMERS !
 CHAIRS @ . ." CHAIRS" CR HEADER
   15 0 DO BARBSHOP SHOW ARRIVALS @
   CUSTOMERS +! SHAVES @ Q @ +
   SUMSHAVE =!
LOOP CR
 ." SUCCESS RATE = "
2 SUMSHAVE @ CUSTOMERS @ AB/ 6 SPACES ;
: SAMEAGAIN START 15DAYS ;

Fig 6.

4 The remaining queue is served when the shop closes at the end of the day.

The programme is an analysis of the problem as posed.

  Before the simulation is carried out, let’s look into the realism of the model. The most unrealistic feature is the suggestion that the waiting queue is served at the end of the day. The actual question suggested ten chairs are provided. This is two and a half hours work at the end if the queue is full! You will see from the result of the simulation that it often is. We might consider varying the time of closing shop depending on an estimated time to finish the queue. Further refinements could be a probability that an arrival would stay dependent on the existing queue length, and the probability that a seated customer would remain longer than a stated time if not served in that time. All these considerations are to some extent quantifiable even to the inclusion of a television set to induce arrivals to remain! (Although how many would leave, served or not, when Match-of-the-Day finished is another question).

  Perhaps these questions are not retevant to abstract queing theory but they are to real-life queue practice. 1 know of a canteen in which a firm of consultants instituted a system of parallel queues. You chose your queue by studying a displayed menu before entering. Some of the problems which arose were as follows:

• If your chosen menu was "off" before you reached the counter what was the ethics of queue changing?
• To get out of your queue when served you had to break through several others with a 4 tray full of spillable goodies to get to the pay desk.
• You are in the queue for steak-and-chips or steak-and-mashed. The queue has ground to a halt because chips are off. You don't want chips. How do you get the message (except by bitter experience or you do want chips but will settle for mashed if it means too long a await...?

What has all this rubbish got to do with mathematics? Let's get back to abstract queuing theory where life is relatively simple. The BARSHOP programme is here displayed on 3 screens starting at 42. This screen starts by the command to load 45, which is an arithmetic routine for evaluating the answer at the end. Then, certain necessary variables are defined and initialised to zero.

  The variable SUMSHAVE and CUSTOMERS are the totals of those served and those arriving, in a 15-days period of 480 mins/day. I think the rest of the variables are self-explanatory

  The word QFULL? asks if the number in the queue equals the number of supplied chairs.

  QOK? asks if there is anyone waiting to be shaved (a question necessary if the barber is idle)

  FINISHED? gets a random number out of 255 and compares it with 17. This is expected to be true 1/15 times, i.e, four times per sixty minutes, if each throw represents a minute of lapsed time.

  CUSTOMER? will be true five times in sixty minutes on the average.

  Screen 43 is the main BARSHOP programme of 480 loops each representing, one minute of the working day.

  The word RANDOM after QOK? requires explanation. It is simply a dummy random number which is thrown and not used in the event of the queue being empty. This is simply

Fig.7

to ensure that precisely the same set of random numbers is thrown from the same seed whichever branch of the conditionals is taken. This is thought by some to be a good thing. I doubt it, but conform to majority decision

  The final screen 44 works by typing

SAMEAGAIN which will always do a 15 day run from the same initial seed. However, ISDAYS will do a run from the seed you are left with so the scatter on resulfs may be evaluated. The word START initialises the random number and runs off 1000 of them to

stir things up (but in an entirely reproducible way). Notice that screen 42 contains instructions to load the others. :

  Figs 7 and 8 show the effect of using the same random number seed (SAMEAGAIN) in. different situations. The same daily arrival pattern recurs.

  Fig 9 repeats the ten-chair case with a new seed, and so quite a different pattern of arrivals. There is, however, little change in the final result - which shows the reliability of the Monte Carlo method Since the barber shaves customers, on the average, at a slower rate than they arrive, he is seldom faced with an empty queue, so the number he gets through before the shop closes is little dependent on the number of chairs. If you simply take into account only those shaved in the 480- minute day, the success rates for the two- chair and ten-chair cases are 0.66 and 0.71 respectively, so that most of the advantage stems from the captives at the end of the day. This requires an average of one and a half hours a day extra work. Fig 10 is a flow-chart of the problem

The problem was taken from:

Simulation: Principles and Methods
Authors: Wayneand Pooch
Publisher:   Prentice-Hall (Winthrop Computer Systems)
Pages   250
Price     £12.95

The book is a clear presentation of all the usual methods and techniques and doesn't include too much mathematical proof. For example, the various statistical distributions and their uses are presented as statements of fact, but the reasons for the choice of one rather than another are always made clear. Problems are present- ed (of which one has been treated above); the reader is asked to write programmes in general-purpose languages such as FORTRAN ot PL/I and in a number of special- purpose languages, the structures of which are discussed in some detail. There is also a chapter on continuous-system simulation and analogue computing.

  A worthwhile book, even if the presentation is somewhat ad hoc in places.

  FORTH ver. 1.7 is at present available from: Cap'n Software, P O Box 575, San Francisco, CA 94101.

  The version is expected to be available from Personal Computers Ltd. 194 Bishopsgate, London EC2