Courses/Computer Science/CPSC 457.W2012/Lecture Notes/Scheduling

From wiki.ucalgary.ca
Jump to: navigation, search

Process Scheduling

In this session, we will begin an examination of one of the central purposes of an "operating system" (be it a desktop OS or a distributed billing and customer service system): scheduling jobs / tasks / processes. After all, fundamentally, the number of virtual tasks that could exist on a system are typically much greater than the amount of physical resources available.

Hence, the hardware (e.g., CPU, memory, and devices) must be multiplexed or shared across all virtual tasks present on the system. Tasks come and go mostly unpredictably. Scheduling deals with sharing these resources in a coherent fashion in the face of this dynamic load.

Focus Question

What support is necessary for deciding which program / process should run next (i.e., be given access and control over the CPU and other system devices)? Is there any way to show that we are doing well at scheduling?

Agenda

Overview of scheduling considerations: fairness, efficiency, progress; scheduling metrics

time quanta, clock, preemption (basic hardware and low-level OS support for reliable timing)

process states (support needed for distinguishing between some characteristics of processes; meta-data that has an impact on determining what process is a candidate for being run)

types of processes (interactive vs. batch)

approaches to scheduling: random, FCFS, LJF, SJN, RR, UWRR, ... priority

priority inversion

context switch (tie back to time quanta)

comparing 2.4 and 2.6 scheduler code

real-time scheduling

Notes

The slides for today:

Linux defines the symbol "current" to be a macro that resolves to the currently executing process (for example, the process that invoked a system call). See the current.h file, which derives the value of current from the CPU state.

There were many key concepts and ideas presented today, among them:

  • preemption
  • time quantum
  • context switch
  • fairness, responsiveness
  • types of processes
  • example scheduling algorithms (know how to draw scheduling timelines)
  • metrics for comparing scheduling algorithms (know these)


The code for part of the 2.6 scheduler is at:

The relevant lines: 

4453        prev->sched_class->put_prev_task(rq, prev);
4454        next = pick_next_task(rq, prev);
4455

Of course, pick_next_task runs in constant time, but there is more work hidden in there.

The code for (part) of the 2.4 scheduler (for 2.4.24) is here:

and the O(n) snippet is listed below: 

/*
 * Default process to select...
*/
       next = idle_task(this_cpu);
       c = -1000;
       list_for_each(tmp, &runqueue_head) {
               p = list_entry(tmp, struct task_struct, run_list);
               if (can_schedule(p, this_cpu)) {
                       int weight = goodness(p, this_cpu, prev->active_mm);
                       if (weight > c)
                               c = weight, next = p;
               }
       }

Readings

  • MOS: 2.4.1 "Introduction to Scheduling" (plus 2 intro paragraphs in S2.4)
  • MOS: 2.4.5 "Policy vs. Mechanism"
  • MOS: 10.3.4: "Scheduling in Linux"
  • MOS: 2.7 "Summary" (this talks about some things we'll consider next)
Retrieved from "http://wiki.ucalgary.ca/index.php?title=Courses/Computer_Science/CPSC_457.W2012/Lecture_Notes/Scheduling&oldid=65832"