[LWN Logo]

From:	Davide Libenzi <dlibenzi@maticad.it>
To:	linux-kernel@vger.rutgers.edu
Subject: Auto-Adaptive scheduler and semaphore patch ( 2.2.14 ) ...
Date:	Mon, 24 Jan 2000 23:08:52 +0100


--Boundary-=_XrJmOWFrxsjyBldbEFSArCBynEcd
Content-Type: text/plain
Content-Transfer-Encoding: 8bit


Hi guys,

this is the first version of the auto-adaptive scheduler whose
target is to maintain the same performance under low workloads
and boosts under high ones.
It uses the linear-scheduler ( current one ) implementation for low workloads
and switch to the cluster-scheduler under high workloads.
The cluster-scheduler boot at an entry point and after a delay time that can be
made software adjustable ( proc fs as an example ).

The patch also contain :

<OLDDESC>
* A clustering subdivision of processes in function of their goodness
 This avoid the linear scan of the running queue to find the
 next process to run.
 My test prove that even in high workloaded environment
 not more than two goodnesses are calculated.

* As IBM guys suggested I've reorganized a bit the fields in task_struct
 to reduce the cache footprint

* A wake_up patch that has the goodness calculation inside it.
 This avoid flushing all waiting threads onto the scheduler 
 shoulders.
 IMVHO this is better than the current because avoid the thread 
 flushing, and is better then a simple FIFO coz it try to select the 
 best taks to run.
 This is 100% precise in UP while it's not in SMP due to the fact 
 that we don't know which CPU will reschedule the task.
 Anyway even if in SMP the precision is not 100%, it's better 
 than FIFO.

</OLDDESC>

I'm just setting up an lmbench for this patch and I'll post results
as long as a doc describing the patch, as soon as test is completed
( and doc too ).

I'll be happy if other guys will give it a try ;)

Davide.

-- 
All this stuff is IMVHO


--Boundary-=_XrJmOWFrxsjyBldbEFSArCBynEcd
Content-Type: application/x-gzip;
  name="adapt-sched-2.2.14.gz"
Content-Transfer-Encoding: base64
Content-Disposition: attachment; filename="adapt-sched-2.2.14.gz"

