OSDev.org

The Place to Start for Operating System Developers
It is currently Thu Mar 28, 2024 2:06 am

All times are UTC - 6 hours




Post new topic Reply to topic  [ 28 posts ]  Go to page Previous  1, 2
Author Message
 Post subject: Re: copy-on-write/mapped files without race conditions?
PostPosted: Sun Apr 03, 2016 5:47 pm 
Offline
Member
Member

Joined: Thu Mar 25, 2010 11:26 pm
Posts: 1801
Location: Melbourne, Australia
kiznit wrote:
Just to be clear about what I said above: imagine you have a thread holding a mutex for a significant amount of time. Other important threads are waiting on that mutex. You release the mutex and you want the important threads to be scheduled immediately. How do you accomplish this without using a yield() call?
I agree kiznit. A yield() is necessary in this case. And this is a very common case.


Rdos, nice job derailing a thread to tell us about your OS.

_________________
If a trainstation is where trains stop, what is a workstation ?


Top
 Profile  
 
 Post subject: Re: copy-on-write/mapped files without race conditions?
PostPosted: Mon Apr 04, 2016 1:22 am 
Offline
Member
Member
User avatar

Joined: Thu Aug 11, 2005 11:00 pm
Posts: 1110
Location: Tartu, Estonia
kiznit wrote:
Just to be clear about what I said above: imagine you have a thread holding a mutex for a significant amount of time. Other important threads are waiting on that mutex. You release the mutex and you want the important threads to be scheduled immediately. How do you accomplish this without using a yield() call?

Just out of curiosity (and not trying to take sides in this discussion): What is the advantage of having yield in this situation, instead of managing mutexes / thread communication via some acquire / release system call mechanism? I think of something like: Thread A releases the mutex through some system call, the scheduler is invoked, sees the mutex become free, unblocks a thread B that was blocked when it tried to acquire the mutex via some system call, raises B's priority because it has been waiting, lowers the A's priority because it had just used the CPU, and switches to B because it has higher priority.

_________________
Programmers' Hardware Database // GitHub user: xenos1984; OS project: NOS


Top
 Profile  
 
 Post subject: Re: copy-on-write/mapped files without race conditions?
PostPosted: Mon Apr 04, 2016 1:42 am 
Offline
Member
Member

Joined: Thu Mar 25, 2010 11:26 pm
Posts: 1801
Location: Melbourne, Australia
XenOS wrote:
Just out of curiosity (and not trying to take sides in this discussion): What is the advantage of having yield in this situation, instead of managing mutexes / thread communication via some acquire / release system call mechanism? I think of something like: Thread A releases the mutex through some system call, the scheduler is invoked, sees the mutex become free, unblocks a thread B that was blocked when it tried to acquire the mutex via some system call, raises B's priority because it has been waiting, lowers the A's priority because it had just used the CPU, and switches to B because it has higher priority.
Xenos, forgive me for jumping in. In some OS's (including QNX, Linux and my hobby OS) releasing a mutex is very light-weight doesn't always involve a kernel call (in Linux futexes mean that the userside data structure knows whether there are probably waiters and only involves the kernel if it thinks there are). This means that generally the scheduler has no idea that a mutex is released.

Even if a kernel call does take place the scheduler may not be invoked because the thread maybe very near the beginning of its time-slice.

In other words in almost all cases, releasing a mutex may unblock other threads but not run give them a chance to run. Calling yield() or similar gives the scheduler a chance to run those other threads.

_________________
If a trainstation is where trains stop, what is a workstation ?


Top
 Profile  
 
 Post subject: Re: copy-on-write/mapped files without race conditions?
PostPosted: Mon Apr 04, 2016 7:36 am 
Offline
Member
Member
User avatar

Joined: Thu Aug 11, 2005 11:00 pm
Posts: 1110
Location: Tartu, Estonia
gerryg400 wrote:
Xenos, forgive me for jumping in. In some OS's (including QNX, Linux and my hobby OS) releasing a mutex is very light-weight doesn't always involve a kernel call (in Linux futexes mean that the userside data structure knows whether there are probably waiters and only involves the kernel if it thinks there are). This means that generally the scheduler has no idea that a mutex is released.

Thanks for this information. In that case, of course, a yield totally makes sense.

