Threads Events and Scheduling Andy Wang COP 5611 Advanced Operating Systems Basic Concept of Threads Processes Thread A sequential execution stream Address space Chunks of memory and everything needed to run a program Process An address space thread s Two types of threads Kernel threads User level threads Kernel vs User Threads OS scheduler only knows about kernel threads user threads processes user kernel kernel threads Characteristics of User Threads User threads Good performance Scheduling involves voluntary yields of processors Sometimes incorrect behaviors A thread blocked on I O may prevent other ready threads from running Kernel knows nothing about the priorities among threads A low priority thread may preempt a high priority thread Characteristics of Kernel Threads Kernel threads each user thread mapped to a kernel thread Correct concurrency semantics Poor performance Scheduling involves kernel crossing One Solution Scheduler Activations Additional interface Thread system can request kernel threads dynamically Thread system can advice kernel scheduler on preemptions Kernel needs to notify the thread system of various events e g blocking via upcalls Kernel needs to make a kernel thread available to activate user level scheduler Why Threads Are A Bad Idea for most purposes by John Ousterhout Threads Grew up in OS world processes Every programmer should be a threads programmer Problem threads are very hard to program Alternative events Claims For most purposes events are better Threads should be used only when true CPU concurrency is needed What Are Threads Shared state memory files etc Threads General purpose solution for managing concurrency Multiple independent execution streams Shared state Pre emptive scheduling Synchronization e g locks conditions What Are Threads Used For Operating systems one kernel thread for each user process Scientific applications one thread per CPU Distributed systems process requests concurrently overlap I Os GUIs Threads correspond to user actions can service display during long running computations Multimedia animations What s Wrong With Threads casual all programmers wizards Visual Basic programmers C programmers C programmers Threads programmers Too hard for most programmers to use Even for experts development is painful Why Threads Are Hard Synchronization Must coordinate access to shared data with locks Forget a lock Corrupted data Deadlock Circular dependencies among locks Each process waits for some other process system hangs thread 1 lock A lock B thread 2 Why Threads Are Hard cont d Hard to debug data and timing dependencies Threads break abstraction can t design modules independently Callbacks don t work with locks T1 T2 deadlock Module A T1 calls Module A deadlock Module B Module B callbacks sleep wakeup T2 Why Threads Are Hard cont d Achieving good performance is hard Simple locking yields low concurrency Fine grain locking reduces performance OSes limit performance context switches Threads not well supported Hard to port threaded code PCs Macs Standard libraries not thread safe Kernel calls window systems not multi threaded Few debugging tools LockLint debuggers Event Driven Programming One execution stream no CPU concurrency Event Loop Register interest in events callbacks Event loop waits for Event Handlers events invokes handlers No preemption of event handlers Handlers generally short lived What Are Events Used For Mostly GUIs One handler for each event press button Handler implements behavior undo delete file etc Distributed systems One handler for each source of input i e socket Handler processes incoming request sends response Event driven I O for I O overlap Problems With Events Long running handlers make application non responsive Fork off subprocesses for long running things e g multimedia use events to find out when done Break up handlers e g event driven I O Periodically call event loop in handler reentrancy adds complexity Can t maintain local state across events handler must return Problems With Events No CPU concurrency not suitable for scientific apps Event driven I O not always well supported e g poor write buffering Events vs Threads Events avoid concurrency as much as possible Easy to get started with events no concurrency no preemption no synchronization no deadlock Use complicated techniques only for unusual cases With threads even the simplest application faces the full complexity Events vs Threads Debugging easier with events Timing dependencies only related to events not to internal scheduling Problems easier to track down slow response to button vs corrupted memory Events vs Threads cont d Events faster than threads on single CPU No locking overheads No context switching Events more portable than threads Threads provide true concurrency Can have long running stateful handlers without freezes Scalable performance on multiple CPUs Should You Abandon Threads No important for high end servers But avoid threads wherever possible Use events not threads for GUIs distributed systems low end servers Only use threads where true CPU Event Driven Handlers concurrency is needed Where threads needed isolate usage in threaded application kernel keep Threaded Kernel most of code single threaded Summary Concurrency is fundamentally hard avoid whenever possible Threads more powerful than events but power is rarely needed Threads are for experts only Use events as primary development tool both GUIs and distributed systems Use threads only for performance critical kernels Process Scheduling Goals Low latency High throughput Fairness Basic Scheduling Approaches FIFO Fair High latency Round robin fair low latency poor throughput Basic Scheduling Approaches STCF SRTCF shortest time remaining time to completion first low latency high throughput unfair Basic Scheduling Approaches Multilevel feedback queues A job starts with the highest priority queue If time slice expires lower the priority by one level If time slice does not expire raise the priority by one level Age long running jobs Lottery Scheduling Claim Priority based schemes are ad hoc Lottery scheduling Randomized scheme Based on a currency abstraction Idea Processes own lottery tickets CPU randomly draws a ticket and execute the corresponding process Properties of Lottery Scheduling Guarantees fairness through probability Guarantees no starvation as long as each process owns one ticket To approximate SRTCF Short jobs get more tickets Long jobs get fewer Examples Each
View Full Document
Unlocking...