CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Multiple spin-block decisions

Peter Damaschke (Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers))
Algorithmica (0178-4617). Vol. 44 (2006), 1, p. 33-48.
[Artikel, refereegranskad vetenskaplig]

We study the online problem of holding a number of idle threads on an application server, which we have ready for processing new requests. The problem stems from the fact that both creating/deleting and holding threads is costly, but future requests and completion times are unpredictable. We propose a practical scheme of barely random discrete algorithms with competitive ratio arbitrarily close to e/(e-1), where e=2.718... is Euler's number. The competitive ratio is sharply concentrated for any input. The results are generalizations of the well-known result for the rent-to-buy problem.

Nyckelord: multithreading, spin-block problem, online algorithms, randomization, implementation issues

Denna post skapades 2006-08-25. Senast ändrad 2015-02-11.
CPL Pubid: 11166


Institutioner (Chalmers)

Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers)


Teoretisk datalogi

Chalmers infrastruktur