Operating System Examples

  • We turn next to a description of the scheduling policies of the Solaris, Windows XP, and Linux operating systems. It is important to remember that we are describing the scheduling of kernel threads with Solaris and Windows XP.
  • Recall that Linux does not distinguish between processes and threads; thus, we use the term task when discussing the Linux scheduler.

2.4.1 Example: Solaris Scheduling

  • Solaris uses priority-based thread scheduling where each thread belongs to one of six classes:

  1. Time sharing (TS)
  2. Interactive (IA)
  3. Real time (RT)
  4. System (SYS)
  5. Fair share (FSS)
  6. Fixed priority (FP)

  • Within each class there are different priorities and different scheduling algorithms.
  • The default scheduling class for a process is time sharing. The scheduling policy for the time-sharing class dynamically alters priorities and assigns time slices of different lengths using a multilevel feedback queue.
  • By default, there is an inverse relationship between priorities and time slices.
  • The higher the priority, the smaller the time slice; and the lower the priority, the larger the time slice.
  • Interactive processes typically have a higher priority; CPU-bound processes, a lower priority. This scheduling policy gives good response time for interactive processes and good throughput for CPU-bound processes.

Figure 2.20 Solaris dispatch table for time-sharing and interactive threads.

  • The interactive class uses the same scheduling policy as the time-sharing class, but it gives windowing applications-such as those created by the KDE or GNOME window managers-a higher priority for better performance.
  • Figure 2.20 shows the dispatch table for scheduling time-sharing and interactive threads.
  • These two scheduling classes include 60 priority levels, but for brevity, we display only a handful.
  • The dispatch table shown in Figure 2.20 contains the following fields:
    • Priority.
      • The class-dependent priority for the time-sharing and interactive classes. A higher number indicates a higher priority.
    • Time quantum.
      • The time quantum for the associated priority.
      • This illustrates the inverse relationship between priorities and time quanta: the lowest priority (priority 0) has the highest tince quantum (200 milliseconds), and the highest priority (priority 59) has the lowest time quantum (20 milliseconds).
    • Time quantum expired.
      • The new priority of a thread that has used its entire time quantum without blocking.
      • Such threads are considered CPU-intensive. As shown in the table, these threads have their priorities lowered.
    • Return from sleep.
      • The priority of a thread that is returning from sleeping (such as waiting for I/O).
      •  As the table illustrates, when I/0 is available for a waiting thread, its priority is boosted to between 50 and 59, thus supporting the scheduling policy of providing good response time for interactive processes.
  • Threads in the real-time class are given the highest priority. This assignment allows a real-time process to have a guaranteed response from the system within a bounded period of time.
  • A real-time process will run before a process in any other class.
  • In general, however, few processes belong to the real-time class.
  • Solaris uses the system class to run kernel threads, such as the scheduler and paging daemon.
  • Once established, the priority of a system thread does not change.
  • The system class is reserved for kernel use (user processes rum1ing in kernel mode are not in the system class).
  • The fixed-priority and fair-share classes were introduced with Solaris 9.
  • Threads in the fixed-priority class have the same priority range as those in the time-sharing class; however, their priorities are not dynamically adjusted.
  • The fair-share scheduling class uses CPU shares instead of priorities to make scheduling decisions.
  • CPU shares indicate entitlement to available CPU resources and are allocated to a set of processes (known as a project).
  • Each scheduling class includes a set of priorities. However, the scheduler converts the class-specific priorities into global priorities and selects the thread with the highest global priority to run.
  • The selected thread n.ms on the CPU until it (1) blocks, (2) uses its time slice, or (3) is preempted by a higher-priority thread.
  • If there are multiple threads with the same priority, the scheduler uses a round-robin queue.


Figure 2.21 Solaris scheduling.

  • Figure 2.21 illustrates how the six scheduling classes relate to one another and how they map to global priorities. Notice that the kernel maintains 10 threads for servicing interrupts.
  • These threads do not belong to any scheduling class and execute at the highest priority (160-169).
  • As mentioned, Solaris has traditionally used the many-to-many model but switched to the one-to-one model beginning with Solaris 9.

