[SOLVED] Python Threading Deadlock Issue

CincinnatiKid · 12-30-2016, 04:07 PM

Below is a program that I wrote that uses the Lucas Lehmer algorithm to figure out if a number is a mersenne prime (2^prime number-1). In my program it is trying to determine if 2^NUM_TO_CHECK-1 is a prime. Using the code below it only runs the "t_run" thread and not the "t_progress" thread until t_run has finished. Is my code not thread safe or something? Any incite would be greatly appreciated.

Code:

import gmpy2
import threading
import time

NUM_TO_CHECK = 86243

class Primes:
	def __init__(self, n):
		self.num = n
		self.i = gmpy2.mpz(1)
		self.testnum = gmpy2.mpz(4)
		self.answer = gmpy2.mpz(0)
		
		self.progress = {'running': 1, 'isprime': 0, 'i': 1}

	def lucaslehmer(self):
		while (self.i <= NUM_TO_CHECK-2):
			self.answer = gmpy2.f_mod(((self.testnum*self.testnum)-2), self.num)
			self.testnum = self.answer
			self.i += 1
		
		if (self.answer == 0):
			self.progress['isprime'] = 2
		else:
			self.progress['isprime'] = 1
		self.progress['running'] = 0

	def getprogress(self, cont, delay):
		if cont:
			while self.progress['running']:
				self.progress['i'] = self.i
				print(self.progress)
				time.sleep(delay)
		print(self.progress)

if __name__ == "__main__":
	primecandidate = gmpy2.mpz(pow(2, NUM_TO_CHECK)-1)
	wwprime = Primes(primecandidate)
	t_progress = threading.Thread(target=wwprime.getprogress, args=(1,1))
	t_progress.start()
	t_run = threading.Thread(target=wwprime.lucaslehmer)
	t_run.start()

CincinnatiKid · 12-30-2016, 04:20 PM

I found out if I put a delay/time.sleep in this loop, the threads work fine together. The problem is, I will be doing millions of calculations and can't sleep here or my calculations will never complete. Any way to make this work as intended?

Code:

while (self.i <= NUM_TO_CHECK-2):
			self.answer = gmpy2.f_mod(((self.testnum*self.testnum)-2), self.num)
			self.testnum = self.answer
			self.i += 1
			time.sleep(1) #IF I DO THIS, BOTH THREADS WORK FINE.

CincinnatiKid · 12-30-2016, 05:01 PM

I read all about locking, I think that is my issue. Below is using RLock in both of my threads. For small numbers that I am checking it appears that using the RLock works as desired. When I calculate big numbers, t_progress only runs once every 10 seconds at most, even though I only sleep 1 second between each loop. I have tried threading.Lock(), threading.RLock(), threading.Semaphore(), and so far RLock() seems the closest, it just still isn't giving the desired result though.

Code:

import gmpy2
import threading
import time

NUM_TO_CHECK = 86243

class Primes:
	def __init__(self, n):
		self.num = n
		self.i = gmpy2.mpz(1)
		self.testnum = gmpy2.mpz(4)
		self.answer = gmpy2.mpz(0)
		
		self.progress = {'running': 1, 'isprime': 0, 'i': 1}
		self.lock = threading.RLock()

	def lucaslehmer(self):
		while (self.i <= NUM_TO_CHECK-2):
			self.lock.acquire()
			self.answer = gmpy2.f_mod(((self.testnum*self.testnum)-2), self.num)
			self.testnum = self.answer
			self.i += 1
			self.lock.release()
		
		if (self.answer == 0):
			self.progress['isprime'] = 2
		else:
			self.progress['isprime'] = 1
		self.progress['running'] = 0

	def getprogress(self, cont, delay):
		if cont:
			while self.progress['running']:
				self.lock.acquire()
				self.progress['i'] = self.i
				print(self.progress)
				self.lock.release()
				time.sleep(delay)
		print(self.progress)

if __name__ == "__main__":
	primecandidate = gmpy2.mpz(pow(2, NUM_TO_CHECK)-1)
	wwprime = Primes(primecandidate)
	t_progress = threading.Thread(target=wwprime.getprogress, args=(1,1))
	t_progress.start()
	t_run = threading.Thread(target=wwprime.lucaslehmer)
	t_run.start()

ntubski · 12-30-2016, 11:18 PM

You should minimize the amount time spent holding the lock. In this case, the only shared resource are the variables self.progress and self.i, so only hold the lock while reading and writing them.

Currently your lucaslehmer thread is hold the lock almost all of the time, including while it's doing the main f_mod calculation, which is why your other thread has a hard time obtaining the lock.

CincinnatiKid · 12-31-2016, 10:55 AM

Quote:

Originally Posted by ntubski

You should minimize the amount time spent holding the lock. In this case, the only shared resource are the variables self.progress and self.i, so only hold the lock while reading and writing them.

Currently your lucaslehmer thread is hold the lock almost all of the time, including while it's doing the main f_mod calculation, which is why your other thread has a hard time obtaining the lock.

It is running a lot better locking when only using the shared resources. It is still a little glitchy as far as not necessarily running t_progress every second, but it is close enough that I am not worried about it. Thanks for your help!

sundialsvcs · 01-02-2017, 09:04 AM

In any language, every piece of code that is accessing a shared resource must "obtain a 'covering lock'" that will serialize access to that resource, before manipulating that resource. Then, it must release that lock as soon as possible thereafter.

Since the process of acquiring and releasing locks is expensive, even if no blocking occurs, you should be prudent in arranging your scheme so that the number of lock/unlock cycles is, within reason, minimized.

"Progress displays" are also very expensive. It is usually a good idea to maintain simple counters in the "worker" threads which can be periodically examined by a separate, timed thread which generates the progress displays. (And, generally, that thread can just retrieve the current counter-values without bothering with a lock on those values: any value obtained will be "close enough.")

Finally: threading will not speed up a CPU-bound activity, except to the extent that it might leverage "multiple cores" and then only if the implementation actually does so.