Minimalist Microkernel Memory Management

[gaf]

I've adapted my example to the equal share scenario:

[pre][scheduler - version: 1.0]

class drivers
{
cpu: 80%

capability: GID 0x0012

quantum_min: 1 TS
quantum_max: 3 TS
}

class groups
{
cpu: 20%
}

class groups::profs
{
cpu: 50%

capability: GID 0x2340

quantum_min: 2 TS
quantum_max: 6 TS
}

class groups::students
{
cpu: 50%

capability: GID 0x0000

quantum_min: 2 TS
quantum_max: 6 TS
}[/pre]

[*]The script says that 80% of the CPU time may be used by drivers which are identified by their GID. If they don't make use of all the time (they normally won't..) the rest is of course given to the groups.
[*]Groups are allowed to run for at least 20% of the time, but normally they'll get more as the drivers aren't that buisy
[*]The class "groups" is just a place holder and can't be used to schedule a task as it doesn't define any capablities
[*]The system supports two groups that can be used by the apps to start a task. "Profs" can only be used by authorized persons (dean, profs) and the apps running in this group get 50% of whatever the drivers left over. The other group ("students") is open for all and gets the other half of the remaining time.
[*]The dean can now claim that the system is perfectly fair, but as there are much more students than profs their programms will execute somewhat slower

[pre]
Some scenarios with this script file:

1) drivers very busy:
drv: 80%, groups: 20% -> profs: 10% + students: 10%

2) all drivers waiting for data:
drivers: 0%, groups: 100% -> profs: 50% + students: 50%

3) drivers idle, 1 prof runs 4 tasks, 10 students run 20 tasks:
drivers: 0%, prof: 4*12.5%, students: 20*2.5%

4) drivers idle, no profs
drivers: 0%, profs: 0%, students: 100%
[/pre]

My usual sources come up short when looking into "upcalls" and "scheduler activations".

IIRC "upcall" simply means that the kernel switches to a user-space app to give it the chance to react to some event (eg: revocation of pages, end of timeslice)

regards,
gaf

[QuiTeVexat]

In my opinion the approach taken in Aegis leads to problems as soon as there is more than one scheduling policy present becaues the "value" of time-slices that applications can allocate changes when new apps are added or old finish their work.

Eh? The only way there's more than one policy present is if there are some userland schedulers running, in which case they have clearly defined timeslices over which they have control.

As an example let's have a look at a simple equal share system in which two users are present and both are entitled to get 50% of the CPU, no matter how many apps are running. In the beginning both users are running one app. If any of them now starts a second task he'll get twice as much as the other and the whole system has to be rebalanced to meet the policy again. The same problem occures if apps quit or are only blocked (!) and it gets even worse when apps are allowed to choose how many time-slices they want..

How so? Say User A's app has 50% of the timeslices and User B's app has the other 50%. When User A starts a new app, his old app donates timeslice to the new app. Say this is 20% of the total timeslices. User A's first app has 30%, his second app 20%, and User B is still getting his full 50% in his one and only app.

If an app quits, the timeslices that were in use could be freed, or the app could have donated its timeslice to another before termination (maybe my editor donates the timeslice it was given back to my shell). If a app was blocked, it would probably be set to automatically yield to some other app until it was reactivated.

Maybe I'm just misunderstanding you.

[gaf]

How so? Say User A's app has 50% of the timeslices and User B's app has the other 50%.

You say that both users have 50% of the time-slices, but how much is that actually: 10, 100, 1000, 10000 ? Since both may start a large number of apps and each of these apps may use several time-slices you'd have to chose a very high number to represent 100% - otherwise one of the users might simply run out of them. Apart from that the "swapping" that has to be done when a new app is started or and old finishes grows bigger with every new task..

When User A starts a new app, his old app donates timeslice to the new app. Say this is 20% of the total timeslices. User A's first app has 30%, his second app 20%, and User B is still getting his full 50% in his one and only app.