2.4.2 Example: Windows XP Scheduling

  • Windows XP schedules threads using a priority-based, preemptive scheduling algorithm.
  • The Windows XP scheduler ensures that the highest-priority thread will always run.
  • The portion of the Windows XP kernel that handles scheduling is called the dispatcher. A thread selected to run by the dispatcher will run until it is preempted by a higher-priority thread, until it terminates, until its time quantum ends, or until it calls a blocking system call, such as for I/O.
  • If a higher-priority real-time thread becomes ready while a lower-priority thread is running, the lower-priority thread will be preempted.
  • This preemption gives a real-time thread preferential access to the CPU when the thread needs such access.
  • The dispatcher uses a 32-level priority scheme to determine the order of thread execution. Priorities are divided into two classes.
  • The variable class contains threads having priorities from 1 to 15, and the real-time class contains threads with priorities ranging from 16 to 31. (There is also a thread running at priority 0 that is used for memory management.)
  • The dispatcher uses a queue for each scheduling priority and traverses the set of queues from highest to lowest until it finds a thread that is ready to run.
  • If no ready thread is found, the dispatcher will execute a special thread called the idle thread.
  • There is a relationship between the numeric priorities of the Windows XP kernel and the Win32 API.
  • The Win32 API identifies several priority classes to which a process can belong. These include:
    • REALTIME_PRIORITY _CLASS
    • HIGH_LPRIORITY _CLASS
    • ABOVE_NORMA_PRIORITY CLASS
    • NORMAL_PRIORITY_CLASS
    • BELOW_NORMAL_PRIORITY _CLASS
    • IDLE_PRIORITY _CLASS
  • Priorities in all classes except the REALTIME...PRIORITY _CLASS are variable, meaning that the priority of a thread belonging to one of these classes can change.
  • A thread within a given priority classes also has a relative priority. The values for relative priorities include:
    • TIME_CRITICAL
    • HIGHEST
    • ABOVE_NORMAL
    • NORMAL
    • BELOW NORMAL
    • LOWEST
    • IDLE
  • The priority of each thread is based on both the priority class it belongs to and its relative priority within that class. This relationship is shown in Figure 2.22.
  • The values of the priority classes appear in the top row. The left column contains the values for the relative priorities.
  • For example, if the relative priority of a thread in the ABOVE_NORMAL_PRIORITY_CLASS  is NORMAL the numeric priority of that thread is 10.

Figure 2.22 Windows XP priorities.

  • Furthermore, each thread has a base priority representing a value in the priority range for the class the thread belongs to.
  • By default, the base priority is the value of the NORMAL relative priority for that class. The base priorities for each priority class are:
    • REALTIME_PRIORITY_CLASS-24
    • HIGH_PRIORITY CLASS-13
    • ABOVE_NORMALPRIORITY_CLASS-10
    • NORMAL_PRIORITY _CLASS-8
    • BELOW _NORMALPRIORITY _CLASS-6
    • IDLE_PRIORITY _CLASS-4
  • Processes are typically members of the NORMALPRIORITY_CLASS.
  • A process belongs to this class unless the parent of the process was of the IDLE_PRIORITY _CLASS or unless another class was specified when the process was created. The initial priority of a thread is typically the base priority of the process the thread belongs to.
  • When a thread's time quantun1 runs out, that thread is interrupted; if the thread is in the variable-priority class, its priority is lowered.
  • The priority is never lowered below the base priority, however. Lowering the priority tends to limit the CPU consumption of compute-bound threads.
  • When a variable priority thread is released from a wait operation, the dispatcher boosts the priority.
  • The amount of the boost depends on what the thread was waiting for; for example, a thread that was waiting for keyboard I/O would get a large increase, whereas a thread waiting for a disk operation would get a moderate one.
  • This strategy tends to give good response times to interactive threads that are using the mouse and windows. It also enables I/O-bound threads to keep the I/O devices busy while permitting compute-bound threads to use spare CPU cycles in the background.
  • This strategy is used by several time-sharing operating systems, including UNIX. In addition, the window with which the user is currently interacting receives a priority boost to enhance its response time.
  • When a user is running an interactive program, the system needs to provide especially good performance. For this reason, Windows XP has a special scheduling rule for processes in the NORMALPRIORITY_CLASS.
  • Windows XP distinguishes between the foreground process that is currently selected on the screen and the background processes that are not currently selected.
  • When a process moves into the foreground, Windows XP increases the scheduling quantum by some factor-typically by 3.
  • This increase gives the foreground process three times longer to run before a time-sharing preemption occurs.

