Concurrent Programing:Why you should care, deeply1Student Questions1. it is said that user-level threads are implemented by a library at the user-level. we have POSIX for starting user threads in C++ How do I POSIX for starting user threads in C++. How do I start a kernel thread? 2. we all know that creating a kernel thread is more expensive than creating a user thread. can you explain more about _how_ it is expensive? ¾ System call 1,000s of cycles¾Function call 10s of cycles2¾Function call 10s of cycles3. Why is creating a process more expensive than creating a kernel thread?Uniprocessor Performance Not Scaling10000-11/780)20%/year101001000rmance (vs. VAX-25% /year52% /year20% /year311978 1980 1982 1984 1986 1988 1990 1992 1994 1996 1998 2000 2002 2004 2006PerfoGraph by Dave PattersonPower and heat lay waste to processor makersIntel P4 (2000-2007)¾ 1.3GHz to 3.8GHz, 31 stage pipeline¾ “Prescott” in 02/04 was too hot. Needed 5.2GHz to beat 2.6GHz AthalonIntel Pentium Core, (2006-)¾ 1.06GHz to 3GHz, 14 stage pipeline¾ Based on mobile (Pentium M) micro-architecture Power efficient2% of electricity in the U.S. feeds computers4% o e ec c y e U S eeds co pu e s¾ Doubled in last 5 yearsWhat about Moore’s law?5Number of transistors double every 24 months¾ Not performance!Architectural trends that favor multicorePower is a first class design constraint¾ Performance per watt the important metricLeakage power significant with small transisitorsLeakage power significant with small transisitors¾ Chip dissipates power even when idle!Small transistors fail more frequently¾ Lower yield, or CPUs that fail?Wires are slow¾ Light in vacuum can travel ~1m in 1 cycle at 3GHz¾Motivates multicore designs (simpler lower-power cores)6¾Motivates multicore designs (simpler, lower-power cores)Quantum effectsMotivates multicore designs (simpler, lower-power cores)Multicores are here, and coming fast!4 cores in 2007 16 cores in 2009 80 cores in 20??Sun RockIntel TeraFLOPAMD Quad Core7Sun Rock“[AMD] quad-core processors … are just the beginning….”http://www.amd.com“Intel has more than 15 multi-core related projects underway”http://www.intel.com Intel TeraFLOPAMD Quad CoreMulticore programming will be in demandHardware manufacturers betting big on multicoreSoftware developers are neededWriting concurrent programs is not easyWriting concurrent programs is not easyYou will learn how to do it in this class8Concurrency ProblemOrder of thread execution is non-deterministic¾ MultiprocessingA system may contain multiple processorsÎcooperatingA system may contain multiple processors Îcooperating threads/processes can execute simultaneously¾ Multi-programming Thread/process execution can be interleaved because of time-slicingOperations often consist of multiple, visible steps¾ Example: x = x + 1 is not a single operation read x from memory into a registerThread 29 increment register store register back to memoryGoal:¾ Ensure that your concurrent program works under ALL possible interleavingreadincrementstoreQuestionsDo the following either completely succeed or completely fail?Writing an 8bit byte to memoryWriting an 8-bit byte to memory¾ A. Yes B. NoCreating a file¾ A. Yes B. NoWriting a 512-byte disk sector¾ A. Yes B. No 10Sharing among threads increases performance…int a = 1, b = 2;main() {C(f)CreateThread(fn1, 4);CreateThread(fn2, 5);}fn1(int arg1) {if(a) b++; }fn2(int arg1) {What are the value of a & bat the end of execution?11a = arg1;}Sharing among theads increases performance, but can lead to problems!!int a = 1, b = 2;main() {C(f)CreateThread(fn1, 4);CreateThread(fn2, 5);}fn1(int arg1) {if(a) b++; }fn2(int arg1) {What are the values of a & bat the end of execution?12a = 0;}Some More ExamplesWhat are the possible values of x in these cases?Thread1: x = 1; Thread2: x = 2;Initially y = 10;Thread1: x = y + 1; Thread2: y = y * 2;13Initially x = 0;Thread1: x = x + 1; Thread2: x = x + 2;Critical SectionsA critical section is an abstraction¾ Consists of a number of consecutive program instructions¾ Usually, crit sec are mutually exclusive and can wait/signalLater, we will talk about atomicity and isolationLater, we will talk about atomicity and isolationCritical sections are used frequently in an OS to protect data structures (e.g., queues, shared variables, lists, …)A critical section implementation must be:¾ Correct: the system behaves as if only 1 thread can execute in the critical section at any given time¾ Efficient: getting into and out of critical section must be fast. Critical sections should be as short as possible.14¾ Concurrency control: a good implementation allows maximum concurrency while preserving correctness¾ Flexible: a good implementation must have as few restrictions as practically possibleThe Need For Mutual ExclusionRunning multiple processes/threads in parallel increases performanceSome computer resources cannot be accessed bySome computer resources cannot be accessed by multiple threads at the same time¾ E.g., a printer can’t print two documents at onceMutual exclusion is the term to indicate that some resource can only be used by one thread at a time¾ Active thread excludes its peersFor shared memory architectures data structures are15For shared memory architectures, data structures are often mutually exclusive¾ Two threads adding to a linked list can corrupt the listExclusion Problems, Real Life ExampleImagine multiple chefs in the same kitchen¾ Each chef follows a different recipeChef 1Chef 1¾ Grab butter, grab salt, do other stuffChef 2¾ Grab salt, grab butter, do other stuffWhat if Chef 1 grabs the butter and Chef 2 grabs the salt?¾Yll t h th ( t t i lti )16¾Yell at each other (not a computer science solution)¾ Chef 1 grabs salt from Chef 2 (preempt resource)¾ Chefs all grab ingredients in the same order Current best solution, but difficult as recipes get complex Ingredient like cheese might be sans refrigeration for a whileThe Need To WaitVery often, synchronization consists of one thread waiting for another to make a condition true¾Master tells worker a request has arrived¾Master tells worker a request has arrived¾ Cleaning thread waits until all lanes are coloredUntil condition is true, thread can sleep¾ Ties synchronization to schedulingMutual exclusion for data structure¾ Code can wait (await)¾Another thread signals (notify)17¾Another thread signals (notify)Even more real life,