X-Git-Url: http://git.madism.org/?p=~madcoder%2Fpwqr.git;a=blobdiff_plain;f=Documentation%2Fpwqr.adoc;h=d028a9ca400c8d8694e5e4c0cf875e14b66e8ba2;hp=57a85d4a5c9c31eccdba0373a7d990aa89c5a177;hb=866e56c8f10d718c24e812335b107a05218dc339;hpb=0fb6dd1141fb6076b2753133c797f0325c55a0df diff --git a/Documentation/pwqr.adoc b/Documentation/pwqr.adoc index 57a85d4..d028a9c 100644 --- a/Documentation/pwqr.adoc +++ b/Documentation/pwqr.adoc @@ -30,7 +30,15 @@ quarantined:: + This state avoids waking a thread to force userland to "park" the thread, this is racy, make the scheduler work for nothing useful. Though if `PWQR_WAKE` is -called, quarantined threads are woken but with a `EDQUOT` errno set. +called, quarantined threads are woken but with a `EDQUOT` errno set, and only +one by one, no matter how wakes have been asked. ++ +This state actually has only one impact: when `PWQR_WAKE` is called for more +than one threads, for example 4, and that userland knows that there is 5 +threads in WAIT state, but that actually 3 of them are in the quarantine, only +2 will be woken up, and the `PWQR_WAKE` call will return 2. Any subsequent +`PWQR_WAKE` call will wake up one quarantined thread to let it be parked, but +returning 0 each time to hide that from userland. parked:: This is the state of threads currently in a `PWQR_PARK` call from @@ -61,6 +69,10 @@ Unparking threads only when waiting becomes zero avoid flip-flops when the job flow is small, and that some of the running threads sometimes blocks (IOW running sometimes decreases, making `running + waiting` be below target concurrency for very small amount of time). ++ +NOTE: unparking only happens after a delay (0.1s in the current +implementation) during which `waiting` must have been remained zero and the +overal load to be under commiting resources for the whole period. The regulation between running and waiting threads is left to userspace that is a way better judge than kernel land that has absolutely no knowledge about @@ -68,21 +80,72 @@ the current workload. Also, doing so means that when there are lots of jobs to process and that the pool has a size that doesn't require more regulation, kernel isn't called for mediation/regulation AT ALL. -NOTE: right now threads are unparked as soon as `running + waiting` -undercommit, and some delay should be applied to be sure it's not a really -short blocking syscall that made us undercommit. -NOTE: when we're overcommiting for a "long" time, userspace should be notified -in some way it should try to reduce its amount of running threads. Note that -the Apple implementation (before Lion at least) has the same issue. Though if -you imagine someone that spawns a zillion jobs that call very slow `msync()s` -or blocking `read()s` over the network, then that all those go back to running +Todos +~~~~~ +When we're overcommiting for a "long" time, userspace should be notified in +some way it should try to reduce its amount of running threads. Note that the +Apple implementation (before Lion at least) has the same issue. Though if you +imagine someone that spawns a zillion jobs that call very slow `msync()s` or +blocking `read()s` over the network, then that all those go back to running state, the overcommit is huge. -A way to mitigate this atm is that when userspace belives the amount of -threads is abnormally high it should periodically try to PARK the threads. If -that blocks the thread, then it's that we were overcommiting. Note that it may -be the best solution rather than a kernel-side implementation. To be thought -over. + +There are several ways to "fix" this: + +in kernel (poll solution):: + Let the file descriptor be pollable, and let it be readable (returning + something like the amount of overcommit at read() time for example) so + that userland is notified that it should try to reduce the amount of + runnable threads. ++ +It sounds very easy, but it has one major drawback: it meaks the pwqfd must be +somehow registered into the eventloop, and it's not very suitable for a +pthread_workqueue implementation. In other words, if you can plug into the +event-loop because it's a custom one or one that provides thread regulation +then it's fine, if you can't (glib, libdispatch, ...) then you need a thread +that will basically just poll() on this file-descriptor, it's really wasteful. ++ +NOTE: this has been implemented now, but still it looks "expensive" to hook +for some users. So if some alternative way to be signalled could exist, it'd +be really awesome. + +in userspace:: + Userspace knows how many "running" threads there are, it's easy to + track the amount of registered threads, and parked/waiting threads are + already accounted for. When "waiting" is zero, if "registerd - parked" + is "High" userspace could choose to randomly try to park one thread. ++ +userspace can use non blocking read() to probe if it's overcommiting. ++ +It's in NONE when userspace belives it's not necessary to probe (e.g. when the +amount of running + waiting threads isn't that large, say less than 110% of +the concurrency or any kind of similar rule). ++ +It's in SLOW mode else. In slow mode each thread does a probe every 32 or 64 +jobs to mitigate the cost of the syscall. If the probe returns '1' then ask +for down-commiting and stay in SLOW mode, if it returns AGAIN all is fine, if +it returns more than '1' ask for down-commiting and go to AGGRESSIVE. ++ +When AGGRESSVE threads check if they must park more often and in a more +controlled fashion (every 32 or 64 jobs isn't nice because jobs can be very +long), for example based on some poor man's timer (clock_gettime(MONOTONIC) +sounds fine). State transition works as for SLOW. ++ +The issue I have with this is that it sounds to add quite some code in the +fastpath code, hence I dislike it a lot. + +my dream:: + To be able to define a new signal we could asynchronously send to the + process. The signal handler would just put some global flag to '1', + the threads in turn would check for this flag in their job consuming + loop, and the first thread that sees it to '1', xchg()s 0 for it, and + goes to PARK mode if it got the '1'. It's fast, inexpensive. ++ +Sadly AFAICT defining new signals() isn't such a good idea. Another +possibility is to give an address for the flag at pwqr_create() time and let +the kernel directly write into userland. The problem is, I feel like it's a +very wrong interface somehow. I should ask some kernel hacker to know if that +would be really frowned upon. If not, then that's the leanest solution of all. pwqr_create ----------- @@ -98,7 +161,21 @@ with a concurrency corresponding to the number of online CPUs at the time of the call, as would be returned by `sysconf(_SC_NPROCESSORS_ONLN)`. `flags`:: - a mask of flags, currently only O_CLOEXEC. + a mask of flags among `O_CLOEXEC`, and `O_NONBLOCK`. + +Available operations on the pwqr file descriptor are: + +`poll`, `epoll` and friends:: + the PWQR file descriptor can be watched for POLLIN events (not POLLOUT + ones as it can not be written to). + +`read`:: + The file returned can be read upon. The read blocks (or fails setting + `EAGAIN` if in non blocking mode) until the regulator believes the + pool is overcommitting. The buffer passed to read should be able to + hold an integer. When `read(3)` is successful, it writes the amount of + overcommiting threads (understand: the number of threads to park so + that the pool isn't overcommiting anymore). RETURN VALUE ~~~~~~~~~~~~ @@ -139,9 +216,8 @@ Valid values for the `op` argument are: value is passed as the `val` argument. The requests returns the old concurrency level on success. + - A zero or negative value for `val` means 'automatic' and is recomputed - as the current number of online CPUs as - `sysconf(_SC_NPROCESSORS_ONLN)` would return. +A zero or negative value for `val` means 'automatic' and is recomputed as the +current number of online CPUs as `sysconf(_SC_NPROCESSORS_ONLN)` would return. `PWQR_REGISTER`:: Registers the calling thread to be taken into account by the pool @@ -153,13 +229,27 @@ Valid values for the `op` argument are: `PWQR_WAKE`:: Tries to wake `val` threads from the pool. This is done according to - the current concurrency level not to overcommit. On success, the - number of woken threads is returned, it can be 0. + the current concurrency level not to overcommit. On success, a hint of + the number of woken threads is returned, it can be 0. ++ +This is only a hint of the number of threads woken up for two reasons. First, +the kernel could really have woken up a thread, but when it becomes scheduled, +it could *then* decide that it would overcommit (because some other thread +unblocked inbetween for example), and block it again. ++ +But it can also lie in the other direction: userland is supposed to account +for waiting threads. So when we're overcommiting and userland want a waiting +thread to be unblocked, we actually say we woke none, but still unblock one +(the famous quarantined threads we talk about above). This allow the userland +counter of waiting threads to decrease, but we know the thread won't be usable +so we return 0. `PWQR_WAKE_OC`:: Tries to wake `val` threads from the pool. This is done bypassing the current concurrency level (`OC` stands for `OVERCOMMIT`). On success, - the number of woken threads is returned, it can be 0. + the number of woken threads is returned, it can be 0, but it's the + real count that has been (or will soon be) woken up. If it's less than + required, it's because there aren't enough parked threads. `PWQR_WAIT`:: Puts the thread to wait for a future `PWQR_WAKE` command. If this @@ -170,6 +260,9 @@ If the concurrency level is below the target, then the kernel checks if the address `addr` still contains the value `val` (in the fashion of `futex(2)`). If it doesn't then the call doesn't block. Else the calling thread is blocked until a `PWQR_WAKE` command is received. ++ +`addr` must of course be a pointer to an aligned integer which stores the +reference ticket in userland. `PWQR_PARK`:: Puts the thread in park mode. Those are spare threads to avoid