| Author |
Message |
Joe Seigh
Guest
|
 Posted:
Tue Feb 15, 2005 6:26 am Post subject:
Re: Self restarting property of RTOS-How it works? |
|
|
On 14 Feb 2005 21:58:49 GMT, Nick Maclaren <nmm1@cus.cam.ac.uk> wrote:
| Quote: | In article <ud8Qd.57$OU1.45@newssvr21.news.prodigy.com>,
Kelly Hall <khall@acm.org> wrote:
If the system sends too mare cars to a request, the cost is momentary
inconvenience for the passengers of the extra car. If the system sends
too few cars to a request, some people get annoyed.
No, you have got that wrong. If it sends too many, the effect is that
the average waiting time goes up for 'random' use patterns.
Actually, sending two elevators down to the ground floor makes sense. If |
you only send one down, it's coming right back up and you'll have both
elevators at the upper floors again. Send two down, and one stays down
waiting at the ground floor.
--
Joe Seigh
Lock-free synchronization primitives
http://atomic-ptr-plus.sourceforge.net/ |
|
| Back to top |
|
 |
del cecchi
Guest
|
| Posted:
Tue Feb 15, 2005 7:50 am Post subject:
Re: Self restarting property of RTOS-How it works? |
|
|
"Eric P." <eric_pattison@sympaticoREMOVE.ca> wrote in message
news:42113E99.61EAB8B6@sympaticoREMOVE.ca...
| Quote: | Del Cecchi wrote:
Eric P. wrote:
Dunno. I assumed he was not sending idle chars otherwise he
wouldn't
have a problem. SDLC sends a 'flag' value first which should
re-sync
the receiver clock if the link was dead for a while. But I'm not
sure if one flag value is enough to re-sync. A 01111110 results in
a
single transition, with six constant values and another
transition.
This does not seem the best training sequence but maybe good
enough.
Not even close for modern high speed serial links. Re-acquiring
lock
takes a long time.
I can see that it would take a while if you have to completely learn a
frequency because you have to slew the Voltage Controlled Oscillator.
So at power up this might take a few milliseconds.
But if the reference frequency is already correct, or almost correct,
and all you are trying to do it sync to the edge transitions of the
inbound data stream then that seems like it should be very fast.
I'm thinking here of dividing down a 16 or 64 times reference clock,
so it might sync to the edge in 1/16th or 1/64th of a data clock.
Is that too optimistic?
dividing down a clock to sample a 2Gbit line (pci express, fibre |
channel, InfiniBand) or a 3.125 Gbit line (xaui) is typically not done.
Rather the transitions in the data drive a phase detector in a classic
pll. And after a few seconds with no transitions, who knows were the
filter voltage has drifted off to.
| Quote: |
On the other hand, since there is no way for the sender to know
if the receiver is synced, it must use a worst case sequence.
Which means to xmit after being in a quiencent state without
sending idle bytes that it must send some specific (large)
number of idles to give the receiver 1 ms to sync.
Ok, so high speed multi-drop sync lines lines are a bad idea.
|
ya sure you betcha
|
|
| Back to top |
|
|
Ed Beroset
Guest
|
| Posted:
Tue Feb 15, 2005 7:56 am Post subject:
Re: Self restarting property of RTOS-How it works? |
|
|
Joe Seigh wrote:
| Quote: | On Mon, 14 Feb 2005 08:30:54 -0800, glen herrmannsfeldt
gah@ugcs.caltech.edu> wrote:
Every time I am in a building with more than one elevator, press
the button wait a long time and then more than one arrive at the same
time I wonder why they don't use any theory at all in programming them.
Not that I know much about queuing theory, at least I know that
there is a theoretical basis for it. It seems that people in that
business should know something about it.
You mean make the elevator utilization more efficient? They'd sell
less elevators. The people in that business know something about
more elevators or they wouldn't be in business. :)
|
Interestingly, there's an algorithm called the "elevator algorithm"
which is used for position the head assembly on a disk drive.
Basically, the elevator starts wherever it is (naturally!) and goes up,
stopping only at floors where either somebody inside the elevator or
somebody waiting on that floor has pressed the button for that floor.
It goes up to the highest floor for which service was requested and then
uses the same simple algorithm on the way back down. It's not optimal
(in terms of either throughput or wait times), but it's simple to
implement and provides decent performance for non-degenerative cases
(which is to say, real life!) You could calculated maximum wait time
pretty easily, but how would you estimate average wait time?
Ed |
|
| Back to top |
|
|
Guy Macon
Guest
|
|
| Back to top |
|
|
Nick Maclaren
Guest
|
| Posted:
Tue Feb 15, 2005 2:07 pm Post subject:
Re: Self restarting property of RTOS-How it works? |
|
|
In article <opsl7syzh8qm36vk@grunion>, Joe Seigh <jseigh_01@xemaps.com> wrote:
| Quote: | On 14 Feb 2005 21:58:49 GMT, Nick Maclaren <nmm1@cus.cam.ac.uk> wrote:
In article <ud8Qd.57$OU1.45@newssvr21.news.prodigy.com>,
Kelly Hall <khall@acm.org> wrote:
If the system sends too mare cars to a request, the cost is momentary
inconvenience for the passengers of the extra car. If the system sends
too few cars to a request, some people get annoyed.
No, you have got that wrong. If it sends too many, the effect is that
the average waiting time goes up for 'random' use patterns.
Actually, sending two elevators down to the ground floor makes sense. If
you only send one down, it's coming right back up and you'll have both
elevators at the upper floors again. Send two down, and one stays down
waiting at the ground floor.
|
There are circumstances when it makes sense, but you should think that
one through a bit more. Think of a precise, reasonable model (i.e.
one that does not involve the accumulation of people inside the
building) and work it out. Quite subtle differences in the model can
lead to big differences in whether particular naive rules help.
It is a hell of a long time since I looked at this one (and I never
looked at it closely), but I can remember that none of the naive
algorithms are much use in practice. There ARE some good ones, but
even they have problems.
Regards,
Nick Maclaren. |
|
| Back to top |
|
|
CBFalconer
Guest
|
| Posted:
Tue Feb 15, 2005 8:53 pm Post subject:
Re: Self restarting property of RTOS-How it works? |
|
|
Nick Maclaren wrote:
| Quote: | Nick Maclaren <nmm1@cus.cam.ac.uk> wrote:
.... snip ...
Actually, sending two elevators down to the ground floor makes
sense. If you only send one down, it's coming right back up and
you'll have both elevators at the upper floors again. Send two
down, and one stays down waiting at the ground floor.
There are circumstances when it makes sense, but you should think
that one through a bit more. Think of a precise, reasonable model
(i.e. one that does not involve the accumulation of people inside
the building) and work it out. Quite subtle differences in the
model can lead to big differences in whether particular naive
rules help.
It is a hell of a long time since I looked at this one (and I
never looked at it closely), but I can remember that none of the
naive algorithms are much use in practice. There ARE some good
ones, but even they have problems.
|
I would expect better algorithms would await better input methods.
For example, instead of selecting from 'up' or 'down', the
prospective rider could select the destination floor. Now an
arriving car has to display which floors it will handle, and
separate the sheep from the goats. The sheep and goats have to be
sufficiently alert to be separated. Maybe something along the
lines of "take a ticket" based on rfids would work.
--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson |
|
| Back to top |
|
|
Craig Ruff
Guest
|
| Posted:
Tue Feb 15, 2005 9:02 pm Post subject:
Re: Self restarting property of RTOS-How it works? |
|
|
In article <1114jf5fbfah663@corp.supernews.com>,
Tim Wescott <tim@wescottnospamdesign.com> wrote:
| Quote: | CBFalconer wrote:
And I've seen proposals (still in the gee-whiz) stage to have an "up"
shaft, a "down" shaft and a few cross-shafts, with motors in the
elevator cars so they have more autonomy for getting up and down.
|
Sounds like the "Tower of Terror" ride at the MGM Studios park at
Disney World. The elevator "car" seats 12 people or so, and starts
out running vertically. It then switches into a horizontal haunted
house mode of operation before finishing vertically again. Think
of the fun the BOFH would have. He he. :-)
--
Craig Ruff NCAR cruff@ucar.edu
(303) 497-1211 P.O. Box 3000
Boulder, CO 80307 |
|
| Back to top |
|
|
Nick Maclaren
Guest
|
| Posted:
Tue Feb 15, 2005 9:18 pm Post subject:
Re: Self restarting property of RTOS-How it works? |
|
|
In article <4211F82F.3035D23D@yahoo.com>,
CBFalconer <cbfalconer@yahoo.com> writes:
|>
|> I would expect better algorithms would await better input methods.
|> For example, instead of selecting from 'up' or 'down', the
|> prospective rider could select the destination floor. Now an
|> arriving car has to display which floors it will handle, and
|> separate the sheep from the goats. The sheep and goats have to be
|> sufficiently alert to be separated. Maybe something along the
|> lines of "take a ticket" based on rfids would work.
Yes. As with all such issues, a very small amount of extra
information can make a great deal of difference. Similarly,
you could have a special program for rush hours (and the morning
one might be very different from the evening one). What becomes
very clear on a fairly casual inspection is that understanding
the properties of the input data is a prerequisite to designing
good algorithms.
This is very, very relevant to telecommunications and many
aspects of computing, as all experts in the relevant aspects know
very well. I know just enough to have a glimmering of the depths
of my ignorance :-)
Regards,
Nick Maclaren. |
|
| Back to top |
|
|
Charles Krug
Guest
|
| Posted:
Tue Feb 15, 2005 9:59 pm Post subject:
Re: Self restarting property of RTOS-How it works? |
|
|
On Tue, 15 Feb 2005 15:53:03 GMT, CBFalconer <cbfalconer@yahoo.com> wrote:
| Quote: | Nick Maclaren wrote:
Nick Maclaren <nmm1@cus.cam.ac.uk> wrote:
... snip ...
I would expect better algorithms would await better input methods.
For example, instead of selecting from 'up' or 'down', the
prospective rider could select the destination floor. Now an
arriving car has to display which floors it will handle, and
separate the sheep from the goats. The sheep and goats have to be
sufficiently alert to be separated. Maybe something along the
lines of "take a ticket" based on rfids would work.
|
When we were younger, we stayed in a hotel in San Juan where the
elevators went to floors in the order the buttons were pressed, without
regard for proximity.
Not sure who came up with that brilliant idea.
You might imagine that a clever 10yo boy made certain that the
elevator's path was the most convoluted possible. My sisters weren't
much better. |
|
| Back to top |
|
|
Stephen Fuld
Guest
|
| Posted:
Tue Feb 15, 2005 10:07 pm Post subject:
Re: Self restarting property of RTOS-How it works? |
|
|
"Nick Maclaren" <nmm1@cus.cam.ac.uk> wrote in message
news:cut7cl$c0o$1@gemini.csx.cam.ac.uk...
| Quote: |
In article <4211F82F.3035D23D@yahoo.com>,
CBFalconer <cbfalconer@yahoo.com> writes:
|
|> I would expect better algorithms would await better input methods.
|> For example, instead of selecting from 'up' or 'down', the
|> prospective rider could select the destination floor. Now an
|> arriving car has to display which floors it will handle, and
|> separate the sheep from the goats. The sheep and goats have to be
|> sufficiently alert to be separated. Maybe something along the
|> lines of "take a ticket" based on rfids would work.
Yes. As with all such issues, a very small amount of extra
information can make a great deal of difference.
|
The key word here is "can". In thinking about this particular possibility,
it seems the big advantage would be if one could have multiple elevators
where one would service the "higher" floors and one the "lower". Then the
people going to the higher ones wouldn't have to wait for all the stops in
the lower ones. This is probably only usefull for fairly tall buildings.
In fact, for such buildings, something like this is frequently done. I have
been in buildings with multiple banks of elevators each clearly labeled with
the range of floors they service. While this doesn't have the flexibility
of being able to change the floors serviced dynamically, it avoids the need
for dynamic "sheep/goat separation", (with presumably a higher mistake rate
than a static system) as described above.
| Quote: | Similarly,
you could have a special program for rush hours (and the morning
one might be very different from the evening one).
|
I think this is pretty standard for tall buildings.
| Quote: | What becomes
very clear on a fairly casual inspection is that understanding
the properties of the input data is a prerequisite to designing
good algorithms.
|
Absolutely. And, since the elevator companies have been at this for
something like a century now, the have worked out an awful lot of the "best
practices".
| Quote: | This is very, very relevant to telecommunications and many
aspects of computing, as all experts in the relevant aspects know
very well.
|
Absolutely.
| Quote: | I know just enough to have a glimmering of the depths
of my ignorance :-)
|
Me too. :-)
--
- Stephen Fuld
e-mail address disguised to prevent spam |
|
| Back to top |
|
|
Nick Maclaren
Guest
|
| Posted:
Tue Feb 15, 2005 10:22 pm Post subject:
Re: Self restarting property of RTOS-How it works? |
|
|
In article <DTpQd.41806$Th1.2595@bgtnsc04-news.ops.worldnet.att.net>,
Charles Krug <cdkrug@worldnet.att.net> writes:
|>
|> When we were younger, we stayed in a hotel in San Juan where the
|> elevators went to floors in the order the buttons were pressed, without
|> regard for proximity.
|>
|> Not sure who came up with that brilliant idea.
|>
|> You might imagine that a clever 10yo boy made certain that the
|> elevator's path was the most convoluted possible. My sisters weren't
|> much better.
Could you overload its memory?
Until recently, we had a lift that used to pass a floor where the
light was lit (for, say, down) heading downwards. It would then
go back up, back down again, still omitting that floor and then
eventually come back UP to the floor.
I eventually found out that it was a data dependent bug. Under
certain unidentified (demand dependent) circumstances, it would
light the light but either not register the request or lose it
from its memory. It wasn't until someone wanted to get out at
that floor (always from below, for irrelevant reasons) that the
people waiting could get on. Repressing the button didn't help,
as it did nothing because it was already registered (locally).
Most versions of TCP/IP have some bugs with very similar
properties, which makes me feel very happy when people plan to
build it into safety-critical designs. So do the signalling and
process killing primitives on many systems, and so of course did
the inimitable IBM 2741.
There really is an awful lot in common between apparently very
different devices and solutions.
Regards,
Nick Maclaren. |
|
| Back to top |
|
|
Guest
|
| Posted:
Tue Feb 15, 2005 10:43 pm Post subject:
Re: Self restarting property of RTOS-How it works? |
|
|
Charles Krug wrote:
| Quote: | On Tue, 15 Feb 2005 15:53:03 GMT, CBFalconer <cbfalconer@yahoo.com
wrote:
When we were younger, we stayed in a hotel in San Juan where the
elevators went to floors in the order the buttons were pressed,
without
regard for proximity.
Not sure who came up with that brilliant idea.
You might imagine that a clever 10yo boy made certain that the
elevator's path was the most convoluted possible. My sisters weren't
much better.
|
they obviously never heard of the elevator disk arm scheduling
algorithm |
|
| Back to top |
|
|
Ketil Malde
Guest
|
| Posted:
Tue Feb 15, 2005 10:48 pm Post subject:
Re: Self restarting property of RTOS-How it works? |
|
|
nmm1@cus.cam.ac.uk (Nick Maclaren) writes:
| Quote: | In article <DTpQd.41806$Th1.2595@bgtnsc04-news.ops.worldnet.att.net>,
Charles Krug <cdkrug@worldnet.att.net> writes:
When we were younger, we stayed in a hotel in San Juan where the
elevators went to floors in the order the buttons were pressed, without
regard for proximity.
[...]
Until recently, we had a lift that used to pass a floor where the
light was lit (for, say, down) heading downwards. It would then
go back up, back down again, still omitting that floor and then
eventually come back UP to the floor.
|
Sigh. Those damned C.S. majors seem to be *everywhere* these days.
:-)
-kzm
--
If I haven't seen further, it is by standing in the footprints of giants |
|
| Back to top |
|
|
CBFalconer
Guest
|
| Posted:
Tue Feb 15, 2005 11:50 pm Post subject:
Re: Self restarting property of RTOS-How it works? |
|
|
Stephen Fuld wrote:
| Quote: | "Nick Maclaren" <nmm1@cus.cam.ac.uk> wrote in message
CBFalconer <cbfalconer@yahoo.com> writes:
I would expect better algorithms would await better input methods.
For example, instead of selecting from 'up' or 'down', the
prospective rider could select the destination floor. Now an
arriving car has to display which floors it will handle, and
separate the sheep from the goats. The sheep and goats have to be
sufficiently alert to be separated. Maybe something along the
lines of "take a ticket" based on rfids would work.
Yes. As with all such issues, a very small amount of extra
information can make a great deal of difference.
The key word here is "can". In thinking about this particular
possibility, it seems the big advantage would be if one could have
multiple elevators where one would service the "higher" floors and
one the "lower". Then the people going to the higher ones wouldn't
have to wait for all the stops in the lower ones. This is probably
only usefull for fairly tall buildings. In fact, for such
buildings, something like this is frequently done. I have been in
buildings with multiple banks of elevators each clearly labeled
with the range of floors they service. While this doesn't have the
flexibility of being able to change the floors serviced
dynamically, it avoids the need for dynamic "sheep/goat
separation", (with presumably a higher mistake rate than a static
system) as described above.
|
Already done, in the tall buildings. There the problem is to
conserve elevator shaft space. Works something like airline hubs
and feeder lines.
--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson |
|
| Back to top |
|
|
Tim Wescott
Guest
|
| Posted:
Wed Feb 16, 2005 12:30 am Post subject:
Re: Self restarting property of RTOS-How it works? |
|
|
CBFalconer wrote:
| Quote: |
Already done, in the tall buildings. There the problem is to
conserve elevator shaft space. Works something like airline hubs
and feeder lines.
And I've seen proposals (still in the gee-whiz) stage to have an "up" |
shaft, a "down" shaft and a few cross-shafts, with motors in the
elevator cars so they have more autonomy for getting up and down.
It was a popular science kind of thing -- I have no idea if it's being
seriously developed (but it'd be fun to do the software!).
--
Tim Wescott
Wescott Design Services
http://www.wescottdesign.com |
|
| Back to top |
|
|
|
|
|
|
FAQ
Memberlist
Register
Profile
Log in to check your private messages
Log in