ThreadsAnnouncementsSlide 3Review: ProcessesSlide 5Slide 6Review: Cooperating ProcessesGoals for TodayCase for ParallelismSlide 10Slide 11Parallel ProgramsProcesses OverheadsNeed “Lightweight” ProcessesThreads and ProcessesMultithreaded ProcessesThreads vs. ProcessesSeparating Threads and ProcessesCooperative ThreadsSlide 20Non-Cooperative ThreadsMultithreading modelsKernel ThreadsUser-Level ThreadsSlide 25Example User Thread InterfaceKey Data StructuresMultiplexing User-Level ThreadsUser-Level vs. Kernel ThreadsMany-to-One ModelOne-to-one ModelMany-to-Many ModelTwo-level ModelMultithreading IssuesThread HazardsConcurrency ProblemsSummaryThreadsAnnouncements•CS 4410 Homework is TODAY (11:59pm)–available and turn in via CMS •CS 4411 initial design documents yesterday/today–Project due following next Wednesday, September 17th•Everyone should have access to CMS (http://cms3.csuglab.cornell.edu)–Check and contact me ([email protected]) or Bill Hogan ([email protected]) today if you do not have access to CMS•Also, everyone should have CSUGLab account–Contact Bill or I if you do notAnnouncements•No office hours by me today–However, Nazrul will hold their office hours 1:30-2:30pmReview: Processes•The unit of execution and scheduling•Thread of execution + address space•A task created by the OS, running in a restricted virtual machine environment –a virtual CPU, virtual memory environment, interface to the OS via system calls•Sequential, instruction-at-a-time execution of a program. Operating system abstraction to represent what is needed to run a single, multithreaded program•Program != Process–A process is a program in execution•Abstraction used for protection–Main Memory State (contents of Address Space)•Multiprogramming: overlap IO and CPU•Context Switches are expensiveReview: ProcessesNewReady RunningExitWaitingadmittedinterruptI/O or event waitI/O or event completiondispatchdoneYieldReview: Processes•How does parent know child process has finished if exec does not return?main(int argc, char **argv){ char *myName = argv[1]; char *progName = argv[2]; int cpid = fork(); if (cpid == 0) { printf(“The child of %s is %d\n”, myName, getpid()); execlp(“/bin/ls”, // executable name “ls”, NULL); // null terminated argv printf(“OH NO. THEY LIED TO ME!!!\n”); } else { printf(“My child is %d\n”, cpid); wait(cpid); exit(0); }}Review: Cooperating Processes•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 itGoals for Today•Case for Threads•Thread detailsmain()read_data()for(all data)compute();CreateProcess(write_data());endforCase for Parallelismmain() read_data() for(all data) compute(); write_data(); endforConsider the following code fragment on a dual core CPUfor(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 ParallelismConsider a Web server create a number of process, and for each process do–get network message from client–get URL data from disk–compose response–send responseServer 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 parallelProcesses 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 allocatedCommunicating between processes is costly –most communication goes through the OSNeed “Lightweight” Processes•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•There can be more than one thread in a process, the first thread calls main & has the process’s stack•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•Threads within a process share code/data/heap, share I/O, but each has its own stack & registers•Expensive creation•Expensive context switching•If a process dies, its resources are reclaimed & all threads dieSeparating Threads and Processes•Makes it easier to support multithreaded applications–Different from multiprocessing, multiprogramming, multitasking•Concurrency (multithreading) is useful for:–improving program structure–handling concurrent events (e.g., web requests)–building parallel programs–Resource sharing–Multiprocessor