And what happends if UserA's first app blocks ? Since there's nothing that enforces the equal share policy the time-slices connected with this app will simply be skipped so that the CPU time is effectivly divided among both of the task: UserA's second app now gets 28.6% and UserB's app 71.4%, although the policies says that it has to be 50%|50%..

I wouldn't say that it's impossible, but I do think that the usage of absolute values causes problems that are actually easy to avoid with a percentages based system.

regards,
gaf

[Colonel Kernel]

And what happends if UserA's first app blocks ? Since there's nothing that enforces the equal share policy the time-slices connected with this app will simply be skipped so that the CPU time is effectivly divided among both of the task: UserA's second app now gets 28.6% and UserB's app 71.4%, although the policies says that it has to be 50%|50%..

When A's first app blocks, wouldn't that user's scheduler just give the remaining time to A's second app...? Or am I missing something here?

[QuiTeVexat]

It doesn't matter so much how many apps are in the system so much as how many apps are going to be running at any given time. At any given time, chances are, most tasks are sitting around doing nothing. Tasks that are sitting around doing nothing need no timeslice. It seems to me you'll have trouble overrunning 1000 or so slices.

If you find you need more timeslices, increase the number. If you want to do this at runtime, increase by some multiple and expand the current slices to take up the proportions they should.


If UserA's first app blocks, it would block donating timeslice to the second app. The second app now has 50% of the processor time, the first 0% (until it awakens), and UserB's app 50%. I don't see how you end up with 28.6% and 71.4%.

Of course, all that was assuming that those users are actually allocating and using their full timeslice quotas. More likely, their apps will release slices they don't need. This isn't much different than in a typical abstractionful OS. I can write a busy-waiting, excessively-looping CPU-bound memory hog just as well in there as I can here. I don't because it would be a busy-waiting, excessively-looping CPU-bound memory hog. To prevent abuse in multi-user systems, use priorities and quotas.

Pax tecum,
Qui te vexat.

[gaf]

When A's first app blocks, wouldn't that user's scheduler just give the remaining time to A's second app...? Or am I missing something here?

That's of course also a possiblity, but it requires switching to the user-level scheduler which should be avoided - at least as long as the problem can also be solved directly in the kernel.

At any given time, chances are, most tasks are sitting around doing nothing.

I actually thought about giving time-slices to all tasks and simply skip those that are blocked. Keeping a list of ready tasks only is of course also possible, but it means that the time-slices have to be updated every single time a task blocks or unblocks, which happens all the time. I've tried to find out how this is actually done in Xok, but scheduling doesn't seem to be very well documented..

If UserA's first app blocks, it would block donating timeslice to the second app. The second app now has 50% of the processor time, the first 0% (until it awakens), and UserB's app 50%.

This might work with two tasks, but what if we have more than that, let's say ten ? In that case the first app would have to divide the quantum by nine and give the pieces to the other tasks. Chances are however that the number of timeslices A holds is either too small or not a multiple of 9, so that you'd end up with something like 7/3 timeslices. One could solve this problem by just assigning 2 time-slices to each and simply not using the rest, but this only works globally and not in a equal-share system.
This means a task always has to donate its time-slices to somebody specific, which isn't always possible. The best example is probably a driver that has just finished sending a request for 5 sectors to the disk and now wants to go idle until the data comes in. To which task should it give the time-slice ? It of course has to be one from the same group, but how does it know with which tasks it shares the group ? This problem could be only be solved by calling the user-level scheduler and asking it to assign the quantum to any task of the group at random, but that not really the idea of multiplexing..

Similiar problems arise if you want to build a priority based round robin system. Here too the user-space scheduler has to be called all the time although the problem could also be solved in the kernel, if it supported some kind of priority levels. Using lottery scheduling priorities can be simulated in a very elegant way that doesn't require any intervention by an external scheduler at all.

