Coroutines in Assembler

CoRoutine

Coroutines are functions or procedures that save control state between calls (as opposed to, but very similar to, Generators, such as Random Number Generators, that save data state between calls). The most common example is a lexical analyser that behaves differently on different calls because it is tracking e.g. whether it is currently inside a function definition or outside a function definition.

Coroutines are very important as one of the very few examples of a form of concurrency that is useful, and yet constrained enough to completely avoid the typical difficulties (race conditions, deadlock, etc). Synchronization is built-in to the paradigm. It therefore cannot in general replace more general unconstrained forms of concurrency, but for some things it appears to be the ideal solution.

Lex and GNU Flex implement coroutine-based lexical analyzers, as can be seen by their support for entering and leaving user-defined states that allow for state-dependent pattern recognition.

In their most intuitive implementation (e.g. in languages that directly support them), they return control (and optionally a value) to the caller with a Yield statement, similarly to a return from a function, but when called (e.g. with "resume coroutine_name"), they resume execution at the point immediately following the previous yield.

For instance, here's a Coroutine that implements a simple Generator, using a fictitious extension to C:

  int coroutine Generate123() {
	yield 1;  /* Execution begins here upon first call to Generate123 */
	yield 2;  /* execution continues here upon "resume Generate123" */
	yield 3;  /* execution continues here upon second "resume Generate123" */
  }

main() { printf("%d\n", Generate123()); /* prints "1" */ printf("%d\n", resume Generate123()); /* prints "2" */ printf("%d\n", resume Generate123()); /* prints "3" */ }

As someone noted below, they can be used to simulate cooperative multitasking, but this is not their major point. Misunderstanding of coroutines as being a bad version of multithreading has hampered their widespread adoption.

It's worth noting that any direct implementation of a state machine simulates coroutines, or you could say that coroutines directly implement state machines, indicating that they are theoretically both fundamental and well-behaved.

Continuations can be viewed as a generalization of coroutines, in that the behavior of coroutines is typically static and defined at compile time, whereas continuations do not necessarily have such restrictions.

It is nonstandard to spell the word with camel case

Well-known example of problem requiring CoRoutines to implement efficiently moved to SameFringeProblem

---

If you understand continuations (see ContinuationExplanation) then coroutines are just two or more continuations that call each other whenever they block, end, or just feel like being polite. They can simulate a very simple and unstructured form of CooperativeThreading and are explained e.g. in the first volume of TheArtOfComputerProgramming. See ContinuationsAndCoroutines and SchemeCoroutineExample.

... ... ... ...

This is alluded to above.... however, it may be useful to divide coroutines into two categories (I just love creating AdHocTaxonomies?)

• Anonymous coroutines. These are what are used for CooperativeThreading, and other situations where one wants to create multiple independent flows of control. Anonymous coroutines have two operations--create (which creates a new coroutine and gives it code to execute), and transfer; which allows the implementation to select a new coroutine to transfer control to, which it does. Note that transfer in this model takes no arguments--there is no meaningful way to send data to the next context to run, because it is not known which context it will be! In some cases, you might be able to specify what co-routine which runs next - but if you do that, the flows of control aren't really independent any more.
• Directed coroutines. These are used for things like generators/iterators in languages such as IconLanguage and PythonLanguage. Directed coroutines also have two operations - create and transfer, but the transfer operation always takes an argument specifying the coroutine to transfer to; very often it also takes additional arguments allowing data to be passed back and forth between the various cooperating contexts. In PythonLanguage (where these are called generators - see GeneratorsInPython), these are not symmetrical; the generator can pass data back to the parent via an argument to yield (and can only resume the parent context); where as the parent context can communicate with multiple generators (but cannot pass data to them, other than at initialization). Also, the syntax is different; the generator uses the "yield" command to transfer control to the parent; the parent uses the next() method of the generator to transfer control to the generator.

I suspect that one reason coroutines get a bad name is that programmers use one form when they ought to use the other. (Many languages, alas, only provide one form or the other; if either.) Strongly agree.

