A PRACTICAL (COMPARATIVE) STUDY OF SCHEDULING POLICIES IN LINUX AND WINDOWS 2K OPERATING SYSTEMS
A PRACTICAL (COMPARATIVE) STUDY OF
SCHEDULING POLICIES
IN
LINUX AND WINDOWS 2k OPERATING SYSTEMS
*B.Madar
Abstract
Shared-memory multiprocessors are often utilised as compute servers with a number of parallel applications executing at the very same time. In such environments, the efficiency of a parallel application can be drastically affected by the operating system scheduling policy.
It is typical to evaluate scheduling policies based on their mean response instances. Another important, but at times opposing, performance metric is a scheduling policy’s fairness.
Then, how do we evaluate a scheduling policy:
Capacity to satisfy all deadlines.
CPU utilization—percentage of time devoted to useful work.
Scheduling overhead—time essential to make scheduling choice.
We will concentrate on scheduling at the level of choosing amongst a set of ready processes. Scheduler is invoked whenever the operating program need to pick a user-level approach to execute:
• Right after approach creation/termination
• A process blocks on I/O
• I/O interrupt occurs
• Clock interrupt occurs (if preemptive).
Introduction on Scheduling Policies.
Kinds of processes:
• Interactive jobs
• low priority, cpu bound jobs that use excess processor capacity (e.g., calculating _ to
101000000 decimal locations)
• Someplace in in between
Distinguish in between a short and extended procedure. Based on the time a method runs when it
gets the CPU. An I/O bound approach is brief and a CPU bound procedure is long.
Note; The concept of brief vs. lengthy is determined by how a lot of its time slice that a process uses, not the total quantity of time it executes.
Criteria
Criteria for a excellent scheduling algorithm:
• Fairness: all processes get fair share of the CPU
• Efficiency: keep CPU busy 100% of time
• Response time: reduce response time
• Turnaround: decrease the time batch users need to wait for output
• Throughput: maximize amount of jobs per hour
They are competing. Fairness/efficiency, interactive/batch
Measurements
In order to evaluate different short-term policies, we want a measure of efficiency.
Assume that a procedure needs t time in execution prior to 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 excellent)
Response ratio (R) — t/T; response of 1 ideal (larger response is good)
Other useful measures:
• Kernel time — amount of time the spent by the kernel in creating policy decisions and carrying them out. Context switching. A well tuned O.S. Makes use of between 10-30%.
• Program time — kernel time devoted to a process.
• Idle time — amount of time invest when the ready list is empty. Thus running a
NULL procedure or running NULL routine code.
Scheduling Policies of LINUX OS
Linux provides three different methods to deal with scheduling, 2 of them for actual-time applications and 1 for normal processes. A static priority value, sched_priority, ranging from to 99, is assigned to each approach. This static priority value can be changed only by way of method calls. The scheduler keeps a list of runnable processes with these priority values. The way Linux determines which approach will be running next is by looking at such list for the highest priority quantity, and then takes the process at the head of the list. The scheduling policy determines where a method 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-vital applications that demand precise control use SCHED_FIFO and SCHED_RR. When using SCHED_OTHER, processes need to be assigned an static priority value of . 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 higher than , as a result they might use SCHED_FIFO and SCHED_RR.
All scheduling is preemptive, meaning that if a approach with a higher priority is prepared to run, the presently running approach is preempted and taken to the wait list. It is the job of the scheduling policy to establish the ordering within the list of runnable processes with equal static priority value.
SCHED_FIFO: Initial In – 1st 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 regular, SCHED_OTHER, procedure currently running. SCHED_FIFO does not deal with time slicing. If a SCHED_FIFO method has been preempted by a higher priority approach, it will go to the top of the wait list and will resume running as soon as all processes with increased priority values have been blocked.
SCHED_RR: Round Robin Scheduling
SCHED_RR works just like SCHED_FIFO, but with one distinction: each SCHED_RR method 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 identical-priority-value list. If a SCHED_RR approach has been preempted by a greater value priority approach, 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 typical time-sharing scheduling algorithm utilized for all normal processes, or processes that do not demand unique static priority actual-time mechanisms. The approach that runs is determined by a dynamic priority inside the list of the exact same static priority values processes, namely . The dynamic priority is based on the nice level and increased for each time quantum the approach is prepared to run, but denied to run by the scheduler. This way ensures fairness among all static priority processes.
Good Level – the ‘nice’ command modifications the priority level value of a process. The priority that may well be adjusted by ‘nice’ runs from -20, the highest, to 19 the lowest.
IMPLEMENTATION
Every of the 3 programs in both, the Kernel and User Levels, was run 25 occasions, which produced varying time outcomes depending on the random numbers generated by them. An average was computed of these 25 results to come up with a final outcome for every algorithm.
The time was accurately measured making use of the following commands:
start_time = clock ();
end_time = clock ();
cpu_time_employed = ((double) (finish_time – commence_time)) / CLOCKS_PER_SEC;
program (“date”);
IMPLEMENTATION OF SCHEDULING AT KERNEL LEVEL
SCHED_FIFO: 1st In – Initial Out Scheduling
3 different programs were written in C to implement and test the FIFO algorithm. Every single program creates 10 threads, and every thread, in turn, generates between 300,000 and three,000,000 random numbers so they utilize CPU resources in varying time slots.
A completely various plan from the ones indicated in the paragraph above runs the 3 main programs.
SCHED_RR: Round Robin Scheduling
Three various programs had been written in C to implement and test the Round Robin algorithm. Each and every program creates 10 threads, and every single thread, in turn, generates in between 300,000 and three,000,000 random numbers so they utilize CPU resources in varying time slots.
A fully distinct plan from the ones indicated in the paragraph above runs the three primary programs.
SCHED_OTHER: Default Linux Time-Sharing Scheduling
Three distinct programs had been written in C to implement and test the other algorithm. Each and every system creates 10 threads, and each and every thread, in turn, generates between 300,000 and three,000,000 random numbers so they make use of CPU resources in varying time slots.
A completely different system from the ones indicated in the paragraph above runs the 3 principal programs.
IMPLEMENTATION OF SCHEDULING AT USER LEVEL
SCHED_FIFO: Very first In – Initial Out Scheduling
Three distinct programs were written in C to implement and test the FIFO algorithm. Every plan creates 10 threads, and every single thread, in turn, increases or decreases the quantity of random numbers by a random quantity so every utilizes CPU resources in varying time slots.
A totally different program from the ones indicated in the paragraph above runs the 3 principal programs.
Shortest Job Fist Scheduling
Three various programs had been written in C to implement and test the Shortest Job Very first algorithm. Each system creates 10 threads, and each and every thread, in turn, increases the amount of random numbers so they make use of CPU resources in varying time slots.
A fully diverse system from the ones indicated in the paragraph above runs the three major programs.
Longest Job Fist Scheduling
3 various programs were written in C to implement and test the Shortest Job Initial algorithm. Every single system creates 10 threads, and every thread, in turn, decreases the quantity of random numbers so they utilize CPU resources in varying time slots.
A entirely different program from the ones indicated in the paragraph above runs the 3 major programs.
TEST Results
After running every of the programs for every of the algorithms 25 instances, as specified earlier, the common time outcomes have been placed in the table beneath:
Plan 1
Time (secs)
Plan 2
Time (secs)
Program three
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 program
The highest-priority runnablethread always runs.
Time-sliced, round-robin inside a priority level.
Windows 2000 uses 32 priority levels
Program level (), Variable levels (1-15), Actual-time levels (16-31)
from Win32 point of view
Processes are given a priority class upon creation:
Idle, Beneath Regular, Standard, Above Regular, High, Genuine-time
Changeable by Activity Manager.
The individual threads have a relative priority inside the class:
Idle, Lowest, Below-Standard, Standard, Above Normal, Highest, Time-Vital.
Quantum in Windows 2000
By default, threads commence with a quantum value of
6 on Windows 2000 Expert
36 on Windows 2000 Server
The rationale for longer default value on Windows 2k Server is to decrease 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 numerous of three quantum units per clock tick is to permit for partial quantum decay on wait completion.–When a thread executes a wait function, its quantum is decreased by 1 quantum unit. –This partial decay addresses the situation in which a thread enters a wait state prior to the clock interval timer fires.–If this adjustment is not produced, it would be probable for threads never to have their quanta diminished.
•Foreground quantum boost
–The field is an index into a 3-entry quantum table employed to obtain the quantum for the threads in the foreground method.
•The value of 3 is invalid and treated as 2.
–The quantum for threads in background processes is taken from the 1st entry in this quantum table.
–The foreground procedure is the procedure that owns the thread that owns the window that’s in focus.
CONCLUSIONS
The results at the Kernel Level had been much better for the Round Robin algorithm and significantly worse for the other algorithm.
The final results at the User Level were greatest for LJF and worst for SJF.
Scheduling performance criteria and goals are dependent on atmosphere
There exist several diverse algorithms targeted for numerous systems
Standard OSes like Windows, Linux, Unix….Normally uses a priority level algorithms
We conclude that there exists a false dichotomy in between schedulers based on proportional share techniques and schedulers. The critical question is not which class of algorithms is far better, but rather, for a given operating program and set of applications,
(1) to what degree ought to existing infrastructure such as a periodic timer interrupt and program 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 present?
BIBLIOGRAPHY
1. Operating Systems Class Site
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 Procedure Scheduling
five.Linux Procedure Scheduling – Summary.
6. A variety of sites associated to OS
* Faculty in Alluri Institute of Management Sciences, Hunter Road Warangal,Andhra Pradesh-506001
A lot more Time-share Articles Purchasing Timeshare
Posted in 
Tags: 