I personally think that the Aegis approach for scheduling is a bit too low-level and doesn't really ensure multiplexing, which therefore has to take place in user-level managers. This however leads to new problems as the API then is no longer dependant on the kernel and any external scheduler will mix multiplexing with a specific abstraction. Such a design would be typical for a ?-kernel, but an exokernel should really seek to avoid it..

I don't see how you end up with 28.6% and 71.4%

I just assumed that the time-slices the first app held were rather skipped than donated. This would mean that the remaining values (20%, 50%) have to be normalized so that they sum up to 100% again.

regards,
gaf

[Colonel Kernel]

Here's a paper (PDF) on user-level scheduling... It's the only one I've read so far actually. Still not sure if what they propose is a good idea.

About upcalls... I understand their purpose, I just can't visualize how they're implemented yet. Is it like unblocking a thread in user-space, or running a procedure in some arbitrary user-space thread's context (ala signals and NT APCs)...?

[QuiTeVexat]

When A's first app blocks, wouldn't that user's scheduler just give the remaining time to A's second app...? Or am I missing something here?

That's of course also a possiblity, but it requires switching to the user-level scheduler which should be avoided - at least as long as the problem can also be solved directly in the kernel.

The kernel could allow for a block-donating-to-X, in which case the user-land scheduler could be avoided, which I agree is preferable.

This means a task always has to donate its time-slices to somebody specific, which isn't always possible. The best example is probably a driver that has just finished sending a request for 5 sectors to the disk and now wants to go idle until the data comes in. To which task should it give the time-slice ?

None in particular. When it begins waiting it frees the slices it's no longer using. Since it is a high priority task, when the data comes in, it will be awakened and given a chance to execute. It will immediately grab up any timeslices it needs, and the kernel will allow this because the task has the priority.

That was one idea. The problem I see with that is it requires that tasks be preemptable from allocated timeslice, which bothers me since applications could be relying on the allocated timeslice for realtime/deadline sort of things. So I was/am/will be playing around with ideas on how to resolve that.

I was thinking of perhaps some sort of protest mechanism combined with a minimum guarantee of resources. But I dunno. This is all a work in progress, of course.

Similiar problems arise if you want to build a priority based round robin system. Here too the user-space scheduler has to be called all the time although the problem could also be solved in the kernel, if it supported some kind of priority levels. Using lottery scheduling priorities can be simulated in a very elegant way that doesn't require any intervention by an external scheduler at all.

I think that priorities are a good idea. I'm rather hesitant though in an exokernel to take away the control that CPU-time-as-a-linear-vector gives to applications.

By the way, has anyone noticed how *way* off topic this is?

Pax tecum,
Qui te vexat.

[gaf]

The kernel could allow for a block-donating-to-X, in which case the user-land scheduler could be avoided, which I agree is preferable.

This could be integrated into the messaging system easily: If a task blocks after having sent a message, its time-slice is donated to the called task. A task that doesn't block due to IPC won't fancy a specific task anyways..

None in particular. When it begins waiting it frees the slices it's no longer using. Since it is a high priority task, when the data comes in, it will be awakened and given a chance to execute. It will immediately grab up any timeslices it needs, and the kernel will allow this because the task has the priority.

The problem is that it has to donate the time-slices to somebody, otherwise the equal-share policy will be broken. Let's take the example from above: userA runs two apps, userB runs only one, the users hold 50% of the CPU each, drivers are "neutral" and belong to neither of the two groups. If one of the two apps of userA now calls the driver, its time-slice is donated to it, and the driver now runs on behalf of the caller (userA: drv 30%, appA2 20% | userB: appB1 50%). The driver sends the request to the device, releases the time-slices and blocks. Due to round-robin the values are automatically normalized and you end up with 28.6% for userA's remaining app and 71.4% for userB's app..

I was thinking of perhaps some sort of protest mechanism combined with a minimum guarantee of resources. But I dunno. This is all a work in progress, of course.

I think that I'd be simpler to not really release the time-slices, but only make them temporarily "invisible" for the scheduler. The task still owns the time-slice, they are just not used at the moment..
[pre]quant AllocateQuantum(length, pos, ..)
error DelocateQuantum(quant)

