A naive round robin CPU scheduler

A couple days ago, I spent maybe an hour whipping together a vary naive CPU scheduler for project 1 in advanced operating systems. This naive scheduler pins each of the virtual CPUs in a round robin fashion, not taking utilization (or any other factor) into consideration. For example, say we have four virtual CPUs and two physical CPUs; the scheduler will assign virtual CPU #0 to physical CPU #0, virtual CPU #1 to physical CPU #1, virtual CPU#3 to physical CPU #0 and virtual CPU#0 to physical CPU#1.

This naive schedule is far from fancy — really the code just performs a mod operation to wrap around the length of the physical CPUs and avoid an index error and carries out a left bit shift operation to populate the bit map — but performs surprisingly well based off monitoring results (below) that measure the utilization of each physical CPU.

Of course, my final scheduler will pin virtual CPUs to physical CPUS more intelligently,  taking the actual workload (i.e. time in nanoseconds) of the virtual CPUs into consideration.  But as always, I wanted to avoid pre-optimization and jump to some fancy algorithm published in some research paper and I’m glad I started with a primitive scheduler that, for the most part, evenly distributes the work apart from the fifth test (which generates uneven workloads), the only test in which the naive scheduler creates a more uneven workload.

With this basic prototype in place, I should be able to come up with a more sophisticated algorithm that takes the virtual CPU utilization into consideration.

Test Case 1

In this test case, you will run 8 virtual machines that all start pinned to pCPU0. The vCPU of each VM will process the same workload.

Expected Outcome

Each pCPU will exhibit an equal balance of vCPUs given the assigned workloads (e.g., if there are 4 pCPUs and 8 vCPUs, then there would be 2 vCPUs per pCPU).

--------------------------------------------------
0 - usage: 103.0 | mapping ['aos_vm1', 'aos_vm8', 'aos_vm4', 'aos_vm6', 'aos_vm5', 'aos_vm2', 'aos_vm3', 'aos_vm7']
1 - usage: 0.0 | mapping []
2 - usage: 0.0 | mapping []
3 - usage: 0.0 | mapping []
--------------------------------------------------
0 - usage: 99.0 | mapping ['aos_vm1', 'aos_vm8', 'aos_vm4', 'aos_vm6', 'aos_vm5', 'aos_vm2', 'aos_vm3', 'aos_vm7']
1 - usage: 0.0 | mapping []
2 - usage: 0.0 | mapping []
3 - usage: 0.0 | mapping []
--------------------------------------------------
0 - usage: 49.0 | mapping ['aos_vm1', 'aos_vm5']
1 - usage: 47.0 | mapping ['aos_vm8', 'aos_vm2']
2 - usage: 50.0 | mapping ['aos_vm4', 'aos_vm3']
3 - usage: 49.0 | mapping ['aos_vm6', 'aos_vm7']
--------------------------------------------------
0 - usage: 60.0 | mapping ['aos_vm1', 'aos_vm5']
1 - usage: 65.0 | mapping ['aos_vm8', 'aos_vm2']
2 - usage: 61.0 | mapping ['aos_vm4', 'aos_vm3']
3 - usage: 61.0 | mapping ['aos_vm6', 'aos_vm7']
--------------------------------------------------

Test 2

In this test case, you will run 8 virtual machines that start with 4 vCPUs pinned to pCPU0 and the other 4 vCPUs pinned to pCPU3. The vCPU of each VM will process the same workload.

Expected Outcome

Each pCPU will exhibit an equal balance of vCPUs given the assigned workloads.

--------------------------------------------------
0 - usage: 102.0 | mapping ['aos_vm1', 'aos_vm4', 'aos_vm5', 'aos_vm3']
1 - usage: 0.0 | mapping []
2 - usage: 0.0 | mapping []
3 - usage: 101.0 | mapping ['aos_vm8', 'aos_vm6', 'aos_vm2', 'aos_vm7']
--------------------------------------------------
0 - usage: 50.0 | mapping ['aos_vm1', 'aos_vm5']
1 - usage: 53.0 | mapping ['aos_vm8', 'aos_vm2']
2 - usage: 51.0 | mapping ['aos_vm4', 'aos_vm3']
3 - usage: 53.0 | mapping ['aos_vm6', 'aos_vm7']
--------------------------------------------------
0 - usage: 102.0 | mapping ['aos_vm1', 'aos_vm5']
1 - usage: 100.0 | mapping ['aos_vm8', 'aos_vm2']
2 - usage: 95.0 | mapping ['aos_vm4', 'aos_vm3']
3 - usage: 99.0 | mapping ['aos_vm6', 'aos_vm7']