H4sICDLKjDgAA2FkYXB0LXNjaGVkLTIuMi4xNADsXHlz28aS/xv6FCOlViFFkCapw5YUK5Et2dZG
1+rY7KtsCgUBQxFPuIxDR7L+7tvHDDAASVnOy9arrXo+RGLu6enj1z0N+cFkIvrXYkP0MxEGcfnY
Hw/Gg9HG4N6NgzB0XwWxF5a+fEWVr3JvKv3BtNF0fpOlfr//DSNaV9NS/LsbC7ElhsOd9RH8E+Ph
cLjU6/VeMJ116RbUfzzG/sPtnc033P+nn0R/PN6y34gefow2xE8/LQmxJspcZmLq5ra4KQsRFPhd
FFMp0qSQcRG4oSgSUWSudyciGSXZE3Rxb6WQhTfAEV4tibzISq+goRz+vrsklnqv1sSHJBOFm9+J
2yTxY5nnAladFzIL4lvs2lNdb/3cycOkUN3FH0s9S33F7rp4zXFi+Qijz6+F6jTN5D3Uf4H/1cLM
Rn8sCVgXbDCXws0kbDfzvcSXvugLP4m/h9ZJ6U1pX9Z9ErpFEEoRJrDevHALuWtB9/5IlHFWxrF7
E0pbDEX9fW8I7ZI0hQFpiDLOg9sYnmiISeje5jRECmRPs8RDmlCpLXw5CbDljQyTB+xNh7a+bY+2
4NQ2Nu3xkE5N710+Ss/xk8gNYrFmPADxLZotltJ3MknMgSeCO793syApYc5Ahn5OZ2B5T14oc6cQ
7v0tHEPgSaRwc+VpAuVP1dBeUsZwjNVzCqNmQQEN+vOHg6kV+0RuDPwTAXOJIJ4kvAS1pSiqDjOK
dmnBlyfnwo19JPHnUpaSj4GJG8TEr46XlrvqUdE0yXRB6OaFM1uaeHeOL9NiumvhcRzDs6DngfhF
Cg9kyEtgh4+FyB+CAhgCiIzLSEBKkomYJqGPPOyK/Cn33DAUdzKLZUgDDwYDWJ9Vb6vN3rd5vluf
Y4OHkb8dLLHFGvIyfX+2MRDGFqoxfNcHTWJX0YpY6c3Q3gZO2sYPk5GaQlS4WeY+OWmR0VC60YMb
FA6fwBp996ahLx+Dgth5AoKOpRudLh+N6pXLyE2nCQja2j20gWlkxBTHHlTEPfpz+c0WGR6e5q02
UzYq27IGS8ykGzr3bliCYAbEBRPj8T6A/vS4uDOo2azuWz1RV3wyTyaIQP+FQV4I6krPZn2UUxs4
ejyN9dG6PRqK3vp4HbQyHgcSBZQNMFQhI5KNLAL1k8QNik7y6qgmOYtIksqYui7uhOPW/fAJJPVZ
mewvkkmaEmkFpmEKIhHKLFeTpUFMglVgfYRchY/EIOcZ2BOvyHVPlKUbrNWKUjMMVVczwqMi19bY
HgH3rr8e2mDdlPV6SspMJA+xyIL8bnkg3rm5fDu0wVRGQfF2+Dia4B/ReTs+eddV1uo71rPi6PTo
yrnav/xZ/DdviWQFzBrK7h9iaOPfnw8vTg+PnYNLexW6uWVYOIamhQbQGemo9CF2PTj84JxfHJ1d
HF39zW48UGvUhJVixPZVKbM8Fl2+/3R44JxdfTq8sMXi8VS/KMI+q0EMjBlFttoO6k0aHf/2R7ox
qB7e3+n18bFNP8UX3YcsBSCKu3pAUkXGV7HoO49wA+wTFdidx+dS6dk3mVaLvCL+q+rTwCc80arX
taC8Efzc5WuvxPxV0WT1j3pYsA7TejVmJas52igO8evwN12Dio2U2WxHPGqUYbQCrXMa2q2N9Zpt
Z+qFqs/a5wGAgv5pHTSJ6xMqsQd1UCN9MegEQ70/v2YlA20EtMGe6oMbTcKZ1UANSdj2CM3DxnBc
66Mg9RZQj9mIZejysho9rzlnklelqG+MCnzU1JzPvKwFqM/l+dGpc3z2/mfn+hQ/Dg8036lGsME/
hl++VB+8zJo5BtCO7Jamq+JJEGOBCklRA4u/gHbzv+oMsKV/hbZr4DVReaNqMfhvNCPQfgbKbrwO
WH1nuL6zPhaj7e3tWdDf7PchCxjsg48w3tnc3Nlcr8H+1pttBPv4MWJ1aaX9vfzBTVMEquKtGO1y
GdpwRUso9cD8SYcQqVgV7y+PPp7uH6uWqS/dYlq3HWqYf9WA+Ih0gt9lNmBoBx1B6QwYukMvPJ9d
s5wwe10Bc71agx+g3ldygOdyRfhPsRsFXoUyASIXDxKMXgrVYLPQmHjTIPRtQPYl+S88QJEUaGsi
1M4I21oDBcCWgOvQ3VFW109kDk09MGy30uZBIoQvpBrLEDHfxA0y3OhAXE0DGCAXSRw+iSBKk6xw
yYTSkJMgy4uX8xP7cPMZStV9laNUu5YfOX69szle4Ee2Op4AcCCe2kCeWge2GtU8NSKo0sOPTUaQ
2pYCXnYUhWQn7YrOqItA4TsZw/aRSfAvMMpSTyziFtGBU70F0nUH2Ao4Rw9+sv9fzseDS8vaeIOc
0bPoDwx0mIOqA6PtA355DKIyqkclWDcQRuN9wOiEiQHOTwG334JuRYsN7I6m/wlPrYNTXR6fXV2C
NzjChejuxnKw3rn8dPThyhoisrmcBhNAWK5XAKJFVIs7At8SpolkEXiDRm/YiHN5dXhudUbihx+M
wbqolD5WVClkOkMEWpnVUfQQr6rBqO9pGd3gfiZN2uaz08MwHa9rdeCH2Nsz16CO6Qq4F3xc4Owb
6bng16uRkNsB9BJQREf1SYwwOnAnYbG06yERQHlbIFxov0A05OPURbffH8xSElf0bv/ysJPjiuAn
kb5Fm2pdsAI6OD5gmq3aLRwgLaJ1ikLGeQkSXEyhm8tMkDMnkqBCKXcDEBdFJMoXV8YeuhQnIE0C
VYXMaetygloBdSeohHkce3x0eg3ndHZ2cHp4eWmNhiR+sImTNq+mSZ4HN4TeeSX5fCrBqEgkRaUf
2vvsih8RdSC/dtqUFT3RmWU47rUzZ7ma4BeyKDPWZqaTmCYBoV0iHvrJrlJ5bUeXGxKnrOQrjW1d
4fI+He4fqD3N80VBkQCTgg3Ar6vQsL/HZgTXrvYKXWGOVssFow27pi3CQao+wy78Ubs+4BXihhBF
YAysij6Eievzvh8C1ChZcHuLlCizmwQshS9nxO34bP/g6uLo48fDC2tz8Qy+DEEJ0cg8mNanGc9E
gBTMWBCKmyQpZqb5ZR+gGIKlS2vMsyxQtjlxa3VUOSDf6gwxkFEJqyEDaGBB9PK7gCJbkyyJYH1g
J5Bltd6vFDd6UmBkFwU/9MQObv3Xiol/20XDL46gEGwphhhBteSphMFTRZJq4y+cwRy86oThH/gK
Djy0g1Z6Wl8+CjzWaeBNuQEgcJlVzrTZn5bDFo+7X7WOjINGhO0XdXTwRNFl5oCgwRJ/hhUWzIHs
qnh0VzRn+UaWfoH9BmtfW28EcvcJOHY1cnImZewhOTEUgQcABJIdbNQVfxD4Foj8xFoFrAhGqU68
RF96gQ8cOU0e4HseZIRm3SqWGuSDAbszmxTt3hi+tkcbrxkBc6RBRUSBnk7gww/YwQOAll3G/98M
UxTPggxDfdv2ekHmlaGLyC8HyTOPioiDrIpiwFRY6mHgG88wCBAJ9yw0cJ0gILANhaD1K5bG516v
S7Fyq2b5IPjNwNSr7QodP5/podB5rZabXbvY6QutKZKRlz51mnJs11Jng/v2u0wmrRbdLm/JlD2Y
sGHEcBKDfXnbiLFYHGMRY3grrLnSmitQ0K+pElvjmmKh2hpaGq8PFL/v+z6DRlBFHfgGEtdtHjEU
PyDmX9HiRCGvFWCPpliGKHbVkReu75NzOtdQgXetWAF5q/g+N3wLWAjAlLQsWIhngG8FJpBz8Cxg
FBgxT5SEc2wbryiUdpNNHQ76D/yqB/ReQJorueJRaAgMfJGxIDBWzQsmIcjlgBq+Ulz8IIPbKR6y
btbBFfF/cCd1UL5rI0Mqfhguut0Rn6e7TJLDORZqgqZLA6ghksklaqMNwR0DsaKWtVLrnIiOWuce
oAAoIYHC4o5aUgWauV13HvgiMNLrsUGBNf4iZ2BxGwwbq6eVWDLMJY2zSDRoVVS51zBhPHtLsKql
XKc+HXNlzJRxQ4uniAD8bn2eLhJ//MkKAI+t6bR/njZKsNFaqwxaFfkuzdAuX60H1IqpWUIzLBTI
qQTL9ZcI5PRfAvkvgfx/KJDUpparWSH6J8nphYySe1mJ6p+XUORa3HhGA75ERPFIWvtXIKm55Nm9
z1DIWpsl5Cwl5lBbxzgBa5ID3Rlp/FSVDLsGuS75jpnIRc5VC0b+KZ3GPsgLqNWmL1R2NUSskQqU
Giu+zkFe3AlGAVzTO4PDziRAMJkVKtICMq6SPv6hfTBMfn4ziw9ihlt1heYWfZX+/MY5gCNdFVBS
vpOK/aGTzO6JgFHrtAHGrA5hVmiGoRKColgwUL4Gqu4IiATOhcB0AiAuRaJUnIn8NQkV6EwUOG2S
sht/hLfNyFG5GOG04BliDBsTE2gBmJ2SQPfsgY3BMyJWZE+aZwxvxPSaFbYeMpBH0sUZEi3GsPje
IsdTSR82XzaaqGIqBz1NY+/Nd5B105ZvwCrYssx14bMSMVWNQkc/vgjU5/Vi/tK16LnbzpEt2n5S
2zkiv+hbtlErkSHz5Tc75r3K0X7vZnJShsv4UHvelAMGBhvBFqaCKd8aE8Hg0SEHGM/cwWgzXraQ
w/0aLw57m3hRP2J/u76D0+IF20vVbZJRxJpUWKyWdSaLblvzWK8HGxbwp4UEv8W8zBy9FvgaAlax
ADFHI/kydFBFO3r4+Top7S4BoxBd3mwQXV6/rugyu08yOEAW+JxLmSa9WHnxnVw9iFJpij7/gAVe
SCLTSDxLJGpGmVcvpdLGcEhU2t6yR+vqvpJVeM1ERoqTNVtqsNZLKJvWpHpPt31/DanqcEybWDN2
JVWY4Hkq0i3iy8k4oqjX1uh1RUZl8GZlcfcvktB/ChmnC8hYBRB5IRh2o6lQiXECEpntIMbEI0rW
AhVW4f6BujvfwkyIN9tjlSjn5hH2wJi0GdJUsUukfZ2/pEOLAPFdoVJq6GFREh8S0+ZcPsz5wwxK
iuKCIsbERlt4u8p7M4psBQfAaAdpzol6RMPP1T1sBgsDWiVwFJym5ZiV0MV8dG5c726Hdv96RLe8
26NtnSZs1ZtAX0C4IWXKUcGvelG/DRpbV7mDYNKI/E6Qfe6sNg6/S9kDVotxXsg17P6ey2zqpjkR
htxoQE/ILVWa5gRUkEjdYmq4wQt0m0I+5C7oLAQaDHCd4SJeXJjmEOZDLUeJS+oEWNGoXK63bwXn
CF1c1KdB/JxlpB+BBvrROIH1ob0BDLi9AQyocn4tzwXsgulqzsX16enR6ccdKP1iaLY617dKzbBM
JtHADTgnlW5Rnf0OnZROuSiMyHt97QBbTmW2o0PowKLpQpXCtwyYKmdSKpchSJ8mlNZJxJWEsRUX
IVNYHlT18cJ0t0FTTtADkppUqMmaF0EYaqSwu9R8VtTFlcNO+5Zxx5CXN0UI0JgKT0FJ0N2CistI
SusWdN2ZlSmoD7yzsIW8lzH3KKZJeTs1W2A/hE51NEEBJ1hLnzsRM9f5I/qW3Y2fQNM+GD3xRoa7
AKvBoNLXgwEG4ZwWfFD5TXkiVtIV4d4AS3GvgDwBdyI5xhBQZi2sVW0XV8SXQABrJMUiKNda9pPM
5yz9INeqk+5x9aZN7kChpPLFmpzvNEBx1aA4ch9tFZAirT5PN3KEibIsKGY0e5n5rIqoTpTiZCtB
gBGlFbrGXHjVWYes1AgUCarvYcygjt5PdT2zx5/9vvYSFsdw9J2KimylM3GcrljGosrfYJJBs0ZC
QBB0KaZ0AlXtTAhlW9UUy7zWrgKHkrJFnotBWbMhLDzCXo8H2q2H9sTeW3WkXdWRRJLOcpKUsa8a
+4neDfdrpg1VW1U0mY1Wsq1M7coUQp894RkdSXlwR1soNZPuVrULVrtwwcrvqj+/4AUxaAQ+sXTe
gRn+mmXm9KiILHlXN5i9pgO30kdB+P4eY8QwNUnXOejywMfktmV9GtXam9kdwAFqG/O2wFd2pJQT
VGpoJzhI06/DCSp7Of9RTUXU98QPwNZdsbradPNBBKLUicsI6Z9T/bJpZ3gxtBYjZMEhA9MF51Su
OYrYkNuXamLu8q2qmHt9my7mPt+sjLnbYm3M9X9CHeudz+hjpbs0IEZyLmO7DO8onoSbAgjIaIcc
pkviijBqCSVNiJJmAwKmUQzSYlIUn4k/EJ+SBziHDOVSPnEaAZAoRRAWN4hDoyDsJvpg9j5h8Ioc
qKaBaLBLpDm9fxY+iUnwCLNw/n7fUgKYorjVab6oA/oL1UrfshZcgMyqlF1ubV5DeF0qW6xcFsEh
Er7FC67EeoEifPmSK11srrn3FY3IOkopMhPDQU1/TkWviuN5i6ScMCmhrBcrnH41ZH+B3qh12k4j
P5hC5YRYSYyQ2eIEnvEFNZB8pBNqUHzdDVpyH8b5xNksu0QSfochdzFiguNhSBcOVHWp3B/2D9+M
wTXaFL3R8M3YXle5JRySI7fHWD5CZuK+uZ4fcRr5SGW82EvqYyjQ9emxs9rwarkWwIkjXW+q/WHi
VTg4/VLKW+C9+mlvD5Mie4LiJPVbezwHr2PuLF/x5RTIU4lP6IO0Yspdg3/mhF4XEKhnPbt7LUDL
et5KdNpEqSDCtxFGoRnDQdTCxsJjWrT/s0n57qM9c02bRafWa63vGRp/lQtfcBAzfNj7c1v/2p5e
wIoK9vR6zTBJr/IWW06wVlxNr5HdcYyEYNr7aHvDfsNBtaQsdkyZ/8I57jrn0vCh0cDi+8WcGV69
Dfng3slSXeHs5+JvSclpABKvhWFxoUR3n66AcJQbmfMbmKS30AuSj55MC04OoFHQn6mxilawbKar
9Gu+MlKpdBRROEItOcF0v6S6sueYv7ynF4WDKA0p4dut8AiNotfohmF10QdzuD4F1GSGLyIC2gH6
T93slq+sCLKpTcdPDwBDcnzXOg+KkkfPYLmw5cTzSry3wEzQnN+/yOhlbTBi6LQwaWmcuMp6b5AH
l0mJ/pMK4GAXL+GAn6veDNGb4GzwHK0H4hKcR12Y4AWbiixR/EFlSgKV8AU7fmuEx65fcVfKHzek
xhwNh/+GJPUCTCiAUf1SVtgRTY3OBeFX0O9ixL2UiIovdBGeqrMWq3Rsk5K2ODr5z09ntnGgyIV5
EpacPJmIHWoOIueKD0cfzujNh9l1SFwGqG222UyeigWJth0BhhgmuD5HrwWOxdyd6NIsY5xlxeCR
FRFJwOe+npEWY1n7XeAV964RhBWTsMyndAPaBLbc5V2X4OK9JnBeylxdbVFw1sF3jB0UMKdMdbzc
fHt57bMtqrd90WbhRWx12zlHQ9pijXZf3xrPGRVzkVQYV8drEXgNa5SGb1eVGb6wZKTa1Fepy585
FonaCfQLp9Ys9cygHLkOHHb08fSM22GgkXdXOS9BwR0j6cbIgfi7BUD0Yg/8kr/jNbPO4MewHhEy
ryOklFX1VlD25H9cH14fcuziszLghhHA/bc0rwKYa5/15foyucbmzpRq59EUNqZuAI9xbmU1U3Xt
0N/jV+ChSA3OpVX6BUUIdXhwlU9TGTwMHIGbg6kVmoWRbsjaZdzwq78JgKtjfAkGrxCAicIVN6Wz
9lxf8NLvzsBYAKjAH+vAGnZUQyoG17/agKt0kkll82GcM3qb9WkgLmY0dgdftJyKZdFVtHju6K3G
2Rp+zZyzm3d4C07vueOb2WRqBlcUrWqO2tHcqbHDLH+S4e5VhltndVRu8qW20Gw5K+MHmqLM+Rc+
FA9JH02XMrE71X3TCpWs0K/Y4FhFjvkg1etSiAAQHlUpfEJn8AE64dBEHkoJPMWERZZdAQrAtI1B
GZRs4uVUb7Q+HOubPnL3lQqsNZ/xGxjgq7qsIrrii55oWztYDrT4LpiAmhBnxwfO5eHJ/vmns4tD
5+Tw6tPZge4Cw65C6/4eUpb6qBS5ptKt29gcrL8+PTq9Ory4uD6/Onp3fCj+h4sbhTwcvzBoXuWd
KyxB5PCTh3ileiVgIPQbSr/LLGlBLNf7XAaZ9G3+5RfDrbG9ib9HZbRlbxG99PXnzbRzdXRyeOG8
+2Sr3+JwM+3umtUsC1TP/NRqcHRycnhwtH/FbYIokn4A7MzNelaV5c935v87AOHXwvZwSAAA

--Boundary-=_XrJmOWFrxsjyBldbEFSArCBynEcd--

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/