I am glad to see so much interest in CoRoutines! I maintain that FlowBasedProgramming (FBP) components are coroutines - in fact, one of the products that we developed at IBM Canada based on these concepts did refer to the asynchronously executing components as "coroutines". (When we produced the Japanese documentation, this came out as "koruchin"). FBP components also can be thought of individual mainline programs - they just have "get"s and "put"s where a mainline might have I/O. This means that a conventional single-thread program is an FBP program consisting of a single component. So conventional single-thread programs are a subset of FBP programs - FBP does not remove any capabilities, but in fact adds some rather interesting ones. End of rant! This also means that they provide a natural way to implement the MichaelJackson Methodology (ASIN 0123790506). -- PaulMorrison

More specifically, FlowBasedProgramming components can be coroutines. They can also be threads, processes, etc.

Sorry, what is the exact distinction you are making? I agree FBP components seem to share the nature of several different things one runs into in the literature. One early term that seems a good fit is EwDijkstra's "[cooperating] sequential processes".

That FBP components are not always coroutines.

Doug, maybe you are using a more exact definition of coroutine than I was...? In your view, do coroutines have a different weight from that of threads (and processes)?

Always lighter than processes, sometimes lighter than threads. The lightest of threads are the same thing as coroutines, but with their running controlled by a scheduler, whereas coroutines run when they are called by each other (no scheduler involved).

Processes can often be considered to be threads in separate address spaces.

BTW over the decades there has been considerable variation in terminology concerning the usage of "thread", "process", and "task" (which I don't see anymore, but used to be used to mean either thread or process in some older OS environments). But I am under the impression that terminology has settled down considerably in recent years.

I believe that "coroutine" was defined unambiguously when it was introduced in 1964, and that its meaning hasn't changed since, but that it has sometimes been used loosely rather than exactly, which confuses things.

Thanks, you're right, I was using "coroutine" in a loose sense. BTW "task" is still used in the mainframe environment (IBM's MVS operating system), and refers to a fairly heavy-weight process using preemptive multithreading.

Ah, no wonder; it's been a long while since I've been in stone's throw of MVS.

I am currently doing some experimenting trying to do FBP in that environment - it could be interesting as a way to include processes that are I/O-bound but not FBP-aware (e.g. SQL) in a network without hanging the whole job while SQL does its thing.

That makes sense. So much so that I'm surprised it hadn't come before in your previous work.

Yes, it's odd enough that I needed to think about it... Possible reasons:

• task-based multithreading was more heavy-weight than we could afford, from a performance point of view, plus being more difficult to code (this was 30 years ago...)
• most machines in those days were uniprocessors
• most of our work was in Assembler, which has asynchronous I/O support for what they call "basic" MVS access methods (BSAM, BDAM, VSAM, EXCP), and AMPS (the first implementation of FlowBasedProgramming) had a "wait on ECB" function, so you could suspend an individual component until the ECB was posted
• FBP allows you to support components written in different languages, so even when we added PL/I and COBOL support, we could still use the I/O modules we had before
• we only added SQL support late in the game, and it wasn't used heavily enough that performance became an issue (before IBM dropped the whole FBP idea)

I think that's it. Good question! -- PaulMorrison

---

"The word 'coroutine' was coined by M.E. Conway in 1958, after he had developed the concept, and he first applied it to the construction of an assembly program. Coroutines were independently studied by J. Erdwinn and J. Merner, at about the same time [...] The first published explanation of the coroutine concept appeared much later in Conway's article 'Design of a Separable Transition-Diagram Compiler', CACM 6 (1963), 396-408. Actually a primitive form of coroutine linkage had already been noted briefly as a 'programming tip' in an early UNIVAC publication [...] A suitable notation for coroutines in ALGOL-like languages was introduced in Dahl and Nygaard's SIMULA I [...] and several excellent examples of coroutines (including replicated coroutines) appear in the book Structured Programming [by Dahl, Dijkstra, and Hoare]." (The Art of Computer Programming, volume 1, pp 229-230)

---

See also GeneratorsAreNotCoroutines

Related: ContinuationsAndCoroutines

Processes, Coroutines, and Concurrency Chapter 19

Art of Assembly   Chapter 19-3 explains co-routine concept very nicely

