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/