error AssociateQuantum(quant, thread)
error RevokeQuantum(quant, thread)[/pre]

By the way, has anyone noticed how *way* off topic this is?

Can't be that bad as long as ColonelKernel, who asked the original question, is still around

Here's a paper (PDF) on user-level scheduling... It's the only one I've read so far actually. Still not sure if what they propose is a good idea.

Thanks, I'll have a look at it as soon as possible. You did realize that it's not really about the exokernel system but rather one of the concept papers they later based their design on ?

About upcalls... I understand their purpose, I just can't visualize how they're implemented yet. Is it like unblocking a thread in user-space, or running a procedure in some arbitrary user-space thread's context (ala signals and NT APCs)...?

(Exokernel: An Operating System Architecture for Application-Level Resource Management)

"Timer interrupts denote the beginning and end of time slices, and are delivered in a manner similar to exceptions (discussed below):[...]
[*] It saves three scratch registers into an agreed-upon save area. (To avoid TLB exceptions, Aegis does this operation using physical addresses.)
[*] It loads the exception program counter. the last virtual address that failed to have a valid translation, and the cause of the exception
[*] It uses the cause of the exception to perform an indirect jump to an application-specified program counter value, where execution resumes with the appropriate permissions set"

So it seems as if Aegis is using the latter approach..

regards,
gaf

[QuiTeVexat]

This could be integrated into the messaging system easily: If a task blocks after having sent a message, its time-slice is donated to the called task. A task that doesn't block due to IPC won't fancy a specific task anyways..

Sounds right. I think the "synchronous protected control transfer" mentioned in the exokernel paper works something like this.

The problem is that it has to donate the time-slices to somebody, otherwise the equal-share policy will be broken. ...
Due to round-robin the values are automatically normalized and you end up with 28.6% for userA's remaining app and 71.4% for userB's app..

I don't see how. Your equal-share policy would prevent userB's app from sucking up all the released timeslices, or, better yet, force it to yield timeslices outside its share at request to userA's apps.

I think that I'd be simpler to not really release the time-slices, but only make them temporarily "invisible" for the scheduler. The task still owns the time-slice, they are just not used at the moment..

Why does the task need to own the timeslices when they are not in use? To prevent other tasks from using them? This would be a waste if another task could use those slices. When the first task wants those timeslices, the kernel would force the second to yield them.

Pax tecum,
Qui te vexat.

[Colonel Kernel]

Can't be that bad as long as ColonelKernel, who asked the original question, is still around

Heh... We should re-name the thread "Colonel Kernel vacuums up exokernel-related design and implementation details"

Thanks, I'll have a look at it as soon as possible. You did realize that it's not really about the exokernel system but rather one of the concept papers they later based their design on ?

Yes, I noticed the paper was quite old. However, it's the only thing I've found so far which is somewhat more generous with implementation details.

(Exokernel: An Operating System Architecture for Application-Level Resource Management)

Thanks for all the info. Sorry if you're just being a librarian on my behalf... I'm still reading all these research papers, between everything else I have to do. I found the original 100-page thesis on exokernels... I think that will take a while.

[gaf]

I don't see how. Your equal-share policy would prevent userB's app from sucking up all the released timeslices

Yes, but userB doesn't even have to allocate any additional time-slices as round-robin normalizes itself. Let's say that there are 100 time-slices in the system, 50 belong to userA, the other 50 to userB. If userA now releases 30 of the time-slices because some driver blocks, userA will only hold 20 TS and userB 50. It doesn't matter that the 30 time-slices still belong to userA as long as the user doesn't use them - this is why a task always has to donate them to some other task in the group when it goes idle.
[pre]while(driver_blocked)
{
// Schedule(taskA1, 30ts)
Schedule(taskA2, 20ts)
Schedule(taskB1, 50ts)
}

