CoroutinesCoroutines vs. threadsExampleExampleldots Coroutinesldots Coroutines in Modula-2Coroutines in Modula-2Coroutines in Modula-2ldots Coroutines in RubyCoroutines in RubyCoroutines in RubyExampleExampleldots Iterators using coroutinesIterators using coroutinesldots Implementing coroutinesImplementing coroutinesImplementing coroutinesldots Implementing coroutinesldots Step 1: Coroutine { t C2} is runningStep 2: Control is transferred to { t C2}Readings and References520 —Spring 2008 — 32CSc 520Principles of ProgrammingLanguages32 : Control Structures — CoroutinesChristian [email protected] of Computer ScienceUniversity of ArizonaCopyrightc 2008 Christian Collberg[1]520 —Spring 2008 — 32CoroutinesCoroutines are supported by Simula and Modula-2.They are similar to Java’s threads, except theprogrammer has to explicitly transfer control from oneexecution context to another.Thus, like threads several coroutines can existsimultaneously but unlike threads there is no centralscheduler that decides which coroutine should run next.A coroutine is represented by a closure.A special operation transfer(C) shifts control to thecoroutineC, at the location where C last left off.[2]520 —Spring 2008 — 32Coroutines vs. threadsCoroutines are like threads, except that with a coroutineyou have to explicitly say when you want to transferfrom one “process” to another.If you have access to coroutines, you can build a threadlibrary on top of it.A thread library makes sure that each process gets itsfair share of the CPU. With coroutines we’re forced tohandle this ourselves, by making sure that we transfercontrol “often enough” to all coroutines.[3]520 —Spring 2008 — 32ExampleThe next slide shows an example from Scott where twocoroutines execute “concurrently”, by explicitlytransferring control between each other.In the example one coroutine displays a movingscreen-saver, the other walks the file-system to checkfor corrupt files.[4]520 —Spring 2008 — 32Example...var us, cfs: coroutine;coroutine update_screen() {...detachloop {... transfer(cfs) ...}}coroutine check_file_system() { ... }main () { ... }[5]520 —Spring 2008 — 32Coroutines...coroutine check_file_system() {...detachfor all files do {... transfer(cfs)... transfer(cfs)... transfer(cfs) ...}}main () {us := new update_screen();cfs := new check_file_system();transfer(us);}[6]520 —Spring 2008 — 32Coroutines in Modula-2[7]520 —Spring 2008 — 32Coroutines in Modula-2Modula-2’s system module provides two functions to create and transferbetween coroutines:PROCEDURE NEWPROCESS(proc: PROC; (*The procedure*)addr: ADDRESS; (*The stack*)size: CARDINAL; (*The stack size*)VAR new: ADDRESS); (*The coroutine*)PROCEDURE TRANSFER(VAR source: ADDRESS; (*Current coroutine*)VAR destination: ADDRESS); (*New coroutine*)The first time TRANSFER is called source will be instantiated tothe main (outermost) coroutine.[8]520 —Spring 2008 — 32Coroutines in Modula-2...VAR crparams: CoroutineParameters;source: ADDRESS; (*current coroutine is called by this*)newcr: ADDRESS; (*coroutine just created by NEWPROCESS*)PROCEDURE Coroutine;VAR myparams: CoroutineParameters;BEGINmyparams := crparams;TRANSFER(newcr, source); (*return to calling coroutine*)(*rest of coroutine*)END Coroutine;PROCEDURE Setup(params: CoroutineParameters; proc: PROC);BEGINNEWPROCESS(proc, addr, size, newcr);crparams := params; TRANSFER(source, newcr);END Setup;[9]520 —Spring 2008 — 32Coroutines in Ruby[10]520 —Spring 2008 — 32Coroutines in RubyRuby doesn’t have co-routines per-se, but Marc DeScheemaecker has a simple library that we can use.class Coroutine# Creates a coroutine. The associated block# does not run yet.def initialize(&block)# Starts the block. It’s an error to call# this method on a coroutine that has# already been started.def start# Switches context to another coroutine. You# need to call this method on the current coroutine.def switch(coroutine)[11]520 —Spring 2008 — 32Coroutines in Ruby...# Returns true if the associated block is# started and has not yet finisheddef running?# Returns true if the associated block is# finisheddef finished?end[12]520 —Spring 2008 — 32Examplec1 prints all letters, c2 prints the numbers 1 . . . 26. Afterprinting a letter c1 swithces to c2, and vice versa.$c1 = Coroutine::new dofor i in ’a’..’z’ doprintf "%s ", i$c1.switch($c2)endend$c2 = Coroutine::new dofor i in 1..26 doprintf "%i ", i$c2.switch($c1)endend[13]520 —Spring 2008 — 32Example...Running the example:$c1.startprintf "\n"yields the resulta 1 b 2 c 3 d 4 e 5 f 6 g 7 h 8 i 9 j 10k 11 l 12 m 13 n 14 o 15 p 16 q 17 r 18s 19 t 20 u 21 v 22 w 23 x 24 y 25 z 26[14]520 —Spring 2008 — 32Iterators using coroutinesIf you have coroutines, implementing iterators becomestrivial! You need one coroutine to generate the values,and another as the main loop.Here, the iterate function creates a coroutine thatgenerates the elements of an array. For simplicity, westore the result in a global variable $result:$result = 0def iterate(arr,other)c = Coroutine::new doi = 0while i < arr.length$result = arr[i]i += 1c.switch(other)endend[15]520 —Spring 2008 — 32Iterators using coroutines...Here’s the main routine. It creates a coroutine, callsiterate to create the iterator coroutine, and thenswitches back and forth until the iterator is done:main = Coroutine::new doa = [1,2,3]iter = iterate(a,main)while not iter.finished?main.switch(iter)printf "%i ", $resultendprintf "\n"end(This code is buggy. Please fix it for me!)[16]520 —Spring 2008 — 32Implementing coroutines[17]520 —Spring 2008 — 32Implementing coroutinesEach coroutine needs its own stack.Each coroutine is represented by a context block. In ourimplementation, the context block contains only onevalue: the coroutine’s stack pointer.[18]520 —Spring 2008 — 32Implementing coroutines...When coroutine C2 issues a transfer(C1), thefollowing happens:1. transfer pushes all registers (including the returnaddress RA on C2’s stack.2. transfer saves the current stackpointer SP intoC2’s context block.3. transfer sets currentcoroutine to C1.4. transfer sets SP to the stackpointer that wassaved in C1’s context block.5. transfer pops all saved registers off of C1’s stack,including the old return address, RA.6. transfer does a normal procedure return, whichhas the effect of setting PC to RA, the location whereC1 wants to continue executing.[19]520
View Full Document
Unlocking...