BBC BASIC for Windows
« Multitasking - Creating Threads »

Welcome Guest. Please Login or Register.
Apr 5th, 2018, 10:29pm



ATTENTION MEMBERS: Conforums will be closing it doors and discontinuing its service on April 15, 2018.
Ad-Free has been deactivated. Outstanding Ad-Free credits will be reimbursed to respective payment methods.

If you require a dump of the post on your message board, please come to the support board and request it.


Thank you Conforums members.

BBC BASIC for Windows Resources
Online BBC BASIC for Windows documentation
BBC BASIC for Windows Beginners' Tutorial
BBC BASIC Home Page
BBC BASIC on Rosetta Code
BBC BASIC discussion group
BBC BASIC for Windows Programmers' Reference

« Previous Topic | Next Topic »
Pages: 1  Notify Send Topic Print
 thread  Author  Topic: Multitasking - Creating Threads  (Read 912 times)
Michael Hutton
Developer

member is offline

Avatar




PM

Gender: Male
Posts: 248
xx 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
« Last Edit: May 16th, 2009, 06:49am by Michael Hutton » User IP Logged

Michael Hutton
Developer

member is offline

Avatar




PM

Gender: Male
Posts: 248
xx 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
« Last Edit: May 17th, 2009, 12:19am by Michael Hutton » User IP Logged

David Williams
Developer

member is offline

Avatar

meh


PM

Gender: Male
Posts: 452
xx 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. wink
User IP Logged

admin
Administrator
ImageImageImageImageImage


member is offline

Avatar




PM


Posts: 1145
xx 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.
User IP Logged

Michael Hutton
Developer

member is offline

Avatar




PM

Gender: Male
Posts: 248
xx Re: Multitasking - Creating Threads
« Reply #4 on: May 17th, 2009, 12:17am »

damnit, yes. angry I did mean a word rather than dwords. I will change the original posts. Thanks for pointing that out.

Michael
User IP Logged

Michael Hutton
Developer

member is offline

Avatar




PM

Gender: Male
Posts: 248
xx 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
User IP Logged

admin
Administrator
ImageImageImageImageImage


member is offline

Avatar




PM


Posts: 1145
xx 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.
User IP Logged

admin
Administrator
ImageImageImageImageImage


member is offline

Avatar




PM


Posts: 1145
xx 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 
User IP Logged

Michael Hutton
Developer

member is offline

Avatar




PM

Gender: Male
Posts: 248
xx 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
User IP Logged

Michael Hutton
Developer

member is offline

Avatar




PM

Gender: Male
Posts: 248
xx 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


User IP Logged

admin
Administrator
ImageImageImageImageImage


member is offline

Avatar




PM


Posts: 1145
xx 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 » User IP Logged

Pages: 1  Notify Send Topic Print
« Previous Topic | Next Topic »

| |

This forum powered for FREE by Conforums ©
Terms of Service | Privacy Policy | Conforums Support | Parental Controls