A PRACTICAL (COMPARATIVE) STUDY OF
SCHEDULING POLICIES
IN
LINUX AND WINDOWS 2k OPERATING SYSTEMS
*B.Madar
Abstract
Shared-memory multiprocessors are frequently used as compute servers with multiple parallel applications executing at the same time. In such environments, the efficiency of a parallel application can be significantly affected by the operating system scheduling policy.
It is common to evaluate scheduling policies based on their mean response times. Another important, but sometimes opposing, performance metric is a scheduling policy’s fairness.
Then, how do we evaluate a scheduling policy:
Ability to satisfy all deadlines.
CPU utilization—percentage of time devoted to useful work.
Scheduling overhead—time required to make scheduling decision.
We will concentrate on scheduling at the level of selecting among a set of ready processes. Scheduler is invoked whenever the operating system must select a user-level process to execute:
• After process creation/termination
• A process blocks on I/O
• I/O interrupt occurs
• Clock interrupt occurs (if preemptive).
Introduction on Scheduling Policies.
Types of processes:
• Interactive jobs
• low priority, cpu bound jobs that use excess processor capacity (e.g., calculating _ to
101000000 decimal places)
• Somewhere in between
Distinguish between a short and long process. Based on the time a process runs when it
gets the CPU. An I/O bound process is short and a CPU bound process is long.
Note; The idea of short vs. long is determined by how much of its time slice that a process uses, not the total amount of time it executes.
Criteria
Criteria for a good scheduling algorithm:
• Fairness: all processes get fair share of the CPU
• Efficiency: keep CPU busy 100% of time
• Response time: minimize response time
• Turnaround: minimize the time batch users must wait for output
• Throughput: maximize number of jobs per hour
They are competing. Fairness/efficiency, interactive/batch
Measurements
In order to compare different short-term policies, we need a measure of performance.
Assume that a process needs t time in execution before it leaves the ready list:
Execution time (t) — execution time
Response time (T) — finish time – arrival time. (Wall clock time)
Missed time (M) — T – t; time spend on the ready list or in blocked state.
Penalty ratio (P) — T/t; penalty of 1 ideal (lower penalty is good)
Response ratio (R) — t/T; response of 1 ideal (higher response is good)
Other useful measures:
• Kernel time — amount of time the spent by the kernel in making policy decisions and carrying them out. Context switching. A well tuned O.S. Uses between 10-30%.
• System time — kernel time devoted to a process.
• Idle time — amount of time spend when the ready list is empty. Thus running a
NULL process or running NULL routine code.
Scheduling Policies of LINUX OS
Linux offers 3 different ways to deal with scheduling, 2 of them for real-time applications and 1 for normal processes. A static priority value, sched_priority, ranging from 0 to 99, is assigned to each process. This static priority value can be changed only via system calls. The scheduler keeps a list of runnable processes with these priority values. The way Linux determines which process will be running next is by looking at such list for the highest priority number, and then takes the process at the head of the list. The scheduling policy determines where a process will be inserted in the event that it has an equal priority value with another process. Likewise, it will determine how it will move once inside the list.
Most processes use SCHED_OTHER which is the default universal time-sharing scheduler policy. Other most time-critical applications that require precise control use SCHED_FIFO and SCHED_RR. When using SCHED_OTHER, processes must be assigned an static priority value of 0. Otherwise, if using the two other algorithms, the priority value shall range from 1 to 99. Only such processes with super user privileges can have a priority value greater than 0, therefore they may use SCHED_FIFO and SCHED_RR.
All scheduling is preemptive, meaning that if a process with a higher priority is ready to run, the currently running process is preempted and taken to the wait list. It is the task of the scheduling policy to determine the ordering within the list of runnable processes with equal static priority value.
SCHED_FIFO: First In – First Out Scheduling
SCHED_FIFO is used only with priority values ranging from 1 to 99, that is, a SCHED_FIFO process ready to be run will always preempt a normal, SCHED_OTHER, process currently running. SCHED_FIFO does not deal with time slicing. If a SCHED_FIFO process has been preempted by a higher priority process, it will go to the top of the wait list and will resume running as soon as all processes with higher priority values have been blocked.
SCHED_RR: Round Robin Scheduling
SCHED_RR works just like SCHED_FIFO, but with one difference: each SCHED_RR process is allowed to run for a specified time quantum. As soon as a running process reaches its allotted time quantum it will be put back at the end of the same-priority-value list. If a SCHED_RR process has been preempted by a higher value priority process, it will complete the unexpired portion of its allotted time quantum when it resumes execution.
SCHED_OTHER: Default Linux Time-Sharing Scheduling
This is the usual time-sharing scheduling algorithm used for all normal processes, or processes that do not require special static priority real-time mechanisms. The process that runs is determined by a dynamic priority inside the list of the same static priority values processes, namely 0. The dynamic priority is based on the nice level and increased for each time quantum the process is ready to run, but denied to run by the scheduler. This way ensures fairness among all static priority 0 processes.
Nice Level – the ‘nice’ command changes the priority level value of a process. The priority that may be adjusted by ‘nice’ runs from -20, the highest, to 19 the lowest.
IMPLEMENTATION
Each of the three programs in both, the Kernel and User Levels, was run 25 times, which produced varying time results depending on the random numbers generated by them. An average was computed of these 25 results to come up with a final result for each algorithm.
The time was accurately measured using the following commands:
start_time = clock ();
end_time = clock ();
cpu_time_used = ((double) (end_time – start_time)) / CLOCKS_PER_SEC;
system (“date”);
IMPLEMENTATION OF SCHEDULING AT KERNEL LEVEL
SCHED_FIFO: First In – First Out Scheduling
Three different programs were written in C to implement and test the FIFO algorithm. Each program creates 10 threads, and each thread, in turn, generates between 300,000 and 3,000,000 random numbers so they utilize CPU resources in varying time slots.
A completely different program from the ones indicated in the paragraph above runs the 3 main programs.
SCHED_RR: Round Robin Scheduling
Three different programs were written in C to implement and test the Round Robin algorithm. Each program creates 10 threads, and each thread, in turn, generates between 300,000 and 3,000,000 random numbers so they utilize CPU resources in varying time slots.
A completely different program from the ones indicated in the paragraph above runs the 3 main programs.
SCHED_OTHER: Default Linux Time-Sharing Scheduling
Three different programs were written in C to implement and test the other algorithm. Each program creates 10 threads, and each thread, in turn, generates between 300,000 and 3,000,000 random numbers so they utilize CPU resources in varying time slots.
A completely different program from the ones indicated in the paragraph above runs the 3 main programs.
IMPLEMENTATION OF SCHEDULING AT USER LEVEL
SCHED_FIFO: First In – First Out Scheduling
Three different programs were written in C to implement and test the FIFO algorithm. Each program creates 10 threads, and each thread, in turn, increases or decreases the number of random numbers by a random number so each utilizes CPU resources in varying time slots.
A completely different program from the ones indicated in the paragraph above runs the 3 main programs.
Shortest Job Fist Scheduling
Three different programs were written in C to implement and test the Shortest Job First algorithm. Each program creates 10 threads, and each thread, in turn, increases the number of random numbers so they utilize CPU resources in varying time slots.
A completely different program from the ones indicated in the paragraph above runs the 3 main programs.
Longest Job Fist Scheduling
Three different programs were written in C to implement and test the Shortest Job First algorithm. Each program creates 10 threads, and each thread, in turn, decreases the number of random numbers so they utilize CPU resources in varying time slots.
A completely different program from the ones indicated in the paragraph above runs the 3 main programs.
TEST RESULTS
After running each of the programs for each of the algorithms 25 times, as specified earlier, the average time results have been placed in the table below:
Program 1
Time (secs)
Program 2
Time (secs)
Program 3
Time (secs)
TOTAL
TIME (secs)
sched_setscheduler (pid, SCHED_FIFO, &p)
31
11
8
50
sched_setscheduler (pid, SCHED_FIFO, &p)
31
11
8
50
sched_setscheduler (pid, SCHED_RR, &p)
17
13
18
48
sched_setscheduler (pid, SCHED_OTHER, &p)
29
11
11
51
SJF
40
31
30
101
LJF
36
32
29
97
Scheduling in Windows 2000
Windows 2000 schedules at the thread granularity.
Priority-driven, preemptive scheduling system
The highest-priority runnablethread always runs.
Time-sliced, round-robin within a priority level.
Windows 2000 uses 32 priority levels
System level (0), Variable levels (1-15), Real-time levels (16-31)
from Win32 point of view
Processes are given a priority class upon creation:
Idle, Below Normal, Normal, Above Normal, High, Real-time
Changeable by Task Manager.
The individual threads have a relative priority within the class:
Idle, Lowest, Below-Normal, Normal, Above Normal, Highest, Time-Critical.
Quantum in Windows 2000
By default, threads start with a quantum value of
6 on Windows 2000 Professional
36 on Windows 2000 Server
The rationale for longer default value on Windows 2k Server is to minimize context switching.
Each time the clock interrupts, the clock-interrupt routine deducts a fixed value (3) from the thread quantum.
The clock interval for most x86 uniprocessorsis 10ms, and for most x86 multiprocessors, 15ms.
Partial quantum decay–The reason quantum is expressed in terms of a multiple of 3 quantum units per clock tick is to allow for partial quantum decay on wait completion.–When a thread executes a wait function, its quantum is reduced by 1 quantum unit. –This partial decay addresses the case in which a thread enters a wait state before the clock interval timer fires.–If this adjustment is not made, it would be possible for threads never to have their quanta reduced.
•Foreground quantum boost
–The field is an index into a three-entry quantum table used to obtain the quantum for the threads in the foreground process.
•The value of 3 is invalid and treated as 2.
–The quantum for threads in background processes is taken from the first entry in this quantum table.
–The foreground process is the process that owns the thread that owns the window that’s in focus.
CONCLUSIONS
The results at the Kernel Level were much better for the Round Robin algorithm and much worse for the other algorithm.
The results at the User Level were best for LJF and worst for SJF.
Scheduling performance criteria and goals are dependent on environment
There exist several different algorithms targeted for various systems
Traditional OSes like Windows, Linux, Unix….Usually uses a priority level algorithms
We conclude that there exists a false dichotomy between schedulers based on proportional share techniques and schedulers. The important question is not which class of algorithms is better, but rather, for a given operating system and set of applications,
(1) to what degree must existing infrastructure such as a periodic timer interrupt and system for manipulating priorities be utilized; (2) how much pessimism and context switch overhead is acceptable; and, (3) what scheduling parameters can the developers of real-time applications be reasonably expected to provide?
BIBLIOGRAPHY
1. Operating Systems Class Website
2.Operating Systems, Harvey M. Deitel, Paul J. Deitel, David R. Choffnes, Third Edition
3.Understanding the Linux Kernel, O’Reilly Online Catalog
4.Linux Process Scheduling
5.Linux Process Scheduling – Summary.
6. Various websites related to OS
* Faculty in Alluri Institute of Management Sciences, Hunter Road Warangal,Andhra Pradesh-506001
