I’m curious how railroads and bus companies managed their inventory in the days before real time computerized systems, in order to avoid double bookings. For instance, let’s say the entire route of a Santa Fe train, back in the 1940s, was
L.A. -- Santa Ana -- San Juan Capistrano -- Oceanside -- San Diego
SFRR could sell all the seats to people who were making the entire journey, but presumably that never happened. There would always be people who wanted to travel only between two intermediate stops, say Santa Ana and Oceanside, or between an endpoint and an intermediate station, like from San Juan to San Diego. Presumably it was the same deal for Greyhound, and for that matter, the airlines as well, at least in the early days when the aircraft used could only manage a few hundred miles at a time.
So how did the counter personnel along the line coordinate sales information so that the sales agents in L.A. would know if a block of tickets had been sold between San Juan and Oceanside, and that among other things that would reduce the number of through tickets that could be sold? Enterprise-wide reservation and ticketing systems like SABRE for the airlines were introduced in the early 1960s, and with time the underlying principles have been applied virtually throughout the transport industry. But how did it work in the old days? Would the company merely try to estimate the load to be expected, based on past experience, and hope for the best?
WAG: (Actually not quite; I knew a reservations agent for American back in the '50s and I think this is something like what she said). Each place got a block of seats based on the best guess of demand. When they were sold, I assume that there was some method of trying to find some other site with unsold tickets.
Even after computerization, this problem is non-trivial. You went, say, to a travel agent who tried to put an itinerary together. They would contact the airline’s computer and try to reserve a seat. The computer would temporarily put a hold on a seat for a certain period. If the seat was sold, that was fine, but if not it would have to be released. And if two agents tried at the same time for the last seat? It would have to be resolved somehow, but the programming problem is non-trivial.
Back in the 1970s & 80s I worked for an organisation that booked North Sea and English Channel ferry crossings for holidaymakers, etc. (Well before the Channel Tunnel).
Not my specific department, but the ferry companies’ brochures included tables of all the sailings, etc. and they mailled us weekly updates of which ones were either full, or nearly full. Then someone (occasionally myself) would have to update the master sheets by hand, altering the status of sailings by scoring through or colouring in (I forget which) the ‘phone to confirm’ sailings or blocking out the ‘full’ sailings.
It was a bit cumbersome but worked well enough.
A couple of years before I left, they got a ‘Prestel’ system, which was an early dial-up computer system, which showed realtime booking info and saved you having to colour in the squares!
{ Seat(seatnumber).LOCK=0;
return -1 ;
}
The function of the variable .LOCK is to ensure only this thread/process is writing the record. if it can get the set, it processes payment , and if payment successed, it allocates the seat.
A thead or process that tries to access it at the same time will loop doing a usleep…
When the 2nd thread does get past the while LCOK … usleep, it checks if the the seat is no longer available, and if not, it doesn’t process payment, and reports back about the failure.
If the seat is available, its the first thread in line to access that record … any other thread would be held up at the while (LOCKED) usleep loop…
maybe my code isn’t perfect about covering all cases, but it gives the idea about how a lock operates.
Oops, its probably simpler to use an OS lock… you can define thousands… per program…
The OS will cause a thread that tries to lock an already locked lock , to wait… until its not locked. (its what I got wrong before, I mixed up OS programming and application programming.)
So the first thread to call it gets to run ,take payment and allocate the seat.
But what if the 2nd thread starts doing same just as the first thread starts on the same seat?
Well its held up at the set lock call…
The second thread can only really start on the seat when the first thread has finished…
So then the 2nd thread checks to see if the set is already allocated… ( perhaps for the 10th time, so what ? it can test 100 times…) but it must test before taking payment, and be sure its available, try to take payment once and only once… and if gets payment then take the seat. … hence the lock around testing for the seat and processing payment.
OS_CALL_LOCK(Seats_LOCK);
if ( Seats[seatnumber].available && process_payment (customerID) )
How was it done before computer networks ? probably by telegraph…
Ordinarily, When you sell a ticket ,you telegraph the info into head office inside the next hour (once an hour , for example .)
Then Head office then announce to all officers sectors for which the seats are getting iffy (the definition of iffy depends on how many they expect to sell in the time it takes for stations to telegraph in sales summaries.) , and the ticket sellers must telegraph in a request to get a seat that involves those sectors. Also telegraph in cancellations and no shows immediately.
Having remote memories of purchasing seat reservations at the ticket counter of a small German rail station in the 1970s (IIRRC the clerk phoned the central reservation office, then filled the seat ticket form for the reserved seat out by hand) I always assumed that for several decades before say the 1980s what now is
client software/browser -> Internet -> server software
was
rail station/travel agency/airline counter clerk -> telephone -> clerks at central booking office
These particular wikis are specific to a single company’s history, but they’re a valid outline of how the process evolved at the other carriers as well.
Here’s what came before it for that company: Essentially a boiler room of phone operators where anyone anywhere selling a ticket called the central office and the operator who answered dug into a paper file and updated the inventory.
It was entirely the problem of scaling this from a handful of operators to a hundred operators that drove the need for first a semi-automated and then fully automated system.
There would also have been some slack in the system. There will always be people who miss the train for one reason or another, and even if everyone shows up, it’s not absolutely necessary for everyone to get a seat as in an aeroplane.
Another factor is that it is not too hard to add cars to a train if ticket sales are brisk, so you don’t necessarily have to know that there is a seat available when you sell the ticket. The morning-of the railroad can see how many tickets were sold and assemble the train as required.
Also, WRT railroads, it was, and has been the case fairly recently that you can just climb aboard most trains and the conductor will sell you a ticket on the spot. So they generally don’t run at capacity. I have never heard of railroads canceling trains if they are underbooked.
In the days of dial-up US travel agents used a system called SABRE (sp?) to book airline tickets. Apparently SABRE accounts were either expensive or limited or something. When my boss started our own in-house travel agency in the mid 1990s he bought out an existing (but failing) travel agent just to get their SABRE account.
Now it is, since the concepts have been implemented at a level where the programmer doesn’t have to worry about it. We spent a lot of time in a class I took around 1971 on this problem, studying Dijkstra’s Semaphores.. I don’t know if they teach the guts of this stuff any more.
I think NJ Transit still does this, though there is an extra charge for buying a ticket on the train. It helps that you can sell tickets to people who have to stand.
In the early 1970s the Eastern shuttle between Boston and new York let you buy your seat after boarding. They had a policy of rolling out a new plane if they filled one and people were waiting which was a big selling point.
Or you can very quickly search for the NJ Transit app on your iPhone, download the app, register, add a credit card, and buy your tickets in the time that the conductor kindly walked to the other end of the train.
That was me one afternoon last summer when I went to NY with kids in tow and had to hop on the train as soon as we arrived at the station, with no time to purchase tickets. The app worked nicely.
When I was a kid, they did overbook planes. If they ran out of seats, someone got left behind. And often there were empty seats - the planes I flew on as a kid always had exmpty seats, except when they were overbooked, and someone got left behind.
The military ran a “standby” system. My relatives (army) would just turn up at the airport, and if there were any spare seats, they could fly.
Later on, when I was a teenager, civilian airlines explicitly ran “standby” systems too. That was when their booking systems got good enough that they could predict empty seats, but not good enough (as they now are) that they could sell empty seats by any method other than letting people buy them at the airport.
The last job my father had before he retired from the Army was at Movement Control, RAF Gütersloh. Part of his job was to deal with soldiers who wanted flights back to the UK.
They would often just turn up with their documents, and he would send them off to the NAFFI until he could find them a space. If they were lucky, it would be a seat on a returning Bristol Britannia or Tristar. If not, they might find themselves sitting on a box in the back of a Cargo DC2.
Isilder, you don’t need locks. The computers of that era generally only had 1 processor for a given area of memory space. Since there’s only 1 processor, the computer just iterates through the incoming queue of booking requests, reserving seats as it gets them. If 2 travel agents in different places try to reserve the same seat “at the same time”, in reality one will end up earlier in that queue than another because the code that populates the queue only reads one I/O device at a time. Under no circumstances will it ever actually be simultaneous.
So the “second place” travel agent will get an error message “that seat is already booked” or “that seat is already temporarily booked and may be sold”.
It depends on the application designer and so forth whether or not the error message would be helpful enough to indicate whether the seat was a “firm” booking or just a temporary reservation while some other travel agent elsewhere talks to a customer. Error messages of that time were pretty bad, I guess the generic “booking error” or “error 942, booking fail” was probably more likely…
Locks are something you need if you have 2 processors allowed to work on the same task at once, with both permitted to write to the same memory space at the same time. Which is still not a good idea under this system architecture, because even for the computers of the time, this is not a computationally expensive task, so it’s a bad design to allow 2 processors at all. The multithreading books and examples I’ve seen all find ways to avoid locks as much as feasible as they are terrible.
It’s a specialized topic, but, really, it always has been. Java, for example, has a multithreading library with a built-in semaphore class which is identical to what Dijkstra wrote about. As for the “guts”, that’s inherently hardware-dependent and can be implemented in terms of compare-and-swap opcodes (x86 does this) or LL/SC (load-link/store-conditional) opcodes (the various ARM flavors have these) and probably others.
As for implementing the hardware, that’s more specialized still, and further into EE territory.
Hmmm… I bought train tickets from Naples to Venice in 2001, and there were quite a few people ended up sitting on their luggage in the corridors of the train cars. So another strategy is “[shrug] who cares?”
For the record, that’s not true. Locks are a standard method of resource management in any multitasking or multi-threaded environment. Even the most primitive modern OS will have many simultaneous processes and execution threads even with a single processor. “Simultaneous” simply means they are transparently scheduled by the OS based on events or clock cycles, and constructs like locks, mutexes, and semaphores are a means of coordinating their shared resources so they don’t trample all over each other.