Discussion on the schedule policy

gistfile1.txt

For this problem, I tested two policies. 

The first one is "small tasks first". Using this policy can make the scheduler achieve very high throughput in the terms of "# of tasks it can schedule in a given time".

But it will be likely to cause starvation problem. In which case if the small tasks keep coming, they will preempt the scheduler and block the big tasks.

So in real environment, this kind of scheduler will incent users not to lie about their actual usage.


The second one is "small tasks first + starvation proof"

In this policy, small tasks are served first. But all tasks will have a waiting limit. If one task timeout, then it will get served anyway.

However this policy has its own problem,

1, If the big task demands too much, it will simply block the whole scheduler. Even worse, it will make all other tasks timeouts. Thus the scheduler policy will reduce to FIFO.

2, It is not easy to determine the value of the timeout.
Idealy, we can use the queue theory to compute the average waiting time dynamically. But since time limits, I didn't implement that.

And more:

To measure the policy, I think there are several metrics

1. Scheduler throughput, that is the number of tasks it scheduled in a given time.

2, Average waiting time(latency), that is the average waiting time of a task in the queue.

3, Deviation of the waiting time, this can measure the fairness of the scheduler.

To improve:

I think I have commentted some in the source code.

Most are not hard, but to achieve locality is a little bit more complex