Re: [PATCH] O17int

Mike Galbraith
2003-08-21T07:49:25Z

[-- Attachment #1: Type: text/plain, Size: 1705 bytes --]

At 03:26 PM 8/21/2003 +1000, Con Kolivas wrote:
>Unhappy with this latest O16.3-O17int patch I'm withdrawing it, and
>recommending nothing on top of O16.3 yet.
>
>More and more it just seems to be a bandaid to the priority inverting spin on
>waiters, and it does seem to be of detriment to general interacivity. I can
>now reproduce some loss of interactive feel with O17.
>
>Something specific for the spin on waiters is required that doesn't affect
>general performance. The fact that I can reproduce the same starvation in
>vanilla 2.6.0-test3 but to a lesser extent means this is an intrinsic problem
>that needs a specific solution.

I can see only one possible answer to this - never allow a normal task to
hold the cpu for long stretches (define) while there are other tasks
runnable. (see attachment)

I think the _easiest_ fix for this particular starvation (without tossing
baby out with bath water;) is to try to "down-shift" in schedule() when
next == prev. This you can do very cheaply with a find_next_bit(). That
won't help the case where there are multiple tasks involved, but should fix
the most common case for dirt cheap. (another simple alternative is to
globally "down-shift" periodically)

The most generally effective form of the "down-shift" anti-starvation
tactic that I've tried, is to periodically check the head of all queues
below current position (can do very quickly), and actively select the
oldest task who hasn't run since some defined deadline. Queues are
serviced based upon priority most of the time, and based upon age some of
the time.

Everything I've tried along these lines has a common upside: works, and
downside: butt ugly :)

-Mike

[-- Attachment #2: strace-blender --]
[-- Type: application/octet-stream, Size: 3377 bytes --]

<SNIP>
1061445810.812454 socket(PF_UNIX, SOCK_STREAM, 0) = 3 <0.000073>
1061445810.812704 uname({sys="Linux", node="mikeg", ...}) = 0 <0.000020>
1061445810.813014 uname({sys="Linux", node="mikeg", ...}) = 0 <0.000019>
1061445810.813400 connect(3, {sin_family=AF_UNIX, path="/tmp/.X11-unix/X0"}, 19) = 0 <0.000372>
1061445810.813988 uname({sys="Linux", node="mikeg", ...}) = 0 <0.000021>
1061445810.814345 fcntl64(3, F_SETFD, FD_CLOEXEC) = 0 <0.000021>
1061445810.814600 access("/root/.Xauthority", R_OK) = 0 <0.000036>
1061445810.814804 open("/root/.Xauthority", O_RDONLY) = 4 <0.000057>
1061445810.815040 fstat64(4, {st_mode=S_IFREG|0600, st_size=103, ...}) = 0 <0.000022>
1061445810.815233 old_mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x404cd000 <0.000031>
1061445810.815413 read(4, "\1\0\0\tel-kaboom\0\0010\0\22MIT-MAGIC-COOK"..., 4096) = 103 <0.000084>
1061445810.815723 read(4, "", 4096) = 0 <0.000022>
1061445810.815909 close(4) = 0 <0.000026>
<SNIP>
1061445810.824626 socket(PF_UNIX, SOCK_STREAM, 0) = 4 <0.000047>
1061445810.824789 uname({sys="Linux", node="mikeg", ...}) = 0 <0.000020>
1061445810.825095 uname({sys="Linux", node="mikeg", ...}) = 0 <0.000019>
1061445810.825392 connect(4, {sin_family=AF_UNIX, path="/tmp/.X11-unix/X0"}, 19) = 0 <0.000242>
<SNIP 40k lines>
1061445834.368068 select(4, [3], NULL, NULL, NULL) = 1 (in [3]) <0.000163>
1061445834.368469 read(3, "\1\0\354\"\0\0\0\0\0\0\0\0\1\0\0\0\0\27\0\0\0\0\0\0\0\0"..., 32) = 32 <0.000025>
1061445834.368698 write(3, "\221\v\3\0\1\0\0\0\2\0\300\1", 12) = 12 <0.000026>
1061445834.368876 writev(3, [{"\221\0012\0\1\0\0\0", 8}, {"\24\0\277\0\0\0\0\0\34\1\0\0\0\5\0\0\312\2\0\0\24\0g\0"..., 192}], 2) = 200 <0.000029>
1061445834.369152 write(3, "\221l\2\0\1\0\0\0", 8) = 8 <0.000026>
1061445834.369328 read(3, 0xbffff4c8, 32) = -1 EAGAIN (Resource temporarily unavailable) <0.000022>
1061445834.369462 select(4, [3], NULL, NULL, NULL) = 1 (in [3]) <0.032704>
1061445834.402553 read(3, "\1\0\357\"\0\0\0\0\0\0\0\0\1\0\0\0\0\27\0\0\0\0\0\0\0\0"..., 32) = 32 <0.000031>
1061445834.402773 gettimeofday({1061445834, 402818}, NULL) = 0 <0.000018>
1061445834.402913 ioctl(3, FIONREAD, [0]) = 0 <0.000021>
1061445834.403056 gettimeofday({1061445834, 403099}, NULL) = 0 <0.000018>
1061445834.403184 gettimeofday({1061445834, 403228}, NULL) = 0 <0.000018>
1061445834.403355 ioctl(3, FIONREAD, [0]) = 0 <0.000020>
1061445834.403489 gettimeofday({1061445834, 403532}, NULL) = 0 <0.000019>
1061445834.403617 gettimeofday({1061445834, 403661}, NULL) = 0 <0.000018>
1061445834.403745 ioctl(3, FIONREAD, [0]) = 0 <0.000019>
1061445834.403876 gettimeofday({1061445834, 403919}, NULL) = 0 <0.000018>
1061445834.404002 gettimeofday({1061445834, 404045}, NULL) = 0 <0.000018>
1061445834.404176 ioctl(3, FIONREAD, [0]) = 0 <0.000021>

<ZZZZZ... and after ~2 seconds uninterrupted thumb twiddling>

1061445836.306958 ioctl(3, FIONREAD, [32]) = 0 <0.001824>
1061445836.308935 read(3, "\6\0\357\"\23\36\32#?\0\0\0\2\0\300\1\0\0\0\0\0\0p\1\0"..., 32) = 32 <0.000028>
1061445836.309194 gettimeofday({1061445836, 309240}, NULL) = 0 <0.000019>
1061445836.309331 ioctl(3, FIONREAD, [0]) = 0 <0.000021>
1061445836.309496 write(3, "(l\4\0?\0\0\0\2\0\300\1\0\0p\1", 16) = 16 <0.000029>
1061445836.309672 read(3, 0xbffff2c4, 32) = -1 EAGAIN (Resource temporarily unavailable) <0.000022>