DOS processes, even when using shared memory, suffer from one primary drawback - each program executes to completion before returning control back to the parent process. While this paradigm is suitable for many applications, it certainly does not suffice for all. A common paradigm is for two programs to swap control of the CPU back and forth while executing. This mechanism, slightly different from the subroutine call and return mechanism, is a coroutine.

Before discussing coroutines, it is probably a good idea to provide a solid definition for the term process. In a nutshell, a process is a program that is executing. A program can exist on the disk; processes exist in memory and have a program stack (with return addresses, etc.) associated with them. If there are multiple processes in memory at one time, each process must have its own program stack.

A cocall operation transfers control between two processes. A cocall is effectively a call and a return instruction all rolled into one operation. From the point of view of the process executing the cocall, the cocall operation is equivalent to a procedure call; from the point of view of the processing being called, the cocall operation is equivalent to a return operation. When the second process cocalls the first, control resumes not at the beginning of the first process, but immediately after the cocall operation. If two processes execute a sequence of mutual cocalls, control will transfer between the two processes in the following fashion:
 

Cocalls are quite useful for games where the "players" take turns, following different strategies. The first player executes some code to make its first move, then cocalls the second player and allows it to make a move. After the second player makes its move, it cocalls the first process and gives the first player its second move, picking up immediately after its cocall. This transfer of control bounces back and forth until one player wins.

The 80x86 CPUs do not provide a cocall instruction. However, it is easy to implement cocalls with existing instructions. Even so, there is little need for you to supply your own cocall mechanism, the UCR Standard Library provides a cocall package for 8086, 80186, and 80286 processors. This package includes the pcb (process control block) data structure and three functions you can call: coinit, cocall, and cocalll.

The pcb structure maintains the current state of a process. The pcb maintains all the register values and other accounting information for a process. When a process makes a cocall, it stores the return address for the cocall in the pcb. Later, when some other process cocalls this process, the cocall operation simply reloads the registers, include cs:ip, from the pcb and that returns control to the next instruction after the first process' cocall. The pcb structure takes the following form:
 

pcb             structNextProc        dword   ?       ;Link to next PCB (for multitasking).regsp           word    ?regss           word    ?regip           word    ?regcs           word    ?regax           word    ?regbx           word    ?regcx           word    ?regdx           word    ?regsi           word    ?regdi           word    ?regbp           word    ?regds           word    ?reges           word    ?regflags        word    ?PrcsID          word    ?StartingTime    dword   ?       ;Used for multitasking accounting.StartingDate    dword   ?       ;Used for multitasking accounting.CPUTime         dword   ?       ;Used for multitasking accounting.

Four of these fields (as labelled) exist for preemptive multitasking and have no meaning for coroutines. We will discuss preemptive multitasking in the next section.

There are two important things that should be evident from this structure. First, the main reason the existing Standard Library coroutine support is limited to 16 bit register is because there is only room for the 16 bit versions of each of the registers in the pcb. If you want to support the 80386 and later 32 bit register sets, you would need to modify the pcb structure and the code that saves and restores registers in the pcb.

The second thing that should be evident is that the coroutine code preserves all registers across a cocall. This means you cannot pass information from one process to another in the registers when using a cocall. You will need to pass data between processes in global memory locations. Since coroutines generally exist in the same program, you will not even need to resort to the shared memory techniques. Any variables you declare in your data segment will be visible to all coroutines.
 

Note, by the way, that a program may contain more than two coroutines. If coroutine one cocalls coroutine two, and coroutine two cocalls coroutine three, and then coroutine three cocalls coroutine one, coroutine one picks up immediately after the cocall it made to coroutine two.

Since a cocall effectively returns to the target coroutine, you might wonder what happens on the first cocall to any process. After all, if that process has not executed any code, there is no "return address" where you can resume execution. This is an easy problem to solve, we need only initialize the return address of such a process to the address of the first instruction to execute in that process.

A similar problem exists for the stack. When a program begins execution, the main program (coroutine one) takes control and uses the stack associated with the entire program. Since each process must have its own stack, where do the other coroutines get their stacks?

The easiest way to initialize the stack and initial address for a coroutine is to do this when declaring a pcb for a process. Consider the following pcb variable declaration:
 

