Forums

Applications "buying" resources

Started by D Yuniskis December 30, 2010
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.