If TS aren't used, the system normalizes itself immediately..[/pre]

Or force it to yield timeslices outside its share at request to userA's apps.

This would work, but the scheduler then has to rebalance the system everytime a task blocks or unblocks. Again problems arise as time-slices can't be divided. Assume that we have a system with two users which have 10 tasks each. One of the tasks of userA goes idle and the scheduler now has to take away the 4 TS this task held from userB to balance this system. This would means that it has to take 2.25 TS from each of userB's tasks, whic is of course not possible. The only solution is again to have userB's scheduler solve the problem by establishing some basic lottery scheduling in the external managers and take away 2 time-slices from each tasks plus an additional TS from one of the them that is choosen at random.

Why does the task need to own the timeslice when it is not in use? To prevent other tasks from using them?

How do the other task in the same group even know that there are now free time-slices available ? In my opinion this could only be done in the scheduler which knows who holds how many timeslices but if it's done there, it's nothing else than donation..

This would be a waste if another task could use those slices.

As time-slices don't have any absolute value you can waste as many of them as you wish to, the system will always normalize and run at 100% (unless you wasted all of them, of course).

When the first task wants those timeslices, the kernel would force the second to yield the slices.

That's exactly what I wanted to avoid: What's the point of giving the apps control over the time-slices if they are revoked all the time ? Wouldn't it then be wiser to let a user-space task manager do the scheduling itself ?

regards,
gaf

[QuiTeVexat]

Yes, but userB doesn't even have to allocate any additional time-slices as round-robin normalizes itself. ... It doesn't matter that the 30 time-slices still belong to userA as long as the user doesn't use them - this is why a task always has to donate them to some other task in the group when it goes idle.

Nothing's getting normalized. Those freed timeslices are *free*. The processor will halt on them unless someone else allocates them.

This would work, but the scheduler then has to rebalance the system everytime a task blocks or unblocks. Again problems arise as time-slices can't be divided. Assume that we have a system with two users which have 10 tasks each. One of the tasks of userA goes idle and the scheduler now has to take away the 4 TS this task held from userB to balance this system. This would means that it has to take 2.25 TS from each of userB's tasks, whic is of course not possible. The only solution is again to have userB's scheduler solve the problem by establishing some basic lottery scheduling in the external managers and take away 2 time-slices from each tasks plus an additional TS from one of the them that is choosen at random.

Rebalancing? Those 4 timeslices are free for allocation by another task. They don't need to be automatically given to others. In fact, this would be transparent allocation, which is contrary to the exokernel concept anyway.

How do the other task in the same group even know that there are now free time-slices available ?

The timeslice allocation table (TAT? TSAT? ) is readable by all tasks.

As time-slices don't have any absolute value you can waste as many of them as you wish to, the system will always normalize and run at 100% (unless you wasted all of them, of course).

Whoa, this right here might be our problem. My concept of the timeslice *was* that it was an absolute value: the time between two timer ticks. If a timeslice is free, the kernel halts the processor until the next interrupt to save power. This way, the apps can define not only how much but when they want to run.

When the first task wants those timeslices, the kernel would force the second to yield the slices.

What's exactly what I wanted to avoid: What's the point of giving the apps control over the time-slices if they are revoked all the time ?

They aren't being revoked all the time; they are being shared between tasks and the kernel is allowing the tasks to get their share when they require it while allowing use of unused resources. Also, with this method, the allocation and revocation are clearly exposed.

Wouldn't it then be wiser to let a user-space task manager do the scheduling itself ?

Then instead of exposing revocation, allocation, etc. we are abstracting it and taking control away from the tasks. Getting away from this forced abstraction was the whole point of the exokernel, no?

Pax tecum,
Qui te vexat.

[gaf]

Whoa, this right here might be our problem. My concept of the timeslice *was* that it was an absolute value: the time between two timer ticks. If a timeslice is free, the kernel halts the processor until the next interrupt to save power.

Hmm, this might change things a bit..

