Notes for 458, 24 March 2008 Threading models Wednesday: Paul Ardis -- parallel clustering algorithms. --------------------- Lauer & Needham: "On the Duality of Operating Systems Structures." Proc. of the 2nd Intl. Symp. on Operating Systems, IRIA, Oct. 1978. Reprinted in OSR 13:2 (Apr. 1979), pp. 3-19. Message-oriented system OS/360 Minix v. procedure-oriented system Windows all commercial Unix variants Example: write to file user space envelope file system memory management system (allocate a buffer) file system disk system (add to queue, schedule completion interrupt) envelope scheduler envelope user space What are goals that might drive choice of system structure? What might constitute tradeoffs? - conceptual clarity Most people seem to find POS clearer, though Tanenbaum would disagree, I think. Explicit coding of the request FSM is a pain. - compartmentalization -- error containment MOS is pretty clearly better here -- no shared data; no process interactions other than message passing - latency POS is usually better here -- that's why most OSes use it (despite arguments of L&N to the contrary) - throughput for a server (different domain than an OS!) MOS is probably better here: better cache and TLB locality - scalability naively, POS seems better here (one thread per request), but the SEDA work would seem to argue otherwise - others? --------------------- SEDA (Welsh et al., SOSP'01) Staged event-driven architecture Assumptions: - You want more active requests than you can accommodate (kernel-supported) processes. - Requests perform several stages; the time consumed by each is workload dependent. - Offered workload is _very_ dynamic. Conclusion: If you want to pipeline effectively, you need to adjust the degree of parallelism in each stage and otherwise explicitly adapt to changes in load. "Load conditioning" via thread pool sizing event batching adaptive load shedding Two main example applications: Haboob web server; GNUtella packet router. Implemented for multiprocessor. --------------------- Capriccio (von Behren et al., SOSP'03) The two key technical innovations: linked stacks, resource-aware schedule via dynamically-discovered blocking graph. Also a thorough (but not new) use of asynchronous I/O. Implemented for uniprocessor only. Count on run-until-block semantics for "free" synchronization. Non-composable. Not clear to what extent they depend on lack of context switches. Perhaps only for "lock" implementation -- RMW w/out expense of CAS. << Everybody understand the synchronous I/O problem? >> Linked stack management is easy if you are willing to create a new frame for every call. The trick in Capriccio is to minimize the number of allocation operations. Can actually improve performance (on a uniprocessor) by improving cache behavior via re-use of stack chunks in different threads. Cf. Lynx, which had cooperative scheduling and used the main stack whenever the compiler could prove that the called routine would not yield. Note that transactions could combine concurrency with "run until block" semantics. Not clear whether this is a good idea. Resource-aware scheduling: when resources are plentiful, preferentially schedule threads that are about to consume them. When scarce, schedule threads that are about to release them. Resources = {heap space, CPU, file descriptors}.