NetNews Usenet Archive 1992 #31/NN_1992_31.iso/spool/comp/programm/3341

Internet Message Format | 1992-12-21 | 5.3 KB

Path: sparky!uunet!zaphod.mps.ohio-state.edu!magnus.acs.ohio-state.edu!usenet.ins.cwru.edu!slc6!trier
From: [e-mail] (Stephen C. Trier)
Newsgroups: comp.programming
Subject: Re: Semaphores, Swap, or Test_And_Set
Date: 21 Dec 1992 18:45:13 GMT
Organization: Case Western Reserve University, Cleveland OH (USA)
Lines: 133
Message-ID: <[e-mail]>
References: <[e-mail]> <[e-mail]> <[e-mail]>
NNTP-Posting-Host: slc6.ins.cwru.edu

In article <[e-mail]> [e-mail] (Mr. Joseph Reagle; MEYERHOFF (U)) writes:
>    Sounds like a pain, I'm not familiar with how DOS deals with
>deals with interupts whether priority based, FCFS, interupts could
>occur but only queued ...

Yes, they are priority based and there is a mechanism for merely delaying
them until after interrupts are unmasked, rather than dropping them
entirely.  However, if a second interrupt comes in at the same priority
level, the record that there was a first interrupt gets lost.

This was pounded into my head when I was investigating (1) why my network
code was sometimes dropping packets, and (2) why my system clock ran slow
when I used a SLIP (Serial-Line IP) driver.  In both cases, the interrupts
were getting masked and in certain rare cases, this caused a critical
interrupt to get lost.

>    Don't know what xchg does and I am not quite sure how to
>implement test_and_set using inc or dec.

XCHG is "exchange", the classic test-and-set instruction.  Here's some
minimal assembly code.  It wouldn't be hard to turn this into properly
C-callable code.

; Test and set the word "flag"
test_and_set:
      mov ax, 1      ; Put a 1 in the AX register
      xchg ax, flag  ; Exchange with flag variable
      ret            ; Return a 1 in AX if we did NOT get the flag.
                     ; Return a 0 if we DID get the flag.
                     ; Note that ZF is not set.  Must look in AX directly.

clear_flag:
      xor ax, ax     ; Get a 0 into AX.
      mov flag, ax   ; Clear the flag, saying we're done.
      ret

You could use this basic pair of primitives to build and sort of mutual
exclusion mechanism you would like.  Making them more sophisticated
requires at least a busy-loop; if you want to guarantee fairness, you
need some slick algorithms or interaction with the process scheduler.

The INC/DEC approach does the same thing, just a little differently.
Here's some code I wrote to do it:

/*
 *  C function to initialize a semaphore.
 */

void sem_init(int *p)
{
    *p = -1;
}

; Assembly code to manipulate semaphores.

; int sem_set(int *p)    Set a semaphore.  Return 1 if semaphore OK, 0 if not.

_sem_set proc near
    push    bp            ; Set up a standard stack frame
    mov    bp, sp            ;       "              "
    mov    bx, word ptr [bx+4]    ; Get the address of the semaphore
    lock inc word ptr [bx]        ; Increment it and maybe set Zero Flag
    jz    success            ; Success if ZF is set.
failure:
    lock dec word ptr [bx]        ; ZF not set; remove our increment
    xor    ax,ax            ; Return 0 (false) to C
    pop    bp            ; Clean up stack frame and return
    ret
success:
    mov    ax,1            ; Return 1 (true) to C
    pop    bp            ; Clean up and return
    ret
_sem_set endp

; void sem_clear(int *p)   Clear a semaphore

_sem_clear proc near
    push    bp            ; Set up standard stack frame
    mov    bp, sp
    mov    bx, word ptr [bp+4]    ; Get address of the semaphore
    lock dec word ptr [bx]        ; Decrement it
    pop    bp            ; Clean up stack frame and return
    ret
_sem_clear endp

Please excuse any ugliness in my 8086 style.  Most of my assembly
programming has been in the 680X/680X0 families and I still feel a little
awkward on the 8086.  Everything is so _backwards_!  ;-)

This approach uses the a lock prefix to make INC and DEC atomic, even
on multiprocessors.  It depends on the flag-setting behavior of INC and
DEC, in that ZF, the Zero Flag, will be set if the result of the increment
is 0.  It will not be set to 0 at any other time.

You could regard the assembly as being somewhat like the following C code:

int sem_set(int *p)
{
    if ((*p)++ == 0)
        return 1;
    else  {
        (*p)--;
        return 0;
    }
}

void sem_clear(int *p)
{
    (*p)--;
}

The difference between this and the assembly is that instruction selection
(and the LOCK prefix) is essential for this to work right, so it is best
not to trust that the compiler will get it right.  The only way to guarantee
that it's done right is to do it yourself.

There are some who might disagree with my referring to these as semaphores,
since they are non-blocking and cannot be used as counting semaphores.  If
it makes you feel better, think of them as semaphore building blocks, around
which you can build whatever sort of fancy setup you want.

BTW, it should be trivial to turn these into counting semaphores.  I'm just
using them for simple mutual exclusion, so I do not need anything that fancy.

I'd eventually like to rewrite this in inline assembly in C, and perhaps
to switch to the shorter and simpler xchg sequence.  This works, though,
and right now, that's what I need in order to get this software out the door.

--
Stephen Trier                      "We want to offer you a price that you
Network software type               just can't afford to take advantage of."
Case Western Reserve University         - Sales blurb from HSC Software
[e-mail]