The Art of
ASSEMBLY LANGUAGE PROGRAMMING

Chapter Nineteen (Part 13)

Table of Content

Chapter Nineteen (Part 15) 

CHAPTER NINETEEN:
PROCESSES COROUTINES AND CONCURRENCY (Part 14)
19.5.3 - The UCR Standard Library Semaphore Support
19.5.4 - Using Semaphores to Protect Critical Regions
19.5.5 - Using Semaphores for Barrier Synchronization

19.5.3 The UCR Standard Library Semaphore Support

The UCR Standard Library process package provides two functions to manipulate semaphore variables: WaitSemaph and RlsSemaph. These functions wait and signal a semaphore respectively. These routines mesh with the process management facilities making it easy to implement synchronization using semaphores in your programs.

The process package provides the following definition for a semaphore data type:

semaphore       struct
SemaCnt         word    1
smaphrLst       dword   ?
endsmaphrLst    dword   ?
semaphore       ends

The SemaCnt field determines how many more processes can share a resource (if positive) or how many processes are currently waiting for the resource (if negative). By default this field is initialized to the value one. This allows one process at a time to use the resource protected by the semaphore. Each time a process waits on a semaphore it decrements this field. If the decremented result is positive or zero the wait operation immediately returns. If the decremented result is negative then the wait operation moves the current process' pcb from the run queue to the semaphore queue defined by the smaphrLst and endsmaphrLst fields in the structure above.

Most of the time you will use the default value of one for the SemaCnt field. There are some occasions though when you might want to allow more than one process access to some resource. For example suppose you've developed a multiplayer game that communicates between different machines using the serial communications port or a network adapter card. You might have an area in the game which has room for only two players at a time. For example players could be racing to a particular "transporter" room in an alien space ship but there is room for only two players in the transporter room at a time. By initializing the semaphore variable to two rather than one the wait operation would allow two players to continue at one time rather than just one. When the third player attempts to enter the transporter room the WaitSemaph function would block the player from entering the room until one of the other players left (perhaps by "transporting out" of the room).

