Conference noted::hackers_v1

527.0. "Arbitration algorithms, anyone?" by MAY20::MINOW (Je suis Marxist, tendance Groucho) Wed Aug 05 1987 12:52

I'm developing a disk controller for a scsi bus (no, it's not a product)
that has the following overall organization:

    acquire(bus_mutex);		/* gain exclusive access to scsi bus	*/
    arbitrate for scsi bus;	/* try to gain access to bus itself	*/
    if (success) {
	perform operation;
	eventually releasing bus;
    }
    release(bus_mutex);

There is one of the above for all devices on the bus.  The problem is
that, to handle overlapped seeks, one of the operations is, roughly,

    start seek;
    release bus;
    release(bus_mutex);
    wait for reselection;
    acquire(bus_mutex);
    continue operation;

When the disk is ready, it arbitrates for the scsi bus and sends my
controller a "reselection" message, which eventually restarts the
reselection code (the bus is seized at that point).  There is a bit
of tapdancing along the way as to who owns the bus that I'll not bore
you with.

You have probably noticed that there is a potential deadly embrace in
the above -- the "mainline" acquires the mutex semaphore, but cannot
acquire the bus because some other device has just initiated a
reselection, but the reselection code, that has the bus, cannot continue
because it cannot acquire the semaphore.

I've solved the problem for now by rewriting the top-level as

    for (count = 0; count < (nunits * 2); count++) {
	acquire(bus_mutex)
	arbitrate for scsi bus;
	if (success) break;		/* Exit loop			*/
	else {
	    release(bus_mutex);
	    sleep(1 msec);		/* Force me to end of run queue	*/
	}
    }
    if (success) {
	onward...
    }

This seems to work, but it's a bit clumsy.  Anyone have any better ideas?

Martin.

    why do you need the bus_mutex?

The mutex queues up requestors -- for example for multiple disk units.
Without the mutex, I'd only have the "sleep" backoff.  Using the mutex,
unit 2 will start up as soon as unit 1 completes.

It's not clear from my description, but the probability of hitting
the "sleep" code is quite low.  Unfortunately, it isn't zero.

Martin.

    The PPLRTL implements counting semaphores in shared memory.
    Press <SELECT> to add it CLT::PPLRTL to your conference.

DECWhiz ?  It sounds like something you spread on toast.  Opinions differ
as to whether it matches Velveeta or not...