ProcessTwo      pcb     {0, offset EndStack2, seg EndStack2,                            offset StartLoc2, seg StartLoc2}

This definition initializes the NextProc field with NULL (the Standard Library coroutine functions do not use this field) and initialize the ss:sp and cs:ip fields with the last address of a stack area (EndStack2) and the first instruction of the process (StartLoc2). Now all you need to do is reserve a reasonable amount of stack storage for the process. You can create multiple stacks in the SHELL.ASM sseg as follows:
 

sseg            segment para stack 'stack'; Stack for process #2:stk2            byte    1024 dup (?)EndStack2       word    ?; Stack for process #3:stk3            byte    1024 dup (?)EndStack3       word    ?; The primary stack for the main program (process #1) must appear at ; the end of sseg.stk             byte    1024 dup (?)sseg            ends

There is the question of "how much space should one reserve for each stack?" This, of course, varies with the application. If you have a simple application that doesn't use recursion or allocate any local variables on the stack, you could get by with as little as 256 bytes of stack space for a process. On the other hand, if you have recursive routines or allocate storage on the stack, you will need considerably more space. For simple programs, 1-8K stack storage should be sufficient. Keep in mind that you can allocate a maximum of 64K in the SHELL.ASM sseg. If you need additional stack space, you will need to up the other stacks in a different segment (they do not need to be in sseg, it's just a convenient place for them) or you will need to allocate the stack space differently.

Note that you do not have to allocate the stack space as an array within your program. You can also allocate stack space dynamically using the Standard Library malloc call. The following code demonstrates how to set up an 8K dynamically allocated stack for the pcb variable Process2:
 

                mov     cx, 8192                malloc                jc      InsufficientRoom                mov     Process2.ss, es                mov     Process2.sp, di

Setting up the coroutines the main program will call is pretty easy. However, there is the issue of setting up the pcb for the main program. You cannot initialize the pcb for the main program the same way you initialize the pcb for the other processes; it is already running and has valid cs:ip and ss:sp values. Were you to initialize the main program's pcb the same way we did for the other processes, the system would simply restart the main program when you make a cocall back to it. To initialize the pcb for the main program, you must use the coinit function. The coinit function expects you to pass it the address of the main program's pcb in the es:di register pair. It initializes some variables internal to the Standard Library so the first cocall operation will save the 80x86 machine state in the pcb you specify by es:di. After the coinit call, you can begin making cocalls to other processes in your program.