To use the WaitSemaph or RlsSemaph function is very easy; just load the es:di register pair with the address of desired semaphore variable and issue the appropriate function call. RlsSemaph always returns immediately (assuming a timer interrupt doesn't occur while in RlsSemaph) the WaitSemaph call returns when the semaphore will allow access to the resource it protects. Examples of these two calls appear in the next section.

Like the Standard Library coroutine and process packages the semaphore package only preserves the 16 bit register set of the 80x86 CPU. If you want to use the 32 bit register set of the 80386 and later processors you will need to modify the source code for the WaitSemaph and RlsSemaph functions. The code you need to change is almost identical to the code in the coroutine and process packages so this is nearly a trivial change. Do keep in mind though that you will need to change this code if you use any 32 bit facilities of the 80386 and later processors.

19.5.4 Using Semaphores to Protect Critical Regions

You can use semaphores to provide mutually exclusive access to any resource. For example if several processes want to use the printer you can create a semaphore that allows access to the printer by only one process at a time (a good example of a process that will be in the "critical region" for several minutes at a time). However the most common task for a semaphore is to protect a critical region from reentry. Three common examples of code you need to protect from reentry include DOS calls BIOS calls and various Standard Library calls. Semaphores are ideal for controlling access to these functions.

To protect DOS from reentry by several different processes you need only create a DOSsmaph variable and issue appropriate WaitSemaph and RlsSemaph calls around the call to DOS. The following sample code demonstrates how to do this.

; MULTIDOS.ASM
;
; This program demonstrates how to use semaphores to protect DOS calls.

.xlist
include         stdlib.a
includelib      stdlib.lib
.list


dseg            segment para public 'data'

DOSsmaph        semaphore       {}

; Macros to wait and release the DOS semaphore:

DOSWait         macro
push    es
push    di
lesi    DOSsmaph
WaitSemaph
pop     di
pop     es
endm

DOSRls          macro
push    es
push    di
lesi    DOSsmaph
RlsSemaph
pop     di
pop     es
endm




; PCB for our background process:

BkgndPCB        pcb     {0
offset EndStk2
seg EndStk2}

; Data the foreground and background processes print:

StrPtrs1        dword   str1_a
str1_b
str1_c
str1_d
str1_e
str1_f
dword   str1_g
str1_h
str1_i
str1_j
str1_k
str1_l
dword   0

str1_a          byte    "Foreground: string 'a'"
cr
lf
0
str1_b          byte    "Foreground: string 'b'"
cr
lf
0
str1_c          byte    "Foreground: string 'c'"
cr
lf
0
str1_d          byte    "Foreground: string 'd'"
cr
lf
0
str1_e          byte    "Foreground: string 'e'"
cr
lf
0
str1_f          byte    "Foreground: string 'f'"
cr
lf
0
str1_g          byte    "Foreground: string 'g'"
cr
lf
0
str1_h          byte    "Foreground: string 'h'"
cr
lf
0
str1_i          byte    "Foreground: string 'i'"
cr
lf
0
str1_j          byte    "Foreground: string 'j'"
cr
lf
0
str1_k          byte    "Foreground: string 'k'"
cr
lf
0
str1_l          byte    "Foreground: string 'l'"
cr
lf
0

StrPtrs2        dword   str2_a
str2_b
str2_c
str2_d
str2_e
str2_f
dword   str2_g
str2_h
str2_i
dword   0

str2_a          byte    "Background: string 'a'"
cr
lf
0
str2_b          byte    "Background: string 'b'"
cr
lf
0
str2_c          byte    "Background: string 'c'"
cr
lf
0
str2_d          byte    "Background: string 'd'"
cr
lf
0
str2_e          byte    "Background: string 'e'"
cr
lf
0
str2_f          byte    "Background: string 'f'"
cr
lf
0
str2_g          byte    "Background: string 'g'"
cr
lf
0
str2_h          byte    "Background: string 'h'"
cr
lf
0
str2_i          byte    "Background: string 'i'"
cr
lf
0

dseg            ends

cseg            segment para public 'code'
assume  cs:cseg
ds:dseg

; A replacement critical error handler.  This routine calls prcsquit
; if the user decides to abort the program.


CritErrMsg      byte    cr
lf
byte    "DOS Critical Error!"
cr
lf
byte    "A)bort
R)etry
I)gnore
F)ail? $"

MyInt24         proc    far
push    dx
push    ds
push    ax

push    cs
pop     ds
Int24Lp:        lea     dx
CritErrMsg
mov     ah
9                   ;DOS print string call.
int     21h

mov     ah
1                   ;DOS read character call.
int     21h
and     al
5Fh                 ;Convert l.c. -> u.c.

cmp     al
'I'                 ;Ignore?
jne     NotIgnore
pop     ax
mov     al
0
jmp     Quit24

NotIgnore:      cmp     al
'r'                 ;Retry?
jne     NotRetry
pop     ax
mov     al
1
jmp     Quit24

NotRetry:       cmp     al
'A'                 ;Abort?
jne     NotAbort
prcsquit                        ;If quitting
fix INT 8.
pop     ax
mov     al
2
jmp     Quit24

NotAbort:       cmp     al
'F'
jne     BadChar
pop     ax
mov     al
3
Quit24:         pop     ds
pop     dx
iret

BadChar:        mov     ah
2
mov     dl
7                   ;Bell character
jmp     Int24Lp
MyInt24         endp



; We will simply disable INT 23h (the break exception).

MyInt23         proc    far
iret
MyInt23         endp



; This background process calls DOS to print several strings to the
; screen.  In the meantime
the foreground process is also printing
; strings to the screen.  To prevent reentry
or at least a jumble of
; characters on the screen
this code uses semaphores to protect the
; DOS calls.  Therefore
each process will print one complete line
; then release the semaphore.  If the other process is waiting it will
; print its line.

