copy-on-write/mapped files without race conditions?

[gerryg400]

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.

[xenos]

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.

[gerryg400]

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.

[xenos]

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).

[kzinti]

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.

[rdos]

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.

[rdos]

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.

[gerryg400]

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.

[kzinti]

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.

[rdos]

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.

[kzinti]

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.

[rdos]

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.

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.

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.

[mariuszp]

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.