CSc 520 — Principles of Programming Languages32 : Control Structures — CoroutinesChristian CollbergDepartment of Computer ScienceUniversity of [email protected] 2008 Christian CollbergApril 9, 20081 Coroutines• Coroutines are supported by Simula and Modula-2. They are similar to Java’s threads, except theprogrammer has to explicitly transfer control from one execution context to another.• Thus, like threads several coroutines can exist simultaneously 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 the coroutine C, at the location where C last leftoff.2 Coroutines vs. threads• Coroutines are like threads, except that with a coroutine you have to explicitly say when you want totransfer from one “process” to another.• If you have access to coroutines, you can build a thread library on top of it.• A thread library makes sure that each process gets its fair share of the CPU. With coroutines we’reforced to handle this ourselves, by making sure that we transfer control “often enough” to all coroutines.3 Example• The next slide shows an example from Scott where two coroutines execute “concurrently”, by explicitlytransferring control between each other.• In the example one coroutine displays a moving screen-saver, the other walks the file-system to checkfor corrupt files.14 Example. . .var us, cfs: coroutine;coroutine update_screen() {...detachloop {... transfer(cfs) ...}}coroutine check_file_system() { ... }main () { ... }5 Coroutines. . .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);}Coroutines in Modula-26 Coroutines in Modula-2• Modula-2’s system module provides two functions to create and transfer between 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 *)2• The first time TRANSFER is called source will be instantiated to the main (outermost) coroutine.7 Coroutines 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;3Coroutines in Ruby8 Coroutines in Ruby• Ruby doesn’t have co-routines per-se, but Marc De Scheemaecker 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)9 Coroutines 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?end10 Example• c1 prints all letters, c2 prints the numbers 1 . . . 26. After printing a letter c1 swithces to c2, and viceversa.$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 ", i4$c2.switch($c1)endend11 Example. . .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 2612 Iterators using coroutines• If you have coroutines, implementing iterators b ecomes trivial! You need one coroutine to generate thevalues, and another as the main loop.• Here, the iterate function creates a coroutine that generates the elements of an array. For simplicity,we store 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)endendreturn cend13 Iterators using coroutines. . .• Here’s the main routine. It creates a coroutine, calls iterate to create the iterator coroutine, andthen switches 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"end5• (This code is buggy. Please fix it for me!)6Implementing coroutines14 Implementing coroutines• Each coroutine needs its own stack.• Each coroutine is represented by a context block. In our implementation, the context block containsonly one value: the coroutine’s stack pointer.15 Implementing coroutines. . .• When coroutine C2 issues a transfer(C1), the following happens:1. transfer pushes all registers (including the return address RA on C2’s stack.2. transfer saves the current stackpointer SP into C2’s context block.3. transfer sets currentcoroutine to C1.4. transfer sets SP to the stackpointer that was saved 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, which has the effect of setting PC to RA, the locationwhere C1 wants to continue executing.16 Implementing coroutines. . .current_coroutine := ...PC := ...SP :=transfer(C) {push R1,R2,RA*current_coroutine := SPcurrent_coroutine := CSP := *Cpop R1,R2,RAreturn}717 Step 1: Coroutine C2 is runningtransfer(C1)C1’s stackC2’s stackSP1C1’s context blockC2’s context blockSP2current_coroutinePCSPR2R1RA........................................C1’s code........................................C2’s codetransfer(C2)18 Step 2: Control is transferred to C2transfer(C2)C1’s stackC2’s stackSP1C1’s context blockC2’s context blockSP2current_coroutinePCSPR1R2RA........................................C1’s code........................................C2’s codetransfer(C1)19 Readings and References• Read Scott, pp. 453–459• http://www.mathematik.uni-ulm.de/oberon/0.5/articles/coroutines.html•
View Full Document
Unlocking...