BackGround      proc
mov     ax
dseg
mov     ds
ax
lea     bx
StrPtrs2            ;Array of str ptrs.
PrintLoop:      cmp     word ptr [bx+2]
0      ;At end of pointers?
je      BkGndDone
les     di
[bx]                ;Get string to print.
DOSWait
puts                            ;Calls DOS to print string.
DOSRls
add     bx
4                   ;Point at next str ptr.
jmp     PrintLoop

BkGndDone:      die
BackGround      endp


Main            proc
mov     ax
dseg
mov     ds
ax
mov     es
ax
meminit


; Initialize the INT 23h and INT 24h exception handler vectors.

mov     ax
0
mov     es
ax
mov     word ptr es:[24h*4]
offset MyInt24
mov     es:[24h*4 + 2]
cs
mov     word ptr es:[23h*4]
offset MyInt23
mov     es:[23h*4 + 2]
cs

prcsinit                ;Start multitasking system.

lesi    BkgndPCB        ;Fire up a new process
fork
test    ax
ax          ;Parent's return?
je      ParentPrcs
jmp     BackGround      ;Go do backgroun stuff.

; The parent process will print a bunch of strings at the same time
; the background process is doing this.  We'll use the DOS semaphore
; to protect the call to DOS that PUTS makes.

ParentPrcs:     DOSWait                         ;Force the other process
mov     cx
0                   ; to wind up waiting in
DlyLp0:         loop    DlyLp0                  ; the semaphore queue by
DlyLp1:         loop    DlyLp1                  ; delay for at least one
DlyLp2:         loop    DlyLp2                  ; clock tick.
DOSRls

lea     bx
StrPtrs1            ;Array of str ptrs.
PrintLoop:      cmp     word ptr [bx+2]
0      ;At end of pointers?
je      ForeGndDone
les     di
[bx]                ;Get string to print.
DOSWait
puts                            ;Calls DOS to print string.
DOSRls
add     bx
4                   ;Point at next str ptr.
jmp     PrintLoop

ForeGndDone:    prcsquit

Quit:           ExitPgm                         ;DOS macro to quit program.
Main            endp

cseg            ends

sseg            segment para stack 'stack'

; Here is the stack for the background process we start

stk2            byte    1024 dup (?)
EndStk2         word    ?

;Here's the stack for the main program/foreground process.

stk             byte    1024 dup (?)
sseg            ends

zzzzzzseg       segment para public 'zzzzzz'
LastBytes       db      16 dup (?)
zzzzzzseg       ends
end     Main

This program doesn't directly call DOS but it calls the Standard Library puts routine that does. In general you could use a single semaphore to protect all BIOS DOS and Standard Library calls. However this is not particularly efficient. For example the Standard Library pattern matching routines make no DOS calls; therefore waiting on the DOS semaphore to do a pattern match while some other process is making a DOS call unnecessarily delays the pattern match. There is nothing wrong with having one process do a pattern match while another is making a DOS call. Unfortunately some Standard Library routines do make DOS calls (puts is a good example) so you must use the DOS semaphore around such calls.

In theory we could use separate semaphores to protect DOS different BIOS calls and different Standard Library calls. However keeping track of all those semaphores within a program is a big task. Furthermore ensuring that a call to DOS does not also invoke an unprotected BIOS routine is a difficult task. So most programmers use a single semaphore to protect all Standard Library DOS and BIOS calls.

19.5.5 Using Semaphores for Barrier Synchronization

Although the primary use of a semaphores is to provide exclusive access to some resource there are other synchronization uses for semaphores as well. In this section we'll look at the use of the Standard Library's semaphores objects to create a barrier.

A barrier is a point in a program where a process stops and waits for other processes to synchronize (reach their respective barriers). In many respects a barrier is the dual to a semaphore. A semaphore prevents more than n processes from gaining access to some resource. A barrier does not grant access until at least n processes are requesting access.