My aim was rather to compare this design with a different one, in which releasing a mutex involves the kernel, a waiter is unblocked and finally the scheduler is invoked (if and only if the unblocked has higher priority than the currently running one, possibly after dynamically shifting priorities). Wouldn't that be just as useful as the release mutex + yield as in the previous case? In this case, it's up to the kernel whether to give the CPU to another thread immediately after releasing the mutex, while in your example it's up to the application (which may be good or bad).

_________________
Programmers' Hardware Database // GitHub user: xenos1984; OS project: NOS


Top
 Profile  
 
 Post subject: Re: copy-on-write/mapped files without race conditions?
PostPosted: Mon Apr 04, 2016 8:57 am 
Offline
Member
Member

Joined: Mon Feb 02, 2015 7:11 pm
Posts: 898
XenOS: yes it can make sense for a kernel-side mutex unlock operation to trigger a context switch in certain cases. As gerryg400 pointed out, I was thinling of a user-space mutex where the OS has no idea / opportunity to re-schedule threads.

_________________
https://github.com/kiznit/rainbow-os


Top
 Profile  
 
 Post subject: Re: copy-on-write/mapped files without race conditions?
PostPosted: Tue Apr 05, 2016 3:33 am 
Offline
Member
Member

Joined: Wed Oct 01, 2008 1:55 pm
Posts: 3191
kzinti wrote:
Just to be clear about what I said above: imagine you have a thread holding a mutex for a significant amount of time. Other important threads are waiting on that mutex. You release the mutex and you want the important threads to be scheduled immediately. How do you accomplish this without using a yield() call?


You let the kernel activate the thread that was waiting and assign the mutex to it. Then if the original thread tries to acquire it again, it will be blocked. Of course, if the activated thread has higher priority, it would be switched to directly. No need for user to interfere with this.


Top
 Profile  
 
 Post subject: Re: copy-on-write/mapped files without race conditions?
PostPosted: Tue Apr 05, 2016 3:40 am 
Offline
Member
Member

Joined: Wed Oct 01, 2008 1:55 pm
Posts: 3191
gerryg400 wrote:
Xenos, forgive me for jumping in. In some OS's (including QNX, Linux and my hobby OS) releasing a mutex is very light-weight doesn't always involve a kernel call (in Linux futexes mean that the userside data structure knows whether there are probably waiters and only involves the kernel if it thinks there are). This means that generally the scheduler has no idea that a mutex is released.

Even if a kernel call does take place the scheduler may not be invoked because the thread maybe very near the beginning of its time-slice.

In other words in almost all cases, releasing a mutex may unblock other threads but not run give them a chance to run. Calling yield() or similar gives the scheduler a chance to run those other threads.


That doesn't seem right. I also use futexes, but as soon as something is blocked on a futex, then the light-weight route no longer can be taken. So, the situation is the same regardless if futexes are used or not.

Also, by always using a yield after releasing a mutex, you are clearly wasting CPU-time for no reason. At least, if you combine it with futexes, there is never any reason to do a yield if the mutex can be taken and released without contention, and in those situations, yield has no function.


Top
 Profile  
 
 Post subject: Re: copy-on-write/mapped files without race conditions?
PostPosted: Tue Apr 05, 2016 4:13 am 
Offline
Member
Member

Joined: Thu Mar 25, 2010 11:26 pm
Posts: 1801
Location: Melbourne, Australia
Rdos, the point is that there are some valid situations in some valid OSes where calling yield() makes sense. They may not apply in RDOS but that doesn't mean they don't apply elsewhere.

_________________
If a trainstation is where trains stop, what is a workstation ?


Top
 Profile  
 
 Post subject: Re: copy-on-write/mapped files without race conditions?
PostPosted: Tue Apr 05, 2016 4:17 am 
Offline
Member
Member

Joined: Mon Feb 02, 2015 7:11 pm
Posts: 898
rdos wrote:
You let the kernel activate the thread that was waiting and assign the mutex to it. Then if the original thread tries to acquire it again, it will be blocked. Of course, if the activated thread has higher priority, it would be switched to directly. No need for user to interfere with this.


So you are going to call your scheduler when releasing a kernel mutex? Everytime? That is not efficient. It also ends up being practically the same thing as calling yield() right after releasing the mutex. But now you pay the price of the sched() function each time you release a mutex, even when you don't need to.

_________________
https://github.com/kiznit/rainbow-os


