• Post Reply Bookmark Topic Watch Topic
  • New Topic

preemptive scheduler  RSS feed

 
abalfazl hossein
Ranch Hand
Posts: 635
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I search about "preemptive scheduler", But I really confuse...

http://www.janeg.ca/scjp/threads/scheduling.html
In preemptive scheduling the highest priority thread continues to
run until it dies, waits, or is preempted by a thread of higher priority


But When I read IBM site
http://www.ibm.com/developerworks/library/j-thread.html
Under the preemptive threading model, the OS interrupts threads
at any time, usually after allowing them to run for a period of time
(known as a time-slice)



http://life.csu.edu.au/java-tut/essential/threads/priority.html

If at any time a thread with a higher priority than all other
Runnable threads becomes Runnable,
the runtime system chooses the new higher-priority
thread for execution. The new thread is said to preempt
the other threads.


I think that
It is better to say, " it preempts the resource" Right?
 
abalfazl hossein
Ranch Hand
Posts: 635
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
There is a question about this word : "preemptive"

Definition of preemptive scheduling:

Under the preemptive threading model, the OS interrupts threads at any time, usually after allowing them to run for a period of time (known as a time-slice)


Definition of Non-preemptive scheduling:

a thread runs until it terminates,stops, blocks,suspends, or yields


I think that the second definition is better and suitcase for "preemptive scheduling"

Because we can say:

The thread preempts the cpu, and other threads can not access it, until it terminates. Right?

 
Henry Wong
author
Sheriff
Posts: 23282
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

"Preemptive" just means that there is some sort of hardware support to get a higher priority thread onto a processor core, as soon as it is runnable.

It doesn't mean that, without it, there is no time slicing. As it is possible for processors to time slice using other means, such as a timer interrupt.

It doesn't mean that a higher priority thread can be starved by a lower priority thread, as a timer interrupt can be used to check to see a higher priority thread becomes runnable.

It just means that without "preempting", the higher priority thread may have to wait a bit.

Henry
 
abalfazl hossein
Ranch Hand
Posts: 635
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks Sir,

My 100th post in this forum!

May you answer my first post about definition please?Which one is correct?Definition of IBM?or JAVA quick reference?

 
abalfazl hossein
Ranch Hand
Posts: 635
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What is the definition of preemptive scheduling?

 
abalfazl hossein
Ranch Hand
Posts: 635
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Time slice is only for preemptive scheduling?



Of course I am still searching, nights and nights!

and tonight, I find something nice!But still I have doubt

In preemptive scheduling we preempt the currently executing process.
In non preemptive we allow the current process to finish its cpu burst time.


http://wiki.answers.com/Q/Two_differences_between_preemptive_and_non_preemptive_scheduling

In fact this is OS that preempts, Isn't?

Is there anyone to answer me?
 
Paul Clapham
Sheriff
Posts: 22379
42
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
abalfazl hossein wrote:In fact this is OS that preempts, Isn't?


Well, of course. It's the OS which controls which threads get to run, so naturally it would be the OS that decides to stop one thread from running and allow a different thread to run. What else could it be?
 
abalfazl hossein
Ranch Hand
Posts: 635
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Let's read the definitions again:

1-

In preemptive scheduling the highest priority thread continues to
run until it dies, waits, or is preempted by a thread of higher priority

2-

Under the preemptive threading model, the OS interrupts threads
at any time, usually after allowing them to run for a period of time
(known as a time-slice)


run until it dies VS the OS interrupts threads at any time, (as a time-slice)

I see incoherent,

Which one is correct?Please give me a straight answer
 
Henry Wong
author
Sheriff
Posts: 23282
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
To preempt, is the definition that I gave in an earlier post. For sanity purposes, let's just call this a "feature".

A preemptive scheduler is simply a scheduler that supports that feature. It may also supports tons of other features. And for schedulers that don't support that feature, they may have found other ways around it.

Also, you need to keep a distinction between this and how a scheduler behaves. Just because it can preempt a thread doesn't mean it will do it to perform a behavior.

So....

In preemptive scheduling the highest priority thread continues to run until it dies, waits, or is preempted by a thread of higher priority


Whether the highest priority threads keep running til it dies, get time sliced with other equally priority threads, or even get time sliced with lower priority threads, has nothing to do with the preempt feature. Although, having the ability to preempt (feature) does make supporting the behavior easier.

Example: Windows has a preemptive scheduler, that will on occasion, allow a lower priority thread to run over a higher priority thread. This is done to mitigate thread starvation. It basically time slices, but gives a smaller slice to starving lower priority threads.


Under the preemptive threading model, the OS interrupts threads at any time, usually after allowing them to run for a period of time (known as a time-slice)


Time slicing is a behavior. Windows, Solaris, Linux, etc. will all time slice, and they all do so in a preemptive manner. But they don't have to. Older operation systems simulate time slicing -- either by trapping the I/O or other blocking operations. Or use some sort of timer interrupt.

abalfazl hossein wrote:
run until it dies VS the OS interrupts threads at any time, (as a time-slice)
I see incoherent,

Which one is correct?


Well, neither is incorrect. You are confusing behavior with the feature. And you are also probably taking out-of-context, of description of schedulers that behave that way. I am pretty sure both documents describe preemptive schedulers that behave that way.

Henry
 
abalfazl hossein
Ranch Hand
Posts: 635
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
All right!

Now I tell my definition, Please tell me is it right or not:

In preemptive scheduling , A thread continues to run on CPU,Until its time slice be finished,or until it dies, waits, or is preempted by a thread of higher priority.We call it preemptive , Because this the time scheduler of OS that decide and control thread and preempt the thread,to allow the thread with higher priority runs.But, even preemptive scheduling tries the thread with higher priority runs on CPU,But if the thread with higher priority, does not finish the job at the time slice,It will go to ready state and another thread will be run.

In Non-preemptive scheduling,There is no time slice, A thread continues until thread finished the job.Even if there's a thread with higher priority,It must wait until the thread that runs on CPU finish its job.


Is what I said right?
 
abalfazl hossein
Ranch Hand
Posts: 635
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What is the role of priority in Non-preemptive scheduler?

May someone answer my questions?
 
Henry Wong
author
Sheriff
Posts: 23282
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
abalfazl hossein wrote:
In Non-preemptive scheduling,There is no time slice, A thread continues until thread finished the job.Even if there's a thread with higher priority,It must wait until the thread that runs on CPU finish its job.

Is what I said right?



No. Read my previous post again. Non-preemptive does *not* mean no time-slice. It is possible to have time slicing using other means.

Henry
 
Henry Wong
author
Sheriff
Posts: 23282
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
abalfazl hossein wrote:What is the role of priority in Non-preemptive scheduler?


The same role as with a preemptive scheduler.

Henry
 
abalfazl hossein
Ranch Hand
Posts: 635
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks for replying.

I read again your post.Excuse me,May you explain more about Non-preemptive,and its main difference with preemptive please?

Thanks in advance
 
abalfazl hossein
Ranch Hand
Posts: 635
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Four conditions enable the posibility for deadlock:
- Mutual exclusion: It must not be possible for more than one thread to use a resource at the same time.

-No preemption: It must not be possible to remove a resource from a thread that holds it. Only the thread that holds a resource can give it up........


Then, according to this, deadlock never happened in preemptive system. Right?
 
abalfazl hossein
Ranch Hand
Posts: 635
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Anyone may explain how deadlock happen in preemptive system?
 
Henry Wong
author
Sheriff
Posts: 23282
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
abalfazl hossein wrote:Anyone may explain how deadlock happen in preemptive system?


I think that you may be confusing two different contexts. And since I don't know where you are quoting from, I can only guess that the term "preempt" may be overloaded with a different meaning.

Deadlock and scheduling have little, in terms of effect, regarding each other. It is possible to deadlock regardless of whether the scheduler is preemptive or not. And there is nothing about a preemptive (or non-preemptive) scheduler that would prevent or promote deadlocks.

Henry
 
Henry Wong
author
Sheriff
Posts: 23282
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
abalfazl hossein wrote:
I read again your post.Excuse me,May you explain more about Non-preemptive,and its main difference with preemptive please?


How can I "explain more" when I have no idea of what you didn't understand of the previous post?

Henry
 
abalfazl hossein
Ranch Hand
Posts: 635
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think that you may be confusing two different contexts. And since I don't know where you are quoting from, I can only guess that the term "preempt" may be overloaded with a different meaning.


Please read chapter 3 from this link:
http://java.sun.com/developer/Books/performance2/


n a preemptive scheduling. A thread is forced to give the resource, But in Non-preemptive, a thread give up the resource itself.

In preemptive scheduling,Because of OS forces thread to release the resource,Then the other threads can access that resource.then deadlock can not happened.
 
Henry Wong
author
Sheriff
Posts: 23282
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
abalfazl hossein wrote:
In preemptive scheduling,Because of OS forces thread to release the resource,Then the other threads can access that resource.then deadlock can not happened.


Why don't you try it yourself?

Take 10 minutes to write a test application that deadlocks. And test it out on the latest JVMs. You will see that it does indeed deadlock.

Henry
 
Henry Wong
author
Sheriff
Posts: 23282
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
abalfazl hossein wrote:
In preemptive scheduling,Because of OS forces thread to release the resource,Then the other threads can access that resource.then deadlock can not happened.


And BTW, the purpose of a lock is to prevent other threads from seeing the data in an interim state. Basically, to make the operation atomic.

If the scheduler implicitedly releases the lock, what would be the purpose of synchronization? As it would be possible to see the data in an interim state.

Henry
 
abalfazl hossein
Ranch Hand
Posts: 635
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I can only guess that the term "preempt" may be overloaded with a different meaning.


May you tell me what do you mean "preempt" in that chapter, Please?

and thank you very much for answers.
 
abalfazl hossein
Ranch Hand
Posts: 635
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
still waiting for answer. What does "preempt" mean in those conditions?





Four Conditions of Deadlock
Four conditions enable the possibility for deadlock:

• Mutual exclusion: It must not be possible for more than one thread to use a resource at
the same time

• Hold and wait: Threads must hold resources and wait for others to become available.
Deadlock is not possible if no thread ever holds more than one resource at a time. Nor
is it possible if a thread can acquire more than one resource, but acquires all its
resources at one instant.
• No preemption: It must not be possible to remove a resource from a thread that holds
it. Only the thread that holds a resource can give it up.
• Circular wait: There must be a cycle of threads, each holding at least one resource and
waiting to acquire one of the resources that the next thread in the cycle holds.
If any of the foregoing conditions is enforced, deadlock simply cannot occur. This idea
comes from operating systems literature (textbooks).
 
Henry Wong
author
Sheriff
Posts: 23282
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
abalfazl hossein wrote:What does "preempt" mean in those conditions?


In this context, "preempt" simply means that the thread can be forced to give up the resource. And in this case, the resource is a lock.

This is similar (but different) from the "preempt" in the preemptive scheduler, where the resource is the time slice (or the CPU).


In other words, this context is not the same as preemptive scheduling. And preemptive scheduling and deadlock have little to do with each other.

Henry
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!