Given the different nature of these two synchronization methods you might think that it would be difficult to use the WaitSemaph and RlsSemaph routines to implement barriers. However it turns out to be quite simple. Suppose we were to initialize the semaphore's SemaCnt field to zero rather than one. When the first process waits on this semaphore the system will immediately block that process. Likewise each additional process that waits on this semaphore will block and wait on the semaphore queue. This would normally be a disaster since there is no active process that will signal the semaphore so it will activate the blocked processes. However if we modify the wait call so that it checks the SemaCnt field before actually doing the wait the nth process can skip the wait call and reactivate the other processes. Consider the following macro:

barrier         macro   Wait4Cnt
local   AllHere
AllDone
cmp     es:[di].semaphore.SemaCnt
-(Wait4Cnt-1)
jle     AllHere
WaitSemaph
cmp     es:[di].semaphore.SemaCnt
0
je      AllDone
AllHere:        RlsSemaph
AllDone:
endm

This macro expects a single parameter that should be the number of processes (including the current process) that need to be at a barrier before any of the processes can proceed. The SemaCnt field is a negative number whose absolute value determines how many processes are currently waiting on the semaphore. If a barrier requires four processes no process can proceed until the fourth process hits the barrier; at that time the SemaCnt field will contain minus three. The macro above computes what the value of SemaCnt should be if all processes are at the barrier. If SemaCnt matches this value it signals the semaphore that begins a chain of operations with each blocked process releasing the next. When SemaCnt hits zero the last blocked process does not release the semaphore since there are no other processes waiting on the queue.

It is very important to remember to initialize the SemaCnt field to zero before using semaphores for barrier synchronization in this manner. If you do not initialize SemaCnt to zero the WaitSemaph call will probably not block any of the processes.

The following sample program provides a simple example of barrier synchronization using the Standard Library's semaphore package:

; BARRIER.ASM
;
; This sample program demonstrates how to use the Standard Library's
; semaphore objects to synchronize several processes at a barrier.
; This program is similar to the MULTIDOS.ASM program insofar as the
; background processes all print a set of strings.  However
rather than
; using an inelegant delay loop to synchronize the foreground and background
; processes
this code uses barrier synchronization to achieve this.

.xlist
include         stdlib.a
includelib      stdlib.lib
.list


dseg            segment para public 'data'

BarrierSemaph   semaphore       {0}             ;Must init SemaCnt to zero.
DOSsmaph        semaphore       {}

; Macros to wait and release the DOS semaphore:

DOSWait         macro
push    es
push    di
lesi    DOSsmaph
WaitSemaph
pop     di
pop     es
endm

DOSRls          macro
push    es
push    di
lesi    DOSsmaph
RlsSemaph
pop     di
pop     es
endm


; Macro to synchronize on a barrier:

Barrier         macro   Wait4Cnt
local   AllHere
AllDone
cmp     es:[di].semaphore.SemaCnt
-(Wait4Cnt-1)
jle     AllHere
WaitSemaph
cmp     es:[di].semaphore.SemaCnt
0
jge     AllDone
AllHere:        RlsSemaph
AllDone:
endm




; PCBs for our background processes:

BkgndPCB2       pcb     {0
offset EndStk2
seg EndStk2}
BkgndPCB3       pcb     {0
offset EndStk3
seg EndStk3}

; Data the foreground and background processes print:

StrPtrs1        dword   str1_a
str1_b
str1_c
str1_d
str1_e
str1_f
dword   str1_g
str1_h
str1_i
str1_j
str1_k
str1_l
dword   0

str1_a          byte    "Foreground: string 'a'"
cr
lf
0
str1_b          byte    "Foreground: string 'b'"
cr
lf
0
str1_c          byte    "Foreground: string 'c'"
cr
lf
0
str1_d          byte    "Foreground: string 'd'"
cr
lf
0
str1_e          byte    "Foreground: string 'e'"
cr
lf
0
str1_f          byte    "Foreground: string 'f'"
cr
lf
0
str1_g          byte    "Foreground: string 'g'"
cr
lf
0
str1_h          byte    "Foreground: string 'h'"
cr
lf
0
str1_i          byte    "Foreground: string 'i'"
cr
lf
0
str1_j          byte    "Foreground: string 'j'"
cr
lf
0
str1_k          byte    "Foreground: string 'k'"
cr
lf
0
str1_l          byte    "Foreground: string 'l'"
cr
lf
0

