#!/usr/bin/python """This module is part of Swampy, a suite of programs available from allendowney.com/swampy. Copyright 2011 Allen B. Downey Distributed under the GNU General Public License at gnu.org/licenses/gpl.html. """ import optparse import os import copy import random import sys import string import time # the following definitions can be accessed in the simulator current_thread = None def noop(*args): """A handy function taht does nothing.""" def balk(): """Jumps to the top of the column.""" current_thread.balk() class Semaphore: """Represents a semaphore in the simulator. Maintains a random queue. """ def __init__(self, n=0): self.n = n self.queue = [] def __str__(self): return str(self.n) def wait(self): self.n -= 1 if self.n < 0: self.block() return self.n def block(self): thread = current_thread thread.enqueue() self.queue.append(thread) def signal(self, n=1): for i in range(n): self.n += 1 if self.queue: self.unblock() def unblock(self): """Chooses a random thread and unblocks it.""" thread = random.choice(self.queue) self.queue.remove(thread) thread.dequeue() thread.next_loop() class FifoSemaphore(Semaphore): """Semaphore that implements a FIFO queue.""" def unblock(self): """Chooses the first thread and unblocks it.""" thread = self.queue.pop(0) thread.dequeue() thread.next_loop() class Lightswitch: """Encapsulates the lightswitch pattern.""" def __init__(self): self.counter = 0 self.mutex = Semaphore(1) def lock(self, semaphore): self.mutex.wait() self.counter += 1 if self.counter == 1: semaphore.wait() self.mutex.signal() def unlock(self, semaphore): self.mutex.wait() self.counter -= 1 if self.counter == 0: semaphore.signal() self.mutex.signal() def pid(): """Gets the ID of the current thread.""" return current_thread.name def num_threads(): """Gets the number of threads.""" sync = current_thread.column.p return len(sync.threads) # make globals and locals for the simulator sim_globals = copy.copy(globals()) sim_locals = dict() # anything defined after this point is not available inside the simulator from Tkinter import N, S, E, W, TOP, BOTTOM, LEFT, RIGHT, END from Gui import Gui, GuiCanvas # get the version of Python v = sys.version.split()[0].split('.') major = int(v[0]) if major == 2: all_thread_names = string.uppercase + string.lowercase else: all_thread_names = string.ascii_uppercase + string.ascii_lowercase font = ("Courier", 12) FSU = 9 # FSU, the fundamental Sync unit, # determines the size of most things. class Sync(Gui): """Represents the thread simulator.""" def __init__(self, args=['']): Gui.__init__(self) self.parse_args(args) self.namer = Namer() self.locals = sim_locals self.globals = sim_globals self.views = {} self.w = self self.threads = [] self.running = False self.delay = 0.2 self.setup() self.run_init() for col in self.cols: col.create_thread() def parse_args(self, args): parser = optparse.OptionParser() parser.add_option('-w', '--write', dest='write', action='store_true', default=False, help='Write thread code in code subdirectory?') parser.add_option('-s', '--side', dest='initside', action='/index.cgi/contrast/https://greenteapress.com/thinkpython/code/store_true', default=False, help='Move the initialization code to the left side?') (self.options, args) = parser.parse_args(args) if args: self.filename = args[0] else: self.filename = '' def get_name(self, name=None): return self.namer.next(name) def get_threads(self): return self.threads def set_global(self, **kwds): self.globals.update(kwds) def get_global(self, attr): return self.globals[attr] def destroy(self): """Closes the top window.""" self.running = False Gui.destroy(self) def setup(self): """Makes the GUI.""" if self.filename: self.read_file(self.filename) self.make_columns() if self.options.write: self.write_files(self.filename) return self.topcol = Column(self, n=5) self.colfr = self.fr() self.cols = [Column(self, LEFT, n=5) for i in range(2)] self.bu(side=RIGHT, , command=self.add_col) self.endfr() self.buttons() def buttons(self): """Makes the buttons.""" self.row([1,1,1,1,1]) self.bu(, command=self.run) self.bu(, command=self.random_run) self.bu(, command=self.stop) self.bu(, command=self.step) self.bu(, command=self.random_step) self.endfr() def register(self, thread): """Adds a new thread.""" self.threads.append(thread) def unregister(self, thread): """Removes a thread.""" self.threads.remove(thread) def run(self): """Runs the simulator with round-robin scheduling.""" self.run_helper(self.step) def random_run(self): """Runs the simulator with random scheduling.""" self.run_helper(self.random_step) def run_helper(self, step=None): """Runs the threads until someone clears self.running.""" self.running = True while self.running: step() self.update() time.sleep(self.delay) def step(self): """Advances all the threads in order""" for thread in self.threads: thread.step_loop() def random_step(self): """Advances one random thread.""" threads = [thread for thread in self.threads if not thread.queued] if not threads: print 'There are currently no threads that can run.' return thread = random.choice(threads) thread.step_loop() def stop(self): """Stops running.""" self.running = False def read_file(self, filename): """Read a file that contains code for the simulator to execute. Lines that start with ## do not appear in the display. A line that starts with "## thread" indicates the beginning of a new column of code. Returns a list of blocks where each block is a list of lines. """ def is_new_thread(line): if line[0:2] != '##': return False words = line.strip('#').split() word = words[0].lower() return word == 'thread' self.blocks = [] block = [] self.blocks.append(block) fp = open(filename) for line in fp: line = line.rstrip() if is_new_thread(line): block = [] self.blocks.append(block) else: block.append(line) fp.close() def make_columns(self): """Adds the code in self.blocks to the GUI.""" if not self.blocks: return side = LEFT if self.options.initside else TOP self.topcol = TopColumn(self, side=side) self.topcol.add_rows(self.blocks[0]) self.colfr = self.fr() self.cols = [] self.endfr() for block in self.blocks[1:]: col = self.add_col(0) col.add_rows(block) self.buttons() def write_files(self, filename, dirname='book_code'): """Writes the code into separate files for the init and threads. filename: name of the file we read dirname: name of the destination subdirectory Destination is a subdirectory of the directory the filename is in. """ path, filename = os.path.split(filename) dest = os.path.join(path, dirname, filename) block = self.blocks[0] self.write_file(block, dest, 0) for i, block in enumerate(self.blocks[1:]): self.write_file(block, dest, i+1) def write_file(self, block, filename, suffix=0): trim_block(block) name = '%s.%s' % (filename, str(suffix)) fp = open(name, 'w') for line in block: fp.write(line + '\n') fp.close() def add_col(self, n=5): """Adds a new column of code to the display.""" self.pushfr(self.colfr) col = Column(self, LEFT, n) self.cols.append(col) self.popfr() return col def run_init(self): """Runs the initialization code in the top column.""" if not self.topcol.num_rows(): return print 'running init' self.clear_views() self.views = {} thread = Thread(self.topcol, name='0') while True: thread.step() if thread.row == None: break self.unregister(thread) def update_views(self): """Loops through the views and updates them.""" for key, view in self.views.iteritems(): view.update(self.locals[key]) def clear_views(self): """Loops through the views and clears them.""" for key, view in self.views.iteritems(): view.clear() def qu(self, **options): """Makes a queue.""" return self.widget(QueueCanvas, **options) def subtract(d1, d2): """Subtracts two dictionaries. Returns a new dictionary containing all the keys from d1 that are not in d2. """ d = {} for key in d1: if key not in d2: d[key] = d1[key] return d def diff_dict(d1, d2): """Diffs two dictionaries. Returns two dictionaries: the first contains all the keys from d1 that are not in d2; the second contains all the keys that are in both dictionaries, but which have different values. """ d = {} c = {} for key in d1: if key not in d2: d[key] = d1[key] elif d1[key] is not d2[key]: c[key] = d1[key] return d, c def trim_block(block): """Removes comments from the beginning and empty lines from the end.""" if block and block[0].startswith('#'): block.pop(0) while block and not block[-1].strip(): block.pop(-1) """ The following classes define the composite objects that make up the display: Row, TopRow, Column and TopColumn. They are all subclasses of Widget. """ class Widget: """Superclass of all display objects. Each Widget keeps a reference to its immediate parent Widget (p) and to the top-most thing (w). """ def __init__(self, p, *args, **options): self.p = p self.w = p.w self.setup(*args, **options) class Row(Widget): """A row of code. Each row contains two queues, runnable and queued, and an entry that contains a line of code. """ def setup(self, ): self.tag = None self.fr = self.w.row([0,0,1]) self.queued = self.w.qu(side=LEFT, n=3) self.runnable = self.w.qu(side=LEFT, n=3, label='Run') self.en = self.w.en(side=LEFT, font=font) self.en.bind('', self.keystroke) self.w.endrow() self.put(text) def update(self, val): if self.tag: self.clear() text = str(val) self.tag = self.runnable.display_text(text) def clear(self): self.runnable.delete(self.tag) def keystroke(self, event=None): "resize the entry whenever the user types a character" self.entry_size() def entry_size(self): "resize the entry" text = self.get() width = self.en.cget('width') l = len(text) + 2 if l> width: self.en.configure(width=l) def add_thread(self, thread): self.runnable.add_thread(thread) def remove_thread(self, thread): self.runnable.remove_thread(thread) def enqueue_thread(self, thread): self.queued.add_thread(thread) def dequeue_thread(self, thread): self.queued.remove_thread(thread) def put(self, text): self.en.delete(0, END) self.en.insert(0, text) self.entry_size() def get(self): return self.en.get() class TopRow(Row): """Rows in the initialization code at the top. The top row is special because there is no queue for queued threads, and the "runnable" queue is actually used to display the value of variables. """ def setup(self, text=''): Row.setup(self, text) self.queued.destroy() self.runnable.delete('all') class Column(Widget): """A list of rows and a few buttons.""" def setup(self, side=TOP, n=0, Row=Row): self.fr = self.w.fr(side=side, bd=3) self.Row = Row self.rows = [self.Row(self) for i in range(n)] self.buttons = self.w.row([1,1], side=BOTTOM) self.bu1 = self.w.bu(text='Create thread', command=self.create_thread) self.bu2 = self.w.bu(text='Add row', command=self.add_row) self.w.endrow() self.w.endfr() def num_rows(self): return len(self.rows) def add_rows(self, block, keep_blanks=False): for line in block: if line or keep_blanks: self.add_row(line) def add_row(self, text=''): self.w.pushfr(self.fr) row = self.Row(self, text) self.w.popfr() self.rows.append(row) def create_thread(self): new = Thread(self) return new def next_row(self, row): if row is None: return self.rows[0] index = self.rows.index(row) try: return self.rows[index+1] except IndexError: return None class TopColumn(Column): """The top column where the initialization code is. The top column is different from the other columns in two ways: it has different buttons, and it uses the TopRow constructor to make new rows rather than the Row constructor. """ def setup(self, side=TOP, n=0, Row=TopRow): Column.setup(self, side, n, Row) self.bu1.configure(text='Run initialization', command=self.p.run_init) class QueueCanvas(GuiCanvas): """Displays the runnable and queued threads.""" def __init__(self, w, n=1, label='Queue'): self.n = n self.label = label width = 2 * n * FSU height = 3 * FSU GuiCanvas.__init__(self, w, width=width, height=height, transforms=[]) self.threads = [] self.setup() def setup(self): self.text([3, 15], self.label, font=font, anchor=W, fill='white') def add_thread(self, thread): self.undraw_queue() self.threads.append(thread) self.draw_queue() def remove_thread(self, thread): self.undraw_queue() self.threads.remove(thread) self.draw_queue() def draw_queue(self): x = FSU y = FSU r = 0.9 * FSU for thread in self.threads: self.draw_thread(thread, x, y, r) x += 1.5*r if x> self.get_width(): x = FSU y += 1.5*r def undraw_queue(self): for thread in self.threads: self.delete(thread.tag) def draw_thread(self, thread, x=FSU, y=FSU, r=0.9*FSU): thread.tag = 'Thread' + thread.name self.circle([x, y], r, fill=thread.color, tags=thread.tag) font=('Courier', int(r+3)) self.text([x, y], thread.name, font=font, tags=thread.tag) self.tag_bind(thread.tag, '', thread.step_loop) def undraw_thread(self, thread): self.delete(thread.tag) def display_text(self, text): tag = self.text([15, 15], text, font=font) return tag class Namer(object): def __init__(self): self.names = all_thread_names self.next_name = 0 self.colors = ['red', 'orange', 'yellow', 'greenyellow', 'green', 'mediumseagreen', 'skyblue', 'violet', 'magenta'] self.next_color = 0 def next(self, name=None): if name == None: name = self.names[self.next_name] self.next_name += 1 self.next_name %= len(self.names) color = self.colors[self.next_color] self.next_color += 1 self.next_color %= len(self.colors) return name, color else: return name, 'white' class Namespace: """Used to store thread-local variables. Inside the simulator, self refers to the thread's namespace. """ class Thread: """Represents simulated threads.""" def __init__(self, column, name=None): self.column = column self.sync = column.p self.name, self.color = self.sync.get_name(name) self.namespace = Namespace() self.flag_map = {} self.while_stack = [] self.sync.register(self) self.start() def __str__(self): return '<' + self.name + '>' def enqueue(self): """Puts this thread into queue.""" self.queued = True self.row.remove_thread(self) self.row.enqueue_thread(self) def dequeue(self): """Removes this thread from queue.""" self.queued = False self.row.dequeue_thread(self) self.row.add_thread(self) def jump_to(self, row): """Removes this thread from its current row and moves it to row.""" if self.row: self.row.remove_thread(self) self.row = row if self.row: self.row.add_thread(self) def balk(self): self.row.remove_thread(self) self.row = None def start(self): """Moves this thread to the top of the column.""" self.queued = False self.row = None self.next_loop() def next_loop(self): """Moves to the next row, looping to the top if necessary.""" self.next_row() if self.row == None: self.start() def next_row(self): """Moves this thread to the next row in the column.""" if self.queued: return row = self.column.next_row(self.row) self.jump_to(row) def skip_body(self): """Skips the body of a conditional.""" # get the current line # get the next line # compute the change in indent # find the outdent source = self.row.get() head_indent = self.count_spaces(source) self.next_row() source = self.row.get() body_indent = self.count_spaces(source) indent = body_indent - head_indent if indent <= 0: raise SyntaxError('Body of compound statement must be indented.') while True: self.next_row() if self.row == None: break source = self.row.get() line_indent = self.count_spaces(source) if line_indent <= head_indent: break def count_spaces(self, source): """Returns the number of leading spaces after expanding tabs.""" s = source.expandtabs(4) t = s.lstrip(' ') return len(s) - len(t) def step(self, event=None): """Executes the current line of code, then moves to the next row. The current limitation of this simulator is that each row has to contain a complete Python statement. Also, each line of code is executed atomically. Args: event: unused, provided so that this method can be used as a binding callback Returns: line of code that executed or None """ if self.queued: return None if self.row == None: return None self.check_end_while() source = self.row.get() print self, source before = copy.copy(self.sync.locals) flag = self.exec_line(source, self.sync) # see if any variables were defined or changed after = self.sync.locals defined, changed = diff_dict(after, before) for key in defined: self.sync.views[key] = self.row if defined or changed: self.sync.update_views() # either skip to the next line or to the end of a false conditional if flag: self.next_row() else: self.skip_body() return source def exec_line(self, source, sync): """Runs a line of source code in the context of the given Sync. Args: source: source code from a Row sync: Sync object Returns: if the line is an if statement, returns the result of evaluating the condition """ global current_thread current_thread = self sync.globals['self'] = self.namespace try: s = source.strip() code = compile(s, '', 'exec') exec code in sync.globals, sync.locals return True except SyntaxError as error: # check whether it's a conditional statement keyword = s.split()[0] if keyword in ['if', 'else:', 'while']: flag = self.handle_conditional(keyword, source, sync) return flag else: raise error def handle_conditional(self, keyword, source, sync): """Evaluates the condition part of an if statement. Args: keyword: if, else or while source: source code from a Row sync: Sync object Returns: if the line is an if statement, returns the result of evaluating the condition; otherwise raises a SyntaxError """ s = source.strip() if not s.endswith(':'): raise SyntaxError('Header must end with :') if keyword in ['if']: # evaluate the condition n = len(keyword) condition = s[n:-1].strip() flag = eval(condition, sync.globals, sync.locals) # store the flag indent = self.count_spaces(source) self.flag_map[indent] = flag return flag elif keyword in ['while']: # evaluate the condition n = len(keyword) condition = s[n:-1].strip() flag = eval(condition, sync.globals, sync.locals) if flag: indent = self.count_spaces(source) self.while_stack.append((indent, self.row)) return flag else: assert keyword == 'else:' # see whether the condition was true indent = self.count_spaces(source) try: flag = self.flag_map[indent] return not flag except KeyError: raise SyntaxError('else does not match if') def check_end_while(self): """Check if we are at the end of a while loop. If so, jump to the top. """ if not self.while_stack: return indent, row = self.while_stack[-1] source = self.row.get() if self.count_spaces(source) <= indent: self.while_stack.pop() self.jump_to(row) def step_loop(self, event=None): self.step() if self.row == None: self.start() def run(self): while True: self.step() if self.row == None: break def main(): sync = Sync(sys.argv[1:]) sync.mainloop() if __name__ == '__main__': main()

AltStyle によって変換されたページ (->オリジナル) /