2/458: Parallel and Distributed Systems Jan. 28, 2008 If you don't have a twiki account, create one: http://www.cs.rochester.edu/twiki/bin/view/TWiki/TWikiRegistration Research accounts should be working (for all but the two students to whom I sent mail) by tomorrow at the latest. Log in and set up your favorite environment. Note that the Linux machines do not share file systems with sync/swym. First assignment is on the web; handed-in portion due Wed. << should I extend that? >> ------------------------------- Implementation of threads kernel threads, kernel processes, LWPs, and user-level threads issues to be balanced kernel entry/exit overhead heavyweight state page tables, swap space file descriptors, I/O state (cwd, pending requests) accounting information (uid, gid, priority) blocking in the kernel Coroutines As in Simula and Modula-2. Covered in section 8.6 in PLP. Multiple execution contexts, only one of which is active. transfer(other): save all callee-saves registers, including ra and fp *current := sp current := other sp := *current restore all callee-saves registers (including ra, but NOT sp!) return (into different coroutine!) Other and current are pointers to CONTEXT BLOCKs. Contains sp; may contain other stuff as well (priority, I/O status, accounting info, etc.) No need to change PC; always changes at the same place. Create new coroutine in a state that looks like it's blocked in transfer. (Or maybe let it execute and then "detach". That's basically early reply.) Run-until block threads on a single process. PLP sections 12.2.4, 12.3.2, and 12.3.3. Need to get rid of explicit argument to transfer. Ready list data structure: threads that are runnable but not running. reschedule: t : cb := dequeue(ready_list) transfer(t) To do this safely, we need to save 'current' somewhere. Two ways to do this. Suppose we're just relinquishing the processor for the sake of fairness (as in MacOS or Windows 3.1): yield: enqueue(ready_list, current) reschedule Now suppose we're implementing synchronization: sleep_on(q) enqueue(q, current) reschedule Some other thread/process will move us to the ready list when we can continue. Preemption Use timer interrupts (in OS) or signals (in library package) to trigger involuntary yields. Requires that we protect the scheduler data structures: yield: disable_signals enqueue(ready_list, current) reschedule re-enable_signals Note that reschedule takes us to a different thread, possibly in code other than yield. Invariant: EVERY CALL to reschedule must be made with signals disabled, and must re-enable them upon its return. (This can be factored differently if desired. E.g. confine synchronization to individual routines, but pass helper routines as args) disable_signals if not sleep_on re-enable signals Multiprocessors Disabling signals doesn't suffice: yield: disable_signals acquire(scheduler_lock) // spin lock enqueue(ready_list, current) reschedule release(scheduler_lock) re-enable_signals disable_signals acquire(scheduler_lock) // spin lock if not sleep_on release(scheduler_lock) re-enable signals ------------------------------------ Anderson et al. (IEEE Trans. on Computers, Dec. 1989) raises issues of locality per-processor data structures granularity of parallelism tradeoff between throughput and latency large critical sections are good for best-case latency (low locking overhead) but bad for throughput (low parallelism) lock overhead the preemption problem for spin locks optimizations allocate stacks lazily cache memory blocks of common sizes (smart malloc) local free lists balancing mechanism required among nodes everybody understand why? can be done with CAS or LL/SC; don't need locks queue of idle processors, in addition to queue of waiting threads "processors searching for work" v. "work searching for processors" This can also be done lock-free, as described in Bill Scherer's paper at PPoPP'05, and adopted for JSR 1.6 per-processor ready lists to avoid contention on central list downside: have to search around (O(P)) when local list is empty questions: How big should a stack be? Is locality more or less important than it was in 1989? Why? ------------------------------------ posix threads (pthreads) ------------------------------------ First assignment: pthreads For Monday 28 Jan.: log on to SunFire, make sure account works, create a program that launches N pthreads that print their id and halt. For Wednesday 30 Jan.: share a counter. Have each thread increment the counter multiple times, under control of various locks (or none). pthread_mutex TAS TATAS ticket MCS (FAI) (chaotic access) Try different numbers of threads, both less and more than number of processors. Plot the results. Write an explanation/discussion of the results. Send writeup to the TA for grading.