2.4.3 Example: Linux Scheduling

  • Prior to Version 2.5, the Linux kernel ran a variation of the traditional UNIX scheduling algorithm.
  • Two problems with the traditional UNIX scheduler are that it does not provide adequate support for SMP systems and that it does not scale well as the number of tasks on the system grows.
  • With Version 2.5, the scheduler was overhauled, and the kernel now provides a scheduling algorithm that runs in constant time-known as O (1)-regardless of the number of tasks on the system.
  • The new scheduler also provides increased support for SMP, including processor affinity and load balancing, as well as providing fairness and support for interactive tasks.
  • The Linux scheduler is a preemptive, priority-based algorithm with two separate priority ranges: a real-time range from 0 to 99 and a nice value ranging from 100 to 140.
  • These two ranges map into a global priority scheme wherein numerically lower values indicate higher priorities.

Figure 2.23 The relationship between priorities and time-slice length.

  • Unlike schedulers for many other systems, including Solaris and Windows XP, Linux assigns higher-priority tasks longer time quanta and lower-priority tasks shorter time quanta.
  • The relationship between priorities and time-slice length is shown in Figure 2.23.
  • A runnable task is considered eligible for execution on the CPU as long as it has time remaining in its time slice.
  • When a task has exhausted its time slice, it is considered expired and is not eligible for execution again until all other tasks have also exhausted their time quanta. The kernel maintains a list of all runnable tasks in a runqueue data structure.
  • Because of its support for SMP, each processor maintains its own runqueue and schedules itself independently.
  • Each runqueue contains two priority arrays: active and expired.
  • The active array contains all tasks with time remaining in their time slices, and the expired array contains all expired tasks.
  • Each of these priority arrays contains a list of tasks indexed according to priority (Figure 2.24).
  • The scheduler chooses the task with the highest priority from the active array for execution on the CPU.
  • On multiprocessor machines, this means that each processor is scheduling the highest-priority task from its own runqueue structure.
  • When all tasks have exhausted their time slices (that is, the active array is empty), the two priority arrays are exchanged; the expired array becomes the active array, and vice versa.


Figure 2.24 List of tasks indexed according to priority.

  • Linux implements real-time scheduling as defined by POSIX.1b, Real-time tasks are assigned static priorities.
  • All other tasks have dynamic priorities that are based on their nice values plus or minus the value 5. The interactivity of a task determines whether the value 5 will be added to or subtracted from the nice value.
  • A task's interactivity is determined by how long it has been sleeping while waiting for I/O. Tasks that are more interactive typically have longer sleep times and therefore are more likely to have adjustments closer to -5, as the scheduler favors interactive tasks.
  • The result of such adjustments will be higher priorities for these tasks.
  • Conversely, tasks with shorter sleep times are often more CPU-bound and thus will have their priorities lowered.
  • A task's dynamic priority is recalculated when the task has exhausted its time quantum and is to be moved to the expired array.
  • Thus, when the two arrays are exchanged, all tasks in the new active array have been assigned new priorities and corresponding time slices.

References

  1. The Operating System Concepts by Silberschatz, Galvin, Gagne, 8th Edition
  2. MODERN OPERATING SYSTEMS by Andrew S. Tanenbaum, Second Edition

Last modified: Sunday, 19 November 2017, 11:49 AM