Top
 Profile  
 
 Post subject: Re: copy-on-write/mapped files without race conditions?
PostPosted: Tue Apr 05, 2016 5:33 am 
Offline
Member
Member

Joined: Wed Oct 01, 2008 1:55 pm
Posts: 3191
kzinti wrote:
rdos wrote:
You let the kernel activate the thread that was waiting and assign the mutex to it. Then if the original thread tries to acquire it again, it will be blocked. Of course, if the activated thread has higher priority, it would be switched to directly. No need for user to interfere with this.


So you are going to call your scheduler when releasing a kernel mutex? Everytime? That is not efficient. It also ends up being practically the same thing as calling yield() right after releasing the mutex. But now you pay the price of the sched() function each time you release a mutex, even when you don't need to.


I don't think so. Since I use futexes, the only time the kernel is called is when there is contention for the mutex, which are the same situations where yield() might be useful. The typical case when a mutex is held only a short time, and contention is unlikely, doesn't need any kernel-calls. The scheduler only needs to be invoked if the release call causes a thread with higher priority to be unblocked, and this thread runs on the current core.

So, in summary, using yield in this context is only useful if:
1. Almost every release of the mutex causes a thread to be unblocked
2. The unblocked thread runs on the same core.

I'd say both of these assumptions are problematic, and if they are not met, yield() is just a waste of time with no benefit.

It would be far better to set a property per mutex that automatically does yield as part of the unblocking process.


Top
 Profile  
 
 Post subject: Re: copy-on-write/mapped files without race conditions?
PostPosted: Tue Apr 05, 2016 12:42 pm 
Offline
Member
Member

Joined: Mon Feb 02, 2015 7:11 pm
Posts: 898
rdos wrote:
It would be far better to set a property per mutex that automatically does yield as part of the unblocking process.


I was thinking about exactly this at some point. For the scenario we have been discussed, I agree with you that having a per-flag mutex that automatically does yield would work. But that's not what you have nor what you argued about. You just changed your design to take into account something you haven't considered. This flag is less flexible that the yield() API as it enforces a contract at mutex creation time. I would rather have a yield flag specified at unlock time. This way you can keep the same flexibility with only one kernel call: mutex_unlock(mutex, 0) or mutex_unlock(mutex, MUTEX_YIELD).

They are more cases where yield() can be useful. I still maintain that not providing that API is a mistake.

_________________
https://github.com/kiznit/rainbow-os


Top
 Profile  
 
 Post subject: Re: copy-on-write/mapped files without race conditions?
PostPosted: Tue Apr 05, 2016 1:02 pm 
Offline
Member
Member

Joined: Wed Oct 01, 2008 1:55 pm
Posts: 3191
kzinti wrote:
rdos wrote:
It would be far better to set a property per mutex that automatically does yield as part of the unblocking process.


I was thinking about exactly this at some point. For the scenario we have been discussed, I agree with you that having a per-flag mutex that automatically does yield would work. But that's not what you have nor what you argued about. You just changed your design to take into account something you haven't considered.


Well, I'm not going to change the design as I don't see enough benefit with it. It was an example of how to solve it if you wanted that functionality without exporting a yield() function.

kzinti wrote:
This flag is less flexible that the yield() API as it enforces a contract at mutex creation time. I would rather have a yield flag specified at unlock time. This way you can keep the same flexibility with only one kernel call: mutex_unlock(mutex, 0) or mutex_unlock(mutex, MUTEX_YIELD).


Certainly, but I like the KISS-principle. :-)

kzinti wrote:
They are more cases where yield() can be useful. I still maintain that not providing that API is a mistake.


I had yield() 5-10 years ago, but removed it because it wasn't used for anything.


Top
 Profile  
 
 Post subject: Re: copy-on-write/mapped files without race conditions?
PostPosted: Tue Apr 05, 2016 5:38 pm 
Offline
Member
Member

Joined: Sat Oct 16, 2010 3:38 pm
Posts: 587
Well, I have to agree with rdos that my _glidix_yield() is never used. It was used at one point when the kernel scheduler was terribly designed and couldn't put a thread to sleep, so I can see where (s)he is coming from.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 28 posts ]  Go to page Previous  1, 2

All times are UTC - 6 hours


Who is online

Users browsing this forum: No registered users and 18 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group