Poor performance of UPDATE against busy table

We have a table being used as a job queue. There's one 'scheduler'
process that manipulates jobs (inserting, updating, and deleting rows/jobs as
they change status). There are a number (~24) of processes reading and
updating rows as they 'claim' and 'complete' jobs.

Our problem is that throughput on this table is fairly low. Updates by
the 'scheduler' sometimes take 15 seconds (!!).  We've tried various
combinations of LOCK TABLE commands, but without much success.

Does anyone know if there are ways to improve the performance of UPDATE
against a table where there are many readers?


--
Jeff Boes                                             vox 616.226.9550
Database Engineer                                     fax 616.349.9076
Nexcerpt, Inc.                                      jboes@nexcerpt.com