The code being posted (again with no comments or promise of correctness, sorry!), contains examples of problems associated with programming, mostly threading related, as you can see below. A basic description of each one:
- search.py – A simple implementation of a Basic Regular Expression (a Deterministic Finite State Machine) which should match a pattern and string
- webbot.py – A simple HTTP GET script which uses various authentication methods: Basic, Digest, Cookies, and SSL
- deadlock.py – A thread based example of the “deadlock” problem where 2 threads attempt to perform 2 related actions in reverse order of each other and obtain the locks in a staggered fashion such that they both are now waiting for each other to finish first before proceeding.
- Example: Thread1 wants to transfer money from Bob to Charlie & Thread2 wants to transfer money from Charlie to Bob. Thread1 first gets a lock on Bob’s account & Thread2 at the same time gets a lock on Charlie’s account. Now Thread1 is waiting to get a lock on Charlie’s account & Thread2 is waiting to get a lock on Bob’s account but they both can’t until one of them releases a lock.
- livelock.py – A thread based example of the “livelock” problem where 2 threads attempt to perform the same reversed action as above but instead attempt to release their own locks at the same time and then wait for the other to grab their lock for the same amount of time and then re-lock at the same time again causing an infinite loop to occur again.
- semaphore.py – The lock scenarios above are examples of binary “semaphores” so this is a thread based example of a counting “semaphore”. The implementation is an example where a library has 10 rooms to offer students, however, the front desk only keeps a count of the number of rooms free when a person enters or leaves a room. If no rooms are available, the thread is blocked and added to a simple First In First Out queue waiting for the room count to become positive again.
- monitor.py – This script is also based on the bank money transfer analogy as above except that it uses a real thread locking mechanism for both withdrawal and deposit actions to prevent both threads from performing different actions at the same time.
- mutex.py – This script demonstrates both an example of a problem and a “monitor” locking solution for when 2 threads attempt to remove adjacent items (i & i+1) in a Linked-List at the same time. Basically, Thread1 removing i will point i-1 at i+1 when Thread2 is trying to remove i+1 at the same time therefore allowing it to still exist afterwards.
search.py
#!/usr/bin/python
import os
import sys
def search(pattern, instr):
allchars = []
for x in range(0, 256):
allchars.append(chr(x))
# compile: [notflag, charset, numtimes, indexlist]
# numtimes: {0:"0", 1:"1", ..., -1:"0 or 1", -2:"0 or more"}
clist = []; clen = 0
try:
pidx = 0; plen = len(pattern)
while (pidx < plen):
pchar = pattern[pidx]
if (pchar == "."):
clist.append([0, allchars, 1, []]); clen += 1
elif (pchar == "?"):
clist[clen - 1][2] = -1
elif (pchar == "*"):
clist[clen - 1][2] = -2
elif (pchar == "["):
notflag = -1; charlist = []
while (pidx < plen):
pidx += 1; pchar = pattern[pidx]
if ((notflag == -1) and (pchar == "^")):
notflag = 1
elif (pchar == "]"):
break
elif (pchar == "-"):
for a in range(ord(pattern[pidx - 1]) + 1, ord(pattern[pidx + 1])):
charlist.append(chr(a))
else:
charlist.append(pchar)
if (notflag == -1):
notflag = 0
clist.append([notflag, charlist, 1, []]); clen += 1
else:
clist.append([0, [pchar], 1, []]); clen += 1
pidx += 1
except:
return False
#print(instr, pattern, clist)
# search
cidx = 0
iidx = 0; ilen = len(instr)
while ((cidx < clen) and (iidx < ilen)):
#print(cidx,clist[cidx],iidx,instr[iidx])
inchr = instr[iidx]
match = (inchr in clist[cidx][1])
if (clist[cidx][0] == 1):
match = (not match)
# match processing
if (match):
# if we matched
# store this related input index and check the next input character (greedy)
clist[cidx][3].append(iidx); iidx += 1
if ((clist[cidx][2] == 1) or (clist[cidx][2] == -1)):
# if this regex match count is ("1" OR "0 or 1") then try the next regex item for matches
cidx += 1
else:
# if we did not match
if ((clist[cidx][2] == -1) or (clist[cidx][2] == -2)):
# if the regex match count is ("0 or 1" OR "0 or more") then try the next regex item for matches
cidx += 1
elif (len(clist[cidx][3]) > 0):
# if this regex already has some matched input then try the next regex item for matches
cidx += 1
else:
# last resort check to see if we can roll back to a past (greedy) regex match
while (1):
tidx = max(cidx - 1, 0)
if (len(clist[tidx][3]) > 0):
# if we found a past (greedy) regex match then use that past input index for this regex and check from there
iidx = clist[tidx][3].pop()
break
cidx = tidx
if (cidx < 1):
# if we have gone back to the first regex then move the input index forward (search)
iidx += 1
break
if (cidx >= clen):
return True
return False
def main():
for line in sys.stdin.readlines():
line = line.rstrip()
if (search(sys.argv[1], line)):
print(line)
if (__name__ == "__main__"):
main()
webbot.py
#!/usr/bin/python
import base64
import hashlib
import os
import random
import ssl
import socket
import sys
import time
def parse_headers(httpresp):
httphead = {}
for httpline in httpresp.split("\n"):
httpline = httpline.strip()
if (not httpline):
break
headlist = httpline.split(":", 1)
if (len(headlist) != 2):
continue
httphead[headlist[0].lower()] = headlist[1].strip()
if ("www-authenticate" in httphead.keys()):
httpauth = {}
authlist = httphead["www-authenticate"].split(" ", 1)
httpauth["type"] = authlist[0]
flag = 0; keyn = ""; temp = ""
for achr in authlist[1]:
if (achr == '='):
keyn = temp; temp = ""
flag = 1
elif ((achr == "'") or (achr == '"')):
if (flag == 1):
temp = ""
if (flag == 2):
httpauth[keyn] = temp; temp = ""
flag += 1
elif (achr == ','):
if (temp != ""):
httpauth[keyn] = temp; temp = ""
flag = 3
elif ((flag != 2) and (achr == ' ')):
pass
else:
temp += achr
if (temp != ""):
httpauth[keyn] = temp; temp = ""
httphead["www-auth"] = httpauth
return httphead
def main():
print("[Basic Auth]");print("")
hostname = "httpbin.org"
filename = "/basic-auth/baseuser/basepass"
authhead = ("Authorization: Basic %s\r\n" % (base64.b64encode("baseuser:basepass")))
cookie = ""
sockobjc = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
sockobjc.connect((hostname, 80))
sockobjc.sendall("GET %s HTTP/1.1\r\nHost: %s\r\n%s%s\r\n" % (filename, hostname, authhead, cookie))
sockresp = sockobjc.recv(1024)
headlist = parse_headers(sockresp)
print(sockresp);print("");print(headlist)
print("");print("")
print("[Digest Auth]");print("")
username = ("dig%duser%d" % (random.randint(1000, 9999), random.randint(1000, 9999)))
password = ("dig%dpass%d" % (random.randint(1000, 9999), random.randint(1000, 9999)))
hostname = "httpbin.org"
filename = ("/digest-auth/auth/%s/%s" % (username, password))
authhead = ""
cookie = ""
sockobjc = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
sockobjc.connect((hostname, 80))
sockobjc.sendall("GET %s HTTP/1.1\r\nHost: %s\r\n%s%s\r\n" % (filename, hostname, authhead, cookie))
sockresp = sockobjc.recv(1024)
headlist = parse_headers(sockresp)
nc = "00000001"; cn = "13377331"
hao = hashlib.md5(username + ":" + headlist["www-auth"]["realm"] + ":" + password).hexdigest()
hat = hashlib.md5("GET" + ":" + filename).hexdigest()
har = hashlib.md5(hao + ":" + headlist["www-auth"]["nonce"] + ":" + nc + ":" + cn + ":" + "auth" + ":" + hat).hexdigest()
authhead = ("Authorization: Digest username=\"%s\", realm=\"%s\", nonce=\"%s\", uri=\"%s\", qop=auth, nc=%s, cnonce=\"%s\", response=\"%s\", opaque=\"%s\"\r\n" % (username, headlist["www-auth"]["realm"], headlist["www-auth"]["nonce"], filename, nc, cn, har, headlist["www-auth"]["opaque"]))
cookie = ("Cookie: %s\r\n" % (headlist["set-cookie"]))
sockobjc = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
sockobjc.connect((hostname, 80))
sockobjc.sendall("GET %s HTTP/1.1\r\nHost: %s\r\n%s%s\r\n" % (filename, hostname, authhead, cookie))
sockresp = sockobjc.recv(1024)
headlist = parse_headers(sockresp)
print(sockresp);print("");print(headlist)
print("");print("")
print("[Cookie Auth]");print("")
hostname = "www.httpwatch.com"
filename = "/httpgallery/authentication/authenticatedimage/default.aspx"
authhead = ("Authorization: Basic %s\r\n" % (base64.b64encode("httpwatch:abcd")))
cookie = ""
sockobjc = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
sockobjc.connect((hostname, 80))
sockobjc.sendall("GET %s HTTP/1.1\r\nHost: %s\r\n%s%s\r\n" % (filename, hostname, authhead, cookie))
sockresp = sockobjc.recv(1024)
headlist = parse_headers(sockresp)
authhead = ("Authorization: Basic %s\r\n" % (base64.b64encode("httpwatch:efgh")))
cookie = ("Cookie: %s\r\n" % (headlist["set-cookie"]))
sockobjc = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
sockobjc.connect((hostname, 80))
sockobjc.sendall("GET %s HTTP/1.1\r\nHost: %s\r\n%s%s\r\n" % (filename, hostname, authhead, cookie))
sockresp = sockobjc.recv(1024)
headlist = parse_headers(sockresp)
print(sockresp);print("");print(headlist)
print("");print("")
print("[SSL Auth]");print("")
hostname = "www.google.ca"
filename = "/images/srpr/logo11w.png"
authhead = ""
cookie = ""
sockobjc = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
sslsocko = ssl.wrap_socket(sockobjc)
sslsocko.connect((hostname, 443))
sslsocko.sendall("GET %s HTTP/1.1\r\nHost: %s\r\n%s%s\r\n" % (filename, hostname, authhead, cookie))
sockresp = sslsocko.recv(1024)
headlist = parse_headers(sockresp)
print(sockresp);print("");print(headlist)
if (__name__ == "__main__"):
main()
deadlock.py
#!/usr/bin/python
import os
import sys
import threading
import time
class Account:
def __init__(self, amount):
self.lock = 0
self.exit = 0
self.balance = amount
def withdraw(self, amount):
self.balance -= amount
def deposit(self, amount):
self.balance += amount
def sync(self):
while (self.lock == 1):
if (self.exit == 1):
print("deadlock exit triggered")
sys.exit(0)
time.sleep(0.5)
self.lock = 1
print("got lock on",self)
def release(self):
self.lock = 0
def transfer(self, Accto, amount):
self.sync()
Accto.sync()
self.withdraw(amount)
Accto.deposit(amount)
Accto.release()
self.release()
def show(self):
return str(self.balance)
class myThread(threading.Thread):
def __init__(self, threadID, name, data):
threading.Thread.__init__(self)
self.threadID = threadID
self.name = name
self.data = data
def run(self):
if (self.threadID == 1):
src = "bob"; to = "charlie"
if (self.threadID == 2):
src = "charlie"; to = "bob"
print("Before: "+self.name+" from "+src+": "+bank[src].show()+" to "+to+": "+bank[to].show())
print("Transfer: "+self.name+" from "+src+" to "+to); bank[src].transfer(bank[to], 5)
print("After: "+self.name+" from "+src+": "+bank[src].show()+" to "+to+": "+bank[to].show())
bank = {"bob":Account(100), "charlie":Account(200)}
thread1 = myThread(1, "Thread-1", bank)
thread2 = myThread(2, "Thread-2", bank)
thread1.start()
thread2.start()
time.sleep(3)
bank["bob"].exit = 1
bank["charlie"].exit = 1
livelock.py
#!/usr/bin/python
import os
import sys
import threading
import time
class Account:
def __init__(self, amount):
self.lock = 0
self.exit = 0
self.balance = amount
def withdraw(self, amount):
self.balance -= amount
def deposit(self, amount):
self.balance += amount
def setlocks(self, linked):
self.lock = 1
waittime = 0.01
print("setlocks started")
while (1):
if (linked.lock != 1):
break
if (self.exit == 1):
print("livelock exit triggered")
sys.exit(0)
time.sleep(waittime)
self.lock = 0
time.sleep(waittime)
self.lock = 1
time.sleep(waittime)
linked.lock = 1
def dellocks(self, linked):
linked.lock = 0
self.lock = 0
def transfer(self, Accto, amount):
self.setlocks(Accto)
self.withdraw(amount)
Accto.deposit(amount)
self.dellocks(Accto)
def show(self):
return str(self.balance)
class myThread(threading.Thread):
def __init__(self, threadID, name, data):
threading.Thread.__init__(self)
self.threadID = threadID
self.name = name
self.data = data
def run(self):
if (self.threadID == 1):
src = "bob"; to = "charlie"
if (self.threadID == 2):
src = "charlie"; to = "bob"
print("Before: "+self.name+" from "+src+": "+bank[src].show()+" to "+to+": "+bank[to].show())
print("Transfer: "+self.name+" from "+src+" to "+to); bank[src].transfer(bank[to], 5)
print("After: "+self.name+" from "+src+": "+bank[src].show()+" to "+to+": "+bank[to].show())
bank = {"bob":Account(100), "charlie":Account(200)}
thread1 = myThread(1, "Thread-1", bank)
thread2 = myThread(2, "Thread-2", bank)
thread1.start()
thread2.start()
time.sleep(3)
bank["bob"].exit = 1
bank["charlie"].exit = 1
semaphore.py
#!/usr/bin/python
import os
import random
import sys
import threading
import time
class Library:
def __init__(self):
self.rooms = ([None]*10)
self.numb = 10
self.queue = []
def wait(self, caller):
self.queue.append(caller)
while ((self.numb < 1) or (self.queue[0] != caller)):
time.sleep(0.1)
self.numb -= 1
for x in range(0, 10):
if (self.rooms[x] == None):
self.rooms[x] = caller
self.queue.pop(0)
return x
sys.stderr.write("ERROR: wait() - Could not find a room!\n")
sys.exit(1)
return -1
def signal(self, caller):
for x in range(0, 10):
if (self.rooms[x] == caller):
self.rooms[x] = None
self.numb += 1
return x
sys.stderr.write("ERROR: signal() - Could not find our room!\n")
sys.exit(1)
return -1
def show(self):
return self.numb
def disp(self):
o = ""
o += ("rooms / time:%d\n" % (int(time.time())))
for x in range(0, 10):
if (self.rooms[x] == None):
o += ("room[%d]=None\n" % (x))
else:
o += ("room[%d]=%s/%d\n" % (x, self.rooms[x].name, self.rooms[x].init + self.rooms[x].secs))
o += ("\n")
o += ("num[%d] / queue[%d] = " % (self.numb, len(self.queue)))
for item in self.queue:
o += ("%s, " % (item.name))
o += ("\n")
sys.stdout.write(("\n"*50) + o.strip() + "\n\n")
class myThread(threading.Thread):
def __init__(self, threadID, name, data):
threading.Thread.__init__(self)
self.threadID = threadID
self.name = name
self.library = data
def run(self):
self.init = int(time.time())
self.secs = random.randint(1, 9)
room = self.library.wait(self)
time.sleep(self.secs)
left = self.library.signal(self)
sys.exit(0)
x = 0
study = Library()
while (1):
thread = myThread(x, "Thread-%d" % (x), study)
thread.start()
secs = 0.5
study.disp()
time.sleep(secs)
x += 1
monitor.py
#!/usr/bin/python
import os
import sys
import threading
import time
class Account:
def __init__(self, amount, iden):
self.balance = amount
self.name = iden
def withdraw(self, amount):
threadLock.acquire()
print(time.ctime(time.time())+" withdraw "+" from "+self.name+" : "+str(self.balance)+" - "+str(amount)+" = "+str(self.balance-amount))
if (self.balance >= amount):
self.balance -= amount
threadLock.release()
def deposit(self, amount):
threadLock.acquire()
print(time.ctime(time.time())+" deposit "+" to "+self.name+" : "+str(self.balance)+" + "+str(amount)+" = "+str(self.balance+amount))
if (amount > 0):
self.balance += amount
threadLock.release()
def show(self):
return str(self.balance)
class myThread(threading.Thread):
def __init__(self, threadID, name, data):
threading.Thread.__init__(self)
self.threadID = threadID
self.name = name
self.data = data
def run(self):
#threadLock.acquire()
if (self.threadID == 1):
src = "bob"; to = "charlie"
if (self.threadID == 2):
src = "charlie"; to = "bob"
for x in range(0, 3):
bank[src].withdraw(5 * self.threadID)
bank[to].deposit(5 * self.threadID)
time.sleep(self.threadID)
#threadLock.release()
threadLock = threading.Lock()
threads = []
bank = {"bob":Account(100, "bob"), "charlie":Account(200, "charlie")}
thread1 = myThread(1, "Thread-1", bank)
thread2 = myThread(2, "Thread-2", bank)
thread1.start()
thread2.start()
threads.append(thread1)
threads.append(thread2)
for t in threads:
t.join()
mutex.py
#!/usr/bin/python
import os
import sys
import threading
import time
class LinkedList:
def __init__(self, data):
self.data = data
self.next = None
def getnext(self):
return self.next
def setnext(self, next):
self.next = next
def getdata(self):
return self.data
def add(self, data):
temp = self
while (temp.next != None):
temp = temp.next
temp.next = LinkedList(data)
def get(self):
o = []
temp = self
while (1):
o.append(temp)
if (temp.next == None):
break
temp = temp.next
return o
class myThread(threading.Thread):
def __init__(self, threadID, name, data):
threading.Thread.__init__(self)
self.threadID = threadID
self.name = name
self.person = data
def run(self):
if (self.threadID > 1):
threadLock.acquire()
if ((self.threadID % 2) == 0):
i = (len(self.person) - 1 - 4)
if ((self.threadID % 2) == 1):
i = (len(self.person) - 1 - 3)
self.person[i-1].next = self.person[i+1]
time.sleep(0.1)
self.person.pop(i)
if (self.threadID > 1):
threadLock.release()
threadLock = threading.Lock()
threads = []
person = LinkedList("Bob")
person.add("Charlie")
person.add("Dave")
person.add("Earl")
person.add("Frank")
person.add("George")
person.add("Hal")
person.add("Ian")
person.add("Jon")
print("")
l = person.get()
for i in l:
print(i.data)
print("")
print("Deleting "+l[len(l) - 1 - 4].data+" and "+l[len(l) - 1 - 3].data+" without threadlock")
thread0 = myThread(0, "Thread-0", l)
thread1 = myThread(1, "Thread-1", l)
thread0.start()
thread1.start()
threads.append(thread0)
threads.append(thread1)
for t in threads:
t.join()
print("")
l = person.get()
for i in l:
print(i.data)
print("")
print("Deleting "+l[len(l) - 1 - 4].data+" and "+l[len(l) - 1 - 3].data+" with threadlock")
thread2 = myThread(2, "Thread-0", l)
thread3 = myThread(3, "Thread-1", l)
thread2.start()
thread3.start()
threads.append(thread2)
threads.append(thread3)
for t in threads:
t.join()
print("")
l = person.get()
for i in l:
print(i.data)
print("")
Jon's FOSS Blog 
I get the idea of your post, and find those lines of code very useful, would it be ok if I create a repo on github with these, surely I will send a link to the post,
Ardian
Sure thing, everything I post is intended to be open source friendly and for anyone/everyone to view/copy/modify! 🙂