Compare
cpu scheduling of linux and windows
ACKNOWLEGMENT
I
mohd sharique ansari of B tech-M Tech (CSE) would like to thank my teacher of
numerical analysis Mr. RK Gupta who helped me throughout the development of
this paper in best possible way. I would like appreciate the dedication and
sincerity of my teacher for his guidance without whom this paper would not been
possible.
At
last I would like to thank all my friends for their support.
INTRODUCTION
CPU SCHEDULING:
Scheduling
basically deals with the selection of a process that exists in the memory and
ready to execute. The selected process is allocated with the CPU. This function
is performed by the CPU scheduler. The CPU scheduler makes a sequence of
“moves” that determines the interleaving of threads.
- Programs use synchronization to prevent “bad moves”.
- …but otherwise scheduling choices appear (to the program) to be nondeterministic.
The
scheduler's moves are dictated by a scheduling policy.
A
general overview of the scheduling is depicted by the below representation:
Windows process
scheduling
1)
Windows 3.1 xs used a non-preemptive scheduler, meaning that it did not
interrupt programs. It relied on the program to end or tell the OS that it
didn't need processor so that it could move on to another process. This is
usually called cooperative multitasking. Windows 95 introduced a rudimentary
preemptive scheduler; however, for legacy support opted to let 16 bit
applications run without preemption
2)
NT-based versions of Windows use a CPU scheduler based on a multilevel feedback
queue, with 32 priority levels defined. It is intended to meet the following
design requirements for multimode systems:
1.
Give preference to short
jobs.
2.
Give preference to I/O
bound processes.
3.
Quickly establish the
nature of a process and schedule the process accordingly.
All
processes receive a priority boost after a wait event, but processes that have
experienced a keyboard I/O wait get a larger boost than those that have
experienced a disk I/O wait.
“Foreground”
processes given higher priority.
3)
Windows XP uses a quantum-based, preemptive priority scheduling algorithm. The
scheduler was modified in Windows Vista to use the cycle counter register of
modern processors to keep track of exactly how many CPU cycles a thread has
executed, rather than just using an interval-timer interrupt routine.
Linux Process Scheduling
From
versions 2.6 to 2.6.23, the kernel used an O (1) scheduler. The Completely Fair
Scheduler is the name of a task scheduler which was merged into the 2.6.23
release of the Linux kernel. It handles CPU resource allocation for executing
processes, and aims to maximize overall CPU utilization while maximizing
interactive performance. It uses that uses red-black trees instead of queues.
Two
classes of processes:
- real-time (soft deadlines)
- timesharing algorithm
Normal
process scheduling uses a prioritized, preemptive, credit-based policy:
- Scheduler always chooses process with the most credits to run.
- On each timer interrupt one credit is deducted until zero is reached at which time the process is preempted.
- If no ready process then all credits for a process calculated as credits = credits/2 + priority.
- This approach favors I/O bound processes which do not use up their credits when they run.
The
Round Robin and FIFO scheduling algorithms are used to switch between real-time
processes
Windows is by far the
most popular proprietary personal computer operating system, while Linux is the
most prominent free software operating system.
|
Windows
|
Linux
|
|
1)Process
a)Address space,
handle table, statistics and at least one thread
b)No inherent
parent/child relationship
|
1) Process is called a Task
a)Basic Address
space, handle table, statistics
b)Parent/child
relationship
c)Basic scheduling
unit
|
|
2) Threads
a) Basic scheduling
unit
b) Fibers -
cooperative user-mode threads
|
2) Threads
a)No threads per-se
b)Tasks can act like
Windows threads by sharing handle table, PID and address space
c)P-Threads -
cooperative user-mode threads
|
|
3)windowing
Windows has a
kernel-mode Windowing subsystem.
|
3)windowing
Linux has a user-mode X-Windowing
system.
|
|
4)Two scheduling classes
a)“Real time”
(fixed) - priority 16-31
b) Dynamic -
priority 1-15
|
4)Has 3 scheduling classes
a)Normal - priority
100-139
b)Fixed Round Robin
- priority 0-99
c)Fixed FIFO -
priority 0-99
|
|
5)Higher priorities are favored
a) Priorities of
dynamic threads get boosted on wakeups
b)Thread priorities
are never lowered
|
5)Lower priorities are favored
a) Priorities of
normal threads go up (decay) as they use CPU
b)Priorities of
interactive threads go down (boost)
|
|
6)Most threads run in variable priority levels
a)Priorities 1-15;
b)A newly created
thread starts with a base priority
c)Threads that
complete I/O operations experience priority boosts (but never higher than 15)
d)A thread's
priority will never be below base priority
|
6)Most threads use a dynamic priority policy
a)Normal class -
similar to the classic UNIX scheduler
b)A newly created
thread starts with a base priority
c)Threads that block
frequently (I/O bound) will have their priority gradually increased
d)Threads that
always exhaust their time slice (CPU bound) will have their priority
gradually decreased
|
|
7)The Windows API function SetThreadPriority()
sets the priority value for a specified thread
a)This value,
together with the priority class of the thread's process, determines the thread's
base priority level
b)Windows will
dynamically adjust priorities for non-real-time threads
|
7)“Nice value” sets a thread's base priority
a)Larger values =
less priority, lower values = higher priority
b)Valid nice values
are in the range of -20 to +20
c)Non-privileged
users can only specify positive nice value
|
|
8) Real time scheduling in windows.
Windows xp supports
static round-robin scheduling policy for threads with priorities in real-time
range (16-31)
a) Threads run for
up to one quantum.
b) Quantum is reset
to full turn on preemption.
c) Priorities never
get boosted.
9) RT threads can starve important system
services such as CSRSS.EXE
Se-Increase Base
Priority Privilege is required to elevate a thread's priority into real-time
range.
|
8) Real time scheduling in Linux.
Linux supports two
static priority scheduling policies: Round-robin and FIFO (first in, first
out)
a) Selected with the
sched-setscheduler( ) system call
b) Use static
priority values in the range of 1 to 99
c) Executed strictly
in order of decreasing static priority
9) RT threads can easily starve lower-priority
threads from executing
Root privileges or
the CAP-SYS-NICE capability are required for the selection of a real-time
scheduling policy
|
|
10) Some System calls and DPC/APC handling can
cause priority inversion
|
10) Long running system calls can cause
priority-inversion
|
|
11) Scheduling timeslices in windows
The thread time
slice (quantum) is 10ms-120ms
a)When quanta can
vary, has one of 2 values
|
11) Scheduling timeslices in Linux.
The thread quantum
is 10ms-200ms
a)Default is 100ms
b)Varies across
entire range based on priority, which is based on interactivity level
|
|
12) Windows NT has always had an O (1) scheduler
based on pre-sorted thread priority queues.
|
12) The Linux 2.4 scheduler is O(n)
If there are 10
active tasks, it scans 10 of them in a list in order to decide which should
execute next
This means long
scans and long durations under the scheduler lock
|
|
13) In windows (vista sp1) the time-slice varies
-manual (user setting, window boost) as well as automatic (window boost).
|
13) In Linux 2.6.28 the time-slice does not vary-
manual(user setting, window boost) and automatic (window boost).
|
|
14) In windows (vista sp1) CPU partitioning is
not possible.
|
14) In Linux 2.6.28 CPU partitioning (CPU sets)
is possible.
|
|
15) Scheduler load balancing is not possible.
|
15) Scheduler load balancing is possible.
|
Posts
0 comments:
Post a Comment