Scheduler and Priorities

[cxzuk]

Hi all,

Im alittle confused on the scheduler, mostly in regard to priorities and starvation.

Starvation is when a process is not given necessary resources?

im not completely sure which resource this is refering to. From what i can tell (referencing the lottery scheduler) this resource is CPU % time?

I do not understand why a (Non priority based) Round Robin would produce starvation?

Does the RR scheduler not work through the list from start to end? Does it get 'reset' periodically?

Does 'priority' simply refer to size of allocated time slot?

Thankyou
Mike

[Combuster]

Starvation in theory is when there's no guarantee that a task actually gets access to any of the resources it requires. That might be individual resources, such as CPU time and disk access, but also combinations thereof. The typical case of starvation happens when a certain lock is taken each time the process gets a time slice, even though both the lock and the processor is available at a regular basis.

And while a task may not be subject to starvation in theory, from an observer's point of view it may be kept unreasonably long from such resources and it would typically be called by the same name.

A non-prioritized round-robin scheduler is of it's own not sufficient to starve a task from CPU resources, as its specification explicitly states that each process gets an timeslice in turn, within a finite amount of time. That doesn't mean that implementation issues allow for certain tasks to be starved.


Priorities are a bigger mess: if a higher priority task is available, it actually prevents lower tasks from executing. That also makes those traditional priorities rather dangerous to deal with. The optimal solution to that specific problem lies somewhere deep in Design Hell.

[cxzuk]

Thankyou combuster.

I think i know where ive gone wrong, but can you tell me the pitfalls to my current design? (Im building an OO microkernel)

The design i have separated out the scheduler into two chunks by the looks of it.

I have a scheduler, which for me provides the illusion of having more cores than I actually have.
Ive taken the term (prob wrongly) multitasking to mean that a core has to multitask, take the place of two or more cores, to provide this illusion.

I have, (i guess? I didnt see it as a scheduler before), another scheduler relating to my IPC. This scheduler determines which order messages are dealt with.

These two schedulers don't currently talk to each other (nor do they exist in code yet either). To optimise my cpu scheduler, the task stores a variable of whether if its waiting for something(ipc) or not. This is set by the IPC scheduler when the message is added to the queue, and read by the scheduler to skip that process.

With that, "Priority" is actually related to the ordering of the IPC?

I can vaguely picture the core scheduler algorithm/code being selected depending on the resource usage needs as an optimisation? But would IPC and Sched need to talk to each other while running?

Thankyou for your time,
Mikey

[bewing]

As Combuster said, there are many ways of looking at starvation, and even with this question you are descending into Design Hell.

You might decide to think of the IPC system/queue as a "resource" -- and then think about whether your tasks are being starved for that resource.

There is no guarantee that any resource will be available at every clock cycle for each task. You do not need to push everything that far (especially since it's impossible) -- and you always need some kind of "blocking method" for when a resource is not available yet. It's just that you want to make sure that your IPC message queue does not take an unreasonably long time to push a message back out to its destination.

[cxzuk]

Hi bewing,

Im sorry, I just can't seem to figure out what your answering here?

Can I have a definition of "Design Hell" so I know what your saying im doing wrong?

And im puzzled why I would think of IPC as a resource? Or is it some kind of thought exercise?

Thankyou
Mike

[Combuster]

And im puzzled why I would think of IPC as a resource? Or is it some kind of thought exercise?

What would (eventually) happen if you keep sending messages from A to B, when B is not reading them?

Can I have a definition of "Design Hell" so I know what your saying im doing wrong?

Did you really have to ask about a metaphor? Design Hell


Before trying anything really hard, have you ever solved this textbook problem? (If you haven't, do not google the solution) Once you fixed the problem with deadlocks, did you fix starvation as well?

[cxzuk]

Before trying anything really hard, have you ever solved this textbook problem? (If you haven't, do not google the solution) Once you fixed the problem with deadlocks, did you fix starvation as well?

Ha, The Hungry Philosophers and starvation? I like the pun

I did solve this many a long time ago, though thinking back I suspect it wasn't a fair solution (It favoured a philosopher over the others).

But this problem does not relate to IPC? - A small diagram of the two problems and why they differ below; (Sorry for the poor images)

The dining philosophers implies some ownership on the resource, IPC is about collaboration to reach a goal. "Dining Philosophers" may be an issue with drivers, but id be more suspect as to why two drivers are trying to own the same device?

The Dining Philosophers is trivial when you move it to collaboration thinking and allow them to communicate; A Spork allocator (Waiter? - Centralised) or Collaboration between them all (Decentralised).

What would (eventually) happen if you keep sending messages from A to B, when B is not reading them?

If you mean asynchronously, A's thread count would reach its limit and A would fail. (For attempting to abuse B - It probably shows a design issue in A)

Only A can keep track of its actions (Imagine one telephone operator with multiple telephones; One call is engaged, That action is placed on hold but is still held by the telephone operator).

Is this understanding right?

As always, thankyou for your time and efforts,
Mikey

[Combuster]

IPC is a typical approach to concurrency problems. It is in turn built on top of simpler processes: what do you do when two students approach enter the queue at the same time?

As for the dining philosophers, it is a problem at multiple levels. Fixing deadlocks is one thing; try solving it under the following constraints:
- Every philosopher will be able to eat within a deterministic amount of steps. They will starve otherwise.
- When a philosopher is hungry, it must either grab a fork or wait for one. A hungry philosopher lacks courtesy.

Then remember that solving scheduling issues is far worse than that.