Author |
Topic: Multitasking - Creating Threads (Read 912 times) |
|
Michael Hutton
Developer
member is offline
Gender: 
Posts: 248
|
 |
Multitasking - Creating Threads
« Thread started on: May 16th, 2009, 06:46am » |
|
Here is a simple example of creating two different threads to increment their own pointer and then wait for them to both finish before exiting:
Code:
A% = 0
B% = 0
REM assemble two different routines to increment A% and B%
DIM code 50, L%-1
FOR pass=8 TO 10 STEP 2
P% = code
[
OPT pass
.ThreadProc1
inc dword [^A%]
cmp dword [^A%],100000000
jne ThreadProc1
ret
.ThreadProc2
inc dword [^B%]
cmp dword [^B%],100000000
jne ThreadProc2
ret
]
NEXT
DIM hThread%(1)
SYS "CreateThread", 0, 1024, ThreadProc1, 0, 0, 0 TO hThread%(0)
SYS "CreateThread", 0, 1024, ThreadProc2, 0, 0, 0 TO hThread%(1)
SYS "WaitForMultipleObjects", 2, ^hThread%(0), 1, -1 TO R%
FOR I%=0 TO 1
SYS "CloseHandle", hThread%(I%)
NEXT
PRINT A%,B%
END
Next is to start them in a suspended state, assign them to different processors, start them and then wait for each to complete.
I haven't quite worked out what the return value from the ThreadProc should be, if anything.
Michael
|
|
|
|
Michael Hutton
Developer
member is offline
Gender:
Posts: 248
|
|
Re: Multitasking - Creating Threads
« Reply #1 on: May 16th, 2009, 08:00am » |
|
here we go:
Code:
REM!WC
MAXIMUM_PROCESSORS = 32
CREATE_SUSPENDED = &4
INFINITE = &FFFFFFFF
_TRUE = 1
A% = 0
B% = 0
:\
\\ assemble two different (pointless) routines to increment A% and B%
\
DIM code 50, L%-1
FOR pass=8 TO 10 STEP 2
P% = code
[
OPT pass
.ThreadProc1
inc dword [^A%]
cmp dword [^A%],100000000
jne ThreadProc1
ret
.ThreadProc2
inc dword [^B%]
cmp dword [^B%],100000000
jne ThreadProc2
ret
]
NEXT
:\
\\ Declare SYSTEM_INFO structure
\
DIM _SYSTEM_INFO{ wProcessorArchitecture%, \ Only lower word if valid: high word is wReserved - was dwOemID
\ dwPageSize%, \
\ lpMinimumApplicationAddress%, \
\ lpMaximumApplicationAddress%, \
\ dwActiveProcessorMask%, \
\ dwNumberOfProcessors%, \
\ dwProcessorType%, \
\ dwAllocationGranulatiry%, \
\ wProcessorLevel{l&,h&}, \
\ wProcessorRevision{l&,h&} }
SYS "GetSystemInfo", _SYSTEM_INFO{}
PRINT "Number of processors available: ";_SYSTEM_INFO.dwNumberOfProcessors%
:\
\\ Create the threads and store their handles in an array
\
DIM hThread%(1)
:\
\\ ON ERROR and ON CLOSE to cleanup thread handles
\
ON ERROR PROCCleanup:REPORT:END
ON CLOSE PROCCleanup:QUIT
:\
\\ Create the threads in a suspended state
\
SYS "CreateThread", 0, 1024, ThreadProc1, 0, CREATE_SUSPENDED, 0 TO hThread%(0)
IF hThread%(0) = 0 THEN ERROR,"Failed to create Thread 1."
SYS "CreateThread", 0, 1024, ThreadProc2, 0, CREATE_SUSPENDED, 0 TO hThread%(1)
IF hThread%(1) = 0 THEN ERROR,"Failed to create Thread 2."
:\
\\ Get the current ideal processor for each thread
\
SYS "SetThreadIdealProcessor", hThread%(0), MAXIMUM_PROCESSORS TO current0%
PRINT "Thread 1 is currently on : ";current0%
SYS "SetThreadIdealProcessor", hThread%(1), MAXIMUM_PROCESSORS TO current1%
PRINT "Thread 2 is currently on : ";current1%
IF current0% = current1% AND _SYSTEM_INFO.dwNumberOfProcessors%>1 THEN
SYS "SetThreadIdealProcessor", hThread%(1), 1 TO R%
IF R%=-1 THEN PRINT"Couldn't change the processor for the 2nd thread."
ENDIF
:\
\\ Wait a bit, check out Task Manager maybe...
\
PRINT "Waiting....."
WAIT 500
PRINT "Starting threads."
PRINT A%,B%
:\
\\ |||Fry||| those processors
\
SYS "ResumeThread", hThread%(0)
SYS "ResumeThread", hThread%(1)
:\
\\ Wait until both threads have stopped and then exit
\
SYS "WaitForMultipleObjects", 2, ^hThread%(0), _TRUE, INFINITE TO R%
PRINT A%,B%
PROCCleanup
END
:\
\\ Close the thread objects
\
DEFPROCCleanup
FOR I%=0 TO 1
IF hThread%(I%) THEN SYS "CloseHandle", hThread%(I%) : hThread%(I%) = 0
NEXT
ENDPROC
Michael
|
|
|
|
David Williams
Developer
member is offline
meh
Gender:
Posts: 452
|
|
Re: Multitasking - Creating Threads
« Reply #2 on: May 16th, 2009, 11:02am » |
|
Wow! This is interesting stuff.
Massive implications for graphics routines, and much besides.
Keep up the fine work. 
|
|
 Logged