To cocall a coroutine, you use the Standard Library cocall function. The cocall function call takes two forms. Without any parameters this function transfers control to the coroutine whose pcb address appears in the es:di register pair. If the address of a pcb appears in the operand field of this instruction, cocall transfers control to the specified coroutine (don't forget, the name of the pcb, not the process, must appear in the operand field).

Coroutines in Z80 assembly language

Comp.compilers Re Assembly verses a high-level language.

[Chapter 8] 8.5 Coroutines it might be interesting to compare with Unix shell implementation.

Etc

Society

Groupthink : Two Party System as Polyarchy : Corruption of Regulators : Bureaucracies : Understanding Micromanagers and Control Freaks : Toxic Managers :   Harvard Mafia : Diplomatic Communication : Surviving a Bad Performance Review : Insufficient Retirement Funds as Immanent Problem of Neoliberal Regime : PseudoScience : Who Rules America : Neoliberalism  : The Iron Law of Oligarchy : Libertarian Philosophy

Quotes

War and Peace : Skeptical Finance : John Kenneth Galbraith :Talleyrand : Oscar Wilde : Otto Von Bismarck : Keynes : George Carlin : Skeptics : Propaganda  : SE quotes : Language Design and Programming Quotes : Random IT-related quotes :  Somerset Maugham : Marcus Aurelius : Kurt Vonnegut : Eric Hoffer : Winston Churchill : Napoleon Bonaparte : Ambrose Bierce :  Bernard Shaw : Mark Twain Quotes

Bulletin:

Vol 25, No.12 (December, 2013) Rational Fools vs. Efficient Crooks The efficient markets hypothesis : Political Skeptic Bulletin, 2013 : Unemployment Bulletin, 2010 :  Vol 23, No.10 (October, 2011) An observation about corporate security departments : Slightly Skeptical Euromaydan Chronicles, June 2014 : Greenspan legacy bulletin, 2008 : Vol 25, No.10 (October, 2013) Cryptolocker Trojan (Win32/Crilock.A) : Vol 25, No.08 (August, 2013) Cloud providers as intelligence collection hubs : Financial Humor Bulletin, 2010 : Inequality Bulletin, 2009 : Financial Humor Bulletin, 2008 : Copyleft Problems Bulletin, 2004 : Financial Humor Bulletin, 2011 : Energy Bulletin, 2010 : Malware Protection Bulletin, 2010 : Vol 26, No.1 (January, 2013) Object-Oriented Cult : Political Skeptic Bulletin, 2011 : Vol 23, No.11 (November, 2011) Softpanorama classification of sysadmin horror stories : Vol 25, No.05 (May, 2013) Corporate bullshit as a communication method  : Vol 25, No.06 (June, 2013) A Note on the Relationship of Brooks Law and Conway Law

History:

Fifty glorious years (1950-2000): the triumph of the US computer engineering : Donald Knuth : TAoCP and its Influence of Computer Science : Richard Stallman : Linus Torvalds  : Larry Wall  : John K. Ousterhout : CTSS : Multix OS Unix History : Unix shell history : VI editor : History of pipes concept : Solaris : MS DOS :  Programming Languages History : PL/1 : Simula 67 : C : History of GCC development :  Scripting Languages : Perl history   : OS History : Mail : DNS : SSH : CPU Instruction Sets : SPARC systems 1987-2006 : Norton Commander : Norton Utilities : Norton Ghost : Frontpage history : Malware Defense History : GNU Screen : OSS early history

Classic books:

The Peter Principle : Parkinson Law : 1984 : The Mythical Man-Month :  How to Solve It by George Polya : The Art of Computer Programming : The Elements of Programming Style : The Unix Hater’s Handbook : The Jargon file : The True Believer : Programming Pearls : The Good Soldier Svejk : The Power Elite

Most popular humor pages:

Manifest of the Softpanorama IT Slacker Society : Ten Commandments of the IT Slackers Society : Computer Humor Collection : BSD Logo Story : The Cuckoo's Egg : IT Slang : C++ Humor : ARE YOU A BBS ADDICT? : The Perl Purity Test : Object oriented programmers of all nations : Financial Humor : Financial Humor Bulletin, 2008 : Financial Humor Bulletin, 2010 : The Most Comprehensive Collection of Editor-related Humor : Programming Language Humor : Goldman Sachs related humor : Greenspan humor : C Humor : Scripting Humor : Real Programmers Humor : Web Humor : GPL-related Humor : OFM Humor : Politically Incorrect Humor : IDS Humor : "Linux Sucks" Humor : Russian Musical Humor : Best Russian Programmer Humor : Microsoft plans to buy Catholic Church : Richard Stallman Related Humor : Admin Humor : Perl-related Humor : Linus Torvalds Related humor : PseudoScience Related Humor : Networking Humor : Shell Humor : Financial Humor Bulletin, 2011 : Financial Humor Bulletin, 2012 : Financial Humor Bulletin, 2013 : Java Humor : Software Engineering Humor : Sun Solaris Related Humor : Education Humor : IBM Humor : Assembler-related Humor : VIM Humor : Computer Viruses Humor : Bright tomorrow is rescheduled to a day after tomorrow : Classic Computer Humor

The Last but not Least Technology is dominated by two types of people: those who understand what they do not manage and those who manage what they do not understand ~Archibald Putt. Ph.D

The statements, views and opinions presented on this web page are those of the author (or referenced source) and are not endorsed by, nor do they necessarily reflect, the opinions of the Softpanorama society. We do not warrant the correctness of the information provided or its fitness for any purpose. The site uses AdSense so you need to be aware of Google privacy policy. You you do not want to be tracked by Google please disable Javascript for this site. This site is perfectly usable without Javascript.

Last modified: March 12, 2019