Transcript SCHEDULING - Notesvillage

SYNCHRONIZATION
Module-4
scheduling
• Scheduling is an operating system mechanism
that arbitrate CPU resources between running
tasks
. Different scheduling algorithms are there
FCFS, SJF, priority based, pre-emptive, round
robin
Scheduling implementation
• Each platform provide native round robin
scheduling mechanism
• Different O.S may offer different
implementation of RR scheduling
• Preemptive O.s means, it allowed to interrupt
an executing task
Preemptive and non-preemptive O.S
• Preemptive means its allow an interruption of
current running task.
• It replaces another ready to run task
• In non-preemptive system, task execute up to
completion
Selecting which task to execute
• Scheduler also has the responsibility selecting
next available task to execute
• In Strict round robin next available task can
get from the run queue
• IBM OS/2, novell Unixware, windowsNT are all
priority based , preemptive, timesliced O.S
• Novell Netware3 and4 are non preemptive,
round robin scheduled O.S
Scheduler Responsibilities
•
•
•
•
•
CPU resource distribution
Maintaining Task queues
Switching the task or allocating CPU
Optionally provide priorities and preemption
It should be efficient and robust
Scheduler goals
1. Minimize the response time
To provide suitable response time,
preemption
and
priority
must
be
implemented.
2. Share the processor among tasks fairly
3. Making efficient use of the processor
4. Increase the throughput
Processing queues
• One of the most important job of scheduler is
to maintain circular queue of available tasks
• Number of queues is dependent on
Implementation
• scheduler consist of three queues
1.run queue
2. Ready queue
3.Idle(wait) queue
• Scheduler maintain list of tasks which may be
in one of three states
1.Ready to run tasks
list of active awaiting process called run
queue.
It is a round robin queue, managed using
FIFO list.
2. Task waiting for i/o operations
.i/o queues are used to maintain it
.single task system cpu idle while i/o
operations
. In multi tasking system, scheduler use the
processor when it wait for i/o
3.Idle task
wait queue used for it
. Idle task is a task which is not ready for
run and i/o operation
. Suspend thread(), sleep() or delay() used to
place task on wait queue
Context switching
• Its an essential operation for an O.S scheduler
• Task switch define as the work required to
switch the control from one task to another
• Amount of time required for switching is
critical
TaskSwitch()
{
Disableinterrupts()
SaveContext(currentTask)
SelectedTask = SelectNextRunnable(Runlist)
RemoveSelected(Runlist, selectedTask)
RestoreContext (selectedTask);
EnableInterrupts()
StartExecution()
}
Critical section
• Accessing or updating shared data
• Section of code that perform operation on the
shared data areas are known as critical section
task A
critical section
task B
One
at a time
access
CS require that only one task executing in them
at a time
Critical section problem
LONG STOCKquote;
Main() {
Begin(TaskA);
Begin(TaskB);
}
TaskA() {
………………
stockQuote = 29.875;
totalValue = numShares *stockQuote;
………
}
TaskB() {
………………
stockQuote = 100.125;
totalValue = numShares *stockQuote;
………
}
Mutual Exclusion
• One Task at a time access
• mutually exclusive means they cant execute
same operation concurrently
• Many ways to implement mutual exclusion
locking variables
disabling interrupt
using semaphore
semaphores
• Synchronize access of shared data
• Each O.S provide general semaphore
operation
• This variable is the controlling acces to the
shared resource and is maintained by
incrementing or decrementing its value:
• A value less than 0 indicates that process are
waiting for the shared resource or region.
• A value greater than 0 indicates that the
resource is available.
P() and V() Operation on Semaphores
• Dijkstra suggested having two operations on
the semaphore,p() and v() respectively .
• the p() operation decrements the semaphore
value by 1, while v() increments the
semaphore by 1.
• in Dijkstra’s orginal model, if the p() operation
caused the Semaphore to go to 0,the process
would spin –wait for the semaphore value to
be incremented with another v() operation.
• This caused the requesting process to wait for
completion of the region by another process.
• By extending the orginal model to allow the
semaphore to become negative and thus
queue up multiple waiting process, the
semaphore becomes more useful
• If during p() operation the semaphore value
becomes negative,the calling process is
blocked.
• any semaphore with a value less than 0
signifies that process are waiting.
• If as a result of a p() operation the semaphore
value is still > =0, the process is allowed
access to the region
LISTING 6.2
LONG stockQuote, totalValue, numShares;
Semaphore mutex = 1;
Main() {
Begin(TaskA);
Begin(TaskB);
}
TaskA() {
………
p(&mutex);
stockQuote = 29.875;
totalValue = numShares * stockQuote;
V(&mutex);
……….}
TaskB() {
………..
p(&mutex);
stockQuote = 100.125;
totalValue = numShates * stockQuote;
V(&mutex);}
Semaphore implementations
• Different types of implementations for
different platform
• Each O.S provides basic semaphore operations
for mutual exclusion
• some provide a richer set of functions for
extended semaphore operations
Novell Netware
• Novell implements two classes of semaphore
functions, local and network.
• Local semaphores are used for
synchronization and mutual exclusion by
programs running on NetWare servers as
NLMs.
• Network semaphores are a mechanism by
which a semaphore may be used by many
different computers throughout a network.
• Local semaphore

Local semaphores are an extremely
efficient operating system mechanism
It should be used to coordinate threads
running at the server
• Network semaphore
 network semaphores involve much more
overhead and possibly network transmissions
It should only be used to coordinate activity
between many systems
Microsoft NT
• Windows NT has a very extensive set of
synchronization options
• These options are provide by Microsoft in the
form of synchronization objects
• and can be used to synchronize events
between processes or threads
• There are four main synchronization objects
with WindowsNT:
1. Mutex
2. Semaphore
3. Event
4. Critical Section
• Each of these objects performs similar
functions in synchronization.