Since halting the CPU isn't really an option though (at least as long as there's still work to do) any of the other tasks has to allocate the free time-slices. The task following the one that has freed its time-slices would have a big advantage as there's nothing that keeps it from just allocation it all. Even if we assume that the tasks aren't that greedy and want to work together, problems might occure as the time-slices have to be allocated before they are executed, otherwise CPU time is wasted. How can they coordinate this without using some central instance ?

They aren't being revoked all the time; they are being shared between tasks and the kernel is allowing the tasks to get their share when they require it while allowing use of unused resources. Also, with this method, the allocation and revocation are clearly exposed.

Let's assume the driver has just freed its time-slices and that some other application has allocated it. Meanwhile the disk finishes reading the sectors and triggers an IRQ to notify the driver. How does the driver now get a time-slice to run if all are allocated ? What would give the driver the right to simply revoke a time-slice ? After all it (now) belongs to a different task which might depend on it - maybe it's even the only TS is has..

Then instead of exposing revocation, allocation, etc. we are abstracting it and taking control away from the tasks. Getting away from this forced abstraction was the whole point of the exokernel, no?

You got me wrong here: I'm not for such a design, but just afraid that the mechanism used in Aegis is too low-level and might eventually make it necessary for some policies to use big user-space managers.

cheers,
gaf

[QuiTeVexat]

Since halting the CPU isn't really an option though (at least as long as there's still work to do)

First, I'd like to note that even if there are tasks with allocated timeslice, there isn't necessarily any work to do. A task could have, for instance, intending to sleep, reserved a timeslice in the future at the time it wants to awaken, or have something set up on a polling interval. In that case, it needs no more timeslice than it requested, and should not be given extra timeslices it didn't ask for.

I do, however, agree that if some compute-bound task wants to use the slice or slices, you want to get them to that task as soon as possible, as to avoid wasting CPU time.

The task following the one that has freed its time-slices would have a big advantage as there's nothing that keeps it from ust allocation it all.

And there's nothing that keeps the other tasks from acquiring their fair share afterwards.

the time-slices have to be allocated before they are executed, otherwise CPU time is wasted. How can they coordinate this without using some central instance ?

The kernel is the central instance. It could, for example, possibly provide:

+ A free list if the number of free slices is low. Tasks could check this list periodically to see if they want any of the slices
+ An opt-in Accept-Newly-Freed-Slices list. The kernel would then have a policy* for dividing slices between tasks on this list. Tasks would be informed when they receive timeslice by this method (possibly just by informing them of the timeslice number upon entry), so the allocation would be both exposed and requested.

And so forth.

* E.g. fair-division, then lottery, taking into account priorities, with preference toward giving contiguous slice areas (since tasks on this list are probably compute-bound anyway).

Let's assume the driver has just freed its time-slices and that some other application has allocated it. Meanwhile the disk finishes reading the sectors and triggers an IRQ to notify the driver. How does the driver now get a time-slice to run if all are allocated ? What would give the driver the right to simply revoke a time-slice ? After all it (now) belongs to a different task which might depend on it - maybe it's even the only TS is has..

The driver has the right to do this because it is a higher priority task. If it is not, then it would have to wait for a lower priority task to begin executing. Or the kernel could hold off and notify the driver later in a a timeslice the driver left around to wait (but that's icky, wasteful and not as responsive to interrupts). You have expressed the concern I had with this, and had written about in an earlier post:

The problem I see with that is it requires that tasks be preemptable from allocated timeslice, which bothers me since applications could be relying on the allocated timeslice for realtime/deadline sort of things. So I was/am/will be playing around with ideas on how to resolve that.

Work-in-progress. That's what we need the ingenious ideas for.

You got me wrong here: I'm not for such a design, but just afraid that the mechanism used in Aegis is too low-level and might eventually make it necessary for some policies to use big user-space managers.

So we just need to come up with some clever ideas so we don't have to sacrifice the benefits we're seeking.

Pax tecum,
Qui te vexat.