6.824 2001 Lecture 3: Async Programming Intro Talked about thread stacks and execution contexts yesterday Deferred discussion of blocking systems calls Today, O/S support for non-blocking calls, and event waiting How to use in user threads and libasync implementation Also discuss async programming techniques What do we want? System calls that don't block read, open, stat, ... Unified method to wait for completion Why are non-blocking system calls hard in general? Typical system call implementation, inside the kernel: [Example 1] Can we just return instead of wait_for_buf? no. Might block in alloc_buf, start_disk. Need a context (stack, PC) in which to execute. Usually executes in the "kernel half" of the process. Every process has a user stack and a kernel stack. If non-blocking, where does this execute? Where is intermediate state (e.g. b) stored until completion? Lesson: no *general* way to make existing system calls non-blocking. It's easier to provide blocking kernel threads! Then just fork a new thread if you want non-blocking call... Maybe design a new O/S with atomic system call interface. Maybe all interaction via message queues to server threads. So it's too late for a general solution in UNIX. Unix system calls mostly like sys_read() example. Non-blocking didn't make sense 30 years ago anyway: Disk I/O relatively much faster than CPU. Communication I/O is special in UNIX. Sockets, pipes, terminals. Network support in early 80s required more sophisticated interfaces. telnet &c must wait for two input sources: net and terminal. So support for events was mandatory. This is the select() &c in the Using TCP Through Sockets handout. Why non-blocking I/O is easy for communication. Socket reads are essentially atomic -- one step. Data has already arrived, or not; read() doesn't have to pull data. [Example 2] No state needs to be stored across blocking wait. Nothing needs to be done to ask for data to arrive. Easy to modify to just return a "would block" notification. Program can call read() again, no problem. When data is finally buffered, it will work. This is true for all communcation-like read()s: network sockets, pipes, terminals, mouse Program can mark file descriptor as "non blocking". What about waiting for events -- input on comms fd's. For above reasons, only needs to work w/ sockets/pipes/&c. So file-descriptor oriented -- no general event waiting. select() You give it a list of file descriptors and a time. Returns when one is readable, or the time has expired. Tells you which fd's were readable. select() blocks (if timeout > 0) to avoid wasteful polling. Condition is actually "read() would not block"; might be EOF. You can wait for readable and/or writeable. Why select() for writing? All communcation fd's have buffered output. To keep devices busy while application does something else. Output buffers have finite size. write() ordinarily blocks if buffer is full; waits for drain. You can make non-blocking, but need to be notified... How to use non-blocking system calls and select()? Simple plan: At each place your code knows it wants to wait for two things, use select(). This is how ssh, telnet, &c work. But your program may be modular! One part wants to wait for input from fd1 An unrelated part wants to wait for input from fd2 How to do both without modules knowing too much about each other? Option 1: user-level threads, with fake read(). [Example 3] Option 2: async programming library. A lot like threads, but upside-down: threads: threads call scheduler loop (thread_schedule). async: scheduler loop (amain) calls callbacks. [Example 4] Simpler than user threads. Flash paper shows async is more efficient, too. But there are some costs. How do async programs maintain state? Ordinary programs, and threads, use variables. Which persist across function calls, and blocking operations. Since they are stored on the stack. Async programs can't keep state on the stack. Since each callback must return immediately. wrap(fn, a, b) generates a closure. That is, a function pointer plus an environment of saved values. Transformation of ordinary code: [Example 5] Into async-style code: Need to split f2, since read() blocks. Thus need to split f1. How to remember second half of f1? And cause it to execute after second half of f2? Don't want to specialize f2... [Example 6] The cb being passed to fn() is a continuation! Why do we supply reference counted garbage collection in libasync? In the ordinary code, z and x are saved across calls on the stack. Space for those values is freed automatically on function return. In the async code, stack not available for that kind of use. Values are stored in the closures created by wrap(). How do we know when we've used a callback the last time? That's why they're reference counted. Of course, we still have a problem with disk operations.