|
|
|
|
admin
Administrator
member is offline
Posts: 1145
|
|
Re: Multitasking - Creating Threads
« Reply #3 on: May 16th, 2009, 9:51pm » |
|
Code:\ wProcessorLevel{l%,h%}, \
\ wProcessorRevision{l%,h%} }
That doesn't look right. A 'w' prefix usually indicates a WORD (16-bit) quantity, but you've got a QWORD (64 bits). Are you sure you didn't mean:
Code:\ wProcessorLevel{l&,h&}, \
\ wProcessorRevision{l&,h&} }
Richard.
|
|
Logged
|
|
|
|
Michael Hutton
Developer
member is offline
Gender:
Posts: 248
|
|
Re: Multitasking - Creating Threads
« Reply #4 on: May 17th, 2009, 12:17am » |
|
damnit, yes.  I did mean a word rather than dwords. I will change the original posts. Thanks for pointing that out.
Michael
|
|
Logged
|
|
|
|
Michael Hutton
Developer
member is offline
Gender:
Posts: 248
|
|
Re: Multitasking - Creating Threads
« Reply #5 on: Aug 10th, 2009, 4:11pm » |
|
Find the greedy philosopher!
Code:
philo1% = 0
philo2% = 0
philo3% = 0
philo4% = 0
philo5% = 0
fork1% = 0
fork2% = 0
fork3% = 0
fork4% = 0
fork5% = 0
finished% = 0
DIM code 1000, L%-1
FOR pass=8 TO 10 STEP 2
P% = code
[
OPT pass
.philo1
;REM go to sleep for a random time
push 10
call "Sleep"
;REM test forks
mov eax,[^fork1%]
mov ebx,[^fork2%]
or eax,ebx
jnz philo1
;REM see if simulation has finished
cmp dword [^finished%],1
jz exit1
;REM forks are free - eat!
;REM set forks in use
mov dword [^fork1%],1
mov dword [^fork2%],1
add dword [^philo1%],1
push 5
call "Sleep"
mov dword [^fork1%],0
mov dword [^fork2%],0
jmp philo1
.exit1
ret
.philo2
push 10
call "Sleep"
;test forks
mov eax,[^fork2%]
mov ebx,[^fork3%]
or eax,ebx
jnz philo2
;REM see if simulation has finished
cmp dword [^finished%],1
jz exit2
;REM forks are free - eat!
;REM set forks in use
mov dword [^fork2%],1
mov dword [^fork3%],1
;REM eat for a while
add dword [^philo2%],1
push 5
call "Sleep"
;REM put down forks
mov dword [^fork2%],0
mov dword [^fork3%],0
jmp philo2
.exit2
ret
.philo3
push 10
call "Sleep"
;test forks
mov eax,[^fork3%]
mov ebx,[^fork4%]
or eax,ebx
jnz philo3
;REM see if simulation has finished
cmp dword [^finished%],1
jz exit3
;REM forks are free - eat!
;REM set forks in use
mov dword [^fork3%],1
mov dword [^fork4%],1
;REM eat for a while
add dword [^philo3%],1
push 5
call "Sleep"
;REM put down forks
mov dword [^fork3%],0
mov dword [^fork4%],0
jmp philo3
.exit3
ret
.philo4
push 10
call "Sleep"
;test forks
mov eax,[^fork4%]
mov ebx,[^fork5%]
or eax,ebx
jnz philo4
;REM see if simulation has finished
cmp dword [^finished%],1
jz exit4
;REM forks are free - eat!
;REM set forks in use
mov dword [^fork4%],1
mov dword [^fork5%],1
;REM eat for a while
add dword [^philo4%],1
push 5
call "Sleep"
;REM put down forks
mov dword [^fork4%],0
mov dword [^fork5%],0
jmp philo4
.exit4
ret
.philo5
push 10
call "Sleep"
;test forks
mov eax,[^fork5%]
mov ebx,[^fork1%]
or eax,ebx
jnz philo5
;REM see if simulation has finished
cmp dword [^finished%],1
jz exit5
;REM forks are free - eat!
;REM set forks in use
mov dword [^fork5%],1
mov dword [^fork1%],1
;REM eat for a while
add dword [^philo5%],1
push 5
call "Sleep"
;REM put down forks
mov dword [^fork5%],0
mov dword [^fork1%],0
jmp philo5
.exit5
ret
]
NEXT
param% = 0
DIM hThread%(4)
SYS "CreateThread", 0, 1024, philo1, param%, 0, 0 TO hThread%(0)
IF hThread%(0) = 0 THEN ERROR 100,"Failed to create Thread."
SYS "CreateThread", 0, 1024, philo2, param%, 0, 0 TO hThread%(1)
IF hThread%(1) = 0 THEN ERROR 100,"Failed to create Thread."
SYS "CreateThread", 0, 1024, philo3, param%, 0, 0 TO hThread%(2)
IF hThread%(1) = 0 THEN ERROR 100,"Failed to create Thread."
SYS "CreateThread", 0, 1024, philo4, param%, 0, 0 TO hThread%(3)
IF hThread%(1) = 0 THEN ERROR 100,"Failed to create Thread."
SYS "CreateThread", 0, 1024, philo5, param%, 0, 0 TO hThread%(4)
IF hThread%(1) = 0 THEN ERROR 100,"Failed to create Thread."
SYS "Sleep", 10000
finished%=1
SYS "WaitForMultipleObjects", 5, ^hThread%(0), 1, -1 TO R%
FOR I%=0 TO 4
SYS "CloseHandle", hThread%(I%)
NEXT
PRINT philo1%,philo2%,philo3%,philo4%,philo5%
I'm sure you could just code one routine for every philosopher but I don't know what the implications are for the threads working on the same code segment would be. You could pass the number of the philosopher in the parameter of the 'CreateThread'....
I know it's a bit simple but I'll see what I can do to improve it... (add random sleep times, for instance)
Michael
|
|
Logged
|
|
|
|
admin
Administrator
member is offline
Posts: 1145
|
|
Re: Multitasking - Creating Threads
« Reply #6 on: Aug 10th, 2009, 10:04pm » |
|
Unfortunately your code is seriously flawed, because it is not written to be 'thread safe' (which is vitally important in this case!). For example here:
Code: mov eax,[^fork1%]
mov ebx,[^fork2%]
or eax,ebx
jnz philo1
;REM forks are free - eat!
Think what happens if a 'task switch' takes place immediately after this code. Philosopher 1 has just determined that forks 1 and 2 are 'free', but the philosopher whose thread is scheduled next will also see forks 1 and 2 as free despite the fact that philosopher 1 has assumed he can use them.
It is essential that the testing of the forks being free and the taking of the forks happens as a non-interruptible (atomic) operation. Only that way can you ensure that a fork isn't being used by two philosophers at the same time.
It is with very good reason that multi-threaded code is considered probably the hardest code of all to write. It would be an interesting - and difficult - challenge to write multi-threaded code to solve this problem, but yours isn't it! It would almost certainly be easier, and much safer, to use a single thread in this case.
Richard.
|
|
Logged
|
|
|
|
admin
Administrator
member is offline
Posts: 1145
|
|
Re: Multitasking - Creating Threads
« Reply #7 on: Aug 11th, 2009, 08:50am » |
|
I think the code below does it properly, i.e. it tests whether a fork is available and if so takes it, in an 'atomic' operation (if the second fork then turns out not to be available, it gives the first fork back). Since this means the two forks are not treated symmetrically it may bias the results slightly. The code relies on cmpxchg for the atomic operations, so there's no chance of it working on an 80386!
The code also uses a common routine shared between all the philosophers (that's much more elegant than having five almost, but not quite, identical routines).
Richard.
Code: DIM fork%(5) : REM Five forks
DIM philo{(5) pfork1%, pfork2%, count%} : REM Five philosophers
REM Allocate forks to philosophers:
f% = 0
FOR p% = 1 TO 5
philo{(p%)}.pfork1% = ^fork%((f% MOD 5)+1)
f% += 1
philo{(p%)}.pfork2% = ^fork%((f% MOD 5)+1)
NEXT p%
REM Global finished flag:
Finished% = 0
DIM code 100, L%-1
FOR pass=8 TO 10 STEP 2
P% = code
[
OPT pass
.philo
mov ebp,[esp+4]
mov esi,[ebp]
mov edi,[ebp+4]
.philoop
;REM see if simulation has finished
cmp dword [^Finished%],0
jnz exit
;REM go to sleep for a 'random' time
push 10
call "Sleep"
;REM test and take forks ATOMICALLY
xor eax,eax
mov ebx,1
cmpxchg [esi],ebx
jnz philoop
cmpxchg [edi],ebx
jz gotforks
;REM return first fork
dec dword [esi]
jmps philoop
.gotforks
;REM we have the forks - eat!
add dword [ebp+8],1
push 5
call "Sleep"
;REM return the forks
dec dword [esi]
dec dword [edi]
jmps philoop
;REM simulation has finished
.exit
ret 4
]
NEXT
ON ERROR Finished% = 1 : PRINT REPORT$ : END
ON CLOSE Finished% = 1 : QUIT
DIM hThread%(5)
FOR p% = 1 TO 5
SYS "CreateThread", 0, 1024, philo, philo{(p%)}, 0, 0 TO hThread%(p%)
IF hThread%(p%) = 0 THEN ERROR 100,"Failed to create Thread."
NEXT
WAIT 1000
Finished% = 1
SYS "WaitForMultipleObjects", 5, ^hThread%(1), 1, -1
FOR p% = 1 TO 5
SYS "CloseHandle", hThread%(p%)
PRINT philo{(p%)}.count% ;
NEXT
PRINT |
|
Logged
|
|
|
|
Michael Hutton
Developer
member is offline
Gender:
Posts: 248
|
|
Re: Multitasking - Creating Threads
« Reply #8 on: Aug 11th, 2009, 09:09am » |
|
Brilliant!
I am just sitting here reading the Intel documentation on 'cmpxchg' think that that would be the way but, obviously, had not got so far! I am just experimenting with two philosophers, one grabbing them immediately and the other trying to get them......
I like the one procedure. I had originally unrolled mine because of my ignorance about threads working on the same code but checking the documentation that seems OK to do...
Fantastic stuff. I will read and digest. I am sure I will have questions!
Michael
|
|
Logged
|
|
|
|
Michael Hutton
Developer
member is offline
Gender:
Posts: 248
|
|
Re: Multitasking - Creating Threads
« Reply #9 on: Aug 11th, 2009, 10:51am » |
|
Is it possible, although very unlikely, that as the code stands this could end up in 'live lock'? (I've just read the wiki article. (http://en.wikipedia.org/wiki/Dining_philosophers_problem)
The only way I can see that happening is if all the threads manage to pick up the fork to their left at the same time, they then check for the right fork to find it being used. Put down the left fork. They ALL sleep for the same time (which is the problem.) Then wake and do the same thing again.. and everyone ends up starving. I know this is highly unlikely to happen.
Michael
|
|
Logged
|
|
|
|
admin
Administrator
member is offline
Posts: 1145
|
|
Re: Multitasking - Creating Threads
« Reply #10 on: Aug 11th, 2009, 9:59pm » |
|
Quote:| Is it possible, although very unlikely, that as the code stands this could end up in 'live lock'? |
|
The Wikipedia article states that deadlock can be prevented by assigning a 'hierarchy' to the forks, such that each philosopher always picks up the lower-numbered fork first and puts it down last. The program can very easily be modified to achieve that (below).
Richard.
Code: DIM fork%(5) : REM Five forks
DIM philo{(5) pfork1%, pfork2%, count%} : REM Five philosophers
REM Allocate forks to philosophers:
f% = 0
FOR p% = 1 TO 5
philo{(p%)}.pfork1% = ^fork%((f% MOD 5)+1)
f% += 1
philo{(p%)}.pfork2% = ^fork%((f% MOD 5)+1)
NEXT p%
REM Ensure each philosopher picks up the lower-numbered fork first:
SWAP philo{(5)}.pfork1%, philo{(5)}.pfork2%
REM Global finished flag:
Finished% = 0
DIM code 100, L%-1
FOR pass=8 TO 10 STEP 2
P% = code
[
OPT pass
.philo
mov ebp,[esp+4]
mov esi,[ebp]
mov edi,[ebp+4]
.philoop
;REM see if simulation has finished
cmp dword [^Finished%],0
jnz exit
;REM go to sleep for a 'random' time
push 10
call "Sleep"
;REM test and take forks ATOMICALLY
xor eax,eax
mov ebx,1
cmpxchg [esi],ebx
jnz philoop
cmpxchg [edi],ebx
jz gotforks
;REM return first fork
dec dword [esi]
jmps philoop
.gotforks
;REM we have the forks - eat!
add dword [ebp+8],1
push 5
call "Sleep"
;REM return the forks (in reverse order)
dec dword [edi]
dec dword [esi]
jmps philoop
;REM simulation has finished
.exit
ret 4
]
NEXT
ON ERROR Finished% = 1 : PRINT REPORT$ : END
ON CLOSE Finished% = 1 : QUIT
DIM hThread%(5)
FOR p% = 1 TO 5
SYS "CreateThread", 0, 1024, philo, philo{(p%)}, 0, 0 TO hThread%(p%)
IF hThread%(p%) = 0 THEN ERROR 100,"Failed to create Thread."
NEXT
WAIT 1000
Finished% = 1
SYS "WaitForMultipleObjects", 5, ^hThread%(1), 1, -1
FOR p% = 1 TO 5
SYS "CloseHandle", hThread%(p%)
PRINT philo{(p%)}.count% ;
NEXT
PRINT |
| « Last Edit: Aug 11th, 2009, 10:01pm by admin » |
Logged
|
|
|
|
|
