Hi,
can anybody explain … how OS implements Semaphores , Mutexes , Events —
I mean Semaphore in terms of Priority Inversion … what and how does that
inversion really take place …
–Arup
Events, Semaphores and Mutexes are Dispatcher Objects…Two structure
called DISPATCHER_HEADER and KWAIT_BLOCK are used to implement Waitings.
DISPATCHER_HEADER says what is the object type, its signal state and which
threads are waiting on this object (a linked list). Each Dispatcher Object
contains a DISPATCHER_HEADER member.
KWAIT_BLOCK represents a thread waiting on an object. A Thread has got list
of wait blocks the thread is waiting on.
You can see members of these structures in your debugger (WDBG) by loading
the OEM debugging extensions into your debugger.
Read the Book Inside W2k for more details.
Johnny
-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of Arup Banerjee
Sent: Mittwoch, 1. Mai 2002 06:37
To: NT Developers Interest List
Subject: [ntdev] How does OS implements Semaphore
Hi,
can anybody explain … how OS implements Semaphores , Mutexes ,
Events — I mean Semaphore in terms of Priority Inversion … what and how
does that inversion really take place …
–Arup
You are currently subscribed to ntdev as: xxxxx@yahoo.de
To unsubscribe send a blank email to %%email.unsub%%
The low-priority thread have grabbed some mutex.
The high-priority thread is waiting on it. This is an inversion.
Max
----- Original Message -----
From: Arup Banerjee
To: NT Developers Interest List
Sent: Wednesday, May 01, 2002 8:36 AM
Subject: [ntdev] How does OS implements Semaphore
Hi,
can anybody explain … how OS implements Semaphores , Mutexes , Events — I mean Semaphore in terms of Priority Inversion … what and how does that inversion really take place …
–Arup
You are currently subscribed to ntdev as: xxxxx@storagecraft.com
To unsubscribe send a blank email to %%email.unsub%%
Max,
the priority inversion problem would just accur, if the low-priority thread
is holding the mutex and is preemped by Scheduler when an other
higher-priority thread is ready to run or it transits to Waiting state; if
the low-priority thread is not preemped and can release the mutex before it
is preempted, there would be NO priority inversion!!!
following scenario:
- A low-priority thread is holding a mutex, which is also used by a
high-priority thread. - The high-priority thread tries to acquire the mutex so it is blocked goes
to Waiting state. - During this time a medium-priority thread becomes ready to run and
preempts the low-priority thread and starts running.
It is obvious that in a priority-based scheduling system the high-priority
thread is the one, which should get the CPU time just when the mutex is
released by the low-priority thread. But as long as the medium-priority
thread is running (no waits or preemption by higher-priority threads which
are ready to run) the low-priority thread remains in Ready state and causes
the high-priority threads to remain in Waiting state.
This situation is called a priority inversion.
Johnny
-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of Maxim S. Shatskih
Sent: Mittwoch, 1. Mai 2002 22:54
To: NT Developers Interest List
Subject: [ntdev] Re: How does OS implements Semaphore
The low-priority thread have grabbed some mutex.
The high-priority thread is waiting on it. This is an inversion.
Max
----- Original Message -----
From: Arup Banerjee
To: NT Developers Interest List
Sent: Wednesday, May 01, 2002 8:36 AM
Subject: [ntdev] How does OS implements Semaphore
Hi,
can anybody explain … how OS implements Semaphores , Mutexes ,
Events — I mean Semaphore in terms of Priority Inversion … what and how
does that inversion really take place …
–Arup
You are currently subscribed to ntdev as: xxxxx@storagecraft.com
To unsubscribe send a blank email to %%email.unsub%%
You are currently subscribed to ntdev as: xxxxx@yahoo.de
To unsubscribe send a blank email to %%email.unsub%%
Hmmm … this is the point I wanted the discussion to arrive … its a
serious problem indeed in RTOS everybody would agree … Priority inversion
would defy coded control logic and make unrecoverable damages … So RTOSes
like VxWorks came up with solutions like providing an additional option when
using mutual exclusion semaphores. This option is SEM_INVERSION_SAFE which
enables a priority inheritance algorithm. This algorithm insures that the
task that owns a resource executes at the priority of the highest priority
task blocked on that resource. When execution is complete, the task
relinquishes the resource and returns to its normal priority. Therefore, the
inheriting task is protected from preemption by an intermediate priority
task.
Is there anyother solutions
-----Original Message-----
From: Johnny [mailto:xxxxx@yahoo.de]
Sent: Thursday, May 02, 2002 6:33 AM
To: NT Developers Interest List
Subject: [ntdev] Re: How does OS implements Semaphore
Max,
the priority inversion problem would just accur, if the low-priority thread
is holding the mutex and is preemped by Scheduler when an other
higher-priority thread is ready to run or it transits to Waiting state; if
the low-priority thread is not preemped and can release the mutex before it
is preempted, there would be NO priority inversion!!!
following scenario:
- A low-priority thread is holding a mutex, which is also used by a
high-priority thread. - The high-priority thread tries to acquire the mutex so it is blocked goes
to Waiting state. - During this time a medium-priority thread becomes ready to run and
preempts the low-priority thread and starts running.
It is obvious that in a priority-based scheduling system the high-priority
thread is the one, which should get the CPU time just when the mutex is
released by the low-priority thread. But as long as the medium-priority
thread is running (no waits or preemption by higher-priority threads which
are ready to run) the low-priority thread remains in Ready state and causes
the high-priority threads to remain in Waiting state.
This situation is called a priority inversion.
Johnny
-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of Maxim S. Shatskih
Sent: Mittwoch, 1. Mai 2002 22:54
To: NT Developers Interest List
Subject: [ntdev] Re: How does OS implements Semaphore
The low-priority thread have grabbed some mutex.
The high-priority thread is waiting on it. This is an inversion.
Max
----- Original Message -----
From: Arup mailto:xxxxx Banerjee
To: NT Developers mailto:xxxxx Interest List
Sent: Wednesday, May 01, 2002 8:36 AM
Subject: [ntdev] How does OS implements Semaphore
Hi,
can anybody explain … how OS implements Semaphores , Mutexes , Events —
I mean Semaphore in terms of Priority Inversion … what and how does that
inversion really take place …
–Arup
—
You are currently subscribed to ntdev as: xxxxx@storagecraft.com
mailto:xxxxx
To unsubscribe send a blank email to %%email.unsub%%
mailto:
—
You are currently subscribed to ntdev as: xxxxx@yahoo.de
To unsubscribe send a blank email to %%email.unsub%%
—
You are currently subscribed to ntdev as: xxxxx@quark.co.in
To unsubscribe send a blank email to %%email.unsub%%</mailto:></mailto:xxxxx></mailto:xxxxx></mailto:xxxxx>
NT is not a realtime OS, so, it does not need this things - unless inversion can cause deadlock, and IIRC it cannot.
Also NT boosts low-priority threads sometimes to avoid starvation.
Max
----- Original Message -----
From: Arup Banerjee
To: NT Developers Interest List
Cc: xxxxx@nucsoft.co.in ; xxxxx@yahoo.com
Sent: Thursday, May 02, 2002 8:31 AM
Subject: [ntdev] Re: How does OS implements Semaphore
Hmmm … this is the point I wanted the discussion to arrive … its a serious problem indeed in RTOS everybody would agree … Priority inversion would defy coded control logic and make unrecoverable damages … So RTOSes like VxWorks came up with solutions like providing an additional option when using mutual exclusion semaphores. This option is SEM_INVERSION_SAFE which enables a priority inheritance algorithm. This algorithm insures that the task that owns a resource executes at the priority of the highest priority task blocked on that resource. When execution is complete, the task relinquishes the resource and returns to its normal priority. Therefore, the inheriting task is protected from preemption by an intermediate priority task.
Is there anyother solutions
-----Original Message-----
From: Johnny [mailto:xxxxx@yahoo.de]
Sent: Thursday, May 02, 2002 6:33 AM
To: NT Developers Interest List
Subject: [ntdev] Re: How does OS implements Semaphore
Max,
the priority inversion problem would just accur, if the low-priority thread is holding the mutex and is preemped by Scheduler when an other higher-priority thread is ready to run or it transits to Waiting state; if the low-priority thread is not preemped and can release the mutex before it is preempted, there would be NO priority inversion!!!
following scenario:
- A low-priority thread is holding a mutex, which is also used by a high-priority thread.
- The high-priority thread tries to acquire the mutex so it is blocked goes to Waiting state.
- During this time a medium-priority thread becomes ready to run and preempts the low-priority thread and starts running.
It is obvious that in a priority-based scheduling system the high-priority thread is the one, which should get the CPU time just when the mutex is released by the low-priority thread. But as long as the medium-priority thread is running (no waits or preemption by higher-priority threads which are ready to run) the low-priority thread remains in Ready state and causes the high-priority threads to remain in Waiting state.
This situation is called a priority inversion.
Johnny
-----Original Message-----
From: xxxxx@lists.osr.com [mailto:xxxxx@lists.osr.com]On Behalf Of Maxim S. Shatskih
Sent: Mittwoch, 1. Mai 2002 22:54
To: NT Developers Interest List
Subject: [ntdev] Re: How does OS implements Semaphore
The low-priority thread have grabbed some mutex.
The high-priority thread is waiting on it. This is an inversion.
Max
----- Original Message -----
From: Arup Banerjee
To: NT Developers Interest List
Sent: Wednesday, May 01, 2002 8:36 AM
Subject: [ntdev] How does OS implements Semaphore
Hi,
can anybody explain … how OS implements Semaphores , Mutexes , Events — I mean Semaphore in terms of Priority Inversion … what and how does that inversion really take place …
–Arup
You are currently subscribed to ntdev as: xxxxx@storagecraft.com
To unsubscribe send a blank email to %%email.unsub%%
You are currently subscribed to ntdev as: xxxxx@yahoo.de
To unsubscribe send a blank email to %%email.unsub%%
You are currently subscribed to ntdev as: xxxxx@quark.co.in
To unsubscribe send a blank email to %%email.unsub%%
You are currently subscribed to ntdev as: xxxxx@storagecraft.com
To unsubscribe send a blank email to %%email.unsub%%
Specifically: NT alters the dynamic priority of a thread whenever it becomes blocked by IO (depends on driver, but usually a bump of 2). If a thread should cause its time-slice to expire its priority is lowered, but also given an extended time-slice for next scheduling. Maybe inversion could cause a deadlock (it could easily be manipulated to do so) – this is simply a bad design of whomever was responsible for desiging such a wretched program that made it so vulnerable. Think of the case of the classic deadlock:
Thread A grabs object A
Thread B grabs object B
Thread A infinite waits for object B
Thread B infinite waits for object A
Here you have two threads locked in a kiss of death. This is not an OS fault that allowed this to happen, but a bad design from the author of A/B who should’ve coded to cater for such an event more elegantly.
In any case, NT’s dynamic scheduling does such a good job at managing thread execution that it is exceptionally rare to ever use thread or process priorities. If a 2-bit programmer uses a feature the OS provides to take aim at his own foot, he deserves everything he gets – but don’t blame the OS!
Regards
Paul Bunn, UltraBac Software, 425-644-6000
Microsoft MVP - NT/Windows 2000/XP
http://www.ultrabac.com
-----Original Message-----
From: Maxim S. Shatskih [mailto:xxxxx@storagecraft.com]
Sent: Thursday, May 02, 2002 6:36 AM
To: NT Developers Interest List
Cc: xxxxx@nucsoft.co.in; xxxxx@yahoo.com
Subject: [ntdev] Re: How does OS implements Semaphore
NT is not a realtime OS, so, it does not need this things - unless inversion can cause deadlock, and IIRC it cannot.
Also NT boosts low-priority threads sometimes to avoid starvation.
Max
----- Original Message -----
From: Arup Banerjee
To: NT Developers Interest List
Cc: xxxxx@nucsoft.co.in ; xxxxx@yahoo.com
Sent: Thursday, May 02, 2002 8:31 AM
Subject: [ntdev] Re: How does OS implements Semaphore
Hmmm … this is the point I wanted the discussion to arrive … its a serious problem indeed in RTOS everybody would agree … Priority inversion would defy coded control logic and make unrecoverable damages … So RTOSes like VxWorks came up with solutions like providing an additional option when using mutual exclusion semaphores. This option is SEM_INVERSION_SAFE which enables a priority inheritance algorithm. This algorithm insures that the task that owns a resource executes at the priority of the highest priority task blocked on that resource. When execution is complete, the task relinquishes the resource and returns to its normal priority. Therefore, the inheriting task is protected from preemption by an intermediate priority task.
Is there anyother solutions
-----Original Message-----
From: Johnny [mailto:xxxxx@yahoo.de]
Sent: Thursday, May 02, 2002 6:33 AM
To: NT Developers Interest List
Subject: [ntdev] Re: How does OS implements Semaphore
Max,
the priority inversion problem would just accur, if the low-priority thread is holding the mutex and is preemped by Scheduler when an other higher-priority thread is ready to run or it transits to Waiting state; if the low-priority thread is not preemped and can release the mutex before it is preempted, there would be NO priority inversion!!!
following scenario:
- A low-priority thread is holding a mutex, which is also used by a high-priority thread.
- The high-priority thread tries to acquire the mutex so it is blocked goes to Waiting state.
- During this time a medium-priority thread becomes ready to run and preempts the low-priority thread and starts running.
It is obvious that in a priority-based scheduling system the high-priority thread is the one, which should get the CPU time just when the mutex is released by the low-priority thread. But as long as the medium-priority thread is running (no waits or preemption by higher-priority threads which are ready to run) the low-priority thread remains in Ready state and causes the high-priority threads to remain in Waiting state.
This situation is called a priority inversion.
Johnny
-----Original Message-----
From: xxxxx@lists.osr.com [mailto:xxxxx@lists.osr.com]On Behalf Of Maxim S. Shatskih
Sent: Mittwoch, 1. Mai 2002 22:54
To: NT Developers Interest List
Subject: [ntdev] Re: How does OS implements Semaphore
The low-priority thread have grabbed some mutex.
The high-priority thread is waiting on it. This is an inversion.
Max
----- Original Message -----
From: Arup Banerjee
To: NT Developers Interest List
Sent: Wednesday, May 01, 2002 8:36 AM
Subject: [ntdev] How does OS implements Semaphore
Hi,
can anybody explain … how OS implements Semaphores , Mutexes , Events — I mean Semaphore in terms of Priority Inversion … what and how does that inversion really take place …
–Arup
You are currently subscribed to ntdev as: xxxxx@storagecraft.com
To unsubscribe send a blank email to %%email.unsub%%
You are currently subscribed to ntdev as: xxxxx@yahoo.de
To unsubscribe send a blank email to %%email.unsub%%
You are currently subscribed to ntdev as: xxxxx@quark.co.in
To unsubscribe send a blank email to %%email.unsub%%
You are currently subscribed to ntdev as: xxxxx@storagecraft.com
To unsubscribe send a blank email to %%email.unsub%%
You are currently subscribed to ntdev as: xxxxx@ultrabac.com
To unsubscribe send a blank email to %%email.unsub%%
Yes but this does not cover the priority inversion deadlock, which is not a
programmer error, but an artifact of priority based scheduling. What NT does
do is to pick threads that have been ready-waiting for a while and give them
a temporary priority boost. This, in a non-deterministic manner, will
eventually find a priority inversion and resolve it. It won’t help realtime
problems, but then again NT is not an RTOS.
-----Original Message-----
From: Paul Bunn [mailto:xxxxx@UltraBac.com]
Sent: Thursday, May 02, 2002 11:44 AM
To: NT Developers Interest List
Subject: [ntdev] Re: How does OS implements SemaphoreSpecifically: NT alters the dynamic priority of a thread
whenever it becomes blocked by IO (depends on driver, but
usually a bump of 2). If a thread should cause its
time-slice to expire its priority is lowered, but also given
an extended time-slice for next scheduling. Maybe inversion
could cause a deadlock (it could easily be manipulated to do
so) – this is simply a bad design of whomever was
responsible for desiging such a wretched program that made it
so vulnerable. Think of the case of the classic deadlock:
Thread A grabs object A Thread B grabs object B Thread A
infinite waits for object B Thread B infinite waits for
object A Here you have two threads locked in a kiss of death.
This is not an OS fault that allowed this to happen, but a
bad design from the author of A/B who should’ve coded to
cater for such an event more elegantly. In any case, NT’s
dynamic scheduling does such a good job at managing thread
execution that it is exceptionally rare to ever use thread or
process priorities. If a 2-bit programmer uses a feature the
OS provides to take aim at his own foot, he deserves
everything he gets – but don’t blame the OS!Regards
Paul Bunn, UltraBac Software, 425-644-6000
Microsoft MVP - NT/Windows 2000/XP
http://www.ultrabac.com-----Original Message-----
From: Maxim S. Shatskih [mailto:xxxxx@storagecraft.com]
Sent: Thursday, May 02, 2002 6:36 AM
To: NT Developers Interest List
Cc: xxxxx@nucsoft.co.in; xxxxx@yahoo.com
Subject: [ntdev] Re: How does OS implements SemaphoreNT is not a realtime OS, so, it does not need this things -
unless inversion can cause deadlock, and IIRC it cannot. Also
NT boosts low-priority threads sometimes to avoid starvation.Max
----- Original Message -----
From: Arup Banerjee
To: NT Developers Interest List
Cc: xxxxx@nucsoft.co.in ; xxxxx@yahoo.com
Sent: Thursday, May 02, 2002 8:31 AM
Subject: [ntdev] Re: How does OS implements SemaphoreHmmm … this is the point I wanted the discussion to arrive
… its a serious problem indeed in RTOS everybody would
agree … Priority inversion would defy coded control logic
and make unrecoverable damages … So RTOSes like VxWorks
came up with solutions like providing an additional option
when using mutual exclusion semaphores. This option is
SEM_INVERSION_SAFE which enables a priority inheritance
algorithm. This algorithm insures that the task that owns a
resource executes at the priority of the highest priority
task blocked on that resource. When execution is complete,
the task relinquishes the resource and returns to its normal
priority. Therefore, the inheriting task is protected from
preemption by an intermediate priority task.Is there anyother solutions
-----Original Message-----
From: Johnny [mailto:xxxxx@yahoo.de]
Sent: Thursday, May 02, 2002 6:33 AM
To: NT Developers Interest List
Subject: [ntdev] Re: How does OS implements SemaphoreMax,
the priority inversion problem would just accur, if the
low-priority thread is holding the mutex and is preemped by
Scheduler when an other higher-priority thread is ready to
run or it transits to Waiting state; if the low-priority
thread is not preemped and can release the mutex before it is
preempted, there would be NO priority inversion!!!following scenario:
- A low-priority thread is holding a mutex, which is also
used by a high-priority thread.- The high-priority thread tries to acquire the mutex so it
is blocked goes to Waiting state.- During this time a medium-priority thread becomes ready to
run and preempts the low-priority thread and starts running.It is obvious that in a priority-based scheduling system the
high-priority thread is the one, which should get the CPU
time just when the mutex is released by the low-priority
thread. But as long as the medium-priority thread is running
(no waits or preemption by higher-priority threads which are
ready to run) the low-priority thread remains in Ready state
and causes the high-priority threads to remain in Waiting state.This situation is called a priority inversion.
Johnny
-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On > Behalf Of Maxim S. Shatskih
Sent: Mittwoch, 1. Mai 2002 22:54
To: NT Developers Interest List
Subject: [ntdev] Re: How does OS implements SemaphoreThe low-priority thread have grabbed some mutex.
The high-priority thread is waiting on it. This is an inversion.Max
----- Original Message -----
From: Arup Banerjee
To: NT Developers Interest List
Sent: Wednesday, May 01, 2002 8:36 AM
Subject: [ntdev] How does OS implements SemaphoreHi,
can anybody explain … how OS implements Semaphores ,
Mutexes , Events — I mean Semaphore in terms of Priority
Inversion … what and how does that inversion really take place …–Arup
You are currently subscribed to ntdev as: xxxxx@storagecraft.com
To unsubscribe send a blank email to %%email.unsub%%You are currently subscribed to ntdev as:
xxxxx@yahoo.de To unsubscribe send a blank email to
%%email.unsub%%You are currently subscribed to ntdev as:
xxxxx@quark.co.in To unsubscribe send a blank email to
%%email.unsub%%You are currently subscribed to ntdev as:
xxxxx@storagecraft.com To unsubscribe send a blank email to
%%email.unsub%%You are currently subscribed to ntdev as: xxxxx@ultrabac.com
To unsubscribe send a blank email to %%email.unsub%%
You are currently subscribed to ntdev as:
xxxxx@stratus.com To unsubscribe send a blank email to
%%email.unsub%%
> Specifically: NT alters the dynamic priority of a thread whenever it
becomes blocked by IO >(depends on driver, but usually a bump of 2).
No, that’s not right, NT alters the priority of a thread when it’s base
priority is not in the real time priority range!!
If a thread should cause its time-slice to expire its priority is lowered,
but also given > an extended time-slice for next scheduling.
As far as I know it is not possible to shorten the quantum of a thread on
NT.
Any way, I have not heard or read anything about priority inversion
algorithms on NT. There are definitely some optimization this regarding, but
not discussed as priority inversion stuff (prety hardly, just in SMP stuff).
In case of NT, which is not a RTOS, this point is not critical. worst case :
DEAD LOCK
Johnny
-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of Paul Bunn
Sent: Donnerstag, 2. Mai 2002 17:44
To: NT Developers Interest List
Subject: [ntdev] Re: How does OS implements Semaphore
Specifically: NT alters the dynamic priority of a thread whenever it becomes
blocked by IO (depends on driver, but usually a bump of 2). If a thread
should cause its time-slice to expire its priority is lowered, but also
given an extended time-slice for next scheduling. Maybe inversion could
cause a deadlock (it could easily be manipulated to do so) – this is simply
a bad design of whomever was responsible for desiging such a wretched
program that made it so vulnerable. Think of the case of the classic
deadlock:
Thread A grabs object A
Thread B grabs object B
Thread A infinite waits for object B
Thread B infinite waits for object A
Here you have two threads locked in a kiss of death. This is not an OS
fault that allowed this to happen, but a bad design from the author of A/B
who should’ve coded to cater for such an event more elegantly.
In any case, NT’s dynamic scheduling does such a good job at managing thread
execution that it is exceptionally rare to ever use thread or process
priorities. If a 2-bit programmer uses a feature the OS provides to take
aim at his own foot, he deserves everything he gets – but don’t blame the
OS!
Regards
Paul Bunn, UltraBac Software, 425-644-6000
Microsoft MVP - NT/Windows 2000/XP
http://www.ultrabac.com
-----Original Message-----
From: Maxim S. Shatskih [mailto:xxxxx@storagecraft.com]
Sent: Thursday, May 02, 2002 6:36 AM
To: NT Developers Interest List
Cc: xxxxx@nucsoft.co.in; xxxxx@yahoo.com
Subject: [ntdev] Re: How does OS implements Semaphore
NT is not a realtime OS, so, it does not need this things - unless inversion
can cause deadlock, and IIRC it cannot.
Also NT boosts low-priority threads sometimes to avoid starvation.
Max
----- Original Message -----
From: Arup Banerjee
To: NT Developers Interest List
Cc: xxxxx@nucsoft.co.in ; xxxxx@yahoo.com
Sent: Thursday, May 02, 2002 8:31 AM
Subject: [ntdev] Re: How does OS implements Semaphore
Hmmm … this is the point I wanted the discussion to arrive … its a
serious problem indeed in RTOS everybody would agree … Priority inversion
would defy coded control logic and make unrecoverable damages … So RTOSes
like VxWorks came up with solutions like providing an additional option when
using mutual exclusion semaphores. This option is SEM_INVERSION_SAFE which
enables a priority inheritance algorithm. This algorithm insures that the
task that owns a resource executes at the priority of the highest priority
task blocked on that resource. When execution is complete, the task
relinquishes the resource and returns to its normal priority. Therefore, the
inheriting task is protected from preemption by an intermediate priority
task.
Is there anyother solutions
-----Original Message-----
From: Johnny [mailto:xxxxx@yahoo.de]
Sent: Thursday, May 02, 2002 6:33 AM
To: NT Developers Interest List
Subject: [ntdev] Re: How does OS implements Semaphore
Max,
the priority inversion problem would just accur, if the low-priority thread
is holding the mutex and is preemped by Scheduler when an other
higher-priority thread is ready to run or it transits to Waiting state; if
the low-priority thread is not preemped and can release the mutex before it
is preempted, there would be NO priority inversion!!!
following scenario:
- A low-priority thread is holding a mutex, which is also used by a
high-priority thread. - The high-priority thread tries to acquire the mutex so it is blocked goes
to Waiting state. - During this time a medium-priority thread becomes ready to run and
preempts the low-priority thread and starts running.
It is obvious that in a priority-based scheduling system the high-priority
thread is the one, which should get the CPU time just when the mutex is
released by the low-priority thread. But as long as the medium-priority
thread is running (no waits or preemption by higher-priority threads which
are ready to run) the low-priority thread remains in Ready state and causes
the high-priority threads to remain in Waiting state.
This situation is called a priority inversion.
Johnny
-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of Maxim S. Shatskih
Sent: Mittwoch, 1. Mai 2002 22:54
To: NT Developers Interest List
Subject: [ntdev] Re: How does OS implements Semaphore
The low-priority thread have grabbed some mutex.
The high-priority thread is waiting on it. This is an inversion.
Max
----- Original Message -----
From: Arup Banerjee
To: NT Developers Interest List
Sent: Wednesday, May 01, 2002 8:36 AM
Subject: [ntdev] How does OS implements Semaphore
Hi,
can anybody explain … how OS implements Semaphores , Mutexes , Events —
I mean Semaphore in terms of Priority Inversion … what and how does that
inversion really take place …
–Arup
You are currently subscribed to ntdev as: xxxxx@storagecraft.com
To unsubscribe send a blank email to %%email.unsub%%
You are currently subscribed to ntdev as: xxxxx@yahoo.de
To unsubscribe send a blank email to %%email.unsub%%
You are currently subscribed to ntdev as: xxxxx@quark.co.in
To unsubscribe send a blank email to %%email.unsub%%
You are currently subscribed to ntdev as: xxxxx@storagecraft.com
To unsubscribe send a blank email to %%email.unsub%%
You are currently subscribed to ntdev as: xxxxx@ultrabac.com
To unsubscribe send a blank email to %%email.unsub%%
You are currently subscribed to ntdev as: xxxxx@yahoo.de
To unsubscribe send a blank email to %%email.unsub%%
Do You Yahoo!?
Get your free @yahoo.com address at http://mail.yahoo.com
>so vulnerable. Think of the case of the classic deadlock:
Thread A grabs object A
Thread B grabs object B
Thread A infinite waits for object B
Thread B infinite waits for object A
This is not inversion.
Max
RToses like VxWorks resolves Priority Inversion problem using Priority
Inheritance Algorighthm …any idea what measure is taken by RToses like eCos
, Psos , QNX , RTLinux , … its not an issue with NT anyway … not a
discussion for this issue anyway …
–Arup
-----Original Message-----
From: Maxim S. Shatskih [mailto:xxxxx@storagecraft.com]
Sent: Friday, May 03, 2002 1:45 AM
To: NT Developers Interest List
Subject: [ntdev] Re: How does OS implements Semaphore>so vulnerable. Think of the case of the classic deadlock:
> Thread A grabs object A
> Thread B grabs object B
> Thread A infinite waits for object B
> Thread B infinite waits for object AThis is not inversion.
Max
You are currently subscribed to ntdev as: xxxxx@quark.co.in
To unsubscribe send a blank email to %%email.unsub%%
This scenario is a classic case of priority inversion.
http://research.microsoft.com/~mbj/Mars_Pathfinder/Mars_Pathfinder.html
Niraj
-----Original Message-----
From: Arup Banerjee [mailto:xxxxx@quark.co.in]
Sent: Thursday, May 02, 2002 9:53 PM
To: NT Developers Interest List
Subject: [ntdev] Re: How does OS implements Semaphore
RToses like VxWorks resolves Priority Inversion problem using Priority
Inheritance Algorighthm …any idea what measure is taken by RToses like eCos
, Psos , QNX , RTLinux , … its not an issue with NT anyway … not a
discussion for this issue anyway …
–Arup
-----Original Message-----
From: Maxim S. Shatskih [mailto:xxxxx@storagecraft.com]
Sent: Friday, May 03, 2002 1:45 AM
To: NT Developers Interest List
Subject: [ntdev] Re: How does OS implements Semaphore>so vulnerable. Think of the case of the classic deadlock:
> Thread A grabs object A
> Thread B grabs object B
> Thread A infinite waits for object B
> Thread B infinite waits for object AThis is not inversion.
Max
You are currently subscribed to ntdev as: xxxxx@quark.co.in
To unsubscribe send a blank email to %%email.unsub%%
You are currently subscribed to ntdev as: xxxxx@netapp.com
To unsubscribe send a blank email to %%email.unsub%%