illinois-cs241 / broadway

A distributed systems framework used running distributable workloads.
Other
18 stars 0 forks source link

Load balancing when scheduling with multiple courses #22

Closed ezhang887 closed 4 years ago

ezhang887 commented 4 years ago

Resolves #21.

Replaces the current global queue with a wrapper around it that contains multiple queues internally (called MultiQueue).

The MultiQueue contains one queue per class. When pushing into the MultiQueue, the course_id will also need to be specified to indicate which internal queue to push into. When pulling from the MultiQueue, it will round-robin between its internal queues, so starvation should not occur.

To easily have access to the course_id when pushing into the MultiQueue, I added it as a field to the GradingRun model and dao. Also, the queues for each class are added into the MultiQueue here.

ezhang887 commented 4 years ago

Round-robin pseudocode (@andyclee ):

func get_job():
        N := num_queues
        if N = 0:
                return Empty

        for i in {0, ..., N-1}:
                idx := (round_robin_idx + i) % N
                if queues[idx] is not empty:
                        round_robin_idx := (idx + 1) % N
                        return queues[idx].pop()
        return Empty