StrPtrs2        dword   str2_a
str2_b
str2_c
str2_d
str2_e
str2_f
dword   str2_g
str2_h
str2_i
dword   0

str2_a          byte    "Background 1: string 'a'"
cr
lf
0
str2_b          byte    "Background 1: string 'b'"
cr
lf
0
str2_c          byte    "Background 1: string 'c'"
cr
lf
0
str2_d          byte    "Background 1: string 'd'"
cr
lf
0
str2_e          byte    "Background 1: string 'e'"
cr
lf
0
str2_f          byte    "Background 1: string 'f'"
cr
lf
0
str2_g          byte    "Background 1: string 'g'"
cr
lf
0
str2_h          byte    "Background 1: string 'h'"
cr
lf
0
str2_i          byte    "Background 1: string 'i'"
cr
lf
0

StrPtrs3        dword   str3_a
str3_b
str3_c
str3_d
str3_e
str3_f
dword   str3_g
str3_h
str3_i
dword   0

str3_a          byte    "Background 2: string 'j'"
cr
lf
0
str3_b          byte    "Background 2: string 'k'"
cr
lf
0
str3_c          byte    "Background 2: string 'l'"
cr
lf
0
str3_d          byte    "Background 2: string 'm'"
cr
lf
0
str3_e          byte    "Background 2: string 'n'"
cr
lf
0
str3_f          byte    "Background 2: string 'o'"
cr
lf
0
str3_g          byte    "Background 2: string 'p'"
cr
lf
0
str3_h          byte    "Background 2: string 'q'"
cr
lf
0
str3_i          byte    "Background 2: string 'r'"
cr
lf
0

dseg            ends

cseg            segment para public 'code'
assume  cs:cseg
ds:dseg

; A replacement critical error handler.  This routine calls prcsquit
; if the user decides to abort the program.


CritErrMsg      byte    cr
lf
byte    "DOS Critical Error!"
cr
lf
byte    "A)bort
R)etry
I)gnore
F)ail? $"

MyInt24         proc    far
push    dx
push    ds
push    ax

push    cs
pop     ds
Int24Lp:        lea     dx
CritErrMsg
mov     ah
9                   ;DOS print string call.
int     21h

mov     ah
1                   ;DOS read character call.
int     21h
and     al
5Fh                 ;Convert l.c. -> u.c.

cmp     al
'I'                 ;Ignore?
jne     NotIgnore
pop     ax
mov     al
0
jmp     Quit24

NotIgnore:      cmp     al
'r'                 ;Retry?
jne     NotRetry
pop     ax
mov     al
1
jmp     Quit24

NotRetry:       cmp     al
'A'                 ;Abort?
jne     NotAbort
prcsquit                        ;If quitting
fix INT 8.
pop     ax
mov     al
2
jmp     Quit24

NotAbort:       cmp     al
'F'
jne     BadChar
pop     ax
mov     al
3
Quit24:         pop     ds
pop     dx
iret

BadChar:        mov     ah
2
mov     dl
7                   ;Bell character
jmp     Int24Lp
MyInt24         endp



; We will simply disable INT 23h (the break exception).

MyInt23         proc    far
iret
MyInt23         endp



; This background processes call DOS to print several strings to the
; screen.  In the meantime
the foreground process is also printing
; strings to the screen.  To prevent reentry
or at least a jumble of
; characters on the screen
this code uses semaphores to protect the
; DOS calls.  Therefore
each process will print one complete line
; then release the semaphore.  If the other process is waiting it will
; print its line.

BackGround1     proc
mov     ax
dseg
mov     ds
ax

; Wait for everyone else to get ready:

lesi    BarrierSemaph
barrier 3

; Okay
start printing the strings:

lea     bx
StrPtrs2            ;Array of str ptrs.
PrintLoop:      cmp     word ptr [bx+2]
0      ;At end of pointers?
je      BkGndDone
les     di
[bx]                ;Get string to print.
DOSWait
puts                            ;Calls DOS to print string.
DOSRls
add     bx
4                   ;Point at next str ptr.
jmp     PrintLoop