Test Case 3

In this test case, you will run 8 virtual machines that start with an already balanced mapping of vCPU->pCPU. The vCPU of each VM will process the same workload.

Expected Outcome

No vCPU->pCPU mapping changes should occur since a balance state has already been achieved.

--------------------------------------------------
0 - usage: 63.0 | mapping ['aos_vm1', 'aos_vm5']
1 - usage: 60.0 | mapping ['aos_vm8', 'aos_vm2']
2 - usage: 59.0 | mapping ['aos_vm4', 'aos_vm3']
3 - usage: 58.0 | mapping ['aos_vm6', 'aos_vm7']
--------------------------------------------------
0 - usage: 57.0 | mapping ['aos_vm1', 'aos_vm5']
1 - usage: 60.0 | mapping ['aos_vm8', 'aos_vm2']
2 - usage: 60.0 | mapping ['aos_vm4', 'aos_vm3']
3 - usage: 61.0 | mapping ['aos_vm6', 'aos_vm7']
--------------------------------------------------
0 - usage: 57.0 | mapping ['aos_vm1', 'aos_vm5']
1 - usage: 59.0 | mapping ['aos_vm8', 'aos_vm2']
2 - usage: 59.0 | mapping ['aos_vm4', 'aos_vm3']
3 - usage: 60.0 | mapping ['aos_vm6', 'aos_vm7']

Test Case 4

In this test case, you will run 8 virtual machines that start with an equal affinity to each pCPU (i.e., the vCPU of each VM is equally like to run on any pCPU of the host). The vCPU of each VM will process the same workload.

Expected Outcome

Each pCPU will exhibit an equal balance of vCPUs given the assigned workloads.

3 - usage: 60.0 | mapping ['aos_vm3', 'aos_vm7']
--------------------------------------------------
0 - usage: 57.0 | mapping ['aos_vm1', 'aos_vm5']
1 - usage: 61.0 | mapping ['aos_vm8', 'aos_vm2']
2 - usage: 58.0 | mapping ['aos_vm4', 'aos_vm3']
3 - usage: 59.0 | mapping ['aos_vm6', 'aos_vm7']
--------------------------------------------------
0 - usage: 59.0 | mapping ['aos_vm1', 'aos_vm5']
1 - usage: 60.0 | mapping ['aos_vm8', 'aos_vm2']
2 - usage: 60.0 | mapping ['aos_vm4', 'aos_vm3']
3 - usage: 61.0 | mapping ['aos_vm6', 'aos_vm7']
--------------------------------------------------

Test Case 5

In this test case, you will run 8 virtual machines that start with an equal affinity to each pCPU (i.e., the vCPU of each VM is equally like to run on any pCPU of the host). Four of these vCPUs will run a heavy workload and the other four vCPUs will run a light workload.

Expected Outcome

Each pCPU will exhibit an equal balance of vCPUs given the assigned workloads.

--------------------------------------------------
0 - usage: 50.0 | mapping ['aos_vm3']
1 - usage: 70.0 | mapping ['aos_vm2', 'aos_vm7']
2 - usage: 142.0 | mapping ['aos_vm1', 'aos_vm4', 'aos_vm6']
3 - usage: 85.0 | mapping ['aos_vm8', 'aos_vm5']
--------------------------------------------------
0 - usage: 88.0 | mapping ['aos_vm1', 'aos_vm7']
1 - usage: 87.0 | mapping ['aos_vm8', 'aos_vm4']
2 - usage: 53.0 | mapping ['aos_vm5']
3 - usage: 119.0 | mapping ['aos_vm6', 'aos_vm2', 'aos_vm3']
--------------------------------------------------
0 - usage: 182.0 | mapping ['aos_vm1', 'aos_vm5', 'aos_vm3', 'aos_vm7']
1 - usage: 36.0 | mapping ['aos_vm8']
2 - usage: 54.0 | mapping ['aos_vm4']
3 - usage: 70.0 | mapping ['aos_vm6', 'aos_vm2']
--------------------------------------------------
0 - usage: 100.0 | mapping ['aos_vm1', 'aos_vm5']
1 - usage: 73.0 | mapping ['aos_vm8', 'aos_vm2']
2 - usage: 99.0 | mapping ['aos_vm4', 'aos_vm3']
3 - usage: 74.0 | mapping ['aos_vm6', 'aos_vm7']
--------------------------------------------------