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("")
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! 🙂