ThreadsAnnouncementsCooperating ProcessesCase for ParallelismSlide 5Parallel ProgramsProcess OverheadsNeed something more lightweightThreads and ProcessesMultithreaded ProcessesThreads vs. ProcessesConundrum..Thread schedulingCooperative ThreadsNon-Cooperative ThreadsMultithreading modelsKernel ThreadsUser-Level ThreadsMultiplexing User-Level ThreadsMany-to-One ModelOne-to-one ModelMany-to-Many ModelTwo-level ModelUser-Level vs. Kernel ThreadsExample User Thread InterfaceKey Data StructuresMultithreading IssuesThread HazardsConcurrency ProblemsThreadsAnnouncementsCooperating Processes•Last time we discussed how processes can be independent or work cooperatively•Cooperating processes can be used:–to gain speedup by overlapping activities or working in parallel–to better structure an application as set of cooperating processes–to share information between jobs•Sometimes processes are structured as a pipeline–each produces work for the next stage that consumes itConsider the following code fragment on a dual core CPU:for(k = 0; k < n; k++)a[k] = b[k] * c[k] + d[k] * e[k];Instead:CreateProcess(fn, 0, n/2);CreateProcess(fn, n/2, n);fn(l, m)for(k = l; k < m; k++)a[k] = b[k] * c[k] + d[k] * e[k];Case for ParallelismCase for Parallelism•Consider a web server:–Get network message from socket–Get URL data from disk–Compose response–Write compose.Server connections are fast, but client connections may not be (grandma’s modem connection) –Takes server a loooong time to feed the response to grandma–While it’s doing that it can’t service any more requestsParallel Programs•To build parallel programs, such as:–Parallel execution on a multiprocessor–Web server to handle multiple simultaneous web requests •We will need to:–Create several processes that can execute in parallel–Cause each to map to the same address space •because they’re part of the same computation–Give each its starting address and initial parameters–The OS will then schedule these processes in parallelProcess Overheads•A full process includes numerous things:–an address space (defining all the code and data pages)–OS resources and accounting information–a “thread of control”, •defines where the process is currently executing •That is the PC and registersCreating a new process is costly –all of the structures (e.g., page tables) that must be allocatedContext switching is costly –Implict and explicit costs as we talked aboutNeed something more lightweight•What’s similar in these processes?–They all share the same code and data (address space)–They all share the same privileges–They share almost everything in the process•What don’t they share?–Each has its own PC, registers, and stack pointer•Idea: why don’t we separate the idea of process (address space, accounting, etc.) from that of the minimal “thread of control” (PC, SP, registers)?Threads and Processes•Most operating systems therefore support two entities:–the process, •which defines the address space and general process attributes–the thread, •which defines a sequential execution stream within a process•A thread is bound to a single process. –For each process, however, there may be many threads.•Threads are the unit of scheduling •Processes are containers in which threads executeMultithreaded ProcessesThreads vs. Processes•A thread has no data segment or heap•A thread cannot live on its own, it must live within a process•Inexpensive creation•Inexpensive context switching•If a thread dies, its stack is reclaimed•A process has code/data/heap & other segments•There must be at least one thread in a process•Expensive creation•Expensive context switching•If a process dies, its resources are reclaimed & all threads dieConundrum..•Can you achieve parallelism within a process without using threads?Thread schedulingA cooperative thread gets to runs until it decides to give up the CPUmain(){tid t1 = CreateThread(fn, arg);…Yield(t1);}fn(int arg){…Yield(any);}Cooperative Threads•Cooperative threads use non pre-emptive scheduling•Advantages:–Simple•Scientific apps•Disadvantages:–For badly written code•Scheduler gets invoked only when Yield is called •A thread could yield the processor when it blocks for I/ONon-Cooperative Threads•No explicit control passing among threads•Rely on a scheduler to decide which thread to run•A thread can be pre-empted at any point•Often called pre-emptive threads•Most modern thread packages use this approach.Multithreading models•There are actually 2 level of threads:• Kernel threads:– Supported and managed directly by the kernel.• User threads:–Supported above the kernel, and without kernel knowledge.Kernel Threads•Kernel threads may not be as heavy weight as processes, but they still suffer from performance problems:–Any thread operation still requires a system call.–Kernel threads may be overly general •to support needs of different users, languages, etc.–The kernel doesn’t trust the user•there must be lots of checking on kernel callsUser-Level Threads•The thread scheduler is part of a user-level library•Each thread is represented simply by:–PC–Registers–Stack–Small control block•All thread operations are at the user-level:–Creating a new thread–switching between threads–synchronizing between threadsMultiplexing User-Level Threads•The user-level thread package sees a “virtual” processor(s)–it schedules user-level threads on these virtual processors–each “virtual” processor is implemented by a kernel thread (LWP)•The big picture:–Create as many kernel threads as there are processors–Create as many user-level threads as the application needs–Multiplex user-level threads on top of the kernel-level threads•Why not just create as many kernel-level threads as app needs?–Context switching–ResourcesMany-to-One ModelLWPuser-levelthreadsThread creation, scheduling, synchronization done in user space.Mainly used in language systems, portable librariesFast - no system calls requiredFew system dependencies; portableNo parallel execution of threads - can’t exploit multiple CPUsAll threads block when one uses synchronous I/OOne-to-one Model More concurrency Better multiprocessor performance Each user thread requires creation of kernel thread Each thread requires kernel resources; limits number of total
View Full Document
Unlocking...