Animated Simulation of Parallel Scheduling Algorithms

1. High-level design

• Step1 :
  • The jobs generator will continuously generate a series of jobs based on the rules that the user selects.
• Step2 :
  • The job will be encapsulated into a task. (Compared to jobs, tasks have more proprieties.) After the encapsulation, the task will be put into the queue.
• Step3 :
  • The scheduler will continuously pick up a task with the highest priority from the queue based on the schedule algorithm and statues of the server cluster.
• Step4 :
  • When a task's quantum expires, or a task is done, the server will put the task into Synchronization Component, which is used to wait for the coming of all parts of the task.

Questions

• 1. Do you have any suggestions for this design?
• 2. In this system, there might be more than one component that accesses to the queue at the same time. So we need to use a lock to enforce limits on access to the queue. However, the lock will affect the statistic results. Do we need to care about that?

Meet with Christine (Oct 30, 2019)

1. Pseudocode

var queue;

// Job Generator (done!)
while(true) {
    //1. generate a job
    var job = generateJob();
    //2. encapsulate a job
    var task = encapsulate(job);
    //3. put the task into a queue
    queue.push(tasks);
    //4. get time intervals 
    var t = exponential(λ);
    //5. sleep t seconds(microseconds)
    time.sleep(t);
}

// Job Scheduler (in-progress)
while(true) {
    //1. sort the queue based on the scheduling algorithms
    sort(queue, rules);
    //2. pick up a task from the queue.
    var task = queue.poll();
    //3. check if the tasks that are processing by the cluster are done. 
    //If done, put the task into a complete queue
    var numOfAvailableNodes = ckeck();
    //4. get the number of server nodes that the current task needs
    var numOfNeededByCurrTask = getNum();
    if(numOfAvailableNodes < numOfNeededByCurrTask) {
    	//perform preemption process to make sure 
    	//the current task can get enough server nodes
        preemption(numOfNeededByCurrTask);
    }
    process(tasks);
}

// Statistic Section (The next step)
while(true) {
    // To do
}

2. plan

Oct 30 - Nov 10 (Scheduler and Statistic Section)

Oct 11 - Nov 20 (Complete the UI part)

Nov 21 - Nov 27(Thanksgiving) (Test and publish)

3. Reference

1.heSRPT: Optimal Parallel Scheduling of Jobs With Known Sizes
https://arxiv.org/pdf/1903.09346.pdf