Concurrent ProgrammingHardware ArchitecturesConcurrent SystemsApplication classesConcurrent ProgrammingProcess ConceptProcess StatesProcess Scheduling QueuesThe Thread Model (1)Thread Usage (1)Thread Usage (2)Client and server with threadsAlternative server threading architecturesThreads: MotivationThreadsState associated with processes and threadsThe Thread Model (2)The Thread Model (3)Threadscont’dUser-Level ThreadsImplementing Threads in User SpaceKernel ThreadsImplementing Threads in the KernelHybrid ImplementationsMultithreading ModelsMany-to-OneMany-to-One ModelOne-to-One ModelOne-to-one ModelMany-to-Many ModelMany-to-Many ModelPthreadsJava ThreadsCreating and Using threadsJava thread constructor and management methodsCreating threadsCooperating concurrent processesSynchronization MechanismsRace ConditionsAssignment 11CS 475 - Spring 2003 1Concurrent ProgrammingProf. Sanjeev SetiaConcurrent & Distributed Software SystemsCS 475CS 475 - Spring 2003 2Hardware ArchitecturesUniprocessorsShared-memory multiprocessorsDistributed-memory multicomputersDistributed systems2CS 475 - Spring 2003 3Concurrent SystemsEssential aspects of any concurrent systemExecution context - state of a concurrent entityScheduling - deciding which context will run nextSynchronization - mechanisms that enable execution contexts to coordinate their use of shared resourcesCS 475 - Spring 2003 4Application classesMulti-threaded ProgramsProcesses/Threads on same computerWindow systems, Operating systemsDistributed computingProcesses/Threads on separate computersFile servers, Web serversParallel computingOn same (multiprocessor) or different computersGoal: solve a problem faster or solve a bigger problem in the same time3CS 475 - Spring 2003 5Concurrent ProgrammingProcess = Address space + one thread of control Concurrent program = multiple threads of controlMultiple single-threaded processesMulti-threaded processCS 475 - Spring 2003 6Process ConceptA process includes:program counter code segmentstack segmentdata segmentProcess = Address Space+ One threadofcontrolStackTextHeapAuxiliaryregions02NAddress space4CS 475 - Spring 2003 7Process States Possible process statesrunningblockedreadyTransitions between states shownCS 475 - Spring 2003 8Process Scheduling QueuesReady queue – set of all processes residing in main memory, ready and waiting to execute.Device queues – set of processes waiting for an I/O device.Processes migrate between the various queues during their lifetime.5CS 475 - Spring 2003 9The Thread Model (1)(a) Three processes each with one thread(b) One process with three threadsCS 475 - Spring 2003 10Thread Usage (1)A word processor with three threads6CS 475 - Spring 2003 11Thread Usage (2)A multithreaded Web serverCS 475 - Spring 2003 12Client and server with threadsServerN threadsInput-outputClientThread 2 makesT1Thread 1requests to servergenerates resultsRequestsReceipt &queuing7CS 475 - Spring 2003 13Alternative server threading architectures a. Thread-per-requestb. Thread-per-connection c. Thread-per-objectremoteworkersI/OremoteremoteI/Oper-connection threads per-object threadsobjectsobjectsobjectsCS 475 - Spring 2003 14Threads: MotivationTraditional UNIX processes created and managed by the OS kernel Process creation expensive - fork system call Context switching expensiveCooperating processes - no need for protection (separate address spaces)8CS 475 - Spring 2003 15ThreadsExecute in same address spaceseparate execution stack, share access to code and (global) dataSmaller creation and context-switch timeCan exploit fine-grain concurrencyEasier to write programs that use asynchronous I/O or communicationCS 475 - Spring 2003 16State associated with processes and threadsProcess ThreadAddress space tables Saved processor registersCommunication interfaces, open files Priority and execution state (such asBLOCKED)Semaphores, other synchronizationobjectsSoftware interrupt handling informationList of thread identifiers Execution environment identifierPages of address space resident in memory; hardware cache entries9CS 475 - Spring 2003 17The Thread Model (2)Items shared by all threads in a processItems private to each threadCS 475 - Spring 2003 18The Thread Model (3)Each thread has its own stack10CS 475 - Spring 2003 19Threads cont’dLess protection against programming errorsUser-level vs kernel-level threadskernel not aware of threads created by user-level thread package (e.g. Pthreads), language (e.g. Java)user-level threads typically multiplexed on top of kernel level threads in a user-transparent fashion CS 475 - Spring 2003 20User-Level ThreadsThread management (scheduling, thread creation) done by user-level threads libraryExamples-POSIX Pthreads-Mach C-threads-Solaris threads-Java threads11CS 475 - Spring 2003 21Implementing Threads in User SpaceA user-level threads packageCS 475 - Spring 2003 22Kernel ThreadsSupported by the KernelExamples- Windows 95/98/NT/2000-Solaris- Tru64 UNIX-BeOS- Linux12CS 475 - Spring 2003 23Implementing Threads in the KernelA threads package managed by the kernelCS 475 - Spring 2003 24Hybrid ImplementationsMultiplexing user-level threads onto kernel-level threads13CS 475 - Spring 2003 25Multithreading ModelsMany-to-OneOne-to-OneMany-to-ManyCS 475 - Spring 2003 26Many-to-OneMany user-level threads mapped to single kernel thread.If one user-level thread makes a blocking system call, the entire process is blocked even though other user-level threads may be “ready”Used on systems that do not support kernel threads.14CS 475 - Spring 2003 27Many-to-One ModelCS 475 - Spring 2003 28One-to-One ModelEach user-level thread maps to kernel thread.Examples- Windows 95/98/NT/2000-OS/215CS 475 - Spring 2003 29One-to-one ModelCS 475 - Spring 2003 30Many-to-Many ModelAllows many user level threads to be mapped to many kernel threads.Allows the operating system to create a sufficient number of kernel threads.Solaris 2 Windows NT/2000 with the ThreadFiberpackage16CS 475 - Spring 2003 31Many-to-Many ModelCS 475 - Spring 2003 32Pthreadsa POSIX standard (IEEE 1003.1c) API for thread creation and synchronization.API specifies behavior of the thread library, implementation is up to development of the library.Common in UNIX operating systems.17CS 475 - Spring 2003 33Java