BkGndDone:      die
BackGround1     endp


BackGround2     proc
mov     ax
dseg
mov     ds
ax

lesi    BarrierSemaph
barrier 3

lea     bx
StrPtrs3            ;Array of str ptrs.
PrintLoop:      cmp     word ptr [bx+2]
0      ;At end of pointers?
je      BkGndDone
les     di
[bx]                ;Get string to print.
DOSWait
puts                            ;Calls DOS to print string.
DOSRls
add     bx
4                   ;Point at next str ptr.
jmp     PrintLoop

BkGndDone:      die
BackGround2     endp



Main            proc
mov     ax
dseg
mov     ds
ax
mov     es
ax
meminit


; Initialize the INT 23h and INT 24h exception handler vectors.

mov     ax
0
mov     es
ax
mov     word ptr es:[24h*4]
offset MyInt24
mov     es:[24h*4 + 2]
cs
mov     word ptr es:[23h*4]
offset MyInt23
mov     es:[23h*4 + 2]
cs

prcsinit                ;Start multitasking system.

; Start the first background process:

lesi    BkgndPCB2       ;Fire up a new process
fork
test    ax
ax          ;Parent's return?
je      StartBG2
jmp     BackGround1     ;Go do backgroun stuff.

; Start the second background process:

StartBG2:       lesi    BkgndPCB3       ;Fire up a new process
fork
test    ax
ax          ;Parent's return?
je      ParentPrcs
jmp     BackGround2     ;Go do backgroun stuff.

; The parent process will print a bunch of strings at the same time
; the background process is doing this.  We'll use the DOS semaphore
; to protect the call to DOS that PUTS makes.

ParentPrcs:     lesi    BarrierSemaph
barrier 3

lea     bx
StrPtrs1            ;Array of str ptrs.
PrintLoop:      cmp     word ptr [bx+2]
0      ;At end of pointers?
je      ForeGndDone
les     di
[bx]                ;Get string to print.
DOSWait
puts                            ;Calls DOS to print string.
DOSRls
add     bx
4                   ;Point at next str ptr.
jmp     PrintLoop

ForeGndDone:    prcsquit

Quit:           ExitPgm                         ;DOS macro to quit program.
Main            endp

cseg            ends

sseg            segment para stack 'stack'

; Here are the stacks for the background processes we start

stk2            byte    1024 dup (?)
EndStk2         word    ?

stk3            byte    1024 dup (?)
EndStk3         word    ?

;Here's the stack for the main program/foreground process.

stk             byte    1024 dup (?)
sseg            ends

zzzzzzseg       segment para public 'zzzzzz'
LastBytes       db      16 dup (?)
zzzzzzseg       ends
end     Main

Sample Output:

Background 1: string 'a'
Background 1: string 'b'
Background 1: string 'c'
Background 1: string 'd'
Background 1: string 'e'
Background 1: string 'f'
Foreground: string 'a'
Background 1: string 'g'
Background 2: string 'j'
Foreground: string 'b'
Background 1: string 'h'
Background 2: string 'k'
Foreground: string 'c'
Background 1: string 'i'
Background 2: string 'l'
Foreground: string 'd'
Background 2: string 'm'
Foreground: string 'e'
Background 2: string 'n'
Foreground: string 'f'
Background 2: string 'o'
Foreground: string 'g'
Background 2: string 'p'
Foreground: string 'h'
Background 2: string 'q'
Foreground: string 'i'
Background 2: string 'r'
Foreground: string 'j'
Foreground: string 'k'
Foreground: string 'l'

Note how background process number one ran for one clock period before the other processes waited on the DOS semaphore. After this initial burst the processes all took turns calling DOS.

Chapter Nineteen (Part 13)

Table of Content

Chapter Nineteen (Part 15)  

Chapter Nineteen: Processes Coroutines and Concurrency (Part 14)
29 SEP 1996