Applications "buying" resources

Hi,

My RTOS has hooks that let the "kernel" ask tasks
(forget how that is defined) to voluntarily shed
resources (time, memory, power).  This lets the
kernel (actually, a "special" user-land task that
makes decisions *for* the kernel) throttle back
the demands placed on the *fixed* resources to
better adjust to the current demands placed on them.

So, if some "new" task needs to be spawned and
needs some resources, the kernel can ask the
currently running set of tasks to relinquish
resources that they may be holding but not *needing*.

But, my current implementation has very coarse
granularity.  In essence, the kernel uses increasingly
harsh tactics to get what it needs:
- "please give up resources"
- "you WILL give up resources"
- "if you won't cooperate, you'll have to go away"
- "die, sucker!"

Of course, if all applications were well behaved, they
would comply with early requests and, hopefully, stave
off the more severe requests that could follow.

But, applications tend to "gamble" -- "maybe someone else
will give up enough resources so I won't have to!"  This
effectively reduces resource management to:
- "please give up resources"
- "die, sucker!"

I can tweak the resources *available* to a particular task.
But, if I use this mechanism to compensate for "uncooperative"
tasks, then it unnecessarily restricts their capabilities...
which makes them *more* inclined to "not cooperate" (as
they *horde* the limited resources that they have!)

What I would like is a scheme whereby applications can decide
how much the resources they are holding are "worth".  And,
then "buy" those resources (with some sort of constrained
"purse").  This gives the "kernel" a bit more flexibility
in handling resource reallocation -- e.g., *it* sets the
current price for the resources and can change that price
dynamically to "entice" tasks to shed resources (by making
it increasingly expensive to hold onto them)

[there are some fairness issues I still need to think through...
e.g., if task A gave up a resource at a pricepoint of K units
and the kernel then raises the pricepoint to L units, should
task A be compensated for his "early sale"?]

Of course, this approach kicks the can down the road a bit
as it now requires me to decide on how much "cash" each
task is given (and if it can vary).

While this seems like a cute idea/model, I wonder if there
isn't a simpler scheme that I could fall back onto?

[remember, my goal is always to NOT have to ask the user
to make these decisions -- especially at the instant the
resource shortage manifests!]

Thanks!
--don

Hi,

My RTOS has hooks that let the "kernel" ask tasks
(forget how that is defined) to voluntarily shed
resources (time, memory, power).  This lets the
kernel (actually, a "special" user-land task that
makes decisions *for* the kernel) throttle back
the demands placed on the *fixed* resources to
better adjust to the current demands placed on them.

So, if some "new" task needs to be spawned and
needs some resources, the kernel can ask the
currently running set of tasks to relinquish
resources that they may be holding but not *needing*.

But, my current implementation has very coarse
granularity.  In essence, the kernel uses increasingly
harsh tactics to get what it needs:
- "please give up resources"
- "you WILL give up resources"
- "if you won't cooperate, you'll have to go away"
- "die, sucker!"

Of course, if all applications were well behaved, they
would comply with early requests and, hopefully, stave
off the more severe requests that could follow.

But, applications tend to "gamble" -- "maybe someone else
will give up enough resources so I won't have to!"  This
effectively reduces resource management to:
- "please give up resources"
- "die, sucker!"

I can tweak the resources *available* to a particular task.
But, if I use this mechanism to compensate for "uncooperative"
tasks, then it unnecessarily restricts their capabilities...
which makes them *more* inclined to "not cooperate" (as
they *horde* the limited resources that they have!)

What I would like is a scheme whereby applications can decide
how much the resources they are holding are "worth".  And,
then "buy" those resources (with some sort of constrained
"purse").  This gives the "kernel" a bit more flexibility
in handling resource reallocation -- e.g., *it* sets the
current price for the resources and can change that price
dynamically to "entice" tasks to shed resources (by making
it increasingly expensive to hold onto them)

[there are some fairness issues I still need to think through...
e.g., if task A gave up a resource at a pricepoint of K units
and the kernel then raises the pricepoint to L units, should
task A be compensated for his "early sale"?]

Of course, this approach kicks the can down the road a bit
as it now requires me to decide on how much "cash" each
task is given (and if it can vary).

While this seems like a cute idea/model, I wonder if there
isn't a simpler scheme that I could fall back onto?

[remember, my goal is always to NOT have to ask the user
to make these decisions -- especially at the instant the
resource shortage manifests!]

Thanks!
--don

On 12/30/2010 1:43 AM, D Yuniskis wrote:

Sorry, reading this I realized it wasn't clear what
I was trying to say <:-(

First of all, note that a task can ignore ANY or ALL
of these "tactics"/requests (except, of course, the
last one :> )

> But, my current implementation has very coarse
> granularity. In essence, the kernel uses increasingly
> harsh tactics to get what it needs:
> - "please give up resources"

The task is asked to shed some particular amount of
some particular resource.  The task can shed any
amount (including none).

> - "you WILL give up resources"

Again, the task is asked to shed some particular amount
of some particular resource.  But, the kernel is now
*expecting* compliance.  The task is still free to
ignore the request (!!!)

> - "if you won't cooperate, you'll have to go away"

The kernel has decided to *take* the resources
from the task -- by sending it a signal to quit.
This gives the task the opportunity to conduct
an orderly shutdown (get its affairs in order).
It is expected to "exit()" when it has done so.

> - "die, sucker!"

The kernel has no more patience and is killing
the task (the task only knows this because it
stops running :> ).  The kernel will reclaim resources
without the task's participation.

The point behind all of these is to allow the
task to use its own criteria for compliance with
each request -- including NONcompliance (some
tasks might really *need* the resources they are
currently holding... not just *want* them).

But, they don't reward good behavior.  And, they
quickly resort to the "big stick" approach...

Hi Arlet,

On 12/30/2010 1:39 AM, Arlet Ottens wrote:
> On Thu, 30 Dec 2010 01:43:56 -0700, D Yuniskis wrote:
>
>> My RTOS has hooks that let the "kernel" ask tasks (forget how that is
>> defined) to voluntarily shed resources (time, memory, power).  This lets
>> the kernel (actually, a "special" user-land task that makes decisions
>> *for* the kernel) throttle back the demands placed on the *fixed*
>> resources to better adjust to the current demands placed on them.
>>
>> So, if some "new" task needs to be spawned and needs some resources, the
>> kernel can ask the currently running set of tasks to relinquish
>> resources that they may be holding but not *needing*.
>>
>> But, my current implementation has very coarse granularity.  In essence,
>> the kernel uses increasingly harsh tactics to get what it needs:
>> - "please give up resources"
>> - "you WILL give up resources"
>> - "if you won't cooperate, you'll have to go away" - "die, sucker!"
>
> Seems overly complicated. Why not simply design the tasks so they'll give
> up any resources they no longer need ?

That's the intent behind the "please give up resources" request.
But, it relies on the task to decide *which* resources it is
going to give up (e.g., maybe it needs this chunk of memory
but not *that* chunk, etc.).

Since each task wants to "look good", they will all *tend*
to hold onto as much as they can get away with -- "maybe someone
else will satisfy the current need".

And, often algorithms trade one resource for another.  E.g.,
give me a bigger chunk of time and I can live with less
memory (or vice versa).

 From the outside (kernel viewpoint), you can't tell what's
important to a particular task.  E.g., when running on AC
power with few competitors, certain tasks might gobble up
*huge* chunks of memory (e.g., many megabytes whereas they
can nominally work with tens of KB) -- this lets them
be more responsive (memory with nothing in it doesn't
save you any power, etc.)

So, I need a "currency" that tasks can use to balance
their "wants" with their "abilities".  So, the information
concerning the relative values of those resources can
remain encapsulated in the task and not exported to
some other "mechanism" for enforcement "from without".

On 30/12/2010 09:39, Arlet Ottens wrote:
> On Thu, 30 Dec 2010 01:43:56 -0700, D Yuniskis wrote:
>
>> Hi,
>>
>> My RTOS has hooks that let the "kernel" ask tasks (forget how that is
>> defined) to voluntarily shed resources (time, memory, power).  This lets
>> the kernel (actually, a "special" user-land task that makes decisions
>> *for* the kernel) throttle back the demands placed on the *fixed*
>> resources to better adjust to the current demands placed on them.
>>
>> So, if some "new" task needs to be spawned and needs some resources, the
>> kernel can ask the currently running set of tasks to relinquish
>> resources that they may be holding but not *needing*.
>>
>> But, my current implementation has very coarse granularity.  In essence,
>> the kernel uses increasingly harsh tactics to get what it needs:
>> - "please give up resources"
>> - "you WILL give up resources"
>> - "if you won't cooperate, you'll have to go away" - "die, sucker!"
>>
>
> Seems overly complicated. Why not simply design the tasks so they'll give
> up any resources they no longer need ?
>

I agree.  The whole idea seems misplaced in an RTOS.  The point of a 
/real time/ operating system is that tasks should do what they have to 
do, within the time (and resource) limits they specify.  Then you put 
them together in a complete system with enough resources to cover all 
needs, with an RTOS that dishes out those resources according to set 
rules, and everyone is happy - every task has sufficient resources to do 
its job.  It is a regimented, military-style organisation with the RTOS 
kernel as the absolute dictator.

This system, however, sounds more like some sort of 70's hippie commune, 
where you think it will all sort of be all right if everyone is nice to 
each other.

Even desktop systems - which don't have real time constraints, and which 
deal which hugely varying loads and programs from all sorts of different 
sources - don't have this sort of complicated mechanism.  Programs get 
the resources they ask for, if the system can supply them.  If there are 
no more resources, they get nothing more.  If the OS runs out of 
resources for critical tasks, it does not ask processes nicely to give 
back resources.  It finds a victim (something low priority, or perhaps a 
memory hog) and asks it to stop itself.  If that fails, it kills it.  No 
ifs and buts, no "please", no messing around with "costs".


Now, just because other RTOS's and non-RT OS's have simpler and clearer 
methods of controlling resources, does not necessarily mean that your 
idea is a bad one.  But you need to do some very careful thinking 
through of realistic use-cases to see what, if anything, this added 
complexity will gain you.

In particular, if you conclude that in the worst case your kernel must 
simply kill the task, then you might as well do that from day 1 - in an 
RTOS, your system has to keep working even in the worst case anyway.  In 
the desktop OS world, it is good to aim for graceful gradual failure 
when things go bad.  In the RTOS world, you aim to guarantee that they 
won't go bad - graceful failure is thus a waste of resources.

On Thu, 30 Dec 2010 02:01:06 -0700, D Yuniskis wrote:

>> Seems overly complicated. Why not simply design the tasks so they'll
>> give up any resources they no longer need ?
> 
> That's the intent behind the "please give up resources" request. But, it
> relies on the task to decide *which* resources it is going to give up
> (e.g., maybe it needs this chunk of memory but not *that* chunk, etc.).
> 
> Since each task wants to "look good", they will all *tend* to hold onto
> as much as they can get away with -- "maybe someone else will satisfy
> the current need".
> 
> And, often algorithms trade one resource for another.  E.g., give me a
> bigger chunk of time and I can live with less memory (or vice versa).
> 
>  From the outside (kernel viewpoint), you can't tell what's
> important to a particular task.  E.g., when running on AC power with few
> competitors, certain tasks might gobble up *huge* chunks of memory
> (e.g., many megabytes whereas they can nominally work with tens of KB)
> -- this lets them be more responsive (memory with nothing in it doesn't
> save you any power, etc.)
> 
> So, I need a "currency" that tasks can use to balance their "wants" with
> their "abilities".  So, the information concerning the relative values
> of those resources can remain encapsulated in the task and not exported
> to some other "mechanism" for enforcement "from without".

How many tasks do you think will be capable of such resource exchange ? 

You could introduce virtual memory, paging, and a filesystem cache, all 
controlled by the kernel, so it can shift resources around dynamically. 

If the set of tasks is reasonably fixed, you can design resource 
partition up-front.

If the set of tasks is wildly variable, under control of the user, you 
could ask the user to set up resource usage on a per-task basis. After 
all, the user knows best what the priorities are. 

On Thu, 30 Dec 2010 01:43:56 -0700, D Yuniskis
<not.going.to.be@seen.com> wrote:

>My RTOS has hooks that let the "kernel" ask tasks
>(forget how that is defined) to voluntarily shed
>resources (time, memory, power).  This lets the
>kernel (actually, a "special" user-land task that
>makes decisions *for* the kernel) throttle back
>the demands placed on the *fixed* resources to
>better adjust to the current demands placed on them.
>
>So, if some "new" task needs to be spawned and
>needs some resources, the kernel can ask the
>currently running set of tasks to relinquish
>resources that they may be holding but not *needing*.

During the last few decades, I have written a few successful control
systems using simple fixed priority real time operating systems
without problems.

The key issue is that any high priority task should use as little
resources as possible. The lowest priority task can use as much
resources it likes.

On Dec 30, 2:43=A0am, D Yuniskis <not.going.to...@seen.com> wrote:
> Hi,
>
> My RTOS has hooks that let the "kernel" ask tasks
> (forget how that is defined) to voluntarily shed
> resources (time, memory, power). =A0This lets the
> kernel (actually, a "special" user-land task that
> makes decisions *for* the kernel) throttle back
> the demands placed on the *fixed* resources to
> better adjust to the current demands placed on them.
>
> So, if some "new" task needs to be spawned and
> needs some resources, the kernel can ask the
> currently running set of tasks to relinquish
> resources that they may be holding but not *needing*.
>
> But, my current implementation has very coarse
> granularity. =A0In essence, the kernel uses increasingly
> harsh tactics to get what it needs:
> - "please give up resources"
> - "you WILL give up resources"
> - "if you won't cooperate, you'll have to go away"
> - "die, sucker!"
>
> Of course, if all applications were well behaved, they
> would comply with early requests and, hopefully, stave
> off the more severe requests that could follow.
>
> But, applications tend to "gamble" -- "maybe someone else
> will give up enough resources so I won't have to!" =A0This
> effectively reduces resource management to:
> - "please give up resources"
> - "die, sucker!"
>
> I can tweak the resources *available* to a particular task.
> But, if I use this mechanism to compensate for "uncooperative"
> tasks, then it unnecessarily restricts their capabilities...
> which makes them *more* inclined to "not cooperate" (as
> they *horde* the limited resources that they have!)
>
> What I would like is a scheme whereby applications can decide
> how much the resources they are holding are "worth". =A0And,
> then "buy" those resources (with some sort of constrained
> "purse"). =A0This gives the "kernel" a bit more flexibility
> in handling resource reallocation -- e.g., *it* sets the
> current price for the resources and can change that price
> dynamically to "entice" tasks to shed resources (by making
> it increasingly expensive to hold onto them)
>
> [there are some fairness issues I still need to think through...
> e.g., if task A gave up a resource at a pricepoint of K units
> and the kernel then raises the pricepoint to L units, should
> task A be compensated for his "early sale"?]
>
> Of course, this approach kicks the can down the road a bit
> as it now requires me to decide on how much "cash" each
> task is given (and if it can vary).
>
> While this seems like a cute idea/model, I wonder if there
> isn't a simpler scheme that I could fall back onto?
>
> [remember, my goal is always to NOT have to ask the user
> to make these decisions -- especially at the instant the
> resource shortage manifests!]


Turning this into an economic problem is certainly an interesting
approach.  In that sense you'd be looking to create markets where
tasks can bid on resources.  The exact units of the cash is not
important, just their relative assignments to the task (IOW, if task 1
is twice as important as task 2, it should get double the budget of
cash units).  Then a task might bid 1/3 of its budget for memory.

Something like a Dutch auction might provide the correct model, but it
would have to be more or less continuous instead of a single event.
IOW, you'd basically need to repeat the auction every time an
additional resource was allocated (or freed).  A Dutch auction is
typically used when you have multiple items for sale (let's say the OS
has one million bytes of memory).  You rank all the bids, and assuming
you have more bids than items, the highest N bids win, and every
bidder is charged the Nth highest bid.  Lets say you have three items
and bids of $1, $2, $3, $4 and $5.  The $3, $4 and $5 bidders get the
three items, and each pays $3.  Usually there's an obvious extension
for bidding on several items (I want M at $x each, which is basically
shorthand for M separate single item bids for $x).  Often there's a
reserve price, below which the items won't be sold (or equivalently
there's a minimum bid).  If there are fewer bidders than items,
usually everyone get the items at either the reserve prices or the
lowest bid.

As the auction progresses, you'd have tasks see their bids drop off
the bottom of the "win" group.  They can then increase their bids,
possibly by allocating more of their budget (and thus freeing
resources elsewhere - which would trigger rebidding in *those*
markets), or possibly by requesting fewer resources (thus being able
to big higher on a unit basis).

Once the bidding stabilizes, everyone gets their allocations, and
things are stable until demand changes.

Hopefully.

With tasks moving budget around multiple markets convergence could be
a real issue if extra constraints were not added.  One thing you could
do would be to *not* allow bidders currently in the provisional "win"
subset to retract their bids - that guarantees any single market
eventually converges (eventually no one can place a higher bid), but
see linked allocations below.  But you must be able to guarantee that
an auction ends (even if another one start right after, an auction
must end, or at least come to a state where the items are doled out
before bidding and reallocation continues).  In the real world this
often happens with a time limit, but that may be difficult to apply.

A problem this ignores is that there may be substantial deallocation
costs - for example, lets say the database task has a million pages
allocated to cache - it can release those, but it's going to have to
do a heck of a lot of work to flush those to disk.  That points out
another issue, freeing up those resources may be slow.  Similarly
processes that cannot bid high enough to continue running typically
would have to abandon the work they've done as they suspend or even
terminate themselves.  These would correspond to externalities in
economics.

Another problem is linked allocations - a task may want N units of
resource A only if it can also get M units of resource B.  If it gets
outbid for resource B, it may want to give up some (or all) of bids on
resource A, even if it's currently a provisional winning bidder for
A.  That too can lead to cycles - dropping the number of units being
bid for A will likely cause the selling price on A to drop, which will
give the task more budget to spend in the next round, and if two tasks
have different demand ratios for A and B (IOW one task wants 2A:1B and
the other 1A:2B), they may spend a lot of time cycling back and forth.

A more complex market would be multiple sellers and multiple buyers,
and you'd have something more like a trading pit on a stock exchange,
but I think convergence gets even hairier there.

I think this would be academically interesting to explore, but far to
complex to use in the real world (or at least in real computer
systems, it obviously *is* used in the *real* world).  Far better to
just assure that your system has sufficient resources, and that a few
resources have big buffers with useful (but not critical) secondary
uses (like memory used for disk caching) that can be throttled
cleanly.  In my experience excessive management of those last few
percent of resources is very hard to do well, and provides very little
gain at the end of the day, for a huge amount of trouble.  Pick a
simple scheme.

One principal I=92ve followed fairly firmly (in far simpler schemes) is
to apply a certain amount of hysteresis to resource allocation
decisions =96 constantly yanking stuff around is not useful.  But doing
that to some general principal is hard, usually you end up with some
fairly arbitrary heuristics.  For example, a system I work on has
worker threads servicing queues of work.  A queue can have zero or
more workers assigned to it, and the assignment is reviewed based on
estimated workloads in the queues, and workers can be added and
removed (the threads use limited resources to process work, and
there=92s a non-trivial cost to starting up and shutting down workers).
In some cases it=92s simple =96 a queue with several workers simply
doesn=92t have enough work, and starts loosing workers (eventually its
last one if the queue is completely idle for long enough).  Or if the
resources are available a queue with more work that its current set of
workers can handle can get more workers assigned without trouble.  But
when things start running short, workers can be taken away from queues
if necessary, (and that=92s broken into two pieces =96 for queues with
work and zero workers, the reassignment process in fairly aggressive,
even, as a last resort, the taking the last worker for a queue still
containing work =96 and a much gentler process for reallocating workers
to queues that are merely overloaded, from queues that are less so,
and that never leaves a queue without workers).  But when the harsher
stuff is happening the system is overloaded, and it=92s typically just
delaying the inevitable.  But getting back to hysteresis, a queue
that=92s been the subject of a management action (basically adding or
removing a worker), is *not* subject to another management action for
a defined interval.

David Brown wrote:
> On 30/12/2010 09:39, Arlet Ottens wrote:
>> On Thu, 30 Dec 2010 01:43:56 -0700, D Yuniskis wrote:
>>> But, my current implementation has very coarse granularity.  In essence,
>>> the kernel uses increasingly harsh tactics to get what it needs:
>>> - "please give up resources"
>>> - "you WILL give up resources"
>>> - "if you won't cooperate, you'll have to go away" - "die, sucker!"
>>
>> Seems overly complicated. Why not simply design the tasks so they'll give
>> up any resources they no longer need ?
> 
> I agree.  The whole idea seems misplaced in an RTOS.  The point of a
> /real time/ operating system is that tasks should do what they have to
> do, within the time (and resource) limits they specify.

Exactly that's what I was thinking. "Real Time" means: given this set of
resources, and this workload, it will work (at all time) or not.

Thus, every task has a set of resources it will always need and never
give up. For everything else, it asks the kernel. "Hey, kernel, if you
have some spare CPU cycles, here's this low-priority job. It helps me to
have it, but I don't need it all the time."

Doing something similar with memory is probably not as easy, but has
been done (e.g. Windows 3.0 "discardable memory"). The problem is that
usually the task has to know that the memory is gone, but you can't let
it clean up for minutes before taking the memory.


  Stefan

On 30.12.2010 09:53, D Yuniskis wrote:

> First of all, note that a task can ignore ANY or ALL
> of these "tactics"/requests (except, of course, the
> last one :> )

That's exactly the problem.  If they can, you have to assume they will. 
  Which renders the entire scheme moot.